Contents of /alx-src/tags/kernel26-2.6.12-alx-r9/lib/radix-tree.c
Parent Directory | Revision Log
Revision 630 -
(show annotations)
(download)
Wed Mar 4 11:03:09 2009 UTC (15 years, 6 months ago) by niro
File MIME type: text/plain
File size: 19907 byte(s)
Wed Mar 4 11:03:09 2009 UTC (15 years, 6 months ago) by niro
File MIME type: text/plain
File size: 19907 byte(s)
Tag kernel26-2.6.12-alx-r9
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 | |
61 | static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH]; |
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 | } |