aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/linux/interval_tree.h27
-rw-r--r--lib/Kconfig.debug12
-rw-r--r--lib/Makefile4
-rw-r--r--lib/interval_tree.c159
-rw-r--r--lib/interval_tree_test_main.c105
-rw-r--r--lib/prio_tree.c4
-rw-r--r--lib/prio_tree_test.c106
7 files changed, 417 insertions, 0 deletions
diff --git a/include/linux/interval_tree.h b/include/linux/interval_tree.h
new file mode 100644
index 000000000000..724556aa3c95
--- /dev/null
+++ b/include/linux/interval_tree.h
@@ -0,0 +1,27 @@
1#ifndef _LINUX_INTERVAL_TREE_H
2#define _LINUX_INTERVAL_TREE_H
3
4#include <linux/rbtree.h>
5
6struct interval_tree_node {
7 struct rb_node rb;
8 unsigned long start; /* Start of interval */
9 unsigned long last; /* Last location _in_ interval */
10 unsigned long __subtree_last;
11};
12
13extern void
14interval_tree_insert(struct interval_tree_node *node, struct rb_root *root);
15
16extern void
17interval_tree_remove(struct interval_tree_node *node, struct rb_root *root);
18
19extern struct interval_tree_node *
20interval_tree_iter_first(struct rb_root *root,
21 unsigned long start, unsigned long last);
22
23extern struct interval_tree_node *
24interval_tree_iter_next(struct interval_tree_node *node,
25 unsigned long start, unsigned long last);
26
27#endif /* _LINUX_INTERVAL_TREE_H */
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index a4e5d93b0f41..ee9f030b6951 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1289,6 +1289,18 @@ config RBTREE_TEST
1289 A benchmark measuring the performance of the rbtree library. 1289 A benchmark measuring the performance of the rbtree library.
1290 Also includes rbtree invariant checks. 1290 Also includes rbtree invariant checks.
1291 1291
1292config PRIO_TREE_TEST
1293 tristate "Prio tree test"
1294 depends on m && DEBUG_KERNEL
1295 help
1296 A benchmark measuring the performance of the prio tree library
1297
1298config INTERVAL_TREE_TEST
1299 tristate "Interval tree test"
1300 depends on m && DEBUG_KERNEL
1301 help
1302 A benchmark measuring the performance of the interval tree library
1303
1292config PROVIDE_OHCI1394_DMA_INIT 1304config PROVIDE_OHCI1394_DMA_INIT
1293 bool "Remote debugging over FireWire early on boot" 1305 bool "Remote debugging over FireWire early on boot"
1294 depends on PCI && X86 1306 depends on PCI && X86
diff --git a/lib/Makefile b/lib/Makefile
index f49445d26b65..26f578bf616a 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -141,6 +141,10 @@ $(foreach file, $(libfdt_files), \
141lib-$(CONFIG_LIBFDT) += $(libfdt_files) 141lib-$(CONFIG_LIBFDT) += $(libfdt_files)
142 142
143obj-$(CONFIG_RBTREE_TEST) += rbtree_test.o 143obj-$(CONFIG_RBTREE_TEST) += rbtree_test.o
144obj-$(CONFIG_PRIO_TREE_TEST) += prio_tree_test.o
145obj-$(CONFIG_INTERVAL_TREE_TEST) += interval_tree_test.o
146
147interval_tree_test-objs := interval_tree_test_main.o interval_tree.o
144 148
145hostprogs-y := gen_crc32table 149hostprogs-y := gen_crc32table
146clean-files := crc32table.h 150clean-files := crc32table.h
diff --git a/lib/interval_tree.c b/lib/interval_tree.c
new file mode 100644
index 000000000000..6fd540b1e499
--- /dev/null
+++ b/lib/interval_tree.c
@@ -0,0 +1,159 @@
1#include <linux/init.h>
2#include <linux/interval_tree.h>
3
4/* Callbacks for augmented rbtree insert and remove */
5
6static inline unsigned long
7compute_subtree_last(struct interval_tree_node *node)
8{
9 unsigned long max = node->last, subtree_last;
10 if (node->rb.rb_left) {
11 subtree_last = rb_entry(node->rb.rb_left,
12 struct interval_tree_node, rb)->__subtree_last;
13 if (max < subtree_last)
14 max = subtree_last;
15 }
16 if (node->rb.rb_right) {
17 subtree_last = rb_entry(node->rb.rb_right,
18 struct interval_tree_node, rb)->__subtree_last;
19 if (max < subtree_last)
20 max = subtree_last;
21 }
22 return max;
23}
24
25RB_DECLARE_CALLBACKS(static, augment_callbacks, struct interval_tree_node, rb,
26 unsigned long, __subtree_last, compute_subtree_last)
27
28/* Insert / remove interval nodes from the tree */
29
30void interval_tree_insert(struct interval_tree_node *node,
31 struct rb_root *root)
32{
33 struct rb_node **link = &root->rb_node, *rb_parent = NULL;
34 unsigned long start = node->start, last = node->last;
35 struct interval_tree_node *parent;
36
37 while (*link) {
38 rb_parent = *link;
39 parent = rb_entry(rb_parent, struct interval_tree_node, rb);
40 if (parent->__subtree_last < last)
41 parent->__subtree_last = last;
42 if (start < parent->start)
43 link = &parent->rb.rb_left;
44 else
45 link = &parent->rb.rb_right;
46 }
47
48 node->__subtree_last = last;
49 rb_link_node(&node->rb, rb_parent, link);
50 rb_insert_augmented(&node->rb, root, &augment_callbacks);
51}
52
53void interval_tree_remove(struct interval_tree_node *node,
54 struct rb_root *root)
55{
56 rb_erase_augmented(&node->rb, root, &augment_callbacks);
57}
58
59/*
60 * Iterate over intervals intersecting [start;last]
61 *
62 * Note that a node's interval intersects [start;last] iff:
63 * Cond1: node->start <= last
64 * and
65 * Cond2: start <= node->last
66 */
67
68static struct interval_tree_node *
69subtree_search(struct interval_tree_node *node,
70 unsigned long start, unsigned long last)
71{
72 while (true) {
73 /*
74 * Loop invariant: start <= node->__subtree_last
75 * (Cond2 is satisfied by one of the subtree nodes)
76 */
77 if (node->rb.rb_left) {
78 struct interval_tree_node *left =
79 rb_entry(node->rb.rb_left,
80 struct interval_tree_node, rb);
81 if (start <= left->__subtree_last) {
82 /*
83 * Some nodes in left subtree satisfy Cond2.
84 * Iterate to find the leftmost such node N.
85 * If it also satisfies Cond1, that's the match
86 * we are looking for. Otherwise, there is no
87 * matching interval as nodes to the right of N
88 * can't satisfy Cond1 either.
89 */
90 node = left;
91 continue;
92 }
93 }
94 if (node->start <= last) { /* Cond1 */
95 if (start <= node->last) /* Cond2 */
96 return node; /* node is leftmost match */
97 if (node->rb.rb_right) {
98 node = rb_entry(node->rb.rb_right,
99 struct interval_tree_node, rb);
100 if (start <= node->__subtree_last)
101 continue;
102 }
103 }
104 return NULL; /* No match */
105 }
106}
107
108struct interval_tree_node *
109interval_tree_iter_first(struct rb_root *root,
110 unsigned long start, unsigned long last)
111{
112 struct interval_tree_node *node;
113
114 if (!root->rb_node)
115 return NULL;
116 node = rb_entry(root->rb_node, struct interval_tree_node, rb);
117 if (node->__subtree_last < start)
118 return NULL;
119 return subtree_search(node, start, last);
120}
121
122struct interval_tree_node *
123interval_tree_iter_next(struct interval_tree_node *node,
124 unsigned long start, unsigned long last)
125{
126 struct rb_node *rb = node->rb.rb_right, *prev;
127
128 while (true) {
129 /*
130 * Loop invariants:
131 * Cond1: node->start <= last
132 * rb == node->rb.rb_right
133 *
134 * First, search right subtree if suitable
135 */
136 if (rb) {
137 struct interval_tree_node *right =
138 rb_entry(rb, struct interval_tree_node, rb);
139 if (start <= right->__subtree_last)
140 return subtree_search(right, start, last);
141 }
142
143 /* Move up the tree until we come from a node's left child */
144 do {
145 rb = rb_parent(&node->rb);
146 if (!rb)
147 return NULL;
148 prev = &node->rb;
149 node = rb_entry(rb, struct interval_tree_node, rb);
150 rb = node->rb.rb_right;
151 } while (prev == rb);
152
153 /* Check if the node intersects [start;last] */
154 if (last < node->start) /* !Cond1 */
155 return NULL;
156 else if (start <= node->last) /* Cond2 */
157 return node;
158 }
159}
diff --git a/lib/interval_tree_test_main.c b/lib/interval_tree_test_main.c
new file mode 100644
index 000000000000..b25903987f7a
--- /dev/null
+++ b/lib/interval_tree_test_main.c
@@ -0,0 +1,105 @@
1#include <linux/module.h>
2#include <linux/interval_tree.h>
3#include <linux/random.h>
4#include <asm/timex.h>
5
6#define NODES 100
7#define PERF_LOOPS 100000
8#define SEARCHES 100
9#define SEARCH_LOOPS 10000
10
11static struct rb_root root = RB_ROOT;
12static struct interval_tree_node nodes[NODES];
13static u32 queries[SEARCHES];
14
15static struct rnd_state rnd;
16
17static inline unsigned long
18search(unsigned long query, struct rb_root *root)
19{
20 struct interval_tree_node *node;
21 unsigned long results = 0;
22
23 for (node = interval_tree_iter_first(root, query, query); node;
24 node = interval_tree_iter_next(node, query, query))
25 results++;
26 return results;
27}
28
29static void init(void)
30{
31 int i;
32 for (i = 0; i < NODES; i++) {
33 u32 a = prandom32(&rnd), b = prandom32(&rnd);
34 if (a <= b) {
35 nodes[i].start = a;
36 nodes[i].last = b;
37 } else {
38 nodes[i].start = b;
39 nodes[i].last = a;
40 }
41 }
42 for (i = 0; i < SEARCHES; i++)
43 queries[i] = prandom32(&rnd);
44}
45
46static int interval_tree_test_init(void)
47{
48 int i, j;
49 unsigned long results;
50 cycles_t time1, time2, time;
51
52 printk(KERN_ALERT "interval tree insert/remove");
53
54 prandom32_seed(&rnd, 3141592653589793238ULL);
55 init();
56
57 time1 = get_cycles();
58
59 for (i = 0; i < PERF_LOOPS; i++) {
60 for (j = 0; j < NODES; j++)
61 interval_tree_insert(nodes + j, &root);
62 for (j = 0; j < NODES; j++)
63 interval_tree_remove(nodes + j, &root);
64 }
65
66 time2 = get_cycles();
67 time = time2 - time1;
68
69 time = div_u64(time, PERF_LOOPS);
70 printk(" -> %llu cycles\n", (unsigned long long)time);
71
72 printk(KERN_ALERT "interval tree search");
73
74 for (j = 0; j < NODES; j++)
75 interval_tree_insert(nodes + j, &root);
76
77 time1 = get_cycles();
78
79 results = 0;
80 for (i = 0; i < SEARCH_LOOPS; i++)
81 for (j = 0; j < SEARCHES; j++)
82 results += search(queries[j], &root);
83
84 time2 = get_cycles();
85 time = time2 - time1;
86
87 time = div_u64(time, SEARCH_LOOPS);
88 results = div_u64(results, SEARCH_LOOPS);
89 printk(" -> %llu cycles (%lu results)\n",
90 (unsigned long long)time, results);
91
92 return -EAGAIN; /* Fail will directly unload the module */
93}
94
95static void interval_tree_test_exit(void)
96{
97 printk(KERN_ALERT "test exit\n");
98}
99
100module_init(interval_tree_test_init)
101module_exit(interval_tree_test_exit)
102
103MODULE_LICENSE("GPL");
104MODULE_AUTHOR("Michel Lespinasse");
105MODULE_DESCRIPTION("Interval Tree test");
diff --git a/lib/prio_tree.c b/lib/prio_tree.c
index 8d443af03b4c..4e0d2edff2b4 100644
--- a/lib/prio_tree.c
+++ b/lib/prio_tree.c
@@ -14,6 +14,7 @@
14#include <linux/init.h> 14#include <linux/init.h>
15#include <linux/mm.h> 15#include <linux/mm.h>
16#include <linux/prio_tree.h> 16#include <linux/prio_tree.h>
17#include <linux/export.h>
17 18
18/* 19/*
19 * A clever mix of heap and radix trees forms a radix priority search tree (PST) 20 * A clever mix of heap and radix trees forms a radix priority search tree (PST)
@@ -241,6 +242,7 @@ struct prio_tree_node *prio_tree_insert(struct prio_tree_root *root,
241 BUG(); 242 BUG();
242 return NULL; 243 return NULL;
243} 244}
245EXPORT_SYMBOL(prio_tree_insert);
244 246
245/* 247/*
246 * Remove a prio_tree_node @node from a radix priority search tree @root. The 248 * Remove a prio_tree_node @node from a radix priority search tree @root. The
@@ -290,6 +292,7 @@ void prio_tree_remove(struct prio_tree_root *root, struct prio_tree_node *node)
290 while (cur != node) 292 while (cur != node)
291 cur = prio_tree_replace(root, cur->parent, cur); 293 cur = prio_tree_replace(root, cur->parent, cur);
292} 294}
295EXPORT_SYMBOL(prio_tree_remove);
293 296
294static void iter_walk_down(struct prio_tree_iter *iter) 297static void iter_walk_down(struct prio_tree_iter *iter)
295{ 298{
@@ -464,3 +467,4 @@ repeat:
464 467
465 goto repeat; 468 goto repeat;
466} 469}
470EXPORT_SYMBOL(prio_tree_next);
diff --git a/lib/prio_tree_test.c b/lib/prio_tree_test.c
new file mode 100644
index 000000000000..c26084ddc6a4
--- /dev/null
+++ b/lib/prio_tree_test.c
@@ -0,0 +1,106 @@
1#include <linux/module.h>
2#include <linux/prio_tree.h>
3#include <linux/random.h>
4#include <asm/timex.h>
5
6#define NODES 100
7#define PERF_LOOPS 100000
8#define SEARCHES 100
9#define SEARCH_LOOPS 10000
10
11static struct prio_tree_root root;
12static struct prio_tree_node nodes[NODES];
13static u32 queries[SEARCHES];
14
15static struct rnd_state rnd;
16
17static inline unsigned long
18search(unsigned long query, struct prio_tree_root *root)
19{
20 struct prio_tree_iter iter;
21 unsigned long results = 0;
22
23 prio_tree_iter_init(&iter, root, query, query);
24 while (prio_tree_next(&iter))
25 results++;
26 return results;
27}
28
29static void init(void)
30{
31 int i;
32 for (i = 0; i < NODES; i++) {
33 u32 a = prandom32(&rnd), b = prandom32(&rnd);
34 if (a <= b) {
35 nodes[i].start = a;
36 nodes[i].last = b;
37 } else {
38 nodes[i].start = b;
39 nodes[i].last = a;
40 }
41 }
42 for (i = 0; i < SEARCHES; i++)
43 queries[i] = prandom32(&rnd);
44}
45
46static int prio_tree_test_init(void)
47{
48 int i, j;
49 unsigned long results;
50 cycles_t time1, time2, time;
51
52 printk(KERN_ALERT "prio tree insert/remove");
53
54 prandom32_seed(&rnd, 3141592653589793238ULL);
55 INIT_PRIO_TREE_ROOT(&root);
56 init();
57
58 time1 = get_cycles();
59
60 for (i = 0; i < PERF_LOOPS; i++) {
61 for (j = 0; j < NODES; j++)
62 prio_tree_insert(&root, nodes + j);
63 for (j = 0; j < NODES; j++)
64 prio_tree_remove(&root, nodes + j);
65 }
66
67 time2 = get_cycles();
68 time = time2 - time1;
69
70 time = div_u64(time, PERF_LOOPS);
71 printk(" -> %llu cycles\n", (unsigned long long)time);
72
73 printk(KERN_ALERT "prio tree search");
74
75 for (j = 0; j < NODES; j++)
76 prio_tree_insert(&root, nodes + j);
77
78 time1 = get_cycles();
79
80 results = 0;
81 for (i = 0; i < SEARCH_LOOPS; i++)
82 for (j = 0; j < SEARCHES; j++)
83 results += search(queries[j], &root);
84
85 time2 = get_cycles();
86 time = time2 - time1;
87
88 time = div_u64(time, SEARCH_LOOPS);
89 results = div_u64(results, SEARCH_LOOPS);
90 printk(" -> %llu cycles (%lu results)\n",
91 (unsigned long long)time, results);
92
93 return -EAGAIN; /* Fail will directly unload the module */
94}
95
96static void prio_tree_test_exit(void)
97{
98 printk(KERN_ALERT "test exit\n");
99}
100
101module_init(prio_tree_test_init)
102module_exit(prio_tree_test_exit)
103
104MODULE_LICENSE("GPL");
105MODULE_AUTHOR("Michel Lespinasse");
106MODULE_DESCRIPTION("Prio Tree test");
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-02 09:32:41 -0400