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
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.
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.
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.
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/gfp.h>
32 #include <linux/string.h>
33 #include <linux/bitops.h>
34 #include <linux/rcupdate.h>
38 #define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6)
40 #define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */
43 #define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT)
44 #define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1)
46 #define RADIX_TREE_TAG_LONGS \
47 ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
49 struct radix_tree_node
{
50 unsigned int height
; /* Height from the bottom */
52 struct rcu_head rcu_head
;
53 void *slots
[RADIX_TREE_MAP_SIZE
];
54 unsigned long tags
[RADIX_TREE_MAX_TAGS
][RADIX_TREE_TAG_LONGS
];
57 struct radix_tree_path
{
58 struct radix_tree_node
*node
;
62 #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
63 #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
64 RADIX_TREE_MAP_SHIFT))
67 * The height_to_maxindex array needs to be one deeper than the maximum
68 * path as height 0 holds only 1 entry.
70 static unsigned long height_to_maxindex
[RADIX_TREE_MAX_PATH
+ 1] __read_mostly
;
73 * Radix tree node cache.
75 static struct kmem_cache
*radix_tree_node_cachep
;
78 * Per-cpu pool of preloaded nodes
80 struct radix_tree_preload
{
82 struct radix_tree_node
*nodes
[RADIX_TREE_MAX_PATH
];
84 static DEFINE_PER_CPU(struct radix_tree_preload
, radix_tree_preloads
) = { 0, };
86 static inline gfp_t
root_gfp_mask(struct radix_tree_root
*root
)
88 return root
->gfp_mask
& __GFP_BITS_MASK
;
91 static inline void tag_set(struct radix_tree_node
*node
, unsigned int tag
,
94 __set_bit(offset
, node
->tags
[tag
]);
97 static inline void tag_clear(struct radix_tree_node
*node
, unsigned int tag
,
100 __clear_bit(offset
, node
->tags
[tag
]);
103 static inline int tag_get(struct radix_tree_node
*node
, unsigned int tag
,
106 return test_bit(offset
, node
->tags
[tag
]);
109 static inline void root_tag_set(struct radix_tree_root
*root
, unsigned int tag
)
111 root
->gfp_mask
|= (__force gfp_t
)(1 << (tag
+ __GFP_BITS_SHIFT
));
114 static inline void root_tag_clear(struct radix_tree_root
*root
, unsigned int tag
)
116 root
->gfp_mask
&= (__force gfp_t
)~(1 << (tag
+ __GFP_BITS_SHIFT
));
119 static inline void root_tag_clear_all(struct radix_tree_root
*root
)
121 root
->gfp_mask
&= __GFP_BITS_MASK
;
124 static inline int root_tag_get(struct radix_tree_root
*root
, unsigned int tag
)
126 return (__force
unsigned)root
->gfp_mask
& (1 << (tag
+ __GFP_BITS_SHIFT
));
130 * Returns 1 if any slot in the node has this tag set.
131 * Otherwise returns 0.
133 static inline int any_tag_set(struct radix_tree_node
*node
, unsigned int tag
)
136 for (idx
= 0; idx
< RADIX_TREE_TAG_LONGS
; idx
++) {
137 if (node
->tags
[tag
][idx
])
143 * This assumes that the caller has performed appropriate preallocation, and
144 * that the caller has pinned this thread of control to the current CPU.
146 static struct radix_tree_node
*
147 radix_tree_node_alloc(struct radix_tree_root
*root
)
149 struct radix_tree_node
*ret
= NULL
;
150 gfp_t gfp_mask
= root_gfp_mask(root
);
152 if (!(gfp_mask
& __GFP_WAIT
)) {
153 struct radix_tree_preload
*rtp
;
156 * Provided the caller has preloaded here, we will always
157 * succeed in getting a node here (and never reach
160 rtp
= &__get_cpu_var(radix_tree_preloads
);
162 ret
= rtp
->nodes
[rtp
->nr
- 1];
163 rtp
->nodes
[rtp
->nr
- 1] = NULL
;
168 ret
= kmem_cache_alloc(radix_tree_node_cachep
, gfp_mask
);
170 BUG_ON(radix_tree_is_indirect_ptr(ret
));
174 static void radix_tree_node_rcu_free(struct rcu_head
*head
)
176 struct radix_tree_node
*node
=
177 container_of(head
, struct radix_tree_node
, rcu_head
);
180 * must only free zeroed nodes into the slab. radix_tree_shrink
181 * can leave us with a non-NULL entry in the first slot, so clear
182 * that here to make sure.
184 tag_clear(node
, 0, 0);
185 tag_clear(node
, 1, 0);
186 node
->slots
[0] = NULL
;
189 kmem_cache_free(radix_tree_node_cachep
, node
);
193 radix_tree_node_free(struct radix_tree_node
*node
)
195 call_rcu(&node
->rcu_head
, radix_tree_node_rcu_free
);
199 * Load up this CPU's radix_tree_node buffer with sufficient objects to
200 * ensure that the addition of a single element in the tree cannot fail. On
201 * success, return zero, with preemption disabled. On error, return -ENOMEM
202 * with preemption not disabled.
204 * To make use of this facility, the radix tree must be initialised without
205 * __GFP_WAIT being passed to INIT_RADIX_TREE().
207 int radix_tree_preload(gfp_t gfp_mask
)
209 struct radix_tree_preload
*rtp
;
210 struct radix_tree_node
*node
;
214 rtp
= &__get_cpu_var(radix_tree_preloads
);
215 while (rtp
->nr
< ARRAY_SIZE(rtp
->nodes
)) {
217 node
= kmem_cache_alloc(radix_tree_node_cachep
, gfp_mask
);
221 rtp
= &__get_cpu_var(radix_tree_preloads
);
222 if (rtp
->nr
< ARRAY_SIZE(rtp
->nodes
))
223 rtp
->nodes
[rtp
->nr
++] = node
;
225 kmem_cache_free(radix_tree_node_cachep
, node
);
231 EXPORT_SYMBOL(radix_tree_preload
);
234 * Return the maximum key which can be store into a
235 * radix tree with height HEIGHT.
237 static inline unsigned long radix_tree_maxindex(unsigned int height
)
239 return height_to_maxindex
[height
];
243 * Extend a radix tree so it can store key @index.
245 static int radix_tree_extend(struct radix_tree_root
*root
, unsigned long index
)
247 struct radix_tree_node
*node
;
251 /* Figure out what the height should be. */
252 height
= root
->height
+ 1;
253 while (index
> radix_tree_maxindex(height
))
256 if (root
->rnode
== NULL
) {
257 root
->height
= height
;
262 unsigned int newheight
;
263 if (!(node
= radix_tree_node_alloc(root
)))
266 /* Increase the height. */
267 node
->slots
[0] = radix_tree_indirect_to_ptr(root
->rnode
);
269 /* Propagate the aggregated tag info into the new root */
270 for (tag
= 0; tag
< RADIX_TREE_MAX_TAGS
; tag
++) {
271 if (root_tag_get(root
, tag
))
272 tag_set(node
, tag
, 0);
275 newheight
= root
->height
+1;
276 node
->height
= newheight
;
278 node
= radix_tree_ptr_to_indirect(node
);
279 rcu_assign_pointer(root
->rnode
, node
);
280 root
->height
= newheight
;
281 } while (height
> root
->height
);
287 * radix_tree_insert - insert into a radix tree
288 * @root: radix tree root
290 * @item: item to insert
292 * Insert an item into the radix tree at position @index.
294 int radix_tree_insert(struct radix_tree_root
*root
,
295 unsigned long index
, void *item
)
297 struct radix_tree_node
*node
= NULL
, *slot
;
298 unsigned int height
, shift
;
302 BUG_ON(radix_tree_is_indirect_ptr(item
));
304 /* Make sure the tree is high enough. */
305 if (index
> radix_tree_maxindex(root
->height
)) {
306 error
= radix_tree_extend(root
, index
);
311 slot
= radix_tree_indirect_to_ptr(root
->rnode
);
313 height
= root
->height
;
314 shift
= (height
-1) * RADIX_TREE_MAP_SHIFT
;
316 offset
= 0; /* uninitialised var warning */
319 /* Have to add a child node. */
320 if (!(slot
= radix_tree_node_alloc(root
)))
322 slot
->height
= height
;
324 rcu_assign_pointer(node
->slots
[offset
], slot
);
327 rcu_assign_pointer(root
->rnode
,
328 radix_tree_ptr_to_indirect(slot
));
331 /* Go a level down */
332 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
334 slot
= node
->slots
[offset
];
335 shift
-= RADIX_TREE_MAP_SHIFT
;
344 rcu_assign_pointer(node
->slots
[offset
], item
);
345 BUG_ON(tag_get(node
, 0, offset
));
346 BUG_ON(tag_get(node
, 1, offset
));
348 rcu_assign_pointer(root
->rnode
, item
);
349 BUG_ON(root_tag_get(root
, 0));
350 BUG_ON(root_tag_get(root
, 1));
355 EXPORT_SYMBOL(radix_tree_insert
);
358 * is_slot == 1 : search for the slot.
359 * is_slot == 0 : search for the node.
361 static void *radix_tree_lookup_element(struct radix_tree_root
*root
,
362 unsigned long index
, int is_slot
)
364 unsigned int height
, shift
;
365 struct radix_tree_node
*node
, **slot
;
367 node
= rcu_dereference(root
->rnode
);
371 if (!radix_tree_is_indirect_ptr(node
)) {
374 return is_slot
? (void *)&root
->rnode
: node
;
376 node
= radix_tree_indirect_to_ptr(node
);
378 height
= node
->height
;
379 if (index
> radix_tree_maxindex(height
))
382 shift
= (height
-1) * RADIX_TREE_MAP_SHIFT
;
385 slot
= (struct radix_tree_node
**)
386 (node
->slots
+ ((index
>>shift
) & RADIX_TREE_MAP_MASK
));
387 node
= rcu_dereference(*slot
);
391 shift
-= RADIX_TREE_MAP_SHIFT
;
393 } while (height
> 0);
395 return is_slot
? (void *)slot
:node
;
399 * radix_tree_lookup_slot - lookup a slot in a radix tree
400 * @root: radix tree root
403 * Returns: the slot corresponding to the position @index in the
404 * radix tree @root. This is useful for update-if-exists operations.
406 * This function can be called under rcu_read_lock iff the slot is not
407 * modified by radix_tree_replace_slot, otherwise it must be called
408 * exclusive from other writers. Any dereference of the slot must be done
409 * using radix_tree_deref_slot.
411 void **radix_tree_lookup_slot(struct radix_tree_root
*root
, unsigned long index
)
413 return (void **)radix_tree_lookup_element(root
, index
, 1);
415 EXPORT_SYMBOL(radix_tree_lookup_slot
);
418 * radix_tree_lookup - perform lookup operation on a radix tree
419 * @root: radix tree root
422 * Lookup the item at the position @index in the radix tree @root.
424 * This function can be called under rcu_read_lock, however the caller
425 * must manage lifetimes of leaf nodes (eg. RCU may also be used to free
426 * them safely). No RCU barriers are required to access or modify the
427 * returned item, however.
429 void *radix_tree_lookup(struct radix_tree_root
*root
, unsigned long index
)
431 return radix_tree_lookup_element(root
, index
, 0);
433 EXPORT_SYMBOL(radix_tree_lookup
);
436 * radix_tree_tag_set - set a tag on a radix tree node
437 * @root: radix tree root
441 * Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
442 * corresponding to @index in the radix tree. From
443 * the root all the way down to the leaf node.
445 * Returns the address of the tagged item. Setting a tag on a not-present
448 void *radix_tree_tag_set(struct radix_tree_root
*root
,
449 unsigned long index
, unsigned int tag
)
451 unsigned int height
, shift
;
452 struct radix_tree_node
*slot
;
454 height
= root
->height
;
455 BUG_ON(index
> radix_tree_maxindex(height
));
457 slot
= radix_tree_indirect_to_ptr(root
->rnode
);
458 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
463 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
464 if (!tag_get(slot
, tag
, offset
))
465 tag_set(slot
, tag
, offset
);
466 slot
= slot
->slots
[offset
];
467 BUG_ON(slot
== NULL
);
468 shift
-= RADIX_TREE_MAP_SHIFT
;
472 /* set the root's tag bit */
473 if (slot
&& !root_tag_get(root
, tag
))
474 root_tag_set(root
, tag
);
478 EXPORT_SYMBOL(radix_tree_tag_set
);
481 * radix_tree_tag_clear - clear a tag on a radix tree node
482 * @root: radix tree root
486 * Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
487 * corresponding to @index in the radix tree. If
488 * this causes the leaf node to have no tags set then clear the tag in the
489 * next-to-leaf node, etc.
491 * Returns the address of the tagged item on success, else NULL. ie:
492 * has the same return value and semantics as radix_tree_lookup().
494 void *radix_tree_tag_clear(struct radix_tree_root
*root
,
495 unsigned long index
, unsigned int tag
)
498 * The radix tree path needs to be one longer than the maximum path
499 * since the "list" is null terminated.
501 struct radix_tree_path path
[RADIX_TREE_MAX_PATH
+ 1], *pathp
= path
;
502 struct radix_tree_node
*slot
= NULL
;
503 unsigned int height
, shift
;
505 height
= root
->height
;
506 if (index
> radix_tree_maxindex(height
))
509 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
511 slot
= radix_tree_indirect_to_ptr(root
->rnode
);
519 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
520 pathp
[1].offset
= offset
;
521 pathp
[1].node
= slot
;
522 slot
= slot
->slots
[offset
];
524 shift
-= RADIX_TREE_MAP_SHIFT
;
531 while (pathp
->node
) {
532 if (!tag_get(pathp
->node
, tag
, pathp
->offset
))
534 tag_clear(pathp
->node
, tag
, pathp
->offset
);
535 if (any_tag_set(pathp
->node
, tag
))
540 /* clear the root's tag bit */
541 if (root_tag_get(root
, tag
))
542 root_tag_clear(root
, tag
);
547 EXPORT_SYMBOL(radix_tree_tag_clear
);
549 #ifndef __KERNEL__ /* Only the test harness uses this at present */
551 * radix_tree_tag_get - get a tag on a radix tree node
552 * @root: radix tree root
554 * @tag: tag index (< RADIX_TREE_MAX_TAGS)
558 * 0: tag not present or not set
561 int radix_tree_tag_get(struct radix_tree_root
*root
,
562 unsigned long index
, unsigned int tag
)
564 unsigned int height
, shift
;
565 struct radix_tree_node
*node
;
566 int saw_unset_tag
= 0;
568 /* check the root's tag bit */
569 if (!root_tag_get(root
, tag
))
572 node
= rcu_dereference(root
->rnode
);
576 if (!radix_tree_is_indirect_ptr(node
))
578 node
= radix_tree_indirect_to_ptr(node
);
580 height
= node
->height
;
581 if (index
> radix_tree_maxindex(height
))
584 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
592 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
595 * This is just a debug check. Later, we can bale as soon as
596 * we see an unset tag.
598 if (!tag_get(node
, tag
, offset
))
601 int ret
= tag_get(node
, tag
, offset
);
603 BUG_ON(ret
&& saw_unset_tag
);
606 node
= rcu_dereference(node
->slots
[offset
]);
607 shift
-= RADIX_TREE_MAP_SHIFT
;
611 EXPORT_SYMBOL(radix_tree_tag_get
);
615 * radix_tree_next_hole - find the next hole (not-present entry)
618 * @max_scan: maximum range to search
620 * Search the set [index, min(index+max_scan-1, MAX_INDEX)] for the lowest
623 * Returns: the index of the hole if found, otherwise returns an index
624 * outside of the set specified (in which case 'return - index >= max_scan'
625 * will be true). In rare cases of index wrap-around, 0 will be returned.
627 * radix_tree_next_hole may be called under rcu_read_lock. However, like
628 * radix_tree_gang_lookup, this will not atomically search a snapshot of
629 * the tree at a single point in time. For example, if a hole is created
630 * at index 5, then subsequently a hole is created at index 10,
631 * radix_tree_next_hole covering both indexes may return 10 if called
632 * under rcu_read_lock.
634 unsigned long radix_tree_next_hole(struct radix_tree_root
*root
,
635 unsigned long index
, unsigned long max_scan
)
639 for (i
= 0; i
< max_scan
; i
++) {
640 if (!radix_tree_lookup(root
, index
))
649 EXPORT_SYMBOL(radix_tree_next_hole
);
652 * radix_tree_prev_hole - find the prev hole (not-present entry)
655 * @max_scan: maximum range to search
657 * Search backwards in the range [max(index-max_scan+1, 0), index]
658 * for the first hole.
660 * Returns: the index of the hole if found, otherwise returns an index
661 * outside of the set specified (in which case 'index - return >= max_scan'
662 * will be true). In rare cases of wrap-around, LONG_MAX will be returned.
664 * radix_tree_next_hole may be called under rcu_read_lock. However, like
665 * radix_tree_gang_lookup, this will not atomically search a snapshot of
666 * the tree at a single point in time. For example, if a hole is created
667 * at index 10, then subsequently a hole is created at index 5,
668 * radix_tree_prev_hole covering both indexes may return 5 if called under
671 unsigned long radix_tree_prev_hole(struct radix_tree_root
*root
,
672 unsigned long index
, unsigned long max_scan
)
676 for (i
= 0; i
< max_scan
; i
++) {
677 if (!radix_tree_lookup(root
, index
))
680 if (index
== LONG_MAX
)
686 EXPORT_SYMBOL(radix_tree_prev_hole
);
689 __lookup(struct radix_tree_node
*slot
, void ***results
, unsigned long index
,
690 unsigned int max_items
, unsigned long *next_index
)
692 unsigned int nr_found
= 0;
693 unsigned int shift
, height
;
696 height
= slot
->height
;
699 shift
= (height
-1) * RADIX_TREE_MAP_SHIFT
;
701 for ( ; height
> 1; height
--) {
702 i
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
704 if (slot
->slots
[i
] != NULL
)
706 index
&= ~((1UL << shift
) - 1);
707 index
+= 1UL << shift
;
709 goto out
; /* 32-bit wraparound */
711 if (i
== RADIX_TREE_MAP_SIZE
)
715 shift
-= RADIX_TREE_MAP_SHIFT
;
716 slot
= rcu_dereference(slot
->slots
[i
]);
721 /* Bottom level: grab some items */
722 for (i
= index
& RADIX_TREE_MAP_MASK
; i
< RADIX_TREE_MAP_SIZE
; i
++) {
724 if (slot
->slots
[i
]) {
725 results
[nr_found
++] = &(slot
->slots
[i
]);
726 if (nr_found
== max_items
)
736 * radix_tree_gang_lookup - perform multiple lookup on a radix tree
737 * @root: radix tree root
738 * @results: where the results of the lookup are placed
739 * @first_index: start the lookup from this key
740 * @max_items: place up to this many items at *results
742 * Performs an index-ascending scan of the tree for present items. Places
743 * them at *@results and returns the number of items which were placed at
746 * The implementation is naive.
748 * Like radix_tree_lookup, radix_tree_gang_lookup may be called under
749 * rcu_read_lock. In this case, rather than the returned results being
750 * an atomic snapshot of the tree at a single point in time, the semantics
751 * of an RCU protected gang lookup are as though multiple radix_tree_lookups
752 * have been issued in individual locks, and results stored in 'results'.
755 radix_tree_gang_lookup(struct radix_tree_root
*root
, void **results
,
756 unsigned long first_index
, unsigned int max_items
)
758 unsigned long max_index
;
759 struct radix_tree_node
*node
;
760 unsigned long cur_index
= first_index
;
763 node
= rcu_dereference(root
->rnode
);
767 if (!radix_tree_is_indirect_ptr(node
)) {
773 node
= radix_tree_indirect_to_ptr(node
);
775 max_index
= radix_tree_maxindex(node
->height
);
778 while (ret
< max_items
) {
779 unsigned int nr_found
, slots_found
, i
;
780 unsigned long next_index
; /* Index of next search */
782 if (cur_index
> max_index
)
784 slots_found
= __lookup(node
, (void ***)results
+ ret
, cur_index
,
785 max_items
- ret
, &next_index
);
787 for (i
= 0; i
< slots_found
; i
++) {
788 struct radix_tree_node
*slot
;
789 slot
= *(((void ***)results
)[ret
+ i
]);
792 results
[ret
+ nr_found
] = rcu_dereference(slot
);
798 cur_index
= next_index
;
803 EXPORT_SYMBOL(radix_tree_gang_lookup
);
806 * radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree
807 * @root: radix tree root
808 * @results: where the results of the lookup are placed
809 * @first_index: start the lookup from this key
810 * @max_items: place up to this many items at *results
812 * Performs an index-ascending scan of the tree for present items. Places
813 * their slots at *@results and returns the number of items which were
814 * placed at *@results.
816 * The implementation is naive.
818 * Like radix_tree_gang_lookup as far as RCU and locking goes. Slots must
819 * be dereferenced with radix_tree_deref_slot, and if using only RCU
820 * protection, radix_tree_deref_slot may fail requiring a retry.
823 radix_tree_gang_lookup_slot(struct radix_tree_root
*root
, void ***results
,
824 unsigned long first_index
, unsigned int max_items
)
826 unsigned long max_index
;
827 struct radix_tree_node
*node
;
828 unsigned long cur_index
= first_index
;
831 node
= rcu_dereference(root
->rnode
);
835 if (!radix_tree_is_indirect_ptr(node
)) {
838 results
[0] = (void **)&root
->rnode
;
841 node
= radix_tree_indirect_to_ptr(node
);
843 max_index
= radix_tree_maxindex(node
->height
);
846 while (ret
< max_items
) {
847 unsigned int slots_found
;
848 unsigned long next_index
; /* Index of next search */
850 if (cur_index
> max_index
)
852 slots_found
= __lookup(node
, results
+ ret
, cur_index
,
853 max_items
- ret
, &next_index
);
857 cur_index
= next_index
;
862 EXPORT_SYMBOL(radix_tree_gang_lookup_slot
);
865 * FIXME: the two tag_get()s here should use find_next_bit() instead of
866 * open-coding the search.
869 __lookup_tag(struct radix_tree_node
*slot
, void ***results
, unsigned long index
,
870 unsigned int max_items
, unsigned long *next_index
, unsigned int tag
)
872 unsigned int nr_found
= 0;
873 unsigned int shift
, height
;
875 height
= slot
->height
;
878 shift
= (height
-1) * RADIX_TREE_MAP_SHIFT
;
881 unsigned long i
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
884 if (tag_get(slot
, tag
, i
))
886 index
&= ~((1UL << shift
) - 1);
887 index
+= 1UL << shift
;
889 goto out
; /* 32-bit wraparound */
891 if (i
== RADIX_TREE_MAP_SIZE
)
895 if (height
== 0) { /* Bottom level: grab some items */
896 unsigned long j
= index
& RADIX_TREE_MAP_MASK
;
898 for ( ; j
< RADIX_TREE_MAP_SIZE
; j
++) {
900 if (!tag_get(slot
, tag
, j
))
903 * Even though the tag was found set, we need to
904 * recheck that we have a non-NULL node, because
905 * if this lookup is lockless, it may have been
906 * subsequently deleted.
908 * Similar care must be taken in any place that
909 * lookup ->slots[x] without a lock (ie. can't
910 * rely on its value remaining the same).
912 if (slot
->slots
[j
]) {
913 results
[nr_found
++] = &(slot
->slots
[j
]);
914 if (nr_found
== max_items
)
919 shift
-= RADIX_TREE_MAP_SHIFT
;
920 slot
= rcu_dereference(slot
->slots
[i
]);
930 * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
932 * @root: radix tree root
933 * @results: where the results of the lookup are placed
934 * @first_index: start the lookup from this key
935 * @max_items: place up to this many items at *results
936 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
938 * Performs an index-ascending scan of the tree for present items which
939 * have the tag indexed by @tag set. Places the items at *@results and
940 * returns the number of items which were placed at *@results.
943 radix_tree_gang_lookup_tag(struct radix_tree_root
*root
, void **results
,
944 unsigned long first_index
, unsigned int max_items
,
947 struct radix_tree_node
*node
;
948 unsigned long max_index
;
949 unsigned long cur_index
= first_index
;
952 /* check the root's tag bit */
953 if (!root_tag_get(root
, tag
))
956 node
= rcu_dereference(root
->rnode
);
960 if (!radix_tree_is_indirect_ptr(node
)) {
966 node
= radix_tree_indirect_to_ptr(node
);
968 max_index
= radix_tree_maxindex(node
->height
);
971 while (ret
< max_items
) {
972 unsigned int nr_found
, slots_found
, i
;
973 unsigned long next_index
; /* Index of next search */
975 if (cur_index
> max_index
)
977 slots_found
= __lookup_tag(node
, (void ***)results
+ ret
,
978 cur_index
, max_items
- ret
, &next_index
, tag
);
980 for (i
= 0; i
< slots_found
; i
++) {
981 struct radix_tree_node
*slot
;
982 slot
= *(((void ***)results
)[ret
+ i
]);
985 results
[ret
+ nr_found
] = rcu_dereference(slot
);
991 cur_index
= next_index
;
996 EXPORT_SYMBOL(radix_tree_gang_lookup_tag
);
999 * radix_tree_gang_lookup_tag_slot - perform multiple slot lookup on a
1000 * radix tree based on a tag
1001 * @root: radix tree root
1002 * @results: where the results of the lookup are placed
1003 * @first_index: start the lookup from this key
1004 * @max_items: place up to this many items at *results
1005 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
1007 * Performs an index-ascending scan of the tree for present items which
1008 * have the tag indexed by @tag set. Places the slots at *@results and
1009 * returns the number of slots which were placed at *@results.
1012 radix_tree_gang_lookup_tag_slot(struct radix_tree_root
*root
, void ***results
,
1013 unsigned long first_index
, unsigned int max_items
,
1016 struct radix_tree_node
*node
;
1017 unsigned long max_index
;
1018 unsigned long cur_index
= first_index
;
1021 /* check the root's tag bit */
1022 if (!root_tag_get(root
, tag
))
1025 node
= rcu_dereference(root
->rnode
);
1029 if (!radix_tree_is_indirect_ptr(node
)) {
1030 if (first_index
> 0)
1032 results
[0] = (void **)&root
->rnode
;
1035 node
= radix_tree_indirect_to_ptr(node
);
1037 max_index
= radix_tree_maxindex(node
->height
);
1040 while (ret
< max_items
) {
1041 unsigned int slots_found
;
1042 unsigned long next_index
; /* Index of next search */
1044 if (cur_index
> max_index
)
1046 slots_found
= __lookup_tag(node
, results
+ ret
,
1047 cur_index
, max_items
- ret
, &next_index
, tag
);
1049 if (next_index
== 0)
1051 cur_index
= next_index
;
1056 EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot
);
1060 * radix_tree_shrink - shrink height of a radix tree to minimal
1061 * @root radix tree root
1063 static inline void radix_tree_shrink(struct radix_tree_root
*root
)
1065 /* try to shrink tree height */
1066 while (root
->height
> 0) {
1067 struct radix_tree_node
*to_free
= root
->rnode
;
1070 BUG_ON(!radix_tree_is_indirect_ptr(to_free
));
1071 to_free
= radix_tree_indirect_to_ptr(to_free
);
1074 * The candidate node has more than one child, or its child
1075 * is not at the leftmost slot, we cannot shrink.
1077 if (to_free
->count
!= 1)
1079 if (!to_free
->slots
[0])
1083 * We don't need rcu_assign_pointer(), since we are simply
1084 * moving the node from one part of the tree to another. If
1085 * it was safe to dereference the old pointer to it
1086 * (to_free->slots[0]), it will be safe to dereference the new
1087 * one (root->rnode).
1089 newptr
= to_free
->slots
[0];
1090 if (root
->height
> 1)
1091 newptr
= radix_tree_ptr_to_indirect(newptr
);
1092 root
->rnode
= newptr
;
1094 radix_tree_node_free(to_free
);
1099 * radix_tree_delete - delete an item from a radix tree
1100 * @root: radix tree root
1103 * Remove the item at @index from the radix tree rooted at @root.
1105 * Returns the address of the deleted item, or NULL if it was not present.
1107 void *radix_tree_delete(struct radix_tree_root
*root
, unsigned long index
)
1110 * The radix tree path needs to be one longer than the maximum path
1111 * since the "list" is null terminated.
1113 struct radix_tree_path path
[RADIX_TREE_MAX_PATH
+ 1], *pathp
= path
;
1114 struct radix_tree_node
*slot
= NULL
;
1115 struct radix_tree_node
*to_free
;
1116 unsigned int height
, shift
;
1120 height
= root
->height
;
1121 if (index
> radix_tree_maxindex(height
))
1126 root_tag_clear_all(root
);
1130 slot
= radix_tree_indirect_to_ptr(slot
);
1132 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
1140 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
1141 pathp
->offset
= offset
;
1143 slot
= slot
->slots
[offset
];
1144 shift
-= RADIX_TREE_MAP_SHIFT
;
1146 } while (height
> 0);
1152 * Clear all tags associated with the just-deleted item
1154 for (tag
= 0; tag
< RADIX_TREE_MAX_TAGS
; tag
++) {
1155 if (tag_get(pathp
->node
, tag
, pathp
->offset
))
1156 radix_tree_tag_clear(root
, index
, tag
);
1160 /* Now free the nodes we do not need anymore */
1161 while (pathp
->node
) {
1162 pathp
->node
->slots
[pathp
->offset
] = NULL
;
1163 pathp
->node
->count
--;
1165 * Queue the node for deferred freeing after the
1166 * last reference to it disappears (set NULL, above).
1169 radix_tree_node_free(to_free
);
1171 if (pathp
->node
->count
) {
1173 radix_tree_indirect_to_ptr(root
->rnode
))
1174 radix_tree_shrink(root
);
1178 /* Node with zero slots in use so free it */
1179 to_free
= pathp
->node
;
1183 root_tag_clear_all(root
);
1187 radix_tree_node_free(to_free
);
1192 EXPORT_SYMBOL(radix_tree_delete
);
1195 * radix_tree_tagged - test whether any items in the tree are tagged
1196 * @root: radix tree root
1199 int radix_tree_tagged(struct radix_tree_root
*root
, unsigned int tag
)
1201 return root_tag_get(root
, tag
);
1203 EXPORT_SYMBOL(radix_tree_tagged
);
1206 radix_tree_node_ctor(void *node
)
1208 memset(node
, 0, sizeof(struct radix_tree_node
));
1211 static __init
unsigned long __maxindex(unsigned int height
)
1213 unsigned int width
= height
* RADIX_TREE_MAP_SHIFT
;
1214 int shift
= RADIX_TREE_INDEX_BITS
- width
;
1218 if (shift
>= BITS_PER_LONG
)
1220 return ~0UL >> shift
;
1223 static __init
void radix_tree_init_maxindex(void)
1227 for (i
= 0; i
< ARRAY_SIZE(height_to_maxindex
); i
++)
1228 height_to_maxindex
[i
] = __maxindex(i
);
1231 static int radix_tree_callback(struct notifier_block
*nfb
,
1232 unsigned long action
,
1235 int cpu
= (long)hcpu
;
1236 struct radix_tree_preload
*rtp
;
1238 /* Free per-cpu pool of perloaded nodes */
1239 if (action
== CPU_DEAD
|| action
== CPU_DEAD_FROZEN
) {
1240 rtp
= &per_cpu(radix_tree_preloads
, cpu
);
1242 kmem_cache_free(radix_tree_node_cachep
,
1243 rtp
->nodes
[rtp
->nr
-1]);
1244 rtp
->nodes
[rtp
->nr
-1] = NULL
;
1251 void __init
radix_tree_init(void)
1253 radix_tree_node_cachep
= kmem_cache_create("radix_tree_node",
1254 sizeof(struct radix_tree_node
), 0,
1255 SLAB_PANIC
| SLAB_RECLAIM_ACCOUNT
,
1256 radix_tree_node_ctor
);
1257 radix_tree_init_maxindex();
1258 hotcpu_notifier(radix_tree_callback
, 0);