Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* |
2 | * Copyright (C) 2001 Momchil Velikov | |
3 | * Portions Copyright (C) 2001 Christoph Hellwig | |
4 | * | |
5 | * This program is free software; you can redistribute it and/or | |
6 | * modify it under the terms of the GNU General Public License as | |
7 | * published by the Free Software Foundation; either version 2, or (at | |
8 | * your option) any later version. | |
9 | * | |
10 | * This program is distributed in the hope that it will be useful, but | |
11 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
13 | * General Public License for more details. | |
14 | * | |
15 | * You should have received a copy of the GNU General Public License | |
16 | * along with this program; if not, write to the Free Software | |
17 | * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. | |
18 | */ | |
19 | ||
20 | #include <linux/errno.h> | |
21 | #include <linux/init.h> | |
22 | #include <linux/kernel.h> | |
23 | #include <linux/module.h> | |
24 | #include <linux/radix-tree.h> | |
25 | #include <linux/percpu.h> | |
26 | #include <linux/slab.h> | |
27 | #include <linux/notifier.h> | |
28 | #include <linux/cpu.h> | |
29 | #include <linux/gfp.h> | |
30 | #include <linux/string.h> | |
31 | #include <linux/bitops.h> | |
32 | ||
33 | ||
34 | #ifdef __KERNEL__ | |
35 | #define RADIX_TREE_MAP_SHIFT 6 | |
36 | #else | |
37 | #define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */ | |
38 | #endif | |
39 | #define RADIX_TREE_TAGS 2 | |
40 | ||
41 | #define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT) | |
42 | #define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1) | |
43 | ||
44 | #define RADIX_TREE_TAG_LONGS \ | |
45 | ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG) | |
46 | ||
47 | struct radix_tree_node { | |
48 | unsigned int count; | |
49 | void *slots[RADIX_TREE_MAP_SIZE]; | |
50 | unsigned long tags[RADIX_TREE_TAGS][RADIX_TREE_TAG_LONGS]; | |
51 | }; | |
52 | ||
53 | struct radix_tree_path { | |
54 | struct radix_tree_node *node, **slot; | |
55 | int offset; | |
56 | }; | |
57 | ||
58 | #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long)) | |
59 | #define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2) | |
60 | ||
6c036527 | 61 | static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH] __read_mostly; |
1da177e4 LT |
62 | |
63 | /* | |
64 | * Radix tree node cache. | |
65 | */ | |
66 | static kmem_cache_t *radix_tree_node_cachep; | |
67 | ||
68 | /* | |
69 | * Per-cpu pool of preloaded nodes | |
70 | */ | |
71 | struct radix_tree_preload { | |
72 | int nr; | |
73 | struct radix_tree_node *nodes[RADIX_TREE_MAX_PATH]; | |
74 | }; | |
75 | DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, }; | |
76 | ||
77 | /* | |
78 | * This assumes that the caller has performed appropriate preallocation, and | |
79 | * that the caller has pinned this thread of control to the current CPU. | |
80 | */ | |
81 | static struct radix_tree_node * | |
82 | radix_tree_node_alloc(struct radix_tree_root *root) | |
83 | { | |
84 | struct radix_tree_node *ret; | |
85 | ||
86 | ret = kmem_cache_alloc(radix_tree_node_cachep, root->gfp_mask); | |
87 | if (ret == NULL && !(root->gfp_mask & __GFP_WAIT)) { | |
88 | struct radix_tree_preload *rtp; | |
89 | ||
90 | rtp = &__get_cpu_var(radix_tree_preloads); | |
91 | if (rtp->nr) { | |
92 | ret = rtp->nodes[rtp->nr - 1]; | |
93 | rtp->nodes[rtp->nr - 1] = NULL; | |
94 | rtp->nr--; | |
95 | } | |
96 | } | |
97 | return ret; | |
98 | } | |
99 | ||
100 | static inline void | |
101 | radix_tree_node_free(struct radix_tree_node *node) | |
102 | { | |
103 | kmem_cache_free(radix_tree_node_cachep, node); | |
104 | } | |
105 | ||
106 | /* | |
107 | * Load up this CPU's radix_tree_node buffer with sufficient objects to | |
108 | * ensure that the addition of a single element in the tree cannot fail. On | |
109 | * success, return zero, with preemption disabled. On error, return -ENOMEM | |
110 | * with preemption not disabled. | |
111 | */ | |
112 | int radix_tree_preload(int gfp_mask) | |
113 | { | |
114 | struct radix_tree_preload *rtp; | |
115 | struct radix_tree_node *node; | |
116 | int ret = -ENOMEM; | |
117 | ||
118 | preempt_disable(); | |
119 | rtp = &__get_cpu_var(radix_tree_preloads); | |
120 | while (rtp->nr < ARRAY_SIZE(rtp->nodes)) { | |
121 | preempt_enable(); | |
122 | node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask); | |
123 | if (node == NULL) | |
124 | goto out; | |
125 | preempt_disable(); | |
126 | rtp = &__get_cpu_var(radix_tree_preloads); | |
127 | if (rtp->nr < ARRAY_SIZE(rtp->nodes)) | |
128 | rtp->nodes[rtp->nr++] = node; | |
129 | else | |
130 | kmem_cache_free(radix_tree_node_cachep, node); | |
131 | } | |
132 | ret = 0; | |
133 | out: | |
134 | return ret; | |
135 | } | |
136 | ||
137 | static inline void tag_set(struct radix_tree_node *node, int tag, int offset) | |
138 | { | |
139 | if (!test_bit(offset, &node->tags[tag][0])) | |
140 | __set_bit(offset, &node->tags[tag][0]); | |
141 | } | |
142 | ||
143 | static inline void tag_clear(struct radix_tree_node *node, int tag, int offset) | |
144 | { | |
145 | __clear_bit(offset, &node->tags[tag][0]); | |
146 | } | |
147 | ||
148 | static inline int tag_get(struct radix_tree_node *node, int tag, int offset) | |
149 | { | |
150 | return test_bit(offset, &node->tags[tag][0]); | |
151 | } | |
152 | ||
153 | /* | |
154 | * Return the maximum key which can be store into a | |
155 | * radix tree with height HEIGHT. | |
156 | */ | |
157 | static inline unsigned long radix_tree_maxindex(unsigned int height) | |
158 | { | |
159 | return height_to_maxindex[height]; | |
160 | } | |
161 | ||
162 | /* | |
163 | * Extend a radix tree so it can store key @index. | |
164 | */ | |
165 | static int radix_tree_extend(struct radix_tree_root *root, unsigned long index) | |
166 | { | |
167 | struct radix_tree_node *node; | |
168 | unsigned int height; | |
169 | char tags[RADIX_TREE_TAGS]; | |
170 | int tag; | |
171 | ||
172 | /* Figure out what the height should be. */ | |
173 | height = root->height + 1; | |
174 | while (index > radix_tree_maxindex(height)) | |
175 | height++; | |
176 | ||
177 | if (root->rnode == NULL) { | |
178 | root->height = height; | |
179 | goto out; | |
180 | } | |
181 | ||
182 | /* | |
183 | * Prepare the tag status of the top-level node for propagation | |
184 | * into the newly-pushed top-level node(s) | |
185 | */ | |
186 | for (tag = 0; tag < RADIX_TREE_TAGS; tag++) { | |
187 | int idx; | |
188 | ||
189 | tags[tag] = 0; | |
190 | for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { | |
191 | if (root->rnode->tags[tag][idx]) { | |
192 | tags[tag] = 1; | |
193 | break; | |
194 | } | |
195 | } | |
196 | } | |
197 | ||
198 | do { | |
199 | if (!(node = radix_tree_node_alloc(root))) | |
200 | return -ENOMEM; | |
201 | ||
202 | /* Increase the height. */ | |
203 | node->slots[0] = root->rnode; | |
204 | ||
205 | /* Propagate the aggregated tag info into the new root */ | |
206 | for (tag = 0; tag < RADIX_TREE_TAGS; tag++) { | |
207 | if (tags[tag]) | |
208 | tag_set(node, tag, 0); | |
209 | } | |
210 | ||
211 | node->count = 1; | |
212 | root->rnode = node; | |
213 | root->height++; | |
214 | } while (height > root->height); | |
215 | out: | |
216 | return 0; | |
217 | } | |
218 | ||
219 | /** | |
220 | * radix_tree_insert - insert into a radix tree | |
221 | * @root: radix tree root | |
222 | * @index: index key | |
223 | * @item: item to insert | |
224 | * | |
225 | * Insert an item into the radix tree at position @index. | |
226 | */ | |
227 | int radix_tree_insert(struct radix_tree_root *root, | |
228 | unsigned long index, void *item) | |
229 | { | |
230 | struct radix_tree_node *node = NULL, *tmp, **slot; | |
231 | unsigned int height, shift; | |
232 | int offset; | |
233 | int error; | |
234 | ||
235 | /* Make sure the tree is high enough. */ | |
236 | if ((!index && !root->rnode) || | |
237 | index > radix_tree_maxindex(root->height)) { | |
238 | error = radix_tree_extend(root, index); | |
239 | if (error) | |
240 | return error; | |
241 | } | |
242 | ||
243 | slot = &root->rnode; | |
244 | height = root->height; | |
245 | shift = (height-1) * RADIX_TREE_MAP_SHIFT; | |
246 | ||
247 | offset = 0; /* uninitialised var warning */ | |
248 | while (height > 0) { | |
249 | if (*slot == NULL) { | |
250 | /* Have to add a child node. */ | |
251 | if (!(tmp = radix_tree_node_alloc(root))) | |
252 | return -ENOMEM; | |
253 | *slot = tmp; | |
254 | if (node) | |
255 | node->count++; | |
256 | } | |
257 | ||
258 | /* Go a level down */ | |
259 | offset = (index >> shift) & RADIX_TREE_MAP_MASK; | |
260 | node = *slot; | |
261 | slot = (struct radix_tree_node **)(node->slots + offset); | |
262 | shift -= RADIX_TREE_MAP_SHIFT; | |
263 | height--; | |
264 | } | |
265 | ||
266 | if (*slot != NULL) | |
267 | return -EEXIST; | |
268 | if (node) { | |
269 | node->count++; | |
270 | BUG_ON(tag_get(node, 0, offset)); | |
271 | BUG_ON(tag_get(node, 1, offset)); | |
272 | } | |
273 | ||
274 | *slot = item; | |
275 | return 0; | |
276 | } | |
277 | EXPORT_SYMBOL(radix_tree_insert); | |
278 | ||
279 | /** | |
280 | * radix_tree_lookup - perform lookup operation on a radix tree | |
281 | * @root: radix tree root | |
282 | * @index: index key | |
283 | * | |
284 | * Lookup the item at the position @index in the radix tree @root. | |
285 | */ | |
286 | void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) | |
287 | { | |
288 | unsigned int height, shift; | |
289 | struct radix_tree_node **slot; | |
290 | ||
291 | height = root->height; | |
292 | if (index > radix_tree_maxindex(height)) | |
293 | return NULL; | |
294 | ||
295 | shift = (height-1) * RADIX_TREE_MAP_SHIFT; | |
296 | slot = &root->rnode; | |
297 | ||
298 | while (height > 0) { | |
299 | if (*slot == NULL) | |
300 | return NULL; | |
301 | ||
302 | slot = (struct radix_tree_node **) | |
303 | ((*slot)->slots + | |
304 | ((index >> shift) & RADIX_TREE_MAP_MASK)); | |
305 | shift -= RADIX_TREE_MAP_SHIFT; | |
306 | height--; | |
307 | } | |
308 | ||
309 | return *slot; | |
310 | } | |
311 | EXPORT_SYMBOL(radix_tree_lookup); | |
312 | ||
313 | /** | |
314 | * radix_tree_tag_set - set a tag on a radix tree node | |
315 | * @root: radix tree root | |
316 | * @index: index key | |
317 | * @tag: tag index | |
318 | * | |
319 | * Set the search tag corresponging to @index in the radix tree. From | |
320 | * the root all the way down to the leaf node. | |
321 | * | |
322 | * Returns the address of the tagged item. Setting a tag on a not-present | |
323 | * item is a bug. | |
324 | */ | |
325 | void *radix_tree_tag_set(struct radix_tree_root *root, | |
326 | unsigned long index, int tag) | |
327 | { | |
328 | unsigned int height, shift; | |
329 | struct radix_tree_node **slot; | |
330 | ||
331 | height = root->height; | |
332 | if (index > radix_tree_maxindex(height)) | |
333 | return NULL; | |
334 | ||
335 | shift = (height - 1) * RADIX_TREE_MAP_SHIFT; | |
336 | slot = &root->rnode; | |
337 | ||
338 | while (height > 0) { | |
339 | int offset; | |
340 | ||
341 | offset = (index >> shift) & RADIX_TREE_MAP_MASK; | |
342 | tag_set(*slot, tag, offset); | |
343 | slot = (struct radix_tree_node **)((*slot)->slots + offset); | |
344 | BUG_ON(*slot == NULL); | |
345 | shift -= RADIX_TREE_MAP_SHIFT; | |
346 | height--; | |
347 | } | |
348 | ||
349 | return *slot; | |
350 | } | |
351 | EXPORT_SYMBOL(radix_tree_tag_set); | |
352 | ||
353 | /** | |
354 | * radix_tree_tag_clear - clear a tag on a radix tree node | |
355 | * @root: radix tree root | |
356 | * @index: index key | |
357 | * @tag: tag index | |
358 | * | |
359 | * Clear the search tag corresponging to @index in the radix tree. If | |
360 | * this causes the leaf node to have no tags set then clear the tag in the | |
361 | * next-to-leaf node, etc. | |
362 | * | |
363 | * Returns the address of the tagged item on success, else NULL. ie: | |
364 | * has the same return value and semantics as radix_tree_lookup(). | |
365 | */ | |
366 | void *radix_tree_tag_clear(struct radix_tree_root *root, | |
367 | unsigned long index, int tag) | |
368 | { | |
369 | struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path; | |
370 | unsigned int height, shift; | |
371 | void *ret = NULL; | |
372 | ||
373 | height = root->height; | |
374 | if (index > radix_tree_maxindex(height)) | |
375 | goto out; | |
376 | ||
377 | shift = (height - 1) * RADIX_TREE_MAP_SHIFT; | |
378 | pathp->node = NULL; | |
379 | pathp->slot = &root->rnode; | |
380 | ||
381 | while (height > 0) { | |
382 | int offset; | |
383 | ||
384 | if (*pathp->slot == NULL) | |
385 | goto out; | |
386 | ||
387 | offset = (index >> shift) & RADIX_TREE_MAP_MASK; | |
388 | pathp[1].offset = offset; | |
389 | pathp[1].node = *pathp[0].slot; | |
390 | pathp[1].slot = (struct radix_tree_node **) | |
391 | (pathp[1].node->slots + offset); | |
392 | pathp++; | |
393 | shift -= RADIX_TREE_MAP_SHIFT; | |
394 | height--; | |
395 | } | |
396 | ||
397 | ret = *pathp[0].slot; | |
398 | if (ret == NULL) | |
399 | goto out; | |
400 | ||
401 | do { | |
402 | int idx; | |
403 | ||
404 | tag_clear(pathp[0].node, tag, pathp[0].offset); | |
405 | for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { | |
406 | if (pathp[0].node->tags[tag][idx]) | |
407 | goto out; | |
408 | } | |
409 | pathp--; | |
410 | } while (pathp[0].node); | |
411 | out: | |
412 | return ret; | |
413 | } | |
414 | EXPORT_SYMBOL(radix_tree_tag_clear); | |
415 | ||
416 | #ifndef __KERNEL__ /* Only the test harness uses this at present */ | |
417 | /** | |
418 | * radix_tree_tag_get - get a tag on a radix tree node | |
419 | * @root: radix tree root | |
420 | * @index: index key | |
421 | * @tag: tag index | |
422 | * | |
423 | * Return the search tag corresponging to @index in the radix tree. | |
424 | * | |
425 | * Returns zero if the tag is unset, or if there is no corresponding item | |
426 | * in the tree. | |
427 | */ | |
428 | int radix_tree_tag_get(struct radix_tree_root *root, | |
429 | unsigned long index, int tag) | |
430 | { | |
431 | unsigned int height, shift; | |
432 | struct radix_tree_node **slot; | |
433 | int saw_unset_tag = 0; | |
434 | ||
435 | height = root->height; | |
436 | if (index > radix_tree_maxindex(height)) | |
437 | return 0; | |
438 | ||
439 | shift = (height - 1) * RADIX_TREE_MAP_SHIFT; | |
440 | slot = &root->rnode; | |
441 | ||
442 | for ( ; ; ) { | |
443 | int offset; | |
444 | ||
445 | if (*slot == NULL) | |
446 | return 0; | |
447 | ||
448 | offset = (index >> shift) & RADIX_TREE_MAP_MASK; | |
449 | ||
450 | /* | |
451 | * This is just a debug check. Later, we can bale as soon as | |
452 | * we see an unset tag. | |
453 | */ | |
454 | if (!tag_get(*slot, tag, offset)) | |
455 | saw_unset_tag = 1; | |
456 | if (height == 1) { | |
457 | int ret = tag_get(*slot, tag, offset); | |
458 | ||
459 | BUG_ON(ret && saw_unset_tag); | |
460 | return ret; | |
461 | } | |
462 | slot = (struct radix_tree_node **)((*slot)->slots + offset); | |
463 | shift -= RADIX_TREE_MAP_SHIFT; | |
464 | height--; | |
465 | } | |
466 | } | |
467 | EXPORT_SYMBOL(radix_tree_tag_get); | |
468 | #endif | |
469 | ||
470 | static unsigned int | |
471 | __lookup(struct radix_tree_root *root, void **results, unsigned long index, | |
472 | unsigned int max_items, unsigned long *next_index) | |
473 | { | |
474 | unsigned int nr_found = 0; | |
475 | unsigned int shift; | |
476 | unsigned int height = root->height; | |
477 | struct radix_tree_node *slot; | |
478 | ||
479 | shift = (height-1) * RADIX_TREE_MAP_SHIFT; | |
480 | slot = root->rnode; | |
481 | ||
482 | while (height > 0) { | |
483 | unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK; | |
484 | ||
485 | for ( ; i < RADIX_TREE_MAP_SIZE; i++) { | |
486 | if (slot->slots[i] != NULL) | |
487 | break; | |
488 | index &= ~((1UL << shift) - 1); | |
489 | index += 1UL << shift; | |
490 | if (index == 0) | |
491 | goto out; /* 32-bit wraparound */ | |
492 | } | |
493 | if (i == RADIX_TREE_MAP_SIZE) | |
494 | goto out; | |
495 | height--; | |
496 | if (height == 0) { /* Bottom level: grab some items */ | |
497 | unsigned long j = index & RADIX_TREE_MAP_MASK; | |
498 | ||
499 | for ( ; j < RADIX_TREE_MAP_SIZE; j++) { | |
500 | index++; | |
501 | if (slot->slots[j]) { | |
502 | results[nr_found++] = slot->slots[j]; | |
503 | if (nr_found == max_items) | |
504 | goto out; | |
505 | } | |
506 | } | |
507 | } | |
508 | shift -= RADIX_TREE_MAP_SHIFT; | |
509 | slot = slot->slots[i]; | |
510 | } | |
511 | out: | |
512 | *next_index = index; | |
513 | return nr_found; | |
514 | } | |
515 | ||
516 | /** | |
517 | * radix_tree_gang_lookup - perform multiple lookup on a radix tree | |
518 | * @root: radix tree root | |
519 | * @results: where the results of the lookup are placed | |
520 | * @first_index: start the lookup from this key | |
521 | * @max_items: place up to this many items at *results | |
522 | * | |
523 | * Performs an index-ascending scan of the tree for present items. Places | |
524 | * them at *@results and returns the number of items which were placed at | |
525 | * *@results. | |
526 | * | |
527 | * The implementation is naive. | |
528 | */ | |
529 | unsigned int | |
530 | radix_tree_gang_lookup(struct radix_tree_root *root, void **results, | |
531 | unsigned long first_index, unsigned int max_items) | |
532 | { | |
533 | const unsigned long max_index = radix_tree_maxindex(root->height); | |
534 | unsigned long cur_index = first_index; | |
535 | unsigned int ret = 0; | |
536 | ||
537 | while (ret < max_items) { | |
538 | unsigned int nr_found; | |
539 | unsigned long next_index; /* Index of next search */ | |
540 | ||
541 | if (cur_index > max_index) | |
542 | break; | |
543 | nr_found = __lookup(root, results + ret, cur_index, | |
544 | max_items - ret, &next_index); | |
545 | ret += nr_found; | |
546 | if (next_index == 0) | |
547 | break; | |
548 | cur_index = next_index; | |
549 | } | |
550 | return ret; | |
551 | } | |
552 | EXPORT_SYMBOL(radix_tree_gang_lookup); | |
553 | ||
554 | /* | |
555 | * FIXME: the two tag_get()s here should use find_next_bit() instead of | |
556 | * open-coding the search. | |
557 | */ | |
558 | static unsigned int | |
559 | __lookup_tag(struct radix_tree_root *root, void **results, unsigned long index, | |
560 | unsigned int max_items, unsigned long *next_index, int tag) | |
561 | { | |
562 | unsigned int nr_found = 0; | |
563 | unsigned int shift; | |
564 | unsigned int height = root->height; | |
565 | struct radix_tree_node *slot; | |
566 | ||
567 | shift = (height - 1) * RADIX_TREE_MAP_SHIFT; | |
568 | slot = root->rnode; | |
569 | ||
570 | while (height > 0) { | |
571 | unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK; | |
572 | ||
573 | for ( ; i < RADIX_TREE_MAP_SIZE; i++) { | |
574 | if (tag_get(slot, tag, i)) { | |
575 | BUG_ON(slot->slots[i] == NULL); | |
576 | break; | |
577 | } | |
578 | index &= ~((1UL << shift) - 1); | |
579 | index += 1UL << shift; | |
580 | if (index == 0) | |
581 | goto out; /* 32-bit wraparound */ | |
582 | } | |
583 | if (i == RADIX_TREE_MAP_SIZE) | |
584 | goto out; | |
585 | height--; | |
586 | if (height == 0) { /* Bottom level: grab some items */ | |
587 | unsigned long j = index & RADIX_TREE_MAP_MASK; | |
588 | ||
589 | for ( ; j < RADIX_TREE_MAP_SIZE; j++) { | |
590 | index++; | |
591 | if (tag_get(slot, tag, j)) { | |
592 | BUG_ON(slot->slots[j] == NULL); | |
593 | results[nr_found++] = slot->slots[j]; | |
594 | if (nr_found == max_items) | |
595 | goto out; | |
596 | } | |
597 | } | |
598 | } | |
599 | shift -= RADIX_TREE_MAP_SHIFT; | |
600 | slot = slot->slots[i]; | |
601 | } | |
602 | out: | |
603 | *next_index = index; | |
604 | return nr_found; | |
605 | } | |
606 | ||
607 | /** | |
608 | * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree | |
609 | * based on a tag | |
610 | * @root: radix tree root | |
611 | * @results: where the results of the lookup are placed | |
612 | * @first_index: start the lookup from this key | |
613 | * @max_items: place up to this many items at *results | |
614 | * @tag: the tag index | |
615 | * | |
616 | * Performs an index-ascending scan of the tree for present items which | |
617 | * have the tag indexed by @tag set. Places the items at *@results and | |
618 | * returns the number of items which were placed at *@results. | |
619 | */ | |
620 | unsigned int | |
621 | radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, | |
622 | unsigned long first_index, unsigned int max_items, int tag) | |
623 | { | |
624 | const unsigned long max_index = radix_tree_maxindex(root->height); | |
625 | unsigned long cur_index = first_index; | |
626 | unsigned int ret = 0; | |
627 | ||
628 | while (ret < max_items) { | |
629 | unsigned int nr_found; | |
630 | unsigned long next_index; /* Index of next search */ | |
631 | ||
632 | if (cur_index > max_index) | |
633 | break; | |
634 | nr_found = __lookup_tag(root, results + ret, cur_index, | |
635 | max_items - ret, &next_index, tag); | |
636 | ret += nr_found; | |
637 | if (next_index == 0) | |
638 | break; | |
639 | cur_index = next_index; | |
640 | } | |
641 | return ret; | |
642 | } | |
643 | EXPORT_SYMBOL(radix_tree_gang_lookup_tag); | |
644 | ||
645 | /** | |
646 | * radix_tree_delete - delete an item from a radix tree | |
647 | * @root: radix tree root | |
648 | * @index: index key | |
649 | * | |
650 | * Remove the item at @index from the radix tree rooted at @root. | |
651 | * | |
652 | * Returns the address of the deleted item, or NULL if it was not present. | |
653 | */ | |
654 | void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) | |
655 | { | |
656 | struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path; | |
657 | struct radix_tree_path *orig_pathp; | |
658 | unsigned int height, shift; | |
659 | void *ret = NULL; | |
660 | char tags[RADIX_TREE_TAGS]; | |
661 | int nr_cleared_tags; | |
662 | ||
663 | height = root->height; | |
664 | if (index > radix_tree_maxindex(height)) | |
665 | goto out; | |
666 | ||
667 | shift = (height - 1) * RADIX_TREE_MAP_SHIFT; | |
668 | pathp->node = NULL; | |
669 | pathp->slot = &root->rnode; | |
670 | ||
671 | while (height > 0) { | |
672 | int offset; | |
673 | ||
674 | if (*pathp->slot == NULL) | |
675 | goto out; | |
676 | ||
677 | offset = (index >> shift) & RADIX_TREE_MAP_MASK; | |
678 | pathp[1].offset = offset; | |
679 | pathp[1].node = *pathp[0].slot; | |
680 | pathp[1].slot = (struct radix_tree_node **) | |
681 | (pathp[1].node->slots + offset); | |
682 | pathp++; | |
683 | shift -= RADIX_TREE_MAP_SHIFT; | |
684 | height--; | |
685 | } | |
686 | ||
687 | ret = *pathp[0].slot; | |
688 | if (ret == NULL) | |
689 | goto out; | |
690 | ||
691 | orig_pathp = pathp; | |
692 | ||
693 | /* | |
694 | * Clear all tags associated with the just-deleted item | |
695 | */ | |
696 | memset(tags, 0, sizeof(tags)); | |
697 | do { | |
698 | int tag; | |
699 | ||
700 | nr_cleared_tags = RADIX_TREE_TAGS; | |
701 | for (tag = 0; tag < RADIX_TREE_TAGS; tag++) { | |
702 | int idx; | |
703 | ||
704 | if (tags[tag]) | |
705 | continue; | |
706 | ||
707 | tag_clear(pathp[0].node, tag, pathp[0].offset); | |
708 | ||
709 | for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { | |
710 | if (pathp[0].node->tags[tag][idx]) { | |
711 | tags[tag] = 1; | |
712 | nr_cleared_tags--; | |
713 | break; | |
714 | } | |
715 | } | |
716 | } | |
717 | pathp--; | |
718 | } while (pathp[0].node && nr_cleared_tags); | |
719 | ||
720 | pathp = orig_pathp; | |
721 | *pathp[0].slot = NULL; | |
722 | while (pathp[0].node && --pathp[0].node->count == 0) { | |
723 | pathp--; | |
724 | BUG_ON(*pathp[0].slot == NULL); | |
725 | *pathp[0].slot = NULL; | |
726 | radix_tree_node_free(pathp[1].node); | |
727 | } | |
728 | if (root->rnode == NULL) | |
729 | root->height = 0; | |
730 | out: | |
731 | return ret; | |
732 | } | |
733 | EXPORT_SYMBOL(radix_tree_delete); | |
734 | ||
735 | /** | |
736 | * radix_tree_tagged - test whether any items in the tree are tagged | |
737 | * @root: radix tree root | |
738 | * @tag: tag to test | |
739 | */ | |
740 | int radix_tree_tagged(struct radix_tree_root *root, int tag) | |
741 | { | |
742 | int idx; | |
743 | ||
744 | if (!root->rnode) | |
745 | return 0; | |
746 | for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { | |
747 | if (root->rnode->tags[tag][idx]) | |
748 | return 1; | |
749 | } | |
750 | return 0; | |
751 | } | |
752 | EXPORT_SYMBOL(radix_tree_tagged); | |
753 | ||
754 | static void | |
755 | radix_tree_node_ctor(void *node, kmem_cache_t *cachep, unsigned long flags) | |
756 | { | |
757 | memset(node, 0, sizeof(struct radix_tree_node)); | |
758 | } | |
759 | ||
760 | static __init unsigned long __maxindex(unsigned int height) | |
761 | { | |
762 | unsigned int tmp = height * RADIX_TREE_MAP_SHIFT; | |
763 | unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1; | |
764 | ||
765 | if (tmp >= RADIX_TREE_INDEX_BITS) | |
766 | index = ~0UL; | |
767 | return index; | |
768 | } | |
769 | ||
770 | static __init void radix_tree_init_maxindex(void) | |
771 | { | |
772 | unsigned int i; | |
773 | ||
774 | for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++) | |
775 | height_to_maxindex[i] = __maxindex(i); | |
776 | } | |
777 | ||
778 | #ifdef CONFIG_HOTPLUG_CPU | |
779 | static int radix_tree_callback(struct notifier_block *nfb, | |
780 | unsigned long action, | |
781 | void *hcpu) | |
782 | { | |
783 | int cpu = (long)hcpu; | |
784 | struct radix_tree_preload *rtp; | |
785 | ||
786 | /* Free per-cpu pool of perloaded nodes */ | |
787 | if (action == CPU_DEAD) { | |
788 | rtp = &per_cpu(radix_tree_preloads, cpu); | |
789 | while (rtp->nr) { | |
790 | kmem_cache_free(radix_tree_node_cachep, | |
791 | rtp->nodes[rtp->nr-1]); | |
792 | rtp->nodes[rtp->nr-1] = NULL; | |
793 | rtp->nr--; | |
794 | } | |
795 | } | |
796 | return NOTIFY_OK; | |
797 | } | |
798 | #endif /* CONFIG_HOTPLUG_CPU */ | |
799 | ||
800 | void __init radix_tree_init(void) | |
801 | { | |
802 | radix_tree_node_cachep = kmem_cache_create("radix_tree_node", | |
803 | sizeof(struct radix_tree_node), 0, | |
804 | SLAB_PANIC, radix_tree_node_ctor, NULL); | |
805 | radix_tree_init_maxindex(); | |
806 | hotcpu_notifier(radix_tree_callback, 0); | |
807 | } |