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
);
161 rtp
= &__get_cpu_var(radix_tree_preloads
);
163 ret
= rtp
->nodes
[rtp
->nr
- 1];
164 rtp
->nodes
[rtp
->nr
- 1] = NULL
;
167 put_cpu_var(radix_tree_preloads
);
170 ret
= kmem_cache_alloc(radix_tree_node_cachep
, gfp_mask
);
172 BUG_ON(radix_tree_is_indirect_ptr(ret
));
176 static void radix_tree_node_rcu_free(struct rcu_head
*head
)
178 struct radix_tree_node
*node
=
179 container_of(head
, struct radix_tree_node
, rcu_head
);
182 * must only free zeroed nodes into the slab. radix_tree_shrink
183 * can leave us with a non-NULL entry in the first slot, so clear
184 * that here to make sure.
186 tag_clear(node
, 0, 0);
187 tag_clear(node
, 1, 0);
188 node
->slots
[0] = NULL
;
191 kmem_cache_free(radix_tree_node_cachep
, node
);
195 radix_tree_node_free(struct radix_tree_node
*node
)
197 call_rcu(&node
->rcu_head
, radix_tree_node_rcu_free
);
200 #ifndef CONFIG_PREEMPT_RT
203 * Load up this CPU's radix_tree_node buffer with sufficient objects to
204 * ensure that the addition of a single element in the tree cannot fail. On
205 * success, return zero, with preemption disabled. On error, return -ENOMEM
206 * with preemption not disabled.
208 int radix_tree_preload(gfp_t gfp_mask
)
210 struct radix_tree_preload
*rtp
;
211 struct radix_tree_node
*node
;
215 rtp
= &__get_cpu_var(radix_tree_preloads
);
216 while (rtp
->nr
< ARRAY_SIZE(rtp
->nodes
)) {
218 node
= kmem_cache_alloc(radix_tree_node_cachep
, gfp_mask
);
222 rtp
= &__get_cpu_var(radix_tree_preloads
);
223 if (rtp
->nr
< ARRAY_SIZE(rtp
->nodes
))
224 rtp
->nodes
[rtp
->nr
++] = node
;
226 kmem_cache_free(radix_tree_node_cachep
, node
);
232 EXPORT_SYMBOL(radix_tree_preload
);
237 * Return the maximum key which can be store into a
238 * radix tree with height HEIGHT.
240 static inline unsigned long radix_tree_maxindex(unsigned int height
)
242 return height_to_maxindex
[height
];
246 * Extend a radix tree so it can store key @index.
248 static int radix_tree_extend(struct radix_tree_root
*root
, unsigned long index
)
250 struct radix_tree_node
*node
;
254 /* Figure out what the height should be. */
255 height
= root
->height
+ 1;
256 while (index
> radix_tree_maxindex(height
))
259 if (root
->rnode
== NULL
) {
260 root
->height
= height
;
265 unsigned int newheight
;
266 if (!(node
= radix_tree_node_alloc(root
)))
269 /* Increase the height. */
270 node
->slots
[0] = radix_tree_indirect_to_ptr(root
->rnode
);
272 /* Propagate the aggregated tag info into the new root */
273 for (tag
= 0; tag
< RADIX_TREE_MAX_TAGS
; tag
++) {
274 if (root_tag_get(root
, tag
))
275 tag_set(node
, tag
, 0);
278 newheight
= root
->height
+1;
279 node
->height
= newheight
;
281 node
= radix_tree_ptr_to_indirect(node
);
282 rcu_assign_pointer(root
->rnode
, node
);
283 root
->height
= newheight
;
284 } while (height
> root
->height
);
290 * radix_tree_insert - insert into a radix tree
291 * @root: radix tree root
293 * @item: item to insert
295 * Insert an item into the radix tree at position @index.
297 int radix_tree_insert(struct radix_tree_root
*root
,
298 unsigned long index
, void *item
)
300 struct radix_tree_node
*node
= NULL
, *slot
;
301 unsigned int height
, shift
;
305 BUG_ON(radix_tree_is_indirect_ptr(item
));
307 /* Make sure the tree is high enough. */
308 if (index
> radix_tree_maxindex(root
->height
)) {
309 error
= radix_tree_extend(root
, index
);
314 slot
= radix_tree_indirect_to_ptr(root
->rnode
);
316 height
= root
->height
;
317 shift
= (height
-1) * RADIX_TREE_MAP_SHIFT
;
319 offset
= 0; /* uninitialised var warning */
322 /* Have to add a child node. */
323 if (!(slot
= radix_tree_node_alloc(root
)))
325 slot
->height
= height
;
327 rcu_assign_pointer(node
->slots
[offset
], slot
);
330 rcu_assign_pointer(root
->rnode
,
331 radix_tree_ptr_to_indirect(slot
));
334 /* Go a level down */
335 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
337 slot
= node
->slots
[offset
];
338 shift
-= RADIX_TREE_MAP_SHIFT
;
347 rcu_assign_pointer(node
->slots
[offset
], item
);
348 BUG_ON(tag_get(node
, 0, offset
));
349 BUG_ON(tag_get(node
, 1, offset
));
351 rcu_assign_pointer(root
->rnode
, item
);
352 BUG_ON(root_tag_get(root
, 0));
353 BUG_ON(root_tag_get(root
, 1));
358 EXPORT_SYMBOL(radix_tree_insert
);
361 * radix_tree_lookup_slot - lookup a slot in a radix tree
362 * @root: radix tree root
365 * Returns: the slot corresponding to the position @index in the
366 * radix tree @root. This is useful for update-if-exists operations.
368 * This function can be called under rcu_read_lock iff the slot is not
369 * modified by radix_tree_replace_slot, otherwise it must be called
370 * exclusive from other writers. Any dereference of the slot must be done
371 * using radix_tree_deref_slot.
373 void **radix_tree_lookup_slot(struct radix_tree_root
*root
, unsigned long index
)
375 unsigned int height
, shift
;
376 struct radix_tree_node
*node
, **slot
;
378 node
= rcu_dereference(root
->rnode
);
382 if (!radix_tree_is_indirect_ptr(node
)) {
385 return (void **)&root
->rnode
;
387 node
= radix_tree_indirect_to_ptr(node
);
389 height
= node
->height
;
390 if (index
> radix_tree_maxindex(height
))
393 shift
= (height
-1) * RADIX_TREE_MAP_SHIFT
;
396 slot
= (struct radix_tree_node
**)
397 (node
->slots
+ ((index
>>shift
) & RADIX_TREE_MAP_MASK
));
398 node
= rcu_dereference(*slot
);
402 shift
-= RADIX_TREE_MAP_SHIFT
;
404 } while (height
> 0);
406 return (void **)slot
;
408 EXPORT_SYMBOL(radix_tree_lookup_slot
);
411 * radix_tree_lookup - perform lookup operation on a radix tree
412 * @root: radix tree root
415 * Lookup the item at the position @index in the radix tree @root.
417 * This function can be called under rcu_read_lock, however the caller
418 * must manage lifetimes of leaf nodes (eg. RCU may also be used to free
419 * them safely). No RCU barriers are required to access or modify the
420 * returned item, however.
422 void *radix_tree_lookup(struct radix_tree_root
*root
, unsigned long index
)
424 unsigned int height
, shift
;
425 struct radix_tree_node
*node
, **slot
;
427 node
= rcu_dereference(root
->rnode
);
431 if (!radix_tree_is_indirect_ptr(node
)) {
436 node
= radix_tree_indirect_to_ptr(node
);
438 height
= node
->height
;
439 if (index
> radix_tree_maxindex(height
))
442 shift
= (height
-1) * RADIX_TREE_MAP_SHIFT
;
445 slot
= (struct radix_tree_node
**)
446 (node
->slots
+ ((index
>>shift
) & RADIX_TREE_MAP_MASK
));
447 node
= rcu_dereference(*slot
);
451 shift
-= RADIX_TREE_MAP_SHIFT
;
453 } while (height
> 0);
457 EXPORT_SYMBOL(radix_tree_lookup
);
460 * radix_tree_tag_set - set a tag on a radix tree node
461 * @root: radix tree root
465 * Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
466 * corresponding to @index in the radix tree. From
467 * the root all the way down to the leaf node.
469 * Returns the address of the tagged item. Setting a tag on a not-present
472 void *radix_tree_tag_set(struct radix_tree_root
*root
,
473 unsigned long index
, unsigned int tag
)
475 unsigned int height
, shift
;
476 struct radix_tree_node
*slot
;
478 height
= root
->height
;
479 BUG_ON(index
> radix_tree_maxindex(height
));
481 slot
= radix_tree_indirect_to_ptr(root
->rnode
);
482 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
487 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
488 if (!tag_get(slot
, tag
, offset
))
489 tag_set(slot
, tag
, offset
);
490 slot
= slot
->slots
[offset
];
491 BUG_ON(slot
== NULL
);
492 shift
-= RADIX_TREE_MAP_SHIFT
;
496 /* set the root's tag bit */
497 if (slot
&& !root_tag_get(root
, tag
))
498 root_tag_set(root
, tag
);
502 EXPORT_SYMBOL(radix_tree_tag_set
);
505 * radix_tree_tag_clear - clear a tag on a radix tree node
506 * @root: radix tree root
510 * Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
511 * corresponding to @index in the radix tree. If
512 * this causes the leaf node to have no tags set then clear the tag in the
513 * next-to-leaf node, etc.
515 * Returns the address of the tagged item on success, else NULL. ie:
516 * has the same return value and semantics as radix_tree_lookup().
518 void *radix_tree_tag_clear(struct radix_tree_root
*root
,
519 unsigned long index
, unsigned int tag
)
522 * The radix tree path needs to be one longer than the maximum path
523 * since the "list" is null terminated.
525 struct radix_tree_path path
[RADIX_TREE_MAX_PATH
+ 1], *pathp
= path
;
526 struct radix_tree_node
*slot
= NULL
;
527 unsigned int height
, shift
;
529 height
= root
->height
;
530 if (index
> radix_tree_maxindex(height
))
533 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
535 slot
= radix_tree_indirect_to_ptr(root
->rnode
);
543 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
544 pathp
[1].offset
= offset
;
545 pathp
[1].node
= slot
;
546 slot
= slot
->slots
[offset
];
548 shift
-= RADIX_TREE_MAP_SHIFT
;
555 while (pathp
->node
) {
556 if (!tag_get(pathp
->node
, tag
, pathp
->offset
))
558 tag_clear(pathp
->node
, tag
, pathp
->offset
);
559 if (any_tag_set(pathp
->node
, tag
))
564 /* clear the root's tag bit */
565 if (root_tag_get(root
, tag
))
566 root_tag_clear(root
, tag
);
571 EXPORT_SYMBOL(radix_tree_tag_clear
);
573 #ifndef __KERNEL__ /* Only the test harness uses this at present */
575 * radix_tree_tag_get - get a tag on a radix tree node
576 * @root: radix tree root
578 * @tag: tag index (< RADIX_TREE_MAX_TAGS)
582 * 0: tag not present or not set
585 int radix_tree_tag_get(struct radix_tree_root
*root
,
586 unsigned long index
, unsigned int tag
)
588 unsigned int height
, shift
;
589 struct radix_tree_node
*node
;
590 int saw_unset_tag
= 0;
592 /* check the root's tag bit */
593 if (!root_tag_get(root
, tag
))
596 node
= rcu_dereference(root
->rnode
);
600 if (!radix_tree_is_indirect_ptr(node
))
602 node
= radix_tree_indirect_to_ptr(node
);
604 height
= node
->height
;
605 if (index
> radix_tree_maxindex(height
))
608 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
616 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
619 * This is just a debug check. Later, we can bale as soon as
620 * we see an unset tag.
622 if (!tag_get(node
, tag
, offset
))
625 int ret
= tag_get(node
, tag
, offset
);
627 BUG_ON(ret
&& saw_unset_tag
);
630 node
= rcu_dereference(node
->slots
[offset
]);
631 shift
-= RADIX_TREE_MAP_SHIFT
;
635 EXPORT_SYMBOL(radix_tree_tag_get
);
639 * radix_tree_next_hole - find the next hole (not-present entry)
642 * @max_scan: maximum range to search
644 * Search the set [index, min(index+max_scan-1, MAX_INDEX)] for the lowest
647 * Returns: the index of the hole if found, otherwise returns an index
648 * outside of the set specified (in which case 'return - index >= max_scan'
649 * will be true). In rare cases of index wrap-around, 0 will be returned.
651 * radix_tree_next_hole may be called under rcu_read_lock. However, like
652 * radix_tree_gang_lookup, this will not atomically search a snapshot of
653 * the tree at a single point in time. For example, if a hole is created
654 * at index 5, then subsequently a hole is created at index 10,
655 * radix_tree_next_hole covering both indexes may return 10 if called
656 * under rcu_read_lock.
658 unsigned long radix_tree_next_hole(struct radix_tree_root
*root
,
659 unsigned long index
, unsigned long max_scan
)
663 for (i
= 0; i
< max_scan
; i
++) {
664 if (!radix_tree_lookup(root
, index
))
673 EXPORT_SYMBOL(radix_tree_next_hole
);
676 __lookup(struct radix_tree_node
*slot
, void ***results
, unsigned long index
,
677 unsigned int max_items
, unsigned long *next_index
)
679 unsigned int nr_found
= 0;
680 unsigned int shift
, height
;
683 height
= slot
->height
;
686 shift
= (height
-1) * RADIX_TREE_MAP_SHIFT
;
688 for ( ; height
> 1; height
--) {
689 i
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
691 if (slot
->slots
[i
] != NULL
)
693 index
&= ~((1UL << shift
) - 1);
694 index
+= 1UL << shift
;
696 goto out
; /* 32-bit wraparound */
698 if (i
== RADIX_TREE_MAP_SIZE
)
702 shift
-= RADIX_TREE_MAP_SHIFT
;
703 slot
= rcu_dereference(slot
->slots
[i
]);
708 /* Bottom level: grab some items */
709 for (i
= index
& RADIX_TREE_MAP_MASK
; i
< RADIX_TREE_MAP_SIZE
; i
++) {
711 if (slot
->slots
[i
]) {
712 results
[nr_found
++] = &(slot
->slots
[i
]);
713 if (nr_found
== max_items
)
723 * radix_tree_gang_lookup - perform multiple lookup on a radix tree
724 * @root: radix tree root
725 * @results: where the results of the lookup are placed
726 * @first_index: start the lookup from this key
727 * @max_items: place up to this many items at *results
729 * Performs an index-ascending scan of the tree for present items. Places
730 * them at *@results and returns the number of items which were placed at
733 * The implementation is naive.
735 * Like radix_tree_lookup, radix_tree_gang_lookup may be called under
736 * rcu_read_lock. In this case, rather than the returned results being
737 * an atomic snapshot of the tree at a single point in time, the semantics
738 * of an RCU protected gang lookup are as though multiple radix_tree_lookups
739 * have been issued in individual locks, and results stored in 'results'.
742 radix_tree_gang_lookup(struct radix_tree_root
*root
, void **results
,
743 unsigned long first_index
, unsigned int max_items
)
745 unsigned long max_index
;
746 struct radix_tree_node
*node
;
747 unsigned long cur_index
= first_index
;
750 node
= rcu_dereference(root
->rnode
);
754 if (!radix_tree_is_indirect_ptr(node
)) {
760 node
= radix_tree_indirect_to_ptr(node
);
762 max_index
= radix_tree_maxindex(node
->height
);
765 while (ret
< max_items
) {
766 unsigned int nr_found
, slots_found
, i
;
767 unsigned long next_index
; /* Index of next search */
769 if (cur_index
> max_index
)
771 slots_found
= __lookup(node
, (void ***)results
+ ret
, cur_index
,
772 max_items
- ret
, &next_index
);
774 for (i
= 0; i
< slots_found
; i
++) {
775 struct radix_tree_node
*slot
;
776 slot
= *(((void ***)results
)[ret
+ i
]);
779 results
[ret
+ nr_found
] = rcu_dereference(slot
);
785 cur_index
= next_index
;
790 EXPORT_SYMBOL(radix_tree_gang_lookup
);
793 * radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree
794 * @root: radix tree root
795 * @results: where the results of the lookup are placed
796 * @first_index: start the lookup from this key
797 * @max_items: place up to this many items at *results
799 * Performs an index-ascending scan of the tree for present items. Places
800 * their slots at *@results and returns the number of items which were
801 * placed at *@results.
803 * The implementation is naive.
805 * Like radix_tree_gang_lookup as far as RCU and locking goes. Slots must
806 * be dereferenced with radix_tree_deref_slot, and if using only RCU
807 * protection, radix_tree_deref_slot may fail requiring a retry.
810 radix_tree_gang_lookup_slot(struct radix_tree_root
*root
, void ***results
,
811 unsigned long first_index
, unsigned int max_items
)
813 unsigned long max_index
;
814 struct radix_tree_node
*node
;
815 unsigned long cur_index
= first_index
;
818 node
= rcu_dereference(root
->rnode
);
822 if (!radix_tree_is_indirect_ptr(node
)) {
825 results
[0] = (void **)&root
->rnode
;
828 node
= radix_tree_indirect_to_ptr(node
);
830 max_index
= radix_tree_maxindex(node
->height
);
833 while (ret
< max_items
) {
834 unsigned int slots_found
;
835 unsigned long next_index
; /* Index of next search */
837 if (cur_index
> max_index
)
839 slots_found
= __lookup(node
, results
+ ret
, cur_index
,
840 max_items
- ret
, &next_index
);
844 cur_index
= next_index
;
849 EXPORT_SYMBOL(radix_tree_gang_lookup_slot
);
852 * FIXME: the two tag_get()s here should use find_next_bit() instead of
853 * open-coding the search.
856 __lookup_tag(struct radix_tree_node
*slot
, void ***results
, unsigned long index
,
857 unsigned int max_items
, unsigned long *next_index
, unsigned int tag
)
859 unsigned int nr_found
= 0;
860 unsigned int shift
, height
;
862 height
= slot
->height
;
865 shift
= (height
-1) * RADIX_TREE_MAP_SHIFT
;
868 unsigned long i
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
871 if (tag_get(slot
, tag
, i
))
873 index
&= ~((1UL << shift
) - 1);
874 index
+= 1UL << shift
;
876 goto out
; /* 32-bit wraparound */
878 if (i
== RADIX_TREE_MAP_SIZE
)
882 if (height
== 0) { /* Bottom level: grab some items */
883 unsigned long j
= index
& RADIX_TREE_MAP_MASK
;
885 for ( ; j
< RADIX_TREE_MAP_SIZE
; j
++) {
887 if (!tag_get(slot
, tag
, j
))
890 * Even though the tag was found set, we need to
891 * recheck that we have a non-NULL node, because
892 * if this lookup is lockless, it may have been
893 * subsequently deleted.
895 * Similar care must be taken in any place that
896 * lookup ->slots[x] without a lock (ie. can't
897 * rely on its value remaining the same).
899 if (slot
->slots
[j
]) {
900 results
[nr_found
++] = &(slot
->slots
[j
]);
901 if (nr_found
== max_items
)
906 shift
-= RADIX_TREE_MAP_SHIFT
;
907 slot
= rcu_dereference(slot
->slots
[i
]);
917 * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
919 * @root: radix tree root
920 * @results: where the results of the lookup are placed
921 * @first_index: start the lookup from this key
922 * @max_items: place up to this many items at *results
923 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
925 * Performs an index-ascending scan of the tree for present items which
926 * have the tag indexed by @tag set. Places the items at *@results and
927 * returns the number of items which were placed at *@results.
930 radix_tree_gang_lookup_tag(struct radix_tree_root
*root
, void **results
,
931 unsigned long first_index
, unsigned int max_items
,
934 struct radix_tree_node
*node
;
935 unsigned long max_index
;
936 unsigned long cur_index
= first_index
;
939 /* check the root's tag bit */
940 if (!root_tag_get(root
, tag
))
943 node
= rcu_dereference(root
->rnode
);
947 if (!radix_tree_is_indirect_ptr(node
)) {
953 node
= radix_tree_indirect_to_ptr(node
);
955 max_index
= radix_tree_maxindex(node
->height
);
958 while (ret
< max_items
) {
959 unsigned int nr_found
, slots_found
, i
;
960 unsigned long next_index
; /* Index of next search */
962 if (cur_index
> max_index
)
964 slots_found
= __lookup_tag(node
, (void ***)results
+ ret
,
965 cur_index
, max_items
- ret
, &next_index
, tag
);
967 for (i
= 0; i
< slots_found
; i
++) {
968 struct radix_tree_node
*slot
;
969 slot
= *(((void ***)results
)[ret
+ i
]);
972 results
[ret
+ nr_found
] = rcu_dereference(slot
);
978 cur_index
= next_index
;
983 EXPORT_SYMBOL(radix_tree_gang_lookup_tag
);
986 * radix_tree_gang_lookup_tag_slot - perform multiple slot lookup on a
987 * radix tree based on a tag
988 * @root: radix tree root
989 * @results: where the results of the lookup are placed
990 * @first_index: start the lookup from this key
991 * @max_items: place up to this many items at *results
992 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
994 * Performs an index-ascending scan of the tree for present items which
995 * have the tag indexed by @tag set. Places the slots at *@results and
996 * returns the number of slots which were placed at *@results.
999 radix_tree_gang_lookup_tag_slot(struct radix_tree_root
*root
, void ***results
,
1000 unsigned long first_index
, unsigned int max_items
,
1003 struct radix_tree_node
*node
;
1004 unsigned long max_index
;
1005 unsigned long cur_index
= first_index
;
1008 /* check the root's tag bit */
1009 if (!root_tag_get(root
, tag
))
1012 node
= rcu_dereference(root
->rnode
);
1016 if (!radix_tree_is_indirect_ptr(node
)) {
1017 if (first_index
> 0)
1019 results
[0] = (void **)&root
->rnode
;
1022 node
= radix_tree_indirect_to_ptr(node
);
1024 max_index
= radix_tree_maxindex(node
->height
);
1027 while (ret
< max_items
) {
1028 unsigned int slots_found
;
1029 unsigned long next_index
; /* Index of next search */
1031 if (cur_index
> max_index
)
1033 slots_found
= __lookup_tag(node
, results
+ ret
,
1034 cur_index
, max_items
- ret
, &next_index
, tag
);
1036 if (next_index
== 0)
1038 cur_index
= next_index
;
1043 EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot
);
1047 * radix_tree_shrink - shrink height of a radix tree to minimal
1048 * @root radix tree root
1050 static inline void radix_tree_shrink(struct radix_tree_root
*root
)
1052 /* try to shrink tree height */
1053 while (root
->height
> 0) {
1054 struct radix_tree_node
*to_free
= root
->rnode
;
1057 BUG_ON(!radix_tree_is_indirect_ptr(to_free
));
1058 to_free
= radix_tree_indirect_to_ptr(to_free
);
1061 * The candidate node has more than one child, or its child
1062 * is not at the leftmost slot, we cannot shrink.
1064 if (to_free
->count
!= 1)
1066 if (!to_free
->slots
[0])
1070 * We don't need rcu_assign_pointer(), since we are simply
1071 * moving the node from one part of the tree to another. If
1072 * it was safe to dereference the old pointer to it
1073 * (to_free->slots[0]), it will be safe to dereference the new
1074 * one (root->rnode).
1076 newptr
= to_free
->slots
[0];
1077 if (root
->height
> 1)
1078 newptr
= radix_tree_ptr_to_indirect(newptr
);
1079 root
->rnode
= newptr
;
1081 radix_tree_node_free(to_free
);
1086 * radix_tree_delete - delete an item from a radix tree
1087 * @root: radix tree root
1090 * Remove the item at @index from the radix tree rooted at @root.
1092 * Returns the address of the deleted item, or NULL if it was not present.
1094 void *radix_tree_delete(struct radix_tree_root
*root
, unsigned long index
)
1097 * The radix tree path needs to be one longer than the maximum path
1098 * since the "list" is null terminated.
1100 struct radix_tree_path path
[RADIX_TREE_MAX_PATH
+ 1], *pathp
= path
;
1101 struct radix_tree_node
*slot
= NULL
;
1102 struct radix_tree_node
*to_free
;
1103 unsigned int height
, shift
;
1107 height
= root
->height
;
1108 if (index
> radix_tree_maxindex(height
))
1113 root_tag_clear_all(root
);
1117 slot
= radix_tree_indirect_to_ptr(slot
);
1119 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
1127 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
1128 pathp
->offset
= offset
;
1130 slot
= slot
->slots
[offset
];
1131 shift
-= RADIX_TREE_MAP_SHIFT
;
1133 } while (height
> 0);
1139 * Clear all tags associated with the just-deleted item
1141 for (tag
= 0; tag
< RADIX_TREE_MAX_TAGS
; tag
++) {
1142 if (tag_get(pathp
->node
, tag
, pathp
->offset
))
1143 radix_tree_tag_clear(root
, index
, tag
);
1147 /* Now free the nodes we do not need anymore */
1148 while (pathp
->node
) {
1149 pathp
->node
->slots
[pathp
->offset
] = NULL
;
1150 pathp
->node
->count
--;
1152 * Queue the node for deferred freeing after the
1153 * last reference to it disappears (set NULL, above).
1156 radix_tree_node_free(to_free
);
1158 if (pathp
->node
->count
) {
1160 radix_tree_indirect_to_ptr(root
->rnode
))
1161 radix_tree_shrink(root
);
1165 /* Node with zero slots in use so free it */
1166 to_free
= pathp
->node
;
1170 root_tag_clear_all(root
);
1174 radix_tree_node_free(to_free
);
1179 EXPORT_SYMBOL(radix_tree_delete
);
1182 * radix_tree_tagged - test whether any items in the tree are tagged
1183 * @root: radix tree root
1186 int radix_tree_tagged(struct radix_tree_root
*root
, unsigned int tag
)
1188 return root_tag_get(root
, tag
);
1190 EXPORT_SYMBOL(radix_tree_tagged
);
1193 radix_tree_node_ctor(void *node
)
1195 memset(node
, 0, sizeof(struct radix_tree_node
));
1198 static __init
unsigned long __maxindex(unsigned int height
)
1200 unsigned int width
= height
* RADIX_TREE_MAP_SHIFT
;
1201 int shift
= RADIX_TREE_INDEX_BITS
- width
;
1205 if (shift
>= BITS_PER_LONG
)
1207 return ~0UL >> shift
;
1210 static __init
void radix_tree_init_maxindex(void)
1214 for (i
= 0; i
< ARRAY_SIZE(height_to_maxindex
); i
++)
1215 height_to_maxindex
[i
] = __maxindex(i
);
1218 static int radix_tree_callback(struct notifier_block
*nfb
,
1219 unsigned long action
,
1222 int cpu
= (long)hcpu
;
1223 struct radix_tree_preload
*rtp
;
1225 /* Free per-cpu pool of perloaded nodes */
1226 if (action
== CPU_DEAD
|| action
== CPU_DEAD_FROZEN
) {
1227 rtp
= &per_cpu(radix_tree_preloads
, cpu
);
1229 kmem_cache_free(radix_tree_node_cachep
,
1230 rtp
->nodes
[rtp
->nr
-1]);
1231 rtp
->nodes
[rtp
->nr
-1] = NULL
;
1238 void __init
radix_tree_init(void)
1240 radix_tree_node_cachep
= kmem_cache_create("radix_tree_node",
1241 sizeof(struct radix_tree_node
), 0,
1242 SLAB_PANIC
| SLAB_RECLAIM_ACCOUNT
,
1243 radix_tree_node_ctor
);
1244 radix_tree_init_maxindex();
1245 hotcpu_notifier(radix_tree_callback
, 0);