Back to home page

LXR

 
 

    


0001 /*
0002  * Copyright (C) 2001 Momchil Velikov
0003  * Portions Copyright (C) 2001 Christoph Hellwig
0004  * Copyright (C) 2005 SGI, Christoph Lameter
0005  * Copyright (C) 2006 Nick Piggin
0006  * Copyright (C) 2012 Konstantin Khlebnikov
0007  * Copyright (C) 2016 Intel, Matthew Wilcox
0008  * Copyright (C) 2016 Intel, Ross Zwisler
0009  *
0010  * This program is free software; you can redistribute it and/or
0011  * modify it under the terms of the GNU General Public License as
0012  * published by the Free Software Foundation; either version 2, or (at
0013  * your option) any later version.
0014  *
0015  * This program is distributed in the hope that it will be useful, but
0016  * WITHOUT ANY WARRANTY; without even the implied warranty of
0017  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
0018  * General Public License for more details.
0019  *
0020  * You should have received a copy of the GNU General Public License
0021  * along with this program; if not, write to the Free Software
0022  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
0023  */
0024 
0025 #include <linux/cpu.h>
0026 #include <linux/errno.h>
0027 #include <linux/init.h>
0028 #include <linux/kernel.h>
0029 #include <linux/export.h>
0030 #include <linux/radix-tree.h>
0031 #include <linux/percpu.h>
0032 #include <linux/slab.h>
0033 #include <linux/kmemleak.h>
0034 #include <linux/cpu.h>
0035 #include <linux/string.h>
0036 #include <linux/bitops.h>
0037 #include <linux/rcupdate.h>
0038 #include <linux/preempt.h>      /* in_interrupt() */
0039 
0040 
0041 /* Number of nodes in fully populated tree of given height */
0042 static unsigned long height_to_maxnodes[RADIX_TREE_MAX_PATH + 1] __read_mostly;
0043 
0044 /*
0045  * Radix tree node cache.
0046  */
0047 static struct kmem_cache *radix_tree_node_cachep;
0048 
0049 /*
0050  * The radix tree is variable-height, so an insert operation not only has
0051  * to build the branch to its corresponding item, it also has to build the
0052  * branch to existing items if the size has to be increased (by
0053  * radix_tree_extend).
0054  *
0055  * The worst case is a zero height tree with just a single item at index 0,
0056  * and then inserting an item at index ULONG_MAX. This requires 2 new branches
0057  * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared.
0058  * Hence:
0059  */
0060 #define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1)
0061 
0062 /*
0063  * Per-cpu pool of preloaded nodes
0064  */
0065 struct radix_tree_preload {
0066     unsigned nr;
0067     /* nodes->private_data points to next preallocated node */
0068     struct radix_tree_node *nodes;
0069 };
0070 static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
0071 
0072 static inline struct radix_tree_node *entry_to_node(void *ptr)
0073 {
0074     return (void *)((unsigned long)ptr & ~RADIX_TREE_INTERNAL_NODE);
0075 }
0076 
0077 static inline void *node_to_entry(void *ptr)
0078 {
0079     return (void *)((unsigned long)ptr | RADIX_TREE_INTERNAL_NODE);
0080 }
0081 
0082 #define RADIX_TREE_RETRY    node_to_entry(NULL)
0083 
0084 #ifdef CONFIG_RADIX_TREE_MULTIORDER
0085 /* Sibling slots point directly to another slot in the same node */
0086 static inline bool is_sibling_entry(struct radix_tree_node *parent, void *node)
0087 {
0088     void **ptr = node;
0089     return (parent->slots <= ptr) &&
0090             (ptr < parent->slots + RADIX_TREE_MAP_SIZE);
0091 }
0092 #else
0093 static inline bool is_sibling_entry(struct radix_tree_node *parent, void *node)
0094 {
0095     return false;
0096 }
0097 #endif
0098 
0099 static inline unsigned long get_slot_offset(struct radix_tree_node *parent,
0100                          void **slot)
0101 {
0102     return slot - parent->slots;
0103 }
0104 
0105 static unsigned int radix_tree_descend(struct radix_tree_node *parent,
0106             struct radix_tree_node **nodep, unsigned long index)
0107 {
0108     unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK;
0109     void **entry = rcu_dereference_raw(parent->slots[offset]);
0110 
0111 #ifdef CONFIG_RADIX_TREE_MULTIORDER
0112     if (radix_tree_is_internal_node(entry)) {
0113         if (is_sibling_entry(parent, entry)) {
0114             void **sibentry = (void **) entry_to_node(entry);
0115             offset = get_slot_offset(parent, sibentry);
0116             entry = rcu_dereference_raw(*sibentry);
0117         }
0118     }
0119 #endif
0120 
0121     *nodep = (void *)entry;
0122     return offset;
0123 }
0124 
0125 static inline gfp_t root_gfp_mask(struct radix_tree_root *root)
0126 {
0127     return root->gfp_mask & __GFP_BITS_MASK;
0128 }
0129 
0130 static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
0131         int offset)
0132 {
0133     __set_bit(offset, node->tags[tag]);
0134 }
0135 
0136 static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,
0137         int offset)
0138 {
0139     __clear_bit(offset, node->tags[tag]);
0140 }
0141 
0142 static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
0143         int offset)
0144 {
0145     return test_bit(offset, node->tags[tag]);
0146 }
0147 
0148 static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag)
0149 {
0150     root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT));
0151 }
0152 
0153 static inline void root_tag_clear(struct radix_tree_root *root, unsigned tag)
0154 {
0155     root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT));
0156 }
0157 
0158 static inline void root_tag_clear_all(struct radix_tree_root *root)
0159 {
0160     root->gfp_mask &= __GFP_BITS_MASK;
0161 }
0162 
0163 static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
0164 {
0165     return (__force int)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
0166 }
0167 
0168 static inline unsigned root_tags_get(struct radix_tree_root *root)
0169 {
0170     return (__force unsigned)root->gfp_mask >> __GFP_BITS_SHIFT;
0171 }
0172 
0173 /*
0174  * Returns 1 if any slot in the node has this tag set.
0175  * Otherwise returns 0.
0176  */
0177 static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
0178 {
0179     unsigned idx;
0180     for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
0181         if (node->tags[tag][idx])
0182             return 1;
0183     }
0184     return 0;
0185 }
0186 
0187 /**
0188  * radix_tree_find_next_bit - find the next set bit in a memory region
0189  *
0190  * @addr: The address to base the search on
0191  * @size: The bitmap size in bits
0192  * @offset: The bitnumber to start searching at
0193  *
0194  * Unrollable variant of find_next_bit() for constant size arrays.
0195  * Tail bits starting from size to roundup(size, BITS_PER_LONG) must be zero.
0196  * Returns next bit offset, or size if nothing found.
0197  */
0198 static __always_inline unsigned long
0199 radix_tree_find_next_bit(struct radix_tree_node *node, unsigned int tag,
0200              unsigned long offset)
0201 {
0202     const unsigned long *addr = node->tags[tag];
0203 
0204     if (offset < RADIX_TREE_MAP_SIZE) {
0205         unsigned long tmp;
0206 
0207         addr += offset / BITS_PER_LONG;
0208         tmp = *addr >> (offset % BITS_PER_LONG);
0209         if (tmp)
0210             return __ffs(tmp) + offset;
0211         offset = (offset + BITS_PER_LONG) & ~(BITS_PER_LONG - 1);
0212         while (offset < RADIX_TREE_MAP_SIZE) {
0213             tmp = *++addr;
0214             if (tmp)
0215                 return __ffs(tmp) + offset;
0216             offset += BITS_PER_LONG;
0217         }
0218     }
0219     return RADIX_TREE_MAP_SIZE;
0220 }
0221 
0222 static unsigned int iter_offset(const struct radix_tree_iter *iter)
0223 {
0224     return (iter->index >> iter_shift(iter)) & RADIX_TREE_MAP_MASK;
0225 }
0226 
0227 /*
0228  * The maximum index which can be stored in a radix tree
0229  */
0230 static inline unsigned long shift_maxindex(unsigned int shift)
0231 {
0232     return (RADIX_TREE_MAP_SIZE << shift) - 1;
0233 }
0234 
0235 static inline unsigned long node_maxindex(struct radix_tree_node *node)
0236 {
0237     return shift_maxindex(node->shift);
0238 }
0239 
0240 #ifndef __KERNEL__
0241 static void dump_node(struct radix_tree_node *node, unsigned long index)
0242 {
0243     unsigned long i;
0244 
0245     pr_debug("radix node: %p offset %d indices %lu-%lu parent %p tags %lx %lx %lx shift %d count %d exceptional %d\n",
0246         node, node->offset, index, index | node_maxindex(node),
0247         node->parent,
0248         node->tags[0][0], node->tags[1][0], node->tags[2][0],
0249         node->shift, node->count, node->exceptional);
0250 
0251     for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
0252         unsigned long first = index | (i << node->shift);
0253         unsigned long last = first | ((1UL << node->shift) - 1);
0254         void *entry = node->slots[i];
0255         if (!entry)
0256             continue;
0257         if (entry == RADIX_TREE_RETRY) {
0258             pr_debug("radix retry offset %ld indices %lu-%lu parent %p\n",
0259                     i, first, last, node);
0260         } else if (!radix_tree_is_internal_node(entry)) {
0261             pr_debug("radix entry %p offset %ld indices %lu-%lu parent %p\n",
0262                     entry, i, first, last, node);
0263         } else if (is_sibling_entry(node, entry)) {
0264             pr_debug("radix sblng %p offset %ld indices %lu-%lu parent %p val %p\n",
0265                     entry, i, first, last, node,
0266                     *(void **)entry_to_node(entry));
0267         } else {
0268             dump_node(entry_to_node(entry), first);
0269         }
0270     }
0271 }
0272 
0273 /* For debug */
0274 static void radix_tree_dump(struct radix_tree_root *root)
0275 {
0276     pr_debug("radix root: %p rnode %p tags %x\n",
0277             root, root->rnode,
0278             root->gfp_mask >> __GFP_BITS_SHIFT);
0279     if (!radix_tree_is_internal_node(root->rnode))
0280         return;
0281     dump_node(entry_to_node(root->rnode), 0);
0282 }
0283 #endif
0284 
0285 /*
0286  * This assumes that the caller has performed appropriate preallocation, and
0287  * that the caller has pinned this thread of control to the current CPU.
0288  */
0289 static struct radix_tree_node *
0290 radix_tree_node_alloc(struct radix_tree_root *root,
0291             struct radix_tree_node *parent,
0292             unsigned int shift, unsigned int offset,
0293             unsigned int count, unsigned int exceptional)
0294 {
0295     struct radix_tree_node *ret = NULL;
0296     gfp_t gfp_mask = root_gfp_mask(root);
0297 
0298     /*
0299      * Preload code isn't irq safe and it doesn't make sense to use
0300      * preloading during an interrupt anyway as all the allocations have
0301      * to be atomic. So just do normal allocation when in interrupt.
0302      */
0303     if (!gfpflags_allow_blocking(gfp_mask) && !in_interrupt()) {
0304         struct radix_tree_preload *rtp;
0305 
0306         /*
0307          * Even if the caller has preloaded, try to allocate from the
0308          * cache first for the new node to get accounted to the memory
0309          * cgroup.
0310          */
0311         ret = kmem_cache_alloc(radix_tree_node_cachep,
0312                        gfp_mask | __GFP_NOWARN);
0313         if (ret)
0314             goto out;
0315 
0316         /*
0317          * Provided the caller has preloaded here, we will always
0318          * succeed in getting a node here (and never reach
0319          * kmem_cache_alloc)
0320          */
0321         rtp = this_cpu_ptr(&radix_tree_preloads);
0322         if (rtp->nr) {
0323             ret = rtp->nodes;
0324             rtp->nodes = ret->private_data;
0325             ret->private_data = NULL;
0326             rtp->nr--;
0327         }
0328         /*
0329          * Update the allocation stack trace as this is more useful
0330          * for debugging.
0331          */
0332         kmemleak_update_trace(ret);
0333         goto out;
0334     }
0335     ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
0336 out:
0337     BUG_ON(radix_tree_is_internal_node(ret));
0338     if (ret) {
0339         ret->parent = parent;
0340         ret->shift = shift;
0341         ret->offset = offset;
0342         ret->count = count;
0343         ret->exceptional = exceptional;
0344     }
0345     return ret;
0346 }
0347 
0348 static void radix_tree_node_rcu_free(struct rcu_head *head)
0349 {
0350     struct radix_tree_node *node =
0351             container_of(head, struct radix_tree_node, rcu_head);
0352 
0353     /*
0354      * Must only free zeroed nodes into the slab.  We can be left with
0355      * non-NULL entries by radix_tree_free_nodes, so clear the entries
0356      * and tags here.
0357      */
0358     memset(node->slots, 0, sizeof(node->slots));
0359     memset(node->tags, 0, sizeof(node->tags));
0360     INIT_LIST_HEAD(&node->private_list);
0361 
0362     kmem_cache_free(radix_tree_node_cachep, node);
0363 }
0364 
0365 static inline void
0366 radix_tree_node_free(struct radix_tree_node *node)
0367 {
0368     call_rcu(&node->rcu_head, radix_tree_node_rcu_free);
0369 }
0370 
0371 /*
0372  * Load up this CPU's radix_tree_node buffer with sufficient objects to
0373  * ensure that the addition of a single element in the tree cannot fail.  On
0374  * success, return zero, with preemption disabled.  On error, return -ENOMEM
0375  * with preemption not disabled.
0376  *
0377  * To make use of this facility, the radix tree must be initialised without
0378  * __GFP_DIRECT_RECLAIM being passed to INIT_RADIX_TREE().
0379  */
0380 static int __radix_tree_preload(gfp_t gfp_mask, unsigned nr)
0381 {
0382     struct radix_tree_preload *rtp;
0383     struct radix_tree_node *node;
0384     int ret = -ENOMEM;
0385 
0386     /*
0387      * Nodes preloaded by one cgroup can be be used by another cgroup, so
0388      * they should never be accounted to any particular memory cgroup.
0389      */
0390     gfp_mask &= ~__GFP_ACCOUNT;
0391 
0392     preempt_disable();
0393     rtp = this_cpu_ptr(&radix_tree_preloads);
0394     while (rtp->nr < nr) {
0395         preempt_enable();
0396         node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
0397         if (node == NULL)
0398             goto out;
0399         preempt_disable();
0400         rtp = this_cpu_ptr(&radix_tree_preloads);
0401         if (rtp->nr < nr) {
0402             node->private_data = rtp->nodes;
0403             rtp->nodes = node;
0404             rtp->nr++;
0405         } else {
0406             kmem_cache_free(radix_tree_node_cachep, node);
0407         }
0408     }
0409     ret = 0;
0410 out:
0411     return ret;
0412 }
0413 
0414 /*
0415  * Load up this CPU's radix_tree_node buffer with sufficient objects to
0416  * ensure that the addition of a single element in the tree cannot fail.  On
0417  * success, return zero, with preemption disabled.  On error, return -ENOMEM
0418  * with preemption not disabled.
0419  *
0420  * To make use of this facility, the radix tree must be initialised without
0421  * __GFP_DIRECT_RECLAIM being passed to INIT_RADIX_TREE().
0422  */
0423 int radix_tree_preload(gfp_t gfp_mask)
0424 {
0425     /* Warn on non-sensical use... */
0426     WARN_ON_ONCE(!gfpflags_allow_blocking(gfp_mask));
0427     return __radix_tree_preload(gfp_mask, RADIX_TREE_PRELOAD_SIZE);
0428 }
0429 EXPORT_SYMBOL(radix_tree_preload);
0430 
0431 /*
0432  * The same as above function, except we don't guarantee preloading happens.
0433  * We do it, if we decide it helps. On success, return zero with preemption
0434  * disabled. On error, return -ENOMEM with preemption not disabled.
0435  */
0436 int radix_tree_maybe_preload(gfp_t gfp_mask)
0437 {
0438     if (gfpflags_allow_blocking(gfp_mask))
0439         return __radix_tree_preload(gfp_mask, RADIX_TREE_PRELOAD_SIZE);
0440     /* Preloading doesn't help anything with this gfp mask, skip it */
0441     preempt_disable();
0442     return 0;
0443 }
0444 EXPORT_SYMBOL(radix_tree_maybe_preload);
0445 
0446 #ifdef CONFIG_RADIX_TREE_MULTIORDER
0447 /*
0448  * Preload with enough objects to ensure that we can split a single entry
0449  * of order @old_order into many entries of size @new_order
0450  */
0451 int radix_tree_split_preload(unsigned int old_order, unsigned int new_order,
0452                             gfp_t gfp_mask)
0453 {
0454     unsigned top = 1 << (old_order % RADIX_TREE_MAP_SHIFT);
0455     unsigned layers = (old_order / RADIX_TREE_MAP_SHIFT) -
0456                 (new_order / RADIX_TREE_MAP_SHIFT);
0457     unsigned nr = 0;
0458 
0459     WARN_ON_ONCE(!gfpflags_allow_blocking(gfp_mask));
0460     BUG_ON(new_order >= old_order);
0461 
0462     while (layers--)
0463         nr = nr * RADIX_TREE_MAP_SIZE + 1;
0464     return __radix_tree_preload(gfp_mask, top * nr);
0465 }
0466 #endif
0467 
0468 /*
0469  * The same as function above, but preload number of nodes required to insert
0470  * (1 << order) continuous naturally-aligned elements.
0471  */
0472 int radix_tree_maybe_preload_order(gfp_t gfp_mask, int order)
0473 {
0474     unsigned long nr_subtrees;
0475     int nr_nodes, subtree_height;
0476 
0477     /* Preloading doesn't help anything with this gfp mask, skip it */
0478     if (!gfpflags_allow_blocking(gfp_mask)) {
0479         preempt_disable();
0480         return 0;
0481     }
0482 
0483     /*
0484      * Calculate number and height of fully populated subtrees it takes to
0485      * store (1 << order) elements.
0486      */
0487     nr_subtrees = 1 << order;
0488     for (subtree_height = 0; nr_subtrees > RADIX_TREE_MAP_SIZE;
0489             subtree_height++)
0490         nr_subtrees >>= RADIX_TREE_MAP_SHIFT;
0491 
0492     /*
0493      * The worst case is zero height tree with a single item at index 0 and
0494      * then inserting items starting at ULONG_MAX - (1 << order).
0495      *
0496      * This requires RADIX_TREE_MAX_PATH nodes to build branch from root to
0497      * 0-index item.
0498      */
0499     nr_nodes = RADIX_TREE_MAX_PATH;
0500 
0501     /* Plus branch to fully populated subtrees. */
0502     nr_nodes += RADIX_TREE_MAX_PATH - subtree_height;
0503 
0504     /* Root node is shared. */
0505     nr_nodes--;
0506 
0507     /* Plus nodes required to build subtrees. */
0508     nr_nodes += nr_subtrees * height_to_maxnodes[subtree_height];
0509 
0510     return __radix_tree_preload(gfp_mask, nr_nodes);
0511 }
0512 
0513 static unsigned radix_tree_load_root(struct radix_tree_root *root,
0514         struct radix_tree_node **nodep, unsigned long *maxindex)
0515 {
0516     struct radix_tree_node *node = rcu_dereference_raw(root->rnode);
0517 
0518     *nodep = node;
0519 
0520     if (likely(radix_tree_is_internal_node(node))) {
0521         node = entry_to_node(node);
0522         *maxindex = node_maxindex(node);
0523         return node->shift + RADIX_TREE_MAP_SHIFT;
0524     }
0525 
0526     *maxindex = 0;
0527     return 0;
0528 }
0529 
0530 /*
0531  *  Extend a radix tree so it can store key @index.
0532  */
0533 static int radix_tree_extend(struct radix_tree_root *root,
0534                 unsigned long index, unsigned int shift)
0535 {
0536     struct radix_tree_node *slot;
0537     unsigned int maxshift;
0538     int tag;
0539 
0540     /* Figure out what the shift should be.  */
0541     maxshift = shift;
0542     while (index > shift_maxindex(maxshift))
0543         maxshift += RADIX_TREE_MAP_SHIFT;
0544 
0545     slot = root->rnode;
0546     if (!slot)
0547         goto out;
0548 
0549     do {
0550         struct radix_tree_node *node = radix_tree_node_alloc(root,
0551                             NULL, shift, 0, 1, 0);
0552         if (!node)
0553             return -ENOMEM;
0554 
0555         /* Propagate the aggregated tag info into the new root */
0556         for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
0557             if (root_tag_get(root, tag))
0558                 tag_set(node, tag, 0);
0559         }
0560 
0561         BUG_ON(shift > BITS_PER_LONG);
0562         if (radix_tree_is_internal_node(slot)) {
0563             entry_to_node(slot)->parent = node;
0564         } else if (radix_tree_exceptional_entry(slot)) {
0565             /* Moving an exceptional root->rnode to a node */
0566             node->exceptional = 1;
0567         }
0568         node->slots[0] = slot;
0569         slot = node_to_entry(node);
0570         rcu_assign_pointer(root->rnode, slot);
0571         shift += RADIX_TREE_MAP_SHIFT;
0572     } while (shift <= maxshift);
0573 out:
0574     return maxshift + RADIX_TREE_MAP_SHIFT;
0575 }
0576 
0577 /**
0578  *  radix_tree_shrink    -    shrink radix tree to minimum height
0579  *  @root       radix tree root
0580  */
0581 static inline void radix_tree_shrink(struct radix_tree_root *root,
0582                      radix_tree_update_node_t update_node,
0583                      void *private)
0584 {
0585     for (;;) {
0586         struct radix_tree_node *node = root->rnode;
0587         struct radix_tree_node *child;
0588 
0589         if (!radix_tree_is_internal_node(node))
0590             break;
0591         node = entry_to_node(node);
0592 
0593         /*
0594          * The candidate node has more than one child, or its child
0595          * is not at the leftmost slot, or the child is a multiorder
0596          * entry, we cannot shrink.
0597          */
0598         if (node->count != 1)
0599             break;
0600         child = node->slots[0];
0601         if (!child)
0602             break;
0603         if (!radix_tree_is_internal_node(child) && node->shift)
0604             break;
0605 
0606         if (radix_tree_is_internal_node(child))
0607             entry_to_node(child)->parent = NULL;
0608 
0609         /*
0610          * We don't need rcu_assign_pointer(), since we are simply
0611          * moving the node from one part of the tree to another: if it
0612          * was safe to dereference the old pointer to it
0613          * (node->slots[0]), it will be safe to dereference the new
0614          * one (root->rnode) as far as dependent read barriers go.
0615          */
0616         root->rnode = child;
0617 
0618         /*
0619          * We have a dilemma here. The node's slot[0] must not be
0620          * NULLed in case there are concurrent lookups expecting to
0621          * find the item. However if this was a bottom-level node,
0622          * then it may be subject to the slot pointer being visible
0623          * to callers dereferencing it. If item corresponding to
0624          * slot[0] is subsequently deleted, these callers would expect
0625          * their slot to become empty sooner or later.
0626          *
0627          * For example, lockless pagecache will look up a slot, deref
0628          * the page pointer, and if the page has 0 refcount it means it
0629          * was concurrently deleted from pagecache so try the deref
0630          * again. Fortunately there is already a requirement for logic
0631          * to retry the entire slot lookup -- the indirect pointer
0632          * problem (replacing direct root node with an indirect pointer
0633          * also results in a stale slot). So tag the slot as indirect
0634          * to force callers to retry.
0635          */
0636         node->count = 0;
0637         if (!radix_tree_is_internal_node(child)) {
0638             node->slots[0] = RADIX_TREE_RETRY;
0639             if (update_node)
0640                 update_node(node, private);
0641         }
0642 
0643         WARN_ON_ONCE(!list_empty(&node->private_list));
0644         radix_tree_node_free(node);
0645     }
0646 }
0647 
0648 static void delete_node(struct radix_tree_root *root,
0649             struct radix_tree_node *node,
0650             radix_tree_update_node_t update_node, void *private)
0651 {
0652     do {
0653         struct radix_tree_node *parent;
0654 
0655         if (node->count) {
0656             if (node == entry_to_node(root->rnode))
0657                 radix_tree_shrink(root, update_node, private);
0658             return;
0659         }
0660 
0661         parent = node->parent;
0662         if (parent) {
0663             parent->slots[node->offset] = NULL;
0664             parent->count--;
0665         } else {
0666             root_tag_clear_all(root);
0667             root->rnode = NULL;
0668         }
0669 
0670         WARN_ON_ONCE(!list_empty(&node->private_list));
0671         radix_tree_node_free(node);
0672 
0673         node = parent;
0674     } while (node);
0675 }
0676 
0677 /**
0678  *  __radix_tree_create -   create a slot in a radix tree
0679  *  @root:      radix tree root
0680  *  @index:     index key
0681  *  @order:     index occupies 2^order aligned slots
0682  *  @nodep:     returns node
0683  *  @slotp:     returns slot
0684  *
0685  *  Create, if necessary, and return the node and slot for an item
0686  *  at position @index in the radix tree @root.
0687  *
0688  *  Until there is more than one item in the tree, no nodes are
0689  *  allocated and @root->rnode is used as a direct slot instead of
0690  *  pointing to a node, in which case *@nodep will be NULL.
0691  *
0692  *  Returns -ENOMEM, or 0 for success.
0693  */
0694 int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
0695             unsigned order, struct radix_tree_node **nodep,
0696             void ***slotp)
0697 {
0698     struct radix_tree_node *node = NULL, *child;
0699     void **slot = (void **)&root->rnode;
0700     unsigned long maxindex;
0701     unsigned int shift, offset = 0;
0702     unsigned long max = index | ((1UL << order) - 1);
0703 
0704     shift = radix_tree_load_root(root, &child, &maxindex);
0705 
0706     /* Make sure the tree is high enough.  */
0707     if (order > 0 && max == ((1UL << order) - 1))
0708         max++;
0709     if (max > maxindex) {
0710         int error = radix_tree_extend(root, max, shift);
0711         if (error < 0)
0712             return error;
0713         shift = error;
0714         child = root->rnode;
0715     }
0716 
0717     while (shift > order) {
0718         shift -= RADIX_TREE_MAP_SHIFT;
0719         if (child == NULL) {
0720             /* Have to add a child node.  */
0721             child = radix_tree_node_alloc(root, node, shift,
0722                             offset, 0, 0);
0723             if (!child)
0724                 return -ENOMEM;
0725             rcu_assign_pointer(*slot, node_to_entry(child));
0726             if (node)
0727                 node->count++;
0728         } else if (!radix_tree_is_internal_node(child))
0729             break;
0730 
0731         /* Go a level down */
0732         node = entry_to_node(child);
0733         offset = radix_tree_descend(node, &child, index);
0734         slot = &node->slots[offset];
0735     }
0736 
0737     if (nodep)
0738         *nodep = node;
0739     if (slotp)
0740         *slotp = slot;
0741     return 0;
0742 }
0743 
0744 #ifdef CONFIG_RADIX_TREE_MULTIORDER
0745 /*
0746  * Free any nodes below this node.  The tree is presumed to not need
0747  * shrinking, and any user data in the tree is presumed to not need a
0748  * destructor called on it.  If we need to add a destructor, we can
0749  * add that functionality later.  Note that we may not clear tags or
0750  * slots from the tree as an RCU walker may still have a pointer into
0751  * this subtree.  We could replace the entries with RADIX_TREE_RETRY,
0752  * but we'll still have to clear those in rcu_free.
0753  */
0754 static void radix_tree_free_nodes(struct radix_tree_node *node)
0755 {
0756     unsigned offset = 0;
0757     struct radix_tree_node *child = entry_to_node(node);
0758 
0759     for (;;) {
0760         void *entry = child->slots[offset];
0761         if (radix_tree_is_internal_node(entry) &&
0762                     !is_sibling_entry(child, entry)) {
0763             child = entry_to_node(entry);
0764             offset = 0;
0765             continue;
0766         }
0767         offset++;
0768         while (offset == RADIX_TREE_MAP_SIZE) {
0769             struct radix_tree_node *old = child;
0770             offset = child->offset + 1;
0771             child = child->parent;
0772             WARN_ON_ONCE(!list_empty(&old->private_list));
0773             radix_tree_node_free(old);
0774             if (old == entry_to_node(node))
0775                 return;
0776         }
0777     }
0778 }
0779 
0780 static inline int insert_entries(struct radix_tree_node *node, void **slot,
0781                 void *item, unsigned order, bool replace)
0782 {
0783     struct radix_tree_node *child;
0784     unsigned i, n, tag, offset, tags = 0;
0785 
0786     if (node) {
0787         if (order > node->shift)
0788             n = 1 << (order - node->shift);
0789         else
0790             n = 1;
0791         offset = get_slot_offset(node, slot);
0792     } else {
0793         n = 1;
0794         offset = 0;
0795     }
0796 
0797     if (n > 1) {
0798         offset = offset & ~(n - 1);
0799         slot = &node->slots[offset];
0800     }
0801     child = node_to_entry(slot);
0802 
0803     for (i = 0; i < n; i++) {
0804         if (slot[i]) {
0805             if (replace) {
0806                 node->count--;
0807                 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
0808                     if (tag_get(node, tag, offset + i))
0809                         tags |= 1 << tag;
0810             } else
0811                 return -EEXIST;
0812         }
0813     }
0814 
0815     for (i = 0; i < n; i++) {
0816         struct radix_tree_node *old = slot[i];
0817         if (i) {
0818             rcu_assign_pointer(slot[i], child);
0819             for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
0820                 if (tags & (1 << tag))
0821                     tag_clear(node, tag, offset + i);
0822         } else {
0823             rcu_assign_pointer(slot[i], item);
0824             for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
0825                 if (tags & (1 << tag))
0826                     tag_set(node, tag, offset);
0827         }
0828         if (radix_tree_is_internal_node(old) &&
0829                     !is_sibling_entry(node, old) &&
0830                     (old != RADIX_TREE_RETRY))
0831             radix_tree_free_nodes(old);
0832         if (radix_tree_exceptional_entry(old))
0833             node->exceptional--;
0834     }
0835     if (node) {
0836         node->count += n;
0837         if (radix_tree_exceptional_entry(item))
0838             node->exceptional += n;
0839     }
0840     return n;
0841 }
0842 #else
0843 static inline int insert_entries(struct radix_tree_node *node, void **slot,
0844                 void *item, unsigned order, bool replace)
0845 {
0846     if (*slot)
0847         return -EEXIST;
0848     rcu_assign_pointer(*slot, item);
0849     if (node) {
0850         node->count++;
0851         if (radix_tree_exceptional_entry(item))
0852             node->exceptional++;
0853     }
0854     return 1;
0855 }
0856 #endif
0857 
0858 /**
0859  *  __radix_tree_insert    -    insert into a radix tree
0860  *  @root:      radix tree root
0861  *  @index:     index key
0862  *  @order:     key covers the 2^order indices around index
0863  *  @item:      item to insert
0864  *
0865  *  Insert an item into the radix tree at position @index.
0866  */
0867 int __radix_tree_insert(struct radix_tree_root *root, unsigned long index,
0868             unsigned order, void *item)
0869 {
0870     struct radix_tree_node *node;
0871     void **slot;
0872     int error;
0873 
0874     BUG_ON(radix_tree_is_internal_node(item));
0875 
0876     error = __radix_tree_create(root, index, order, &node, &slot);
0877     if (error)
0878         return error;
0879 
0880     error = insert_entries(node, slot, item, order, false);
0881     if (error < 0)
0882         return error;
0883 
0884     if (node) {
0885         unsigned offset = get_slot_offset(node, slot);
0886         BUG_ON(tag_get(node, 0, offset));
0887         BUG_ON(tag_get(node, 1, offset));
0888         BUG_ON(tag_get(node, 2, offset));
0889     } else {
0890         BUG_ON(root_tags_get(root));
0891     }
0892 
0893     return 0;
0894 }
0895 EXPORT_SYMBOL(__radix_tree_insert);
0896 
0897 /**
0898  *  __radix_tree_lookup -   lookup an item in a radix tree
0899  *  @root:      radix tree root
0900  *  @index:     index key
0901  *  @nodep:     returns node
0902  *  @slotp:     returns slot
0903  *
0904  *  Lookup and return the item at position @index in the radix
0905  *  tree @root.
0906  *
0907  *  Until there is more than one item in the tree, no nodes are
0908  *  allocated and @root->rnode is used as a direct slot instead of
0909  *  pointing to a node, in which case *@nodep will be NULL.
0910  */
0911 void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index,
0912               struct radix_tree_node **nodep, void ***slotp)
0913 {
0914     struct radix_tree_node *node, *parent;
0915     unsigned long maxindex;
0916     void **slot;
0917 
0918  restart:
0919     parent = NULL;
0920     slot = (void **)&root->rnode;
0921     radix_tree_load_root(root, &node, &maxindex);
0922     if (index > maxindex)
0923         return NULL;
0924 
0925     while (radix_tree_is_internal_node(node)) {
0926         unsigned offset;
0927 
0928         if (node == RADIX_TREE_RETRY)
0929             goto restart;
0930         parent = entry_to_node(node);
0931         offset = radix_tree_descend(parent, &node, index);
0932         slot = parent->slots + offset;
0933     }
0934 
0935     if (nodep)
0936         *nodep = parent;
0937     if (slotp)
0938         *slotp = slot;
0939     return node;
0940 }
0941 
0942 /**
0943  *  radix_tree_lookup_slot    -    lookup a slot in a radix tree
0944  *  @root:      radix tree root
0945  *  @index:     index key
0946  *
0947  *  Returns:  the slot corresponding to the position @index in the
0948  *  radix tree @root. This is useful for update-if-exists operations.
0949  *
0950  *  This function can be called under rcu_read_lock iff the slot is not
0951  *  modified by radix_tree_replace_slot, otherwise it must be called
0952  *  exclusive from other writers. Any dereference of the slot must be done
0953  *  using radix_tree_deref_slot.
0954  */
0955 void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
0956 {
0957     void **slot;
0958 
0959     if (!__radix_tree_lookup(root, index, NULL, &slot))
0960         return NULL;
0961     return slot;
0962 }
0963 EXPORT_SYMBOL(radix_tree_lookup_slot);
0964 
0965 /**
0966  *  radix_tree_lookup    -    perform lookup operation on a radix tree
0967  *  @root:      radix tree root
0968  *  @index:     index key
0969  *
0970  *  Lookup the item at the position @index in the radix tree @root.
0971  *
0972  *  This function can be called under rcu_read_lock, however the caller
0973  *  must manage lifetimes of leaf nodes (eg. RCU may also be used to free
0974  *  them safely). No RCU barriers are required to access or modify the
0975  *  returned item, however.
0976  */
0977 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
0978 {
0979     return __radix_tree_lookup(root, index, NULL, NULL);
0980 }
0981 EXPORT_SYMBOL(radix_tree_lookup);
0982 
0983 static inline int slot_count(struct radix_tree_node *node,
0984                         void **slot)
0985 {
0986     int n = 1;
0987 #ifdef CONFIG_RADIX_TREE_MULTIORDER
0988     void *ptr = node_to_entry(slot);
0989     unsigned offset = get_slot_offset(node, slot);
0990     int i;
0991 
0992     for (i = 1; offset + i < RADIX_TREE_MAP_SIZE; i++) {
0993         if (node->slots[offset + i] != ptr)
0994             break;
0995         n++;
0996     }
0997 #endif
0998     return n;
0999 }
1000 
1001 static void replace_slot(struct radix_tree_root *root,
1002              struct radix_tree_node *node,
1003              void **slot, void *item,
1004              bool warn_typeswitch)
1005 {
1006     void *old = rcu_dereference_raw(*slot);
1007     int count, exceptional;
1008 
1009     WARN_ON_ONCE(radix_tree_is_internal_node(item));
1010 
1011     count = !!item - !!old;
1012     exceptional = !!radix_tree_exceptional_entry(item) -
1013               !!radix_tree_exceptional_entry(old);
1014 
1015     WARN_ON_ONCE(warn_typeswitch && (count || exceptional));
1016 
1017     if (node) {
1018         node->count += count;
1019         if (exceptional) {
1020             exceptional *= slot_count(node, slot);
1021             node->exceptional += exceptional;
1022         }
1023     }
1024 
1025     rcu_assign_pointer(*slot, item);
1026 }
1027 
1028 static inline void delete_sibling_entries(struct radix_tree_node *node,
1029                         void **slot)
1030 {
1031 #ifdef CONFIG_RADIX_TREE_MULTIORDER
1032     bool exceptional = radix_tree_exceptional_entry(*slot);
1033     void *ptr = node_to_entry(slot);
1034     unsigned offset = get_slot_offset(node, slot);
1035     int i;
1036 
1037     for (i = 1; offset + i < RADIX_TREE_MAP_SIZE; i++) {
1038         if (node->slots[offset + i] != ptr)
1039             break;
1040         node->slots[offset + i] = NULL;
1041         node->count--;
1042         if (exceptional)
1043             node->exceptional--;
1044     }
1045 #endif
1046 }
1047 
1048 /**
1049  * __radix_tree_replace     - replace item in a slot
1050  * @root:       radix tree root
1051  * @node:       pointer to tree node
1052  * @slot:       pointer to slot in @node
1053  * @item:       new item to store in the slot.
1054  * @update_node:    callback for changing leaf nodes
1055  * @private:        private data to pass to @update_node
1056  *
1057  * For use with __radix_tree_lookup().  Caller must hold tree write locked
1058  * across slot lookup and replacement.
1059  */
1060 void __radix_tree_replace(struct radix_tree_root *root,
1061               struct radix_tree_node *node,
1062               void **slot, void *item,
1063               radix_tree_update_node_t update_node, void *private)
1064 {
1065     if (!item)
1066         delete_sibling_entries(node, slot);
1067     /*
1068      * This function supports replacing exceptional entries and
1069      * deleting entries, but that needs accounting against the
1070      * node unless the slot is root->rnode.
1071      */
1072     replace_slot(root, node, slot, item,
1073              !node && slot != (void **)&root->rnode);
1074 
1075     if (!node)
1076         return;
1077 
1078     if (update_node)
1079         update_node(node, private);
1080 
1081     delete_node(root, node, update_node, private);
1082 }
1083 
1084 /**
1085  * radix_tree_replace_slot  - replace item in a slot
1086  * @root:   radix tree root
1087  * @slot:   pointer to slot
1088  * @item:   new item to store in the slot.
1089  *
1090  * For use with radix_tree_lookup_slot(), radix_tree_gang_lookup_slot(),
1091  * radix_tree_gang_lookup_tag_slot().  Caller must hold tree write locked
1092  * across slot lookup and replacement.
1093  *
1094  * NOTE: This cannot be used to switch between non-entries (empty slots),
1095  * regular entries, and exceptional entries, as that requires accounting
1096  * inside the radix tree node. When switching from one type of entry or
1097  * deleting, use __radix_tree_lookup() and __radix_tree_replace() or
1098  * radix_tree_iter_replace().
1099  */
1100 void radix_tree_replace_slot(struct radix_tree_root *root,
1101                  void **slot, void *item)
1102 {
1103     replace_slot(root, NULL, slot, item, true);
1104 }
1105 
1106 /**
1107  * radix_tree_iter_replace - replace item in a slot
1108  * @root:   radix tree root
1109  * @slot:   pointer to slot
1110  * @item:   new item to store in the slot.
1111  *
1112  * For use with radix_tree_split() and radix_tree_for_each_slot().
1113  * Caller must hold tree write locked across split and replacement.
1114  */
1115 void radix_tree_iter_replace(struct radix_tree_root *root,
1116         const struct radix_tree_iter *iter, void **slot, void *item)
1117 {
1118     __radix_tree_replace(root, iter->node, slot, item, NULL, NULL);
1119 }
1120 
1121 #ifdef CONFIG_RADIX_TREE_MULTIORDER
1122 /**
1123  * radix_tree_join - replace multiple entries with one multiorder entry
1124  * @root: radix tree root
1125  * @index: an index inside the new entry
1126  * @order: order of the new entry
1127  * @item: new entry
1128  *
1129  * Call this function to replace several entries with one larger entry.
1130  * The existing entries are presumed to not need freeing as a result of
1131  * this call.
1132  *
1133  * The replacement entry will have all the tags set on it that were set
1134  * on any of the entries it is replacing.
1135  */
1136 int radix_tree_join(struct radix_tree_root *root, unsigned long index,
1137             unsigned order, void *item)
1138 {
1139     struct radix_tree_node *node;
1140     void **slot;
1141     int error;
1142 
1143     BUG_ON(radix_tree_is_internal_node(item));
1144 
1145     error = __radix_tree_create(root, index, order, &node, &slot);
1146     if (!error)
1147         error = insert_entries(node, slot, item, order, true);
1148     if (error > 0)
1149         error = 0;
1150 
1151     return error;
1152 }
1153 
1154 /**
1155  * radix_tree_split - Split an entry into smaller entries
1156  * @root: radix tree root
1157  * @index: An index within the large entry
1158  * @order: Order of new entries
1159  *
1160  * Call this function as the first step in replacing a multiorder entry
1161  * with several entries of lower order.  After this function returns,
1162  * loop over the relevant portion of the tree using radix_tree_for_each_slot()
1163  * and call radix_tree_iter_replace() to set up each new entry.
1164  *
1165  * The tags from this entry are replicated to all the new entries.
1166  *
1167  * The radix tree should be locked against modification during the entire
1168  * replacement operation.  Lock-free lookups will see RADIX_TREE_RETRY which
1169  * should prompt RCU walkers to restart the lookup from the root.
1170  */
1171 int radix_tree_split(struct radix_tree_root *root, unsigned long index,
1172                 unsigned order)
1173 {
1174     struct radix_tree_node *parent, *node, *child;
1175     void **slot;
1176     unsigned int offset, end;
1177     unsigned n, tag, tags = 0;
1178 
1179     if (!__radix_tree_lookup(root, index, &parent, &slot))
1180         return -ENOENT;
1181     if (!parent)
1182         return -ENOENT;
1183 
1184     offset = get_slot_offset(parent, slot);
1185 
1186     for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
1187         if (tag_get(parent, tag, offset))
1188             tags |= 1 << tag;
1189 
1190     for (end = offset + 1; end < RADIX_TREE_MAP_SIZE; end++) {
1191         if (!is_sibling_entry(parent, parent->slots[end]))
1192             break;
1193         for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
1194             if (tags & (1 << tag))
1195                 tag_set(parent, tag, end);
1196         /* rcu_assign_pointer ensures tags are set before RETRY */
1197         rcu_assign_pointer(parent->slots[end], RADIX_TREE_RETRY);
1198     }
1199     rcu_assign_pointer(parent->slots[offset], RADIX_TREE_RETRY);
1200     parent->exceptional -= (end - offset);
1201 
1202     if (order == parent->shift)
1203         return 0;
1204     if (order > parent->shift) {
1205         while (offset < end)
1206             offset += insert_entries(parent, &parent->slots[offset],
1207                     RADIX_TREE_RETRY, order, true);
1208         return 0;
1209     }
1210 
1211     node = parent;
1212 
1213     for (;;) {
1214         if (node->shift > order) {
1215             child = radix_tree_node_alloc(root, node,
1216                     node->shift - RADIX_TREE_MAP_SHIFT,
1217                     offset, 0, 0);
1218             if (!child)
1219                 goto nomem;
1220             if (node != parent) {
1221                 node->count++;
1222                 node->slots[offset] = node_to_entry(child);
1223                 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
1224                     if (tags & (1 << tag))
1225                         tag_set(node, tag, offset);
1226             }
1227 
1228             node = child;
1229             offset = 0;
1230             continue;
1231         }
1232 
1233         n = insert_entries(node, &node->slots[offset],
1234                     RADIX_TREE_RETRY, order, false);
1235         BUG_ON(n > RADIX_TREE_MAP_SIZE);
1236 
1237         for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
1238             if (tags & (1 << tag))
1239                 tag_set(node, tag, offset);
1240         offset += n;
1241 
1242         while (offset == RADIX_TREE_MAP_SIZE) {
1243             if (node == parent)
1244                 break;
1245             offset = node->offset;
1246             child = node;
1247             node = node->parent;
1248             rcu_assign_pointer(node->slots[offset],
1249                         node_to_entry(child));
1250             offset++;
1251         }
1252         if ((node == parent) && (offset == end))
1253             return 0;
1254     }
1255 
1256  nomem:
1257     /* Shouldn't happen; did user forget to preload? */
1258     /* TODO: free all the allocated nodes */
1259     WARN_ON(1);
1260     return -ENOMEM;
1261 }
1262 #endif
1263 
1264 /**
1265  *  radix_tree_tag_set - set a tag on a radix tree node
1266  *  @root:      radix tree root
1267  *  @index:     index key
1268  *  @tag:       tag index
1269  *
1270  *  Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
1271  *  corresponding to @index in the radix tree.  From
1272  *  the root all the way down to the leaf node.
1273  *
1274  *  Returns the address of the tagged item.  Setting a tag on a not-present
1275  *  item is a bug.
1276  */
1277 void *radix_tree_tag_set(struct radix_tree_root *root,
1278             unsigned long index, unsigned int tag)
1279 {
1280     struct radix_tree_node *node, *parent;
1281     unsigned long maxindex;
1282 
1283     radix_tree_load_root(root, &node, &maxindex);
1284     BUG_ON(index > maxindex);
1285 
1286     while (radix_tree_is_internal_node(node)) {
1287         unsigned offset;
1288 
1289         parent = entry_to_node(node);
1290         offset = radix_tree_descend(parent, &node, index);
1291         BUG_ON(!node);
1292 
1293         if (!tag_get(parent, tag, offset))
1294             tag_set(parent, tag, offset);
1295     }
1296 
1297     /* set the root's tag bit */
1298     if (!root_tag_get(root, tag))
1299         root_tag_set(root, tag);
1300 
1301     return node;
1302 }
1303 EXPORT_SYMBOL(radix_tree_tag_set);
1304 
1305 static void node_tag_clear(struct radix_tree_root *root,
1306                 struct radix_tree_node *node,
1307                 unsigned int tag, unsigned int offset)
1308 {
1309     while (node) {
1310         if (!tag_get(node, tag, offset))
1311             return;
1312         tag_clear(node, tag, offset);
1313         if (any_tag_set(node, tag))
1314             return;
1315 
1316         offset = node->offset;
1317         node = node->parent;
1318     }
1319 
1320     /* clear the root's tag bit */
1321     if (root_tag_get(root, tag))
1322         root_tag_clear(root, tag);
1323 }
1324 
1325 static void node_tag_set(struct radix_tree_root *root,
1326                 struct radix_tree_node *node,
1327                 unsigned int tag, unsigned int offset)
1328 {
1329     while (node) {
1330         if (tag_get(node, tag, offset))
1331             return;
1332         tag_set(node, tag, offset);
1333         offset = node->offset;
1334         node = node->parent;
1335     }
1336 
1337     if (!root_tag_get(root, tag))
1338         root_tag_set(root, tag);
1339 }
1340 
1341 /**
1342  * radix_tree_iter_tag_set - set a tag on the current iterator entry
1343  * @root:   radix tree root
1344  * @iter:   iterator state
1345  * @tag:    tag to set
1346  */
1347 void radix_tree_iter_tag_set(struct radix_tree_root *root,
1348             const struct radix_tree_iter *iter, unsigned int tag)
1349 {
1350     node_tag_set(root, iter->node, tag, iter_offset(iter));
1351 }
1352 
1353 /**
1354  *  radix_tree_tag_clear - clear a tag on a radix tree node
1355  *  @root:      radix tree root
1356  *  @index:     index key
1357  *  @tag:       tag index
1358  *
1359  *  Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
1360  *  corresponding to @index in the radix tree.  If this causes
1361  *  the leaf node to have no tags set then clear the tag in the
1362  *  next-to-leaf node, etc.
1363  *
1364  *  Returns the address of the tagged item on success, else NULL.  ie:
1365  *  has the same return value and semantics as radix_tree_lookup().
1366  */
1367 void *radix_tree_tag_clear(struct radix_tree_root *root,
1368             unsigned long index, unsigned int tag)
1369 {
1370     struct radix_tree_node *node, *parent;
1371     unsigned long maxindex;
1372     int uninitialized_var(offset);
1373 
1374     radix_tree_load_root(root, &node, &maxindex);
1375     if (index > maxindex)
1376         return NULL;
1377 
1378     parent = NULL;
1379 
1380     while (radix_tree_is_internal_node(node)) {
1381         parent = entry_to_node(node);
1382         offset = radix_tree_descend(parent, &node, index);
1383     }
1384 
1385     if (node)
1386         node_tag_clear(root, parent, tag, offset);
1387 
1388     return node;
1389 }
1390 EXPORT_SYMBOL(radix_tree_tag_clear);
1391 
1392 /**
1393  * radix_tree_tag_get - get a tag on a radix tree node
1394  * @root:       radix tree root
1395  * @index:      index key
1396  * @tag:        tag index (< RADIX_TREE_MAX_TAGS)
1397  *
1398  * Return values:
1399  *
1400  *  0: tag not present or not set
1401  *  1: tag set
1402  *
1403  * Note that the return value of this function may not be relied on, even if
1404  * the RCU lock is held, unless tag modification and node deletion are excluded
1405  * from concurrency.
1406  */
1407 int radix_tree_tag_get(struct radix_tree_root *root,
1408             unsigned long index, unsigned int tag)
1409 {
1410     struct radix_tree_node *node, *parent;
1411     unsigned long maxindex;
1412 
1413     if (!root_tag_get(root, tag))
1414         return 0;
1415 
1416     radix_tree_load_root(root, &node, &maxindex);
1417     if (index > maxindex)
1418         return 0;
1419     if (node == NULL)
1420         return 0;
1421 
1422     while (radix_tree_is_internal_node(node)) {
1423         unsigned offset;
1424 
1425         parent = entry_to_node(node);
1426         offset = radix_tree_descend(parent, &node, index);
1427 
1428         if (!node)
1429             return 0;
1430         if (!tag_get(parent, tag, offset))
1431             return 0;
1432         if (node == RADIX_TREE_RETRY)
1433             break;
1434     }
1435 
1436     return 1;
1437 }
1438 EXPORT_SYMBOL(radix_tree_tag_get);
1439 
1440 static inline void __set_iter_shift(struct radix_tree_iter *iter,
1441                     unsigned int shift)
1442 {
1443 #ifdef CONFIG_RADIX_TREE_MULTIORDER
1444     iter->shift = shift;
1445 #endif
1446 }
1447 
1448 /* Construct iter->tags bit-mask from node->tags[tag] array */
1449 static void set_iter_tags(struct radix_tree_iter *iter,
1450                 struct radix_tree_node *node, unsigned offset,
1451                 unsigned tag)
1452 {
1453     unsigned tag_long = offset / BITS_PER_LONG;
1454     unsigned tag_bit  = offset % BITS_PER_LONG;
1455 
1456     iter->tags = node->tags[tag][tag_long] >> tag_bit;
1457 
1458     /* This never happens if RADIX_TREE_TAG_LONGS == 1 */
1459     if (tag_long < RADIX_TREE_TAG_LONGS - 1) {
1460         /* Pick tags from next element */
1461         if (tag_bit)
1462             iter->tags |= node->tags[tag][tag_long + 1] <<
1463                         (BITS_PER_LONG - tag_bit);
1464         /* Clip chunk size, here only BITS_PER_LONG tags */
1465         iter->next_index = __radix_tree_iter_add(iter, BITS_PER_LONG);
1466     }
1467 }
1468 
1469 #ifdef CONFIG_RADIX_TREE_MULTIORDER
1470 static void **skip_siblings(struct radix_tree_node **nodep,
1471             void **slot, struct radix_tree_iter *iter)
1472 {
1473     void *sib = node_to_entry(slot - 1);
1474 
1475     while (iter->index < iter->next_index) {
1476         *nodep = rcu_dereference_raw(*slot);
1477         if (*nodep && *nodep != sib)
1478             return slot;
1479         slot++;
1480         iter->index = __radix_tree_iter_add(iter, 1);
1481         iter->tags >>= 1;
1482     }
1483 
1484     *nodep = NULL;
1485     return NULL;
1486 }
1487 
1488 void ** __radix_tree_next_slot(void **slot, struct radix_tree_iter *iter,
1489                     unsigned flags)
1490 {
1491     unsigned tag = flags & RADIX_TREE_ITER_TAG_MASK;
1492     struct radix_tree_node *node = rcu_dereference_raw(*slot);
1493 
1494     slot = skip_siblings(&node, slot, iter);
1495 
1496     while (radix_tree_is_internal_node(node)) {
1497         unsigned offset;
1498         unsigned long next_index;
1499 
1500         if (node == RADIX_TREE_RETRY)
1501             return slot;
1502         node = entry_to_node(node);
1503         iter->node = node;
1504         iter->shift = node->shift;
1505 
1506         if (flags & RADIX_TREE_ITER_TAGGED) {
1507             offset = radix_tree_find_next_bit(node, tag, 0);
1508             if (offset == RADIX_TREE_MAP_SIZE)
1509                 return NULL;
1510             slot = &node->slots[offset];
1511             iter->index = __radix_tree_iter_add(iter, offset);
1512             set_iter_tags(iter, node, offset, tag);
1513             node = rcu_dereference_raw(*slot);
1514         } else {
1515             offset = 0;
1516             slot = &node->slots[0];
1517             for (;;) {
1518                 node = rcu_dereference_raw(*slot);
1519                 if (node)
1520                     break;
1521                 slot++;
1522                 offset++;
1523                 if (offset == RADIX_TREE_MAP_SIZE)
1524                     return NULL;
1525             }
1526             iter->index = __radix_tree_iter_add(iter, offset);
1527         }
1528         if ((flags & RADIX_TREE_ITER_CONTIG) && (offset > 0))
1529             goto none;
1530         next_index = (iter->index | shift_maxindex(iter->shift)) + 1;
1531         if (next_index < iter->next_index)
1532             iter->next_index = next_index;
1533     }
1534 
1535     return slot;
1536  none:
1537     iter->next_index = 0;
1538     return NULL;
1539 }
1540 EXPORT_SYMBOL(__radix_tree_next_slot);
1541 #else
1542 static void **skip_siblings(struct radix_tree_node **nodep,
1543             void **slot, struct radix_tree_iter *iter)
1544 {
1545     return slot;
1546 }
1547 #endif
1548 
1549 void **radix_tree_iter_resume(void **slot, struct radix_tree_iter *iter)
1550 {
1551     struct radix_tree_node *node;
1552 
1553     slot++;
1554     iter->index = __radix_tree_iter_add(iter, 1);
1555     node = rcu_dereference_raw(*slot);
1556     skip_siblings(&node, slot, iter);
1557     iter->next_index = iter->index;
1558     iter->tags = 0;
1559     return NULL;
1560 }
1561 EXPORT_SYMBOL(radix_tree_iter_resume);
1562 
1563 /**
1564  * radix_tree_next_chunk - find next chunk of slots for iteration
1565  *
1566  * @root:   radix tree root
1567  * @iter:   iterator state
1568  * @flags:  RADIX_TREE_ITER_* flags and tag index
1569  * Returns: pointer to chunk first slot, or NULL if iteration is over
1570  */
1571 void **radix_tree_next_chunk(struct radix_tree_root *root,
1572                  struct radix_tree_iter *iter, unsigned flags)
1573 {
1574     unsigned tag = flags & RADIX_TREE_ITER_TAG_MASK;
1575     struct radix_tree_node *node, *child;
1576     unsigned long index, offset, maxindex;
1577 
1578     if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag))
1579         return NULL;
1580 
1581     /*
1582      * Catch next_index overflow after ~0UL. iter->index never overflows
1583      * during iterating; it can be zero only at the beginning.
1584      * And we cannot overflow iter->next_index in a single step,
1585      * because RADIX_TREE_MAP_SHIFT < BITS_PER_LONG.
1586      *
1587      * This condition also used by radix_tree_next_slot() to stop
1588      * contiguous iterating, and forbid switching to the next chunk.
1589      */
1590     index = iter->next_index;
1591     if (!index && iter->index)
1592         return NULL;
1593 
1594  restart:
1595     radix_tree_load_root(root, &child, &maxindex);
1596     if (index > maxindex)
1597         return NULL;
1598     if (!child)
1599         return NULL;
1600 
1601     if (!radix_tree_is_internal_node(child)) {
1602         /* Single-slot tree */
1603         iter->index = index;
1604         iter->next_index = maxindex + 1;
1605         iter->tags = 1;
1606         iter->node = NULL;
1607         __set_iter_shift(iter, 0);
1608         return (void **)&root->rnode;
1609     }
1610 
1611     do {
1612         node = entry_to_node(child);
1613         offset = radix_tree_descend(node, &child, index);
1614 
1615         if ((flags & RADIX_TREE_ITER_TAGGED) ?
1616                 !tag_get(node, tag, offset) : !child) {
1617             /* Hole detected */
1618             if (flags & RADIX_TREE_ITER_CONTIG)
1619                 return NULL;
1620 
1621             if (flags & RADIX_TREE_ITER_TAGGED)
1622                 offset = radix_tree_find_next_bit(node, tag,
1623                         offset + 1);
1624             else
1625                 while (++offset < RADIX_TREE_MAP_SIZE) {
1626                     void *slot = node->slots[offset];
1627                     if (is_sibling_entry(node, slot))
1628                         continue;
1629                     if (slot)
1630                         break;
1631                 }
1632             index &= ~node_maxindex(node);
1633             index += offset << node->shift;
1634             /* Overflow after ~0UL */
1635             if (!index)
1636                 return NULL;
1637             if (offset == RADIX_TREE_MAP_SIZE)
1638                 goto restart;
1639             child = rcu_dereference_raw(node->slots[offset]);
1640         }
1641 
1642         if (!child)
1643             goto restart;
1644         if (child == RADIX_TREE_RETRY)
1645             break;
1646     } while (radix_tree_is_internal_node(child));
1647 
1648     /* Update the iterator state */
1649     iter->index = (index &~ node_maxindex(node)) | (offset << node->shift);
1650     iter->next_index = (index | node_maxindex(node)) + 1;
1651     iter->node = node;
1652     __set_iter_shift(iter, node->shift);
1653 
1654     if (flags & RADIX_TREE_ITER_TAGGED)
1655         set_iter_tags(iter, node, offset, tag);
1656 
1657     return node->slots + offset;
1658 }
1659 EXPORT_SYMBOL(radix_tree_next_chunk);
1660 
1661 /**
1662  *  radix_tree_gang_lookup - perform multiple lookup on a radix tree
1663  *  @root:      radix tree root
1664  *  @results:   where the results of the lookup are placed
1665  *  @first_index:   start the lookup from this key
1666  *  @max_items: place up to this many items at *results
1667  *
1668  *  Performs an index-ascending scan of the tree for present items.  Places
1669  *  them at *@results and returns the number of items which were placed at
1670  *  *@results.
1671  *
1672  *  The implementation is naive.
1673  *
1674  *  Like radix_tree_lookup, radix_tree_gang_lookup may be called under
1675  *  rcu_read_lock. In this case, rather than the returned results being
1676  *  an atomic snapshot of the tree at a single point in time, the
1677  *  semantics of an RCU protected gang lookup are as though multiple
1678  *  radix_tree_lookups have been issued in individual locks, and results
1679  *  stored in 'results'.
1680  */
1681 unsigned int
1682 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
1683             unsigned long first_index, unsigned int max_items)
1684 {
1685     struct radix_tree_iter iter;
1686     void **slot;
1687     unsigned int ret = 0;
1688 
1689     if (unlikely(!max_items))
1690         return 0;
1691 
1692     radix_tree_for_each_slot(slot, root, &iter, first_index) {
1693         results[ret] = rcu_dereference_raw(*slot);
1694         if (!results[ret])
1695             continue;
1696         if (radix_tree_is_internal_node(results[ret])) {
1697             slot = radix_tree_iter_retry(&iter);
1698             continue;
1699         }
1700         if (++ret == max_items)
1701             break;
1702     }
1703 
1704     return ret;
1705 }
1706 EXPORT_SYMBOL(radix_tree_gang_lookup);
1707 
1708 /**
1709  *  radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree
1710  *  @root:      radix tree root
1711  *  @results:   where the results of the lookup are placed
1712  *  @indices:   where their indices should be placed (but usually NULL)
1713  *  @first_index:   start the lookup from this key
1714  *  @max_items: place up to this many items at *results
1715  *
1716  *  Performs an index-ascending scan of the tree for present items.  Places
1717  *  their slots at *@results and returns the number of items which were
1718  *  placed at *@results.
1719  *
1720  *  The implementation is naive.
1721  *
1722  *  Like radix_tree_gang_lookup as far as RCU and locking goes. Slots must
1723  *  be dereferenced with radix_tree_deref_slot, and if using only RCU
1724  *  protection, radix_tree_deref_slot may fail requiring a retry.
1725  */
1726 unsigned int
1727 radix_tree_gang_lookup_slot(struct radix_tree_root *root,
1728             void ***results, unsigned long *indices,
1729             unsigned long first_index, unsigned int max_items)
1730 {
1731     struct radix_tree_iter iter;
1732     void **slot;
1733     unsigned int ret = 0;
1734 
1735     if (unlikely(!max_items))
1736         return 0;
1737 
1738     radix_tree_for_each_slot(slot, root, &iter, first_index) {
1739         results[ret] = slot;
1740         if (indices)
1741             indices[ret] = iter.index;
1742         if (++ret == max_items)
1743             break;
1744     }
1745 
1746     return ret;
1747 }
1748 EXPORT_SYMBOL(radix_tree_gang_lookup_slot);
1749 
1750 /**
1751  *  radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
1752  *                               based on a tag
1753  *  @root:      radix tree root
1754  *  @results:   where the results of the lookup are placed
1755  *  @first_index:   start the lookup from this key
1756  *  @max_items: place up to this many items at *results
1757  *  @tag:       the tag index (< RADIX_TREE_MAX_TAGS)
1758  *
1759  *  Performs an index-ascending scan of the tree for present items which
1760  *  have the tag indexed by @tag set.  Places the items at *@results and
1761  *  returns the number of items which were placed at *@results.
1762  */
1763 unsigned int
1764 radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
1765         unsigned long first_index, unsigned int max_items,
1766         unsigned int tag)
1767 {
1768     struct radix_tree_iter iter;
1769     void **slot;
1770     unsigned int ret = 0;
1771 
1772     if (unlikely(!max_items))
1773         return 0;
1774 
1775     radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) {
1776         results[ret] = rcu_dereference_raw(*slot);
1777         if (!results[ret])
1778             continue;
1779         if (radix_tree_is_internal_node(results[ret])) {
1780             slot = radix_tree_iter_retry(&iter);
1781             continue;
1782         }
1783         if (++ret == max_items)
1784             break;
1785     }
1786 
1787     return ret;
1788 }
1789 EXPORT_SYMBOL(radix_tree_gang_lookup_tag);
1790 
1791 /**
1792  *  radix_tree_gang_lookup_tag_slot - perform multiple slot lookup on a
1793  *                    radix tree based on a tag
1794  *  @root:      radix tree root
1795  *  @results:   where the results of the lookup are placed
1796  *  @first_index:   start the lookup from this key
1797  *  @max_items: place up to this many items at *results
1798  *  @tag:       the tag index (< RADIX_TREE_MAX_TAGS)
1799  *
1800  *  Performs an index-ascending scan of the tree for present items which
1801  *  have the tag indexed by @tag set.  Places the slots at *@results and
1802  *  returns the number of slots which were placed at *@results.
1803  */
1804 unsigned int
1805 radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
1806         unsigned long first_index, unsigned int max_items,
1807         unsigned int tag)
1808 {
1809     struct radix_tree_iter iter;
1810     void **slot;
1811     unsigned int ret = 0;
1812 
1813     if (unlikely(!max_items))
1814         return 0;
1815 
1816     radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) {
1817         results[ret] = slot;
1818         if (++ret == max_items)
1819             break;
1820     }
1821 
1822     return ret;
1823 }
1824 EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot);
1825 
1826 /**
1827  *  __radix_tree_delete_node    -    try to free node after clearing a slot
1828  *  @root:      radix tree root
1829  *  @node:      node containing @index
1830  *  @update_node:   callback for changing leaf nodes
1831  *  @private:   private data to pass to @update_node
1832  *
1833  *  After clearing the slot at @index in @node from radix tree
1834  *  rooted at @root, call this function to attempt freeing the
1835  *  node and shrinking the tree.
1836  */
1837 void __radix_tree_delete_node(struct radix_tree_root *root,
1838                   struct radix_tree_node *node,
1839                   radix_tree_update_node_t update_node,
1840                   void *private)
1841 {
1842     delete_node(root, node, update_node, private);
1843 }
1844 
1845 /**
1846  *  radix_tree_delete_item    -    delete an item from a radix tree
1847  *  @root:      radix tree root
1848  *  @index:     index key
1849  *  @item:      expected item
1850  *
1851  *  Remove @item at @index from the radix tree rooted at @root.
1852  *
1853  *  Returns the address of the deleted item, or NULL if it was not present
1854  *  or the entry at the given @index was not @item.
1855  */
1856 void *radix_tree_delete_item(struct radix_tree_root *root,
1857                  unsigned long index, void *item)
1858 {
1859     struct radix_tree_node *node;
1860     unsigned int offset;
1861     void **slot;
1862     void *entry;
1863     int tag;
1864 
1865     entry = __radix_tree_lookup(root, index, &node, &slot);
1866     if (!entry)
1867         return NULL;
1868 
1869     if (item && entry != item)
1870         return NULL;
1871 
1872     if (!node) {
1873         root_tag_clear_all(root);
1874         root->rnode = NULL;
1875         return entry;
1876     }
1877 
1878     offset = get_slot_offset(node, slot);
1879 
1880     /* Clear all tags associated with the item to be deleted.  */
1881     for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
1882         node_tag_clear(root, node, tag, offset);
1883 
1884     __radix_tree_replace(root, node, slot, NULL, NULL, NULL);
1885 
1886     return entry;
1887 }
1888 EXPORT_SYMBOL(radix_tree_delete_item);
1889 
1890 /**
1891  *  radix_tree_delete    -    delete an item from a radix tree
1892  *  @root:      radix tree root
1893  *  @index:     index key
1894  *
1895  *  Remove the item at @index from the radix tree rooted at @root.
1896  *
1897  *  Returns the address of the deleted item, or NULL if it was not present.
1898  */
1899 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
1900 {
1901     return radix_tree_delete_item(root, index, NULL);
1902 }
1903 EXPORT_SYMBOL(radix_tree_delete);
1904 
1905 void radix_tree_clear_tags(struct radix_tree_root *root,
1906                struct radix_tree_node *node,
1907                void **slot)
1908 {
1909     if (node) {
1910         unsigned int tag, offset = get_slot_offset(node, slot);
1911         for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
1912             node_tag_clear(root, node, tag, offset);
1913     } else {
1914         /* Clear root node tags */
1915         root->gfp_mask &= __GFP_BITS_MASK;
1916     }
1917 }
1918 
1919 /**
1920  *  radix_tree_tagged - test whether any items in the tree are tagged
1921  *  @root:      radix tree root
1922  *  @tag:       tag to test
1923  */
1924 int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag)
1925 {
1926     return root_tag_get(root, tag);
1927 }
1928 EXPORT_SYMBOL(radix_tree_tagged);
1929 
1930 static void
1931 radix_tree_node_ctor(void *arg)
1932 {
1933     struct radix_tree_node *node = arg;
1934 
1935     memset(node, 0, sizeof(*node));
1936     INIT_LIST_HEAD(&node->private_list);
1937 }
1938 
1939 static __init unsigned long __maxindex(unsigned int height)
1940 {
1941     unsigned int width = height * RADIX_TREE_MAP_SHIFT;
1942     int shift = RADIX_TREE_INDEX_BITS - width;
1943 
1944     if (shift < 0)
1945         return ~0UL;
1946     if (shift >= BITS_PER_LONG)
1947         return 0UL;
1948     return ~0UL >> shift;
1949 }
1950 
1951 static __init void radix_tree_init_maxnodes(void)
1952 {
1953     unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1];
1954     unsigned int i, j;
1955 
1956     for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
1957         height_to_maxindex[i] = __maxindex(i);
1958     for (i = 0; i < ARRAY_SIZE(height_to_maxnodes); i++) {
1959         for (j = i; j > 0; j--)
1960             height_to_maxnodes[i] += height_to_maxindex[j - 1] + 1;
1961     }
1962 }
1963 
1964 static int radix_tree_cpu_dead(unsigned int cpu)
1965 {
1966     struct radix_tree_preload *rtp;
1967     struct radix_tree_node *node;
1968 
1969     /* Free per-cpu pool of preloaded nodes */
1970     rtp = &per_cpu(radix_tree_preloads, cpu);
1971     while (rtp->nr) {
1972         node = rtp->nodes;
1973         rtp->nodes = node->private_data;
1974         kmem_cache_free(radix_tree_node_cachep, node);
1975         rtp->nr--;
1976     }
1977     return 0;
1978 }
1979 
1980 void __init radix_tree_init(void)
1981 {
1982     int ret;
1983     radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
1984             sizeof(struct radix_tree_node), 0,
1985             SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
1986             radix_tree_node_ctor);
1987     radix_tree_init_maxnodes();
1988     ret = cpuhp_setup_state_nocalls(CPUHP_RADIX_DEAD, "lib/radix:dead",
1989                     NULL, radix_tree_cpu_dead);
1990     WARN_ON(ret < 0);
1991 }