Merge branch 'wireless-devel' into master-devel

[linux-2.6/zen-sources.git] / lib / radix-tree.c

/*
 * Copyright (C) 2001 Momchil Velikov
 * Portions Copyright (C) 2001 Christoph Hellwig
 * Copyright (C) 2005 SGI, Christoph Lameter <clameter@sgi.com>
 * Copyright (C) 2006 Nick Piggin
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2, or (at
 * your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

#include <linux/errno.h>
#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/radix-tree.h>
#include <linux/percpu.h>
#include <linux/slab.h>
#include <linux/notifier.h>
#include <linux/cpu.h>
#include <linux/gfp.h>
#include <linux/string.h>
#include <linux/bitops.h>
#include <linux/rcupdate.h>
#include <linux/spinlock.h>


#ifdef __KERNEL__
#define RADIX_TREE_MAP_SHIFT    (CONFIG_BASE_SMALL ? 4 : 6)
#else
#define RADIX_TREE_MAP_SHIFT    3       /* For more stressful testing */
#endif

#define RADIX_TREE_MAP_SIZE     (1UL << RADIX_TREE_MAP_SHIFT)
#define RADIX_TREE_MAP_MASK     (RADIX_TREE_MAP_SIZE-1)

#define RADIX_TREE_TAG_LONGS    \
        ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)

struct radix_tree_node {
        unsigned int    height;         /* Height from the bottom */
        unsigned int    count;
        struct rcu_head rcu_head;
        void            *slots[RADIX_TREE_MAP_SIZE];
        unsigned long   tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
#ifdef CONFIG_RADIX_TREE_CONCURRENT
        spinlock_t      lock;
#endif
};

struct radix_tree_path {
        struct radix_tree_node *node;
        int offset;
#ifdef CONFIG_RADIX_TREE_CONCURRENT
        spinlock_t *locked;
#endif
};

#define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))
#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
                                          RADIX_TREE_MAP_SHIFT))

/*
 * The height_to_maxindex array needs to be one deeper than the maximum
 * path as height 0 holds only 1 entry.
 */
static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly;

#ifdef CONFIG_RADIX_TREE_CONCURRENT
static struct lock_class_key radix_node_class[RADIX_TREE_MAX_PATH];
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
static const char *radix_node_key_string[RADIX_TREE_MAX_PATH] = {
        "radix-node-00",
        "radix-node-01",
        "radix-node-02",
        "radix-node-03",
        "radix-node-04",
        "radix-node-05",
        "radix-node-06",
        "radix-node-07",
        "radix-node-08",
        "radix-node-09",
        "radix-node-10",
        "radix-node-11",
        "radix-node-12",
        "radix-node-13",
        "radix-node-14",
        "radix-node-15",
};
#endif

#ifdef CONFIG_RADIX_TREE_OPTIMISTIC
static DEFINE_PER_CPU(unsigned long[RADIX_TREE_MAX_PATH+1], optimistic_histogram);

static void optimistic_hit(unsigned long height)
{
        if (height > RADIX_TREE_MAX_PATH)
                height = RADIX_TREE_MAX_PATH;

        __get_cpu_var(optimistic_histogram)[height]++;
}

#ifdef CONFIG_PROC_FS

#include <linux/seq_file.h>
#include <linux/uaccess.h>

static void *frag_start(struct seq_file *m, loff_t *pos)
{
        if (*pos < 0 || *pos > RADIX_TREE_MAX_PATH)
                return NULL;

        m->private = (void *)(unsigned long)*pos;
        return pos;
}

static void *frag_next(struct seq_file *m, void *arg, loff_t *pos)
{
        if (*pos < RADIX_TREE_MAX_PATH) {
                (*pos)++;
                (*((unsigned long *)&m->private))++;
                return pos;
        }
        return NULL;
}

static void frag_stop(struct seq_file *m, void *arg)
{
}

unsigned long get_optimistic_stat(unsigned long index)
{
        unsigned long total = 0;
        int cpu;

        for_each_possible_cpu(cpu) {
                total += per_cpu(optimistic_histogram, cpu)[index];
        }
        return total;
}

static int frag_show(struct seq_file *m, void *arg)
{
        unsigned long index = (unsigned long)m->private;
        unsigned long hits = get_optimistic_stat(index);

        if (index == 0)
                seq_printf(m, "levels skipped\thits\n");

        if (index < RADIX_TREE_MAX_PATH)
                seq_printf(m, "%9lu\t%9lu\n", index, hits);
        else
                seq_printf(m, "failed\t%9lu\n", hits);

        return 0;
}

struct seq_operations optimistic_op = {
        .start = frag_start,
        .next = frag_next,
        .stop = frag_stop,
        .show = frag_show,
};

static void optimistic_reset(void)
{
        int cpu;
        int height;
        for_each_possible_cpu(cpu) {
                for (height = 0; height <= RADIX_TREE_MAX_PATH; height++)
                        per_cpu(optimistic_histogram, cpu)[height] = 0;
        }
}

ssize_t optimistic_write(struct file *file, const char __user *buf,
                size_t count, loff_t *ppos)
{
        if (count) {
                char c;
                if (get_user(c, buf))
                        return -EFAULT;
                if (c == '0')
                        optimistic_reset();
        }
        return count;
}

#endif // CONFIG_PROC_FS
#endif // CONFIG_RADIX_TREE_OPTIMISTIC

/*
 * Radix tree node cache.
 */
static struct kmem_cache *radix_tree_node_cachep;

/*
 * Per-cpu pool of preloaded nodes
 */
struct radix_tree_preload {
        int nr;
        struct radix_tree_node *nodes[RADIX_TREE_MAX_PATH];
};
DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };

static inline gfp_t root_gfp_mask(struct radix_tree_root *root)
{
        return root->gfp_mask & __GFP_BITS_MASK;
}

/*
 * This assumes that the caller has performed appropriate preallocation, and
 * that the caller has pinned this thread of control to the current CPU.
 */
static struct radix_tree_node *
radix_tree_node_alloc(struct radix_tree_root *root, int height)
{
        struct radix_tree_node *ret = NULL;
        gfp_t gfp_mask = root_gfp_mask(root);

        if (!(gfp_mask & __GFP_WAIT)) {
                struct radix_tree_preload *rtp;

                /*
                 * Provided the caller has preloaded here, we will always
                 * succeed in getting a node here (and never reach
                 * kmem_cache_alloc)
                 */
                rtp = &__get_cpu_var(radix_tree_preloads);
                if (rtp->nr) {
                        ret = rtp->nodes[rtp->nr - 1];
                        rtp->nodes[rtp->nr - 1] = NULL;
                        rtp->nr--;
                }
        }
        if (ret == NULL)
                ret = kmem_cache_alloc(radix_tree_node_cachep,
                                set_migrateflags(gfp_mask, __GFP_RECLAIMABLE));

        BUG_ON(radix_tree_is_indirect_ptr(ret));
#ifdef CONFIG_RADIX_TREE_CONCURRENT
        spin_lock_init(&ret->lock);
        lockdep_set_class_and_name(&ret->lock,
                        &radix_node_class[height],
                        radix_node_key_string[height]);
#endif
        ret->height = height;
        return ret;
}

static void radix_tree_node_rcu_free(struct rcu_head *head)
{
        struct radix_tree_node *node =
                        container_of(head, struct radix_tree_node, rcu_head);
        kmem_cache_free(radix_tree_node_cachep, node);
}

static inline void
radix_tree_node_free(struct radix_tree_node *node)
{
        call_rcu(&node->rcu_head, radix_tree_node_rcu_free);
}

/*
 * Load up this CPU's radix_tree_node buffer with sufficient objects to
 * ensure that the addition of a single element in the tree cannot fail.  On
 * success, return zero, with preemption disabled.  On error, return -ENOMEM
 * with preemption not disabled.
 */
int radix_tree_preload(gfp_t gfp_mask)
{
        struct radix_tree_preload *rtp;
        struct radix_tree_node *node;
        int ret = -ENOMEM;

        preempt_disable();
        rtp = &__get_cpu_var(radix_tree_preloads);
        while (rtp->nr < ARRAY_SIZE(rtp->nodes)) {
                preempt_enable();
                node = kmem_cache_alloc(radix_tree_node_cachep,
                                set_migrateflags(gfp_mask, __GFP_RECLAIMABLE));
                if (node == NULL)
                        goto out;
                preempt_disable();
                rtp = &__get_cpu_var(radix_tree_preloads);
                if (rtp->nr < ARRAY_SIZE(rtp->nodes))
                        rtp->nodes[rtp->nr++] = node;
                else
                        kmem_cache_free(radix_tree_node_cachep, node);
        }
        ret = 0;
out:
        return ret;
}
EXPORT_SYMBOL(radix_tree_preload);

static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
                int offset)
{
        __set_bit(offset, node->tags[tag]);
}

static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,
                int offset)
{
        __clear_bit(offset, node->tags[tag]);
}

static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
                int offset)
{
        return test_bit(offset, node->tags[tag]);
}

static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag)
{
        root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT));
}


static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag)
{
        root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT));
}

static inline void root_tag_clear_all(struct radix_tree_root *root)
{
        root->gfp_mask &= __GFP_BITS_MASK;
}

static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
{
        return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
}

/*
 * Returns 1 if any slot in the node has this tag set.
 * Otherwise returns 0.
 */
static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
{
        int idx;
        for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
                if (node->tags[tag][idx])
                        return 1;
        }
        return 0;
}

static inline int any_tag_set_but(struct radix_tree_node *node,
                unsigned int tag, int offset)
{
        int idx;
        int offset_idx = offset / BITS_PER_LONG;
        unsigned long offset_mask = ~(1UL << (offset % BITS_PER_LONG));
        for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
                unsigned long mask = ~0UL;
                if (idx == offset_idx)
                        mask = offset_mask;
                if (node->tags[tag][idx] & mask)
                        return 1;
        }
        return 0;
}

/*
 *      Return the maximum key which can be store into a
 *      radix tree with height HEIGHT.
 */
static inline unsigned long radix_tree_maxindex(unsigned int height)
{
        return height_to_maxindex[height];
}

/*
 *      Extend a radix tree so it can store key @index.
 */
static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
{
        struct radix_tree_node *node;
        unsigned int height;
        int tag;

        /* Figure out what the height should be.  */
        height = root->height + 1;
        while (index > radix_tree_maxindex(height))
                height++;

        if (root->rnode == NULL) {
                root->height = height;
                goto out;
        }

        do {
                unsigned int newheight = root->height + 1;
                if (!(node = radix_tree_node_alloc(root, newheight)))
                        return -ENOMEM;

                /* Increase the height.  */
                node->slots[0] = radix_tree_indirect_to_ptr(root->rnode);

                /* Propagate the aggregated tag info into the new root */
                for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
                        if (root_tag_get(root, tag))
                                tag_set(node, tag, 0);
                }

                node->count = 1;
                node = radix_tree_ptr_to_indirect(node);
                rcu_assign_pointer(root->rnode, node);
                root->height = newheight;
        } while (height > root->height);
out:
        return 0;
}

#ifdef CONFIG_RADIX_TREE_CONCURRENT
static inline struct radix_tree_context *
radix_tree_get_context(struct radix_tree_root **rootp)
{
        struct radix_tree_context *context = NULL;
        unsigned long addr = (unsigned long)*rootp;

        if (addr & 1) {
                context = (struct radix_tree_context *)(addr - 1);
                *rootp = context->root;
        }

        return context;
}

#define RADIX_TREE_CONTEXT(context, root) \
        struct radix_tree_context *context =    \
                radix_tree_get_context(&root)

static inline spinlock_t *radix_node_lock(struct radix_tree_root *root,
                struct radix_tree_node *node)
{
        spinlock_t *locked = &node->lock;
        spin_lock(locked);
        return locked;
}

static inline void radix_ladder_lock(struct radix_tree_context *context,
                struct radix_tree_node *node)
{
        if (context) {
                struct radix_tree_root *root = context->root;
                spinlock_t *locked = radix_node_lock(root, node);
                if (locked) {
                        spin_unlock(context->locked);
                        context->locked = locked;
                }
        }
}

static inline void radix_path_init(struct radix_tree_context *context,
                struct radix_tree_path *pathp)
{
        pathp->locked = context ? context->locked : NULL;
}

static inline void radix_path_lock(struct radix_tree_context *context,
                struct radix_tree_path *pathp, struct radix_tree_node *node)
{
        if (context) {
                struct radix_tree_root *root = context->root;
                spinlock_t *locked = radix_node_lock(root, node);
                if (locked)
                        context->locked = locked;
                pathp->locked = locked;
        } else
                pathp->locked = NULL;
}

static inline void radix_path_unlock(struct radix_tree_context *context,
                struct radix_tree_path *punlock)
{
        if (context && punlock->locked &&
                        context->locked != punlock->locked)
                spin_unlock(punlock->locked);
}
#else
#define RADIX_TREE_CONTEXT(context, root) do { } while (0)
#define radix_ladder_lock(context, node) do { } while (0)
#define radix_path_init(context, pathp) do { } while (0)
#define radix_path_lock(context, pathp, node) do { } while (0)
#define radix_path_unlock(context, punlock) do { } while (0)
#endif

#ifdef CONFIG_RADIX_TREE_OPTIMISTIC
typedef int (*radix_valid_fn)(struct radix_tree_node *, int, int);

static struct radix_tree_node *
radix_optimistic_lookup(struct radix_tree_context *context, unsigned long index,
                int tag, radix_valid_fn valid)
{
        unsigned int height, shift;
        struct radix_tree_node *node, *ret = NULL, **slot;
        struct radix_tree_root *root = context->root;

        node = rcu_dereference(root->rnode);
        if (node == NULL)
                return NULL;

        if (!radix_tree_is_indirect_ptr(node))
                        return NULL;

        node = radix_tree_indirect_to_ptr(node);

        height = node->height;
        if (index > radix_tree_maxindex(height))
                return NULL;

        shift = (height-1) * RADIX_TREE_MAP_SHIFT;
        do {
                int offset = (index >> shift) & RADIX_TREE_MAP_MASK;
                if ((*valid)(node, offset, tag))
                        ret = node;
                slot = (struct radix_tree_node **)(node->slots + offset);
                node = rcu_dereference(*slot);
                if (!node)
                        break;

                shift -= RADIX_TREE_MAP_SHIFT;
                height--;
        } while (height > 0);

        return ret;
}

static struct radix_tree_node *
__radix_optimistic_lock(struct radix_tree_context *context, unsigned long index,
                int tag, radix_valid_fn valid)
{
        struct radix_tree_node *node;
        spinlock_t *locked;
        unsigned int shift, offset;

        node = radix_optimistic_lookup(context, index, tag, valid);
        if (!node)
                goto out;

        locked = radix_node_lock(context->root, node);
        if (!locked)
                goto out;

#if 0
        if (node != radix_optimistic_lookup(context, index, tag, valid))
                goto out_unlock;
#else
        /* check if the node got freed */
        if (!node->count)
                goto out_unlock;

        /* check if the node is still a valid termination point */
        shift = (node->height - 1) * RADIX_TREE_MAP_SHIFT;
        offset = (index >> shift) & RADIX_TREE_MAP_MASK;
        if (!(*valid)(node, offset, tag))
                goto out_unlock;
#endif

        context->locked = locked;
        return node;

out_unlock:
        spin_unlock(locked);
out:
        return NULL;
}

static struct radix_tree_node *
radix_optimistic_lock(struct radix_tree_context *context, unsigned long index,
                int tag, radix_valid_fn valid)
{
        struct radix_tree_node *node = NULL;

        if (context) {
                node = __radix_optimistic_lock(context, index, tag, valid);
                if (!node) {
                        BUG_ON(context->locked);
                        spin_lock(&context->root->lock);
                        context->locked = &context->root->lock;
                        optimistic_hit(RADIX_TREE_MAX_PATH);
                } else
                        optimistic_hit(context->root->height - node->height);
        }
        return node;
}

static int radix_valid_always(struct radix_tree_node *node, int offset, int tag)
{
        return 1;
}

static int radix_valid_tag(struct radix_tree_node *node, int offset, int tag)
{
        return tag_get(node, tag, offset);
}
#else
#define radix_optimistic_lock(context, index, tag, valid) NULL
#endif

/**
 *      radix_tree_insert    -    insert into a radix tree
 *      @root:          radix tree root
 *      @index:         index key
 *      @item:          item to insert
 *
 *      Insert an item into the radix tree at position @index.
 */
int radix_tree_insert(struct radix_tree_root *root,
                        unsigned long index, void *item)
{
        struct radix_tree_node *node = NULL, *slot;
        unsigned int height, shift;
        int offset;
        int error;
        int tag;
        RADIX_TREE_CONTEXT(context, root);

        BUG_ON(radix_tree_is_indirect_ptr(item));

        node = radix_optimistic_lock(context, index, 0, radix_valid_always);
        if (node) {
                height = node->height;
                shift = (height-1) * RADIX_TREE_MAP_SHIFT;
                goto optimistic;
        }

        /* Make sure the tree is high enough.  */
        if (index > radix_tree_maxindex(root->height)) {
                error = radix_tree_extend(root, index);
                if (error)
                        return error;
        }

        slot = radix_tree_indirect_to_ptr(root->rnode);
        height = root->height;
        shift = (height-1) * RADIX_TREE_MAP_SHIFT;

        offset = 0;                     /* uninitialised var warning */
        while (height > 0) {
                if (slot == NULL) {
                        /* Have to add a child node.  */
                        if (!(slot = radix_tree_node_alloc(root, height)))
                                return -ENOMEM;
                        if (node) {
                                rcu_assign_pointer(node->slots[offset], slot);
                                node->count++;
                        } else
                                rcu_assign_pointer(root->rnode,
                                        radix_tree_ptr_to_indirect(slot));
                }

                /* Go a level down */
                node = slot;
                radix_ladder_lock(context, node);

optimistic:
                offset = (index >> shift) & RADIX_TREE_MAP_MASK;
                slot = node->slots[offset];
                shift -= RADIX_TREE_MAP_SHIFT;
                height--;
        }

        if (slot != NULL)
                return -EEXIST;

        if (node) {
                node->count++;
                rcu_assign_pointer(node->slots[offset], item);
                for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
                        BUG_ON(tag_get(node, tag, offset));
        } else {
                rcu_assign_pointer(root->rnode, item);
                for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
                        BUG_ON(root_tag_get(root, tag));
        }

        return 0;
}
EXPORT_SYMBOL(radix_tree_insert);

/**
 *      radix_tree_lookup_slot    -    lookup a slot in a radix tree
 *      @root:          radix tree root
 *      @index:         index key
 *
 *      Returns:  the slot corresponding to the position @index in the
 *      radix tree @root. This is useful for update-if-exists operations.
 *
 *      This function can be called under rcu_read_lock iff the slot is not
 *      modified by radix_tree_replace_slot, otherwise it must be called
 *      exclusive from other writers. Any dereference of the slot must be done
 *      using radix_tree_deref_slot.
 */
void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
{
        unsigned int height, shift;
        struct radix_tree_node *node, **slot;

        node = rcu_dereference(root->rnode);
        if (node == NULL)
                return NULL;

        if (!radix_tree_is_indirect_ptr(node)) {
                if (index > 0)
                        return NULL;
                return (void **)&root->rnode;
        }
        node = radix_tree_indirect_to_ptr(node);

        height = node->height;
        if (index > radix_tree_maxindex(height))
                return NULL;

        shift = (height-1) * RADIX_TREE_MAP_SHIFT;

        do {
                slot = (struct radix_tree_node **)
                        (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
                node = rcu_dereference(*slot);
                if (node == NULL)
                        return NULL;

                shift -= RADIX_TREE_MAP_SHIFT;
                height--;
        } while (height > 0);

        return (void **)slot;
}
EXPORT_SYMBOL(radix_tree_lookup_slot);

/**
 *      radix_tree_lookup    -    perform lookup operation on a radix tree
 *      @root:          radix tree root
 *      @index:         index key
 *
 *      Lookup the item at the position @index in the radix tree @root.
 *
 *      This function can be called under rcu_read_lock, however the caller
 *      must manage lifetimes of leaf nodes (eg. RCU may also be used to free
 *      them safely). No RCU barriers are required to access or modify the
 *      returned item, however.
 */
void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
{
        unsigned int height, shift;
        struct radix_tree_node *node, **slot;
        RADIX_TREE_CONTEXT(context, root);

        node = radix_optimistic_lock(context, index, 0, radix_valid_always);
        if (node)
                goto optimistic;

        node = rcu_dereference(root->rnode);
        if (node == NULL)
                return NULL;

        if (!radix_tree_is_indirect_ptr(node)) {
                if (index > 0)
                        return NULL;
                return node;
        }
        node = radix_tree_indirect_to_ptr(node);

optimistic:
        height = node->height;
        if (index > radix_tree_maxindex(height))
                return NULL;

        shift = (height-1) * RADIX_TREE_MAP_SHIFT;

        do {
                slot = (struct radix_tree_node **)
                        (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
                node = rcu_dereference(*slot);
                if (node == NULL)
                        return NULL;

                radix_ladder_lock(context, node);

                shift -= RADIX_TREE_MAP_SHIFT;
                height--;
        } while (height > 0);

        return node;
}
EXPORT_SYMBOL(radix_tree_lookup);

/**
 *      radix_tree_tag_set - set a tag on a radix tree node
 *      @root:          radix tree root
 *      @index:         index key
 *      @tag:           tag index
 *
 *      Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
 *      corresponding to @index in the radix tree.  From
 *      the root all the way down to the leaf node.
 *
 *      Returns the address of the tagged item.   Setting a tag on a not-present
 *      item is a bug.
 */
void *radix_tree_tag_set(struct radix_tree_root *root,
                        unsigned long index, unsigned int tag)
{
        unsigned int height, shift;
        struct radix_tree_node *slot;
        RADIX_TREE_CONTEXT(context, root);

        slot = radix_optimistic_lock(context, index, tag, radix_valid_tag);
        if (slot) {
                height = slot->height;
                shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
                goto optimistic;
        }

        height = root->height;
        BUG_ON(index > radix_tree_maxindex(height));

        slot = radix_tree_indirect_to_ptr(root->rnode);
        shift = (height - 1) * RADIX_TREE_MAP_SHIFT;

        /* set the root's tag bit */
        if (slot && !root_tag_get(root, tag))
                root_tag_set(root, tag);

        while (height > 0) {
                int offset;

                radix_ladder_lock(context, slot);

optimistic:
                offset = (index >> shift) & RADIX_TREE_MAP_MASK;
                if (!tag_get(slot, tag, offset))
                        tag_set(slot, tag, offset);
                slot = slot->slots[offset];
                BUG_ON(slot == NULL);
                shift -= RADIX_TREE_MAP_SHIFT;
                height--;
        }

        return slot;
}
EXPORT_SYMBOL(radix_tree_tag_set);

/*
 * the change can never propagate upwards from here.
 */
static
int radix_valid_tag_clear(struct radix_tree_node *node, int offset, int tag)
{
        int this, other;

        this = tag_get(node, tag, offset);
        other = any_tag_set_but(node, tag, offset);

        return !this || other;
}

/**
 *      radix_tree_tag_clear - clear a tag on a radix tree node
 *      @root:          radix tree root
 *      @index:         index key
 *      @tag:           tag index
 *
 *      Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
 *      corresponding to @index in the radix tree.  If
 *      this causes the leaf node to have no tags set then clear the tag in the
 *      next-to-leaf node, etc.
 *
 *      Returns the address of the tagged item on success, else NULL.  ie:
 *      has the same return value and semantics as radix_tree_lookup().
 */
void *radix_tree_tag_clear(struct radix_tree_root *root,
                        unsigned long index, unsigned int tag)
{
        /*
         * The radix tree path needs to be one longer than the maximum path
         * since the "list" is null terminated.
         */
        struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
        struct radix_tree_path *punlock = path, *piter;
        struct radix_tree_node *slot = NULL;
        unsigned int height, shift, offset;

        RADIX_TREE_CONTEXT(context, root);

        slot = radix_optimistic_lock(context, index, tag,
                        radix_valid_tag_clear);
        if (slot) {
                height = slot->height;
                shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
                offset = (index >> shift) & RADIX_TREE_MAP_MASK;
                pathp->offset = offset;
                pathp->node = slot;
                radix_path_init(context, pathp);
                goto optimistic;
        }

        pathp->node = NULL;
        radix_path_init(context, pathp);

        height = root->height;
        if (index > radix_tree_maxindex(height))
                goto out;

        shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
        slot = radix_tree_indirect_to_ptr(root->rnode);

        while (height > 0) {
                if (slot == NULL)
                        goto out;

                offset = (index >> shift) & RADIX_TREE_MAP_MASK;
                pathp++;
                pathp->offset = offset;
                pathp->node = slot;
                radix_path_lock(context, pathp, slot);

                if (radix_valid_tag_clear(slot, offset, tag)) {
                        for (; punlock < pathp; punlock++)
                                radix_path_unlock(context, punlock);
                }

optimistic:
                slot = slot->slots[offset];
                shift -= RADIX_TREE_MAP_SHIFT;
                height--;
        }

        if (slot == NULL)
                goto out;

        for (piter = pathp; piter >= punlock; piter--) {
                if (piter->node) {
                        if (!tag_get(piter->node, tag, piter->offset))
                                break;
                        tag_clear(piter->node, tag, piter->offset);
                        if (any_tag_set(piter->node, tag))
                                break;
                } else {
                        if (root_tag_get(root, tag))
                                root_tag_clear(root, tag);
                }
        }

out:
        for (; punlock < pathp; punlock++)
                radix_path_unlock(context, punlock);
        return slot;
}
EXPORT_SYMBOL(radix_tree_tag_clear);

#ifndef __KERNEL__      /* Only the test harness uses this at present */
/**
 * radix_tree_tag_get - get a tag on a radix tree node
 * @root:               radix tree root
 * @index:              index key
 * @tag:                tag index (< RADIX_TREE_MAX_TAGS)
 *
 * Return values:
 *
 *  0: tag not present or not set
 *  1: tag set
 */
int radix_tree_tag_get(struct radix_tree_root *root,
                        unsigned long index, unsigned int tag)
{
        unsigned int height, shift;
        struct radix_tree_node *node;
        int saw_unset_tag = 0;

        /* check the root's tag bit */
        if (!root_tag_get(root, tag))
                return 0;

        node = rcu_dereference(root->rnode);
        if (node == NULL)
                return 0;

        if (!radix_tree_is_indirect_ptr(node))
                return (index == 0);
        node = radix_tree_indirect_to_ptr(node);

        height = node->height;
        if (index > radix_tree_maxindex(height))
                return 0;

        shift = (height - 1) * RADIX_TREE_MAP_SHIFT;

        for ( ; ; ) {
                int offset;

                if (node == NULL)
                        return 0;

                offset = (index >> shift) & RADIX_TREE_MAP_MASK;

                /*
                 * This is just a debug check.  Later, we can bale as soon as
                 * we see an unset tag.
                 */
                if (!tag_get(node, tag, offset))
                        saw_unset_tag = 1;
                if (height == 1) {
                        int ret = tag_get(node, tag, offset);

                        BUG_ON(ret && saw_unset_tag);
                        return !!ret;
                }
                node = rcu_dereference(node->slots[offset]);
                shift -= RADIX_TREE_MAP_SHIFT;
                height--;
        }
}
EXPORT_SYMBOL(radix_tree_tag_get);
#endif

/**
 *      radix_tree_next_hole    -    find the next hole (not-present entry)
 *      @root:          tree root
 *      @index:         index key
 *      @max_scan:      maximum range to search
 *
 *      Search the set [index, min(index+max_scan-1, MAX_INDEX)] for the lowest
 *      indexed hole.
 *
 *      Returns: the index of the hole if found, otherwise returns an index
 *      outside of the set specified (in which case 'return - index >= max_scan'
 *      will be true).
 *
 *      radix_tree_next_hole may be called under rcu_read_lock. However, like
 *      radix_tree_gang_lookup, this will not atomically search a snapshot of the
 *      tree at a single point in time. For example, if a hole is created at index
 *      5, then subsequently a hole is created at index 10, radix_tree_next_hole
 *      covering both indexes may return 10 if called under rcu_read_lock.
 */
unsigned long radix_tree_next_hole(struct radix_tree_root *root,
                                unsigned long index, unsigned long max_scan)
{
        unsigned long i;

        for (i = 0; i < max_scan; i++) {
                if (!radix_tree_lookup(root, index))
                        break;
                index++;
                if (index == 0)
                        break;
        }

        return index;
}
EXPORT_SYMBOL(radix_tree_next_hole);

static unsigned int
__lookup(struct radix_tree_node *slot, void ***results, unsigned long index,
        unsigned int max_items, unsigned long *next_index)
{
        unsigned int nr_found = 0;
        unsigned int shift, height;
        unsigned long i;

        height = slot->height;
        if (height == 0)
                goto out;
        shift = (height-1) * RADIX_TREE_MAP_SHIFT;

        for ( ; height > 1; height--) {
                i = (index >> shift) & RADIX_TREE_MAP_MASK;
                for (;;) {
                        if (slot->slots[i] != NULL)
                                break;
                        index &= ~((1UL << shift) - 1);
                        index += 1UL << shift;
                        if (index == 0)
                                goto out;       /* 32-bit wraparound */
                        i++;
                        if (i == RADIX_TREE_MAP_SIZE)
                                goto out;
                }

                shift -= RADIX_TREE_MAP_SHIFT;
                slot = rcu_dereference(slot->slots[i]);
                if (slot == NULL)
                        goto out;
        }

        /* Bottom level: grab some items */
        for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
                index++;
                if (slot->slots[i]) {
                        results[nr_found++] = &(slot->slots[i]);
                        if (nr_found == max_items)
                                goto out;
                }
        }
out:
        *next_index = index;
        return nr_found;
}

/**
 *      radix_tree_gang_lookup - perform multiple lookup on a radix tree
 *      @root:          radix tree root
 *      @results:       where the results of the lookup are placed
 *      @first_index:   start the lookup from this key
 *      @max_items:     place up to this many items at *results
 *
 *      Performs an index-ascending scan of the tree for present items.  Places
 *      them at *@results and returns the number of items which were placed at
 *      *@results.
 *
 *      The implementation is naive.
 *
 *      Like radix_tree_lookup, radix_tree_gang_lookup may be called under
 *      rcu_read_lock. In this case, rather than the returned results being
 *      an atomic snapshot of the tree at a single point in time, the semantics
 *      of an RCU protected gang lookup are as though multiple radix_tree_lookups
 *      have been issued in individual locks, and results stored in 'results'.
 */
unsigned int
radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
                        unsigned long first_index, unsigned int max_items)
{
        unsigned long max_index;
        struct radix_tree_node *node;
        unsigned long cur_index = first_index;
        unsigned int ret;

        node = rcu_dereference(root->rnode);
        if (!node)
                return 0;

        if (!radix_tree_is_indirect_ptr(node)) {
                if (first_index > 0)
                        return 0;
                results[0] = node;
                return 1;
        }
        node = radix_tree_indirect_to_ptr(node);

        max_index = radix_tree_maxindex(node->height);

        ret = 0;
        while (ret < max_items) {
                unsigned int nr_found, slots_found, i;
                unsigned long next_index;       /* Index of next search */

                if (cur_index > max_index)
                        break;
                slots_found = __lookup(node, (void ***)results + ret, cur_index,
                                        max_items - ret, &next_index);
                nr_found = 0;
                for (i = 0; i < slots_found; i++) {
                        struct radix_tree_node *slot;
                        slot = *(((void ***)results)[ret + i]);
                        if (!slot)
                                continue;
                        results[ret + nr_found] = rcu_dereference(slot);
                        nr_found++;
                }
                ret += nr_found;
                if (next_index == 0)
                        break;
                cur_index = next_index;
        }

        return ret;
}
EXPORT_SYMBOL(radix_tree_gang_lookup);

/**
 *      radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree
 *      @root:          radix tree root
 *      @results:       where the results of the lookup are placed
 *      @first_index:   start the lookup from this key
 *      @max_items:     place up to this many items at *results
 *
 *      Performs an index-ascending scan of the tree for present items.  Places
 *      their slots at *@results and returns the number of items which were
 *      placed at *@results.
 *
 *      The implementation is naive.
 *
 *      Like radix_tree_gang_lookup as far as RCU and locking goes. Slots must
 *      be dereferenced with radix_tree_deref_slot, and if using only RCU
 *      protection, radix_tree_deref_slot may fail requiring a retry.
 */
unsigned int
radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
                        unsigned long first_index, unsigned int max_items)
{
        unsigned long max_index;
        struct radix_tree_node *node;
        unsigned long cur_index = first_index;
        unsigned int ret;

        node = rcu_dereference(root->rnode);
        if (!node)
                return 0;

        if (!radix_tree_is_indirect_ptr(node)) {
                if (first_index > 0)
                        return 0;
                results[0] = (void **)&root->rnode;
                return 1;
        }
        node = radix_tree_indirect_to_ptr(node);

        max_index = radix_tree_maxindex(node->height);

        ret = 0;
        while (ret < max_items) {
                unsigned int slots_found;
                unsigned long next_index;       /* Index of next search */

                if (cur_index > max_index)
                        break;
                slots_found = __lookup(node, results + ret, cur_index,
                                        max_items - ret, &next_index);
                ret += slots_found;
                if (next_index == 0)
                        break;
                cur_index = next_index;
        }

        return ret;
}
EXPORT_SYMBOL(radix_tree_gang_lookup_slot);

/*
 * FIXME: the two tag_get()s here should use find_next_bit() instead of
 * open-coding the search.
 */
static unsigned int
__lookup_tag(struct radix_tree_node *slot, void ***results, unsigned long index,
        unsigned int max_items, unsigned long *next_index, unsigned int tag)
{
        unsigned int nr_found = 0;
        unsigned int shift, height;

        height = slot->height;
        if (height == 0)
                goto out;
        shift = (height-1) * RADIX_TREE_MAP_SHIFT;

        while (height > 0) {
                unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK ;

                for (;;) {
                        if (tag_get(slot, tag, i))
                                break;
                        index &= ~((1UL << shift) - 1);
                        index += 1UL << shift;
                        if (index == 0)
                                goto out;       /* 32-bit wraparound */
                        i++;
                        if (i == RADIX_TREE_MAP_SIZE)
                                goto out;
                }
                height--;
                if (height == 0) {      /* Bottom level: grab some items */
                        unsigned long j = index & RADIX_TREE_MAP_MASK;

                        for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
                                struct radix_tree_node *node;
                                index++;
                                if (!tag_get(slot, tag, j))
                                        continue;
                                node = slot->slots[j];
                                /*
                                 * Even though the tag was found set, we need to
                                 * recheck that we have a non-NULL node, because
                                 * if this lookup is lockless, it may have been
                                 * subsequently deleted.
                                 *
                                 * Similar care must be taken in any place that
                                 * lookup ->slots[x] without a lock (ie. can't
                                 * rely on its value remaining the same).
                                 */
                                if (slot->slots[j]) {
                                        results[nr_found++] = &slot->slots[j];
                                        if (nr_found == max_items)
                                                goto out;
                                }
                        }
                }
                shift -= RADIX_TREE_MAP_SHIFT;
                slot = rcu_dereference(slot->slots[i]);
                if (slot == NULL)
                        break;
        }
out:
        *next_index = index;
        return nr_found;
}

/**
 *      radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
 *                                   based on a tag
 *      @root:          radix tree root
 *      @results:       where the results of the lookup are placed
 *      @first_index:   start the lookup from this key
 *      @max_items:     place up to this many items at *results
 *      @tag:           the tag index (< RADIX_TREE_MAX_TAGS)
 *
 *      Performs an index-ascending scan of the tree for present items which
 *      have the tag indexed by @tag set.  Places the items at *@results and
 *      returns the number of items which were placed at *@results.
 */
unsigned int
radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
                unsigned long first_index, unsigned int max_items,
                unsigned int tag)
{
        struct radix_tree_node *node;
        unsigned long max_index;
        unsigned long cur_index = first_index;
        unsigned int ret;

        /* check the root's tag bit */
        if (!root_tag_get(root, tag))
                return 0;

        node = rcu_dereference(root->rnode);
        if (!node)
                return 0;

        if (!radix_tree_is_indirect_ptr(node)) {
                if (first_index > 0)
                        return 0;
                results[0] = node;
                return 1;
        }
        node = radix_tree_indirect_to_ptr(node);

        max_index = radix_tree_maxindex(node->height);

        ret = 0;
        while (ret < max_items) {
                unsigned int slots_found, nr_found, i;
                unsigned long next_index;       /* Index of next search */

                if (cur_index > max_index)
                        break;
                slots_found = __lookup_tag(node, (void ***)results + ret,
                                cur_index, max_items - ret, &next_index, tag);
                nr_found = 0;
                for (i = 0; i < slots_found; i++) {
                        struct radix_tree_node *slot;
                        slot = *((void ***)results)[ret + i];
                        if (!slot)
                                continue;
                        results[ret + nr_found] = rcu_dereference(slot);
                        nr_found++;
                }
                ret += nr_found;
                if (next_index == 0)
                        break;
                cur_index = next_index;
        }

        return ret;
}
EXPORT_SYMBOL(radix_tree_gang_lookup_tag);

/**
 *      radix_tree_gang_lookup_tag_slot - perform multiple slot lookup on a
 *                                        radix tree based on a tag
 *      @root:          radix tree root
 *      @results:       where the results of the lookup are placed
 *      @first_index:   start the lookup from this key
 *      @max_items:     place up to this many items at *results
 *      @tag:           the tag index (< RADIX_TREE_MAX_TAGS)
 *
 *      Performs an index-ascending scan of the tree for present items which
 *      have the tag indexed by @tag set.  Places the slots at *@results and
 *      returns the number of slots which were placed at *@results.
 */
unsigned int
radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
                unsigned long first_index, unsigned int max_items,
                unsigned int tag)
{
        struct radix_tree_node *node;
        unsigned long max_index;
        unsigned long cur_index = first_index;
        unsigned int ret;

        /* check the root's tag bit */
        if (!root_tag_get(root, tag))
                return 0;

        node = rcu_dereference(root->rnode);
        if (!node)
                return 0;

        if (!radix_tree_is_indirect_ptr(node)) {
                if (first_index > 0)
                        return 0;
                results[0] = (void **)&root->rnode;
                return 1;
        }
        node = radix_tree_indirect_to_ptr(node);

        max_index = radix_tree_maxindex(node->height);

        ret = 0;
        while (ret < max_items) {
                unsigned int slots_found;
                unsigned long next_index;       /* Index of next search */

                if (cur_index > max_index)
                        break;
                slots_found = __lookup_tag(node, results + ret,
                                cur_index, max_items - ret, &next_index, tag);
                ret += slots_found;
                if (next_index == 0)
                        break;
                cur_index = next_index;
        }

        return ret;
}
EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot);


/**
 *      radix_tree_shrink    -    shrink height of a radix tree to minimal
 *      @root           radix tree root
 */
static inline void radix_tree_shrink(struct radix_tree_root *root)
{
        /* try to shrink tree height */
        while (root->height > 0) {
                struct radix_tree_node *to_free = root->rnode;
                void *newptr;
                int tag;

                BUG_ON(!radix_tree_is_indirect_ptr(to_free));
                to_free = radix_tree_indirect_to_ptr(to_free);

                /*
                 * The candidate node has more than one child, or its child
                 * is not at the leftmost slot, we cannot shrink.
                 */
                if (to_free->count != 1)
                        break;
                if (!to_free->slots[0])
                        break;

                /*
                 * We don't need rcu_assign_pointer(), since we are simply
                 * moving the node from one part of the tree to another. If
                 * it was safe to dereference the old pointer to it
                 * (to_free->slots[0]), it will be safe to dereference the new
                 * one (root->rnode).
                 */
                newptr = to_free->slots[0];
                if (root->height > 1)
                        newptr = radix_tree_ptr_to_indirect(newptr);
                root->rnode = newptr;
                root->height--;
                /* must only free zeroed nodes into the slab */
                for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
                        tag_clear(to_free, tag, 0);
                to_free->slots[0] = NULL;
                to_free->count = 0;
        }
}

static
int radix_valid_delete(struct radix_tree_node *node, int offset, int tag)
{
        /*
         * we need to check for > 2, because nodes with a single child
         * can still be deleted, see radix_tree_shrink().
         */
        int unlock = (node->count > 2);

        if (!unlock)
                return unlock;

        for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
                if (!radix_valid_tag_clear(node, offset, tag)) {
                        unlock = 0;
                        break;
                }
        }

        return unlock;
}

/**
 *      radix_tree_delete    -    delete an item from a radix tree
 *      @root:          radix tree root
 *      @index:         index key
 *
 *      Remove the item at @index from the radix tree rooted at @root.
 *
 *      Returns the address of the deleted item, or NULL if it was not present.
 */
void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
{
        /*
         * The radix tree path needs to be one longer than the maximum path
         * since the "list" is null terminated.
         */
        struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
        struct radix_tree_path *punlock = path, *piter;
        struct radix_tree_node *slot = NULL;
        unsigned int height, shift;
        int tag;
        int offset;
        RADIX_TREE_CONTEXT(context, root);

        slot = radix_optimistic_lock(context, index, 0, radix_valid_delete);
        if (slot) {
                height = slot->height;
                shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
                offset = (index >> shift) & RADIX_TREE_MAP_MASK;
                pathp->offset = offset;
                pathp->node = slot;
                radix_path_init(context, pathp);
                goto optimistic;
        }

        pathp->node = NULL;
        radix_path_init(context, pathp);

        height = root->height;
        if (index > radix_tree_maxindex(height))
                goto out;

        slot = root->rnode;
        if (height == 0) {
                root_tag_clear_all(root);
                root->rnode = NULL;
                goto out;
        }
        slot = radix_tree_indirect_to_ptr(slot);

        shift = (height - 1) * RADIX_TREE_MAP_SHIFT;

        do {
                if (slot == NULL)
                        goto out;

                pathp++;
                offset = (index >> shift) & RADIX_TREE_MAP_MASK;
                pathp->offset = offset;
                pathp->node = slot;
                radix_path_lock(context, pathp, slot);

                if (radix_valid_delete(slot, offset, 0)) {
                        for (; punlock < pathp; punlock++)
                                radix_path_unlock(context, punlock);
                }

optimistic:
                slot = slot->slots[offset];
                shift -= RADIX_TREE_MAP_SHIFT;
                height--;
        } while (height > 0);

        if (slot == NULL)
                goto out;

        /*
         * Clear all tags associated with the just-deleted item
         */
        for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
                for (piter = pathp; piter >= punlock; piter--) {
                        if (piter->node) {
                                if (!tag_get(piter->node, tag, piter->offset))
                                        break;
                                tag_clear(piter->node, tag, piter->offset);
                                if (any_tag_set(piter->node, tag))
                                        break;
                        } else {
                                if (root_tag_get(root, tag))
                                        root_tag_clear(root, tag);
                        }
                }
        }

        /* Now unhook the nodes we do not need anymore */
        for (piter = pathp; piter >= punlock && piter->node; piter--) {
                piter->node->slots[piter->offset] = NULL;
                piter->node->count--;

                if (piter->node->count) {
                        if (piter->node ==
                                        radix_tree_indirect_to_ptr(root->rnode))
                                radix_tree_shrink(root);
                        goto out;
                }
        }

        BUG_ON(piter->node);

        root_tag_clear_all(root);
        root->height = 0;
        root->rnode = NULL;

out:
        for (; punlock <= pathp; punlock++) {
                radix_path_unlock(context, punlock);
                if (punlock->node && punlock->node->count == 0)
                        radix_tree_node_free(punlock->node);
        }
        return slot;
}
EXPORT_SYMBOL(radix_tree_delete);

/**
 *      radix_tree_tagged - test whether any items in the tree are tagged
 *      @root:          radix tree root
 *      @tag:           tag to test
 */
int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag)
{
        return root_tag_get(root, tag);
}
EXPORT_SYMBOL(radix_tree_tagged);

static void
radix_tree_node_ctor(struct kmem_cache *cachep, void *node)
{
        memset(node, 0, sizeof(struct radix_tree_node));
}

static __init unsigned long __maxindex(unsigned int height)
{
        unsigned int width = height * RADIX_TREE_MAP_SHIFT;
        int shift = RADIX_TREE_INDEX_BITS - width;

        if (shift < 0)
                return ~0UL;
        if (shift >= BITS_PER_LONG)
                return 0UL;
        return ~0UL >> shift;
}

static __init void radix_tree_init_maxindex(void)
{
        unsigned int i;

        for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
                height_to_maxindex[i] = __maxindex(i);
}

static int radix_tree_callback(struct notifier_block *nfb,
                            unsigned long action,
                            void *hcpu)
{
       int cpu = (long)hcpu;
       struct radix_tree_preload *rtp;

       /* Free per-cpu pool of perloaded nodes */
       if (action == CPU_DEAD || action == CPU_DEAD_FROZEN) {
               rtp = &per_cpu(radix_tree_preloads, cpu);
               while (rtp->nr) {
                       kmem_cache_free(radix_tree_node_cachep,
                                       rtp->nodes[rtp->nr-1]);
                       rtp->nodes[rtp->nr-1] = NULL;
                       rtp->nr--;
               }
       }
       return NOTIFY_OK;
}

void __init radix_tree_init(void)
{
        radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
                        sizeof(struct radix_tree_node), 0,
                        SLAB_PANIC, radix_tree_node_ctor);
        radix_tree_init_maxindex();
        hotcpu_notifier(radix_tree_callback, 0);
}