aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorMichel Lespinasse <walken@google.com>2012-10-08 19:31:30 -0400
committerLinus Torvalds <torvalds@linux-foundation.org>2012-10-09 03:22:40 -0400
commit147e615f83c2c36caf89e7a3bf78090ade6f266c (patch)
tree0cd64fd67f4b55bbe364217911a8100827c8b04f /lib
parent85d3a316c714197f94e75c1e5b2d37607d66e5de (diff)
prio_tree: remove
After both prio_tree users have been converted to use red-black trees, there is no need to keep around the prio tree library anymore. Signed-off-by: Michel Lespinasse <walken@google.com> Cc: Rik van Riel <riel@redhat.com> Cc: Hillf Danton <dhillf@gmail.com> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: Catalin Marinas <catalin.marinas@arm.com> Cc: Andrea Arcangeli <aarcange@redhat.com> Cc: David Woodhouse <dwmw2@infradead.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig.debug6
-rw-r--r--lib/Makefile3
-rw-r--r--lib/prio_tree.c455
-rw-r--r--lib/prio_tree_test.c106
4 files changed, 1 insertions, 569 deletions
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index ee9f030b6951..a6e7e7741523 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1289,12 +1289,6 @@ 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 1292config INTERVAL_TREE_TEST
1299 tristate "Interval tree test" 1293 tristate "Interval tree test"
1300 depends on m && DEBUG_KERNEL 1294 depends on m && DEBUG_KERNEL
diff --git a/lib/Makefile b/lib/Makefile
index 26f578bf616a..3128e357e286 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -9,7 +9,7 @@ endif
9 9
10lib-y := ctype.o string.o vsprintf.o cmdline.o \ 10lib-y := ctype.o string.o vsprintf.o cmdline.o \
11 rbtree.o radix-tree.o dump_stack.o timerqueue.o\ 11 rbtree.o radix-tree.o dump_stack.o timerqueue.o\
12 idr.o int_sqrt.o extable.o prio_tree.o \ 12 idr.o int_sqrt.o extable.o \
13 sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \ 13 sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \
14 proportions.o flex_proportions.o prio_heap.o ratelimit.o show_mem.o \ 14 proportions.o flex_proportions.o prio_heap.o ratelimit.o show_mem.o \
15 is_single_threaded.o plist.o decompress.o 15 is_single_threaded.o plist.o decompress.o
@@ -141,7 +141,6 @@ $(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 144obj-$(CONFIG_INTERVAL_TREE_TEST) += interval_tree_test.o
146 145
147interval_tree_test-objs := interval_tree_test_main.o interval_tree.o 146interval_tree_test-objs := interval_tree_test_main.o interval_tree.o
diff --git a/lib/prio_tree.c b/lib/prio_tree.c
deleted file mode 100644
index bba37148c15e..000000000000
--- a/lib/prio_tree.c
+++ /dev/null
@@ -1,455 +0,0 @@
1/*
2 * lib/prio_tree.c - priority search tree
3 *
4 * Copyright (C) 2004, Rajesh Venkatasubramanian <vrajesh@umich.edu>
5 *
6 * This file is released under the GPL v2.
7 *
8 * Based on the radix priority search tree proposed by Edward M. McCreight
9 * SIAM Journal of Computing, vol. 14, no.2, pages 257-276, May 1985
10 *
11 * 02Feb2004 Initial version
12 */
13
14#include <linux/init.h>
15#include <linux/mm.h>
16#include <linux/prio_tree.h>
17#include <linux/export.h>
18
19/*
20 * A clever mix of heap and radix trees forms a radix priority search tree (PST)
21 * which is useful for storing intervals, e.g, we can consider a vma as a closed
22 * interval of file pages [offset_begin, offset_end], and store all vmas that
23 * map a file in a PST. Then, using the PST, we can answer a stabbing query,
24 * i.e., selecting a set of stored intervals (vmas) that overlap with (map) a
25 * given input interval X (a set of consecutive file pages), in "O(log n + m)"
26 * time where 'log n' is the height of the PST, and 'm' is the number of stored
27 * intervals (vmas) that overlap (map) with the input interval X (the set of
28 * consecutive file pages).
29 *
30 * In our implementation, we store closed intervals of the form [radix_index,
31 * heap_index]. We assume that always radix_index <= heap_index. McCreight's PST
32 * is designed for storing intervals with unique radix indices, i.e., each
33 * interval have different radix_index. However, this limitation can be easily
34 * overcome by using the size, i.e., heap_index - radix_index, as part of the
35 * index, so we index the tree using [(radix_index,size), heap_index].
36 *
37 * When the above-mentioned indexing scheme is used, theoretically, in a 32 bit
38 * machine, the maximum height of a PST can be 64. We can use a balanced version
39 * of the priority search tree to optimize the tree height, but the balanced
40 * tree proposed by McCreight is too complex and memory-hungry for our purpose.
41 */
42
43/*
44 * The following macros are used for implementing prio_tree for i_mmap
45 */
46
47static void get_index(const struct prio_tree_root *root,
48 const struct prio_tree_node *node,
49 unsigned long *radix, unsigned long *heap)
50{
51 *radix = node->start;
52 *heap = node->last;
53}
54
55static unsigned long index_bits_to_maxindex[BITS_PER_LONG];
56
57void __init prio_tree_init(void)
58{
59 unsigned int i;
60
61 for (i = 0; i < ARRAY_SIZE(index_bits_to_maxindex) - 1; i++)
62 index_bits_to_maxindex[i] = (1UL << (i + 1)) - 1;
63 index_bits_to_maxindex[ARRAY_SIZE(index_bits_to_maxindex) - 1] = ~0UL;
64}
65
66/*
67 * Maximum heap_index that can be stored in a PST with index_bits bits
68 */
69static inline unsigned long prio_tree_maxindex(unsigned int bits)
70{
71 return index_bits_to_maxindex[bits - 1];
72}
73
74static void prio_set_parent(struct prio_tree_node *parent,
75 struct prio_tree_node *child, bool left)
76{
77 if (left)
78 parent->left = child;
79 else
80 parent->right = child;
81
82 child->parent = parent;
83}
84
85/*
86 * Extend a priority search tree so that it can store a node with heap_index
87 * max_heap_index. In the worst case, this algorithm takes O((log n)^2).
88 * However, this function is used rarely and the common case performance is
89 * not bad.
90 */
91static struct prio_tree_node *prio_tree_expand(struct prio_tree_root *root,
92 struct prio_tree_node *node, unsigned long max_heap_index)
93{
94 struct prio_tree_node *prev;
95
96 if (max_heap_index > prio_tree_maxindex(root->index_bits))
97 root->index_bits++;
98
99 prev = node;
100 INIT_PRIO_TREE_NODE(node);
101
102 while (max_heap_index > prio_tree_maxindex(root->index_bits)) {
103 struct prio_tree_node *tmp = root->prio_tree_node;
104
105 root->index_bits++;
106
107 if (prio_tree_empty(root))
108 continue;
109
110 prio_tree_remove(root, root->prio_tree_node);
111 INIT_PRIO_TREE_NODE(tmp);
112
113 prio_set_parent(prev, tmp, true);
114 prev = tmp;
115 }
116
117 if (!prio_tree_empty(root))
118 prio_set_parent(prev, root->prio_tree_node, true);
119
120 root->prio_tree_node = node;
121 return node;
122}
123
124/*
125 * Replace a prio_tree_node with a new node and return the old node
126 */
127struct prio_tree_node *prio_tree_replace(struct prio_tree_root *root,
128 struct prio_tree_node *old, struct prio_tree_node *node)
129{
130 INIT_PRIO_TREE_NODE(node);
131
132 if (prio_tree_root(old)) {
133 BUG_ON(root->prio_tree_node != old);
134 /*
135 * We can reduce root->index_bits here. However, it is complex
136 * and does not help much to improve performance (IMO).
137 */
138 root->prio_tree_node = node;
139 } else
140 prio_set_parent(old->parent, node, old->parent->left == old);
141
142 if (!prio_tree_left_empty(old))
143 prio_set_parent(node, old->left, true);
144
145 if (!prio_tree_right_empty(old))
146 prio_set_parent(node, old->right, false);
147
148 return old;
149}
150
151/*
152 * Insert a prio_tree_node @node into a radix priority search tree @root. The
153 * algorithm typically takes O(log n) time where 'log n' is the number of bits
154 * required to represent the maximum heap_index. In the worst case, the algo
155 * can take O((log n)^2) - check prio_tree_expand.
156 *
157 * If a prior node with same radix_index and heap_index is already found in
158 * the tree, then returns the address of the prior node. Otherwise, inserts
159 * @node into the tree and returns @node.
160 */
161struct prio_tree_node *prio_tree_insert(struct prio_tree_root *root,
162 struct prio_tree_node *node)
163{
164 struct prio_tree_node *cur, *res = node;
165 unsigned long radix_index, heap_index;
166 unsigned long r_index, h_index, index, mask;
167 int size_flag = 0;
168
169 get_index(root, node, &radix_index, &heap_index);
170
171 if (prio_tree_empty(root) ||
172 heap_index > prio_tree_maxindex(root->index_bits))
173 return prio_tree_expand(root, node, heap_index);
174
175 cur = root->prio_tree_node;
176 mask = 1UL << (root->index_bits - 1);
177
178 while (mask) {
179 get_index(root, cur, &r_index, &h_index);
180
181 if (r_index == radix_index && h_index == heap_index)
182 return cur;
183
184 if (h_index < heap_index ||
185 (h_index == heap_index && r_index > radix_index)) {
186 struct prio_tree_node *tmp = node;
187 node = prio_tree_replace(root, cur, node);
188 cur = tmp;
189 /* swap indices */
190 index = r_index;
191 r_index = radix_index;
192 radix_index = index;
193 index = h_index;
194 h_index = heap_index;
195 heap_index = index;
196 }
197
198 if (size_flag)
199 index = heap_index - radix_index;
200 else
201 index = radix_index;
202
203 if (index & mask) {
204 if (prio_tree_right_empty(cur)) {
205 INIT_PRIO_TREE_NODE(node);
206 prio_set_parent(cur, node, false);
207 return res;
208 } else
209 cur = cur->right;
210 } else {
211 if (prio_tree_left_empty(cur)) {
212 INIT_PRIO_TREE_NODE(node);
213 prio_set_parent(cur, node, true);
214 return res;
215 } else
216 cur = cur->left;
217 }
218
219 mask >>= 1;
220
221 if (!mask) {
222 mask = 1UL << (BITS_PER_LONG - 1);
223 size_flag = 1;
224 }
225 }
226 /* Should not reach here */
227 BUG();
228 return NULL;
229}
230EXPORT_SYMBOL(prio_tree_insert);
231
232/*
233 * Remove a prio_tree_node @node from a radix priority search tree @root. The
234 * algorithm takes O(log n) time where 'log n' is the number of bits required
235 * to represent the maximum heap_index.
236 */
237void prio_tree_remove(struct prio_tree_root *root, struct prio_tree_node *node)
238{
239 struct prio_tree_node *cur;
240 unsigned long r_index, h_index_right, h_index_left;
241
242 cur = node;
243
244 while (!prio_tree_left_empty(cur) || !prio_tree_right_empty(cur)) {
245 if (!prio_tree_left_empty(cur))
246 get_index(root, cur->left, &r_index, &h_index_left);
247 else {
248 cur = cur->right;
249 continue;
250 }
251
252 if (!prio_tree_right_empty(cur))
253 get_index(root, cur->right, &r_index, &h_index_right);
254 else {
255 cur = cur->left;
256 continue;
257 }
258
259 /* both h_index_left and h_index_right cannot be 0 */
260 if (h_index_left >= h_index_right)
261 cur = cur->left;
262 else
263 cur = cur->right;
264 }
265
266 if (prio_tree_root(cur)) {
267 BUG_ON(root->prio_tree_node != cur);
268 __INIT_PRIO_TREE_ROOT(root, root->raw);
269 return;
270 }
271
272 if (cur->parent->right == cur)
273 cur->parent->right = cur->parent;
274 else
275 cur->parent->left = cur->parent;
276
277 while (cur != node)
278 cur = prio_tree_replace(root, cur->parent, cur);
279}
280EXPORT_SYMBOL(prio_tree_remove);
281
282static void iter_walk_down(struct prio_tree_iter *iter)
283{
284 iter->mask >>= 1;
285 if (iter->mask) {
286 if (iter->size_level)
287 iter->size_level++;
288 return;
289 }
290
291 if (iter->size_level) {
292 BUG_ON(!prio_tree_left_empty(iter->cur));
293 BUG_ON(!prio_tree_right_empty(iter->cur));
294 iter->size_level++;
295 iter->mask = ULONG_MAX;
296 } else {
297 iter->size_level = 1;
298 iter->mask = 1UL << (BITS_PER_LONG - 1);
299 }
300}
301
302static void iter_walk_up(struct prio_tree_iter *iter)
303{
304 if (iter->mask == ULONG_MAX)
305 iter->mask = 1UL;
306 else if (iter->size_level == 1)
307 iter->mask = 1UL;
308 else
309 iter->mask <<= 1;
310 if (iter->size_level)
311 iter->size_level--;
312 if (!iter->size_level && (iter->value & iter->mask))
313 iter->value ^= iter->mask;
314}
315
316/*
317 * Following functions help to enumerate all prio_tree_nodes in the tree that
318 * overlap with the input interval X [radix_index, heap_index]. The enumeration
319 * takes O(log n + m) time where 'log n' is the height of the tree (which is
320 * proportional to # of bits required to represent the maximum heap_index) and
321 * 'm' is the number of prio_tree_nodes that overlap the interval X.
322 */
323
324static struct prio_tree_node *prio_tree_left(struct prio_tree_iter *iter,
325 unsigned long *r_index, unsigned long *h_index)
326{
327 if (prio_tree_left_empty(iter->cur))
328 return NULL;
329
330 get_index(iter->root, iter->cur->left, r_index, h_index);
331
332 if (iter->r_index <= *h_index) {
333 iter->cur = iter->cur->left;
334 iter_walk_down(iter);
335 return iter->cur;
336 }
337
338 return NULL;
339}
340
341static struct prio_tree_node *prio_tree_right(struct prio_tree_iter *iter,
342 unsigned long *r_index, unsigned long *h_index)
343{
344 unsigned long value;
345
346 if (prio_tree_right_empty(iter->cur))
347 return NULL;
348
349 if (iter->size_level)
350 value = iter->value;
351 else
352 value = iter->value | iter->mask;
353
354 if (iter->h_index < value)
355 return NULL;
356
357 get_index(iter->root, iter->cur->right, r_index, h_index);
358
359 if (iter->r_index <= *h_index) {
360 iter->cur = iter->cur->right;
361 iter_walk_down(iter);
362 return iter->cur;
363 }
364
365 return NULL;
366}
367
368static struct prio_tree_node *prio_tree_parent(struct prio_tree_iter *iter)
369{
370 iter->cur = iter->cur->parent;
371 iter_walk_up(iter);
372 return iter->cur;
373}
374
375static inline int overlap(struct prio_tree_iter *iter,
376 unsigned long r_index, unsigned long h_index)
377{
378 return iter->h_index >= r_index && iter->r_index <= h_index;
379}
380
381/*
382 * prio_tree_first:
383 *
384 * Get the first prio_tree_node that overlaps with the interval [radix_index,
385 * heap_index]. Note that always radix_index <= heap_index. We do a pre-order
386 * traversal of the tree.
387 */
388static struct prio_tree_node *prio_tree_first(struct prio_tree_iter *iter)
389{
390 struct prio_tree_root *root;
391 unsigned long r_index, h_index;
392
393 INIT_PRIO_TREE_ITER(iter);
394
395 root = iter->root;
396 if (prio_tree_empty(root))
397 return NULL;
398
399 get_index(root, root->prio_tree_node, &r_index, &h_index);
400
401 if (iter->r_index > h_index)
402 return NULL;
403
404 iter->mask = 1UL << (root->index_bits - 1);
405 iter->cur = root->prio_tree_node;
406
407 while (1) {
408 if (overlap(iter, r_index, h_index))
409 return iter->cur;
410
411 if (prio_tree_left(iter, &r_index, &h_index))
412 continue;
413
414 if (prio_tree_right(iter, &r_index, &h_index))
415 continue;
416
417 break;
418 }
419 return NULL;
420}
421
422/*
423 * prio_tree_next:
424 *
425 * Get the next prio_tree_node that overlaps with the input interval in iter
426 */
427struct prio_tree_node *prio_tree_next(struct prio_tree_iter *iter)
428{
429 unsigned long r_index, h_index;
430
431 if (iter->cur == NULL)
432 return prio_tree_first(iter);
433
434repeat:
435 while (prio_tree_left(iter, &r_index, &h_index))
436 if (overlap(iter, r_index, h_index))
437 return iter->cur;
438
439 while (!prio_tree_right(iter, &r_index, &h_index)) {
440 while (!prio_tree_root(iter->cur) &&
441 iter->cur->parent->right == iter->cur)
442 prio_tree_parent(iter);
443
444 if (prio_tree_root(iter->cur))
445 return NULL;
446
447 prio_tree_parent(iter);
448 }
449
450 if (overlap(iter, r_index, h_index))
451 return iter->cur;
452
453 goto repeat;
454}
455EXPORT_SYMBOL(prio_tree_next);
diff --git a/lib/prio_tree_test.c b/lib/prio_tree_test.c
deleted file mode 100644
index c26084ddc6a4..000000000000
--- a/lib/prio_tree_test.c
+++ /dev/null
@@ -1,106 +0,0 @@
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-12-27 19:46:21 -0500