Root/lib/radix-tree.c

Source at commit b386be689295730688885552666ea40b2e639b14 created 8 years 11 months ago.
By Maarten ter Huurne, Revert "MIPS: JZ4740: reset: Initialize hibernate wakeup counters."
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
48struct radix_tree_node {
49    unsigned int height; /* Height from the bottom */
50    unsigned int count;
51    union {
52        struct radix_tree_node *parent; /* Used when ascending tree */
53        struct rcu_head rcu_head; /* Used when freeing node */
54    };
55    void __rcu *slots[RADIX_TREE_MAP_SIZE];
56    unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
57};
58
59#define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
60#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
61                      RADIX_TREE_MAP_SHIFT))
62
63/*
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;
68
69/*
70 * Radix tree node cache.
71 */
72static struct kmem_cache *radix_tree_node_cachep;
73
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};
81static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
82
83static 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
93static inline gfp_t root_gfp_mask(struct radix_tree_root *root)
94{
95    return root->gfp_mask & __GFP_BITS_MASK;
96}
97
98static 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}
149/*
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{
156    struct radix_tree_node *ret = NULL;
157    gfp_t gfp_mask = root_gfp_mask(root);
158
159    if (!(gfp_mask & __GFP_WAIT)) {
160        struct radix_tree_preload *rtp;
161
162        /*
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         */
167        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    }
174    if (ret == NULL)
175        ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
176
177    BUG_ON(radix_tree_is_indirect_ptr(ret));
178    return ret;
179}
180
181static 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);
185    int i;
186
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     */
192    for (i = 0; i < RADIX_TREE_MAX_TAGS; i++)
193        tag_clear(node, i, 0);
194
195    node->slots[0] = NULL;
196    node->count = 0;
197
198    kmem_cache_free(radix_tree_node_cachep, node);
199}
200
201static inline void
202radix_tree_node_free(struct radix_tree_node *node)
203{
204    call_rcu(&node->rcu_head, radix_tree_node_rcu_free);
205}
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.
212 *
213 * To make use of this facility, the radix tree must be initialised without
214 * __GFP_WAIT being passed to INIT_RADIX_TREE().
215 */
216int radix_tree_preload(gfp_t gfp_mask)
217{
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();
226        node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
227        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}
240EXPORT_SYMBOL(radix_tree_preload);
241
242/*
243 * 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;
257    struct radix_tree_node *slot;
258    unsigned int height;
259    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
271    do {
272        unsigned int newheight;
273        if (!(node = radix_tree_node_alloc(root)))
274            return -ENOMEM;
275
276        /* Propagate the aggregated tag info into the new root */
277        for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
278            if (root_tag_get(root, tag))
279                tag_set(node, tag, 0);
280        }
281
282        /* Increase the height. */
283        newheight = root->height+1;
284        node->height = newheight;
285        node->count = 1;
286        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;
293        node = ptr_to_indirect(node);
294        rcu_assign_pointer(root->rnode, node);
295        root->height = newheight;
296    } 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{
312    struct radix_tree_node *node = NULL, *slot;
313    unsigned int height, shift;
314    int offset;
315    int error;
316
317    BUG_ON(radix_tree_is_indirect_ptr(item));
318
319    /* Make sure the tree is high enough. */
320    if (index > radix_tree_maxindex(root->height)) {
321        error = radix_tree_extend(root, index);
322        if (error)
323            return error;
324    }
325
326    slot = indirect_to_ptr(root->rnode);
327
328    height = root->height;
329    shift = (height-1) * RADIX_TREE_MAP_SHIFT;
330
331    offset = 0; /* uninitialised var warning */
332    while (height > 0) {
333        if (slot == NULL) {
334            /* Have to add a child node. */
335            if (!(slot = radix_tree_node_alloc(root)))
336                return -ENOMEM;
337            slot->height = height;
338            slot->parent = node;
339            if (node) {
340                rcu_assign_pointer(node->slots[offset], slot);
341                node->count++;
342            } else
343                rcu_assign_pointer(root->rnode, ptr_to_indirect(slot));
344        }
345
346        /* Go a level down */
347        offset = (index >> shift) & RADIX_TREE_MAP_MASK;
348        node = slot;
349        slot = node->slots[offset];
350        shift -= RADIX_TREE_MAP_SHIFT;
351        height--;
352    }
353
354    if (slot != NULL)
355        return -EEXIST;
356
357    if (node) {
358        node->count++;
359        rcu_assign_pointer(node->slots[offset], item);
360        BUG_ON(tag_get(node, 0, offset));
361        BUG_ON(tag_get(node, 1, offset));
362    } else {
363        rcu_assign_pointer(root->rnode, item);
364        BUG_ON(root_tag_get(root, 0));
365        BUG_ON(root_tag_get(root, 1));
366    }
367
368    return 0;
369}
370EXPORT_SYMBOL(radix_tree_insert);
371
372/*
373 * is_slot == 1 : search for the slot.
374 * is_slot == 0 : search for the node.
375 */
376static void *radix_tree_lookup_element(struct radix_tree_root *root,
377                unsigned long index, int is_slot)
378{
379    unsigned int height, shift;
380    struct radix_tree_node *node, **slot;
381
382    node = rcu_dereference_raw(root->rnode);
383    if (node == NULL)
384        return NULL;
385
386    if (!radix_tree_is_indirect_ptr(node)) {
387        if (index > 0)
388            return NULL;
389        return is_slot ? (void *)&root->rnode : node;
390    }
391    node = indirect_to_ptr(node);
392
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));
402        node = rcu_dereference_raw(*slot);
403        if (node == NULL)
404            return NULL;
405
406        shift -= RADIX_TREE_MAP_SHIFT;
407        height--;
408    } while (height > 0);
409
410    return is_slot ? (void *)slot : indirect_to_ptr(node);
411}
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);
429}
430EXPORT_SYMBOL(radix_tree_lookup_slot);
431
432/**
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.
438 *
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.
443 */
444void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
445{
446    return radix_tree_lookup_element(root, index, 0);
447}
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 *
456 * Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
457 * corresponding to @index in the radix tree. From
458 * 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,
464            unsigned long index, unsigned int tag)
465{
466    unsigned int height, shift;
467    struct radix_tree_node *slot;
468
469    height = root->height;
470    BUG_ON(index > radix_tree_maxindex(height));
471
472    slot = indirect_to_ptr(root->rnode);
473    shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
474
475    while (height > 0) {
476        int offset;
477
478        offset = (index >> shift) & RADIX_TREE_MAP_MASK;
479        if (!tag_get(slot, tag, offset))
480            tag_set(slot, tag, offset);
481        slot = slot->slots[offset];
482        BUG_ON(slot == NULL);
483        shift -= RADIX_TREE_MAP_SHIFT;
484        height--;
485    }
486
487    /* set the root's tag bit */
488    if (slot && !root_tag_get(root, tag))
489        root_tag_set(root, tag);
490
491    return slot;
492}
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 *
501 * Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
502 * corresponding to @index in the radix tree. If
503 * 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,
510            unsigned long index, unsigned int tag)
511{
512    struct radix_tree_node *node = NULL;
513    struct radix_tree_node *slot = NULL;
514    unsigned int height, shift;
515    int uninitialized_var(offset);
516
517    height = root->height;
518    if (index > radix_tree_maxindex(height))
519        goto out;
520
521    shift = height * RADIX_TREE_MAP_SHIFT;
522    slot = indirect_to_ptr(root->rnode);
523
524    while (shift) {
525        if (slot == NULL)
526            goto out;
527
528        shift -= RADIX_TREE_MAP_SHIFT;
529        offset = (index >> shift) & RADIX_TREE_MAP_MASK;
530        node = slot;
531        slot = slot->slots[offset];
532    }
533
534    if (slot == NULL)
535        goto out;
536
537    while (node) {
538        if (!tag_get(node, tag, offset))
539            goto out;
540        tag_clear(node, tag, offset);
541        if (any_tag_set(node, tag))
542            goto out;
543
544        index >>= RADIX_TREE_MAP_SHIFT;
545        offset = index & RADIX_TREE_MAP_MASK;
546        node = node->parent;
547    }
548
549    /* clear the root's tag bit */
550    if (root_tag_get(root, tag))
551        root_tag_clear(root, tag);
552
553out:
554    return slot;
555}
556EXPORT_SYMBOL(radix_tree_tag_clear);
557
558/**
559 * radix_tree_tag_get - get a tag on a radix tree node
560 * @root: radix tree root
561 * @index: index key
562 * @tag: tag index (< RADIX_TREE_MAX_TAGS)
563 *
564 * Return values:
565 *
566 * 0: tag not present or not set
567 * 1: tag set
568 *
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.
572 */
573int radix_tree_tag_get(struct radix_tree_root *root,
574            unsigned long index, unsigned int tag)
575{
576    unsigned int height, shift;
577    struct radix_tree_node *node;
578
579    /* check the root's tag bit */
580    if (!root_tag_get(root, tag))
581        return 0;
582
583    node = rcu_dereference_raw(root->rnode);
584    if (node == NULL)
585        return 0;
586
587    if (!radix_tree_is_indirect_ptr(node))
588        return (index == 0);
589    node = indirect_to_ptr(node);
590
591    height = node->height;
592    if (index > radix_tree_maxindex(height))
593        return 0;
594
595    shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
596
597    for ( ; ; ) {
598        int offset;
599
600        if (node == NULL)
601            return 0;
602
603        offset = (index >> shift) & RADIX_TREE_MAP_MASK;
604        if (!tag_get(node, tag, offset))
605            return 0;
606        if (height == 1)
607            return 1;
608        node = rcu_dereference_raw(node->slots[offset]);
609        shift -= RADIX_TREE_MAP_SHIFT;
610        height--;
611    }
612}
613EXPORT_SYMBOL(radix_tree_tag_get);
614
615/**
616 * 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 *
630 * 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 *
637 * The function returns number of leaves where the tag was set and sets
638 * *first_indexp to the first unscanned index.
639 * WARNING! *first_indexp can wrap if last_index is ULONG_MAX. Caller must
640 * be prepared to handle that.
641 */
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{
647    unsigned int height = root->height;
648    struct radix_tree_node *node = NULL;
649    struct radix_tree_node *slot;
650    unsigned int shift;
651    unsigned long tagged = 0;
652    unsigned long index = *first_indexp;
653
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;
670    slot = indirect_to_ptr(root->rnode);
671
672    for (;;) {
673        unsigned long upindex;
674        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;
681        if (shift) {
682            /* Go down one level */
683            shift -= RADIX_TREE_MAP_SHIFT;
684            node = slot;
685            slot = slot->slots[offset];
686            continue;
687        }
688
689        /* tag the leaf */
690        tagged++;
691        tag_set(slot, settag, offset);
692
693        /* walk back up the path tagging interior nodes */
694        upindex = index;
695        while (node) {
696            upindex >>= RADIX_TREE_MAP_SHIFT;
697            offset = upindex & RADIX_TREE_MAP_MASK;
698
699            /* stop if we find a node with the tag already set */
700            if (tag_get(node, settag, offset))
701                break;
702            tag_set(node, settag, offset);
703            node = node->parent;
704        }
705
706        /*
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
715next:
716        /* Go to next item at level determined by 'shift' */
717        index = ((index >> shift) + 1) << shift;
718        /* Overflow can happen when last_index is ~0UL... */
719        if (index > last_index || !index)
720            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             */
729            slot = slot->parent;
730            shift += RADIX_TREE_MAP_SHIFT;
731        }
732    }
733    /*
734     * 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.
736     */
737    if (tagged > 0)
738        root_tag_set(root, settag);
739    *first_indexp = index;
740
741    return tagged;
742}
743EXPORT_SYMBOL(radix_tree_range_tag_if_tagged);
744
745
746/**
747 * 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'
757 * will be true). In rare cases of index wrap-around, 0 will be returned.
758 *
759 * radix_tree_next_hole may be called under rcu_read_lock. However, like
760 * 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.
765 */
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
783/**
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'
794 * will be true). In rare cases of wrap-around, ULONG_MAX will be returned.
795 *
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--;
812        if (index == ULONG_MAX)
813            break;
814    }
815
816    return index;
817}
818EXPORT_SYMBOL(radix_tree_prev_hole);
819
820static unsigned int
821__lookup(struct radix_tree_node *slot, void ***results, unsigned long *indices,
822    unsigned long index, unsigned int max_items, unsigned long *next_index)
823{
824    unsigned int nr_found = 0;
825    unsigned int shift, height;
826    unsigned long i;
827
828    height = slot->height;
829    if (height == 0)
830        goto out;
831    shift = (height-1) * RADIX_TREE_MAP_SHIFT;
832
833    for ( ; height > 1; height--) {
834        i = (index >> shift) & RADIX_TREE_MAP_MASK;
835        for (;;) {
836            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 */
842            i++;
843            if (i == RADIX_TREE_MAP_SIZE)
844                goto out;
845        }
846
847        shift -= RADIX_TREE_MAP_SHIFT;
848        slot = rcu_dereference_raw(slot->slots[i]);
849        if (slot == NULL)
850            goto out;
851    }
852
853    /* Bottom level: grab some items */
854    for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
855        if (slot->slots[i]) {
856            results[nr_found] = &(slot->slots[i]);
857            if (indices)
858                indices[nr_found] = index;
859            if (++nr_found == max_items) {
860                index++;
861                goto out;
862            }
863        }
864        index++;
865    }
866out:
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.
883 *
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'.
889 */
890unsigned int
891radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
892            unsigned long first_index, unsigned int max_items)
893{
894    unsigned long max_index;
895    struct radix_tree_node *node;
896    unsigned long cur_index = first_index;
897    unsigned int ret;
898
899    node = rcu_dereference_raw(root->rnode);
900    if (!node)
901        return 0;
902
903    if (!radix_tree_is_indirect_ptr(node)) {
904        if (first_index > 0)
905            return 0;
906        results[0] = node;
907        return 1;
908    }
909    node = indirect_to_ptr(node);
910
911    max_index = radix_tree_maxindex(node->height);
912
913    ret = 0;
914    while (ret < max_items) {
915        unsigned int nr_found, slots_found, i;
916        unsigned long next_index; /* Index of next search */
917
918        if (cur_index > max_index)
919            break;
920        slots_found = __lookup(node, (void ***)results + ret, NULL,
921                cur_index, max_items - ret, &next_index);
922        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;
928            results[ret + nr_found] =
929                indirect_to_ptr(rcu_dereference_raw(slot));
930            nr_found++;
931        }
932        ret += nr_found;
933        if (next_index == 0)
934            break;
935        cur_index = next_index;
936    }
937
938    return ret;
939}
940EXPORT_SYMBOL(radix_tree_gang_lookup);
941
942/**
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
946 * @indices: where their indices should be placed (but usually NULL)
947 * @first_index: start the lookup from this key
948 * @max_items: place up to this many items at *results
949 *
950 * Performs an index-ascending scan of the tree for present items. Places
951 * their slots at *@results and returns the number of items which were
952 * placed at *@results.
953 *
954 * The implementation is naive.
955 *
956 * Like radix_tree_gang_lookup as far as RCU and locking goes. Slots must
957 * be dereferenced with radix_tree_deref_slot, and if using only RCU
958 * protection, radix_tree_deref_slot may fail requiring a retry.
959 */
960unsigned int
961radix_tree_gang_lookup_slot(struct radix_tree_root *root,
962            void ***results, unsigned long *indices,
963            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
970    node = rcu_dereference_raw(root->rnode);
971    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;
978        if (indices)
979            indices[0] = 0;
980        return 1;
981    }
982    node = indirect_to_ptr(node);
983
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;
993        slots_found = __lookup(node, results + ret,
994                indices ? indices + ret : NULL,
995                cur_index, max_items - ret, &next_index);
996        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
1006/*
1007 * FIXME: the two tag_get()s here should use find_next_bit() instead of
1008 * open-coding the search.
1009 */
1010static unsigned int
1011__lookup_tag(struct radix_tree_node *slot, void ***results, unsigned long index,
1012    unsigned int max_items, unsigned long *next_index, unsigned int tag)
1013{
1014    unsigned int nr_found = 0;
1015    unsigned int shift, height;
1016
1017    height = slot->height;
1018    if (height == 0)
1019        goto out;
1020    shift = (height-1) * RADIX_TREE_MAP_SHIFT;
1021
1022    while (height > 0) {
1023        unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK ;
1024
1025        for (;;) {
1026            if (tag_get(slot, tag, i))
1027                break;
1028            index &= ~((1UL << shift) - 1);
1029            index += 1UL << shift;
1030            if (index == 0)
1031                goto out; /* 32-bit wraparound */
1032            i++;
1033            if (i == RADIX_TREE_MAP_SIZE)
1034                goto out;
1035        }
1036        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++;
1042                if (!tag_get(slot, tag, j))
1043                    continue;
1044                /*
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                 */
1054                if (slot->slots[j]) {
1055                    results[nr_found++] = &(slot->slots[j]);
1056                    if (nr_found == max_items)
1057                        goto out;
1058                }
1059            }
1060        }
1061        shift -= RADIX_TREE_MAP_SHIFT;
1062        slot = rcu_dereference_raw(slot->slots[i]);
1063        if (slot == NULL)
1064            break;
1065    }
1066out:
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
1078 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
1079 *
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,
1086        unsigned long first_index, unsigned int max_items,
1087        unsigned int tag)
1088{
1089    struct radix_tree_node *node;
1090    unsigned long max_index;
1091    unsigned long cur_index = first_index;
1092    unsigned int ret;
1093
1094    /* check the root's tag bit */
1095    if (!root_tag_get(root, tag))
1096        return 0;
1097
1098    node = rcu_dereference_raw(root->rnode);
1099    if (!node)
1100        return 0;
1101
1102    if (!radix_tree_is_indirect_ptr(node)) {
1103        if (first_index > 0)
1104            return 0;
1105        results[0] = node;
1106        return 1;
1107    }
1108    node = indirect_to_ptr(node);
1109
1110    max_index = radix_tree_maxindex(node->height);
1111
1112    ret = 0;
1113    while (ret < max_items) {
1114        unsigned int nr_found, slots_found, i;
1115        unsigned long next_index; /* Index of next search */
1116
1117        if (cur_index > max_index)
1118            break;
1119        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;
1127            results[ret + nr_found] =
1128                indirect_to_ptr(rcu_dereference_raw(slot));
1129            nr_found++;
1130        }
1131        ret += nr_found;
1132        if (next_index == 0)
1133            break;
1134        cur_index = next_index;
1135    }
1136
1137    return ret;
1138}
1139EXPORT_SYMBOL(radix_tree_gang_lookup_tag);
1140
1141/**
1142 * 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
1168    node = rcu_dereference_raw(root->rnode);
1169    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    }
1178    node = indirect_to_ptr(node);
1179
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
1201#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 */
1293
1294/**
1295 * 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 */
1301    while (root->height > 0) {
1302        struct radix_tree_node *to_free = root->rnode;
1303        struct radix_tree_node *slot;
1304
1305        BUG_ON(!radix_tree_is_indirect_ptr(to_free));
1306        to_free = indirect_to_ptr(to_free);
1307
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
1317        /*
1318         * We don't need rcu_assign_pointer(), since we are simply
1319         * moving the node from one part of the tree to another: if it
1320         * was safe to dereference the old pointer to it
1321         * (to_free->slots[0]), it will be safe to dereference the new
1322         * one (root->rnode) as far as dependent read barriers go.
1323         */
1324        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;
1330        root->height--;
1331
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
1354        radix_tree_node_free(to_free);
1355    }
1356}
1357
1358/**
1359 * 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{
1369    struct radix_tree_node *node = NULL;
1370    struct radix_tree_node *slot = NULL;
1371    struct radix_tree_node *to_free;
1372    unsigned int height, shift;
1373    int tag;
1374    int uninitialized_var(offset);
1375
1376    height = root->height;
1377    if (index > radix_tree_maxindex(height))
1378        goto out;
1379
1380    slot = root->rnode;
1381    if (height == 0) {
1382        root_tag_clear_all(root);
1383        root->rnode = NULL;
1384        goto out;
1385    }
1386    slot = indirect_to_ptr(slot);
1387    shift = height * RADIX_TREE_MAP_SHIFT;
1388
1389    do {
1390        if (slot == NULL)
1391            goto out;
1392
1393        shift -= RADIX_TREE_MAP_SHIFT;
1394        offset = (index >> shift) & RADIX_TREE_MAP_MASK;
1395        node = slot;
1396        slot = slot->slots[offset];
1397    } while (shift);
1398
1399    if (slot == NULL)
1400        goto out;
1401
1402    /*
1403     * Clear all tags associated with the item to be deleted.
1404     * This way of doing it would be inefficient, but seldom is any set.
1405     */
1406    for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
1407        if (tag_get(node, tag, offset))
1408            radix_tree_tag_clear(root, index, tag);
1409    }
1410
1411    to_free = NULL;
1412    /* Now free the nodes we do not need anymore */
1413    while (node) {
1414        node->slots[offset] = NULL;
1415        node->count--;
1416        /*
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);
1422
1423        if (node->count) {
1424            if (node == indirect_to_ptr(root->rnode))
1425                radix_tree_shrink(root);
1426            goto out;
1427        }
1428
1429        /* Node with zero slots in use so free it */
1430        to_free = node;
1431
1432        index >>= RADIX_TREE_MAP_SHIFT;
1433        offset = index & RADIX_TREE_MAP_MASK;
1434        node = node->parent;
1435    }
1436
1437    root_tag_clear_all(root);
1438    root->height = 0;
1439    root->rnode = NULL;
1440    if (to_free)
1441        radix_tree_node_free(to_free);
1442
1443out:
1444    return slot;
1445}
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 */
1453int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag)
1454{
1455    return root_tag_get(root, tag);
1456}
1457EXPORT_SYMBOL(radix_tree_tagged);
1458
1459static void
1460radix_tree_node_ctor(void *node)
1461{
1462    memset(node, 0, sizeof(struct radix_tree_node));
1463}
1464
1465static __init unsigned long __maxindex(unsigned int height)
1466{
1467    unsigned int width = height * RADIX_TREE_MAP_SHIFT;
1468    int shift = RADIX_TREE_INDEX_BITS - width;
1469
1470    if (shift < 0)
1471        return ~0UL;
1472    if (shift >= BITS_PER_LONG)
1473        return 0UL;
1474    return ~0UL >> shift;
1475}
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
1485static 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 */
1493       if (action == CPU_DEAD || action == CPU_DEAD_FROZEN) {
1494               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}
1504
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,
1509            SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
1510            radix_tree_node_ctor);
1511    radix_tree_init_maxindex();
1512    hotcpu_notifier(radix_tree_callback, 0);
1513}
1514

Archive Download this file



interactive