blob: dc63d08183945bd25e1c1f854f65cfd75b20b254 [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;
Hugh Dickinse2bdb932012-01-12 17:20:41 -080051 union {
52 struct radix_tree_node *parent; /* Used when ascending tree */
53 struct rcu_head rcu_head; /* Used when freeing node */
54 };
Arnd Bergmanna1115572010-02-25 23:43:52 +010055 void __rcu *slots[RADIX_TREE_MAP_SIZE];
Jonathan Corbetdaff89f2006-03-25 03:08:05 -080056 unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
Linus Torvalds1da177e2005-04-16 15:20:36 -070057};
58
Linus Torvalds1da177e2005-04-16 15:20:36 -070059#define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
Jeff Moyer26fb1582007-10-16 01:24:49 -070060#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
61 RADIX_TREE_MAP_SHIFT))
Linus Torvalds1da177e2005-04-16 15:20:36 -070062
Jeff Moyer26fb1582007-10-16 01:24:49 -070063/*
64 * The height_to_maxindex array needs to be one deeper than the maximum
65 * path as height 0 holds only 1 entry.
66 */
67static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly;
Linus Torvalds1da177e2005-04-16 15:20:36 -070068
69/*
70 * Radix tree node cache.
71 */
Christoph Lametere18b8902006-12-06 20:33:20 -080072static struct kmem_cache *radix_tree_node_cachep;
Linus Torvalds1da177e2005-04-16 15:20:36 -070073
74/*
75 * Per-cpu pool of preloaded nodes
76 */
77struct radix_tree_preload {
78 int nr;
79 struct radix_tree_node *nodes[RADIX_TREE_MAX_PATH];
80};
Harvey Harrison8cef7d52009-01-06 14:40:50 -080081static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
Linus Torvalds1da177e2005-04-16 15:20:36 -070082
Nick Piggin27d20fd2010-11-11 14:05:19 -080083static inline void *ptr_to_indirect(void *ptr)
84{
85 return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR);
86}
87
88static inline void *indirect_to_ptr(void *ptr)
89{
90 return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR);
91}
92
Nick Piggin612d6c12006-06-23 02:03:22 -070093static inline gfp_t root_gfp_mask(struct radix_tree_root *root)
94{
95 return root->gfp_mask & __GFP_BITS_MASK;
96}
97
Nick Piggin643b52b2008-06-12 15:21:52 -070098static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
99 int offset)
100{
101 __set_bit(offset, node->tags[tag]);
102}
103
104static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,
105 int offset)
106{
107 __clear_bit(offset, node->tags[tag]);
108}
109
110static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
111 int offset)
112{
113 return test_bit(offset, node->tags[tag]);
114}
115
116static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag)
117{
118 root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT));
119}
120
121static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag)
122{
123 root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT));
124}
125
126static inline void root_tag_clear_all(struct radix_tree_root *root)
127{
128 root->gfp_mask &= __GFP_BITS_MASK;
129}
130
131static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
132{
133 return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
134}
135
136/*
137 * Returns 1 if any slot in the node has this tag set.
138 * Otherwise returns 0.
139 */
140static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
141{
142 int idx;
143 for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
144 if (node->tags[tag][idx])
145 return 1;
146 }
147 return 0;
148}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700149/*
150 * This assumes that the caller has performed appropriate preallocation, and
151 * that the caller has pinned this thread of control to the current CPU.
152 */
153static struct radix_tree_node *
154radix_tree_node_alloc(struct radix_tree_root *root)
155{
Nick Piggine2848a02008-02-04 22:29:10 -0800156 struct radix_tree_node *ret = NULL;
Nick Piggin612d6c12006-06-23 02:03:22 -0700157 gfp_t gfp_mask = root_gfp_mask(root);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700158
Nick Piggine2848a02008-02-04 22:29:10 -0800159 if (!(gfp_mask & __GFP_WAIT)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700160 struct radix_tree_preload *rtp;
161
Nick Piggine2848a02008-02-04 22:29:10 -0800162 /*
163 * Provided the caller has preloaded here, we will always
164 * succeed in getting a node here (and never reach
165 * kmem_cache_alloc)
166 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700167 rtp = &__get_cpu_var(radix_tree_preloads);
168 if (rtp->nr) {
169 ret = rtp->nodes[rtp->nr - 1];
170 rtp->nodes[rtp->nr - 1] = NULL;
171 rtp->nr--;
172 }
173 }
Nick Piggine2848a02008-02-04 22:29:10 -0800174 if (ret == NULL)
Christoph Lameter488514d2008-04-28 02:12:05 -0700175 ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
Nick Piggine2848a02008-02-04 22:29:10 -0800176
Nick Pigginc0bc9872007-10-16 01:24:42 -0700177 BUG_ON(radix_tree_is_indirect_ptr(ret));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700178 return ret;
179}
180
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800181static void radix_tree_node_rcu_free(struct rcu_head *head)
182{
183 struct radix_tree_node *node =
184 container_of(head, struct radix_tree_node, rcu_head);
Dave Chinnerb6dd0862010-08-23 10:33:19 +1000185 int i;
Nick Piggin643b52b2008-06-12 15:21:52 -0700186
187 /*
188 * must only free zeroed nodes into the slab. radix_tree_shrink
189 * can leave us with a non-NULL entry in the first slot, so clear
190 * that here to make sure.
191 */
Dave Chinnerb6dd0862010-08-23 10:33:19 +1000192 for (i = 0; i < RADIX_TREE_MAX_TAGS; i++)
193 tag_clear(node, i, 0);
194
Nick Piggin643b52b2008-06-12 15:21:52 -0700195 node->slots[0] = NULL;
196 node->count = 0;
197
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800198 kmem_cache_free(radix_tree_node_cachep, node);
199}
200
Linus Torvalds1da177e2005-04-16 15:20:36 -0700201static inline void
202radix_tree_node_free(struct radix_tree_node *node)
203{
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800204 call_rcu(&node->rcu_head, radix_tree_node_rcu_free);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700205}
206
207/*
208 * Load up this CPU's radix_tree_node buffer with sufficient objects to
209 * ensure that the addition of a single element in the tree cannot fail. On
210 * success, return zero, with preemption disabled. On error, return -ENOMEM
211 * with preemption not disabled.
David Howellsb34df792009-11-19 18:11:14 +0000212 *
213 * To make use of this facility, the radix tree must be initialised without
214 * __GFP_WAIT being passed to INIT_RADIX_TREE().
Linus Torvalds1da177e2005-04-16 15:20:36 -0700215 */
Al Virodd0fc662005-10-07 07:46:04 +0100216int radix_tree_preload(gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700217{
218 struct radix_tree_preload *rtp;
219 struct radix_tree_node *node;
220 int ret = -ENOMEM;
221
222 preempt_disable();
223 rtp = &__get_cpu_var(radix_tree_preloads);
224 while (rtp->nr < ARRAY_SIZE(rtp->nodes)) {
225 preempt_enable();
Christoph Lameter488514d2008-04-28 02:12:05 -0700226 node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700227 if (node == NULL)
228 goto out;
229 preempt_disable();
230 rtp = &__get_cpu_var(radix_tree_preloads);
231 if (rtp->nr < ARRAY_SIZE(rtp->nodes))
232 rtp->nodes[rtp->nr++] = node;
233 else
234 kmem_cache_free(radix_tree_node_cachep, node);
235 }
236 ret = 0;
237out:
238 return ret;
239}
David Chinnerd7f09232007-07-14 16:05:04 +1000240EXPORT_SYMBOL(radix_tree_preload);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700241
Nick Piggin6e954b92006-01-08 01:01:40 -0800242/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700243 * Return the maximum key which can be store into a
244 * radix tree with height HEIGHT.
245 */
246static inline unsigned long radix_tree_maxindex(unsigned int height)
247{
248 return height_to_maxindex[height];
249}
250
251/*
252 * Extend a radix tree so it can store key @index.
253 */
254static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
255{
256 struct radix_tree_node *node;
Hugh Dickinse2bdb932012-01-12 17:20:41 -0800257 struct radix_tree_node *slot;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700258 unsigned int height;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700259 int tag;
260
261 /* Figure out what the height should be. */
262 height = root->height + 1;
263 while (index > radix_tree_maxindex(height))
264 height++;
265
266 if (root->rnode == NULL) {
267 root->height = height;
268 goto out;
269 }
270
Linus Torvalds1da177e2005-04-16 15:20:36 -0700271 do {
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800272 unsigned int newheight;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700273 if (!(node = radix_tree_node_alloc(root)))
274 return -ENOMEM;
275
Linus Torvalds1da177e2005-04-16 15:20:36 -0700276 /* Propagate the aggregated tag info into the new root */
Jonathan Corbetdaff89f2006-03-25 03:08:05 -0800277 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
Nick Piggin612d6c12006-06-23 02:03:22 -0700278 if (root_tag_get(root, tag))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700279 tag_set(node, tag, 0);
280 }
281
Hugh Dickinse2bdb932012-01-12 17:20:41 -0800282 /* Increase the height. */
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800283 newheight = root->height+1;
284 node->height = newheight;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700285 node->count = 1;
Hugh Dickinse2bdb932012-01-12 17:20:41 -0800286 node->parent = NULL;
287 slot = root->rnode;
288 if (newheight > 1) {
289 slot = indirect_to_ptr(slot);
290 slot->parent = node;
291 }
292 node->slots[0] = slot;
Nick Piggin27d20fd2010-11-11 14:05:19 -0800293 node = ptr_to_indirect(node);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800294 rcu_assign_pointer(root->rnode, node);
295 root->height = newheight;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700296 } while (height > root->height);
297out:
298 return 0;
299}
300
301/**
302 * radix_tree_insert - insert into a radix tree
303 * @root: radix tree root
304 * @index: index key
305 * @item: item to insert
306 *
307 * Insert an item into the radix tree at position @index.
308 */
309int radix_tree_insert(struct radix_tree_root *root,
310 unsigned long index, void *item)
311{
Christoph Lameter201b6262005-09-06 15:16:46 -0700312 struct radix_tree_node *node = NULL, *slot;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700313 unsigned int height, shift;
314 int offset;
315 int error;
316
Nick Pigginc0bc9872007-10-16 01:24:42 -0700317 BUG_ON(radix_tree_is_indirect_ptr(item));
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800318
Linus Torvalds1da177e2005-04-16 15:20:36 -0700319 /* Make sure the tree is high enough. */
Nick Piggin612d6c12006-06-23 02:03:22 -0700320 if (index > radix_tree_maxindex(root->height)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700321 error = radix_tree_extend(root, index);
322 if (error)
323 return error;
324 }
325
Nick Piggin27d20fd2010-11-11 14:05:19 -0800326 slot = indirect_to_ptr(root->rnode);
Nick Pigginc0bc9872007-10-16 01:24:42 -0700327
Linus Torvalds1da177e2005-04-16 15:20:36 -0700328 height = root->height;
329 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
330
331 offset = 0; /* uninitialised var warning */
Nick Piggin612d6c12006-06-23 02:03:22 -0700332 while (height > 0) {
Christoph Lameter201b6262005-09-06 15:16:46 -0700333 if (slot == NULL) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700334 /* Have to add a child node. */
Christoph Lameter201b6262005-09-06 15:16:46 -0700335 if (!(slot = radix_tree_node_alloc(root)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700336 return -ENOMEM;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800337 slot->height = height;
Hugh Dickinse2bdb932012-01-12 17:20:41 -0800338 slot->parent = node;
Christoph Lameter201b6262005-09-06 15:16:46 -0700339 if (node) {
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800340 rcu_assign_pointer(node->slots[offset], slot);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700341 node->count++;
Christoph Lameter201b6262005-09-06 15:16:46 -0700342 } else
Nick Piggin27d20fd2010-11-11 14:05:19 -0800343 rcu_assign_pointer(root->rnode, ptr_to_indirect(slot));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700344 }
345
346 /* Go a level down */
347 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
Christoph Lameter201b6262005-09-06 15:16:46 -0700348 node = slot;
349 slot = node->slots[offset];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700350 shift -= RADIX_TREE_MAP_SHIFT;
351 height--;
Nick Piggin612d6c12006-06-23 02:03:22 -0700352 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700353
Christoph Lameter201b6262005-09-06 15:16:46 -0700354 if (slot != NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700355 return -EEXIST;
Christoph Lameter201b6262005-09-06 15:16:46 -0700356
Nick Piggin612d6c12006-06-23 02:03:22 -0700357 if (node) {
358 node->count++;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800359 rcu_assign_pointer(node->slots[offset], item);
Nick Piggin612d6c12006-06-23 02:03:22 -0700360 BUG_ON(tag_get(node, 0, offset));
361 BUG_ON(tag_get(node, 1, offset));
362 } else {
Nick Pigginc0bc9872007-10-16 01:24:42 -0700363 rcu_assign_pointer(root->rnode, item);
Nick Piggin612d6c12006-06-23 02:03:22 -0700364 BUG_ON(root_tag_get(root, 0));
365 BUG_ON(root_tag_get(root, 1));
366 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700367
Linus Torvalds1da177e2005-04-16 15:20:36 -0700368 return 0;
369}
370EXPORT_SYMBOL(radix_tree_insert);
371
Huang Shijieb72b71c2009-06-16 15:33:42 -0700372/*
373 * is_slot == 1 : search for the slot.
374 * is_slot == 0 : search for the node.
Hans Reisera4331362005-11-07 00:59:29 -0800375 */
Huang Shijieb72b71c2009-06-16 15:33:42 -0700376static void *radix_tree_lookup_element(struct radix_tree_root *root,
377 unsigned long index, int is_slot)
Hans Reisera4331362005-11-07 00:59:29 -0800378{
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800379 unsigned int height, shift;
380 struct radix_tree_node *node, **slot;
381
Paul E. McKenney2676a582010-02-22 17:04:54 -0800382 node = rcu_dereference_raw(root->rnode);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800383 if (node == NULL)
384 return NULL;
385
Nick Pigginc0bc9872007-10-16 01:24:42 -0700386 if (!radix_tree_is_indirect_ptr(node)) {
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800387 if (index > 0)
388 return NULL;
Huang Shijieb72b71c2009-06-16 15:33:42 -0700389 return is_slot ? (void *)&root->rnode : node;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800390 }
Nick Piggin27d20fd2010-11-11 14:05:19 -0800391 node = indirect_to_ptr(node);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800392
393 height = node->height;
394 if (index > radix_tree_maxindex(height))
395 return NULL;
396
397 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
398
399 do {
400 slot = (struct radix_tree_node **)
401 (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
Paul E. McKenney2676a582010-02-22 17:04:54 -0800402 node = rcu_dereference_raw(*slot);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800403 if (node == NULL)
404 return NULL;
405
406 shift -= RADIX_TREE_MAP_SHIFT;
407 height--;
408 } while (height > 0);
409
Nick Piggin27d20fd2010-11-11 14:05:19 -0800410 return is_slot ? (void *)slot : indirect_to_ptr(node);
Huang Shijieb72b71c2009-06-16 15:33:42 -0700411}
412
413/**
414 * radix_tree_lookup_slot - lookup a slot in a radix tree
415 * @root: radix tree root
416 * @index: index key
417 *
418 * Returns: the slot corresponding to the position @index in the
419 * radix tree @root. This is useful for update-if-exists operations.
420 *
421 * This function can be called under rcu_read_lock iff the slot is not
422 * modified by radix_tree_replace_slot, otherwise it must be called
423 * exclusive from other writers. Any dereference of the slot must be done
424 * using radix_tree_deref_slot.
425 */
426void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
427{
428 return (void **)radix_tree_lookup_element(root, index, 1);
Hans Reisera4331362005-11-07 00:59:29 -0800429}
430EXPORT_SYMBOL(radix_tree_lookup_slot);
431
Linus Torvalds1da177e2005-04-16 15:20:36 -0700432/**
433 * radix_tree_lookup - perform lookup operation on a radix tree
434 * @root: radix tree root
435 * @index: index key
436 *
437 * Lookup the item at the position @index in the radix tree @root.
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800438 *
439 * This function can be called under rcu_read_lock, however the caller
440 * must manage lifetimes of leaf nodes (eg. RCU may also be used to free
441 * them safely). No RCU barriers are required to access or modify the
442 * returned item, however.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700443 */
444void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
445{
Huang Shijieb72b71c2009-06-16 15:33:42 -0700446 return radix_tree_lookup_element(root, index, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700447}
448EXPORT_SYMBOL(radix_tree_lookup);
449
450/**
451 * radix_tree_tag_set - set a tag on a radix tree node
452 * @root: radix tree root
453 * @index: index key
454 * @tag: tag index
455 *
Jonathan Corbetdaff89f2006-03-25 03:08:05 -0800456 * Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
457 * corresponding to @index in the radix tree. From
Linus Torvalds1da177e2005-04-16 15:20:36 -0700458 * the root all the way down to the leaf node.
459 *
460 * Returns the address of the tagged item. Setting a tag on a not-present
461 * item is a bug.
462 */
463void *radix_tree_tag_set(struct radix_tree_root *root,
Jonathan Corbetdaff89f2006-03-25 03:08:05 -0800464 unsigned long index, unsigned int tag)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700465{
466 unsigned int height, shift;
Christoph Lameter201b6262005-09-06 15:16:46 -0700467 struct radix_tree_node *slot;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700468
469 height = root->height;
Peter Zijlstra4c91c362006-06-23 02:03:25 -0700470 BUG_ON(index > radix_tree_maxindex(height));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700471
Nick Piggin27d20fd2010-11-11 14:05:19 -0800472 slot = indirect_to_ptr(root->rnode);
Nick Piggin612d6c12006-06-23 02:03:22 -0700473 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700474
475 while (height > 0) {
476 int offset;
477
478 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
Nick Piggind5274262006-01-08 01:01:41 -0800479 if (!tag_get(slot, tag, offset))
480 tag_set(slot, tag, offset);
Christoph Lameter201b6262005-09-06 15:16:46 -0700481 slot = slot->slots[offset];
482 BUG_ON(slot == NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700483 shift -= RADIX_TREE_MAP_SHIFT;
484 height--;
485 }
486
Nick Piggin612d6c12006-06-23 02:03:22 -0700487 /* set the root's tag bit */
488 if (slot && !root_tag_get(root, tag))
489 root_tag_set(root, tag);
490
Christoph Lameter201b6262005-09-06 15:16:46 -0700491 return slot;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700492}
493EXPORT_SYMBOL(radix_tree_tag_set);
494
495/**
496 * radix_tree_tag_clear - clear a tag on a radix tree node
497 * @root: radix tree root
498 * @index: index key
499 * @tag: tag index
500 *
Jonathan Corbetdaff89f2006-03-25 03:08:05 -0800501 * Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
502 * corresponding to @index in the radix tree. If
Linus Torvalds1da177e2005-04-16 15:20:36 -0700503 * this causes the leaf node to have no tags set then clear the tag in the
504 * next-to-leaf node, etc.
505 *
506 * Returns the address of the tagged item on success, else NULL. ie:
507 * has the same return value and semantics as radix_tree_lookup().
508 */
509void *radix_tree_tag_clear(struct radix_tree_root *root,
Jonathan Corbetdaff89f2006-03-25 03:08:05 -0800510 unsigned long index, unsigned int tag)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700511{
Hugh Dickinse2bdb932012-01-12 17:20:41 -0800512 struct radix_tree_node *node = NULL;
Nick Piggin612d6c12006-06-23 02:03:22 -0700513 struct radix_tree_node *slot = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700514 unsigned int height, shift;
Hugh Dickinse2bdb932012-01-12 17:20:41 -0800515 int uninitialized_var(offset);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700516
517 height = root->height;
518 if (index > radix_tree_maxindex(height))
519 goto out;
520
Hugh Dickinse2bdb932012-01-12 17:20:41 -0800521 shift = height * RADIX_TREE_MAP_SHIFT;
Nick Piggin27d20fd2010-11-11 14:05:19 -0800522 slot = indirect_to_ptr(root->rnode);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700523
Hugh Dickinse2bdb932012-01-12 17:20:41 -0800524 while (shift) {
Christoph Lameter201b6262005-09-06 15:16:46 -0700525 if (slot == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700526 goto out;
527
Linus Torvalds1da177e2005-04-16 15:20:36 -0700528 shift -= RADIX_TREE_MAP_SHIFT;
Hugh Dickinse2bdb932012-01-12 17:20:41 -0800529 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
530 node = slot;
531 slot = slot->slots[offset];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700532 }
533
Nick Piggin612d6c12006-06-23 02:03:22 -0700534 if (slot == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700535 goto out;
536
Hugh Dickinse2bdb932012-01-12 17:20:41 -0800537 while (node) {
538 if (!tag_get(node, tag, offset))
Nick Piggind5274262006-01-08 01:01:41 -0800539 goto out;
Hugh Dickinse2bdb932012-01-12 17:20:41 -0800540 tag_clear(node, tag, offset);
541 if (any_tag_set(node, tag))
Nick Piggin6e954b92006-01-08 01:01:40 -0800542 goto out;
Hugh Dickinse2bdb932012-01-12 17:20:41 -0800543
544 index >>= RADIX_TREE_MAP_SHIFT;
545 offset = index & RADIX_TREE_MAP_MASK;
546 node = node->parent;
Nick Piggin612d6c12006-06-23 02:03:22 -0700547 }
548
549 /* clear the root's tag bit */
550 if (root_tag_get(root, tag))
551 root_tag_clear(root, tag);
552
Linus Torvalds1da177e2005-04-16 15:20:36 -0700553out:
Nick Piggin612d6c12006-06-23 02:03:22 -0700554 return slot;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700555}
556EXPORT_SYMBOL(radix_tree_tag_clear);
557
Linus Torvalds1da177e2005-04-16 15:20:36 -0700558/**
Marcelo Tosatti32605a12005-09-06 15:16:48 -0700559 * radix_tree_tag_get - get a tag on a radix tree node
560 * @root: radix tree root
561 * @index: index key
Jonathan Corbetdaff89f2006-03-25 03:08:05 -0800562 * @tag: tag index (< RADIX_TREE_MAX_TAGS)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700563 *
Marcelo Tosatti32605a12005-09-06 15:16:48 -0700564 * Return values:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700565 *
Nick Piggin612d6c12006-06-23 02:03:22 -0700566 * 0: tag not present or not set
567 * 1: tag set
David Howellsce826532010-04-06 22:36:20 +0100568 *
569 * Note that the return value of this function may not be relied on, even if
570 * the RCU lock is held, unless tag modification and node deletion are excluded
571 * from concurrency.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700572 */
573int radix_tree_tag_get(struct radix_tree_root *root,
Jonathan Corbetdaff89f2006-03-25 03:08:05 -0800574 unsigned long index, unsigned int tag)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700575{
576 unsigned int height, shift;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800577 struct radix_tree_node *node;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700578
Nick Piggin612d6c12006-06-23 02:03:22 -0700579 /* check the root's tag bit */
580 if (!root_tag_get(root, tag))
581 return 0;
582
Paul E. McKenney2676a582010-02-22 17:04:54 -0800583 node = rcu_dereference_raw(root->rnode);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800584 if (node == NULL)
585 return 0;
586
Nick Pigginc0bc9872007-10-16 01:24:42 -0700587 if (!radix_tree_is_indirect_ptr(node))
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800588 return (index == 0);
Nick Piggin27d20fd2010-11-11 14:05:19 -0800589 node = indirect_to_ptr(node);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800590
591 height = node->height;
592 if (index > radix_tree_maxindex(height))
593 return 0;
Nick Piggin612d6c12006-06-23 02:03:22 -0700594
Linus Torvalds1da177e2005-04-16 15:20:36 -0700595 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700596
597 for ( ; ; ) {
598 int offset;
599
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800600 if (node == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700601 return 0;
602
603 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800604 if (!tag_get(node, tag, offset))
Hugh Dickins3fa36ac2011-10-31 17:07:02 -0700605 return 0;
David Howellsce826532010-04-06 22:36:20 +0100606 if (height == 1)
Hugh Dickins3fa36ac2011-10-31 17:07:02 -0700607 return 1;
Paul E. McKenney2676a582010-02-22 17:04:54 -0800608 node = rcu_dereference_raw(node->slots[offset]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700609 shift -= RADIX_TREE_MAP_SHIFT;
610 height--;
611 }
612}
613EXPORT_SYMBOL(radix_tree_tag_get);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700614
Fengguang Wu6df8ba42007-10-16 01:24:33 -0700615/**
Jan Karaebf8aa42010-08-09 17:19:11 -0700616 * radix_tree_range_tag_if_tagged - for each item in given range set given
617 * tag if item has another tag set
618 * @root: radix tree root
619 * @first_indexp: pointer to a starting index of a range to scan
620 * @last_index: last index of a range to scan
621 * @nr_to_tag: maximum number items to tag
622 * @iftag: tag index to test
623 * @settag: tag index to set if tested tag is set
624 *
625 * This function scans range of radix tree from first_index to last_index
626 * (inclusive). For each item in the range if iftag is set, the function sets
627 * also settag. The function stops either after tagging nr_to_tag items or
628 * after reaching last_index.
629 *
Dave Chinner144dcfc2010-08-23 10:33:53 +1000630 * The tags must be set from the leaf level only and propagated back up the
631 * path to the root. We must do this so that we resolve the full path before
632 * setting any tags on intermediate nodes. If we set tags as we descend, then
633 * we can get to the leaf node and find that the index that has the iftag
634 * set is outside the range we are scanning. This reults in dangling tags and
635 * can lead to problems with later tag operations (e.g. livelocks on lookups).
636 *
Jan Karaebf8aa42010-08-09 17:19:11 -0700637 * The function returns number of leaves where the tag was set and sets
638 * *first_indexp to the first unscanned index.
Jan Karad5ed3a42010-08-19 14:13:33 -0700639 * WARNING! *first_indexp can wrap if last_index is ULONG_MAX. Caller must
640 * be prepared to handle that.
Jan Karaebf8aa42010-08-09 17:19:11 -0700641 */
642unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
643 unsigned long *first_indexp, unsigned long last_index,
644 unsigned long nr_to_tag,
645 unsigned int iftag, unsigned int settag)
646{
Dave Chinner144dcfc2010-08-23 10:33:53 +1000647 unsigned int height = root->height;
Hugh Dickinse2bdb932012-01-12 17:20:41 -0800648 struct radix_tree_node *node = NULL;
Dave Chinner144dcfc2010-08-23 10:33:53 +1000649 struct radix_tree_node *slot;
650 unsigned int shift;
651 unsigned long tagged = 0;
652 unsigned long index = *first_indexp;
Jan Karaebf8aa42010-08-09 17:19:11 -0700653
654 last_index = min(last_index, radix_tree_maxindex(height));
655 if (index > last_index)
656 return 0;
657 if (!nr_to_tag)
658 return 0;
659 if (!root_tag_get(root, iftag)) {
660 *first_indexp = last_index + 1;
661 return 0;
662 }
663 if (height == 0) {
664 *first_indexp = last_index + 1;
665 root_tag_set(root, settag);
666 return 1;
667 }
668
669 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
Nick Piggin27d20fd2010-11-11 14:05:19 -0800670 slot = indirect_to_ptr(root->rnode);
Jan Karaebf8aa42010-08-09 17:19:11 -0700671
672 for (;;) {
Hugh Dickinse2bdb932012-01-12 17:20:41 -0800673 unsigned long upindex;
Jan Karaebf8aa42010-08-09 17:19:11 -0700674 int offset;
675
676 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
677 if (!slot->slots[offset])
678 goto next;
679 if (!tag_get(slot, iftag, offset))
680 goto next;
Hugh Dickinse2bdb932012-01-12 17:20:41 -0800681 if (shift) {
Dave Chinner144dcfc2010-08-23 10:33:53 +1000682 /* Go down one level */
Dave Chinner144dcfc2010-08-23 10:33:53 +1000683 shift -= RADIX_TREE_MAP_SHIFT;
Hugh Dickinse2bdb932012-01-12 17:20:41 -0800684 node = slot;
Dave Chinner144dcfc2010-08-23 10:33:53 +1000685 slot = slot->slots[offset];
686 continue;
Jan Karaebf8aa42010-08-09 17:19:11 -0700687 }
Dave Chinner144dcfc2010-08-23 10:33:53 +1000688
689 /* tag the leaf */
690 tagged++;
691 tag_set(slot, settag, offset);
692
693 /* walk back up the path tagging interior nodes */
Hugh Dickinse2bdb932012-01-12 17:20:41 -0800694 upindex = index;
695 while (node) {
696 upindex >>= RADIX_TREE_MAP_SHIFT;
697 offset = upindex & RADIX_TREE_MAP_MASK;
698
Dave Chinner144dcfc2010-08-23 10:33:53 +1000699 /* stop if we find a node with the tag already set */
Hugh Dickinse2bdb932012-01-12 17:20:41 -0800700 if (tag_get(node, settag, offset))
Dave Chinner144dcfc2010-08-23 10:33:53 +1000701 break;
Hugh Dickinse2bdb932012-01-12 17:20:41 -0800702 tag_set(node, settag, offset);
703 node = node->parent;
Dave Chinner144dcfc2010-08-23 10:33:53 +1000704 }
705
Hugh Dickinse2bdb932012-01-12 17:20:41 -0800706 /*
707 * Small optimization: now clear that node pointer.
708 * Since all of this slot's ancestors now have the tag set
709 * from setting it above, we have no further need to walk
710 * back up the tree setting tags, until we update slot to
711 * point to another radix_tree_node.
712 */
713 node = NULL;
714
Jan Karaebf8aa42010-08-09 17:19:11 -0700715next:
716 /* Go to next item at level determined by 'shift' */
717 index = ((index >> shift) + 1) << shift;
Jan Karad5ed3a42010-08-19 14:13:33 -0700718 /* Overflow can happen when last_index is ~0UL... */
719 if (index > last_index || !index)
Jan Karaebf8aa42010-08-09 17:19:11 -0700720 break;
721 if (tagged >= nr_to_tag)
722 break;
723 while (((index >> shift) & RADIX_TREE_MAP_MASK) == 0) {
724 /*
725 * We've fully scanned this node. Go up. Because
726 * last_index is guaranteed to be in the tree, what
727 * we do below cannot wander astray.
728 */
Hugh Dickinse2bdb932012-01-12 17:20:41 -0800729 slot = slot->parent;
Jan Karaebf8aa42010-08-09 17:19:11 -0700730 shift += RADIX_TREE_MAP_SHIFT;
731 }
732 }
733 /*
Toshiyuki Okajimaac15ee62011-01-25 15:07:32 -0800734 * We need not to tag the root tag if there is no tag which is set with
735 * settag within the range from *first_indexp to last_index.
Jan Karaebf8aa42010-08-09 17:19:11 -0700736 */
Toshiyuki Okajimaac15ee62011-01-25 15:07:32 -0800737 if (tagged > 0)
738 root_tag_set(root, settag);
Jan Karaebf8aa42010-08-09 17:19:11 -0700739 *first_indexp = index;
740
741 return tagged;
742}
743EXPORT_SYMBOL(radix_tree_range_tag_if_tagged);
744
745
746/**
Fengguang Wu6df8ba42007-10-16 01:24:33 -0700747 * radix_tree_next_hole - find the next hole (not-present entry)
748 * @root: tree root
749 * @index: index key
750 * @max_scan: maximum range to search
751 *
752 * Search the set [index, min(index+max_scan-1, MAX_INDEX)] for the lowest
753 * indexed hole.
754 *
755 * Returns: the index of the hole if found, otherwise returns an index
756 * outside of the set specified (in which case 'return - index >= max_scan'
Wu Fengguang8e6bdb72008-11-27 11:42:22 +0100757 * will be true). In rare cases of index wrap-around, 0 will be returned.
Fengguang Wu6df8ba42007-10-16 01:24:33 -0700758 *
759 * radix_tree_next_hole may be called under rcu_read_lock. However, like
Wu Fengguang8e6bdb72008-11-27 11:42:22 +0100760 * radix_tree_gang_lookup, this will not atomically search a snapshot of
761 * the tree at a single point in time. For example, if a hole is created
762 * at index 5, then subsequently a hole is created at index 10,
763 * radix_tree_next_hole covering both indexes may return 10 if called
764 * under rcu_read_lock.
Fengguang Wu6df8ba42007-10-16 01:24:33 -0700765 */
766unsigned long radix_tree_next_hole(struct radix_tree_root *root,
767 unsigned long index, unsigned long max_scan)
768{
769 unsigned long i;
770
771 for (i = 0; i < max_scan; i++) {
772 if (!radix_tree_lookup(root, index))
773 break;
774 index++;
775 if (index == 0)
776 break;
777 }
778
779 return index;
780}
781EXPORT_SYMBOL(radix_tree_next_hole);
782
Wu Fengguangdc566122009-06-16 15:31:32 -0700783/**
784 * radix_tree_prev_hole - find the prev hole (not-present entry)
785 * @root: tree root
786 * @index: index key
787 * @max_scan: maximum range to search
788 *
789 * Search backwards in the range [max(index-max_scan+1, 0), index]
790 * for the first hole.
791 *
792 * Returns: the index of the hole if found, otherwise returns an index
793 * outside of the set specified (in which case 'index - return >= max_scan'
Cesar Eduardo Barrosedcd1d82010-05-26 14:44:27 -0700794 * will be true). In rare cases of wrap-around, ULONG_MAX will be returned.
Wu Fengguangdc566122009-06-16 15:31:32 -0700795 *
796 * radix_tree_next_hole may be called under rcu_read_lock. However, like
797 * radix_tree_gang_lookup, this will not atomically search a snapshot of
798 * the tree at a single point in time. For example, if a hole is created
799 * at index 10, then subsequently a hole is created at index 5,
800 * radix_tree_prev_hole covering both indexes may return 5 if called under
801 * rcu_read_lock.
802 */
803unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
804 unsigned long index, unsigned long max_scan)
805{
806 unsigned long i;
807
808 for (i = 0; i < max_scan; i++) {
809 if (!radix_tree_lookup(root, index))
810 break;
811 index--;
Cesar Eduardo Barrosedcd1d82010-05-26 14:44:27 -0700812 if (index == ULONG_MAX)
Wu Fengguangdc566122009-06-16 15:31:32 -0700813 break;
814 }
815
816 return index;
817}
818EXPORT_SYMBOL(radix_tree_prev_hole);
819
Linus Torvalds1da177e2005-04-16 15:20:36 -0700820static unsigned int
Hugh Dickins63286502011-08-03 16:21:18 -0700821__lookup(struct radix_tree_node *slot, void ***results, unsigned long *indices,
822 unsigned long index, unsigned int max_items, unsigned long *next_index)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700823{
824 unsigned int nr_found = 0;
Christoph Lameter201b6262005-09-06 15:16:46 -0700825 unsigned int shift, height;
Christoph Lameter201b6262005-09-06 15:16:46 -0700826 unsigned long i;
827
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800828 height = slot->height;
829 if (height == 0)
Christoph Lameter201b6262005-09-06 15:16:46 -0700830 goto out;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700831 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700832
Christoph Lameter201b6262005-09-06 15:16:46 -0700833 for ( ; height > 1; height--) {
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800834 i = (index >> shift) & RADIX_TREE_MAP_MASK;
835 for (;;) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700836 if (slot->slots[i] != NULL)
837 break;
838 index &= ~((1UL << shift) - 1);
839 index += 1UL << shift;
840 if (index == 0)
841 goto out; /* 32-bit wraparound */
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800842 i++;
843 if (i == RADIX_TREE_MAP_SIZE)
844 goto out;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700845 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700846
Linus Torvalds1da177e2005-04-16 15:20:36 -0700847 shift -= RADIX_TREE_MAP_SHIFT;
Paul E. McKenney2676a582010-02-22 17:04:54 -0800848 slot = rcu_dereference_raw(slot->slots[i]);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800849 if (slot == NULL)
850 goto out;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700851 }
Christoph Lameter201b6262005-09-06 15:16:46 -0700852
853 /* Bottom level: grab some items */
854 for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
Nick Piggin47feff22008-07-25 19:45:29 -0700855 if (slot->slots[i]) {
Hugh Dickins63286502011-08-03 16:21:18 -0700856 results[nr_found] = &(slot->slots[i]);
857 if (indices)
858 indices[nr_found] = index;
859 if (++nr_found == max_items) {
860 index++;
Christoph Lameter201b6262005-09-06 15:16:46 -0700861 goto out;
Hugh Dickins63286502011-08-03 16:21:18 -0700862 }
Christoph Lameter201b6262005-09-06 15:16:46 -0700863 }
Hugh Dickins63286502011-08-03 16:21:18 -0700864 index++;
Christoph Lameter201b6262005-09-06 15:16:46 -0700865 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700866out:
867 *next_index = index;
868 return nr_found;
869}
870
871/**
872 * radix_tree_gang_lookup - perform multiple lookup on a radix tree
873 * @root: radix tree root
874 * @results: where the results of the lookup are placed
875 * @first_index: start the lookup from this key
876 * @max_items: place up to this many items at *results
877 *
878 * Performs an index-ascending scan of the tree for present items. Places
879 * them at *@results and returns the number of items which were placed at
880 * *@results.
881 *
882 * The implementation is naive.
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800883 *
884 * Like radix_tree_lookup, radix_tree_gang_lookup may be called under
885 * rcu_read_lock. In this case, rather than the returned results being
886 * an atomic snapshot of the tree at a single point in time, the semantics
887 * of an RCU protected gang lookup are as though multiple radix_tree_lookups
888 * have been issued in individual locks, and results stored in 'results'.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700889 */
890unsigned int
891radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
892 unsigned long first_index, unsigned int max_items)
893{
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800894 unsigned long max_index;
895 struct radix_tree_node *node;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700896 unsigned long cur_index = first_index;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800897 unsigned int ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700898
Paul E. McKenney2676a582010-02-22 17:04:54 -0800899 node = rcu_dereference_raw(root->rnode);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800900 if (!node)
901 return 0;
902
Nick Pigginc0bc9872007-10-16 01:24:42 -0700903 if (!radix_tree_is_indirect_ptr(node)) {
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800904 if (first_index > 0)
905 return 0;
Nick Pigginc0bc9872007-10-16 01:24:42 -0700906 results[0] = node;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800907 return 1;
908 }
Nick Piggin27d20fd2010-11-11 14:05:19 -0800909 node = indirect_to_ptr(node);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800910
911 max_index = radix_tree_maxindex(node->height);
912
913 ret = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700914 while (ret < max_items) {
Nick Piggin47feff22008-07-25 19:45:29 -0700915 unsigned int nr_found, slots_found, i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700916 unsigned long next_index; /* Index of next search */
917
918 if (cur_index > max_index)
919 break;
Hugh Dickins63286502011-08-03 16:21:18 -0700920 slots_found = __lookup(node, (void ***)results + ret, NULL,
921 cur_index, max_items - ret, &next_index);
Nick Piggin47feff22008-07-25 19:45:29 -0700922 nr_found = 0;
923 for (i = 0; i < slots_found; i++) {
924 struct radix_tree_node *slot;
925 slot = *(((void ***)results)[ret + i]);
926 if (!slot)
927 continue;
Nick Piggin27d20fd2010-11-11 14:05:19 -0800928 results[ret + nr_found] =
929 indirect_to_ptr(rcu_dereference_raw(slot));
Nick Piggin47feff22008-07-25 19:45:29 -0700930 nr_found++;
931 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700932 ret += nr_found;
933 if (next_index == 0)
934 break;
935 cur_index = next_index;
936 }
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800937
Linus Torvalds1da177e2005-04-16 15:20:36 -0700938 return ret;
939}
940EXPORT_SYMBOL(radix_tree_gang_lookup);
941
Nick Piggin47feff22008-07-25 19:45:29 -0700942/**
943 * radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree
944 * @root: radix tree root
945 * @results: where the results of the lookup are placed
Hugh Dickins63286502011-08-03 16:21:18 -0700946 * @indices: where their indices should be placed (but usually NULL)
Nick Piggin47feff22008-07-25 19:45:29 -0700947 * @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
Hugh Dickins63286502011-08-03 16:21:18 -0700961radix_tree_gang_lookup_slot(struct radix_tree_root *root,
962 void ***results, unsigned long *indices,
Nick Piggin47feff22008-07-25 19:45:29 -0700963 unsigned long first_index, unsigned int max_items)
964{
965 unsigned long max_index;
966 struct radix_tree_node *node;
967 unsigned long cur_index = first_index;
968 unsigned int ret;
969
Paul E. McKenney2676a582010-02-22 17:04:54 -0800970 node = rcu_dereference_raw(root->rnode);
Nick Piggin47feff22008-07-25 19:45:29 -0700971 if (!node)
972 return 0;
973
974 if (!radix_tree_is_indirect_ptr(node)) {
975 if (first_index > 0)
976 return 0;
977 results[0] = (void **)&root->rnode;
Hugh Dickins63286502011-08-03 16:21:18 -0700978 if (indices)
979 indices[0] = 0;
Nick Piggin47feff22008-07-25 19:45:29 -0700980 return 1;
981 }
Nick Piggin27d20fd2010-11-11 14:05:19 -0800982 node = indirect_to_ptr(node);
Nick Piggin47feff22008-07-25 19:45:29 -0700983
984 max_index = radix_tree_maxindex(node->height);
985
986 ret = 0;
987 while (ret < max_items) {
988 unsigned int slots_found;
989 unsigned long next_index; /* Index of next search */
990
991 if (cur_index > max_index)
992 break;
Hugh Dickins63286502011-08-03 16:21:18 -0700993 slots_found = __lookup(node, results + ret,
994 indices ? indices + ret : NULL,
995 cur_index, max_items - ret, &next_index);
Nick Piggin47feff22008-07-25 19:45:29 -0700996 ret += slots_found;
997 if (next_index == 0)
998 break;
999 cur_index = next_index;
1000 }
1001
1002 return ret;
1003}
1004EXPORT_SYMBOL(radix_tree_gang_lookup_slot);
1005
Linus Torvalds1da177e2005-04-16 15:20:36 -07001006/*
1007 * FIXME: the two tag_get()s here should use find_next_bit() instead of
1008 * open-coding the search.
1009 */
1010static unsigned int
Nick Piggin47feff22008-07-25 19:45:29 -07001011__lookup_tag(struct radix_tree_node *slot, void ***results, unsigned long index,
Jonathan Corbetdaff89f2006-03-25 03:08:05 -08001012 unsigned int max_items, unsigned long *next_index, unsigned int tag)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001013{
1014 unsigned int nr_found = 0;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001015 unsigned int shift, height;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001016
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001017 height = slot->height;
1018 if (height == 0)
Nick Piggin612d6c12006-06-23 02:03:22 -07001019 goto out;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001020 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
Nick Piggin612d6c12006-06-23 02:03:22 -07001021
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001022 while (height > 0) {
1023 unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK ;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001024
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001025 for (;;) {
1026 if (tag_get(slot, tag, i))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001027 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001028 index &= ~((1UL << shift) - 1);
1029 index += 1UL << shift;
1030 if (index == 0)
1031 goto out; /* 32-bit wraparound */
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001032 i++;
1033 if (i == RADIX_TREE_MAP_SIZE)
1034 goto out;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001035 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001036 height--;
1037 if (height == 0) { /* Bottom level: grab some items */
1038 unsigned long j = index & RADIX_TREE_MAP_MASK;
1039
1040 for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
1041 index++;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001042 if (!tag_get(slot, tag, j))
1043 continue;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001044 /*
1045 * Even though the tag was found set, we need to
1046 * recheck that we have a non-NULL node, because
1047 * if this lookup is lockless, it may have been
1048 * subsequently deleted.
1049 *
1050 * Similar care must be taken in any place that
1051 * lookup ->slots[x] without a lock (ie. can't
1052 * rely on its value remaining the same).
1053 */
Nick Piggin47feff22008-07-25 19:45:29 -07001054 if (slot->slots[j]) {
1055 results[nr_found++] = &(slot->slots[j]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001056 if (nr_found == max_items)
1057 goto out;
1058 }
1059 }
1060 }
1061 shift -= RADIX_TREE_MAP_SHIFT;
Paul E. McKenney2676a582010-02-22 17:04:54 -08001062 slot = rcu_dereference_raw(slot->slots[i]);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001063 if (slot == NULL)
1064 break;
1065 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001066out:
1067 *next_index = index;
1068 return nr_found;
1069}
1070
1071/**
1072 * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
1073 * based on a tag
1074 * @root: radix tree root
1075 * @results: where the results of the lookup are placed
1076 * @first_index: start the lookup from this key
1077 * @max_items: place up to this many items at *results
Jonathan Corbetdaff89f2006-03-25 03:08:05 -08001078 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001079 *
1080 * Performs an index-ascending scan of the tree for present items which
1081 * have the tag indexed by @tag set. Places the items at *@results and
1082 * returns the number of items which were placed at *@results.
1083 */
1084unsigned int
1085radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
Jonathan Corbetdaff89f2006-03-25 03:08:05 -08001086 unsigned long first_index, unsigned int max_items,
1087 unsigned int tag)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001088{
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001089 struct radix_tree_node *node;
1090 unsigned long max_index;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001091 unsigned long cur_index = first_index;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001092 unsigned int ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001093
Nick Piggin612d6c12006-06-23 02:03:22 -07001094 /* check the root's tag bit */
1095 if (!root_tag_get(root, tag))
1096 return 0;
1097
Paul E. McKenney2676a582010-02-22 17:04:54 -08001098 node = rcu_dereference_raw(root->rnode);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001099 if (!node)
1100 return 0;
1101
Nick Pigginc0bc9872007-10-16 01:24:42 -07001102 if (!radix_tree_is_indirect_ptr(node)) {
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001103 if (first_index > 0)
1104 return 0;
Nick Pigginc0bc9872007-10-16 01:24:42 -07001105 results[0] = node;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001106 return 1;
1107 }
Nick Piggin27d20fd2010-11-11 14:05:19 -08001108 node = indirect_to_ptr(node);
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001109
1110 max_index = radix_tree_maxindex(node->height);
1111
1112 ret = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001113 while (ret < max_items) {
Nick Piggin47feff22008-07-25 19:45:29 -07001114 unsigned int nr_found, slots_found, i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001115 unsigned long next_index; /* Index of next search */
1116
1117 if (cur_index > max_index)
1118 break;
Nick Piggin47feff22008-07-25 19:45:29 -07001119 slots_found = __lookup_tag(node, (void ***)results + ret,
1120 cur_index, max_items - ret, &next_index, tag);
1121 nr_found = 0;
1122 for (i = 0; i < slots_found; i++) {
1123 struct radix_tree_node *slot;
1124 slot = *(((void ***)results)[ret + i]);
1125 if (!slot)
1126 continue;
Nick Piggin27d20fd2010-11-11 14:05:19 -08001127 results[ret + nr_found] =
1128 indirect_to_ptr(rcu_dereference_raw(slot));
Nick Piggin47feff22008-07-25 19:45:29 -07001129 nr_found++;
1130 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001131 ret += nr_found;
1132 if (next_index == 0)
1133 break;
1134 cur_index = next_index;
1135 }
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001136
Linus Torvalds1da177e2005-04-16 15:20:36 -07001137 return ret;
1138}
1139EXPORT_SYMBOL(radix_tree_gang_lookup_tag);
1140
1141/**
Nick Piggin47feff22008-07-25 19:45:29 -07001142 * radix_tree_gang_lookup_tag_slot - perform multiple slot lookup on a
1143 * radix tree based on a tag
1144 * @root: radix tree root
1145 * @results: where the results of the lookup are placed
1146 * @first_index: start the lookup from this key
1147 * @max_items: place up to this many items at *results
1148 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
1149 *
1150 * Performs an index-ascending scan of the tree for present items which
1151 * have the tag indexed by @tag set. Places the slots at *@results and
1152 * returns the number of slots which were placed at *@results.
1153 */
1154unsigned int
1155radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
1156 unsigned long first_index, unsigned int max_items,
1157 unsigned int tag)
1158{
1159 struct radix_tree_node *node;
1160 unsigned long max_index;
1161 unsigned long cur_index = first_index;
1162 unsigned int ret;
1163
1164 /* check the root's tag bit */
1165 if (!root_tag_get(root, tag))
1166 return 0;
1167
Paul E. McKenney2676a582010-02-22 17:04:54 -08001168 node = rcu_dereference_raw(root->rnode);
Nick Piggin47feff22008-07-25 19:45:29 -07001169 if (!node)
1170 return 0;
1171
1172 if (!radix_tree_is_indirect_ptr(node)) {
1173 if (first_index > 0)
1174 return 0;
1175 results[0] = (void **)&root->rnode;
1176 return 1;
1177 }
Nick Piggin27d20fd2010-11-11 14:05:19 -08001178 node = indirect_to_ptr(node);
Nick Piggin47feff22008-07-25 19:45:29 -07001179
1180 max_index = radix_tree_maxindex(node->height);
1181
1182 ret = 0;
1183 while (ret < max_items) {
1184 unsigned int slots_found;
1185 unsigned long next_index; /* Index of next search */
1186
1187 if (cur_index > max_index)
1188 break;
1189 slots_found = __lookup_tag(node, results + ret,
1190 cur_index, max_items - ret, &next_index, tag);
1191 ret += slots_found;
1192 if (next_index == 0)
1193 break;
1194 cur_index = next_index;
1195 }
1196
1197 return ret;
1198}
1199EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot);
1200
Hugh Dickinse504f3f2011-08-03 16:21:27 -07001201#if defined(CONFIG_SHMEM) && defined(CONFIG_SWAP)
1202#include <linux/sched.h> /* for cond_resched() */
1203
1204/*
1205 * This linear search is at present only useful to shmem_unuse_inode().
1206 */
1207static unsigned long __locate(struct radix_tree_node *slot, void *item,
1208 unsigned long index, unsigned long *found_index)
1209{
1210 unsigned int shift, height;
1211 unsigned long i;
1212
1213 height = slot->height;
1214 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
1215
1216 for ( ; height > 1; height--) {
1217 i = (index >> shift) & RADIX_TREE_MAP_MASK;
1218 for (;;) {
1219 if (slot->slots[i] != NULL)
1220 break;
1221 index &= ~((1UL << shift) - 1);
1222 index += 1UL << shift;
1223 if (index == 0)
1224 goto out; /* 32-bit wraparound */
1225 i++;
1226 if (i == RADIX_TREE_MAP_SIZE)
1227 goto out;
1228 }
1229
1230 shift -= RADIX_TREE_MAP_SHIFT;
1231 slot = rcu_dereference_raw(slot->slots[i]);
1232 if (slot == NULL)
1233 goto out;
1234 }
1235
1236 /* Bottom level: check items */
1237 for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
1238 if (slot->slots[i] == item) {
1239 *found_index = index + i;
1240 index = 0;
1241 goto out;
1242 }
1243 }
1244 index += RADIX_TREE_MAP_SIZE;
1245out:
1246 return index;
1247}
1248
1249/**
1250 * radix_tree_locate_item - search through radix tree for item
1251 * @root: radix tree root
1252 * @item: item to be found
1253 *
1254 * Returns index where item was found, or -1 if not found.
1255 * Caller must hold no lock (since this time-consuming function needs
1256 * to be preemptible), and must check afterwards if item is still there.
1257 */
1258unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item)
1259{
1260 struct radix_tree_node *node;
1261 unsigned long max_index;
1262 unsigned long cur_index = 0;
1263 unsigned long found_index = -1;
1264
1265 do {
1266 rcu_read_lock();
1267 node = rcu_dereference_raw(root->rnode);
1268 if (!radix_tree_is_indirect_ptr(node)) {
1269 rcu_read_unlock();
1270 if (node == item)
1271 found_index = 0;
1272 break;
1273 }
1274
1275 node = indirect_to_ptr(node);
1276 max_index = radix_tree_maxindex(node->height);
1277 if (cur_index > max_index)
1278 break;
1279
1280 cur_index = __locate(node, item, cur_index, &found_index);
1281 rcu_read_unlock();
1282 cond_resched();
1283 } while (cur_index != 0 && cur_index <= max_index);
1284
1285 return found_index;
1286}
1287#else
1288unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item)
1289{
1290 return -1;
1291}
1292#endif /* CONFIG_SHMEM && CONFIG_SWAP */
Nick Piggin47feff22008-07-25 19:45:29 -07001293
1294/**
Nick Piggina5f51c92006-01-08 01:01:41 -08001295 * radix_tree_shrink - shrink height of a radix tree to minimal
1296 * @root radix tree root
1297 */
1298static inline void radix_tree_shrink(struct radix_tree_root *root)
1299{
1300 /* try to shrink tree height */
Nick Pigginc0bc9872007-10-16 01:24:42 -07001301 while (root->height > 0) {
Nick Piggina5f51c92006-01-08 01:01:41 -08001302 struct radix_tree_node *to_free = root->rnode;
Hugh Dickinse2bdb932012-01-12 17:20:41 -08001303 struct radix_tree_node *slot;
Nick Piggina5f51c92006-01-08 01:01:41 -08001304
Nick Pigginc0bc9872007-10-16 01:24:42 -07001305 BUG_ON(!radix_tree_is_indirect_ptr(to_free));
Nick Piggin27d20fd2010-11-11 14:05:19 -08001306 to_free = indirect_to_ptr(to_free);
Nick Pigginc0bc9872007-10-16 01:24:42 -07001307
1308 /*
1309 * The candidate node has more than one child, or its child
1310 * is not at the leftmost slot, we cannot shrink.
1311 */
1312 if (to_free->count != 1)
1313 break;
1314 if (!to_free->slots[0])
1315 break;
1316
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001317 /*
1318 * We don't need rcu_assign_pointer(), since we are simply
Nick Piggin27d20fd2010-11-11 14:05:19 -08001319 * moving the node from one part of the tree to another: if it
1320 * was safe to dereference the old pointer to it
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001321 * (to_free->slots[0]), it will be safe to dereference the new
Nick Piggin27d20fd2010-11-11 14:05:19 -08001322 * one (root->rnode) as far as dependent read barriers go.
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001323 */
Hugh Dickinse2bdb932012-01-12 17:20:41 -08001324 slot = to_free->slots[0];
1325 if (root->height > 1) {
1326 slot->parent = NULL;
1327 slot = ptr_to_indirect(slot);
1328 }
1329 root->rnode = slot;
Nick Piggina5f51c92006-01-08 01:01:41 -08001330 root->height--;
Nick Piggin27d20fd2010-11-11 14:05:19 -08001331
1332 /*
1333 * We have a dilemma here. The node's slot[0] must not be
1334 * NULLed in case there are concurrent lookups expecting to
1335 * find the item. However if this was a bottom-level node,
1336 * then it may be subject to the slot pointer being visible
1337 * to callers dereferencing it. If item corresponding to
1338 * slot[0] is subsequently deleted, these callers would expect
1339 * their slot to become empty sooner or later.
1340 *
1341 * For example, lockless pagecache will look up a slot, deref
1342 * the page pointer, and if the page is 0 refcount it means it
1343 * was concurrently deleted from pagecache so try the deref
1344 * again. Fortunately there is already a requirement for logic
1345 * to retry the entire slot lookup -- the indirect pointer
1346 * problem (replacing direct root node with an indirect pointer
1347 * also results in a stale slot). So tag the slot as indirect
1348 * to force callers to retry.
1349 */
1350 if (root->height == 0)
1351 *((unsigned long *)&to_free->slots[0]) |=
1352 RADIX_TREE_INDIRECT_PTR;
1353
Nick Piggina5f51c92006-01-08 01:01:41 -08001354 radix_tree_node_free(to_free);
1355 }
1356}
1357
1358/**
Linus Torvalds1da177e2005-04-16 15:20:36 -07001359 * radix_tree_delete - delete an item from a radix tree
1360 * @root: radix tree root
1361 * @index: index key
1362 *
1363 * Remove the item at @index from the radix tree rooted at @root.
1364 *
1365 * Returns the address of the deleted item, or NULL if it was not present.
1366 */
1367void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
1368{
Hugh Dickinse2bdb932012-01-12 17:20:41 -08001369 struct radix_tree_node *node = NULL;
Nick Piggin612d6c12006-06-23 02:03:22 -07001370 struct radix_tree_node *slot = NULL;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001371 struct radix_tree_node *to_free;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001372 unsigned int height, shift;
Nick Piggind5274262006-01-08 01:01:41 -08001373 int tag;
Hugh Dickinse2bdb932012-01-12 17:20:41 -08001374 int uninitialized_var(offset);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001375
1376 height = root->height;
1377 if (index > radix_tree_maxindex(height))
1378 goto out;
1379
Nick Piggin612d6c12006-06-23 02:03:22 -07001380 slot = root->rnode;
Nick Pigginc0bc9872007-10-16 01:24:42 -07001381 if (height == 0) {
Nick Piggin612d6c12006-06-23 02:03:22 -07001382 root_tag_clear_all(root);
1383 root->rnode = NULL;
1384 goto out;
1385 }
Nick Piggin27d20fd2010-11-11 14:05:19 -08001386 slot = indirect_to_ptr(slot);
Hugh Dickinse2bdb932012-01-12 17:20:41 -08001387 shift = height * RADIX_TREE_MAP_SHIFT;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001388
Nick Piggin612d6c12006-06-23 02:03:22 -07001389 do {
Christoph Lameter201b6262005-09-06 15:16:46 -07001390 if (slot == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001391 goto out;
1392
Linus Torvalds1da177e2005-04-16 15:20:36 -07001393 shift -= RADIX_TREE_MAP_SHIFT;
Hugh Dickinse2bdb932012-01-12 17:20:41 -08001394 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
1395 node = slot;
1396 slot = slot->slots[offset];
1397 } while (shift);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001398
Nick Piggin612d6c12006-06-23 02:03:22 -07001399 if (slot == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001400 goto out;
1401
Linus Torvalds1da177e2005-04-16 15:20:36 -07001402 /*
Hugh Dickinse2bdb932012-01-12 17:20:41 -08001403 * Clear all tags associated with the item to be deleted.
1404 * This way of doing it would be inefficient, but seldom is any set.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001405 */
Jonathan Corbetdaff89f2006-03-25 03:08:05 -08001406 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
Hugh Dickinse2bdb932012-01-12 17:20:41 -08001407 if (tag_get(node, tag, offset))
Nick Piggin612d6c12006-06-23 02:03:22 -07001408 radix_tree_tag_clear(root, index, tag);
Nick Piggind5274262006-01-08 01:01:41 -08001409 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001410
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001411 to_free = NULL;
Christoph Lameter201b6262005-09-06 15:16:46 -07001412 /* Now free the nodes we do not need anymore */
Hugh Dickinse2bdb932012-01-12 17:20:41 -08001413 while (node) {
1414 node->slots[offset] = NULL;
1415 node->count--;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001416 /*
1417 * Queue the node for deferred freeing after the
1418 * last reference to it disappears (set NULL, above).
1419 */
1420 if (to_free)
1421 radix_tree_node_free(to_free);
Nick Piggina5f51c92006-01-08 01:01:41 -08001422
Hugh Dickinse2bdb932012-01-12 17:20:41 -08001423 if (node->count) {
1424 if (node == indirect_to_ptr(root->rnode))
Nick Piggina5f51c92006-01-08 01:01:41 -08001425 radix_tree_shrink(root);
Christoph Lameter201b6262005-09-06 15:16:46 -07001426 goto out;
Nick Piggina5f51c92006-01-08 01:01:41 -08001427 }
Christoph Lameter201b6262005-09-06 15:16:46 -07001428
1429 /* Node with zero slots in use so free it */
Hugh Dickinse2bdb932012-01-12 17:20:41 -08001430 to_free = node;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001431
Hugh Dickinse2bdb932012-01-12 17:20:41 -08001432 index >>= RADIX_TREE_MAP_SHIFT;
1433 offset = index & RADIX_TREE_MAP_MASK;
1434 node = node->parent;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001435 }
Hugh Dickinse2bdb932012-01-12 17:20:41 -08001436
Nick Piggin612d6c12006-06-23 02:03:22 -07001437 root_tag_clear_all(root);
Christoph Lameter201b6262005-09-06 15:16:46 -07001438 root->height = 0;
Nick Piggin612d6c12006-06-23 02:03:22 -07001439 root->rnode = NULL;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001440 if (to_free)
1441 radix_tree_node_free(to_free);
Nick Piggin612d6c12006-06-23 02:03:22 -07001442
Linus Torvalds1da177e2005-04-16 15:20:36 -07001443out:
Nick Piggin612d6c12006-06-23 02:03:22 -07001444 return slot;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001445}
1446EXPORT_SYMBOL(radix_tree_delete);
1447
1448/**
1449 * radix_tree_tagged - test whether any items in the tree are tagged
1450 * @root: radix tree root
1451 * @tag: tag to test
1452 */
Jonathan Corbetdaff89f2006-03-25 03:08:05 -08001453int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001454{
Nick Piggin612d6c12006-06-23 02:03:22 -07001455 return root_tag_get(root, tag);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001456}
1457EXPORT_SYMBOL(radix_tree_tagged);
1458
1459static void
Alexey Dobriyan51cc5062008-07-25 19:45:34 -07001460radix_tree_node_ctor(void *node)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001461{
1462 memset(node, 0, sizeof(struct radix_tree_node));
1463}
1464
1465static __init unsigned long __maxindex(unsigned int height)
1466{
Peter Lund430d2752007-10-16 23:29:35 -07001467 unsigned int width = height * RADIX_TREE_MAP_SHIFT;
1468 int shift = RADIX_TREE_INDEX_BITS - width;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001469
Peter Lund430d2752007-10-16 23:29:35 -07001470 if (shift < 0)
1471 return ~0UL;
1472 if (shift >= BITS_PER_LONG)
1473 return 0UL;
1474 return ~0UL >> shift;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001475}
1476
1477static __init void radix_tree_init_maxindex(void)
1478{
1479 unsigned int i;
1480
1481 for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
1482 height_to_maxindex[i] = __maxindex(i);
1483}
1484
Linus Torvalds1da177e2005-04-16 15:20:36 -07001485static int radix_tree_callback(struct notifier_block *nfb,
1486 unsigned long action,
1487 void *hcpu)
1488{
1489 int cpu = (long)hcpu;
1490 struct radix_tree_preload *rtp;
1491
1492 /* Free per-cpu pool of perloaded nodes */
Rafael J. Wysocki8bb78442007-05-09 02:35:10 -07001493 if (action == CPU_DEAD || action == CPU_DEAD_FROZEN) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001494 rtp = &per_cpu(radix_tree_preloads, cpu);
1495 while (rtp->nr) {
1496 kmem_cache_free(radix_tree_node_cachep,
1497 rtp->nodes[rtp->nr-1]);
1498 rtp->nodes[rtp->nr-1] = NULL;
1499 rtp->nr--;
1500 }
1501 }
1502 return NOTIFY_OK;
1503}
Linus Torvalds1da177e2005-04-16 15:20:36 -07001504
1505void __init radix_tree_init(void)
1506{
1507 radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
1508 sizeof(struct radix_tree_node), 0,
Christoph Lameter488514d2008-04-28 02:12:05 -07001509 SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
1510 radix_tree_node_ctor);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001511 radix_tree_init_maxindex();
1512 hotcpu_notifier(radix_tree_callback, 0);
1513}