i2c-eg20t: use i2c_add_numbered_adapter to get a fixed bus number
[linux-2.6.git] / lib / radix-tree.c
index 0871582..dc63d08 100644 (file)
 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];
+       union {
+               struct radix_tree_node *parent; /* Used when ascending tree */
+               struct rcu_head rcu_head;       /* Used when freeing node */
+       };
+       void __rcu      *slots[RADIX_TREE_MAP_SIZE];
        unsigned long   tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
 };
 
-struct radix_tree_path {
-       struct radix_tree_node *node;
-       int offset;
-};
-
 #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))
@@ -82,6 +80,16 @@ struct radix_tree_preload {
 };
 static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
 
+static inline void *ptr_to_indirect(void *ptr)
+{
+       return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR);
+}
+
+static inline void *indirect_to_ptr(void *ptr)
+{
+       return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR);
+}
+
 static inline gfp_t root_gfp_mask(struct radix_tree_root *root)
 {
        return root->gfp_mask & __GFP_BITS_MASK;
@@ -174,14 +182,16 @@ 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);
+       int i;
 
        /*
         * must only free zeroed nodes into the slab. radix_tree_shrink
         * can leave us with a non-NULL entry in the first slot, so clear
         * that here to make sure.
         */
-       tag_clear(node, 0, 0);
-       tag_clear(node, 1, 0);
+       for (i = 0; i < RADIX_TREE_MAX_TAGS; i++)
+               tag_clear(node, i, 0);
+
        node->slots[0] = NULL;
        node->count = 0;
 
@@ -244,6 +254,7 @@ static inline unsigned long radix_tree_maxindex(unsigned int height)
 static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
 {
        struct radix_tree_node *node;
+       struct radix_tree_node *slot;
        unsigned int height;
        int tag;
 
@@ -262,19 +273,24 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
                if (!(node = radix_tree_node_alloc(root)))
                        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);
                }
 
+               /* Increase the height.  */
                newheight = root->height+1;
                node->height = newheight;
                node->count = 1;
-               node = radix_tree_ptr_to_indirect(node);
+               node->parent = NULL;
+               slot = root->rnode;
+               if (newheight > 1) {
+                       slot = indirect_to_ptr(slot);
+                       slot->parent = node;
+               }
+               node->slots[0] = slot;
+               node = ptr_to_indirect(node);
                rcu_assign_pointer(root->rnode, node);
                root->height = newheight;
        } while (height > root->height);
@@ -307,7 +323,7 @@ int radix_tree_insert(struct radix_tree_root *root,
                        return error;
        }
 
-       slot = radix_tree_indirect_to_ptr(root->rnode);
+       slot = indirect_to_ptr(root->rnode);
 
        height = root->height;
        shift = (height-1) * RADIX_TREE_MAP_SHIFT;
@@ -319,12 +335,12 @@ int radix_tree_insert(struct radix_tree_root *root,
                        if (!(slot = radix_tree_node_alloc(root)))
                                return -ENOMEM;
                        slot->height = height;
+                       slot->parent = node;
                        if (node) {
                                rcu_assign_pointer(node->slots[offset], slot);
                                node->count++;
                        } else
-                               rcu_assign_pointer(root->rnode,
-                                       radix_tree_ptr_to_indirect(slot));
+                               rcu_assign_pointer(root->rnode, ptr_to_indirect(slot));
                }
 
                /* Go a level down */
@@ -372,7 +388,7 @@ static void *radix_tree_lookup_element(struct radix_tree_root *root,
                        return NULL;
                return is_slot ? (void *)&root->rnode : node;
        }
-       node = radix_tree_indirect_to_ptr(node);
+       node = indirect_to_ptr(node);
 
        height = node->height;
        if (index > radix_tree_maxindex(height))
@@ -391,7 +407,7 @@ static void *radix_tree_lookup_element(struct radix_tree_root *root,
                height--;
        } while (height > 0);
 
-       return is_slot ? (void *)slot:node;
+       return is_slot ? (void *)slot : indirect_to_ptr(node);
 }
 
 /**
@@ -453,7 +469,7 @@ void *radix_tree_tag_set(struct radix_tree_root *root,
        height = root->height;
        BUG_ON(index > radix_tree_maxindex(height));
 
-       slot = radix_tree_indirect_to_ptr(root->rnode);
+       slot = indirect_to_ptr(root->rnode);
        shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
 
        while (height > 0) {
@@ -493,47 +509,41 @@ EXPORT_SYMBOL(radix_tree_tag_set);
 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_node *node = NULL;
        struct radix_tree_node *slot = NULL;
        unsigned int height, shift;
+       int uninitialized_var(offset);
 
        height = root->height;
        if (index > radix_tree_maxindex(height))
                goto out;
 
-       shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
-       pathp->node = NULL;
-       slot = radix_tree_indirect_to_ptr(root->rnode);
-
-       while (height > 0) {
-               int offset;
+       shift = height * RADIX_TREE_MAP_SHIFT;
+       slot = indirect_to_ptr(root->rnode);
 
+       while (shift) {
                if (slot == NULL)
                        goto out;
 
+               shift -= RADIX_TREE_MAP_SHIFT;
                offset = (index >> shift) & RADIX_TREE_MAP_MASK;
-               pathp[1].offset = offset;
-               pathp[1].node = slot;
+               node = slot;
                slot = slot->slots[offset];
-               pathp++;
-               shift -= RADIX_TREE_MAP_SHIFT;
-               height--;
        }
 
        if (slot == NULL)
                goto out;
 
-       while (pathp->node) {
-               if (!tag_get(pathp->node, tag, pathp->offset))
+       while (node) {
+               if (!tag_get(node, tag, offset))
                        goto out;
-               tag_clear(pathp->node, tag, pathp->offset);
-               if (any_tag_set(pathp->node, tag))
+               tag_clear(node, tag, offset);
+               if (any_tag_set(node, tag))
                        goto out;
-               pathp--;
+
+               index >>= RADIX_TREE_MAP_SHIFT;
+               offset = index & RADIX_TREE_MAP_MASK;
+               node = node->parent;
        }
 
        /* clear the root's tag bit */
@@ -555,13 +565,16 @@ EXPORT_SYMBOL(radix_tree_tag_clear);
  *
  *  0: tag not present or not set
  *  1: tag set
+ *
+ * Note that the return value of this function may not be relied on, even if
+ * the RCU lock is held, unless tag modification and node deletion are excluded
+ * from concurrency.
  */
 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))
@@ -573,7 +586,7 @@ int radix_tree_tag_get(struct radix_tree_root *root,
 
        if (!radix_tree_is_indirect_ptr(node))
                return (index == 0);
-       node = radix_tree_indirect_to_ptr(node);
+       node = indirect_to_ptr(node);
 
        height = node->height;
        if (index > radix_tree_maxindex(height))
@@ -588,19 +601,10 @@ int radix_tree_tag_get(struct radix_tree_root *root,
                        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;
-               }
+                       return 0;
+               if (height == 1)
+                       return 1;
                node = rcu_dereference_raw(node->slots[offset]);
                shift -= RADIX_TREE_MAP_SHIFT;
                height--;
@@ -609,6 +613,137 @@ int radix_tree_tag_get(struct radix_tree_root *root,
 EXPORT_SYMBOL(radix_tree_tag_get);
 
 /**
+ * radix_tree_range_tag_if_tagged - for each item in given range set given
+ *                                tag if item has another tag set
+ * @root:              radix tree root
+ * @first_indexp:      pointer to a starting index of a range to scan
+ * @last_index:                last index of a range to scan
+ * @nr_to_tag:         maximum number items to tag
+ * @iftag:             tag index to test
+ * @settag:            tag index to set if tested tag is set
+ *
+ * This function scans range of radix tree from first_index to last_index
+ * (inclusive).  For each item in the range if iftag is set, the function sets
+ * also settag. The function stops either after tagging nr_to_tag items or
+ * after reaching last_index.
+ *
+ * The tags must be set from the leaf level only and propagated back up the
+ * path to the root. We must do this so that we resolve the full path before
+ * setting any tags on intermediate nodes. If we set tags as we descend, then
+ * we can get to the leaf node and find that the index that has the iftag
+ * set is outside the range we are scanning. This reults in dangling tags and
+ * can lead to problems with later tag operations (e.g. livelocks on lookups).
+ *
+ * The function returns number of leaves where the tag was set and sets
+ * *first_indexp to the first unscanned index.
+ * WARNING! *first_indexp can wrap if last_index is ULONG_MAX. Caller must
+ * be prepared to handle that.
+ */
+unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
+               unsigned long *first_indexp, unsigned long last_index,
+               unsigned long nr_to_tag,
+               unsigned int iftag, unsigned int settag)
+{
+       unsigned int height = root->height;
+       struct radix_tree_node *node = NULL;
+       struct radix_tree_node *slot;
+       unsigned int shift;
+       unsigned long tagged = 0;
+       unsigned long index = *first_indexp;
+
+       last_index = min(last_index, radix_tree_maxindex(height));
+       if (index > last_index)
+               return 0;
+       if (!nr_to_tag)
+               return 0;
+       if (!root_tag_get(root, iftag)) {
+               *first_indexp = last_index + 1;
+               return 0;
+       }
+       if (height == 0) {
+               *first_indexp = last_index + 1;
+               root_tag_set(root, settag);
+               return 1;
+       }
+
+       shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
+       slot = indirect_to_ptr(root->rnode);
+
+       for (;;) {
+               unsigned long upindex;
+               int offset;
+
+               offset = (index >> shift) & RADIX_TREE_MAP_MASK;
+               if (!slot->slots[offset])
+                       goto next;
+               if (!tag_get(slot, iftag, offset))
+                       goto next;
+               if (shift) {
+                       /* Go down one level */
+                       shift -= RADIX_TREE_MAP_SHIFT;
+                       node = slot;
+                       slot = slot->slots[offset];
+                       continue;
+               }
+
+               /* tag the leaf */
+               tagged++;
+               tag_set(slot, settag, offset);
+
+               /* walk back up the path tagging interior nodes */
+               upindex = index;
+               while (node) {
+                       upindex >>= RADIX_TREE_MAP_SHIFT;
+                       offset = upindex & RADIX_TREE_MAP_MASK;
+
+                       /* stop if we find a node with the tag already set */
+                       if (tag_get(node, settag, offset))
+                               break;
+                       tag_set(node, settag, offset);
+                       node = node->parent;
+               }
+
+               /*
+                * Small optimization: now clear that node pointer.
+                * Since all of this slot's ancestors now have the tag set
+                * from setting it above, we have no further need to walk
+                * back up the tree setting tags, until we update slot to
+                * point to another radix_tree_node.
+                */
+               node = NULL;
+
+next:
+               /* Go to next item at level determined by 'shift' */
+               index = ((index >> shift) + 1) << shift;
+               /* Overflow can happen when last_index is ~0UL... */
+               if (index > last_index || !index)
+                       break;
+               if (tagged >= nr_to_tag)
+                       break;
+               while (((index >> shift) & RADIX_TREE_MAP_MASK) == 0) {
+                       /*
+                        * We've fully scanned this node. Go up. Because
+                        * last_index is guaranteed to be in the tree, what
+                        * we do below cannot wander astray.
+                        */
+                       slot = slot->parent;
+                       shift += RADIX_TREE_MAP_SHIFT;
+               }
+       }
+       /*
+        * We need not to tag the root tag if there is no tag which is set with
+        * settag within the range from *first_indexp to last_index.
+        */
+       if (tagged > 0)
+               root_tag_set(root, settag);
+       *first_indexp = index;
+
+       return tagged;
+}
+EXPORT_SYMBOL(radix_tree_range_tag_if_tagged);
+
+
+/**
  *     radix_tree_next_hole    -    find the next hole (not-present entry)
  *     @root:          tree root
  *     @index:         index key
@@ -656,7 +791,7 @@ EXPORT_SYMBOL(radix_tree_next_hole);
  *
  *     Returns: the index of the hole if found, otherwise returns an index
  *     outside of the set specified (in which case 'index - return >= max_scan'
- *     will be true). In rare cases of wrap-around, LONG_MAX will be returned.
+ *     will be true). In rare cases of wrap-around, ULONG_MAX will be returned.
  *
  *     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
@@ -674,7 +809,7 @@ unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
                if (!radix_tree_lookup(root, index))
                        break;
                index--;
-               if (index == LONG_MAX)
+               if (index == ULONG_MAX)
                        break;
        }
 
@@ -683,8 +818,8 @@ unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
 EXPORT_SYMBOL(radix_tree_prev_hole);
 
 static unsigned int
-__lookup(struct radix_tree_node *slot, void ***results, unsigned long index,
-       unsigned int max_items, unsigned long *next_index)
+__lookup(struct radix_tree_node *slot, void ***results, unsigned long *indices,
+       unsigned long index, unsigned int max_items, unsigned long *next_index)
 {
        unsigned int nr_found = 0;
        unsigned int shift, height;
@@ -717,12 +852,16 @@ __lookup(struct radix_tree_node *slot, void ***results, unsigned long index,
 
        /* 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)
+                       results[nr_found] = &(slot->slots[i]);
+                       if (indices)
+                               indices[nr_found] = index;
+                       if (++nr_found == max_items) {
+                               index++;
                                goto out;
+                       }
                }
+               index++;
        }
 out:
        *next_index = index;
@@ -767,7 +906,7 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
                results[0] = node;
                return 1;
        }
-       node = radix_tree_indirect_to_ptr(node);
+       node = indirect_to_ptr(node);
 
        max_index = radix_tree_maxindex(node->height);
 
@@ -778,15 +917,16 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
 
                if (cur_index > max_index)
                        break;
-               slots_found = __lookup(node, (void ***)results + ret, cur_index,
-                                       max_items - ret, &next_index);
+               slots_found = __lookup(node, (void ***)results + ret, NULL,
+                               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_raw(slot);
+                       results[ret + nr_found] =
+                               indirect_to_ptr(rcu_dereference_raw(slot));
                        nr_found++;
                }
                ret += nr_found;
@@ -803,6 +943,7 @@ 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
+ *     @indices:       where their indices should be placed (but usually NULL)
  *     @first_index:   start the lookup from this key
  *     @max_items:     place up to this many items at *results
  *
@@ -817,7 +958,8 @@ EXPORT_SYMBOL(radix_tree_gang_lookup);
  *     protection, radix_tree_deref_slot may fail requiring a retry.
  */
 unsigned int
-radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
+radix_tree_gang_lookup_slot(struct radix_tree_root *root,
+                       void ***results, unsigned long *indices,
                        unsigned long first_index, unsigned int max_items)
 {
        unsigned long max_index;
@@ -833,9 +975,11 @@ radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
                if (first_index > 0)
                        return 0;
                results[0] = (void **)&root->rnode;
+               if (indices)
+                       indices[0] = 0;
                return 1;
        }
-       node = radix_tree_indirect_to_ptr(node);
+       node = indirect_to_ptr(node);
 
        max_index = radix_tree_maxindex(node->height);
 
@@ -846,8 +990,9 @@ radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
 
                if (cur_index > max_index)
                        break;
-               slots_found = __lookup(node, results + ret, cur_index,
-                                       max_items - ret, &next_index);
+               slots_found = __lookup(node, results + ret,
+                               indices ? indices + ret : NULL,
+                               cur_index, max_items - ret, &next_index);
                ret += slots_found;
                if (next_index == 0)
                        break;
@@ -960,7 +1105,7 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
                results[0] = node;
                return 1;
        }
-       node = radix_tree_indirect_to_ptr(node);
+       node = indirect_to_ptr(node);
 
        max_index = radix_tree_maxindex(node->height);
 
@@ -979,7 +1124,8 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
                        slot = *(((void ***)results)[ret + i]);
                        if (!slot)
                                continue;
-                       results[ret + nr_found] = rcu_dereference_raw(slot);
+                       results[ret + nr_found] =
+                               indirect_to_ptr(rcu_dereference_raw(slot));
                        nr_found++;
                }
                ret += nr_found;
@@ -1029,7 +1175,7 @@ radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
                results[0] = (void **)&root->rnode;
                return 1;
        }
-       node = radix_tree_indirect_to_ptr(node);
+       node = indirect_to_ptr(node);
 
        max_index = radix_tree_maxindex(node->height);
 
@@ -1052,6 +1198,98 @@ radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
 }
 EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot);
 
+#if defined(CONFIG_SHMEM) && defined(CONFIG_SWAP)
+#include <linux/sched.h> /* for cond_resched() */
+
+/*
+ * This linear search is at present only useful to shmem_unuse_inode().
+ */
+static unsigned long __locate(struct radix_tree_node *slot, void *item,
+                             unsigned long index, unsigned long *found_index)
+{
+       unsigned int shift, height;
+       unsigned long i;
+
+       height = slot->height;
+       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_raw(slot->slots[i]);
+               if (slot == NULL)
+                       goto out;
+       }
+
+       /* Bottom level: check items */
+       for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
+               if (slot->slots[i] == item) {
+                       *found_index = index + i;
+                       index = 0;
+                       goto out;
+               }
+       }
+       index += RADIX_TREE_MAP_SIZE;
+out:
+       return index;
+}
+
+/**
+ *     radix_tree_locate_item - search through radix tree for item
+ *     @root:          radix tree root
+ *     @item:          item to be found
+ *
+ *     Returns index where item was found, or -1 if not found.
+ *     Caller must hold no lock (since this time-consuming function needs
+ *     to be preemptible), and must check afterwards if item is still there.
+ */
+unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item)
+{
+       struct radix_tree_node *node;
+       unsigned long max_index;
+       unsigned long cur_index = 0;
+       unsigned long found_index = -1;
+
+       do {
+               rcu_read_lock();
+               node = rcu_dereference_raw(root->rnode);
+               if (!radix_tree_is_indirect_ptr(node)) {
+                       rcu_read_unlock();
+                       if (node == item)
+                               found_index = 0;
+                       break;
+               }
+
+               node = indirect_to_ptr(node);
+               max_index = radix_tree_maxindex(node->height);
+               if (cur_index > max_index)
+                       break;
+
+               cur_index = __locate(node, item, cur_index, &found_index);
+               rcu_read_unlock();
+               cond_resched();
+       } while (cur_index != 0 && cur_index <= max_index);
+
+       return found_index;
+}
+#else
+unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item)
+{
+       return -1;
+}
+#endif /* CONFIG_SHMEM && CONFIG_SWAP */
 
 /**
  *     radix_tree_shrink    -    shrink height of a radix tree to minimal
@@ -1062,10 +1300,10 @@ 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;
+               struct radix_tree_node *slot;
 
                BUG_ON(!radix_tree_is_indirect_ptr(to_free));
-               to_free = radix_tree_indirect_to_ptr(to_free);
+               to_free = indirect_to_ptr(to_free);
 
                /*
                 * The candidate node has more than one child, or its child
@@ -1078,16 +1316,41 @@ static inline void radix_tree_shrink(struct radix_tree_root *root)
 
                /*
                 * 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
+                * 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).
+                * one (root->rnode) as far as dependent read barriers go.
                 */
-               newptr = to_free->slots[0];
-               if (root->height > 1)
-                       newptr = radix_tree_ptr_to_indirect(newptr);
-               root->rnode = newptr;
+               slot = to_free->slots[0];
+               if (root->height > 1) {
+                       slot->parent = NULL;
+                       slot = ptr_to_indirect(slot);
+               }
+               root->rnode = slot;
                root->height--;
+
+               /*
+                * We have a dilemma here. The node's slot[0] must not be
+                * NULLed in case there are concurrent lookups expecting to
+                * find the item. However if this was a bottom-level node,
+                * then it may be subject to the slot pointer being visible
+                * to callers dereferencing it. If item corresponding to
+                * slot[0] is subsequently deleted, these callers would expect
+                * their slot to become empty sooner or later.
+                *
+                * For example, lockless pagecache will look up a slot, deref
+                * the page pointer, and if the page is 0 refcount it means it
+                * was concurrently deleted from pagecache so try the deref
+                * again. Fortunately there is already a requirement for logic
+                * to retry the entire slot lookup -- the indirect pointer
+                * problem (replacing direct root node with an indirect pointer
+                * also results in a stale slot). So tag the slot as indirect
+                * to force callers to retry.
+                */
+               if (root->height == 0)
+                       *((unsigned long *)&to_free->slots[0]) |=
+                                               RADIX_TREE_INDIRECT_PTR;
+
                radix_tree_node_free(to_free);
        }
 }
@@ -1103,16 +1366,12 @@ static inline void radix_tree_shrink(struct radix_tree_root *root)
  */
 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_node *node = NULL;
        struct radix_tree_node *slot = NULL;
        struct radix_tree_node *to_free;
        unsigned int height, shift;
        int tag;
-       int offset;
+       int uninitialized_var(offset);
 
        height = root->height;
        if (index > radix_tree_maxindex(height))
@@ -1124,40 +1383,36 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
                root->rnode = NULL;
                goto out;
        }
-       slot = radix_tree_indirect_to_ptr(slot);
-
-       shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
-       pathp->node = NULL;
+       slot = indirect_to_ptr(slot);
+       shift = height * RADIX_TREE_MAP_SHIFT;
 
        do {
                if (slot == NULL)
                        goto out;
 
-               pathp++;
+               shift -= RADIX_TREE_MAP_SHIFT;
                offset = (index >> shift) & RADIX_TREE_MAP_MASK;
-               pathp->offset = offset;
-               pathp->node = slot;
+               node = slot;
                slot = slot->slots[offset];
-               shift -= RADIX_TREE_MAP_SHIFT;
-               height--;
-       } while (height > 0);
+       } while (shift);
 
        if (slot == NULL)
                goto out;
 
        /*
-        * Clear all tags associated with the just-deleted item
+        * Clear all tags associated with the item to be deleted.
+        * This way of doing it would be inefficient, but seldom is any set.
         */
        for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
-               if (tag_get(pathp->node, tag, pathp->offset))
+               if (tag_get(node, tag, offset))
                        radix_tree_tag_clear(root, index, tag);
        }
 
        to_free = NULL;
        /* Now free the nodes we do not need anymore */
-       while (pathp->node) {
-               pathp->node->slots[pathp->offset] = NULL;
-               pathp->node->count--;
+       while (node) {
+               node->slots[offset] = NULL;
+               node->count--;
                /*
                 * Queue the node for deferred freeing after the
                 * last reference to it disappears (set NULL, above).
@@ -1165,18 +1420,20 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
                if (to_free)
                        radix_tree_node_free(to_free);
 
-               if (pathp->node->count) {
-                       if (pathp->node ==
-                                       radix_tree_indirect_to_ptr(root->rnode))
+               if (node->count) {
+                       if (node == indirect_to_ptr(root->rnode))
                                radix_tree_shrink(root);
                        goto out;
                }
 
                /* Node with zero slots in use so free it */
-               to_free = pathp->node;
-               pathp--;
+               to_free = node;
 
+               index >>= RADIX_TREE_MAP_SHIFT;
+               offset = index & RADIX_TREE_MAP_MASK;
+               node = node->parent;
        }
+
        root_tag_clear_all(root);
        root->height = 0;
        root->rnode = NULL;