2 * Copyright (C) 2007 Oracle. All rights reserved.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
20 * Copyright (C) 2001 Momchil Velikov
21 * Portions Copyright (C) 2001 Christoph Hellwig
22 * Copyright (C) 2005 SGI, Christoph Lameter <clameter@sgi.com>
24 * This program is free software; you can redistribute it and/or
25 * modify it under the terms of the GNU General Public License as
26 * published by the Free Software Foundation; either version 2, or (at
27 * your option) any later version.
29 * This program is distributed in the hope that it will be useful, but
30 * WITHOUT ANY WARRANTY; without even the implied warranty of
31 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
32 * General Public License for more details.
34 * You should have received a copy of the GNU General Public License
35 * along with this program; if not, write to the Free Software
36 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
39 #include "kerncompat.h"
40 #include "radix-tree.h"
42 #define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6)
44 #define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */
47 #define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT)
48 #define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1)
50 #define RADIX_TREE_TAG_LONGS \
51 ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
53 struct radix_tree_node
{
55 void *slots
[RADIX_TREE_MAP_SIZE
];
56 unsigned long tags
[RADIX_TREE_MAX_TAGS
][RADIX_TREE_TAG_LONGS
];
59 struct radix_tree_path
{
60 struct radix_tree_node
*node
;
64 #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
65 #define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2)
67 static unsigned long height_to_maxindex
[RADIX_TREE_MAX_PATH
] __read_mostly
;
70 * Per-cpu pool of preloaded nodes
72 struct radix_tree_preload
{
74 struct radix_tree_node
*nodes
[RADIX_TREE_MAX_PATH
];
76 static struct radix_tree_preload radix_tree_preloads
= { 0, };
78 static inline gfp_t
root_gfp_mask(struct radix_tree_root
*root
)
80 return root
->gfp_mask
& __GFP_BITS_MASK
;
83 static int internal_nodes
= 0;
85 * This assumes that the caller has performed appropriate preallocation, and
86 * that the caller has pinned this thread of control to the current CPU.
88 static struct radix_tree_node
*
89 radix_tree_node_alloc(struct radix_tree_root
*root
)
91 struct radix_tree_node
*ret
;
92 ret
= malloc(sizeof(struct radix_tree_node
));
94 memset(ret
, 0, sizeof(struct radix_tree_node
));
101 radix_tree_node_free(struct radix_tree_node
*node
)
108 * Load up this CPU's radix_tree_node buffer with sufficient objects to
109 * ensure that the addition of a single element in the tree cannot fail. On
110 * success, return zero, with preemption disabled. On error, return -ENOMEM
111 * with preemption not disabled.
113 int radix_tree_preload(gfp_t gfp_mask
)
115 struct radix_tree_preload
*rtp
;
116 struct radix_tree_node
*node
;
120 rtp
= &__get_cpu_var(radix_tree_preloads
);
121 while (rtp
->nr
< ARRAY_SIZE(rtp
->nodes
)) {
123 node
= radix_tree_node_alloc(NULL
);
127 rtp
= &__get_cpu_var(radix_tree_preloads
);
128 if (rtp
->nr
< ARRAY_SIZE(rtp
->nodes
))
129 rtp
->nodes
[rtp
->nr
++] = node
;
131 radix_tree_node_free(node
);
138 static inline void tag_set(struct radix_tree_node
*node
, unsigned int tag
,
141 __set_bit(offset
, node
->tags
[tag
]);
144 static inline void tag_clear(struct radix_tree_node
*node
, unsigned int tag
,
147 __clear_bit(offset
, node
->tags
[tag
]);
150 static inline int tag_get(struct radix_tree_node
*node
, unsigned int tag
,
153 return test_bit(offset
, node
->tags
[tag
]);
156 static inline void root_tag_set(struct radix_tree_root
*root
, unsigned int tag
)
158 root
->gfp_mask
|= (__force gfp_t
)(1 << (tag
+ __GFP_BITS_SHIFT
));
162 static inline void root_tag_clear(struct radix_tree_root
*root
, unsigned int tag
)
164 root
->gfp_mask
&= (__force gfp_t
)~(1 << (tag
+ __GFP_BITS_SHIFT
));
167 static inline void root_tag_clear_all(struct radix_tree_root
*root
)
169 root
->gfp_mask
&= __GFP_BITS_MASK
;
172 static inline int root_tag_get(struct radix_tree_root
*root
, unsigned int tag
)
174 return (__force
unsigned)root
->gfp_mask
& (1 << (tag
+ __GFP_BITS_SHIFT
));
178 * Returns 1 if any slot in the node has this tag set.
179 * Otherwise returns 0.
181 static inline int any_tag_set(struct radix_tree_node
*node
, unsigned int tag
)
184 for (idx
= 0; idx
< RADIX_TREE_TAG_LONGS
; idx
++) {
185 if (node
->tags
[tag
][idx
])
192 * Return the maximum key which can be store into a
193 * radix tree with height HEIGHT.
195 static inline unsigned long radix_tree_maxindex(unsigned int height
)
197 return height_to_maxindex
[height
];
201 * Extend a radix tree so it can store key @index.
203 static int radix_tree_extend(struct radix_tree_root
*root
, unsigned long index
)
205 struct radix_tree_node
*node
;
209 /* Figure out what the height should be. */
210 height
= root
->height
+ 1;
211 while (index
> radix_tree_maxindex(height
))
214 if (root
->rnode
== NULL
) {
215 root
->height
= height
;
220 if (!(node
= radix_tree_node_alloc(root
)))
223 /* Increase the height. */
224 node
->slots
[0] = root
->rnode
;
226 /* Propagate the aggregated tag info into the new root */
227 for (tag
= 0; tag
< RADIX_TREE_MAX_TAGS
; tag
++) {
228 if (root_tag_get(root
, tag
))
229 tag_set(node
, tag
, 0);
235 } while (height
> root
->height
);
241 * radix_tree_insert - insert into a radix tree
242 * @root: radix tree root
244 * @item: item to insert
246 * Insert an item into the radix tree at position @index.
248 int radix_tree_insert(struct radix_tree_root
*root
,
249 unsigned long index
, void *item
)
251 struct radix_tree_node
*node
= NULL
, *slot
;
252 unsigned int height
, shift
;
256 /* Make sure the tree is high enough. */
257 if (index
> radix_tree_maxindex(root
->height
)) {
258 error
= radix_tree_extend(root
, index
);
264 height
= root
->height
;
265 shift
= (height
-1) * RADIX_TREE_MAP_SHIFT
;
267 offset
= 0; /* uninitialised var warning */
270 /* Have to add a child node. */
271 if (!(slot
= radix_tree_node_alloc(root
)))
274 node
->slots
[offset
] = slot
;
280 /* Go a level down */
281 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
283 slot
= node
->slots
[offset
];
284 shift
-= RADIX_TREE_MAP_SHIFT
;
293 node
->slots
[offset
] = item
;
294 BUG_ON(tag_get(node
, 0, offset
));
295 BUG_ON(tag_get(node
, 1, offset
));
298 BUG_ON(root_tag_get(root
, 0));
299 BUG_ON(root_tag_get(root
, 1));
305 static inline void **__lookup_slot(struct radix_tree_root
*root
,
308 unsigned int height
, shift
;
309 struct radix_tree_node
**slot
;
311 height
= root
->height
;
313 if (index
> radix_tree_maxindex(height
))
316 if (height
== 0 && root
->rnode
)
317 return (void *)&root
->rnode
;
319 shift
= (height
-1) * RADIX_TREE_MAP_SHIFT
;
326 slot
= (struct radix_tree_node
**)
328 ((index
>> shift
) & RADIX_TREE_MAP_MASK
));
329 shift
-= RADIX_TREE_MAP_SHIFT
;
333 return (void **)slot
;
337 * radix_tree_lookup_slot - lookup a slot in a radix tree
338 * @root: radix tree root
341 * Lookup the slot corresponding to the position @index in the radix tree
342 * @root. This is useful for update-if-exists operations.
344 void **radix_tree_lookup_slot(struct radix_tree_root
*root
, unsigned long index
)
346 return __lookup_slot(root
, index
);
350 * radix_tree_lookup - perform lookup operation on a radix tree
351 * @root: radix tree root
354 * Lookup the item at the position @index in the radix tree @root.
356 void *radix_tree_lookup(struct radix_tree_root
*root
, unsigned long index
)
360 slot
= __lookup_slot(root
, index
);
361 return slot
!= NULL
? *slot
: NULL
;
365 * radix_tree_tag_set - set a tag on a radix tree node
366 * @root: radix tree root
370 * Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
371 * corresponding to @index in the radix tree. From
372 * the root all the way down to the leaf node.
374 * Returns the address of the tagged item. Setting a tag on a not-present
377 void *radix_tree_tag_set(struct radix_tree_root
*root
,
378 unsigned long index
, unsigned int tag
)
380 unsigned int height
, shift
;
381 struct radix_tree_node
*slot
;
383 height
= root
->height
;
384 BUG_ON(index
> radix_tree_maxindex(height
));
387 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
392 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
393 if (!tag_get(slot
, tag
, offset
))
394 tag_set(slot
, tag
, offset
);
395 slot
= slot
->slots
[offset
];
396 BUG_ON(slot
== NULL
);
397 shift
-= RADIX_TREE_MAP_SHIFT
;
401 /* set the root's tag bit */
402 if (slot
&& !root_tag_get(root
, tag
))
403 root_tag_set(root
, tag
);
409 * radix_tree_tag_clear - clear a tag on a radix tree node
410 * @root: radix tree root
414 * Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
415 * corresponding to @index in the radix tree. If
416 * this causes the leaf node to have no tags set then clear the tag in the
417 * next-to-leaf node, etc.
419 * Returns the address of the tagged item on success, else NULL. ie:
420 * has the same return value and semantics as radix_tree_lookup().
422 void *radix_tree_tag_clear(struct radix_tree_root
*root
,
423 unsigned long index
, unsigned int tag
)
425 struct radix_tree_path path
[RADIX_TREE_MAX_PATH
], *pathp
= path
;
426 struct radix_tree_node
*slot
= NULL
;
427 unsigned int height
, shift
;
429 height
= root
->height
;
430 if (index
> radix_tree_maxindex(height
))
433 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
443 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
444 pathp
[1].offset
= offset
;
445 pathp
[1].node
= slot
;
446 slot
= slot
->slots
[offset
];
448 shift
-= RADIX_TREE_MAP_SHIFT
;
455 while (pathp
->node
) {
456 if (!tag_get(pathp
->node
, tag
, pathp
->offset
))
458 tag_clear(pathp
->node
, tag
, pathp
->offset
);
459 if (any_tag_set(pathp
->node
, tag
))
464 /* clear the root's tag bit */
465 if (root_tag_get(root
, tag
))
466 root_tag_clear(root
, tag
);
472 #ifndef __KERNEL__ /* Only the test harness uses this at present */
474 * radix_tree_tag_get - get a tag on a radix tree node
475 * @root: radix tree root
477 * @tag: tag index (< RADIX_TREE_MAX_TAGS)
481 * 0: tag not present or not set
484 int radix_tree_tag_get(struct radix_tree_root
*root
,
485 unsigned long index
, unsigned int tag
)
487 unsigned int height
, shift
;
488 struct radix_tree_node
*slot
;
489 int saw_unset_tag
= 0;
491 height
= root
->height
;
492 if (index
> radix_tree_maxindex(height
))
495 /* check the root's tag bit */
496 if (!root_tag_get(root
, tag
))
502 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
511 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
514 * This is just a debug check. Later, we can bale as soon as
515 * we see an unset tag.
517 if (!tag_get(slot
, tag
, offset
))
520 int ret
= tag_get(slot
, tag
, offset
);
522 BUG_ON(ret
&& saw_unset_tag
);
525 slot
= slot
->slots
[offset
];
526 shift
-= RADIX_TREE_MAP_SHIFT
;
533 __lookup(struct radix_tree_root
*root
, void **results
, unsigned long index
,
534 unsigned int max_items
, unsigned long *next_index
)
536 unsigned int nr_found
= 0;
537 unsigned int shift
, height
;
538 struct radix_tree_node
*slot
;
541 height
= root
->height
;
543 if (root
->rnode
&& index
== 0)
544 results
[nr_found
++] = root
->rnode
;
548 shift
= (height
-1) * RADIX_TREE_MAP_SHIFT
;
551 for ( ; height
> 1; height
--) {
553 for (i
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
554 i
< RADIX_TREE_MAP_SIZE
; i
++) {
555 if (slot
->slots
[i
] != NULL
)
557 index
&= ~((1UL << shift
) - 1);
558 index
+= 1UL << shift
;
560 goto out
; /* 32-bit wraparound */
562 if (i
== RADIX_TREE_MAP_SIZE
)
565 shift
-= RADIX_TREE_MAP_SHIFT
;
566 slot
= slot
->slots
[i
];
569 /* Bottom level: grab some items */
570 for (i
= index
& RADIX_TREE_MAP_MASK
; i
< RADIX_TREE_MAP_SIZE
; i
++) {
572 if (slot
->slots
[i
]) {
573 results
[nr_found
++] = slot
->slots
[i
];
574 if (nr_found
== max_items
)
584 * radix_tree_gang_lookup - perform multiple lookup on a radix tree
585 * @root: radix tree root
586 * @results: where the results of the lookup are placed
587 * @first_index: start the lookup from this key
588 * @max_items: place up to this many items at *results
590 * Performs an index-ascending scan of the tree for present items. Places
591 * them at *@results and returns the number of items which were placed at
594 * The implementation is naive.
597 radix_tree_gang_lookup(struct radix_tree_root
*root
, void **results
,
598 unsigned long first_index
, unsigned int max_items
)
600 const unsigned long max_index
= radix_tree_maxindex(root
->height
);
601 unsigned long cur_index
= first_index
;
602 unsigned int ret
= 0;
604 while (ret
< max_items
) {
605 unsigned int nr_found
;
606 unsigned long next_index
; /* Index of next search */
608 if (cur_index
> max_index
)
610 nr_found
= __lookup(root
, results
+ ret
, cur_index
,
611 max_items
- ret
, &next_index
);
615 cur_index
= next_index
;
621 * FIXME: the two tag_get()s here should use find_next_bit() instead of
622 * open-coding the search.
625 __lookup_tag(struct radix_tree_root
*root
, void **results
, unsigned long index
,
626 unsigned int max_items
, unsigned long *next_index
, unsigned int tag
)
628 unsigned int nr_found
= 0;
630 unsigned int height
= root
->height
;
631 struct radix_tree_node
*slot
;
634 if (root
->rnode
&& index
== 0)
635 results
[nr_found
++] = root
->rnode
;
639 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
643 unsigned long i
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
645 for ( ; i
< RADIX_TREE_MAP_SIZE
; i
++) {
646 if (tag_get(slot
, tag
, i
)) {
647 BUG_ON(slot
->slots
[i
] == NULL
);
650 index
&= ~((1UL << shift
) - 1);
651 index
+= 1UL << shift
;
653 goto out
; /* 32-bit wraparound */
655 if (i
== RADIX_TREE_MAP_SIZE
)
658 if (height
== 0) { /* Bottom level: grab some items */
659 unsigned long j
= index
& RADIX_TREE_MAP_MASK
;
661 for ( ; j
< RADIX_TREE_MAP_SIZE
; j
++) {
663 if (tag_get(slot
, tag
, j
)) {
664 BUG_ON(slot
->slots
[j
] == NULL
);
665 results
[nr_found
++] = slot
->slots
[j
];
666 if (nr_found
== max_items
)
671 shift
-= RADIX_TREE_MAP_SHIFT
;
672 slot
= slot
->slots
[i
];
673 } while (height
> 0);
680 * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
682 * @root: radix tree root
683 * @results: where the results of the lookup are placed
684 * @first_index: start the lookup from this key
685 * @max_items: place up to this many items at *results
686 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
688 * Performs an index-ascending scan of the tree for present items which
689 * have the tag indexed by @tag set. Places the items at *@results and
690 * returns the number of items which were placed at *@results.
693 radix_tree_gang_lookup_tag(struct radix_tree_root
*root
, void **results
,
694 unsigned long first_index
, unsigned int max_items
,
697 const unsigned long max_index
= radix_tree_maxindex(root
->height
);
698 unsigned long cur_index
= first_index
;
699 unsigned int ret
= 0;
701 /* check the root's tag bit */
702 if (!root_tag_get(root
, tag
))
705 while (ret
< max_items
) {
706 unsigned int nr_found
;
707 unsigned long next_index
; /* Index of next search */
709 if (cur_index
> max_index
)
711 nr_found
= __lookup_tag(root
, results
+ ret
, cur_index
,
712 max_items
- ret
, &next_index
, tag
);
716 cur_index
= next_index
;
722 * radix_tree_shrink - shrink height of a radix tree to minimal
723 * @root radix tree root
725 static inline void radix_tree_shrink(struct radix_tree_root
*root
)
727 /* try to shrink tree height */
728 while (root
->height
> 0 &&
729 root
->rnode
->count
== 1 &&
730 root
->rnode
->slots
[0]) {
731 struct radix_tree_node
*to_free
= root
->rnode
;
733 root
->rnode
= to_free
->slots
[0];
735 /* must only free zeroed nodes into the slab */
736 tag_clear(to_free
, 0, 0);
737 tag_clear(to_free
, 1, 0);
738 to_free
->slots
[0] = NULL
;
740 radix_tree_node_free(to_free
);
745 * radix_tree_delete - delete an item from a radix tree
746 * @root: radix tree root
749 * Remove the item at @index from the radix tree rooted at @root.
751 * Returns the address of the deleted item, or NULL if it was not present.
753 void *radix_tree_delete(struct radix_tree_root
*root
, unsigned long index
)
755 struct radix_tree_path path
[RADIX_TREE_MAX_PATH
], *pathp
= path
;
756 struct radix_tree_node
*slot
= NULL
;
757 unsigned int height
, shift
;
761 height
= root
->height
;
762 if (index
> radix_tree_maxindex(height
))
766 if (height
== 0 && root
->rnode
) {
767 root_tag_clear_all(root
);
772 shift
= (height
- 1) * RADIX_TREE_MAP_SHIFT
;
780 offset
= (index
>> shift
) & RADIX_TREE_MAP_MASK
;
781 pathp
->offset
= offset
;
783 slot
= slot
->slots
[offset
];
784 shift
-= RADIX_TREE_MAP_SHIFT
;
786 } while (height
> 0);
792 * Clear all tags associated with the just-deleted item
794 for (tag
= 0; tag
< RADIX_TREE_MAX_TAGS
; tag
++) {
795 if (tag_get(pathp
->node
, tag
, pathp
->offset
))
796 radix_tree_tag_clear(root
, index
, tag
);
799 /* Now free the nodes we do not need anymore */
800 while (pathp
->node
) {
801 pathp
->node
->slots
[pathp
->offset
] = NULL
;
802 pathp
->node
->count
--;
804 if (pathp
->node
->count
) {
805 if (pathp
->node
== root
->rnode
)
806 radix_tree_shrink(root
);
810 /* Node with zero slots in use so free it */
811 radix_tree_node_free(pathp
->node
);
815 root_tag_clear_all(root
);
824 * radix_tree_tagged - test whether any items in the tree are tagged
825 * @root: radix tree root
828 int radix_tree_tagged(struct radix_tree_root
*root
, unsigned int tag
)
830 return root_tag_get(root
, tag
);
833 static unsigned long __maxindex(unsigned int height
)
835 unsigned int tmp
= height
* RADIX_TREE_MAP_SHIFT
;
836 unsigned long index
= ~0UL;
838 if (tmp
< RADIX_TREE_INDEX_BITS
)
839 index
= (index
>> (RADIX_TREE_INDEX_BITS
- tmp
- 1)) >> 1;
843 static void radix_tree_init_maxindex(void)
847 for (i
= 0; i
< ARRAY_SIZE(height_to_maxindex
); i
++)
848 height_to_maxindex
[i
] = __maxindex(i
);
851 void radix_tree_init(void)
853 radix_tree_init_maxindex();