2 * Copyright (C) 2001 Momchil Velikov
3 * Portions Copyright (C) 2001 Christoph Hellwig
4 * Copyright (C) 2005 SGI, Christoph Lameter <clameter@sgi.com>
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License as
8 * published by the Free Software Foundation; either version 2, or (at
9 * your option) any later version.
11 * This program is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
21 #include <linux/errno.h>
22 #include <linux/init.h>
23 #include <linux/kernel.h>
24 #include <linux/module.h>
25 #include <linux/radix-tree.h>
26 #include <linux/percpu.h>
27 #include <linux/slab.h>
28 #include <linux/notifier.h>
29 #include <linux/cpu.h>
30 #include <linux/gfp.h>
31 #include <linux/string.h>
32 #include <linux/bitops.h>
36 #define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6)
38 #define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */
41 #define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT)
42 #define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1)
44 #define RADIX_TREE_TAG_LONGS \
45 ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
47 struct radix_tree_node
{
49 void *slots
[RADIX_TREE_MAP_SIZE
];
50 unsigned long tags
[RADIX_TREE_MAX_TAGS
][RADIX_TREE_TAG_LONGS
];
53 struct radix_tree_path
{
54 struct radix_tree_node
*node
;
58 #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
59 #define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2)
61 static unsigned long height_to_maxindex
[RADIX_TREE_MAX_PATH
] __read_mostly
;
64 * Radix tree node cache.
66 static kmem_cache_t
*radix_tree_node_cachep
;
69 * Per-cpu pool of preloaded nodes
71 struct radix_tree_preload
{
73 struct radix_tree_node
*nodes
[RADIX_TREE_MAX_PATH
];
75 DEFINE_PER_CPU(struct radix_tree_preload
, radix_tree_preloads
) = { 0, };
77 static inline gfp_t
root_gfp_mask(struct radix_tree_root
*root
)
79 return root
->gfp_mask
& __GFP_BITS_MASK
;
83 * This assumes that the caller has performed appropriate preallocation, and
84 * that the caller has pinned this thread of control to the current CPU.
86 static struct radix_tree_node
*
87 radix_tree_node_alloc(struct radix_tree_root
*root
)
89 struct radix_tree_node
*ret
;
90 gfp_t gfp_mask
= root_gfp_mask(root
);
92 ret
= kmem_cache_alloc(radix_tree_node_cachep
, gfp_mask
);
93 if (ret
== NULL
&& !(gfp_mask
& __GFP_WAIT
)) {
94 struct radix_tree_preload
*rtp
;
96 rtp
= &__get_cpu_var(radix_tree_preloads
);
98 ret
= rtp
->nodes
[rtp
->nr
- 1];
99 rtp
->nodes
[rtp
->nr
- 1] = NULL
;
107 radix_tree_node_free(struct radix_tree_node
*node
)
109 kmem_cache_free(radix_tree_node_cachep
, node
);
113 * Load up this CPU's radix_tree_node buffer with sufficient objects to
114 * ensure that the addition of a single element in the tree cannot fail. On
115 * success, return zero, with preemption disabled. On error, return -ENOMEM
116 * with preemption not disabled.
118 int radix_tree_preload(gfp_t gfp_mask
)
120 struct radix_tree_preload
*rtp
;
121 struct radix_tree_node
*node
;
125 rtp
= &__get_cpu_var(radix_tree_preloads
);
126 while (rtp
->nr
< ARRAY_SIZE(rtp
->nodes
)) {
128 node
= kmem_cache_alloc(radix_tree_node_cachep
, gfp_mask
);
132 rtp
= &__get_cpu_var(radix_tree_preloads
);
133 if (rtp
->nr
< ARRAY_SIZE(rtp
->nodes
))
134 rtp
->nodes
[rtp
->nr
++] = node
;
136 kmem_cache_free(radix_tree_node_cachep
, node
);
143 static inline void tag_set(struct radix_tree_node
*node
, unsigned int tag
,
146 __set_bit(offset
, node
->tags
[tag
]);
149 static inline void tag_clear(struct radix_tree_node
*node
, unsigned int tag
,
152 __clear_bit(offset
, node
->tags
[tag
]);
155 static inline int tag_get(struct radix_tree_node
*node
, unsigned int tag
,
158 return test_bit(offset
, node
->tags
[tag
]);
161 static inline void root_tag_set(struct radix_tree_root
*root
, unsigned int tag
)
163 root
->gfp_mask
|= (1 << (tag
+ __GFP_BITS_SHIFT
));
167 static inline void root_tag_clear(struct radix_tree_root
*root
, unsigned int tag
)
169 root
->gfp_mask
&= ~(1 << (tag
+ __GFP_BITS_SHIFT
));
172 static inline void root_tag_clear_all(struct radix_tree_root
*root
)
174 root
->gfp_mask
&= __GFP_BITS_MASK
;
177 static inline int root_tag_get(struct radix_tree_root
*root
, unsigned int tag
)
179 return root
->gfp_mask
& (1 << (tag
+ __GFP_BITS_SHIFT
));
183 * Returns 1 if any slot in the node has this tag set.
184 * Otherwise returns 0.
186 static inline int any_tag_set(struct radix_tree_node
*node
, unsigned int tag
)
189 for (idx
= 0; idx
< RADIX_TREE_TAG_LONGS
; idx
++) {
190 if (node
->tags
[tag
][idx
])
197 * Return the maximum key which can be store into a
198 * radix tree with height HEIGHT.
200 static inline unsigned long radix_tree_maxindex(unsigned int height
)
202 return height_to_maxindex
[height
];
206 * Extend a radix tree so it can store key @index.
208 static int radix_tree_extend(struct radix_tree_root
*root
, unsigned long index
)
210 struct radix_tree_node
*node
;
214 /* Figure out what the height should be. */
215 height
= root
->height
+ 1;
216 while (index
> radix_tree_maxindex(height
))
219 if (root
->rnode
== NULL
) {
220 root
->height
= height
;
225 if (!(node
= radix_tree_node_alloc(root
)))
228 /* Increase the height. */
229 node
->slots
[0] = root
->rnode
;
231 /* Propagate the aggregated tag info into the new root */
232 for (tag
= 0; tag
< RADIX_TREE_MAX_TAGS
; tag
++) {
233 if (root_tag_get(root
, tag
))
234 tag_set(node
, tag
, 0);
240 } while (height
> root
->height
);
246 * radix_tree_insert - insert into a radix tree
247 * @root: radix tree root
249 * @item: item to insert
251 * Insert an item into the radix tree at position @index.
253 int radix_tree_insert(struct radix_tree_root
*root
,
254 unsigned long index
, void *item
)
256 struct radix_tree_node
*node
= NULL
, *slot
;
257 unsigned int height
, shift
;
261 /* Make sure the tree is high enough. */
262 if (index
> radix_tree_maxindex(root
->height
)) {
263 error
= radix_tree_extend(root
, index
);
269 height
= root
->height
;
270 shift
= (height
-1) * RADIX_TREE_MAP_SHIFT
;
272 offset
= 0; /* uninitialised var warning */
275 /* Have to add a child node. */
276 if (!(slot
= radix_tree_node_alloc(root
)))
279 node
->slots
[offset
] = slot
;
285 /* Go a level down */
286 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
288 slot
= node
->slots
[offset
];
289 shift
-= RADIX_TREE_MAP_SHIFT
;
298 node
->slots
[offset
] = item
;
299 BUG_ON(tag_get(node
, 0, offset
));
300 BUG_ON(tag_get(node
, 1, offset
));
303 BUG_ON(root_tag_get(root
, 0));
304 BUG_ON(root_tag_get(root
, 1));
309 EXPORT_SYMBOL(radix_tree_insert
);
311 static inline void **__lookup_slot(struct radix_tree_root
*root
,
314 unsigned int height
, shift
;
315 struct radix_tree_node
**slot
;
317 height
= root
->height
;
319 if (index
> radix_tree_maxindex(height
))
322 if (height
== 0 && root
->rnode
)
323 return (void **)&root
->rnode
;
325 shift
= (height
-1) * RADIX_TREE_MAP_SHIFT
;
332 slot
= (struct radix_tree_node
**)
334 ((index
>> shift
) & RADIX_TREE_MAP_MASK
));
335 shift
-= RADIX_TREE_MAP_SHIFT
;
339 return (void **)slot
;
343 * radix_tree_lookup_slot - lookup a slot in a radix tree
344 * @root: radix tree root
347 * Lookup the slot corresponding to the position @index in the radix tree
348 * @root. This is useful for update-if-exists operations.
350 void **radix_tree_lookup_slot(struct radix_tree_root
*root
, unsigned long index
)
352 return __lookup_slot(root
, index
);
354 EXPORT_SYMBOL(radix_tree_lookup_slot
);
357 * radix_tree_lookup - perform lookup operation on a radix tree
358 * @root: radix tree root
361 * Lookup the item at the position @index in the radix tree @root.
363 void *radix_tree_lookup(struct radix_tree_root
*root
, unsigned long index
)
367 slot
= __lookup_slot(root
, index
);
368 return slot
!= NULL
? *slot
: NULL
;
370 EXPORT_SYMBOL(radix_tree_lookup
);
373 * radix_tree_tag_set - set a tag on a radix tree node
374 * @root: radix tree root
378 * Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
379 * corresponding to @index in the radix tree. From
380 * the root all the way down to the leaf node.
382 * Returns the address of the tagged item. Setting a tag on a not-present
385 void *radix_tree_tag_set(struct radix_tree_root
*root
,
386 unsigned long index
, unsigned int tag
)
388 unsigned int height
, shift
;
389 struct radix_tree_node
*slot
;
391 height
= root
->height
;
392 if (index
> radix_tree_maxindex(height
))
396 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
401 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
402 if (!tag_get(slot
, tag
, offset
))
403 tag_set(slot
, tag
, offset
);
404 slot
= slot
->slots
[offset
];
405 BUG_ON(slot
== NULL
);
406 shift
-= RADIX_TREE_MAP_SHIFT
;
410 /* set the root's tag bit */
411 if (slot
&& !root_tag_get(root
, tag
))
412 root_tag_set(root
, tag
);
416 EXPORT_SYMBOL(radix_tree_tag_set
);
419 * radix_tree_tag_clear - clear a tag on a radix tree node
420 * @root: radix tree root
424 * Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
425 * corresponding to @index in the radix tree. If
426 * this causes the leaf node to have no tags set then clear the tag in the
427 * next-to-leaf node, etc.
429 * Returns the address of the tagged item on success, else NULL. ie:
430 * has the same return value and semantics as radix_tree_lookup().
432 void *radix_tree_tag_clear(struct radix_tree_root
*root
,
433 unsigned long index
, unsigned int tag
)
435 struct radix_tree_path path
[RADIX_TREE_MAX_PATH
], *pathp
= path
;
436 struct radix_tree_node
*slot
= NULL
;
437 unsigned int height
, shift
;
439 height
= root
->height
;
440 if (index
> radix_tree_maxindex(height
))
443 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
453 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
454 pathp
[1].offset
= offset
;
455 pathp
[1].node
= slot
;
456 slot
= slot
->slots
[offset
];
458 shift
-= RADIX_TREE_MAP_SHIFT
;
465 while (pathp
->node
) {
466 if (!tag_get(pathp
->node
, tag
, pathp
->offset
))
468 tag_clear(pathp
->node
, tag
, pathp
->offset
);
469 if (any_tag_set(pathp
->node
, tag
))
474 /* clear the root's tag bit */
475 if (root_tag_get(root
, tag
))
476 root_tag_clear(root
, tag
);
481 EXPORT_SYMBOL(radix_tree_tag_clear
);
483 #ifndef __KERNEL__ /* Only the test harness uses this at present */
485 * radix_tree_tag_get - get a tag on a radix tree node
486 * @root: radix tree root
488 * @tag: tag index (< RADIX_TREE_MAX_TAGS)
492 * 0: tag not present or not set
495 int radix_tree_tag_get(struct radix_tree_root
*root
,
496 unsigned long index
, unsigned int tag
)
498 unsigned int height
, shift
;
499 struct radix_tree_node
*slot
;
500 int saw_unset_tag
= 0;
502 height
= root
->height
;
503 if (index
> radix_tree_maxindex(height
))
506 /* check the root's tag bit */
507 if (!root_tag_get(root
, tag
))
513 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
522 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
525 * This is just a debug check. Later, we can bale as soon as
526 * we see an unset tag.
528 if (!tag_get(slot
, tag
, offset
))
531 int ret
= tag_get(slot
, tag
, offset
);
533 BUG_ON(ret
&& saw_unset_tag
);
536 slot
= slot
->slots
[offset
];
537 shift
-= RADIX_TREE_MAP_SHIFT
;
541 EXPORT_SYMBOL(radix_tree_tag_get
);
545 __lookup(struct radix_tree_root
*root
, void **results
, unsigned long index
,
546 unsigned int max_items
, unsigned long *next_index
)
548 unsigned int nr_found
= 0;
549 unsigned int shift
, height
;
550 struct radix_tree_node
*slot
;
553 height
= root
->height
;
555 if (root
->rnode
&& index
== 0)
556 results
[nr_found
++] = root
->rnode
;
560 shift
= (height
-1) * RADIX_TREE_MAP_SHIFT
;
563 for ( ; height
> 1; height
--) {
565 for (i
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
566 i
< RADIX_TREE_MAP_SIZE
; i
++) {
567 if (slot
->slots
[i
] != NULL
)
569 index
&= ~((1UL << shift
) - 1);
570 index
+= 1UL << shift
;
572 goto out
; /* 32-bit wraparound */
574 if (i
== RADIX_TREE_MAP_SIZE
)
577 shift
-= RADIX_TREE_MAP_SHIFT
;
578 slot
= slot
->slots
[i
];
581 /* Bottom level: grab some items */
582 for (i
= index
& RADIX_TREE_MAP_MASK
; i
< RADIX_TREE_MAP_SIZE
; i
++) {
584 if (slot
->slots
[i
]) {
585 results
[nr_found
++] = slot
->slots
[i
];
586 if (nr_found
== max_items
)
596 * radix_tree_gang_lookup - perform multiple lookup on a radix tree
597 * @root: radix tree root
598 * @results: where the results of the lookup are placed
599 * @first_index: start the lookup from this key
600 * @max_items: place up to this many items at *results
602 * Performs an index-ascending scan of the tree for present items. Places
603 * them at *@results and returns the number of items which were placed at
606 * The implementation is naive.
609 radix_tree_gang_lookup(struct radix_tree_root
*root
, void **results
,
610 unsigned long first_index
, unsigned int max_items
)
612 const unsigned long max_index
= radix_tree_maxindex(root
->height
);
613 unsigned long cur_index
= first_index
;
614 unsigned int ret
= 0;
616 while (ret
< max_items
) {
617 unsigned int nr_found
;
618 unsigned long next_index
; /* Index of next search */
620 if (cur_index
> max_index
)
622 nr_found
= __lookup(root
, results
+ ret
, cur_index
,
623 max_items
- ret
, &next_index
);
627 cur_index
= next_index
;
631 EXPORT_SYMBOL(radix_tree_gang_lookup
);
634 * FIXME: the two tag_get()s here should use find_next_bit() instead of
635 * open-coding the search.
638 __lookup_tag(struct radix_tree_root
*root
, void **results
, unsigned long index
,
639 unsigned int max_items
, unsigned long *next_index
, unsigned int tag
)
641 unsigned int nr_found
= 0;
643 unsigned int height
= root
->height
;
644 struct radix_tree_node
*slot
;
647 if (root
->rnode
&& index
== 0)
648 results
[nr_found
++] = root
->rnode
;
652 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
656 unsigned long i
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
658 for ( ; i
< RADIX_TREE_MAP_SIZE
; i
++) {
659 if (tag_get(slot
, tag
, i
)) {
660 BUG_ON(slot
->slots
[i
] == NULL
);
663 index
&= ~((1UL << shift
) - 1);
664 index
+= 1UL << shift
;
666 goto out
; /* 32-bit wraparound */
668 if (i
== RADIX_TREE_MAP_SIZE
)
671 if (height
== 0) { /* Bottom level: grab some items */
672 unsigned long j
= index
& RADIX_TREE_MAP_MASK
;
674 for ( ; j
< RADIX_TREE_MAP_SIZE
; j
++) {
676 if (tag_get(slot
, tag
, j
)) {
677 BUG_ON(slot
->slots
[j
] == NULL
);
678 results
[nr_found
++] = slot
->slots
[j
];
679 if (nr_found
== max_items
)
684 shift
-= RADIX_TREE_MAP_SHIFT
;
685 slot
= slot
->slots
[i
];
686 } while (height
> 0);
693 * radix_tree_gang_lookup_tag - 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
699 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
701 * Performs an index-ascending scan of the tree for present items which
702 * have the tag indexed by @tag set. Places the items at *@results and
703 * returns the number of items which were placed at *@results.
706 radix_tree_gang_lookup_tag(struct radix_tree_root
*root
, void **results
,
707 unsigned long first_index
, unsigned int max_items
,
710 const unsigned long max_index
= radix_tree_maxindex(root
->height
);
711 unsigned long cur_index
= first_index
;
712 unsigned int ret
= 0;
714 /* check the root's tag bit */
715 if (!root_tag_get(root
, tag
))
718 while (ret
< max_items
) {
719 unsigned int nr_found
;
720 unsigned long next_index
; /* Index of next search */
722 if (cur_index
> max_index
)
724 nr_found
= __lookup_tag(root
, results
+ ret
, cur_index
,
725 max_items
- ret
, &next_index
, tag
);
729 cur_index
= next_index
;
733 EXPORT_SYMBOL(radix_tree_gang_lookup_tag
);
736 * radix_tree_shrink - shrink height of a radix tree to minimal
737 * @root radix tree root
739 static inline void radix_tree_shrink(struct radix_tree_root
*root
)
741 /* try to shrink tree height */
742 while (root
->height
> 0 &&
743 root
->rnode
->count
== 1 &&
744 root
->rnode
->slots
[0]) {
745 struct radix_tree_node
*to_free
= root
->rnode
;
747 root
->rnode
= to_free
->slots
[0];
749 /* must only free zeroed nodes into the slab */
750 tag_clear(to_free
, 0, 0);
751 tag_clear(to_free
, 1, 0);
752 to_free
->slots
[0] = NULL
;
754 radix_tree_node_free(to_free
);
759 * radix_tree_delete - delete an item from a radix tree
760 * @root: radix tree root
763 * Remove the item at @index from the radix tree rooted at @root.
765 * Returns the address of the deleted item, or NULL if it was not present.
767 void *radix_tree_delete(struct radix_tree_root
*root
, unsigned long index
)
769 struct radix_tree_path path
[RADIX_TREE_MAX_PATH
], *pathp
= path
;
770 struct radix_tree_node
*slot
= NULL
;
771 unsigned int height
, shift
;
775 height
= root
->height
;
776 if (index
> radix_tree_maxindex(height
))
780 if (height
== 0 && root
->rnode
) {
781 root_tag_clear_all(root
);
786 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
794 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
795 pathp
->offset
= offset
;
797 slot
= slot
->slots
[offset
];
798 shift
-= RADIX_TREE_MAP_SHIFT
;
800 } while (height
> 0);
806 * Clear all tags associated with the just-deleted item
808 for (tag
= 0; tag
< RADIX_TREE_MAX_TAGS
; tag
++) {
809 if (tag_get(pathp
->node
, tag
, pathp
->offset
))
810 radix_tree_tag_clear(root
, index
, tag
);
813 /* Now free the nodes we do not need anymore */
814 while (pathp
->node
) {
815 pathp
->node
->slots
[pathp
->offset
] = NULL
;
816 pathp
->node
->count
--;
818 if (pathp
->node
->count
) {
819 if (pathp
->node
== root
->rnode
)
820 radix_tree_shrink(root
);
824 /* Node with zero slots in use so free it */
825 radix_tree_node_free(pathp
->node
);
829 root_tag_clear_all(root
);
836 EXPORT_SYMBOL(radix_tree_delete
);
839 * radix_tree_tagged - test whether any items in the tree are tagged
840 * @root: radix tree root
843 int radix_tree_tagged(struct radix_tree_root
*root
, unsigned int tag
)
845 return root_tag_get(root
, tag
);
847 EXPORT_SYMBOL(radix_tree_tagged
);
850 radix_tree_node_ctor(void *node
, kmem_cache_t
*cachep
, unsigned long flags
)
852 memset(node
, 0, sizeof(struct radix_tree_node
));
855 static __init
unsigned long __maxindex(unsigned int height
)
857 unsigned int tmp
= height
* RADIX_TREE_MAP_SHIFT
;
858 unsigned long index
= (~0UL >> (RADIX_TREE_INDEX_BITS
- tmp
- 1)) >> 1;
860 if (tmp
>= RADIX_TREE_INDEX_BITS
)
865 static __init
void radix_tree_init_maxindex(void)
869 for (i
= 0; i
< ARRAY_SIZE(height_to_maxindex
); i
++)
870 height_to_maxindex
[i
] = __maxindex(i
);
873 #ifdef CONFIG_HOTPLUG_CPU
874 static int radix_tree_callback(struct notifier_block
*nfb
,
875 unsigned long action
,
878 int cpu
= (long)hcpu
;
879 struct radix_tree_preload
*rtp
;
881 /* Free per-cpu pool of perloaded nodes */
882 if (action
== CPU_DEAD
) {
883 rtp
= &per_cpu(radix_tree_preloads
, cpu
);
885 kmem_cache_free(radix_tree_node_cachep
,
886 rtp
->nodes
[rtp
->nr
-1]);
887 rtp
->nodes
[rtp
->nr
-1] = NULL
;
893 #endif /* CONFIG_HOTPLUG_CPU */
895 void __init
radix_tree_init(void)
897 radix_tree_node_cachep
= kmem_cache_create("radix_tree_node",
898 sizeof(struct radix_tree_node
), 0,
899 SLAB_PANIC
, radix_tree_node_ctor
, NULL
);
900 radix_tree_init_maxindex();
901 hotcpu_notifier(radix_tree_callback
, 0);