lib/radix-tree.c: fix overflow in radix_tree_range_tag_if_tagged()
[linux-2.6.git] / lib / radix-tree.c
1 /*
2  * Copyright (C) 2001 Momchil Velikov
3  * Portions Copyright (C) 2001 Christoph Hellwig
4  * Copyright (C) 2005 SGI, Christoph Lameter
5  * Copyright (C) 2006 Nick Piggin
6  *
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>
31 #include <linux/string.h>
32 #include <linux/bitops.h>
33 #include <linux/rcupdate.h>
34
35
36 #ifdef __KERNEL__
37 #define RADIX_TREE_MAP_SHIFT    (CONFIG_BASE_SMALL ? 4 : 6)
38 #else
39 #define RADIX_TREE_MAP_SHIFT    3       /* For more stressful testing */
40 #endif
41
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
48 struct radix_tree_node {
49         unsigned int    height;         /* Height from the bottom */
50         unsigned int    count;
51         struct rcu_head rcu_head;
52         void            *slots[RADIX_TREE_MAP_SIZE];
53         unsigned long   tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
54 };
55
56 struct radix_tree_path {
57         struct radix_tree_node *node;
58         int offset;
59 };
60
61 #define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))
62 #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
63                                           RADIX_TREE_MAP_SHIFT))
64
65 /*
66  * The height_to_maxindex array needs to be one deeper than the maximum
67  * path as height 0 holds only 1 entry.
68  */
69 static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly;
70
71 /*
72  * Radix tree node cache.
73  */
74 static struct kmem_cache *radix_tree_node_cachep;
75
76 /*
77  * Per-cpu pool of preloaded nodes
78  */
79 struct radix_tree_preload {
80         int nr;
81         struct radix_tree_node *nodes[RADIX_TREE_MAX_PATH];
82 };
83 static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
84
85 static inline gfp_t root_gfp_mask(struct radix_tree_root *root)
86 {
87         return root->gfp_mask & __GFP_BITS_MASK;
88 }
89
90 static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
91                 int offset)
92 {
93         __set_bit(offset, node->tags[tag]);
94 }
95
96 static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,
97                 int offset)
98 {
99         __clear_bit(offset, node->tags[tag]);
100 }
101
102 static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
103                 int offset)
104 {
105         return test_bit(offset, node->tags[tag]);
106 }
107
108 static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag)
109 {
110         root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT));
111 }
112
113 static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag)
114 {
115         root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT));
116 }
117
118 static inline void root_tag_clear_all(struct radix_tree_root *root)
119 {
120         root->gfp_mask &= __GFP_BITS_MASK;
121 }
122
123 static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
124 {
125         return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
126 }
127
128 /*
129  * Returns 1 if any slot in the node has this tag set.
130  * Otherwise returns 0.
131  */
132 static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
133 {
134         int idx;
135         for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
136                 if (node->tags[tag][idx])
137                         return 1;
138         }
139         return 0;
140 }
141 /*
142  * This assumes that the caller has performed appropriate preallocation, and
143  * that the caller has pinned this thread of control to the current CPU.
144  */
145 static struct radix_tree_node *
146 radix_tree_node_alloc(struct radix_tree_root *root)
147 {
148         struct radix_tree_node *ret = NULL;
149         gfp_t gfp_mask = root_gfp_mask(root);
150
151         if (!(gfp_mask & __GFP_WAIT)) {
152                 struct radix_tree_preload *rtp;
153
154                 /*
155                  * Provided the caller has preloaded here, we will always
156                  * succeed in getting a node here (and never reach
157                  * kmem_cache_alloc)
158                  */
159                 rtp = &__get_cpu_var(radix_tree_preloads);
160                 if (rtp->nr) {
161                         ret = rtp->nodes[rtp->nr - 1];
162                         rtp->nodes[rtp->nr - 1] = NULL;
163                         rtp->nr--;
164                 }
165         }
166         if (ret == NULL)
167                 ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
168
169         BUG_ON(radix_tree_is_indirect_ptr(ret));
170         return ret;
171 }
172
173 static void radix_tree_node_rcu_free(struct rcu_head *head)
174 {
175         struct radix_tree_node *node =
176                         container_of(head, struct radix_tree_node, rcu_head);
177
178         /*
179          * must only free zeroed nodes into the slab. radix_tree_shrink
180          * can leave us with a non-NULL entry in the first slot, so clear
181          * that here to make sure.
182          */
183         tag_clear(node, 0, 0);
184         tag_clear(node, 1, 0);
185         node->slots[0] = NULL;
186         node->count = 0;
187
188         kmem_cache_free(radix_tree_node_cachep, node);
189 }
190
191 static inline void
192 radix_tree_node_free(struct radix_tree_node *node)
193 {
194         call_rcu(&node->rcu_head, radix_tree_node_rcu_free);
195 }
196
197 /*
198  * Load up this CPU's radix_tree_node buffer with sufficient objects to
199  * ensure that the addition of a single element in the tree cannot fail.  On
200  * success, return zero, with preemption disabled.  On error, return -ENOMEM
201  * with preemption not disabled.
202  *
203  * To make use of this facility, the radix tree must be initialised without
204  * __GFP_WAIT being passed to INIT_RADIX_TREE().
205  */
206 int radix_tree_preload(gfp_t gfp_mask)
207 {
208         struct radix_tree_preload *rtp;
209         struct radix_tree_node *node;
210         int ret = -ENOMEM;
211
212         preempt_disable();
213         rtp = &__get_cpu_var(radix_tree_preloads);
214         while (rtp->nr < ARRAY_SIZE(rtp->nodes)) {
215                 preempt_enable();
216                 node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
217                 if (node == NULL)
218                         goto out;
219                 preempt_disable();
220                 rtp = &__get_cpu_var(radix_tree_preloads);
221                 if (rtp->nr < ARRAY_SIZE(rtp->nodes))
222                         rtp->nodes[rtp->nr++] = node;
223                 else
224                         kmem_cache_free(radix_tree_node_cachep, node);
225         }
226         ret = 0;
227 out:
228         return ret;
229 }
230 EXPORT_SYMBOL(radix_tree_preload);
231
232 /*
233  *      Return the maximum key which can be store into a
234  *      radix tree with height HEIGHT.
235  */
236 static inline unsigned long radix_tree_maxindex(unsigned int height)
237 {
238         return height_to_maxindex[height];
239 }
240
241 /*
242  *      Extend a radix tree so it can store key @index.
243  */
244 static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
245 {
246         struct radix_tree_node *node;
247         unsigned int height;
248         int tag;
249
250         /* Figure out what the height should be.  */
251         height = root->height + 1;
252         while (index > radix_tree_maxindex(height))
253                 height++;
254
255         if (root->rnode == NULL) {
256                 root->height = height;
257                 goto out;
258         }
259
260         do {
261                 unsigned int newheight;
262                 if (!(node = radix_tree_node_alloc(root)))
263                         return -ENOMEM;
264
265                 /* Increase the height.  */
266                 node->slots[0] = radix_tree_indirect_to_ptr(root->rnode);
267
268                 /* Propagate the aggregated tag info into the new root */
269                 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
270                         if (root_tag_get(root, tag))
271                                 tag_set(node, tag, 0);
272                 }
273
274                 newheight = root->height+1;
275                 node->height = newheight;
276                 node->count = 1;
277                 node = radix_tree_ptr_to_indirect(node);
278                 rcu_assign_pointer(root->rnode, node);
279                 root->height = newheight;
280         } while (height > root->height);
281 out:
282         return 0;
283 }
284
285 /**
286  *      radix_tree_insert    -    insert into a radix tree
287  *      @root:          radix tree root
288  *      @index:         index key
289  *      @item:          item to insert
290  *
291  *      Insert an item into the radix tree at position @index.
292  */
293 int radix_tree_insert(struct radix_tree_root *root,
294                         unsigned long index, void *item)
295 {
296         struct radix_tree_node *node = NULL, *slot;
297         unsigned int height, shift;
298         int offset;
299         int error;
300
301         BUG_ON(radix_tree_is_indirect_ptr(item));
302
303         /* Make sure the tree is high enough.  */
304         if (index > radix_tree_maxindex(root->height)) {
305                 error = radix_tree_extend(root, index);
306                 if (error)
307                         return error;
308         }
309
310         slot = radix_tree_indirect_to_ptr(root->rnode);
311
312         height = root->height;
313         shift = (height-1) * RADIX_TREE_MAP_SHIFT;
314
315         offset = 0;                     /* uninitialised var warning */
316         while (height > 0) {
317                 if (slot == NULL) {
318                         /* Have to add a child node.  */
319                         if (!(slot = radix_tree_node_alloc(root)))
320                                 return -ENOMEM;
321                         slot->height = height;
322                         if (node) {
323                                 rcu_assign_pointer(node->slots[offset], slot);
324                                 node->count++;
325                         } else
326                                 rcu_assign_pointer(root->rnode,
327                                         radix_tree_ptr_to_indirect(slot));
328                 }
329
330                 /* Go a level down */
331                 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
332                 node = slot;
333                 slot = node->slots[offset];
334                 shift -= RADIX_TREE_MAP_SHIFT;
335                 height--;
336         }
337
338         if (slot != NULL)
339                 return -EEXIST;
340
341         if (node) {
342                 node->count++;
343                 rcu_assign_pointer(node->slots[offset], item);
344                 BUG_ON(tag_get(node, 0, offset));
345                 BUG_ON(tag_get(node, 1, offset));
346         } else {
347                 rcu_assign_pointer(root->rnode, item);
348                 BUG_ON(root_tag_get(root, 0));
349                 BUG_ON(root_tag_get(root, 1));
350         }
351
352         return 0;
353 }
354 EXPORT_SYMBOL(radix_tree_insert);
355
356 /*
357  * is_slot == 1 : search for the slot.
358  * is_slot == 0 : search for the node.
359  */
360 static void *radix_tree_lookup_element(struct radix_tree_root *root,
361                                 unsigned long index, int is_slot)
362 {
363         unsigned int height, shift;
364         struct radix_tree_node *node, **slot;
365
366         node = rcu_dereference_raw(root->rnode);
367         if (node == NULL)
368                 return NULL;
369
370         if (!radix_tree_is_indirect_ptr(node)) {
371                 if (index > 0)
372                         return NULL;
373                 return is_slot ? (void *)&root->rnode : node;
374         }
375         node = radix_tree_indirect_to_ptr(node);
376
377         height = node->height;
378         if (index > radix_tree_maxindex(height))
379                 return NULL;
380
381         shift = (height-1) * RADIX_TREE_MAP_SHIFT;
382
383         do {
384                 slot = (struct radix_tree_node **)
385                         (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
386                 node = rcu_dereference_raw(*slot);
387                 if (node == NULL)
388                         return NULL;
389
390                 shift -= RADIX_TREE_MAP_SHIFT;
391                 height--;
392         } while (height > 0);
393
394         return is_slot ? (void *)slot:node;
395 }
396
397 /**
398  *      radix_tree_lookup_slot    -    lookup a slot in a radix tree
399  *      @root:          radix tree root
400  *      @index:         index key
401  *
402  *      Returns:  the slot corresponding to the position @index in the
403  *      radix tree @root. This is useful for update-if-exists operations.
404  *
405  *      This function can be called under rcu_read_lock iff the slot is not
406  *      modified by radix_tree_replace_slot, otherwise it must be called
407  *      exclusive from other writers. Any dereference of the slot must be done
408  *      using radix_tree_deref_slot.
409  */
410 void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
411 {
412         return (void **)radix_tree_lookup_element(root, index, 1);
413 }
414 EXPORT_SYMBOL(radix_tree_lookup_slot);
415
416 /**
417  *      radix_tree_lookup    -    perform lookup operation on a radix tree
418  *      @root:          radix tree root
419  *      @index:         index key
420  *
421  *      Lookup the item at the position @index in the radix tree @root.
422  *
423  *      This function can be called under rcu_read_lock, however the caller
424  *      must manage lifetimes of leaf nodes (eg. RCU may also be used to free
425  *      them safely). No RCU barriers are required to access or modify the
426  *      returned item, however.
427  */
428 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
429 {
430         return radix_tree_lookup_element(root, index, 0);
431 }
432 EXPORT_SYMBOL(radix_tree_lookup);
433
434 /**
435  *      radix_tree_tag_set - set a tag on a radix tree node
436  *      @root:          radix tree root
437  *      @index:         index key
438  *      @tag:           tag index
439  *
440  *      Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
441  *      corresponding to @index in the radix tree.  From
442  *      the root all the way down to the leaf node.
443  *
444  *      Returns the address of the tagged item.   Setting a tag on a not-present
445  *      item is a bug.
446  */
447 void *radix_tree_tag_set(struct radix_tree_root *root,
448                         unsigned long index, unsigned int tag)
449 {
450         unsigned int height, shift;
451         struct radix_tree_node *slot;
452
453         height = root->height;
454         BUG_ON(index > radix_tree_maxindex(height));
455
456         slot = radix_tree_indirect_to_ptr(root->rnode);
457         shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
458
459         while (height > 0) {
460                 int offset;
461
462                 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
463                 if (!tag_get(slot, tag, offset))
464                         tag_set(slot, tag, offset);
465                 slot = slot->slots[offset];
466                 BUG_ON(slot == NULL);
467                 shift -= RADIX_TREE_MAP_SHIFT;
468                 height--;
469         }
470
471         /* set the root's tag bit */
472         if (slot && !root_tag_get(root, tag))
473                 root_tag_set(root, tag);
474
475         return slot;
476 }
477 EXPORT_SYMBOL(radix_tree_tag_set);
478
479 /**
480  *      radix_tree_tag_clear - clear a tag on a radix tree node
481  *      @root:          radix tree root
482  *      @index:         index key
483  *      @tag:           tag index
484  *
485  *      Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
486  *      corresponding to @index in the radix tree.  If
487  *      this causes the leaf node to have no tags set then clear the tag in the
488  *      next-to-leaf node, etc.
489  *
490  *      Returns the address of the tagged item on success, else NULL.  ie:
491  *      has the same return value and semantics as radix_tree_lookup().
492  */
493 void *radix_tree_tag_clear(struct radix_tree_root *root,
494                         unsigned long index, unsigned int tag)
495 {
496         /*
497          * The radix tree path needs to be one longer than the maximum path
498          * since the "list" is null terminated.
499          */
500         struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
501         struct radix_tree_node *slot = NULL;
502         unsigned int height, shift;
503
504         height = root->height;
505         if (index > radix_tree_maxindex(height))
506                 goto out;
507
508         shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
509         pathp->node = NULL;
510         slot = radix_tree_indirect_to_ptr(root->rnode);
511
512         while (height > 0) {
513                 int offset;
514
515                 if (slot == NULL)
516                         goto out;
517
518                 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
519                 pathp[1].offset = offset;
520                 pathp[1].node = slot;
521                 slot = slot->slots[offset];
522                 pathp++;
523                 shift -= RADIX_TREE_MAP_SHIFT;
524                 height--;
525         }
526
527         if (slot == NULL)
528                 goto out;
529
530         while (pathp->node) {
531                 if (!tag_get(pathp->node, tag, pathp->offset))
532                         goto out;
533                 tag_clear(pathp->node, tag, pathp->offset);
534                 if (any_tag_set(pathp->node, tag))
535                         goto out;
536                 pathp--;
537         }
538
539         /* clear the root's tag bit */
540         if (root_tag_get(root, tag))
541                 root_tag_clear(root, tag);
542
543 out:
544         return slot;
545 }
546 EXPORT_SYMBOL(radix_tree_tag_clear);
547
548 /**
549  * radix_tree_tag_get - get a tag on a radix tree node
550  * @root:               radix tree root
551  * @index:              index key
552  * @tag:                tag index (< RADIX_TREE_MAX_TAGS)
553  *
554  * Return values:
555  *
556  *  0: tag not present or not set
557  *  1: tag set
558  *
559  * Note that the return value of this function may not be relied on, even if
560  * the RCU lock is held, unless tag modification and node deletion are excluded
561  * from concurrency.
562  */
563 int radix_tree_tag_get(struct radix_tree_root *root,
564                         unsigned long index, unsigned int tag)
565 {
566         unsigned int height, shift;
567         struct radix_tree_node *node;
568         int saw_unset_tag = 0;
569
570         /* check the root's tag bit */
571         if (!root_tag_get(root, tag))
572                 return 0;
573
574         node = rcu_dereference_raw(root->rnode);
575         if (node == NULL)
576                 return 0;
577
578         if (!radix_tree_is_indirect_ptr(node))
579                 return (index == 0);
580         node = radix_tree_indirect_to_ptr(node);
581
582         height = node->height;
583         if (index > radix_tree_maxindex(height))
584                 return 0;
585
586         shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
587
588         for ( ; ; ) {
589                 int offset;
590
591                 if (node == NULL)
592                         return 0;
593
594                 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
595
596                 /*
597                  * This is just a debug check.  Later, we can bale as soon as
598                  * we see an unset tag.
599                  */
600                 if (!tag_get(node, tag, offset))
601                         saw_unset_tag = 1;
602                 if (height == 1)
603                         return !!tag_get(node, tag, offset);
604                 node = rcu_dereference_raw(node->slots[offset]);
605                 shift -= RADIX_TREE_MAP_SHIFT;
606                 height--;
607         }
608 }
609 EXPORT_SYMBOL(radix_tree_tag_get);
610
611 /**
612  * radix_tree_range_tag_if_tagged - for each item in given range set given
613  *                                 tag if item has another tag set
614  * @root:               radix tree root
615  * @first_indexp:       pointer to a starting index of a range to scan
616  * @last_index:         last index of a range to scan
617  * @nr_to_tag:          maximum number items to tag
618  * @iftag:              tag index to test
619  * @settag:             tag index to set if tested tag is set
620  *
621  * This function scans range of radix tree from first_index to last_index
622  * (inclusive).  For each item in the range if iftag is set, the function sets
623  * also settag. The function stops either after tagging nr_to_tag items or
624  * after reaching last_index.
625  *
626  * The function returns number of leaves where the tag was set and sets
627  * *first_indexp to the first unscanned index.
628  * WARNING! *first_indexp can wrap if last_index is ULONG_MAX. Caller must
629  * be prepared to handle that.
630  */
631 unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
632                 unsigned long *first_indexp, unsigned long last_index,
633                 unsigned long nr_to_tag,
634                 unsigned int iftag, unsigned int settag)
635 {
636         unsigned int height = root->height, shift;
637         unsigned long tagged = 0, index = *first_indexp;
638         struct radix_tree_node *open_slots[height], *slot;
639
640         last_index = min(last_index, radix_tree_maxindex(height));
641         if (index > last_index)
642                 return 0;
643         if (!nr_to_tag)
644                 return 0;
645         if (!root_tag_get(root, iftag)) {
646                 *first_indexp = last_index + 1;
647                 return 0;
648         }
649         if (height == 0) {
650                 *first_indexp = last_index + 1;
651                 root_tag_set(root, settag);
652                 return 1;
653         }
654
655         shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
656         slot = radix_tree_indirect_to_ptr(root->rnode);
657
658         for (;;) {
659                 int offset;
660
661                 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
662                 if (!slot->slots[offset])
663                         goto next;
664                 if (!tag_get(slot, iftag, offset))
665                         goto next;
666                 tag_set(slot, settag, offset);
667                 if (height == 1) {
668                         tagged++;
669                         goto next;
670                 }
671                 /* Go down one level */
672                 height--;
673                 shift -= RADIX_TREE_MAP_SHIFT;
674                 open_slots[height] = slot;
675                 slot = slot->slots[offset];
676                 continue;
677 next:
678                 /* Go to next item at level determined by 'shift' */
679                 index = ((index >> shift) + 1) << shift;
680                 /* Overflow can happen when last_index is ~0UL... */
681                 if (index > last_index || !index)
682                         break;
683                 if (tagged >= nr_to_tag)
684                         break;
685                 while (((index >> shift) & RADIX_TREE_MAP_MASK) == 0) {
686                         /*
687                          * We've fully scanned this node. Go up. Because
688                          * last_index is guaranteed to be in the tree, what
689                          * we do below cannot wander astray.
690                          */
691                         slot = open_slots[height];
692                         height++;
693                         shift += RADIX_TREE_MAP_SHIFT;
694                 }
695         }
696         /*
697          * The iftag must have been set somewhere because otherwise
698          * we would return immediated at the beginning of the function
699          */
700         root_tag_set(root, settag);
701         *first_indexp = index;
702
703         return tagged;
704 }
705 EXPORT_SYMBOL(radix_tree_range_tag_if_tagged);
706
707
708 /**
709  *      radix_tree_next_hole    -    find the next hole (not-present entry)
710  *      @root:          tree root
711  *      @index:         index key
712  *      @max_scan:      maximum range to search
713  *
714  *      Search the set [index, min(index+max_scan-1, MAX_INDEX)] for the lowest
715  *      indexed hole.
716  *
717  *      Returns: the index of the hole if found, otherwise returns an index
718  *      outside of the set specified (in which case 'return - index >= max_scan'
719  *      will be true). In rare cases of index wrap-around, 0 will be returned.
720  *
721  *      radix_tree_next_hole may be called under rcu_read_lock. However, like
722  *      radix_tree_gang_lookup, this will not atomically search a snapshot of
723  *      the tree at a single point in time. For example, if a hole is created
724  *      at index 5, then subsequently a hole is created at index 10,
725  *      radix_tree_next_hole covering both indexes may return 10 if called
726  *      under rcu_read_lock.
727  */
728 unsigned long radix_tree_next_hole(struct radix_tree_root *root,
729                                 unsigned long index, unsigned long max_scan)
730 {
731         unsigned long i;
732
733         for (i = 0; i < max_scan; i++) {
734                 if (!radix_tree_lookup(root, index))
735                         break;
736                 index++;
737                 if (index == 0)
738                         break;
739         }
740
741         return index;
742 }
743 EXPORT_SYMBOL(radix_tree_next_hole);
744
745 /**
746  *      radix_tree_prev_hole    -    find the prev hole (not-present entry)
747  *      @root:          tree root
748  *      @index:         index key
749  *      @max_scan:      maximum range to search
750  *
751  *      Search backwards in the range [max(index-max_scan+1, 0), index]
752  *      for the first hole.
753  *
754  *      Returns: the index of the hole if found, otherwise returns an index
755  *      outside of the set specified (in which case 'index - return >= max_scan'
756  *      will be true). In rare cases of wrap-around, ULONG_MAX will be returned.
757  *
758  *      radix_tree_next_hole may be called under rcu_read_lock. However, like
759  *      radix_tree_gang_lookup, this will not atomically search a snapshot of
760  *      the tree at a single point in time. For example, if a hole is created
761  *      at index 10, then subsequently a hole is created at index 5,
762  *      radix_tree_prev_hole covering both indexes may return 5 if called under
763  *      rcu_read_lock.
764  */
765 unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
766                                    unsigned long index, unsigned long max_scan)
767 {
768         unsigned long i;
769
770         for (i = 0; i < max_scan; i++) {
771                 if (!radix_tree_lookup(root, index))
772                         break;
773                 index--;
774                 if (index == ULONG_MAX)
775                         break;
776         }
777
778         return index;
779 }
780 EXPORT_SYMBOL(radix_tree_prev_hole);
781
782 static unsigned int
783 __lookup(struct radix_tree_node *slot, void ***results, unsigned long index,
784         unsigned int max_items, unsigned long *next_index)
785 {
786         unsigned int nr_found = 0;
787         unsigned int shift, height;
788         unsigned long i;
789
790         height = slot->height;
791         if (height == 0)
792                 goto out;
793         shift = (height-1) * RADIX_TREE_MAP_SHIFT;
794
795         for ( ; height > 1; height--) {
796                 i = (index >> shift) & RADIX_TREE_MAP_MASK;
797                 for (;;) {
798                         if (slot->slots[i] != NULL)
799                                 break;
800                         index &= ~((1UL << shift) - 1);
801                         index += 1UL << shift;
802                         if (index == 0)
803                                 goto out;       /* 32-bit wraparound */
804                         i++;
805                         if (i == RADIX_TREE_MAP_SIZE)
806                                 goto out;
807                 }
808
809                 shift -= RADIX_TREE_MAP_SHIFT;
810                 slot = rcu_dereference_raw(slot->slots[i]);
811                 if (slot == NULL)
812                         goto out;
813         }
814
815         /* Bottom level: grab some items */
816         for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
817                 index++;
818                 if (slot->slots[i]) {
819                         results[nr_found++] = &(slot->slots[i]);
820                         if (nr_found == max_items)
821                                 goto out;
822                 }
823         }
824 out:
825         *next_index = index;
826         return nr_found;
827 }
828
829 /**
830  *      radix_tree_gang_lookup - perform multiple lookup on a radix tree
831  *      @root:          radix tree root
832  *      @results:       where the results of the lookup are placed
833  *      @first_index:   start the lookup from this key
834  *      @max_items:     place up to this many items at *results
835  *
836  *      Performs an index-ascending scan of the tree for present items.  Places
837  *      them at *@results and returns the number of items which were placed at
838  *      *@results.
839  *
840  *      The implementation is naive.
841  *
842  *      Like radix_tree_lookup, radix_tree_gang_lookup may be called under
843  *      rcu_read_lock. In this case, rather than the returned results being
844  *      an atomic snapshot of the tree at a single point in time, the semantics
845  *      of an RCU protected gang lookup are as though multiple radix_tree_lookups
846  *      have been issued in individual locks, and results stored in 'results'.
847  */
848 unsigned int
849 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
850                         unsigned long first_index, unsigned int max_items)
851 {
852         unsigned long max_index;
853         struct radix_tree_node *node;
854         unsigned long cur_index = first_index;
855         unsigned int ret;
856
857         node = rcu_dereference_raw(root->rnode);
858         if (!node)
859                 return 0;
860
861         if (!radix_tree_is_indirect_ptr(node)) {
862                 if (first_index > 0)
863                         return 0;
864                 results[0] = node;
865                 return 1;
866         }
867         node = radix_tree_indirect_to_ptr(node);
868
869         max_index = radix_tree_maxindex(node->height);
870
871         ret = 0;
872         while (ret < max_items) {
873                 unsigned int nr_found, slots_found, i;
874                 unsigned long next_index;       /* Index of next search */
875
876                 if (cur_index > max_index)
877                         break;
878                 slots_found = __lookup(node, (void ***)results + ret, cur_index,
879                                         max_items - ret, &next_index);
880                 nr_found = 0;
881                 for (i = 0; i < slots_found; i++) {
882                         struct radix_tree_node *slot;
883                         slot = *(((void ***)results)[ret + i]);
884                         if (!slot)
885                                 continue;
886                         results[ret + nr_found] = rcu_dereference_raw(slot);
887                         nr_found++;
888                 }
889                 ret += nr_found;
890                 if (next_index == 0)
891                         break;
892                 cur_index = next_index;
893         }
894
895         return ret;
896 }
897 EXPORT_SYMBOL(radix_tree_gang_lookup);
898
899 /**
900  *      radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree
901  *      @root:          radix tree root
902  *      @results:       where the results of the lookup are placed
903  *      @first_index:   start the lookup from this key
904  *      @max_items:     place up to this many items at *results
905  *
906  *      Performs an index-ascending scan of the tree for present items.  Places
907  *      their slots at *@results and returns the number of items which were
908  *      placed at *@results.
909  *
910  *      The implementation is naive.
911  *
912  *      Like radix_tree_gang_lookup as far as RCU and locking goes. Slots must
913  *      be dereferenced with radix_tree_deref_slot, and if using only RCU
914  *      protection, radix_tree_deref_slot may fail requiring a retry.
915  */
916 unsigned int
917 radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
918                         unsigned long first_index, unsigned int max_items)
919 {
920         unsigned long max_index;
921         struct radix_tree_node *node;
922         unsigned long cur_index = first_index;
923         unsigned int ret;
924
925         node = rcu_dereference_raw(root->rnode);
926         if (!node)
927                 return 0;
928
929         if (!radix_tree_is_indirect_ptr(node)) {
930                 if (first_index > 0)
931                         return 0;
932                 results[0] = (void **)&root->rnode;
933                 return 1;
934         }
935         node = radix_tree_indirect_to_ptr(node);
936
937         max_index = radix_tree_maxindex(node->height);
938
939         ret = 0;
940         while (ret < max_items) {
941                 unsigned int slots_found;
942                 unsigned long next_index;       /* Index of next search */
943
944                 if (cur_index > max_index)
945                         break;
946                 slots_found = __lookup(node, results + ret, cur_index,
947                                         max_items - ret, &next_index);
948                 ret += slots_found;
949                 if (next_index == 0)
950                         break;
951                 cur_index = next_index;
952         }
953
954         return ret;
955 }
956 EXPORT_SYMBOL(radix_tree_gang_lookup_slot);
957
958 /*
959  * FIXME: the two tag_get()s here should use find_next_bit() instead of
960  * open-coding the search.
961  */
962 static unsigned int
963 __lookup_tag(struct radix_tree_node *slot, void ***results, unsigned long index,
964         unsigned int max_items, unsigned long *next_index, unsigned int tag)
965 {
966         unsigned int nr_found = 0;
967         unsigned int shift, height;
968
969         height = slot->height;
970         if (height == 0)
971                 goto out;
972         shift = (height-1) * RADIX_TREE_MAP_SHIFT;
973
974         while (height > 0) {
975                 unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK ;
976
977                 for (;;) {
978                         if (tag_get(slot, tag, i))
979                                 break;
980                         index &= ~((1UL << shift) - 1);
981                         index += 1UL << shift;
982                         if (index == 0)
983                                 goto out;       /* 32-bit wraparound */
984                         i++;
985                         if (i == RADIX_TREE_MAP_SIZE)
986                                 goto out;
987                 }
988                 height--;
989                 if (height == 0) {      /* Bottom level: grab some items */
990                         unsigned long j = index & RADIX_TREE_MAP_MASK;
991
992                         for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
993                                 index++;
994                                 if (!tag_get(slot, tag, j))
995                                         continue;
996                                 /*
997                                  * Even though the tag was found set, we need to
998                                  * recheck that we have a non-NULL node, because
999                                  * if this lookup is lockless, it may have been
1000                                  * subsequently deleted.
1001                                  *
1002                                  * Similar care must be taken in any place that
1003                                  * lookup ->slots[x] without a lock (ie. can't
1004                                  * rely on its value remaining the same).
1005                                  */
1006                                 if (slot->slots[j]) {
1007                                         results[nr_found++] = &(slot->slots[j]);
1008                                         if (nr_found == max_items)
1009                                                 goto out;
1010                                 }
1011                         }
1012                 }
1013                 shift -= RADIX_TREE_MAP_SHIFT;
1014                 slot = rcu_dereference_raw(slot->slots[i]);
1015                 if (slot == NULL)
1016                         break;
1017         }
1018 out:
1019         *next_index = index;
1020         return nr_found;
1021 }
1022
1023 /**
1024  *      radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
1025  *                                   based on a tag
1026  *      @root:          radix tree root
1027  *      @results:       where the results of the lookup are placed
1028  *      @first_index:   start the lookup from this key
1029  *      @max_items:     place up to this many items at *results
1030  *      @tag:           the tag index (< RADIX_TREE_MAX_TAGS)
1031  *
1032  *      Performs an index-ascending scan of the tree for present items which
1033  *      have the tag indexed by @tag set.  Places the items at *@results and
1034  *      returns the number of items which were placed at *@results.
1035  */
1036 unsigned int
1037 radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
1038                 unsigned long first_index, unsigned int max_items,
1039                 unsigned int tag)
1040 {
1041         struct radix_tree_node *node;
1042         unsigned long max_index;
1043         unsigned long cur_index = first_index;
1044         unsigned int ret;
1045
1046         /* check the root's tag bit */
1047         if (!root_tag_get(root, tag))
1048                 return 0;
1049
1050         node = rcu_dereference_raw(root->rnode);
1051         if (!node)
1052                 return 0;
1053
1054         if (!radix_tree_is_indirect_ptr(node)) {
1055                 if (first_index > 0)
1056                         return 0;
1057                 results[0] = node;
1058                 return 1;
1059         }
1060         node = radix_tree_indirect_to_ptr(node);
1061
1062         max_index = radix_tree_maxindex(node->height);
1063
1064         ret = 0;
1065         while (ret < max_items) {
1066                 unsigned int nr_found, slots_found, i;
1067                 unsigned long next_index;       /* Index of next search */
1068
1069                 if (cur_index > max_index)
1070                         break;
1071                 slots_found = __lookup_tag(node, (void ***)results + ret,
1072                                 cur_index, max_items - ret, &next_index, tag);
1073                 nr_found = 0;
1074                 for (i = 0; i < slots_found; i++) {
1075                         struct radix_tree_node *slot;
1076                         slot = *(((void ***)results)[ret + i]);
1077                         if (!slot)
1078                                 continue;
1079                         results[ret + nr_found] = rcu_dereference_raw(slot);
1080                         nr_found++;
1081                 }
1082                 ret += nr_found;
1083                 if (next_index == 0)
1084                         break;
1085                 cur_index = next_index;
1086         }
1087
1088         return ret;
1089 }
1090 EXPORT_SYMBOL(radix_tree_gang_lookup_tag);
1091
1092 /**
1093  *      radix_tree_gang_lookup_tag_slot - perform multiple slot lookup on a
1094  *                                        radix tree based on a tag
1095  *      @root:          radix tree root
1096  *      @results:       where the results of the lookup are placed
1097  *      @first_index:   start the lookup from this key
1098  *      @max_items:     place up to this many items at *results
1099  *      @tag:           the tag index (< RADIX_TREE_MAX_TAGS)
1100  *
1101  *      Performs an index-ascending scan of the tree for present items which
1102  *      have the tag indexed by @tag set.  Places the slots at *@results and
1103  *      returns the number of slots which were placed at *@results.
1104  */
1105 unsigned int
1106 radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
1107                 unsigned long first_index, unsigned int max_items,
1108                 unsigned int tag)
1109 {
1110         struct radix_tree_node *node;
1111         unsigned long max_index;
1112         unsigned long cur_index = first_index;
1113         unsigned int ret;
1114
1115         /* check the root's tag bit */
1116         if (!root_tag_get(root, tag))
1117                 return 0;
1118
1119         node = rcu_dereference_raw(root->rnode);
1120         if (!node)
1121                 return 0;
1122
1123         if (!radix_tree_is_indirect_ptr(node)) {
1124                 if (first_index > 0)
1125                         return 0;
1126                 results[0] = (void **)&root->rnode;
1127                 return 1;
1128         }
1129         node = radix_tree_indirect_to_ptr(node);
1130
1131         max_index = radix_tree_maxindex(node->height);
1132
1133         ret = 0;
1134         while (ret < max_items) {
1135                 unsigned int slots_found;
1136                 unsigned long next_index;       /* Index of next search */
1137
1138                 if (cur_index > max_index)
1139                         break;
1140                 slots_found = __lookup_tag(node, results + ret,
1141                                 cur_index, max_items - ret, &next_index, tag);
1142                 ret += slots_found;
1143                 if (next_index == 0)
1144                         break;
1145                 cur_index = next_index;
1146         }
1147
1148         return ret;
1149 }
1150 EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot);
1151
1152
1153 /**
1154  *      radix_tree_shrink    -    shrink height of a radix tree to minimal
1155  *      @root           radix tree root
1156  */
1157 static inline void radix_tree_shrink(struct radix_tree_root *root)
1158 {
1159         /* try to shrink tree height */
1160         while (root->height > 0) {
1161                 struct radix_tree_node *to_free = root->rnode;
1162                 void *newptr;
1163
1164                 BUG_ON(!radix_tree_is_indirect_ptr(to_free));
1165                 to_free = radix_tree_indirect_to_ptr(to_free);
1166
1167                 /*
1168                  * The candidate node has more than one child, or its child
1169                  * is not at the leftmost slot, we cannot shrink.
1170                  */
1171                 if (to_free->count != 1)
1172                         break;
1173                 if (!to_free->slots[0])
1174                         break;
1175
1176                 /*
1177                  * We don't need rcu_assign_pointer(), since we are simply
1178                  * moving the node from one part of the tree to another. If
1179                  * it was safe to dereference the old pointer to it
1180                  * (to_free->slots[0]), it will be safe to dereference the new
1181                  * one (root->rnode).
1182                  */
1183                 newptr = to_free->slots[0];
1184                 if (root->height > 1)
1185                         newptr = radix_tree_ptr_to_indirect(newptr);
1186                 root->rnode = newptr;
1187                 root->height--;
1188                 radix_tree_node_free(to_free);
1189         }
1190 }
1191
1192 /**
1193  *      radix_tree_delete    -    delete an item from a radix tree
1194  *      @root:          radix tree root
1195  *      @index:         index key
1196  *
1197  *      Remove the item at @index from the radix tree rooted at @root.
1198  *
1199  *      Returns the address of the deleted item, or NULL if it was not present.
1200  */
1201 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
1202 {
1203         /*
1204          * The radix tree path needs to be one longer than the maximum path
1205          * since the "list" is null terminated.
1206          */
1207         struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
1208         struct radix_tree_node *slot = NULL;
1209         struct radix_tree_node *to_free;
1210         unsigned int height, shift;
1211         int tag;
1212         int offset;
1213
1214         height = root->height;
1215         if (index > radix_tree_maxindex(height))
1216                 goto out;
1217
1218         slot = root->rnode;
1219         if (height == 0) {
1220                 root_tag_clear_all(root);
1221                 root->rnode = NULL;
1222                 goto out;
1223         }
1224         slot = radix_tree_indirect_to_ptr(slot);
1225
1226         shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
1227         pathp->node = NULL;
1228
1229         do {
1230                 if (slot == NULL)
1231                         goto out;
1232
1233                 pathp++;
1234                 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
1235                 pathp->offset = offset;
1236                 pathp->node = slot;
1237                 slot = slot->slots[offset];
1238                 shift -= RADIX_TREE_MAP_SHIFT;
1239                 height--;
1240         } while (height > 0);
1241
1242         if (slot == NULL)
1243                 goto out;
1244
1245         /*
1246          * Clear all tags associated with the just-deleted item
1247          */
1248         for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
1249                 if (tag_get(pathp->node, tag, pathp->offset))
1250                         radix_tree_tag_clear(root, index, tag);
1251         }
1252
1253         to_free = NULL;
1254         /* Now free the nodes we do not need anymore */
1255         while (pathp->node) {
1256                 pathp->node->slots[pathp->offset] = NULL;
1257                 pathp->node->count--;
1258                 /*
1259                  * Queue the node for deferred freeing after the
1260                  * last reference to it disappears (set NULL, above).
1261                  */
1262                 if (to_free)
1263                         radix_tree_node_free(to_free);
1264
1265                 if (pathp->node->count) {
1266                         if (pathp->node ==
1267                                         radix_tree_indirect_to_ptr(root->rnode))
1268                                 radix_tree_shrink(root);
1269                         goto out;
1270                 }
1271
1272                 /* Node with zero slots in use so free it */
1273                 to_free = pathp->node;
1274                 pathp--;
1275
1276         }
1277         root_tag_clear_all(root);
1278         root->height = 0;
1279         root->rnode = NULL;
1280         if (to_free)
1281                 radix_tree_node_free(to_free);
1282
1283 out:
1284         return slot;
1285 }
1286 EXPORT_SYMBOL(radix_tree_delete);
1287
1288 /**
1289  *      radix_tree_tagged - test whether any items in the tree are tagged
1290  *      @root:          radix tree root
1291  *      @tag:           tag to test
1292  */
1293 int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag)
1294 {
1295         return root_tag_get(root, tag);
1296 }
1297 EXPORT_SYMBOL(radix_tree_tagged);
1298
1299 static void
1300 radix_tree_node_ctor(void *node)
1301 {
1302         memset(node, 0, sizeof(struct radix_tree_node));
1303 }
1304
1305 static __init unsigned long __maxindex(unsigned int height)
1306 {
1307         unsigned int width = height * RADIX_TREE_MAP_SHIFT;
1308         int shift = RADIX_TREE_INDEX_BITS - width;
1309
1310         if (shift < 0)
1311                 return ~0UL;
1312         if (shift >= BITS_PER_LONG)
1313                 return 0UL;
1314         return ~0UL >> shift;
1315 }
1316
1317 static __init void radix_tree_init_maxindex(void)
1318 {
1319         unsigned int i;
1320
1321         for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
1322                 height_to_maxindex[i] = __maxindex(i);
1323 }
1324
1325 static int radix_tree_callback(struct notifier_block *nfb,
1326                             unsigned long action,
1327                             void *hcpu)
1328 {
1329        int cpu = (long)hcpu;
1330        struct radix_tree_preload *rtp;
1331
1332        /* Free per-cpu pool of perloaded nodes */
1333        if (action == CPU_DEAD || action == CPU_DEAD_FROZEN) {
1334                rtp = &per_cpu(radix_tree_preloads, cpu);
1335                while (rtp->nr) {
1336                        kmem_cache_free(radix_tree_node_cachep,
1337                                        rtp->nodes[rtp->nr-1]);
1338                        rtp->nodes[rtp->nr-1] = NULL;
1339                        rtp->nr--;
1340                }
1341        }
1342        return NOTIFY_OK;
1343 }
1344
1345 void __init radix_tree_init(void)
1346 {
1347         radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
1348                         sizeof(struct radix_tree_node), 0,
1349                         SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
1350                         radix_tree_node_ctor);
1351         radix_tree_init_maxindex();
1352         hotcpu_notifier(radix_tree_callback, 0);
1353 }