1 files changed, 22 insertions, 14 deletions

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index d60be40c111b..9599aa72d7a0 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -342,7 +342,8 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
 
                 /* Increase the height.  */
                 newheight = root->height+1;
-                node->height = newheight;
+                BUG_ON(newheight & ~RADIX_TREE_HEIGHT_MASK);
+                node->path = newheight;
                 node->count = 1;
                 node->parent = NULL;
                 slot = root->rnode;
@@ -400,11 +401,12 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
                         /* Have to add a child node.  */
                         if (!(slot = radix_tree_node_alloc(root)))
                                 return -ENOMEM;
-                        slot->height = height;
+                        slot->path = height;
                         slot->parent = node;
                         if (node) {
                                 rcu_assign_pointer(node->slots[offset], slot);
                                 node->count++;
+                                slot->path |= offset << RADIX_TREE_HEIGHT_SHIFT;
                         } else
                                 rcu_assign_pointer(root->rnode, ptr_to_indirect(slot));
                 }
@@ -498,7 +500,7 @@ void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index,
         }
         node = indirect_to_ptr(node);
 
-        height = node->height;
+        height = node->path & RADIX_TREE_HEIGHT_MASK;
         if (index > radix_tree_maxindex(height))
                 return NULL;
 
@@ -704,7 +706,7 @@ int radix_tree_tag_get(struct radix_tree_root *root,
                 return (index == 0);
         node = indirect_to_ptr(node);
 
-        height = node->height;
+        height = node->path & RADIX_TREE_HEIGHT_MASK;
         if (index > radix_tree_maxindex(height))
                 return 0;
 
@@ -741,7 +743,7 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
 {
         unsigned shift, tag = flags & RADIX_TREE_ITER_TAG_MASK;
         struct radix_tree_node *rnode, *node;
-        unsigned long index, offset;
+        unsigned long index, offset, height;
 
         if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag))
                 return NULL;
@@ -772,7 +774,8 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
                 return NULL;
 
 restart:
-        shift = (rnode->height - 1) * RADIX_TREE_MAP_SHIFT;
+        height = rnode->path & RADIX_TREE_HEIGHT_MASK;
+        shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
         offset = index >> shift;
 
         /* Index outside of the tree */
@@ -1142,7 +1145,7 @@ static unsigned long __locate(struct radix_tree_node *slot, void *item,
         unsigned int shift, height;
         unsigned long i;
 
-        height = slot->height;
+        height = slot->path & RADIX_TREE_HEIGHT_MASK;
         shift = (height-1) * RADIX_TREE_MAP_SHIFT;
 
         for ( ; height > 1; height--) {
@@ -1205,7 +1208,8 @@ unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item)
                 }
 
                 node = indirect_to_ptr(node);
-                max_index = radix_tree_maxindex(node->height);
+                max_index = radix_tree_maxindex(node->path &
+                                                RADIX_TREE_HEIGHT_MASK);
                 if (cur_index > max_index) {
                         rcu_read_unlock();
                         break;
@@ -1301,7 +1305,7 @@ static inline void radix_tree_shrink(struct radix_tree_root *root)
  *
  *      Returns %true if @node was freed, %false otherwise.
  */
-bool __radix_tree_delete_node(struct radix_tree_root *root, unsigned long index,
+bool __radix_tree_delete_node(struct radix_tree_root *root,
                               struct radix_tree_node *node)
 {
         bool deleted = false;
@@ -1320,9 +1324,10 @@ bool __radix_tree_delete_node(struct radix_tree_root *root, unsigned long index,
 
                 parent = node->parent;
                 if (parent) {
-                        index >>= RADIX_TREE_MAP_SHIFT;
+                        unsigned int offset;
 
-                        parent->slots[index & RADIX_TREE_MAP_MASK] = NULL;
+                        offset = node->path >> RADIX_TREE_HEIGHT_SHIFT;
+                        parent->slots[offset] = NULL;
                         parent->count--;
                 } else {
                         root_tag_clear_all(root);
@@ -1386,7 +1391,7 @@ void *radix_tree_delete_item(struct radix_tree_root *root,
         node->slots[offset] = NULL;
         node->count--;
 
-        __radix_tree_delete_node(root, index, node);
+        __radix_tree_delete_node(root, node);
 
         return entry;
 }
@@ -1419,9 +1424,12 @@ int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag)
 EXPORT_SYMBOL(radix_tree_tagged);
 
 static void
-radix_tree_node_ctor(void *node)
+radix_tree_node_ctor(void *arg)
 {
-        memset(node, 0, sizeof(struct radix_tree_node));
+        struct radix_tree_node *node = arg;
+
+        memset(node, 0, sizeof(*node));
+        INIT_LIST_HEAD(&node->private_list);
 }
 
 static __init unsigned long __maxindex(unsigned int height)