Root/
Source at commit be977234bfb4a6dca8a39e7c52165e4cd536ad71 created 12 years 9 months ago. By Lars-Peter Clausen, jz4740: Fix compile error | |
---|---|
1 | /* |
2 | * Copyright (C) 2001 Momchil Velikov |
3 | * Portions Copyright (C) 2001 Christoph Hellwig |
4 | * Copyright (C) 2005 SGI, Christoph Lameter |
5 | * Copyright (C) 2006 Nick Piggin |
6 | * |
7 | * This program is free software; you can redistribute it and/or |
8 | * modify it under the terms of the GNU General Public License as |
9 | * published by the Free Software Foundation; either version 2, or (at |
10 | * your option) any later version. |
11 | * |
12 | * This program is distributed in the hope that it will be useful, but |
13 | * WITHOUT ANY WARRANTY; without even the implied warranty of |
14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
15 | * General Public License for more details. |
16 | * |
17 | * You should have received a copy of the GNU General Public License |
18 | * along with this program; if not, write to the Free Software |
19 | * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. |
20 | */ |
21 | |
22 | #include <linux/errno.h> |
23 | #include <linux/init.h> |
24 | #include <linux/kernel.h> |
25 | #include <linux/module.h> |
26 | #include <linux/radix-tree.h> |
27 | #include <linux/percpu.h> |
28 | #include <linux/slab.h> |
29 | #include <linux/notifier.h> |
30 | #include <linux/cpu.h> |
31 | #include <linux/string.h> |
32 | #include <linux/bitops.h> |
33 | #include <linux/rcupdate.h> |
34 | |
35 | |
36 | #ifdef __KERNEL__ |
37 | #define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6) |
38 | #else |
39 | #define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */ |
40 | #endif |
41 | |
42 | #define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT) |
43 | #define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1) |
44 | |
45 | #define RADIX_TREE_TAG_LONGS \ |
46 | ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG) |
47 | |
48 | struct radix_tree_node { |
49 | unsigned int height; /* Height from the bottom */ |
50 | unsigned int count; |
51 | struct rcu_head rcu_head; |
52 | void __rcu *slots[RADIX_TREE_MAP_SIZE]; |
53 | unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS]; |
54 | }; |
55 | |
56 | struct radix_tree_path { |
57 | struct radix_tree_node *node; |
58 | int offset; |
59 | }; |
60 | |
61 | #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long)) |
62 | #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \ |
63 | RADIX_TREE_MAP_SHIFT)) |
64 | |
65 | /* |
66 | * The height_to_maxindex array needs to be one deeper than the maximum |
67 | * path as height 0 holds only 1 entry. |
68 | */ |
69 | static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly; |
70 | |
71 | /* |
72 | * Radix tree node cache. |
73 | */ |
74 | static struct kmem_cache *radix_tree_node_cachep; |
75 | |
76 | /* |
77 | * Per-cpu pool of preloaded nodes |
78 | */ |
79 | struct radix_tree_preload { |
80 | int nr; |
81 | struct radix_tree_node *nodes[RADIX_TREE_MAX_PATH]; |
82 | }; |
83 | static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, }; |
84 | |
85 | static inline void *ptr_to_indirect(void *ptr) |
86 | { |
87 | return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR); |
88 | } |
89 | |
90 | static inline void *indirect_to_ptr(void *ptr) |
91 | { |
92 | return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR); |
93 | } |
94 | |
95 | static inline gfp_t root_gfp_mask(struct radix_tree_root *root) |
96 | { |
97 | return root->gfp_mask & __GFP_BITS_MASK; |
98 | } |
99 | |
100 | static inline void tag_set(struct radix_tree_node *node, unsigned int tag, |
101 | int offset) |
102 | { |
103 | __set_bit(offset, node->tags[tag]); |
104 | } |
105 | |
106 | static inline void tag_clear(struct radix_tree_node *node, unsigned int tag, |
107 | int offset) |
108 | { |
109 | __clear_bit(offset, node->tags[tag]); |
110 | } |
111 | |
112 | static inline int tag_get(struct radix_tree_node *node, unsigned int tag, |
113 | int offset) |
114 | { |
115 | return test_bit(offset, node->tags[tag]); |
116 | } |
117 | |
118 | static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag) |
119 | { |
120 | root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT)); |
121 | } |
122 | |
123 | static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag) |
124 | { |
125 | root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT)); |
126 | } |
127 | |
128 | static inline void root_tag_clear_all(struct radix_tree_root *root) |
129 | { |
130 | root->gfp_mask &= __GFP_BITS_MASK; |
131 | } |
132 | |
133 | static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag) |
134 | { |
135 | return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT)); |
136 | } |
137 | |
138 | /* |
139 | * Returns 1 if any slot in the node has this tag set. |
140 | * Otherwise returns 0. |
141 | */ |
142 | static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag) |
143 | { |
144 | int idx; |
145 | for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { |
146 | if (node->tags[tag][idx]) |
147 | return 1; |
148 | } |
149 | return 0; |
150 | } |
151 | /* |
152 | * This assumes that the caller has performed appropriate preallocation, and |
153 | * that the caller has pinned this thread of control to the current CPU. |
154 | */ |
155 | static struct radix_tree_node * |
156 | radix_tree_node_alloc(struct radix_tree_root *root) |
157 | { |
158 | struct radix_tree_node *ret = NULL; |
159 | gfp_t gfp_mask = root_gfp_mask(root); |
160 | |
161 | if (!(gfp_mask & __GFP_WAIT)) { |
162 | struct radix_tree_preload *rtp; |
163 | |
164 | /* |
165 | * Provided the caller has preloaded here, we will always |
166 | * succeed in getting a node here (and never reach |
167 | * kmem_cache_alloc) |
168 | */ |
169 | rtp = &__get_cpu_var(radix_tree_preloads); |
170 | if (rtp->nr) { |
171 | ret = rtp->nodes[rtp->nr - 1]; |
172 | rtp->nodes[rtp->nr - 1] = NULL; |
173 | rtp->nr--; |
174 | } |
175 | } |
176 | if (ret == NULL) |
177 | ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask); |
178 | |
179 | BUG_ON(radix_tree_is_indirect_ptr(ret)); |
180 | return ret; |
181 | } |
182 | |
183 | static void radix_tree_node_rcu_free(struct rcu_head *head) |
184 | { |
185 | struct radix_tree_node *node = |
186 | container_of(head, struct radix_tree_node, rcu_head); |
187 | int i; |
188 | |
189 | /* |
190 | * must only free zeroed nodes into the slab. radix_tree_shrink |
191 | * can leave us with a non-NULL entry in the first slot, so clear |
192 | * that here to make sure. |
193 | */ |
194 | for (i = 0; i < RADIX_TREE_MAX_TAGS; i++) |
195 | tag_clear(node, i, 0); |
196 | |
197 | node->slots[0] = NULL; |
198 | node->count = 0; |
199 | |
200 | kmem_cache_free(radix_tree_node_cachep, node); |
201 | } |
202 | |
203 | static inline void |
204 | radix_tree_node_free(struct radix_tree_node *node) |
205 | { |
206 | call_rcu(&node->rcu_head, radix_tree_node_rcu_free); |
207 | } |
208 | |
209 | /* |
210 | * Load up this CPU's radix_tree_node buffer with sufficient objects to |
211 | * ensure that the addition of a single element in the tree cannot fail. On |
212 | * success, return zero, with preemption disabled. On error, return -ENOMEM |
213 | * with preemption not disabled. |
214 | * |
215 | * To make use of this facility, the radix tree must be initialised without |
216 | * __GFP_WAIT being passed to INIT_RADIX_TREE(). |
217 | */ |
218 | int radix_tree_preload(gfp_t gfp_mask) |
219 | { |
220 | struct radix_tree_preload *rtp; |
221 | struct radix_tree_node *node; |
222 | int ret = -ENOMEM; |
223 | |
224 | preempt_disable(); |
225 | rtp = &__get_cpu_var(radix_tree_preloads); |
226 | while (rtp->nr < ARRAY_SIZE(rtp->nodes)) { |
227 | preempt_enable(); |
228 | node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask); |
229 | if (node == NULL) |
230 | goto out; |
231 | preempt_disable(); |
232 | rtp = &__get_cpu_var(radix_tree_preloads); |
233 | if (rtp->nr < ARRAY_SIZE(rtp->nodes)) |
234 | rtp->nodes[rtp->nr++] = node; |
235 | else |
236 | kmem_cache_free(radix_tree_node_cachep, node); |
237 | } |
238 | ret = 0; |
239 | out: |
240 | return ret; |
241 | } |
242 | EXPORT_SYMBOL(radix_tree_preload); |
243 | |
244 | /* |
245 | * Return the maximum key which can be store into a |
246 | * radix tree with height HEIGHT. |
247 | */ |
248 | static inline unsigned long radix_tree_maxindex(unsigned int height) |
249 | { |
250 | return height_to_maxindex[height]; |
251 | } |
252 | |
253 | /* |
254 | * Extend a radix tree so it can store key @index. |
255 | */ |
256 | static int radix_tree_extend(struct radix_tree_root *root, unsigned long index) |
257 | { |
258 | struct radix_tree_node *node; |
259 | unsigned int height; |
260 | int tag; |
261 | |
262 | /* Figure out what the height should be. */ |
263 | height = root->height + 1; |
264 | while (index > radix_tree_maxindex(height)) |
265 | height++; |
266 | |
267 | if (root->rnode == NULL) { |
268 | root->height = height; |
269 | goto out; |
270 | } |
271 | |
272 | do { |
273 | unsigned int newheight; |
274 | if (!(node = radix_tree_node_alloc(root))) |
275 | return -ENOMEM; |
276 | |
277 | /* Increase the height. */ |
278 | node->slots[0] = indirect_to_ptr(root->rnode); |
279 | |
280 | /* Propagate the aggregated tag info into the new root */ |
281 | for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) { |
282 | if (root_tag_get(root, tag)) |
283 | tag_set(node, tag, 0); |
284 | } |
285 | |
286 | newheight = root->height+1; |
287 | node->height = newheight; |
288 | node->count = 1; |
289 | node = ptr_to_indirect(node); |
290 | rcu_assign_pointer(root->rnode, node); |
291 | root->height = newheight; |
292 | } while (height > root->height); |
293 | out: |
294 | return 0; |
295 | } |
296 | |
297 | /** |
298 | * radix_tree_insert - insert into a radix tree |
299 | * @root: radix tree root |
300 | * @index: index key |
301 | * @item: item to insert |
302 | * |
303 | * Insert an item into the radix tree at position @index. |
304 | */ |
305 | int radix_tree_insert(struct radix_tree_root *root, |
306 | unsigned long index, void *item) |
307 | { |
308 | struct radix_tree_node *node = NULL, *slot; |
309 | unsigned int height, shift; |
310 | int offset; |
311 | int error; |
312 | |
313 | BUG_ON(radix_tree_is_indirect_ptr(item)); |
314 | |
315 | /* Make sure the tree is high enough. */ |
316 | if (index > radix_tree_maxindex(root->height)) { |
317 | error = radix_tree_extend(root, index); |
318 | if (error) |
319 | return error; |
320 | } |
321 | |
322 | slot = indirect_to_ptr(root->rnode); |
323 | |
324 | height = root->height; |
325 | shift = (height-1) * RADIX_TREE_MAP_SHIFT; |
326 | |
327 | offset = 0; /* uninitialised var warning */ |
328 | while (height > 0) { |
329 | if (slot == NULL) { |
330 | /* Have to add a child node. */ |
331 | if (!(slot = radix_tree_node_alloc(root))) |
332 | return -ENOMEM; |
333 | slot->height = height; |
334 | if (node) { |
335 | rcu_assign_pointer(node->slots[offset], slot); |
336 | node->count++; |
337 | } else |
338 | rcu_assign_pointer(root->rnode, ptr_to_indirect(slot)); |
339 | } |
340 | |
341 | /* Go a level down */ |
342 | offset = (index >> shift) & RADIX_TREE_MAP_MASK; |
343 | node = slot; |
344 | slot = node->slots[offset]; |
345 | shift -= RADIX_TREE_MAP_SHIFT; |
346 | height--; |
347 | } |
348 | |
349 | if (slot != NULL) |
350 | return -EEXIST; |
351 | |
352 | if (node) { |
353 | node->count++; |
354 | rcu_assign_pointer(node->slots[offset], item); |
355 | BUG_ON(tag_get(node, 0, offset)); |
356 | BUG_ON(tag_get(node, 1, offset)); |
357 | } else { |
358 | rcu_assign_pointer(root->rnode, item); |
359 | BUG_ON(root_tag_get(root, 0)); |
360 | BUG_ON(root_tag_get(root, 1)); |
361 | } |
362 | |
363 | return 0; |
364 | } |
365 | EXPORT_SYMBOL(radix_tree_insert); |
366 | |
367 | /* |
368 | * is_slot == 1 : search for the slot. |
369 | * is_slot == 0 : search for the node. |
370 | */ |
371 | static void *radix_tree_lookup_element(struct radix_tree_root *root, |
372 | unsigned long index, int is_slot) |
373 | { |
374 | unsigned int height, shift; |
375 | struct radix_tree_node *node, **slot; |
376 | |
377 | node = rcu_dereference_raw(root->rnode); |
378 | if (node == NULL) |
379 | return NULL; |
380 | |
381 | if (!radix_tree_is_indirect_ptr(node)) { |
382 | if (index > 0) |
383 | return NULL; |
384 | return is_slot ? (void *)&root->rnode : node; |
385 | } |
386 | node = indirect_to_ptr(node); |
387 | |
388 | height = node->height; |
389 | if (index > radix_tree_maxindex(height)) |
390 | return NULL; |
391 | |
392 | shift = (height-1) * RADIX_TREE_MAP_SHIFT; |
393 | |
394 | do { |
395 | slot = (struct radix_tree_node **) |
396 | (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK)); |
397 | node = rcu_dereference_raw(*slot); |
398 | if (node == NULL) |
399 | return NULL; |
400 | |
401 | shift -= RADIX_TREE_MAP_SHIFT; |
402 | height--; |
403 | } while (height > 0); |
404 | |
405 | return is_slot ? (void *)slot : indirect_to_ptr(node); |
406 | } |
407 | |
408 | /** |
409 | * radix_tree_lookup_slot - lookup a slot in a radix tree |
410 | * @root: radix tree root |
411 | * @index: index key |
412 | * |
413 | * Returns: the slot corresponding to the position @index in the |
414 | * radix tree @root. This is useful for update-if-exists operations. |
415 | * |
416 | * This function can be called under rcu_read_lock iff the slot is not |
417 | * modified by radix_tree_replace_slot, otherwise it must be called |
418 | * exclusive from other writers. Any dereference of the slot must be done |
419 | * using radix_tree_deref_slot. |
420 | */ |
421 | void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index) |
422 | { |
423 | return (void **)radix_tree_lookup_element(root, index, 1); |
424 | } |
425 | EXPORT_SYMBOL(radix_tree_lookup_slot); |
426 | |
427 | /** |
428 | * radix_tree_lookup - perform lookup operation on a radix tree |
429 | * @root: radix tree root |
430 | * @index: index key |
431 | * |
432 | * Lookup the item at the position @index in the radix tree @root. |
433 | * |
434 | * This function can be called under rcu_read_lock, however the caller |
435 | * must manage lifetimes of leaf nodes (eg. RCU may also be used to free |
436 | * them safely). No RCU barriers are required to access or modify the |
437 | * returned item, however. |
438 | */ |
439 | void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) |
440 | { |
441 | return radix_tree_lookup_element(root, index, 0); |
442 | } |
443 | EXPORT_SYMBOL(radix_tree_lookup); |
444 | |
445 | /** |
446 | * radix_tree_tag_set - set a tag on a radix tree node |
447 | * @root: radix tree root |
448 | * @index: index key |
449 | * @tag: tag index |
450 | * |
451 | * Set the search tag (which must be < RADIX_TREE_MAX_TAGS) |
452 | * corresponding to @index in the radix tree. From |
453 | * the root all the way down to the leaf node. |
454 | * |
455 | * Returns the address of the tagged item. Setting a tag on a not-present |
456 | * item is a bug. |
457 | */ |
458 | void *radix_tree_tag_set(struct radix_tree_root *root, |
459 | unsigned long index, unsigned int tag) |
460 | { |
461 | unsigned int height, shift; |
462 | struct radix_tree_node *slot; |
463 | |
464 | height = root->height; |
465 | BUG_ON(index > radix_tree_maxindex(height)); |
466 | |
467 | slot = indirect_to_ptr(root->rnode); |
468 | shift = (height - 1) * RADIX_TREE_MAP_SHIFT; |
469 | |
470 | while (height > 0) { |
471 | int offset; |
472 | |
473 | offset = (index >> shift) & RADIX_TREE_MAP_MASK; |
474 | if (!tag_get(slot, tag, offset)) |
475 | tag_set(slot, tag, offset); |
476 | slot = slot->slots[offset]; |
477 | BUG_ON(slot == NULL); |
478 | shift -= RADIX_TREE_MAP_SHIFT; |
479 | height--; |
480 | } |
481 | |
482 | /* set the root's tag bit */ |
483 | if (slot && !root_tag_get(root, tag)) |
484 | root_tag_set(root, tag); |
485 | |
486 | return slot; |
487 | } |
488 | EXPORT_SYMBOL(radix_tree_tag_set); |
489 | |
490 | /** |
491 | * radix_tree_tag_clear - clear a tag on a radix tree node |
492 | * @root: radix tree root |
493 | * @index: index key |
494 | * @tag: tag index |
495 | * |
496 | * Clear the search tag (which must be < RADIX_TREE_MAX_TAGS) |
497 | * corresponding to @index in the radix tree. If |
498 | * this causes the leaf node to have no tags set then clear the tag in the |
499 | * next-to-leaf node, etc. |
500 | * |
501 | * Returns the address of the tagged item on success, else NULL. ie: |
502 | * has the same return value and semantics as radix_tree_lookup(). |
503 | */ |
504 | void *radix_tree_tag_clear(struct radix_tree_root *root, |
505 | unsigned long index, unsigned int tag) |
506 | { |
507 | /* |
508 | * The radix tree path needs to be one longer than the maximum path |
509 | * since the "list" is null terminated. |
510 | */ |
511 | struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path; |
512 | struct radix_tree_node *slot = NULL; |
513 | unsigned int height, shift; |
514 | |
515 | height = root->height; |
516 | if (index > radix_tree_maxindex(height)) |
517 | goto out; |
518 | |
519 | shift = (height - 1) * RADIX_TREE_MAP_SHIFT; |
520 | pathp->node = NULL; |
521 | slot = indirect_to_ptr(root->rnode); |
522 | |
523 | while (height > 0) { |
524 | int offset; |
525 | |
526 | if (slot == NULL) |
527 | goto out; |
528 | |
529 | offset = (index >> shift) & RADIX_TREE_MAP_MASK; |
530 | pathp[1].offset = offset; |
531 | pathp[1].node = slot; |
532 | slot = slot->slots[offset]; |
533 | pathp++; |
534 | shift -= RADIX_TREE_MAP_SHIFT; |
535 | height--; |
536 | } |
537 | |
538 | if (slot == NULL) |
539 | goto out; |
540 | |
541 | while (pathp->node) { |
542 | if (!tag_get(pathp->node, tag, pathp->offset)) |
543 | goto out; |
544 | tag_clear(pathp->node, tag, pathp->offset); |
545 | if (any_tag_set(pathp->node, tag)) |
546 | goto out; |
547 | pathp--; |
548 | } |
549 | |
550 | /* clear the root's tag bit */ |
551 | if (root_tag_get(root, tag)) |
552 | root_tag_clear(root, tag); |
553 | |
554 | out: |
555 | return slot; |
556 | } |
557 | EXPORT_SYMBOL(radix_tree_tag_clear); |
558 | |
559 | /** |
560 | * radix_tree_tag_get - get a tag on a radix tree node |
561 | * @root: radix tree root |
562 | * @index: index key |
563 | * @tag: tag index (< RADIX_TREE_MAX_TAGS) |
564 | * |
565 | * Return values: |
566 | * |
567 | * 0: tag not present or not set |
568 | * 1: tag set |
569 | * |
570 | * Note that the return value of this function may not be relied on, even if |
571 | * the RCU lock is held, unless tag modification and node deletion are excluded |
572 | * from concurrency. |
573 | */ |
574 | int radix_tree_tag_get(struct radix_tree_root *root, |
575 | unsigned long index, unsigned int tag) |
576 | { |
577 | unsigned int height, shift; |
578 | struct radix_tree_node *node; |
579 | int saw_unset_tag = 0; |
580 | |
581 | /* check the root's tag bit */ |
582 | if (!root_tag_get(root, tag)) |
583 | return 0; |
584 | |
585 | node = rcu_dereference_raw(root->rnode); |
586 | if (node == NULL) |
587 | return 0; |
588 | |
589 | if (!radix_tree_is_indirect_ptr(node)) |
590 | return (index == 0); |
591 | node = indirect_to_ptr(node); |
592 | |
593 | height = node->height; |
594 | if (index > radix_tree_maxindex(height)) |
595 | return 0; |
596 | |
597 | shift = (height - 1) * RADIX_TREE_MAP_SHIFT; |
598 | |
599 | for ( ; ; ) { |
600 | int offset; |
601 | |
602 | if (node == NULL) |
603 | return 0; |
604 | |
605 | offset = (index >> shift) & RADIX_TREE_MAP_MASK; |
606 | |
607 | /* |
608 | * This is just a debug check. Later, we can bale as soon as |
609 | * we see an unset tag. |
610 | */ |
611 | if (!tag_get(node, tag, offset)) |
612 | saw_unset_tag = 1; |
613 | if (height == 1) |
614 | return !!tag_get(node, tag, offset); |
615 | node = rcu_dereference_raw(node->slots[offset]); |
616 | shift -= RADIX_TREE_MAP_SHIFT; |
617 | height--; |
618 | } |
619 | } |
620 | EXPORT_SYMBOL(radix_tree_tag_get); |
621 | |
622 | /** |
623 | * radix_tree_range_tag_if_tagged - for each item in given range set given |
624 | * tag if item has another tag set |
625 | * @root: radix tree root |
626 | * @first_indexp: pointer to a starting index of a range to scan |
627 | * @last_index: last index of a range to scan |
628 | * @nr_to_tag: maximum number items to tag |
629 | * @iftag: tag index to test |
630 | * @settag: tag index to set if tested tag is set |
631 | * |
632 | * This function scans range of radix tree from first_index to last_index |
633 | * (inclusive). For each item in the range if iftag is set, the function sets |
634 | * also settag. The function stops either after tagging nr_to_tag items or |
635 | * after reaching last_index. |
636 | * |
637 | * The tags must be set from the leaf level only and propagated back up the |
638 | * path to the root. We must do this so that we resolve the full path before |
639 | * setting any tags on intermediate nodes. If we set tags as we descend, then |
640 | * we can get to the leaf node and find that the index that has the iftag |
641 | * set is outside the range we are scanning. This reults in dangling tags and |
642 | * can lead to problems with later tag operations (e.g. livelocks on lookups). |
643 | * |
644 | * The function returns number of leaves where the tag was set and sets |
645 | * *first_indexp to the first unscanned index. |
646 | * WARNING! *first_indexp can wrap if last_index is ULONG_MAX. Caller must |
647 | * be prepared to handle that. |
648 | */ |
649 | unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root, |
650 | unsigned long *first_indexp, unsigned long last_index, |
651 | unsigned long nr_to_tag, |
652 | unsigned int iftag, unsigned int settag) |
653 | { |
654 | unsigned int height = root->height; |
655 | struct radix_tree_path path[height]; |
656 | struct radix_tree_path *pathp = path; |
657 | struct radix_tree_node *slot; |
658 | unsigned int shift; |
659 | unsigned long tagged = 0; |
660 | unsigned long index = *first_indexp; |
661 | |
662 | last_index = min(last_index, radix_tree_maxindex(height)); |
663 | if (index > last_index) |
664 | return 0; |
665 | if (!nr_to_tag) |
666 | return 0; |
667 | if (!root_tag_get(root, iftag)) { |
668 | *first_indexp = last_index + 1; |
669 | return 0; |
670 | } |
671 | if (height == 0) { |
672 | *first_indexp = last_index + 1; |
673 | root_tag_set(root, settag); |
674 | return 1; |
675 | } |
676 | |
677 | shift = (height - 1) * RADIX_TREE_MAP_SHIFT; |
678 | slot = indirect_to_ptr(root->rnode); |
679 | |
680 | /* |
681 | * we fill the path from (root->height - 2) to 0, leaving the index at |
682 | * (root->height - 1) as a terminator. Zero the node in the terminator |
683 | * so that we can use this to end walk loops back up the path. |
684 | */ |
685 | path[height - 1].node = NULL; |
686 | |
687 | for (;;) { |
688 | int offset; |
689 | |
690 | offset = (index >> shift) & RADIX_TREE_MAP_MASK; |
691 | if (!slot->slots[offset]) |
692 | goto next; |
693 | if (!tag_get(slot, iftag, offset)) |
694 | goto next; |
695 | if (height > 1) { |
696 | /* Go down one level */ |
697 | height--; |
698 | shift -= RADIX_TREE_MAP_SHIFT; |
699 | path[height - 1].node = slot; |
700 | path[height - 1].offset = offset; |
701 | slot = slot->slots[offset]; |
702 | continue; |
703 | } |
704 | |
705 | /* tag the leaf */ |
706 | tagged++; |
707 | tag_set(slot, settag, offset); |
708 | |
709 | /* walk back up the path tagging interior nodes */ |
710 | pathp = &path[0]; |
711 | while (pathp->node) { |
712 | /* stop if we find a node with the tag already set */ |
713 | if (tag_get(pathp->node, settag, pathp->offset)) |
714 | break; |
715 | tag_set(pathp->node, settag, pathp->offset); |
716 | pathp++; |
717 | } |
718 | |
719 | next: |
720 | /* Go to next item at level determined by 'shift' */ |
721 | index = ((index >> shift) + 1) << shift; |
722 | /* Overflow can happen when last_index is ~0UL... */ |
723 | if (index > last_index || !index) |
724 | break; |
725 | if (tagged >= nr_to_tag) |
726 | break; |
727 | while (((index >> shift) & RADIX_TREE_MAP_MASK) == 0) { |
728 | /* |
729 | * We've fully scanned this node. Go up. Because |
730 | * last_index is guaranteed to be in the tree, what |
731 | * we do below cannot wander astray. |
732 | */ |
733 | slot = path[height - 1].node; |
734 | height++; |
735 | shift += RADIX_TREE_MAP_SHIFT; |
736 | } |
737 | } |
738 | /* |
739 | * We need not to tag the root tag if there is no tag which is set with |
740 | * settag within the range from *first_indexp to last_index. |
741 | */ |
742 | if (tagged > 0) |
743 | root_tag_set(root, settag); |
744 | *first_indexp = index; |
745 | |
746 | return tagged; |
747 | } |
748 | EXPORT_SYMBOL(radix_tree_range_tag_if_tagged); |
749 | |
750 | |
751 | /** |
752 | * radix_tree_next_hole - find the next hole (not-present entry) |
753 | * @root: tree root |
754 | * @index: index key |
755 | * @max_scan: maximum range to search |
756 | * |
757 | * Search the set [index, min(index+max_scan-1, MAX_INDEX)] for the lowest |
758 | * indexed hole. |
759 | * |
760 | * Returns: the index of the hole if found, otherwise returns an index |
761 | * outside of the set specified (in which case 'return - index >= max_scan' |
762 | * will be true). In rare cases of index wrap-around, 0 will be returned. |
763 | * |
764 | * radix_tree_next_hole may be called under rcu_read_lock. However, like |
765 | * radix_tree_gang_lookup, this will not atomically search a snapshot of |
766 | * the tree at a single point in time. For example, if a hole is created |
767 | * at index 5, then subsequently a hole is created at index 10, |
768 | * radix_tree_next_hole covering both indexes may return 10 if called |
769 | * under rcu_read_lock. |
770 | */ |
771 | unsigned long radix_tree_next_hole(struct radix_tree_root *root, |
772 | unsigned long index, unsigned long max_scan) |
773 | { |
774 | unsigned long i; |
775 | |
776 | for (i = 0; i < max_scan; i++) { |
777 | if (!radix_tree_lookup(root, index)) |
778 | break; |
779 | index++; |
780 | if (index == 0) |
781 | break; |
782 | } |
783 | |
784 | return index; |
785 | } |
786 | EXPORT_SYMBOL(radix_tree_next_hole); |
787 | |
788 | /** |
789 | * radix_tree_prev_hole - find the prev hole (not-present entry) |
790 | * @root: tree root |
791 | * @index: index key |
792 | * @max_scan: maximum range to search |
793 | * |
794 | * Search backwards in the range [max(index-max_scan+1, 0), index] |
795 | * for the first hole. |
796 | * |
797 | * Returns: the index of the hole if found, otherwise returns an index |
798 | * outside of the set specified (in which case 'index - return >= max_scan' |
799 | * will be true). In rare cases of wrap-around, ULONG_MAX will be returned. |
800 | * |
801 | * radix_tree_next_hole may be called under rcu_read_lock. However, like |
802 | * radix_tree_gang_lookup, this will not atomically search a snapshot of |
803 | * the tree at a single point in time. For example, if a hole is created |
804 | * at index 10, then subsequently a hole is created at index 5, |
805 | * radix_tree_prev_hole covering both indexes may return 5 if called under |
806 | * rcu_read_lock. |
807 | */ |
808 | unsigned long radix_tree_prev_hole(struct radix_tree_root *root, |
809 | unsigned long index, unsigned long max_scan) |
810 | { |
811 | unsigned long i; |
812 | |
813 | for (i = 0; i < max_scan; i++) { |
814 | if (!radix_tree_lookup(root, index)) |
815 | break; |
816 | index--; |
817 | if (index == ULONG_MAX) |
818 | break; |
819 | } |
820 | |
821 | return index; |
822 | } |
823 | EXPORT_SYMBOL(radix_tree_prev_hole); |
824 | |
825 | static unsigned int |
826 | __lookup(struct radix_tree_node *slot, void ***results, unsigned long index, |
827 | unsigned int max_items, unsigned long *next_index) |
828 | { |
829 | unsigned int nr_found = 0; |
830 | unsigned int shift, height; |
831 | unsigned long i; |
832 | |
833 | height = slot->height; |
834 | if (height == 0) |
835 | goto out; |
836 | shift = (height-1) * RADIX_TREE_MAP_SHIFT; |
837 | |
838 | for ( ; height > 1; height--) { |
839 | i = (index >> shift) & RADIX_TREE_MAP_MASK; |
840 | for (;;) { |
841 | if (slot->slots[i] != NULL) |
842 | break; |
843 | index &= ~((1UL << shift) - 1); |
844 | index += 1UL << shift; |
845 | if (index == 0) |
846 | goto out; /* 32-bit wraparound */ |
847 | i++; |
848 | if (i == RADIX_TREE_MAP_SIZE) |
849 | goto out; |
850 | } |
851 | |
852 | shift -= RADIX_TREE_MAP_SHIFT; |
853 | slot = rcu_dereference_raw(slot->slots[i]); |
854 | if (slot == NULL) |
855 | goto out; |
856 | } |
857 | |
858 | /* Bottom level: grab some items */ |
859 | for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) { |
860 | index++; |
861 | if (slot->slots[i]) { |
862 | results[nr_found++] = &(slot->slots[i]); |
863 | if (nr_found == max_items) |
864 | goto out; |
865 | } |
866 | } |
867 | out: |
868 | *next_index = index; |
869 | return nr_found; |
870 | } |
871 | |
872 | /** |
873 | * radix_tree_gang_lookup - perform multiple lookup on a radix tree |
874 | * @root: radix tree root |
875 | * @results: where the results of the lookup are placed |
876 | * @first_index: start the lookup from this key |
877 | * @max_items: place up to this many items at *results |
878 | * |
879 | * Performs an index-ascending scan of the tree for present items. Places |
880 | * them at *@results and returns the number of items which were placed at |
881 | * *@results. |
882 | * |
883 | * The implementation is naive. |
884 | * |
885 | * Like radix_tree_lookup, radix_tree_gang_lookup may be called under |
886 | * rcu_read_lock. In this case, rather than the returned results being |
887 | * an atomic snapshot of the tree at a single point in time, the semantics |
888 | * of an RCU protected gang lookup are as though multiple radix_tree_lookups |
889 | * have been issued in individual locks, and results stored in 'results'. |
890 | */ |
891 | unsigned int |
892 | radix_tree_gang_lookup(struct radix_tree_root *root, void **results, |
893 | unsigned long first_index, unsigned int max_items) |
894 | { |
895 | unsigned long max_index; |
896 | struct radix_tree_node *node; |
897 | unsigned long cur_index = first_index; |
898 | unsigned int ret; |
899 | |
900 | node = rcu_dereference_raw(root->rnode); |
901 | if (!node) |
902 | return 0; |
903 | |
904 | if (!radix_tree_is_indirect_ptr(node)) { |
905 | if (first_index > 0) |
906 | return 0; |
907 | results[0] = node; |
908 | return 1; |
909 | } |
910 | node = indirect_to_ptr(node); |
911 | |
912 | max_index = radix_tree_maxindex(node->height); |
913 | |
914 | ret = 0; |
915 | while (ret < max_items) { |
916 | unsigned int nr_found, slots_found, i; |
917 | unsigned long next_index; /* Index of next search */ |
918 | |
919 | if (cur_index > max_index) |
920 | break; |
921 | slots_found = __lookup(node, (void ***)results + ret, cur_index, |
922 | max_items - ret, &next_index); |
923 | nr_found = 0; |
924 | for (i = 0; i < slots_found; i++) { |
925 | struct radix_tree_node *slot; |
926 | slot = *(((void ***)results)[ret + i]); |
927 | if (!slot) |
928 | continue; |
929 | results[ret + nr_found] = |
930 | indirect_to_ptr(rcu_dereference_raw(slot)); |
931 | nr_found++; |
932 | } |
933 | ret += nr_found; |
934 | if (next_index == 0) |
935 | break; |
936 | cur_index = next_index; |
937 | } |
938 | |
939 | return ret; |
940 | } |
941 | EXPORT_SYMBOL(radix_tree_gang_lookup); |
942 | |
943 | /** |
944 | * radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree |
945 | * @root: radix tree root |
946 | * @results: where the results of the lookup are placed |
947 | * @first_index: start the lookup from this key |
948 | * @max_items: place up to this many items at *results |
949 | * |
950 | * Performs an index-ascending scan of the tree for present items. Places |
951 | * their slots at *@results and returns the number of items which were |
952 | * placed at *@results. |
953 | * |
954 | * The implementation is naive. |
955 | * |
956 | * Like radix_tree_gang_lookup as far as RCU and locking goes. Slots must |
957 | * be dereferenced with radix_tree_deref_slot, and if using only RCU |
958 | * protection, radix_tree_deref_slot may fail requiring a retry. |
959 | */ |
960 | unsigned int |
961 | radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results, |
962 | unsigned long first_index, unsigned int max_items) |
963 | { |
964 | unsigned long max_index; |
965 | struct radix_tree_node *node; |
966 | unsigned long cur_index = first_index; |
967 | unsigned int ret; |
968 | |
969 | node = rcu_dereference_raw(root->rnode); |
970 | if (!node) |
971 | return 0; |
972 | |
973 | if (!radix_tree_is_indirect_ptr(node)) { |
974 | if (first_index > 0) |
975 | return 0; |
976 | results[0] = (void **)&root->rnode; |
977 | return 1; |
978 | } |
979 | node = indirect_to_ptr(node); |
980 | |
981 | max_index = radix_tree_maxindex(node->height); |
982 | |
983 | ret = 0; |
984 | while (ret < max_items) { |
985 | unsigned int slots_found; |
986 | unsigned long next_index; /* Index of next search */ |
987 | |
988 | if (cur_index > max_index) |
989 | break; |
990 | slots_found = __lookup(node, results + ret, cur_index, |
991 | max_items - ret, &next_index); |
992 | ret += slots_found; |
993 | if (next_index == 0) |
994 | break; |
995 | cur_index = next_index; |
996 | } |
997 | |
998 | return ret; |
999 | } |
1000 | EXPORT_SYMBOL(radix_tree_gang_lookup_slot); |
1001 | |
1002 | /* |
1003 | * FIXME: the two tag_get()s here should use find_next_bit() instead of |
1004 | * open-coding the search. |
1005 | */ |
1006 | static unsigned int |
1007 | __lookup_tag(struct radix_tree_node *slot, void ***results, unsigned long index, |
1008 | unsigned int max_items, unsigned long *next_index, unsigned int tag) |
1009 | { |
1010 | unsigned int nr_found = 0; |
1011 | unsigned int shift, height; |
1012 | |
1013 | height = slot->height; |
1014 | if (height == 0) |
1015 | goto out; |
1016 | shift = (height-1) * RADIX_TREE_MAP_SHIFT; |
1017 | |
1018 | while (height > 0) { |
1019 | unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK ; |
1020 | |
1021 | for (;;) { |
1022 | if (tag_get(slot, tag, i)) |
1023 | break; |
1024 | index &= ~((1UL << shift) - 1); |
1025 | index += 1UL << shift; |
1026 | if (index == 0) |
1027 | goto out; /* 32-bit wraparound */ |
1028 | i++; |
1029 | if (i == RADIX_TREE_MAP_SIZE) |
1030 | goto out; |
1031 | } |
1032 | height--; |
1033 | if (height == 0) { /* Bottom level: grab some items */ |
1034 | unsigned long j = index & RADIX_TREE_MAP_MASK; |
1035 | |
1036 | for ( ; j < RADIX_TREE_MAP_SIZE; j++) { |
1037 | index++; |
1038 | if (!tag_get(slot, tag, j)) |
1039 | continue; |
1040 | /* |
1041 | * Even though the tag was found set, we need to |
1042 | * recheck that we have a non-NULL node, because |
1043 | * if this lookup is lockless, it may have been |
1044 | * subsequently deleted. |
1045 | * |
1046 | * Similar care must be taken in any place that |
1047 | * lookup ->slots[x] without a lock (ie. can't |
1048 | * rely on its value remaining the same). |
1049 | */ |
1050 | if (slot->slots[j]) { |
1051 | results[nr_found++] = &(slot->slots[j]); |
1052 | if (nr_found == max_items) |
1053 | goto out; |
1054 | } |
1055 | } |
1056 | } |
1057 | shift -= RADIX_TREE_MAP_SHIFT; |
1058 | slot = rcu_dereference_raw(slot->slots[i]); |
1059 | if (slot == NULL) |
1060 | break; |
1061 | } |
1062 | out: |
1063 | *next_index = index; |
1064 | return nr_found; |
1065 | } |
1066 | |
1067 | /** |
1068 | * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree |
1069 | * based on a tag |
1070 | * @root: radix tree root |
1071 | * @results: where the results of the lookup are placed |
1072 | * @first_index: start the lookup from this key |
1073 | * @max_items: place up to this many items at *results |
1074 | * @tag: the tag index (< RADIX_TREE_MAX_TAGS) |
1075 | * |
1076 | * Performs an index-ascending scan of the tree for present items which |
1077 | * have the tag indexed by @tag set. Places the items at *@results and |
1078 | * returns the number of items which were placed at *@results. |
1079 | */ |
1080 | unsigned int |
1081 | radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, |
1082 | unsigned long first_index, unsigned int max_items, |
1083 | unsigned int tag) |
1084 | { |
1085 | struct radix_tree_node *node; |
1086 | unsigned long max_index; |
1087 | unsigned long cur_index = first_index; |
1088 | unsigned int ret; |
1089 | |
1090 | /* check the root's tag bit */ |
1091 | if (!root_tag_get(root, tag)) |
1092 | return 0; |
1093 | |
1094 | node = rcu_dereference_raw(root->rnode); |
1095 | if (!node) |
1096 | return 0; |
1097 | |
1098 | if (!radix_tree_is_indirect_ptr(node)) { |
1099 | if (first_index > 0) |
1100 | return 0; |
1101 | results[0] = node; |
1102 | return 1; |
1103 | } |
1104 | node = indirect_to_ptr(node); |
1105 | |
1106 | max_index = radix_tree_maxindex(node->height); |
1107 | |
1108 | ret = 0; |
1109 | while (ret < max_items) { |
1110 | unsigned int nr_found, slots_found, i; |
1111 | unsigned long next_index; /* Index of next search */ |
1112 | |
1113 | if (cur_index > max_index) |
1114 | break; |
1115 | slots_found = __lookup_tag(node, (void ***)results + ret, |
1116 | cur_index, max_items - ret, &next_index, tag); |
1117 | nr_found = 0; |
1118 | for (i = 0; i < slots_found; i++) { |
1119 | struct radix_tree_node *slot; |
1120 | slot = *(((void ***)results)[ret + i]); |
1121 | if (!slot) |
1122 | continue; |
1123 | results[ret + nr_found] = |
1124 | indirect_to_ptr(rcu_dereference_raw(slot)); |
1125 | nr_found++; |
1126 | } |
1127 | ret += nr_found; |
1128 | if (next_index == 0) |
1129 | break; |
1130 | cur_index = next_index; |
1131 | } |
1132 | |
1133 | return ret; |
1134 | } |
1135 | EXPORT_SYMBOL(radix_tree_gang_lookup_tag); |
1136 | |
1137 | /** |
1138 | * radix_tree_gang_lookup_tag_slot - perform multiple slot lookup on a |
1139 | * radix tree based on a tag |
1140 | * @root: radix tree root |
1141 | * @results: where the results of the lookup are placed |
1142 | * @first_index: start the lookup from this key |
1143 | * @max_items: place up to this many items at *results |
1144 | * @tag: the tag index (< RADIX_TREE_MAX_TAGS) |
1145 | * |
1146 | * Performs an index-ascending scan of the tree for present items which |
1147 | * have the tag indexed by @tag set. Places the slots at *@results and |
1148 | * returns the number of slots which were placed at *@results. |
1149 | */ |
1150 | unsigned int |
1151 | radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results, |
1152 | unsigned long first_index, unsigned int max_items, |
1153 | unsigned int tag) |
1154 | { |
1155 | struct radix_tree_node *node; |
1156 | unsigned long max_index; |
1157 | unsigned long cur_index = first_index; |
1158 | unsigned int ret; |
1159 | |
1160 | /* check the root's tag bit */ |
1161 | if (!root_tag_get(root, tag)) |
1162 | return 0; |
1163 | |
1164 | node = rcu_dereference_raw(root->rnode); |
1165 | if (!node) |
1166 | return 0; |
1167 | |
1168 | if (!radix_tree_is_indirect_ptr(node)) { |
1169 | if (first_index > 0) |
1170 | return 0; |
1171 | results[0] = (void **)&root->rnode; |
1172 | return 1; |
1173 | } |
1174 | node = indirect_to_ptr(node); |
1175 | |
1176 | max_index = radix_tree_maxindex(node->height); |
1177 | |
1178 | ret = 0; |
1179 | while (ret < max_items) { |
1180 | unsigned int slots_found; |
1181 | unsigned long next_index; /* Index of next search */ |
1182 | |
1183 | if (cur_index > max_index) |
1184 | break; |
1185 | slots_found = __lookup_tag(node, results + ret, |
1186 | cur_index, max_items - ret, &next_index, tag); |
1187 | ret += slots_found; |
1188 | if (next_index == 0) |
1189 | break; |
1190 | cur_index = next_index; |
1191 | } |
1192 | |
1193 | return ret; |
1194 | } |
1195 | EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot); |
1196 | |
1197 | |
1198 | /** |
1199 | * radix_tree_shrink - shrink height of a radix tree to minimal |
1200 | * @root radix tree root |
1201 | */ |
1202 | static inline void radix_tree_shrink(struct radix_tree_root *root) |
1203 | { |
1204 | /* try to shrink tree height */ |
1205 | while (root->height > 0) { |
1206 | struct radix_tree_node *to_free = root->rnode; |
1207 | void *newptr; |
1208 | |
1209 | BUG_ON(!radix_tree_is_indirect_ptr(to_free)); |
1210 | to_free = indirect_to_ptr(to_free); |
1211 | |
1212 | /* |
1213 | * The candidate node has more than one child, or its child |
1214 | * is not at the leftmost slot, we cannot shrink. |
1215 | */ |
1216 | if (to_free->count != 1) |
1217 | break; |
1218 | if (!to_free->slots[0]) |
1219 | break; |
1220 | |
1221 | /* |
1222 | * We don't need rcu_assign_pointer(), since we are simply |
1223 | * moving the node from one part of the tree to another: if it |
1224 | * was safe to dereference the old pointer to it |
1225 | * (to_free->slots[0]), it will be safe to dereference the new |
1226 | * one (root->rnode) as far as dependent read barriers go. |
1227 | */ |
1228 | newptr = to_free->slots[0]; |
1229 | if (root->height > 1) |
1230 | newptr = ptr_to_indirect(newptr); |
1231 | root->rnode = newptr; |
1232 | root->height--; |
1233 | |
1234 | /* |
1235 | * We have a dilemma here. The node's slot[0] must not be |
1236 | * NULLed in case there are concurrent lookups expecting to |
1237 | * find the item. However if this was a bottom-level node, |
1238 | * then it may be subject to the slot pointer being visible |
1239 | * to callers dereferencing it. If item corresponding to |
1240 | * slot[0] is subsequently deleted, these callers would expect |
1241 | * their slot to become empty sooner or later. |
1242 | * |
1243 | * For example, lockless pagecache will look up a slot, deref |
1244 | * the page pointer, and if the page is 0 refcount it means it |
1245 | * was concurrently deleted from pagecache so try the deref |
1246 | * again. Fortunately there is already a requirement for logic |
1247 | * to retry the entire slot lookup -- the indirect pointer |
1248 | * problem (replacing direct root node with an indirect pointer |
1249 | * also results in a stale slot). So tag the slot as indirect |
1250 | * to force callers to retry. |
1251 | */ |
1252 | if (root->height == 0) |
1253 | *((unsigned long *)&to_free->slots[0]) |= |
1254 | RADIX_TREE_INDIRECT_PTR; |
1255 | |
1256 | radix_tree_node_free(to_free); |
1257 | } |
1258 | } |
1259 | |
1260 | /** |
1261 | * radix_tree_delete - delete an item from a radix tree |
1262 | * @root: radix tree root |
1263 | * @index: index key |
1264 | * |
1265 | * Remove the item at @index from the radix tree rooted at @root. |
1266 | * |
1267 | * Returns the address of the deleted item, or NULL if it was not present. |
1268 | */ |
1269 | void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) |
1270 | { |
1271 | /* |
1272 | * The radix tree path needs to be one longer than the maximum path |
1273 | * since the "list" is null terminated. |
1274 | */ |
1275 | struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path; |
1276 | struct radix_tree_node *slot = NULL; |
1277 | struct radix_tree_node *to_free; |
1278 | unsigned int height, shift; |
1279 | int tag; |
1280 | int offset; |
1281 | |
1282 | height = root->height; |
1283 | if (index > radix_tree_maxindex(height)) |
1284 | goto out; |
1285 | |
1286 | slot = root->rnode; |
1287 | if (height == 0) { |
1288 | root_tag_clear_all(root); |
1289 | root->rnode = NULL; |
1290 | goto out; |
1291 | } |
1292 | slot = indirect_to_ptr(slot); |
1293 | |
1294 | shift = (height - 1) * RADIX_TREE_MAP_SHIFT; |
1295 | pathp->node = NULL; |
1296 | |
1297 | do { |
1298 | if (slot == NULL) |
1299 | goto out; |
1300 | |
1301 | pathp++; |
1302 | offset = (index >> shift) & RADIX_TREE_MAP_MASK; |
1303 | pathp->offset = offset; |
1304 | pathp->node = slot; |
1305 | slot = slot->slots[offset]; |
1306 | shift -= RADIX_TREE_MAP_SHIFT; |
1307 | height--; |
1308 | } while (height > 0); |
1309 | |
1310 | if (slot == NULL) |
1311 | goto out; |
1312 | |
1313 | /* |
1314 | * Clear all tags associated with the just-deleted item |
1315 | */ |
1316 | for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) { |
1317 | if (tag_get(pathp->node, tag, pathp->offset)) |
1318 | radix_tree_tag_clear(root, index, tag); |
1319 | } |
1320 | |
1321 | to_free = NULL; |
1322 | /* Now free the nodes we do not need anymore */ |
1323 | while (pathp->node) { |
1324 | pathp->node->slots[pathp->offset] = NULL; |
1325 | pathp->node->count--; |
1326 | /* |
1327 | * Queue the node for deferred freeing after the |
1328 | * last reference to it disappears (set NULL, above). |
1329 | */ |
1330 | if (to_free) |
1331 | radix_tree_node_free(to_free); |
1332 | |
1333 | if (pathp->node->count) { |
1334 | if (pathp->node == indirect_to_ptr(root->rnode)) |
1335 | radix_tree_shrink(root); |
1336 | goto out; |
1337 | } |
1338 | |
1339 | /* Node with zero slots in use so free it */ |
1340 | to_free = pathp->node; |
1341 | pathp--; |
1342 | |
1343 | } |
1344 | root_tag_clear_all(root); |
1345 | root->height = 0; |
1346 | root->rnode = NULL; |
1347 | if (to_free) |
1348 | radix_tree_node_free(to_free); |
1349 | |
1350 | out: |
1351 | return slot; |
1352 | } |
1353 | EXPORT_SYMBOL(radix_tree_delete); |
1354 | |
1355 | /** |
1356 | * radix_tree_tagged - test whether any items in the tree are tagged |
1357 | * @root: radix tree root |
1358 | * @tag: tag to test |
1359 | */ |
1360 | int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag) |
1361 | { |
1362 | return root_tag_get(root, tag); |
1363 | } |
1364 | EXPORT_SYMBOL(radix_tree_tagged); |
1365 | |
1366 | static void |
1367 | radix_tree_node_ctor(void *node) |
1368 | { |
1369 | memset(node, 0, sizeof(struct radix_tree_node)); |
1370 | } |
1371 | |
1372 | static __init unsigned long __maxindex(unsigned int height) |
1373 | { |
1374 | unsigned int width = height * RADIX_TREE_MAP_SHIFT; |
1375 | int shift = RADIX_TREE_INDEX_BITS - width; |
1376 | |
1377 | if (shift < 0) |
1378 | return ~0UL; |
1379 | if (shift >= BITS_PER_LONG) |
1380 | return 0UL; |
1381 | return ~0UL >> shift; |
1382 | } |
1383 | |
1384 | static __init void radix_tree_init_maxindex(void) |
1385 | { |
1386 | unsigned int i; |
1387 | |
1388 | for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++) |
1389 | height_to_maxindex[i] = __maxindex(i); |
1390 | } |
1391 | |
1392 | static int radix_tree_callback(struct notifier_block *nfb, |
1393 | unsigned long action, |
1394 | void *hcpu) |
1395 | { |
1396 | int cpu = (long)hcpu; |
1397 | struct radix_tree_preload *rtp; |
1398 | |
1399 | /* Free per-cpu pool of perloaded nodes */ |
1400 | if (action == CPU_DEAD || action == CPU_DEAD_FROZEN) { |
1401 | rtp = &per_cpu(radix_tree_preloads, cpu); |
1402 | while (rtp->nr) { |
1403 | kmem_cache_free(radix_tree_node_cachep, |
1404 | rtp->nodes[rtp->nr-1]); |
1405 | rtp->nodes[rtp->nr-1] = NULL; |
1406 | rtp->nr--; |
1407 | } |
1408 | } |
1409 | return NOTIFY_OK; |
1410 | } |
1411 | |
1412 | void __init radix_tree_init(void) |
1413 | { |
1414 | radix_tree_node_cachep = kmem_cache_create("radix_tree_node", |
1415 | sizeof(struct radix_tree_node), 0, |
1416 | SLAB_PANIC | SLAB_RECLAIM_ACCOUNT, |
1417 | radix_tree_node_ctor); |
1418 | radix_tree_init_maxindex(); |
1419 | hotcpu_notifier(radix_tree_callback, 0); |
1420 | } |
1421 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9