aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Documentation/00-INDEX2
-rw-r--r--Documentation/prio_tree.txt107
-rw-r--r--include/linux/prio_tree.h120
-rw-r--r--init/main.c2
-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
8 files changed, 1 insertions, 800 deletions
diff --git a/Documentation/00-INDEX b/Documentation/00-INDEX
index 49c051380daf..f54273e2ac97 100644
--- a/Documentation/00-INDEX
+++ b/Documentation/00-INDEX
@@ -270,8 +270,6 @@ preempt-locking.txt
270 - info on locking under a preemptive kernel. 270 - info on locking under a preemptive kernel.
271printk-formats.txt 271printk-formats.txt
272 - how to get printk format specifiers right 272 - how to get printk format specifiers right
273prio_tree.txt
274 - info on radix-priority-search-tree use for indexing vmas.
275ramoops.txt 273ramoops.txt
276 - documentation of the ramoops oops/panic logging module. 274 - documentation of the ramoops oops/panic logging module.
277rbtree.txt 275rbtree.txt
diff --git a/Documentation/prio_tree.txt b/Documentation/prio_tree.txt
deleted file mode 100644
index 3aa68f9a117b..000000000000
--- a/Documentation/prio_tree.txt
+++ /dev/null
@@ -1,107 +0,0 @@
1The prio_tree.c code indexes vmas using 3 different indexes:
2 * heap_index = vm_pgoff + vm_size_in_pages : end_vm_pgoff
3 * radix_index = vm_pgoff : start_vm_pgoff
4 * size_index = vm_size_in_pages
5
6A regular radix-priority-search-tree indexes vmas using only heap_index and
7radix_index. The conditions for indexing are:
8 * ->heap_index >= ->left->heap_index &&
9 ->heap_index >= ->right->heap_index
10 * if (->heap_index == ->left->heap_index)
11 then ->radix_index < ->left->radix_index;
12 * if (->heap_index == ->right->heap_index)
13 then ->radix_index < ->right->radix_index;
14 * nodes are hashed to left or right subtree using radix_index
15 similar to a pure binary radix tree.
16
17A regular radix-priority-search-tree helps to store and query
18intervals (vmas). However, a regular radix-priority-search-tree is only
19suitable for storing vmas with different radix indices (vm_pgoff).
20
21Therefore, the prio_tree.c extends the regular radix-priority-search-tree
22to handle many vmas with the same vm_pgoff. Such vmas are handled in
232 different ways: 1) All vmas with the same radix _and_ heap indices are
24linked using vm_set.list, 2) if there are many vmas with the same radix
25index, but different heap indices and if the regular radix-priority-search
26tree cannot index them all, we build an overflow-sub-tree that indexes such
27vmas using heap and size indices instead of heap and radix indices. For
28example, in the figure below some vmas with vm_pgoff = 0 (zero) are
29indexed by regular radix-priority-search-tree whereas others are pushed
30into an overflow-subtree. Note that all vmas in an overflow-sub-tree have
31the same vm_pgoff (radix_index) and if necessary we build different
32overflow-sub-trees to handle each possible radix_index. For example,
33in figure we have 3 overflow-sub-trees corresponding to radix indices
340, 2, and 4.
35
36In the final tree the first few (prio_tree_root->index_bits) levels
37are indexed using heap and radix indices whereas the overflow-sub-trees below
38those levels (i.e. levels prio_tree_root->index_bits + 1 and higher) are
39indexed using heap and size indices. In overflow-sub-trees the size_index
40is used for hashing the nodes to appropriate places.
41
42Now, an example prio_tree:
43
44 vmas are represented [radix_index, size_index, heap_index]
45 i.e., [start_vm_pgoff, vm_size_in_pages, end_vm_pgoff]
46
47level prio_tree_root->index_bits = 3
48-----
49 _
50 0 [0,7,7] |
51 / \ |
52 ------------------ ------------ | Regular
53 / \ | radix priority
54 1 [1,6,7] [4,3,7] | search tree
55 / \ / \ |
56 ------- ----- ------ ----- | heap-and-radix
57 / \ / \ | indexed
58 2 [0,6,6] [2,5,7] [5,2,7] [6,1,7] |
59 / \ / \ / \ / \ |
60 3 [0,5,5] [1,5,6] [2,4,6] [3,4,7] [4,2,6] [5,1,6] [6,0,6] [7,0,7] |
61 / / / _
62 / / / _
63 4 [0,4,4] [2,3,5] [4,1,5] |
64 / / / |
65 5 [0,3,3] [2,2,4] [4,0,4] | Overflow-sub-trees
66 / / |
67 6 [0,2,2] [2,1,3] | heap-and-size
68 / / | indexed
69 7 [0,1,1] [2,0,2] |
70 / |
71 8 [0,0,0] |
72 _
73
74Note that we use prio_tree_root->index_bits to optimize the height
75of the heap-and-radix indexed tree. Since prio_tree_root->index_bits is
76set according to the maximum end_vm_pgoff mapped, we are sure that all
77bits (in vm_pgoff) above prio_tree_root->index_bits are 0 (zero). Therefore,
78we only use the first prio_tree_root->index_bits as radix_index.
79Whenever index_bits is increased in prio_tree_expand, we shuffle the tree
80to make sure that the first prio_tree_root->index_bits levels of the tree
81is indexed properly using heap and radix indices.
82
83We do not optimize the height of overflow-sub-trees using index_bits.
84The reason is: there can be many such overflow-sub-trees and all of
85them have to be suffled whenever the index_bits increases. This may involve
86walking the whole prio_tree in prio_tree_insert->prio_tree_expand code
87path which is not desirable. Hence, we do not optimize the height of the
88heap-and-size indexed overflow-sub-trees using prio_tree->index_bits.
89Instead the overflow sub-trees are indexed using full BITS_PER_LONG bits
90of size_index. This may lead to skewed sub-trees because most of the
91higher significant bits of the size_index are likely to be 0 (zero). In
92the example above, all 3 overflow-sub-trees are skewed. This may marginally
93affect the performance. However, processes rarely map many vmas with the
94same start_vm_pgoff but different end_vm_pgoffs. Therefore, we normally
95do not require overflow-sub-trees to index all vmas.
96
97From the above discussion it is clear that the maximum height of
98a prio_tree can be prio_tree_root->index_bits + BITS_PER_LONG.
99However, in most of the common cases we do not need overflow-sub-trees,
100so the tree height in the common cases will be prio_tree_root->index_bits.
101
102It is fair to mention here that the prio_tree_root->index_bits
103is increased on demand, however, the index_bits is not decreased when
104vmas are removed from the prio_tree. That's tricky to do. Hence, it's
105left as a home work problem.
106
107
diff --git a/include/linux/prio_tree.h b/include/linux/prio_tree.h
deleted file mode 100644
index db04abb557e0..000000000000
--- a/include/linux/prio_tree.h
+++ /dev/null
@@ -1,120 +0,0 @@
1#ifndef _LINUX_PRIO_TREE_H
2#define _LINUX_PRIO_TREE_H
3
4/*
5 * K&R 2nd ed. A8.3 somewhat obliquely hints that initial sequences of struct
6 * fields with identical types should end up at the same location. We'll use
7 * this until we can scrap struct raw_prio_tree_node.
8 *
9 * Note: all this could be done more elegantly by using unnamed union/struct
10 * fields. However, gcc 2.95.3 and apparently also gcc 3.0.4 don't support this
11 * language extension.
12 */
13
14struct raw_prio_tree_node {
15 struct prio_tree_node *left;
16 struct prio_tree_node *right;
17 struct prio_tree_node *parent;
18};
19
20struct prio_tree_node {
21 struct prio_tree_node *left;
22 struct prio_tree_node *right;
23 struct prio_tree_node *parent;
24 unsigned long start;
25 unsigned long last; /* last location _in_ interval */
26};
27
28struct prio_tree_root {
29 struct prio_tree_node *prio_tree_node;
30 unsigned short index_bits;
31 unsigned short raw;
32 /*
33 * 0: nodes are of type struct prio_tree_node
34 * 1: nodes are of type raw_prio_tree_node
35 */
36};
37
38struct prio_tree_iter {
39 struct prio_tree_node *cur;
40 unsigned long mask;
41 unsigned long value;
42 int size_level;
43
44 struct prio_tree_root *root;
45 pgoff_t r_index;
46 pgoff_t h_index;
47};
48
49static inline void prio_tree_iter_init(struct prio_tree_iter *iter,
50 struct prio_tree_root *root, pgoff_t r_index, pgoff_t h_index)
51{
52 iter->root = root;
53 iter->r_index = r_index;
54 iter->h_index = h_index;
55 iter->cur = NULL;
56}
57
58#define __INIT_PRIO_TREE_ROOT(ptr, _raw) \
59do { \
60 (ptr)->prio_tree_node = NULL; \
61 (ptr)->index_bits = 1; \
62 (ptr)->raw = (_raw); \
63} while (0)
64
65#define INIT_PRIO_TREE_ROOT(ptr) __INIT_PRIO_TREE_ROOT(ptr, 0)
66#define INIT_RAW_PRIO_TREE_ROOT(ptr) __INIT_PRIO_TREE_ROOT(ptr, 1)
67
68#define INIT_PRIO_TREE_NODE(ptr) \
69do { \
70 (ptr)->left = (ptr)->right = (ptr)->parent = (ptr); \
71} while (0)
72
73#define INIT_PRIO_TREE_ITER(ptr) \
74do { \
75 (ptr)->cur = NULL; \
76 (ptr)->mask = 0UL; \
77 (ptr)->value = 0UL; \
78 (ptr)->size_level = 0; \
79} while (0)
80
81#define prio_tree_entry(ptr, type, member) \
82 ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
83
84static inline int prio_tree_empty(const struct prio_tree_root *root)
85{
86 return root->prio_tree_node == NULL;
87}
88
89static inline int prio_tree_root(const struct prio_tree_node *node)
90{
91 return node->parent == node;
92}
93
94static inline int prio_tree_left_empty(const struct prio_tree_node *node)
95{
96 return node->left == node;
97}
98
99static inline int prio_tree_right_empty(const struct prio_tree_node *node)
100{
101 return node->right == node;
102}
103
104
105struct prio_tree_node *prio_tree_replace(struct prio_tree_root *root,
106 struct prio_tree_node *old, struct prio_tree_node *node);
107struct prio_tree_node *prio_tree_insert(struct prio_tree_root *root,
108 struct prio_tree_node *node);
109void prio_tree_remove(struct prio_tree_root *root, struct prio_tree_node *node);
110struct prio_tree_node *prio_tree_next(struct prio_tree_iter *iter);
111
112#define raw_prio_tree_replace(root, old, node) \
113 prio_tree_replace(root, (struct prio_tree_node *) (old), \
114 (struct prio_tree_node *) (node))
115#define raw_prio_tree_insert(root, node) \
116 prio_tree_insert(root, (struct prio_tree_node *) (node))
117#define raw_prio_tree_remove(root, node) \
118 prio_tree_remove(root, (struct prio_tree_node *) (node))
119
120#endif /* _LINUX_PRIO_TREE_H */
diff --git a/init/main.c b/init/main.c
index db34c0ec4711..313360fe1118 100644
--- a/init/main.c
+++ b/init/main.c
@@ -86,7 +86,6 @@ extern void init_IRQ(void);
86extern void fork_init(unsigned long); 86extern void fork_init(unsigned long);
87extern void mca_init(void); 87extern void mca_init(void);
88extern void sbus_init(void); 88extern void sbus_init(void);
89extern void prio_tree_init(void);
90extern void radix_tree_init(void); 89extern void radix_tree_init(void);
91#ifndef CONFIG_DEBUG_RODATA 90#ifndef CONFIG_DEBUG_RODATA
92static inline void mark_rodata_ro(void) { } 91static inline void mark_rodata_ro(void) { }
@@ -547,7 +546,6 @@ asmlinkage void __init start_kernel(void)
547 /* init some links before init_ISA_irqs() */ 546 /* init some links before init_ISA_irqs() */
548 early_irq_init(); 547 early_irq_init();
549 init_IRQ(); 548 init_IRQ();
550 prio_tree_init();
551 init_timers(); 549 init_timers();
552 hrtimers_init(); 550 hrtimers_init();
553 softirq_init(); 551 softirq_init();
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 2025-01-22 20:44:51 -0500