blob: 7ea2e033d7153ad23de9dc02c0c0786abc1e11e2 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
2 * Copyright (C) 2001 Momchil Velikov
3 * Portions Copyright (C) 2001 Christoph Hellwig
Christoph Lametercde53532008-07-04 09:59:22 -07004 * Copyright (C) 2005 SGI, Christoph Lameter
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08005 * Copyright (C) 2006 Nick Piggin
Linus Torvalds1da177e2005-04-16 15:20:36 -07006 *
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.
11 *
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.
16 *
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.
20 */
21
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>
Linus Torvalds1da177e2005-04-16 15:20:36 -070031#include <linux/string.h>
32#include <linux/bitops.h>
Nick Piggin7cf9c2c2006-12-06 20:33:44 -080033#include <linux/rcupdate.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070034
35
36#ifdef __KERNEL__
Nick Piggincfd9b7d2006-06-23 02:03:22 -070037#define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6)
Linus Torvalds1da177e2005-04-16 15:20:36 -070038#else
39#define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */
40#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -070041
42#define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT)
43#define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1)
44
45#define RADIX_TREE_TAG_LONGS \
46 ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
47
48struct radix_tree_node {
Nick Piggin7cf9c2c2006-12-06 20:33:44 -080049 unsigned int height; /* Height from the bottom */
Linus Torvalds1da177e2005-04-16 15:20:36 -070050 unsigned int count;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -080051 struct rcu_head rcu_head;
Arnd Bergmanna1115572010-02-25 23:43:52 +010052 void __rcu *slots[RADIX_TREE_MAP_SIZE];
Jonathan Corbetdaff89f2006-03-25 03:08:05 -080053 unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
Linus Torvalds1da177e2005-04-16 15:20:36 -070054};
55
56struct radix_tree_path {
Christoph Lameter201b6262005-09-06 15:16:46 -070057 struct radix_tree_node *node;
Linus Torvalds1da177e2005-04-16 15:20:36 -070058 int offset;
59};
60
61#define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
Jeff Moyer26fb1582007-10-16 01:24:49 -070062#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
63 RADIX_TREE_MAP_SHIFT))
Linus Torvalds1da177e2005-04-16 15:20:36 -070064
Jeff Moyer26fb1582007-10-16 01:24:49 -070065/*
66 * The height_to_maxindex array needs to be one deeper than the maximum
67 * path as height 0 holds only 1 entry.
68 */
69static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly;
Linus Torvalds1da177e2005-04-16 15:20:36 -070070
71/*
72 * Radix tree node cache.
73 */
Christoph Lametere18b8902006-12-06 20:33:20 -080074static struct kmem_cache *radix_tree_node_cachep;
Linus Torvalds1da177e2005-04-16 15:20:36 -070075
76/*
77 * Per-cpu pool of preloaded nodes
78 */
79struct radix_tree_preload {
80 int nr;
81 struct radix_tree_node *nodes[RADIX_TREE_MAX_PATH];
82};
Harvey Harrison8cef7d52009-01-06 14:40:50 -080083static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
Linus Torvalds1da177e2005-04-16 15:20:36 -070084
Nick Piggin27d20fd2010-11-11 14:05:19 -080085static inline void *ptr_to_indirect(void *ptr)
86{
87 return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR);
88}
89
90static inline void *indirect_to_ptr(void *ptr)
91{
92 return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR);
93}
94
Nick Piggin612d6c12006-06-23 02:03:22 -070095static inline gfp_t root_gfp_mask(struct radix_tree_root *root)
96{
97 return root->gfp_mask & __GFP_BITS_MASK;
98}
99
Nick Piggin643b52b2008-06-12 15:21:52 -0700100static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
101 int offset)
102{
103 __set_bit(offset, node->tags[tag]);
104}
105
106static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,
107 int offset)
108{
109 __clear_bit(offset, node->tags[tag]);
110}
111
112static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
113 int offset)
114{
115 return test_bit(offset, node->tags[tag]);
116}
117
118static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag)
119{
120 root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT));
121}
122
123static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag)
124{
125 root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT));
126}
127
128static inline void root_tag_clear_all(struct radix_tree_root *root)
129{
130 root->gfp_mask &= __GFP_BITS_MASK;
131}
132
133static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
134{
135 return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
136}
137
138/*
139 * Returns 1 if any slot in the node has this tag set.
140 * Otherwise returns 0.
141 */
142static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
143{
144 int idx;
145 for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
146 if (node->tags[tag][idx])
147 return 1;
148 }
149 return 0;
150}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700151/*
152 * This assumes that the caller has performed appropriate preallocation, and
153 * that the caller has pinned this thread of control to the current CPU.
154 */
155static struct radix_tree_node *
156radix_tree_node_alloc(struct radix_tree_root *root)
157{
Nick Piggine2848a02008-02-04 22:29:10 -0800158 struct radix_tree_node *ret = NULL;
Nick Piggin612d6c12006-06-23 02:03:22 -0700159 gfp_t gfp_mask = root_gfp_mask(root);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700160
Nick Piggine2848a02008-02-04 22:29:10 -0800161 if (!(gfp_mask & __GFP_WAIT)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700162 struct radix_tree_preload *rtp;
163
Nick Piggine2848a02008-02-04 22:29:10 -0800164 /*
165 * Provided the caller has preloaded here, we will always
166 * succeed in getting a node here (and never reach
167 * kmem_cache_alloc)
168 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700169 rtp = &__get_cpu_var(radix_tree_preloads);
170 if (rtp->nr) {
171 ret = rtp->nodes[rtp->nr - 1];
172 rtp->nodes[rtp->nr - 1] = NULL;
173 rtp->nr--;
174 }
175 }
Nick Piggine2848a02008-02-04 22:29:10 -0800176 if (ret == NULL)
Christoph Lameter488514d2008-04-28 02:12:05 -0700177 ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
Nick Piggine2848a02008-02-04 22:29:10 -0800178
Nick Pigginc0bc9872007-10-16 01:24:42 -0700179 BUG_ON(radix_tree_is_indirect_ptr(ret));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700180 return ret;
181}
182
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800183static void radix_tree_node_rcu_free(struct rcu_head *head)
184{
185 struct radix_tree_node *node =
186 container_of(head, struct radix_tree_node, rcu_head);
Dave Chinnerb6dd0862010-08-23 10:33:19 +1000187 int i;
Nick Piggin643b52b2008-06-12 15:21:52 -0700188
189 /*
190 * must only free zeroed nodes into the slab. radix_tree_shrink
191 * can leave us with a non-NULL entry in the first slot, so clear
192 * that here to make sure.
193 */
Dave Chinnerb6dd0862010-08-23 10:33:19 +1000194 for (i = 0; i < RADIX_TREE_MAX_TAGS; i++)
195 tag_clear(node, i, 0);
196
Nick Piggin643b52b2008-06-12 15:21:52 -0700197 node->slots[0] = NULL;
198 node->count = 0;
199
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800200 kmem_cache_free(radix_tree_node_cachep, node);
201}
202
Linus Torvalds1da177e2005-04-16 15:20:36 -0700203static inline void
204radix_tree_node_free(struct radix_tree_node *node)
205{
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800206 call_rcu(&node->rcu_head, radix_tree_node_rcu_free);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700207}
208
209/*
210 * Load up this CPU's radix_tree_node buffer with sufficient objects to
211 * ensure that the addition of a single element in the tree cannot fail. On
212 * success, return zero, with preemption disabled. On error, return -ENOMEM
213 * with preemption not disabled.
David Howellsb34df792009-11-19 18:11:14 +0000214 *
215 * To make use of this facility, the radix tree must be initialised without
216 * __GFP_WAIT being passed to INIT_RADIX_TREE().
Linus Torvalds1da177e2005-04-16 15:20:36 -0700217 */
Al Virodd0fc662005-10-07 07:46:04 +0100218int radix_tree_preload(gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700219{
220 struct radix_tree_preload *rtp;
221 struct radix_tree_node *node;
222 int ret = -ENOMEM;
223
224 preempt_disable();
225 rtp = &__get_cpu_var(radix_tree_preloads);
226 while (rtp->nr < ARRAY_SIZE(rtp->nodes)) {
227 preempt_enable();
Christoph Lameter488514d2008-04-28 02:12:05 -0700228 node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700229 if (node == NULL)
230 goto out;
231 preempt_disable();
232 rtp = &__get_cpu_var(radix_tree_preloads);
233 if (rtp->nr < ARRAY_SIZE(rtp->nodes))
234 rtp->nodes[rtp->nr++] = node;
235 else
236 kmem_cache_free(radix_tree_node_cachep, node);
237 }
238 ret = 0;
239out:
240 return ret;
241}
David Chinnerd7f09232007-07-14 16:05:04 +1000242EXPORT_SYMBOL(radix_tree_preload);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700243
Nick Piggin6e954b92006-01-08 01:01:40 -0800244/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700245 * Return the maximum key which can be store into a
246 * radix tree with height HEIGHT.
247 */
248static inline unsigned long radix_tree_maxindex(unsigned int height)
249{
250 return height_to_maxindex[height];
251}
252
253/*
254 * Extend a radix tree so it can store key @index.
255 */
256static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
257{
258 struct radix_tree_node *node;
259 unsigned int height;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700260 int tag;
261
262 /* Figure out what the height should be. */
263 height = root->height + 1;
264 while (index > radix_tree_maxindex(height))
265 height++;
266
267 if (root->rnode == NULL) {
268 root->height = height;
269 goto out;
270 }
271
Linus Torvalds1da177e2005-04-16 15:20:36 -0700272 do {
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800273 unsigned int newheight;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700274 if (!(node = radix_tree_node_alloc(root)))
275 return -ENOMEM;
276
277 /* Increase the height. */
Nick Piggin27d20fd2010-11-11 14:05:19 -0800278 node->slots[0] = indirect_to_ptr(root->rnode);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700279
280 /* Propagate the aggregated tag info into the new root */
Jonathan Corbetdaff89f2006-03-25 03:08:05 -0800281 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
Nick Piggin612d6c12006-06-23 02:03:22 -0700282 if (root_tag_get(root, tag))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700283 tag_set(node, tag, 0);
284 }
285
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800286 newheight = root->height+1;
287 node->height = newheight;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700288 node->count = 1;
Nick Piggin27d20fd2010-11-11 14:05:19 -0800289 node = ptr_to_indirect(node);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800290 rcu_assign_pointer(root->rnode, node);
291 root->height = newheight;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700292 } while (height > root->height);
293out:
294 return 0;
295}
296
297/**
298 * radix_tree_insert - insert into a radix tree
299 * @root: radix tree root
300 * @index: index key
301 * @item: item to insert
302 *
303 * Insert an item into the radix tree at position @index.
304 */
305int radix_tree_insert(struct radix_tree_root *root,
306 unsigned long index, void *item)
307{
Christoph Lameter201b6262005-09-06 15:16:46 -0700308 struct radix_tree_node *node = NULL, *slot;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700309 unsigned int height, shift;
310 int offset;
311 int error;
312
Nick Pigginc0bc9872007-10-16 01:24:42 -0700313 BUG_ON(radix_tree_is_indirect_ptr(item));
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800314
Linus Torvalds1da177e2005-04-16 15:20:36 -0700315 /* Make sure the tree is high enough. */
Nick Piggin612d6c12006-06-23 02:03:22 -0700316 if (index > radix_tree_maxindex(root->height)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700317 error = radix_tree_extend(root, index);
318 if (error)
319 return error;
320 }
321
Nick Piggin27d20fd2010-11-11 14:05:19 -0800322 slot = indirect_to_ptr(root->rnode);
Nick Pigginc0bc9872007-10-16 01:24:42 -0700323
Linus Torvalds1da177e2005-04-16 15:20:36 -0700324 height = root->height;
325 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
326
327 offset = 0; /* uninitialised var warning */
Nick Piggin612d6c12006-06-23 02:03:22 -0700328 while (height > 0) {
Christoph Lameter201b6262005-09-06 15:16:46 -0700329 if (slot == NULL) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700330 /* Have to add a child node. */
Christoph Lameter201b6262005-09-06 15:16:46 -0700331 if (!(slot = radix_tree_node_alloc(root)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700332 return -ENOMEM;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800333 slot->height = height;
Christoph Lameter201b6262005-09-06 15:16:46 -0700334 if (node) {
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800335 rcu_assign_pointer(node->slots[offset], slot);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700336 node->count++;
Christoph Lameter201b6262005-09-06 15:16:46 -0700337 } else
Nick Piggin27d20fd2010-11-11 14:05:19 -0800338 rcu_assign_pointer(root->rnode, ptr_to_indirect(slot));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700339 }
340
341 /* Go a level down */
342 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
Christoph Lameter201b6262005-09-06 15:16:46 -0700343 node = slot;
344 slot = node->slots[offset];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700345 shift -= RADIX_TREE_MAP_SHIFT;
346 height--;
Nick Piggin612d6c12006-06-23 02:03:22 -0700347 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700348
Christoph Lameter201b6262005-09-06 15:16:46 -0700349 if (slot != NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700350 return -EEXIST;
Christoph Lameter201b6262005-09-06 15:16:46 -0700351
Nick Piggin612d6c12006-06-23 02:03:22 -0700352 if (node) {
353 node->count++;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800354 rcu_assign_pointer(node->slots[offset], item);
Nick Piggin612d6c12006-06-23 02:03:22 -0700355 BUG_ON(tag_get(node, 0, offset));
356 BUG_ON(tag_get(node, 1, offset));
357 } else {
Nick Pigginc0bc9872007-10-16 01:24:42 -0700358 rcu_assign_pointer(root->rnode, item);
Nick Piggin612d6c12006-06-23 02:03:22 -0700359 BUG_ON(root_tag_get(root, 0));
360 BUG_ON(root_tag_get(root, 1));
361 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700362
Linus Torvalds1da177e2005-04-16 15:20:36 -0700363 return 0;
364}
365EXPORT_SYMBOL(radix_tree_insert);
366
Huang Shijieb72b71c2009-06-16 15:33:42 -0700367/*
368 * is_slot == 1 : search for the slot.
369 * is_slot == 0 : search for the node.
Hans Reisera4331362005-11-07 00:59:29 -0800370 */
Huang Shijieb72b71c2009-06-16 15:33:42 -0700371static void *radix_tree_lookup_element(struct radix_tree_root *root,
372 unsigned long index, int is_slot)
Hans Reisera4331362005-11-07 00:59:29 -0800373{
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800374 unsigned int height, shift;
375 struct radix_tree_node *node, **slot;
376
Paul E. McKenney2676a582010-02-22 17:04:54 -0800377 node = rcu_dereference_raw(root->rnode);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800378 if (node == NULL)
379 return NULL;
380
Nick Pigginc0bc9872007-10-16 01:24:42 -0700381 if (!radix_tree_is_indirect_ptr(node)) {
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800382 if (index > 0)
383 return NULL;
Huang Shijieb72b71c2009-06-16 15:33:42 -0700384 return is_slot ? (void *)&root->rnode : node;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800385 }
Nick Piggin27d20fd2010-11-11 14:05:19 -0800386 node = indirect_to_ptr(node);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800387
388 height = node->height;
389 if (index > radix_tree_maxindex(height))
390 return NULL;
391
392 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
393
394 do {
395 slot = (struct radix_tree_node **)
396 (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
Paul E. McKenney2676a582010-02-22 17:04:54 -0800397 node = rcu_dereference_raw(*slot);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800398 if (node == NULL)
399 return NULL;
400
401 shift -= RADIX_TREE_MAP_SHIFT;
402 height--;
403 } while (height > 0);
404
Nick Piggin27d20fd2010-11-11 14:05:19 -0800405 return is_slot ? (void *)slot : indirect_to_ptr(node);
Huang Shijieb72b71c2009-06-16 15:33:42 -0700406}
407
408/**
409 * radix_tree_lookup_slot - lookup a slot in a radix tree
410 * @root: radix tree root
411 * @index: index key
412 *
413 * Returns: the slot corresponding to the position @index in the
414 * radix tree @root. This is useful for update-if-exists operations.
415 *
416 * This function can be called under rcu_read_lock iff the slot is not
417 * modified by radix_tree_replace_slot, otherwise it must be called
418 * exclusive from other writers. Any dereference of the slot must be done
419 * using radix_tree_deref_slot.
420 */
421void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
422{
423 return (void **)radix_tree_lookup_element(root, index, 1);
Hans Reisera4331362005-11-07 00:59:29 -0800424}
425EXPORT_SYMBOL(radix_tree_lookup_slot);
426
Linus Torvalds1da177e2005-04-16 15:20:36 -0700427/**
428 * radix_tree_lookup - perform lookup operation on a radix tree
429 * @root: radix tree root
430 * @index: index key
431 *
432 * Lookup the item at the position @index in the radix tree @root.
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800433 *
434 * This function can be called under rcu_read_lock, however the caller
435 * must manage lifetimes of leaf nodes (eg. RCU may also be used to free
436 * them safely). No RCU barriers are required to access or modify the
437 * returned item, however.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700438 */
439void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
440{
Huang Shijieb72b71c2009-06-16 15:33:42 -0700441 return radix_tree_lookup_element(root, index, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700442}
443EXPORT_SYMBOL(radix_tree_lookup);
444
445/**
446 * radix_tree_tag_set - set a tag on a radix tree node
447 * @root: radix tree root
448 * @index: index key
449 * @tag: tag index
450 *
Jonathan Corbetdaff89f2006-03-25 03:08:05 -0800451 * Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
452 * corresponding to @index in the radix tree. From
Linus Torvalds1da177e2005-04-16 15:20:36 -0700453 * the root all the way down to the leaf node.
454 *
455 * Returns the address of the tagged item. Setting a tag on a not-present
456 * item is a bug.
457 */
458void *radix_tree_tag_set(struct radix_tree_root *root,
Jonathan Corbetdaff89f2006-03-25 03:08:05 -0800459 unsigned long index, unsigned int tag)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700460{
461 unsigned int height, shift;
Christoph Lameter201b6262005-09-06 15:16:46 -0700462 struct radix_tree_node *slot;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700463
464 height = root->height;
Peter Zijlstra4c91c362006-06-23 02:03:25 -0700465 BUG_ON(index > radix_tree_maxindex(height));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700466
Nick Piggin27d20fd2010-11-11 14:05:19 -0800467 slot = indirect_to_ptr(root->rnode);
Nick Piggin612d6c12006-06-23 02:03:22 -0700468 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700469
470 while (height > 0) {
471 int offset;
472
473 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
Nick Piggind5274262006-01-08 01:01:41 -0800474 if (!tag_get(slot, tag, offset))
475 tag_set(slot, tag, offset);
Christoph Lameter201b6262005-09-06 15:16:46 -0700476 slot = slot->slots[offset];
477 BUG_ON(slot == NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700478 shift -= RADIX_TREE_MAP_SHIFT;
479 height--;
480 }
481
Nick Piggin612d6c12006-06-23 02:03:22 -0700482 /* set the root's tag bit */
483 if (slot && !root_tag_get(root, tag))
484 root_tag_set(root, tag);
485
Christoph Lameter201b6262005-09-06 15:16:46 -0700486 return slot;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700487}
488EXPORT_SYMBOL(radix_tree_tag_set);
489
490/**
491 * radix_tree_tag_clear - clear a tag on a radix tree node
492 * @root: radix tree root
493 * @index: index key
494 * @tag: tag index
495 *
Jonathan Corbetdaff89f2006-03-25 03:08:05 -0800496 * Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
497 * corresponding to @index in the radix tree. If
Linus Torvalds1da177e2005-04-16 15:20:36 -0700498 * this causes the leaf node to have no tags set then clear the tag in the
499 * next-to-leaf node, etc.
500 *
501 * Returns the address of the tagged item on success, else NULL. ie:
502 * has the same return value and semantics as radix_tree_lookup().
503 */
504void *radix_tree_tag_clear(struct radix_tree_root *root,
Jonathan Corbetdaff89f2006-03-25 03:08:05 -0800505 unsigned long index, unsigned int tag)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700506{
Jeff Moyer26fb1582007-10-16 01:24:49 -0700507 /*
508 * The radix tree path needs to be one longer than the maximum path
509 * since the "list" is null terminated.
510 */
511 struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
Nick Piggin612d6c12006-06-23 02:03:22 -0700512 struct radix_tree_node *slot = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700513 unsigned int height, shift;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700514
515 height = root->height;
516 if (index > radix_tree_maxindex(height))
517 goto out;
518
519 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
520 pathp->node = NULL;
Nick Piggin27d20fd2010-11-11 14:05:19 -0800521 slot = indirect_to_ptr(root->rnode);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700522
523 while (height > 0) {
524 int offset;
525
Christoph Lameter201b6262005-09-06 15:16:46 -0700526 if (slot == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700527 goto out;
528
529 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
530 pathp[1].offset = offset;
Christoph Lameter201b6262005-09-06 15:16:46 -0700531 pathp[1].node = slot;
532 slot = slot->slots[offset];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700533 pathp++;
534 shift -= RADIX_TREE_MAP_SHIFT;
535 height--;
536 }
537
Nick Piggin612d6c12006-06-23 02:03:22 -0700538 if (slot == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700539 goto out;
540
Nick Piggin612d6c12006-06-23 02:03:22 -0700541 while (pathp->node) {
Nick Piggind5274262006-01-08 01:01:41 -0800542 if (!tag_get(pathp->node, tag, pathp->offset))
543 goto out;
Christoph Lameter201b6262005-09-06 15:16:46 -0700544 tag_clear(pathp->node, tag, pathp->offset);
Nick Piggin6e954b92006-01-08 01:01:40 -0800545 if (any_tag_set(pathp->node, tag))
546 goto out;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700547 pathp--;
Nick Piggin612d6c12006-06-23 02:03:22 -0700548 }
549
550 /* clear the root's tag bit */
551 if (root_tag_get(root, tag))
552 root_tag_clear(root, tag);
553
Linus Torvalds1da177e2005-04-16 15:20:36 -0700554out:
Nick Piggin612d6c12006-06-23 02:03:22 -0700555 return slot;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700556}
557EXPORT_SYMBOL(radix_tree_tag_clear);
558
Linus Torvalds1da177e2005-04-16 15:20:36 -0700559/**
Marcelo Tosatti32605a12005-09-06 15:16:48 -0700560 * radix_tree_tag_get - get a tag on a radix tree node
561 * @root: radix tree root
562 * @index: index key
Jonathan Corbetdaff89f2006-03-25 03:08:05 -0800563 * @tag: tag index (< RADIX_TREE_MAX_TAGS)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700564 *
Marcelo Tosatti32605a12005-09-06 15:16:48 -0700565 * Return values:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700566 *
Nick Piggin612d6c12006-06-23 02:03:22 -0700567 * 0: tag not present or not set
568 * 1: tag set
David Howellsce826532010-04-06 22:36:20 +0100569 *
570 * Note that the return value of this function may not be relied on, even if
571 * the RCU lock is held, unless tag modification and node deletion are excluded
572 * from concurrency.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700573 */
574int radix_tree_tag_get(struct radix_tree_root *root,
Jonathan Corbetdaff89f2006-03-25 03:08:05 -0800575 unsigned long index, unsigned int tag)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700576{
577 unsigned int height, shift;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800578 struct radix_tree_node *node;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700579 int saw_unset_tag = 0;
580
Nick Piggin612d6c12006-06-23 02:03:22 -0700581 /* check the root's tag bit */
582 if (!root_tag_get(root, tag))
583 return 0;
584
Paul E. McKenney2676a582010-02-22 17:04:54 -0800585 node = rcu_dereference_raw(root->rnode);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800586 if (node == NULL)
587 return 0;
588
Nick Pigginc0bc9872007-10-16 01:24:42 -0700589 if (!radix_tree_is_indirect_ptr(node))
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800590 return (index == 0);
Nick Piggin27d20fd2010-11-11 14:05:19 -0800591 node = indirect_to_ptr(node);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800592
593 height = node->height;
594 if (index > radix_tree_maxindex(height))
595 return 0;
Nick Piggin612d6c12006-06-23 02:03:22 -0700596
Linus Torvalds1da177e2005-04-16 15:20:36 -0700597 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700598
599 for ( ; ; ) {
600 int offset;
601
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800602 if (node == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700603 return 0;
604
605 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
606
607 /*
608 * This is just a debug check. Later, we can bale as soon as
609 * we see an unset tag.
610 */
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800611 if (!tag_get(node, tag, offset))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700612 saw_unset_tag = 1;
David Howellsce826532010-04-06 22:36:20 +0100613 if (height == 1)
614 return !!tag_get(node, tag, offset);
Paul E. McKenney2676a582010-02-22 17:04:54 -0800615 node = rcu_dereference_raw(node->slots[offset]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700616 shift -= RADIX_TREE_MAP_SHIFT;
617 height--;
618 }
619}
620EXPORT_SYMBOL(radix_tree_tag_get);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700621
Fengguang Wu6df8ba42007-10-16 01:24:33 -0700622/**
Jan Karaebf8aa42010-08-09 17:19:11 -0700623 * radix_tree_range_tag_if_tagged - for each item in given range set given
624 * tag if item has another tag set
625 * @root: radix tree root
626 * @first_indexp: pointer to a starting index of a range to scan
627 * @last_index: last index of a range to scan
628 * @nr_to_tag: maximum number items to tag
629 * @iftag: tag index to test
630 * @settag: tag index to set if tested tag is set
631 *
632 * This function scans range of radix tree from first_index to last_index
633 * (inclusive). For each item in the range if iftag is set, the function sets
634 * also settag. The function stops either after tagging nr_to_tag items or
635 * after reaching last_index.
636 *
Dave Chinner144dcfc2010-08-23 10:33:53 +1000637 * The tags must be set from the leaf level only and propagated back up the
638 * path to the root. We must do this so that we resolve the full path before
639 * setting any tags on intermediate nodes. If we set tags as we descend, then
640 * we can get to the leaf node and find that the index that has the iftag
641 * set is outside the range we are scanning. This reults in dangling tags and
642 * can lead to problems with later tag operations (e.g. livelocks on lookups).
643 *
Jan Karaebf8aa42010-08-09 17:19:11 -0700644 * The function returns number of leaves where the tag was set and sets
645 * *first_indexp to the first unscanned index.
Jan Karad5ed3a42010-08-19 14:13:33 -0700646 * WARNING! *first_indexp can wrap if last_index is ULONG_MAX. Caller must
647 * be prepared to handle that.
Jan Karaebf8aa42010-08-09 17:19:11 -0700648 */
649unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
650 unsigned long *first_indexp, unsigned long last_index,
651 unsigned long nr_to_tag,
652 unsigned int iftag, unsigned int settag)
653{
Dave Chinner144dcfc2010-08-23 10:33:53 +1000654 unsigned int height = root->height;
655 struct radix_tree_path path[height];
656 struct radix_tree_path *pathp = path;
657 struct radix_tree_node *slot;
658 unsigned int shift;
659 unsigned long tagged = 0;
660 unsigned long index = *first_indexp;
Jan Karaebf8aa42010-08-09 17:19:11 -0700661
662 last_index = min(last_index, radix_tree_maxindex(height));
663 if (index > last_index)
664 return 0;
665 if (!nr_to_tag)
666 return 0;
667 if (!root_tag_get(root, iftag)) {
668 *first_indexp = last_index + 1;
669 return 0;
670 }
671 if (height == 0) {
672 *first_indexp = last_index + 1;
673 root_tag_set(root, settag);
674 return 1;
675 }
676
677 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
Nick Piggin27d20fd2010-11-11 14:05:19 -0800678 slot = indirect_to_ptr(root->rnode);
Jan Karaebf8aa42010-08-09 17:19:11 -0700679
Dave Chinner144dcfc2010-08-23 10:33:53 +1000680 /*
681 * we fill the path from (root->height - 2) to 0, leaving the index at
682 * (root->height - 1) as a terminator. Zero the node in the terminator
683 * so that we can use this to end walk loops back up the path.
684 */
685 path[height - 1].node = NULL;
686
Jan Karaebf8aa42010-08-09 17:19:11 -0700687 for (;;) {
688 int offset;
689
690 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
691 if (!slot->slots[offset])
692 goto next;
693 if (!tag_get(slot, iftag, offset))
694 goto next;
Dave Chinner144dcfc2010-08-23 10:33:53 +1000695 if (height > 1) {
696 /* Go down one level */
697 height--;
698 shift -= RADIX_TREE_MAP_SHIFT;
699 path[height - 1].node = slot;
700 path[height - 1].offset = offset;
701 slot = slot->slots[offset];
702 continue;
Jan Karaebf8aa42010-08-09 17:19:11 -0700703 }
Dave Chinner144dcfc2010-08-23 10:33:53 +1000704
705 /* tag the leaf */
706 tagged++;
707 tag_set(slot, settag, offset);
708
709 /* walk back up the path tagging interior nodes */
710 pathp = &path[0];
711 while (pathp->node) {
712 /* stop if we find a node with the tag already set */
713 if (tag_get(pathp->node, settag, pathp->offset))
714 break;
715 tag_set(pathp->node, settag, pathp->offset);
716 pathp++;
717 }
718
Jan Karaebf8aa42010-08-09 17:19:11 -0700719next:
720 /* Go to next item at level determined by 'shift' */
721 index = ((index >> shift) + 1) << shift;
Jan Karad5ed3a42010-08-19 14:13:33 -0700722 /* Overflow can happen when last_index is ~0UL... */
723 if (index > last_index || !index)
Jan Karaebf8aa42010-08-09 17:19:11 -0700724 break;
725 if (tagged >= nr_to_tag)
726 break;
727 while (((index >> shift) & RADIX_TREE_MAP_MASK) == 0) {
728 /*
729 * We've fully scanned this node. Go up. Because
730 * last_index is guaranteed to be in the tree, what
731 * we do below cannot wander astray.
732 */
Dave Chinner144dcfc2010-08-23 10:33:53 +1000733 slot = path[height - 1].node;
Jan Karaebf8aa42010-08-09 17:19:11 -0700734 height++;
735 shift += RADIX_TREE_MAP_SHIFT;
736 }
737 }
738 /*
Toshiyuki Okajimaac15ee62011-01-25 15:07:32 -0800739 * We need not to tag the root tag if there is no tag which is set with
740 * settag within the range from *first_indexp to last_index.
Jan Karaebf8aa42010-08-09 17:19:11 -0700741 */
Toshiyuki Okajimaac15ee62011-01-25 15:07:32 -0800742 if (tagged > 0)
743 root_tag_set(root, settag);
Jan Karaebf8aa42010-08-09 17:19:11 -0700744 *first_indexp = index;
745
746 return tagged;
747}
748EXPORT_SYMBOL(radix_tree_range_tag_if_tagged);
749
750
751/**
Fengguang Wu6df8ba42007-10-16 01:24:33 -0700752 * radix_tree_next_hole - find the next hole (not-present entry)
753 * @root: tree root
754 * @index: index key
755 * @max_scan: maximum range to search
756 *
757 * Search the set [index, min(index+max_scan-1, MAX_INDEX)] for the lowest
758 * indexed hole.
759 *
760 * Returns: the index of the hole if found, otherwise returns an index
761 * outside of the set specified (in which case 'return - index >= max_scan'
Wu Fengguang8e6bdb72008-11-27 11:42:22 +0100762 * will be true). In rare cases of index wrap-around, 0 will be returned.
Fengguang Wu6df8ba42007-10-16 01:24:33 -0700763 *
764 * radix_tree_next_hole may be called under rcu_read_lock. However, like
Wu Fengguang8e6bdb72008-11-27 11:42:22 +0100765 * radix_tree_gang_lookup, this will not atomically search a snapshot of
766 * the tree at a single point in time. For example, if a hole is created
767 * at index 5, then subsequently a hole is created at index 10,
768 * radix_tree_next_hole covering both indexes may return 10 if called
769 * under rcu_read_lock.
Fengguang Wu6df8ba42007-10-16 01:24:33 -0700770 */
771unsigned long radix_tree_next_hole(struct radix_tree_root *root,
772 unsigned long index, unsigned long max_scan)
773{
774 unsigned long i;
775
776 for (i = 0; i < max_scan; i++) {
777 if (!radix_tree_lookup(root, index))
778 break;
779 index++;
780 if (index == 0)
781 break;
782 }
783
784 return index;
785}
786EXPORT_SYMBOL(radix_tree_next_hole);
787
Wu Fengguangdc566122009-06-16 15:31:32 -0700788/**
789 * radix_tree_prev_hole - find the prev hole (not-present entry)
790 * @root: tree root
791 * @index: index key
792 * @max_scan: maximum range to search
793 *
794 * Search backwards in the range [max(index-max_scan+1, 0), index]
795 * for the first hole.
796 *
797 * Returns: the index of the hole if found, otherwise returns an index
798 * outside of the set specified (in which case 'index - return >= max_scan'
Cesar Eduardo Barrosedcd1d82010-05-26 14:44:27 -0700799 * will be true). In rare cases of wrap-around, ULONG_MAX will be returned.
Wu Fengguangdc566122009-06-16 15:31:32 -0700800 *
801 * radix_tree_next_hole may be called under rcu_read_lock. However, like
802 * radix_tree_gang_lookup, this will not atomically search a snapshot of
803 * the tree at a single point in time. For example, if a hole is created
804 * at index 10, then subsequently a hole is created at index 5,
805 * radix_tree_prev_hole covering both indexes may return 5 if called under
806 * rcu_read_lock.
807 */
808unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
809 unsigned long index, unsigned long max_scan)
810{
811 unsigned long i;
812
813 for (i = 0; i < max_scan; i++) {
814 if (!radix_tree_lookup(root, index))
815 break;
816 index--;
Cesar Eduardo Barrosedcd1d82010-05-26 14:44:27 -0700817 if (index == ULONG_MAX)
Wu Fengguangdc566122009-06-16 15:31:32 -0700818 break;
819 }
820
821 return index;
822}
823EXPORT_SYMBOL(radix_tree_prev_hole);
824
Linus Torvalds1da177e2005-04-16 15:20:36 -0700825static unsigned int
Nick Piggin47feff22008-07-25 19:45:29 -0700826__lookup(struct radix_tree_node *slot, void ***results, unsigned long index,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700827 unsigned int max_items, unsigned long *next_index)
828{
829 unsigned int nr_found = 0;
Christoph Lameter201b6262005-09-06 15:16:46 -0700830 unsigned int shift, height;
Christoph Lameter201b6262005-09-06 15:16:46 -0700831 unsigned long i;
832
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800833 height = slot->height;
834 if (height == 0)
Christoph Lameter201b6262005-09-06 15:16:46 -0700835 goto out;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700836 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700837
Christoph Lameter201b6262005-09-06 15:16:46 -0700838 for ( ; height > 1; height--) {
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800839 i = (index >> shift) & RADIX_TREE_MAP_MASK;
840 for (;;) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700841 if (slot->slots[i] != NULL)
842 break;
843 index &= ~((1UL << shift) - 1);
844 index += 1UL << shift;
845 if (index == 0)
846 goto out; /* 32-bit wraparound */
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800847 i++;
848 if (i == RADIX_TREE_MAP_SIZE)
849 goto out;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700850 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700851
Linus Torvalds1da177e2005-04-16 15:20:36 -0700852 shift -= RADIX_TREE_MAP_SHIFT;
Paul E. McKenney2676a582010-02-22 17:04:54 -0800853 slot = rcu_dereference_raw(slot->slots[i]);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800854 if (slot == NULL)
855 goto out;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700856 }
Christoph Lameter201b6262005-09-06 15:16:46 -0700857
858 /* Bottom level: grab some items */
859 for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
860 index++;
Nick Piggin47feff22008-07-25 19:45:29 -0700861 if (slot->slots[i]) {
862 results[nr_found++] = &(slot->slots[i]);
Christoph Lameter201b6262005-09-06 15:16:46 -0700863 if (nr_found == max_items)
864 goto out;
865 }
866 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700867out:
868 *next_index = index;
869 return nr_found;
870}
871
872/**
873 * radix_tree_gang_lookup - perform multiple lookup on a radix tree
874 * @root: radix tree root
875 * @results: where the results of the lookup are placed
876 * @first_index: start the lookup from this key
877 * @max_items: place up to this many items at *results
878 *
879 * Performs an index-ascending scan of the tree for present items. Places
880 * them at *@results and returns the number of items which were placed at
881 * *@results.
882 *
883 * The implementation is naive.
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800884 *
885 * Like radix_tree_lookup, radix_tree_gang_lookup may be called under
886 * rcu_read_lock. In this case, rather than the returned results being
887 * an atomic snapshot of the tree at a single point in time, the semantics
888 * of an RCU protected gang lookup are as though multiple radix_tree_lookups
889 * have been issued in individual locks, and results stored in 'results'.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700890 */
891unsigned int
892radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
893 unsigned long first_index, unsigned int max_items)
894{
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800895 unsigned long max_index;
896 struct radix_tree_node *node;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700897 unsigned long cur_index = first_index;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800898 unsigned int ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700899
Paul E. McKenney2676a582010-02-22 17:04:54 -0800900 node = rcu_dereference_raw(root->rnode);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800901 if (!node)
902 return 0;
903
Nick Pigginc0bc9872007-10-16 01:24:42 -0700904 if (!radix_tree_is_indirect_ptr(node)) {
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800905 if (first_index > 0)
906 return 0;
Nick Pigginc0bc9872007-10-16 01:24:42 -0700907 results[0] = node;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800908 return 1;
909 }
Nick Piggin27d20fd2010-11-11 14:05:19 -0800910 node = indirect_to_ptr(node);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800911
912 max_index = radix_tree_maxindex(node->height);
913
914 ret = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700915 while (ret < max_items) {
Nick Piggin47feff22008-07-25 19:45:29 -0700916 unsigned int nr_found, slots_found, i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700917 unsigned long next_index; /* Index of next search */
918
919 if (cur_index > max_index)
920 break;
Nick Piggin47feff22008-07-25 19:45:29 -0700921 slots_found = __lookup(node, (void ***)results + ret, cur_index,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700922 max_items - ret, &next_index);
Nick Piggin47feff22008-07-25 19:45:29 -0700923 nr_found = 0;
924 for (i = 0; i < slots_found; i++) {
925 struct radix_tree_node *slot;
926 slot = *(((void ***)results)[ret + i]);
927 if (!slot)
928 continue;
Nick Piggin27d20fd2010-11-11 14:05:19 -0800929 results[ret + nr_found] =
930 indirect_to_ptr(rcu_dereference_raw(slot));
Nick Piggin47feff22008-07-25 19:45:29 -0700931 nr_found++;
932 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700933 ret += nr_found;
934 if (next_index == 0)
935 break;
936 cur_index = next_index;
937 }
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800938
Linus Torvalds1da177e2005-04-16 15:20:36 -0700939 return ret;
940}
941EXPORT_SYMBOL(radix_tree_gang_lookup);
942
Nick Piggin47feff22008-07-25 19:45:29 -0700943/**
944 * radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree
945 * @root: radix tree root
946 * @results: where the results of the lookup are placed
947 * @first_index: start the lookup from this key
948 * @max_items: place up to this many items at *results
949 *
950 * Performs an index-ascending scan of the tree for present items. Places
951 * their slots at *@results and returns the number of items which were
952 * placed at *@results.
953 *
954 * The implementation is naive.
955 *
956 * Like radix_tree_gang_lookup as far as RCU and locking goes. Slots must
957 * be dereferenced with radix_tree_deref_slot, and if using only RCU
958 * protection, radix_tree_deref_slot may fail requiring a retry.
959 */
960unsigned int
961radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
962 unsigned long first_index, unsigned int max_items)
963{
964 unsigned long max_index;
965 struct radix_tree_node *node;
966 unsigned long cur_index = first_index;
967 unsigned int ret;
968
Paul E. McKenney2676a582010-02-22 17:04:54 -0800969 node = rcu_dereference_raw(root->rnode);
Nick Piggin47feff22008-07-25 19:45:29 -0700970 if (!node)
971 return 0;
972
973 if (!radix_tree_is_indirect_ptr(node)) {
974 if (first_index > 0)
975 return 0;
976 results[0] = (void **)&root->rnode;
977 return 1;
978 }
Nick Piggin27d20fd2010-11-11 14:05:19 -0800979 node = indirect_to_ptr(node);
Nick Piggin47feff22008-07-25 19:45:29 -0700980
981 max_index = radix_tree_maxindex(node->height);
982
983 ret = 0;
984 while (ret < max_items) {
985 unsigned int slots_found;
986 unsigned long next_index; /* Index of next search */
987
988 if (cur_index > max_index)
989 break;
990 slots_found = __lookup(node, results + ret, cur_index,
991 max_items - ret, &next_index);
992 ret += slots_found;
993 if (next_index == 0)
994 break;
995 cur_index = next_index;
996 }
997
998 return ret;
999}
1000EXPORT_SYMBOL(radix_tree_gang_lookup_slot);
1001
Linus Torvalds1da177e2005-04-16 15:20:36 -07001002/*
1003 * FIXME: the two tag_get()s here should use find_next_bit() instead of
1004 * open-coding the search.
1005 */
1006static unsigned int
Nick Piggin47feff22008-07-25 19:45:29 -07001007__lookup_tag(struct radix_tree_node *slot, void ***results, unsigned long index,
Jonathan Corbetdaff89f2006-03-25 03:08:05 -08001008 unsigned int max_items, unsigned long *next_index, unsigned int tag)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001009{
1010 unsigned int nr_found = 0;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001011 unsigned int shift, height;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001012
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001013 height = slot->height;
1014 if (height == 0)
Nick Piggin612d6c12006-06-23 02:03:22 -07001015 goto out;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001016 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
Nick Piggin612d6c12006-06-23 02:03:22 -07001017
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001018 while (height > 0) {
1019 unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK ;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001020
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001021 for (;;) {
1022 if (tag_get(slot, tag, i))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001023 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001024 index &= ~((1UL << shift) - 1);
1025 index += 1UL << shift;
1026 if (index == 0)
1027 goto out; /* 32-bit wraparound */
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001028 i++;
1029 if (i == RADIX_TREE_MAP_SIZE)
1030 goto out;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001031 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001032 height--;
1033 if (height == 0) { /* Bottom level: grab some items */
1034 unsigned long j = index & RADIX_TREE_MAP_MASK;
1035
1036 for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
1037 index++;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001038 if (!tag_get(slot, tag, j))
1039 continue;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001040 /*
1041 * Even though the tag was found set, we need to
1042 * recheck that we have a non-NULL node, because
1043 * if this lookup is lockless, it may have been
1044 * subsequently deleted.
1045 *
1046 * Similar care must be taken in any place that
1047 * lookup ->slots[x] without a lock (ie. can't
1048 * rely on its value remaining the same).
1049 */
Nick Piggin47feff22008-07-25 19:45:29 -07001050 if (slot->slots[j]) {
1051 results[nr_found++] = &(slot->slots[j]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001052 if (nr_found == max_items)
1053 goto out;
1054 }
1055 }
1056 }
1057 shift -= RADIX_TREE_MAP_SHIFT;
Paul E. McKenney2676a582010-02-22 17:04:54 -08001058 slot = rcu_dereference_raw(slot->slots[i]);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001059 if (slot == NULL)
1060 break;
1061 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001062out:
1063 *next_index = index;
1064 return nr_found;
1065}
1066
1067/**
1068 * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
1069 * based on a tag
1070 * @root: radix tree root
1071 * @results: where the results of the lookup are placed
1072 * @first_index: start the lookup from this key
1073 * @max_items: place up to this many items at *results
Jonathan Corbetdaff89f2006-03-25 03:08:05 -08001074 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001075 *
1076 * Performs an index-ascending scan of the tree for present items which
1077 * have the tag indexed by @tag set. Places the items at *@results and
1078 * returns the number of items which were placed at *@results.
1079 */
1080unsigned int
1081radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
Jonathan Corbetdaff89f2006-03-25 03:08:05 -08001082 unsigned long first_index, unsigned int max_items,
1083 unsigned int tag)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001084{
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001085 struct radix_tree_node *node;
1086 unsigned long max_index;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001087 unsigned long cur_index = first_index;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001088 unsigned int ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001089
Nick Piggin612d6c12006-06-23 02:03:22 -07001090 /* check the root's tag bit */
1091 if (!root_tag_get(root, tag))
1092 return 0;
1093
Paul E. McKenney2676a582010-02-22 17:04:54 -08001094 node = rcu_dereference_raw(root->rnode);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001095 if (!node)
1096 return 0;
1097
Nick Pigginc0bc9872007-10-16 01:24:42 -07001098 if (!radix_tree_is_indirect_ptr(node)) {
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001099 if (first_index > 0)
1100 return 0;
Nick Pigginc0bc9872007-10-16 01:24:42 -07001101 results[0] = node;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001102 return 1;
1103 }
Nick Piggin27d20fd2010-11-11 14:05:19 -08001104 node = indirect_to_ptr(node);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001105
1106 max_index = radix_tree_maxindex(node->height);
1107
1108 ret = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001109 while (ret < max_items) {
Nick Piggin47feff22008-07-25 19:45:29 -07001110 unsigned int nr_found, slots_found, i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001111 unsigned long next_index; /* Index of next search */
1112
1113 if (cur_index > max_index)
1114 break;
Nick Piggin47feff22008-07-25 19:45:29 -07001115 slots_found = __lookup_tag(node, (void ***)results + ret,
1116 cur_index, max_items - ret, &next_index, tag);
1117 nr_found = 0;
1118 for (i = 0; i < slots_found; i++) {
1119 struct radix_tree_node *slot;
1120 slot = *(((void ***)results)[ret + i]);
1121 if (!slot)
1122 continue;
Nick Piggin27d20fd2010-11-11 14:05:19 -08001123 results[ret + nr_found] =
1124 indirect_to_ptr(rcu_dereference_raw(slot));
Nick Piggin47feff22008-07-25 19:45:29 -07001125 nr_found++;
1126 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001127 ret += nr_found;
1128 if (next_index == 0)
1129 break;
1130 cur_index = next_index;
1131 }
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001132
Linus Torvalds1da177e2005-04-16 15:20:36 -07001133 return ret;
1134}
1135EXPORT_SYMBOL(radix_tree_gang_lookup_tag);
1136
1137/**
Nick Piggin47feff22008-07-25 19:45:29 -07001138 * radix_tree_gang_lookup_tag_slot - perform multiple slot lookup on a
1139 * radix tree based on a tag
1140 * @root: radix tree root
1141 * @results: where the results of the lookup are placed
1142 * @first_index: start the lookup from this key
1143 * @max_items: place up to this many items at *results
1144 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
1145 *
1146 * Performs an index-ascending scan of the tree for present items which
1147 * have the tag indexed by @tag set. Places the slots at *@results and
1148 * returns the number of slots which were placed at *@results.
1149 */
1150unsigned int
1151radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
1152 unsigned long first_index, unsigned int max_items,
1153 unsigned int tag)
1154{
1155 struct radix_tree_node *node;
1156 unsigned long max_index;
1157 unsigned long cur_index = first_index;
1158 unsigned int ret;
1159
1160 /* check the root's tag bit */
1161 if (!root_tag_get(root, tag))
1162 return 0;
1163
Paul E. McKenney2676a582010-02-22 17:04:54 -08001164 node = rcu_dereference_raw(root->rnode);
Nick Piggin47feff22008-07-25 19:45:29 -07001165 if (!node)
1166 return 0;
1167
1168 if (!radix_tree_is_indirect_ptr(node)) {
1169 if (first_index > 0)
1170 return 0;
1171 results[0] = (void **)&root->rnode;
1172 return 1;
1173 }
Nick Piggin27d20fd2010-11-11 14:05:19 -08001174 node = indirect_to_ptr(node);
Nick Piggin47feff22008-07-25 19:45:29 -07001175
1176 max_index = radix_tree_maxindex(node->height);
1177
1178 ret = 0;
1179 while (ret < max_items) {
1180 unsigned int slots_found;
1181 unsigned long next_index; /* Index of next search */
1182
1183 if (cur_index > max_index)
1184 break;
1185 slots_found = __lookup_tag(node, results + ret,
1186 cur_index, max_items - ret, &next_index, tag);
1187 ret += slots_found;
1188 if (next_index == 0)
1189 break;
1190 cur_index = next_index;
1191 }
1192
1193 return ret;
1194}
1195EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot);
1196
1197
1198/**
Nick Piggina5f51c92006-01-08 01:01:41 -08001199 * radix_tree_shrink - shrink height of a radix tree to minimal
1200 * @root radix tree root
1201 */
1202static inline void radix_tree_shrink(struct radix_tree_root *root)
1203{
1204 /* try to shrink tree height */
Nick Pigginc0bc9872007-10-16 01:24:42 -07001205 while (root->height > 0) {
Nick Piggina5f51c92006-01-08 01:01:41 -08001206 struct radix_tree_node *to_free = root->rnode;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001207 void *newptr;
Nick Piggina5f51c92006-01-08 01:01:41 -08001208
Nick Pigginc0bc9872007-10-16 01:24:42 -07001209 BUG_ON(!radix_tree_is_indirect_ptr(to_free));
Nick Piggin27d20fd2010-11-11 14:05:19 -08001210 to_free = indirect_to_ptr(to_free);
Nick Pigginc0bc9872007-10-16 01:24:42 -07001211
1212 /*
1213 * The candidate node has more than one child, or its child
1214 * is not at the leftmost slot, we cannot shrink.
1215 */
1216 if (to_free->count != 1)
1217 break;
1218 if (!to_free->slots[0])
1219 break;
1220
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001221 /*
1222 * We don't need rcu_assign_pointer(), since we are simply
Nick Piggin27d20fd2010-11-11 14:05:19 -08001223 * moving the node from one part of the tree to another: if it
1224 * was safe to dereference the old pointer to it
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001225 * (to_free->slots[0]), it will be safe to dereference the new
Nick Piggin27d20fd2010-11-11 14:05:19 -08001226 * one (root->rnode) as far as dependent read barriers go.
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001227 */
1228 newptr = to_free->slots[0];
Nick Pigginc0bc9872007-10-16 01:24:42 -07001229 if (root->height > 1)
Nick Piggin27d20fd2010-11-11 14:05:19 -08001230 newptr = ptr_to_indirect(newptr);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001231 root->rnode = newptr;
Nick Piggina5f51c92006-01-08 01:01:41 -08001232 root->height--;
Nick Piggin27d20fd2010-11-11 14:05:19 -08001233
1234 /*
1235 * We have a dilemma here. The node's slot[0] must not be
1236 * NULLed in case there are concurrent lookups expecting to
1237 * find the item. However if this was a bottom-level node,
1238 * then it may be subject to the slot pointer being visible
1239 * to callers dereferencing it. If item corresponding to
1240 * slot[0] is subsequently deleted, these callers would expect
1241 * their slot to become empty sooner or later.
1242 *
1243 * For example, lockless pagecache will look up a slot, deref
1244 * the page pointer, and if the page is 0 refcount it means it
1245 * was concurrently deleted from pagecache so try the deref
1246 * again. Fortunately there is already a requirement for logic
1247 * to retry the entire slot lookup -- the indirect pointer
1248 * problem (replacing direct root node with an indirect pointer
1249 * also results in a stale slot). So tag the slot as indirect
1250 * to force callers to retry.
1251 */
1252 if (root->height == 0)
1253 *((unsigned long *)&to_free->slots[0]) |=
1254 RADIX_TREE_INDIRECT_PTR;
1255
Nick Piggina5f51c92006-01-08 01:01:41 -08001256 radix_tree_node_free(to_free);
1257 }
1258}
1259
1260/**
Linus Torvalds1da177e2005-04-16 15:20:36 -07001261 * radix_tree_delete - delete an item from a radix tree
1262 * @root: radix tree root
1263 * @index: index key
1264 *
1265 * Remove the item at @index from the radix tree rooted at @root.
1266 *
1267 * Returns the address of the deleted item, or NULL if it was not present.
1268 */
1269void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
1270{
Jeff Moyer26fb1582007-10-16 01:24:49 -07001271 /*
1272 * The radix tree path needs to be one longer than the maximum path
1273 * since the "list" is null terminated.
1274 */
1275 struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
Nick Piggin612d6c12006-06-23 02:03:22 -07001276 struct radix_tree_node *slot = NULL;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001277 struct radix_tree_node *to_free;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001278 unsigned int height, shift;
Nick Piggind5274262006-01-08 01:01:41 -08001279 int tag;
1280 int offset;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001281
1282 height = root->height;
1283 if (index > radix_tree_maxindex(height))
1284 goto out;
1285
Nick Piggin612d6c12006-06-23 02:03:22 -07001286 slot = root->rnode;
Nick Pigginc0bc9872007-10-16 01:24:42 -07001287 if (height == 0) {
Nick Piggin612d6c12006-06-23 02:03:22 -07001288 root_tag_clear_all(root);
1289 root->rnode = NULL;
1290 goto out;
1291 }
Nick Piggin27d20fd2010-11-11 14:05:19 -08001292 slot = indirect_to_ptr(slot);
Nick Piggin612d6c12006-06-23 02:03:22 -07001293
Linus Torvalds1da177e2005-04-16 15:20:36 -07001294 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
1295 pathp->node = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001296
Nick Piggin612d6c12006-06-23 02:03:22 -07001297 do {
Christoph Lameter201b6262005-09-06 15:16:46 -07001298 if (slot == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001299 goto out;
1300
Linus Torvalds1da177e2005-04-16 15:20:36 -07001301 pathp++;
Nick Piggind5274262006-01-08 01:01:41 -08001302 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
1303 pathp->offset = offset;
1304 pathp->node = slot;
1305 slot = slot->slots[offset];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001306 shift -= RADIX_TREE_MAP_SHIFT;
Nick Piggin612d6c12006-06-23 02:03:22 -07001307 height--;
1308 } while (height > 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001309
Nick Piggin612d6c12006-06-23 02:03:22 -07001310 if (slot == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001311 goto out;
1312
Linus Torvalds1da177e2005-04-16 15:20:36 -07001313 /*
1314 * Clear all tags associated with the just-deleted item
1315 */
Jonathan Corbetdaff89f2006-03-25 03:08:05 -08001316 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
Nick Piggin612d6c12006-06-23 02:03:22 -07001317 if (tag_get(pathp->node, tag, pathp->offset))
1318 radix_tree_tag_clear(root, index, tag);
Nick Piggind5274262006-01-08 01:01:41 -08001319 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001320
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001321 to_free = NULL;
Christoph Lameter201b6262005-09-06 15:16:46 -07001322 /* Now free the nodes we do not need anymore */
Nick Piggin612d6c12006-06-23 02:03:22 -07001323 while (pathp->node) {
Christoph Lameter201b6262005-09-06 15:16:46 -07001324 pathp->node->slots[pathp->offset] = NULL;
Nick Piggina5f51c92006-01-08 01:01:41 -08001325 pathp->node->count--;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001326 /*
1327 * Queue the node for deferred freeing after the
1328 * last reference to it disappears (set NULL, above).
1329 */
1330 if (to_free)
1331 radix_tree_node_free(to_free);
Nick Piggina5f51c92006-01-08 01:01:41 -08001332
1333 if (pathp->node->count) {
Nick Piggin27d20fd2010-11-11 14:05:19 -08001334 if (pathp->node == indirect_to_ptr(root->rnode))
Nick Piggina5f51c92006-01-08 01:01:41 -08001335 radix_tree_shrink(root);
Christoph Lameter201b6262005-09-06 15:16:46 -07001336 goto out;
Nick Piggina5f51c92006-01-08 01:01:41 -08001337 }
Christoph Lameter201b6262005-09-06 15:16:46 -07001338
1339 /* Node with zero slots in use so free it */
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001340 to_free = pathp->node;
Nick Piggin612d6c12006-06-23 02:03:22 -07001341 pathp--;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001342
Linus Torvalds1da177e2005-04-16 15:20:36 -07001343 }
Nick Piggin612d6c12006-06-23 02:03:22 -07001344 root_tag_clear_all(root);
Christoph Lameter201b6262005-09-06 15:16:46 -07001345 root->height = 0;
Nick Piggin612d6c12006-06-23 02:03:22 -07001346 root->rnode = NULL;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001347 if (to_free)
1348 radix_tree_node_free(to_free);
Nick Piggin612d6c12006-06-23 02:03:22 -07001349
Linus Torvalds1da177e2005-04-16 15:20:36 -07001350out:
Nick Piggin612d6c12006-06-23 02:03:22 -07001351 return slot;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001352}
1353EXPORT_SYMBOL(radix_tree_delete);
1354
1355/**
1356 * radix_tree_tagged - test whether any items in the tree are tagged
1357 * @root: radix tree root
1358 * @tag: tag to test
1359 */
Jonathan Corbetdaff89f2006-03-25 03:08:05 -08001360int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001361{
Nick Piggin612d6c12006-06-23 02:03:22 -07001362 return root_tag_get(root, tag);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001363}
1364EXPORT_SYMBOL(radix_tree_tagged);
1365
1366static void
Alexey Dobriyan51cc5062008-07-25 19:45:34 -07001367radix_tree_node_ctor(void *node)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001368{
1369 memset(node, 0, sizeof(struct radix_tree_node));
1370}
1371
1372static __init unsigned long __maxindex(unsigned int height)
1373{
Peter Lund430d2752007-10-16 23:29:35 -07001374 unsigned int width = height * RADIX_TREE_MAP_SHIFT;
1375 int shift = RADIX_TREE_INDEX_BITS - width;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001376
Peter Lund430d2752007-10-16 23:29:35 -07001377 if (shift < 0)
1378 return ~0UL;
1379 if (shift >= BITS_PER_LONG)
1380 return 0UL;
1381 return ~0UL >> shift;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001382}
1383
1384static __init void radix_tree_init_maxindex(void)
1385{
1386 unsigned int i;
1387
1388 for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
1389 height_to_maxindex[i] = __maxindex(i);
1390}
1391
Linus Torvalds1da177e2005-04-16 15:20:36 -07001392static int radix_tree_callback(struct notifier_block *nfb,
1393 unsigned long action,
1394 void *hcpu)
1395{
1396 int cpu = (long)hcpu;
1397 struct radix_tree_preload *rtp;
1398
1399 /* Free per-cpu pool of perloaded nodes */
Rafael J. Wysocki8bb78442007-05-09 02:35:10 -07001400 if (action == CPU_DEAD || action == CPU_DEAD_FROZEN) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001401 rtp = &per_cpu(radix_tree_preloads, cpu);
1402 while (rtp->nr) {
1403 kmem_cache_free(radix_tree_node_cachep,
1404 rtp->nodes[rtp->nr-1]);
1405 rtp->nodes[rtp->nr-1] = NULL;
1406 rtp->nr--;
1407 }
1408 }
1409 return NOTIFY_OK;
1410}
Linus Torvalds1da177e2005-04-16 15:20:36 -07001411
1412void __init radix_tree_init(void)
1413{
1414 radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
1415 sizeof(struct radix_tree_node), 0,
Christoph Lameter488514d2008-04-28 02:12:05 -07001416 SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
1417 radix_tree_node_ctor);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001418 radix_tree_init_maxindex();
1419 hotcpu_notifier(radix_tree_callback, 0);
1420}