radix-tree: fix extending the tree for multi-order entries at offset 0

[karo-tx-linux.git] / lib / radix-tree.c

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 1624c41179614321728bcdd878c7fb4153a91748..f13ddbba8ace72fe515985f0265529619ab940b3 100644 (file)
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -80,6 +80,46 @@ static inline void *indirect_to_ptr(void *ptr)
        return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR);
 }
 
+#ifdef CONFIG_RADIX_TREE_MULTIORDER
+/* Sibling slots point directly to another slot in the same node */
+static inline bool is_sibling_entry(struct radix_tree_node *parent, void *node)
+{
+       void **ptr = node;
+       return (parent->slots <= ptr) &&
+                       (ptr < parent->slots + RADIX_TREE_MAP_SIZE);
+}
+#else
+static inline bool is_sibling_entry(struct radix_tree_node *parent, void *node)
+{
+       return false;
+}
+#endif
+
+static inline unsigned long get_slot_offset(struct radix_tree_node *parent,
+                                                void **slot)
+{
+       return slot - parent->slots;
+}
+
+static unsigned radix_tree_descend(struct radix_tree_node *parent,
+                               struct radix_tree_node **nodep, unsigned offset)
+{
+       void **entry = rcu_dereference_raw(parent->slots[offset]);
+
+#ifdef CONFIG_RADIX_TREE_MULTIORDER
+       if (radix_tree_is_indirect_ptr(entry)) {
+               unsigned long siboff = get_slot_offset(parent, entry);
+               if (siboff < RADIX_TREE_MAP_SIZE) {
+                       offset = siboff;
+                       entry = rcu_dereference_raw(parent->slots[offset]);
+               }
+       }
+#endif
+
+       *nodep = (void *)entry;
+       return offset;
+}
+
 static inline gfp_t root_gfp_mask(struct radix_tree_root *root)
 {
        return root->gfp_mask & __GFP_BITS_MASK;
@@ -365,11 +405,34 @@ static inline unsigned long radix_tree_maxindex(unsigned int height)
        return height_to_maxindex[height];
 }
 
+static inline unsigned long node_maxindex(struct radix_tree_node *node)
+{
+       return radix_tree_maxindex(node->path & RADIX_TREE_HEIGHT_MASK);
+}
+
+static unsigned radix_tree_load_root(struct radix_tree_root *root,
+               struct radix_tree_node **nodep, unsigned long *maxindex)
+{
+       struct radix_tree_node *node = rcu_dereference_raw(root->rnode);
+
+       *nodep = node;
+
+       if (likely(radix_tree_is_indirect_ptr(node))) {
+               node = indirect_to_ptr(node);
+               *maxindex = node_maxindex(node);
+               return (node->path & RADIX_TREE_HEIGHT_MASK) *
+                       RADIX_TREE_MAP_SHIFT;
+       }
+
+       *maxindex = 0;
+       return 0;
+}
+
 /*
  *     Extend a radix tree so it can store key @index.
  */
 static int radix_tree_extend(struct radix_tree_root *root,
-                               unsigned long index, unsigned order)
+                               unsigned long index)
 {
        struct radix_tree_node *node;
        struct radix_tree_node *slot;
@@ -381,7 +444,7 @@ static int radix_tree_extend(struct radix_tree_root *root,
        while (index > radix_tree_maxindex(height))
                height++;
 
-       if ((root->rnode == NULL) && (order == 0)) {
+       if (root->rnode == NULL) {
                root->height = height;
                goto out;
        }
@@ -404,7 +467,7 @@ static int radix_tree_extend(struct radix_tree_root *root,
                node->count = 1;
                node->parent = NULL;
                slot = root->rnode;
-               if (radix_tree_is_indirect_ptr(slot) && newheight > 1) {
+               if (radix_tree_is_indirect_ptr(slot)) {
                        slot = indirect_to_ptr(slot);
                        slot->parent = node;
                        slot = ptr_to_indirect(slot);
@@ -415,7 +478,7 @@ static int radix_tree_extend(struct radix_tree_root *root,
                root->height = newheight;
        } while (height > root->height);
 out:
-       return 0;
+       return height * RADIX_TREE_MAP_SHIFT;
 }
 
 /**
@@ -440,22 +503,26 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
                        void ***slotp)
 {
        struct radix_tree_node *node = NULL, *slot;
+       unsigned long maxindex;
        unsigned int height, shift, offset;
-       int error;
+       unsigned long max = index | ((1UL << order) - 1);
 
-       BUG_ON((0 < order) && (order < RADIX_TREE_MAP_SHIFT));
+       shift = radix_tree_load_root(root, &slot, &maxindex);
 
        /* Make sure the tree is high enough.  */
-       if (index > radix_tree_maxindex(root->height)) {
-               error = radix_tree_extend(root, index, order);
-               if (error)
+       if (max > maxindex) {
+               int error = radix_tree_extend(root, max);
+               if (error < 0)
                        return error;
+               shift = error;
+               slot = root->rnode;
+               if (order == shift) {
+                       shift += RADIX_TREE_MAP_SHIFT;
+                       root->height++;
+               }
        }
 
-       slot = root->rnode;
-
        height = root->height;
-       shift = height * RADIX_TREE_MAP_SHIFT;
 
        offset = 0;                     /* uninitialised var warning */
        while (shift > order) {
@@ -484,9 +551,10 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
                slot = node->slots[offset];
        }
 
+#ifdef CONFIG_RADIX_TREE_MULTIORDER
        /* Insert pointers to the canonical entry */
-       if ((shift - order) > 0) {
-               int i, n = 1 << (shift - order);
+       if (order > shift) {
+               int i, n = 1 << (order - shift);
                offset = offset & ~(n - 1);
                slot = ptr_to_indirect(&node->slots[offset]);
                for (i = 0; i < n; i++) {
@@ -499,6 +567,7 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
                        node->count++;
                }
        }
+#endif
 
        if (nodep)
                *nodep = node;
@@ -1469,6 +1538,20 @@ bool __radix_tree_delete_node(struct radix_tree_root *root,
        return deleted;
 }
 
+static inline void delete_sibling_entries(struct radix_tree_node *node,
+                                       void *ptr, unsigned offset)
+{
+#ifdef CONFIG_RADIX_TREE_MULTIORDER
+       int i;
+       for (i = 1; offset + i < RADIX_TREE_MAP_SIZE; i++) {
+               if (node->slots[offset + i] != ptr)
+                       break;
+               node->slots[offset + i] = NULL;
+               node->count--;
+       }
+#endif
+}
+
 /**
  *     radix_tree_delete_item    -    delete an item from a radix tree
  *     @root:          radix tree root
@@ -1484,7 +1567,7 @@ void *radix_tree_delete_item(struct radix_tree_root *root,
                             unsigned long index, void *item)
 {
        struct radix_tree_node *node;
-       unsigned int offset, i;
+       unsigned int offset;
        void **slot;
        void *entry;
        int tag;
@@ -1502,7 +1585,7 @@ void *radix_tree_delete_item(struct radix_tree_root *root,
                return entry;
        }
 
-       offset = index & RADIX_TREE_MAP_MASK;
+       offset = get_slot_offset(node, slot);
 
        /*
         * Clear all tags associated with the item to be deleted.
@@ -1513,13 +1596,7 @@ void *radix_tree_delete_item(struct radix_tree_root *root,
                        radix_tree_tag_clear(root, index, tag);
        }
 
-       /* Delete any sibling slots pointing to this slot */
-       for (i = 1; offset + i < RADIX_TREE_MAP_SIZE; i++) {
-               if (node->slots[offset + i] != ptr_to_indirect(slot))
-                       break;
-               node->slots[offset + i] = NULL;
-               node->count--;
-       }
+       delete_sibling_entries(node, ptr_to_indirect(slot), offset);
        node->slots[offset] = NULL;
        node->count--;