2 * Copyright (C) 2001 Momchil Velikov
3 * Portions Copyright (C) 2001 Christoph Hellwig
4 * Copyright (C) 2005 SGI, Christoph Lameter <clameter@sgi.com>
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 (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2)
65 static unsigned long height_to_maxindex
[RADIX_TREE_MAX_PATH
] __read_mostly
;
68 * Radix tree node cache.
70 static struct kmem_cache
*radix_tree_node_cachep
;
73 * Per-cpu pool of preloaded nodes
75 struct radix_tree_preload
{
77 struct radix_tree_node
*nodes
[RADIX_TREE_MAX_PATH
];
79 DEFINE_PER_CPU(struct radix_tree_preload
, radix_tree_preloads
) = { 0, };
81 static inline gfp_t
root_gfp_mask(struct radix_tree_root
*root
)
83 return root
->gfp_mask
& __GFP_BITS_MASK
;
87 * This assumes that the caller has performed appropriate preallocation, and
88 * that the caller has pinned this thread of control to the current CPU.
90 static struct radix_tree_node
*
91 radix_tree_node_alloc(struct radix_tree_root
*root
)
93 struct radix_tree_node
*ret
;
94 gfp_t gfp_mask
= root_gfp_mask(root
);
96 ret
= kmem_cache_alloc(radix_tree_node_cachep
, gfp_mask
);
97 if (ret
== NULL
&& !(gfp_mask
& __GFP_WAIT
)) {
98 struct radix_tree_preload
*rtp
;
100 rtp
= &__get_cpu_var(radix_tree_preloads
);
102 ret
= rtp
->nodes
[rtp
->nr
- 1];
103 rtp
->nodes
[rtp
->nr
- 1] = NULL
;
107 BUG_ON(radix_tree_is_indirect_ptr(ret
));
111 static void radix_tree_node_rcu_free(struct rcu_head
*head
)
113 struct radix_tree_node
*node
=
114 container_of(head
, struct radix_tree_node
, rcu_head
);
115 kmem_cache_free(radix_tree_node_cachep
, node
);
119 radix_tree_node_free(struct radix_tree_node
*node
)
121 call_rcu(&node
->rcu_head
, radix_tree_node_rcu_free
);
125 * Load up this CPU's radix_tree_node buffer with sufficient objects to
126 * ensure that the addition of a single element in the tree cannot fail. On
127 * success, return zero, with preemption disabled. On error, return -ENOMEM
128 * with preemption not disabled.
130 int radix_tree_preload(gfp_t gfp_mask
)
132 struct radix_tree_preload
*rtp
;
133 struct radix_tree_node
*node
;
137 rtp
= &__get_cpu_var(radix_tree_preloads
);
138 while (rtp
->nr
< ARRAY_SIZE(rtp
->nodes
)) {
140 node
= kmem_cache_alloc(radix_tree_node_cachep
, gfp_mask
);
144 rtp
= &__get_cpu_var(radix_tree_preloads
);
145 if (rtp
->nr
< ARRAY_SIZE(rtp
->nodes
))
146 rtp
->nodes
[rtp
->nr
++] = node
;
148 kmem_cache_free(radix_tree_node_cachep
, node
);
154 EXPORT_SYMBOL(radix_tree_preload
);
156 static inline void tag_set(struct radix_tree_node
*node
, unsigned int tag
,
159 __set_bit(offset
, node
->tags
[tag
]);
162 static inline void tag_clear(struct radix_tree_node
*node
, unsigned int tag
,
165 __clear_bit(offset
, node
->tags
[tag
]);
168 static inline int tag_get(struct radix_tree_node
*node
, unsigned int tag
,
171 return test_bit(offset
, node
->tags
[tag
]);
174 static inline void root_tag_set(struct radix_tree_root
*root
, unsigned int tag
)
176 root
->gfp_mask
|= (__force gfp_t
)(1 << (tag
+ __GFP_BITS_SHIFT
));
180 static inline void root_tag_clear(struct radix_tree_root
*root
, unsigned int tag
)
182 root
->gfp_mask
&= (__force gfp_t
)~(1 << (tag
+ __GFP_BITS_SHIFT
));
185 static inline void root_tag_clear_all(struct radix_tree_root
*root
)
187 root
->gfp_mask
&= __GFP_BITS_MASK
;
190 static inline int root_tag_get(struct radix_tree_root
*root
, unsigned int tag
)
192 return (__force
unsigned)root
->gfp_mask
& (1 << (tag
+ __GFP_BITS_SHIFT
));
196 * Returns 1 if any slot in the node has this tag set.
197 * Otherwise returns 0.
199 static inline int any_tag_set(struct radix_tree_node
*node
, unsigned int tag
)
202 for (idx
= 0; idx
< RADIX_TREE_TAG_LONGS
; idx
++) {
203 if (node
->tags
[tag
][idx
])
210 * Return the maximum key which can be store into a
211 * radix tree with height HEIGHT.
213 static inline unsigned long radix_tree_maxindex(unsigned int height
)
215 return height_to_maxindex
[height
];
219 * Extend a radix tree so it can store key @index.
221 static int radix_tree_extend(struct radix_tree_root
*root
, unsigned long index
)
223 struct radix_tree_node
*node
;
227 /* Figure out what the height should be. */
228 height
= root
->height
+ 1;
229 while (index
> radix_tree_maxindex(height
))
232 if (root
->rnode
== NULL
) {
233 root
->height
= height
;
238 unsigned int newheight
;
239 if (!(node
= radix_tree_node_alloc(root
)))
242 /* Increase the height. */
243 node
->slots
[0] = radix_tree_indirect_to_ptr(root
->rnode
);
245 /* Propagate the aggregated tag info into the new root */
246 for (tag
= 0; tag
< RADIX_TREE_MAX_TAGS
; tag
++) {
247 if (root_tag_get(root
, tag
))
248 tag_set(node
, tag
, 0);
251 newheight
= root
->height
+1;
252 node
->height
= newheight
;
254 node
= radix_tree_ptr_to_indirect(node
);
255 rcu_assign_pointer(root
->rnode
, node
);
256 root
->height
= newheight
;
257 } while (height
> root
->height
);
263 * radix_tree_insert - insert into a radix tree
264 * @root: radix tree root
266 * @item: item to insert
268 * Insert an item into the radix tree at position @index.
270 int radix_tree_insert(struct radix_tree_root
*root
,
271 unsigned long index
, void *item
)
273 struct radix_tree_node
*node
= NULL
, *slot
;
274 unsigned int height
, shift
;
278 BUG_ON(radix_tree_is_indirect_ptr(item
));
280 /* Make sure the tree is high enough. */
281 if (index
> radix_tree_maxindex(root
->height
)) {
282 error
= radix_tree_extend(root
, index
);
287 slot
= radix_tree_indirect_to_ptr(root
->rnode
);
289 height
= root
->height
;
290 shift
= (height
-1) * RADIX_TREE_MAP_SHIFT
;
292 offset
= 0; /* uninitialised var warning */
295 /* Have to add a child node. */
296 if (!(slot
= radix_tree_node_alloc(root
)))
298 slot
->height
= height
;
300 rcu_assign_pointer(node
->slots
[offset
], slot
);
303 rcu_assign_pointer(root
->rnode
,
304 radix_tree_ptr_to_indirect(slot
));
307 /* Go a level down */
308 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
310 slot
= node
->slots
[offset
];
311 shift
-= RADIX_TREE_MAP_SHIFT
;
320 rcu_assign_pointer(node
->slots
[offset
], item
);
321 BUG_ON(tag_get(node
, 0, offset
));
322 BUG_ON(tag_get(node
, 1, offset
));
324 rcu_assign_pointer(root
->rnode
, item
);
325 BUG_ON(root_tag_get(root
, 0));
326 BUG_ON(root_tag_get(root
, 1));
331 EXPORT_SYMBOL(radix_tree_insert
);
334 * radix_tree_lookup_slot - lookup a slot in a radix tree
335 * @root: radix tree root
338 * Returns: the slot corresponding to the position @index in the
339 * radix tree @root. This is useful for update-if-exists operations.
341 * This function cannot be called under rcu_read_lock, it must be
342 * excluded from writers, as must the returned slot for subsequent
343 * use by radix_tree_deref_slot() and radix_tree_replace slot.
344 * Caller must hold tree write locked across slot lookup and
347 void **radix_tree_lookup_slot(struct radix_tree_root
*root
, unsigned long index
)
349 unsigned int height
, shift
;
350 struct radix_tree_node
*node
, **slot
;
356 if (!radix_tree_is_indirect_ptr(node
)) {
359 return (void **)&root
->rnode
;
361 node
= radix_tree_indirect_to_ptr(node
);
363 height
= node
->height
;
364 if (index
> radix_tree_maxindex(height
))
367 shift
= (height
-1) * RADIX_TREE_MAP_SHIFT
;
370 slot
= (struct radix_tree_node
**)
371 (node
->slots
+ ((index
>>shift
) & RADIX_TREE_MAP_MASK
));
376 shift
-= RADIX_TREE_MAP_SHIFT
;
378 } while (height
> 0);
380 return (void **)slot
;
382 EXPORT_SYMBOL(radix_tree_lookup_slot
);
385 * radix_tree_lookup - perform lookup operation on a radix tree
386 * @root: radix tree root
389 * Lookup the item at the position @index in the radix tree @root.
391 * This function can be called under rcu_read_lock, however the caller
392 * must manage lifetimes of leaf nodes (eg. RCU may also be used to free
393 * them safely). No RCU barriers are required to access or modify the
394 * returned item, however.
396 void *radix_tree_lookup(struct radix_tree_root
*root
, unsigned long index
)
398 unsigned int height
, shift
;
399 struct radix_tree_node
*node
, **slot
;
401 node
= rcu_dereference(root
->rnode
);
405 if (!radix_tree_is_indirect_ptr(node
)) {
410 node
= radix_tree_indirect_to_ptr(node
);
412 height
= node
->height
;
413 if (index
> radix_tree_maxindex(height
))
416 shift
= (height
-1) * RADIX_TREE_MAP_SHIFT
;
419 slot
= (struct radix_tree_node
**)
420 (node
->slots
+ ((index
>>shift
) & RADIX_TREE_MAP_MASK
));
421 node
= rcu_dereference(*slot
);
425 shift
-= RADIX_TREE_MAP_SHIFT
;
427 } while (height
> 0);
431 EXPORT_SYMBOL(radix_tree_lookup
);
434 * radix_tree_tag_set - set a tag on a radix tree node
435 * @root: radix tree root
439 * Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
440 * corresponding to @index in the radix tree. From
441 * the root all the way down to the leaf node.
443 * Returns the address of the tagged item. Setting a tag on a not-present
446 void *radix_tree_tag_set(struct radix_tree_root
*root
,
447 unsigned long index
, unsigned int tag
)
449 unsigned int height
, shift
;
450 struct radix_tree_node
*slot
;
452 height
= root
->height
;
453 BUG_ON(index
> radix_tree_maxindex(height
));
455 slot
= radix_tree_indirect_to_ptr(root
->rnode
);
456 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
461 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
462 if (!tag_get(slot
, tag
, offset
))
463 tag_set(slot
, tag
, offset
);
464 slot
= slot
->slots
[offset
];
465 BUG_ON(slot
== NULL
);
466 shift
-= RADIX_TREE_MAP_SHIFT
;
470 /* set the root's tag bit */
471 if (slot
&& !root_tag_get(root
, tag
))
472 root_tag_set(root
, tag
);
476 EXPORT_SYMBOL(radix_tree_tag_set
);
479 * radix_tree_tag_clear - clear a tag on a radix tree node
480 * @root: radix tree root
484 * Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
485 * corresponding to @index in the radix tree. If
486 * this causes the leaf node to have no tags set then clear the tag in the
487 * next-to-leaf node, etc.
489 * Returns the address of the tagged item on success, else NULL. ie:
490 * has the same return value and semantics as radix_tree_lookup().
492 void *radix_tree_tag_clear(struct radix_tree_root
*root
,
493 unsigned long index
, unsigned int tag
)
495 struct radix_tree_path path
[RADIX_TREE_MAX_PATH
], *pathp
= path
;
496 struct radix_tree_node
*slot
= NULL
;
497 unsigned int height
, shift
;
499 height
= root
->height
;
500 if (index
> radix_tree_maxindex(height
))
503 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
505 slot
= radix_tree_indirect_to_ptr(root
->rnode
);
513 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
514 pathp
[1].offset
= offset
;
515 pathp
[1].node
= slot
;
516 slot
= slot
->slots
[offset
];
518 shift
-= RADIX_TREE_MAP_SHIFT
;
525 while (pathp
->node
) {
526 if (!tag_get(pathp
->node
, tag
, pathp
->offset
))
528 tag_clear(pathp
->node
, tag
, pathp
->offset
);
529 if (any_tag_set(pathp
->node
, tag
))
534 /* clear the root's tag bit */
535 if (root_tag_get(root
, tag
))
536 root_tag_clear(root
, tag
);
541 EXPORT_SYMBOL(radix_tree_tag_clear
);
543 #ifndef __KERNEL__ /* Only the test harness uses this at present */
545 * radix_tree_tag_get - get a tag on a radix tree node
546 * @root: radix tree root
548 * @tag: tag index (< RADIX_TREE_MAX_TAGS)
552 * 0: tag not present or not set
555 int radix_tree_tag_get(struct radix_tree_root
*root
,
556 unsigned long index
, unsigned int tag
)
558 unsigned int height
, shift
;
559 struct radix_tree_node
*node
;
560 int saw_unset_tag
= 0;
562 /* check the root's tag bit */
563 if (!root_tag_get(root
, tag
))
566 node
= rcu_dereference(root
->rnode
);
570 if (!radix_tree_is_indirect_ptr(node
))
572 node
= radix_tree_indirect_to_ptr(node
);
574 height
= node
->height
;
575 if (index
> radix_tree_maxindex(height
))
578 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
586 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
589 * This is just a debug check. Later, we can bale as soon as
590 * we see an unset tag.
592 if (!tag_get(node
, tag
, offset
))
595 int ret
= tag_get(node
, tag
, offset
);
597 BUG_ON(ret
&& saw_unset_tag
);
600 node
= rcu_dereference(node
->slots
[offset
]);
601 shift
-= RADIX_TREE_MAP_SHIFT
;
605 EXPORT_SYMBOL(radix_tree_tag_get
);
609 * radix_tree_next_hole - find the next hole (not-present entry)
612 * @max_scan: maximum range to search
614 * Search the set [index, min(index+max_scan-1, MAX_INDEX)] for the lowest
617 * Returns: the index of the hole if found, otherwise returns an index
618 * outside of the set specified (in which case 'return - index >= max_scan'
621 * radix_tree_next_hole may be called under rcu_read_lock. However, like
622 * radix_tree_gang_lookup, this will not atomically search a snapshot of the
623 * tree at a single point in time. For example, if a hole is created at index
624 * 5, then subsequently a hole is created at index 10, radix_tree_next_hole
625 * covering both indexes may return 10 if called under rcu_read_lock.
627 unsigned long radix_tree_next_hole(struct radix_tree_root
*root
,
628 unsigned long index
, unsigned long max_scan
)
632 for (i
= 0; i
< max_scan
; i
++) {
633 if (!radix_tree_lookup(root
, index
))
642 EXPORT_SYMBOL(radix_tree_next_hole
);
645 __lookup(struct radix_tree_node
*slot
, void **results
, unsigned long index
,
646 unsigned int max_items
, unsigned long *next_index
)
648 unsigned int nr_found
= 0;
649 unsigned int shift
, height
;
652 height
= slot
->height
;
655 shift
= (height
-1) * RADIX_TREE_MAP_SHIFT
;
657 for ( ; height
> 1; height
--) {
658 i
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
660 if (slot
->slots
[i
] != NULL
)
662 index
&= ~((1UL << shift
) - 1);
663 index
+= 1UL << shift
;
665 goto out
; /* 32-bit wraparound */
667 if (i
== RADIX_TREE_MAP_SIZE
)
671 shift
-= RADIX_TREE_MAP_SHIFT
;
672 slot
= rcu_dereference(slot
->slots
[i
]);
677 /* Bottom level: grab some items */
678 for (i
= index
& RADIX_TREE_MAP_MASK
; i
< RADIX_TREE_MAP_SIZE
; i
++) {
679 struct radix_tree_node
*node
;
681 node
= slot
->slots
[i
];
683 results
[nr_found
++] = rcu_dereference(node
);
684 if (nr_found
== max_items
)
694 * radix_tree_gang_lookup - perform multiple lookup on a radix tree
695 * @root: radix tree root
696 * @results: where the results of the lookup are placed
697 * @first_index: start the lookup from this key
698 * @max_items: place up to this many items at *results
700 * Performs an index-ascending scan of the tree for present items. Places
701 * them at *@results and returns the number of items which were placed at
704 * The implementation is naive.
706 * Like radix_tree_lookup, radix_tree_gang_lookup may be called under
707 * rcu_read_lock. In this case, rather than the returned results being
708 * an atomic snapshot of the tree at a single point in time, the semantics
709 * of an RCU protected gang lookup are as though multiple radix_tree_lookups
710 * have been issued in individual locks, and results stored in 'results'.
713 radix_tree_gang_lookup(struct radix_tree_root
*root
, void **results
,
714 unsigned long first_index
, unsigned int max_items
)
716 unsigned long max_index
;
717 struct radix_tree_node
*node
;
718 unsigned long cur_index
= first_index
;
721 node
= rcu_dereference(root
->rnode
);
725 if (!radix_tree_is_indirect_ptr(node
)) {
731 node
= radix_tree_indirect_to_ptr(node
);
733 max_index
= radix_tree_maxindex(node
->height
);
736 while (ret
< max_items
) {
737 unsigned int nr_found
;
738 unsigned long next_index
; /* Index of next search */
740 if (cur_index
> max_index
)
742 nr_found
= __lookup(node
, results
+ ret
, cur_index
,
743 max_items
- ret
, &next_index
);
747 cur_index
= next_index
;
752 EXPORT_SYMBOL(radix_tree_gang_lookup
);
755 * FIXME: the two tag_get()s here should use find_next_bit() instead of
756 * open-coding the search.
759 __lookup_tag(struct radix_tree_node
*slot
, void **results
, unsigned long index
,
760 unsigned int max_items
, unsigned long *next_index
, unsigned int tag
)
762 unsigned int nr_found
= 0;
763 unsigned int shift
, height
;
765 height
= slot
->height
;
768 shift
= (height
-1) * RADIX_TREE_MAP_SHIFT
;
771 unsigned long i
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
774 if (tag_get(slot
, tag
, i
))
776 index
&= ~((1UL << shift
) - 1);
777 index
+= 1UL << shift
;
779 goto out
; /* 32-bit wraparound */
781 if (i
== RADIX_TREE_MAP_SIZE
)
785 if (height
== 0) { /* Bottom level: grab some items */
786 unsigned long j
= index
& RADIX_TREE_MAP_MASK
;
788 for ( ; j
< RADIX_TREE_MAP_SIZE
; j
++) {
789 struct radix_tree_node
*node
;
791 if (!tag_get(slot
, tag
, j
))
793 node
= slot
->slots
[j
];
795 * Even though the tag was found set, we need to
796 * recheck that we have a non-NULL node, because
797 * if this lookup is lockless, it may have been
798 * subsequently deleted.
800 * Similar care must be taken in any place that
801 * lookup ->slots[x] without a lock (ie. can't
802 * rely on its value remaining the same).
805 node
= rcu_dereference(node
);
806 results
[nr_found
++] = node
;
807 if (nr_found
== max_items
)
812 shift
-= RADIX_TREE_MAP_SHIFT
;
813 slot
= rcu_dereference(slot
->slots
[i
]);
823 * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
825 * @root: radix tree root
826 * @results: where the results of the lookup are placed
827 * @first_index: start the lookup from this key
828 * @max_items: place up to this many items at *results
829 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
831 * Performs an index-ascending scan of the tree for present items which
832 * have the tag indexed by @tag set. Places the items at *@results and
833 * returns the number of items which were placed at *@results.
836 radix_tree_gang_lookup_tag(struct radix_tree_root
*root
, void **results
,
837 unsigned long first_index
, unsigned int max_items
,
840 struct radix_tree_node
*node
;
841 unsigned long max_index
;
842 unsigned long cur_index
= first_index
;
845 /* check the root's tag bit */
846 if (!root_tag_get(root
, tag
))
849 node
= rcu_dereference(root
->rnode
);
853 if (!radix_tree_is_indirect_ptr(node
)) {
859 node
= radix_tree_indirect_to_ptr(node
);
861 max_index
= radix_tree_maxindex(node
->height
);
864 while (ret
< max_items
) {
865 unsigned int nr_found
;
866 unsigned long next_index
; /* Index of next search */
868 if (cur_index
> max_index
)
870 nr_found
= __lookup_tag(node
, results
+ ret
, cur_index
,
871 max_items
- ret
, &next_index
, tag
);
875 cur_index
= next_index
;
880 EXPORT_SYMBOL(radix_tree_gang_lookup_tag
);
883 * radix_tree_shrink - shrink height of a radix tree to minimal
884 * @root radix tree root
886 static inline void radix_tree_shrink(struct radix_tree_root
*root
)
888 /* try to shrink tree height */
889 while (root
->height
> 0) {
890 struct radix_tree_node
*to_free
= root
->rnode
;
893 BUG_ON(!radix_tree_is_indirect_ptr(to_free
));
894 to_free
= radix_tree_indirect_to_ptr(to_free
);
897 * The candidate node has more than one child, or its child
898 * is not at the leftmost slot, we cannot shrink.
900 if (to_free
->count
!= 1)
902 if (!to_free
->slots
[0])
906 * We don't need rcu_assign_pointer(), since we are simply
907 * moving the node from one part of the tree to another. If
908 * it was safe to dereference the old pointer to it
909 * (to_free->slots[0]), it will be safe to dereference the new
912 newptr
= to_free
->slots
[0];
913 if (root
->height
> 1)
914 newptr
= radix_tree_ptr_to_indirect(newptr
);
915 root
->rnode
= newptr
;
917 /* must only free zeroed nodes into the slab */
918 tag_clear(to_free
, 0, 0);
919 tag_clear(to_free
, 1, 0);
920 to_free
->slots
[0] = NULL
;
922 radix_tree_node_free(to_free
);
927 * radix_tree_delete - delete an item from a radix tree
928 * @root: radix tree root
931 * Remove the item at @index from the radix tree rooted at @root.
933 * Returns the address of the deleted item, or NULL if it was not present.
935 void *radix_tree_delete(struct radix_tree_root
*root
, unsigned long index
)
937 struct radix_tree_path path
[RADIX_TREE_MAX_PATH
], *pathp
= path
;
938 struct radix_tree_node
*slot
= NULL
;
939 struct radix_tree_node
*to_free
;
940 unsigned int height
, shift
;
944 height
= root
->height
;
945 if (index
> radix_tree_maxindex(height
))
950 root_tag_clear_all(root
);
954 slot
= radix_tree_indirect_to_ptr(slot
);
956 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
964 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
965 pathp
->offset
= offset
;
967 slot
= slot
->slots
[offset
];
968 shift
-= RADIX_TREE_MAP_SHIFT
;
970 } while (height
> 0);
976 * Clear all tags associated with the just-deleted item
978 for (tag
= 0; tag
< RADIX_TREE_MAX_TAGS
; tag
++) {
979 if (tag_get(pathp
->node
, tag
, pathp
->offset
))
980 radix_tree_tag_clear(root
, index
, tag
);
984 /* Now free the nodes we do not need anymore */
985 while (pathp
->node
) {
986 pathp
->node
->slots
[pathp
->offset
] = NULL
;
987 pathp
->node
->count
--;
989 * Queue the node for deferred freeing after the
990 * last reference to it disappears (set NULL, above).
993 radix_tree_node_free(to_free
);
995 if (pathp
->node
->count
) {
997 radix_tree_indirect_to_ptr(root
->rnode
))
998 radix_tree_shrink(root
);
1002 /* Node with zero slots in use so free it */
1003 to_free
= pathp
->node
;
1007 root_tag_clear_all(root
);
1011 radix_tree_node_free(to_free
);
1016 EXPORT_SYMBOL(radix_tree_delete
);
1019 * radix_tree_tagged - test whether any items in the tree are tagged
1020 * @root: radix tree root
1023 int radix_tree_tagged(struct radix_tree_root
*root
, unsigned int tag
)
1025 return root_tag_get(root
, tag
);
1027 EXPORT_SYMBOL(radix_tree_tagged
);
1030 radix_tree_node_ctor(void *node
, struct kmem_cache
*cachep
, unsigned long flags
)
1032 memset(node
, 0, sizeof(struct radix_tree_node
));
1035 static __init
unsigned long __maxindex(unsigned int height
)
1037 unsigned int tmp
= height
* RADIX_TREE_MAP_SHIFT
;
1038 unsigned long index
= (~0UL >> (RADIX_TREE_INDEX_BITS
- tmp
- 1)) >> 1;
1040 if (tmp
>= RADIX_TREE_INDEX_BITS
)
1045 static __init
void radix_tree_init_maxindex(void)
1049 for (i
= 0; i
< ARRAY_SIZE(height_to_maxindex
); i
++)
1050 height_to_maxindex
[i
] = __maxindex(i
);
1053 static int radix_tree_callback(struct notifier_block
*nfb
,
1054 unsigned long action
,
1057 int cpu
= (long)hcpu
;
1058 struct radix_tree_preload
*rtp
;
1060 /* Free per-cpu pool of perloaded nodes */
1061 if (action
== CPU_DEAD
|| action
== CPU_DEAD_FROZEN
) {
1062 rtp
= &per_cpu(radix_tree_preloads
, cpu
);
1064 kmem_cache_free(radix_tree_node_cachep
,
1065 rtp
->nodes
[rtp
->nr
-1]);
1066 rtp
->nodes
[rtp
->nr
-1] = NULL
;
1073 void __init
radix_tree_init(void)
1075 radix_tree_node_cachep
= kmem_cache_create("radix_tree_node",
1076 sizeof(struct radix_tree_node
), 0,
1077 SLAB_PANIC
, radix_tree_node_ctor
);
1078 radix_tree_init_maxindex();
1079 hotcpu_notifier(radix_tree_callback
, 0);