radix-tree: rewrite __radix_tree_lookup

Use the new multi-order support functions to rewrite __radix_tree_lookup()

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross Zwisler <ross.zwisler@linux.intel.com>
Cc: Konstantin Khlebnikov <koct9i@gmail.com>
Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com>
Cc: Jan Kara <jack@suse.com>
Cc: Neil Brown <neilb@suse.de>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

1 files changed, 16 insertions, 32 deletions

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index a1ba41730071..f14ada9830ca 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -634,44 +634,28 @@ void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index,
                           struct radix_tree_node **nodep, void ***slotp)
 {
         struct radix_tree_node *node, *parent;
-        unsigned int height, shift;
+        unsigned long maxindex;
+        unsigned int shift;
         void **slot;
 
-        node = rcu_dereference_raw(root->rnode);
-        if (node == NULL)
-                return NULL;
-
-        if (!radix_tree_is_indirect_ptr(node)) {
-                if (index > 0)
-                        return NULL;
-
-                if (nodep)
-                        *nodep = NULL;
-                if (slotp)
-                        *slotp = (void **)&root->rnode;
-                return node;
-        }
-        node = indirect_to_ptr(node);
-
-        height = node->path & RADIX_TREE_HEIGHT_MASK;
-        if (index > radix_tree_maxindex(height))
+ restart:
+        parent = NULL;
+        slot = (void **)&root->rnode;
+        shift = radix_tree_load_root(root, &node, &maxindex);
+        if (index > maxindex)
                 return NULL;
 
-        shift = (height-1) * RADIX_TREE_MAP_SHIFT;
-
-        do {
-                parent = node;
-                slot = node->slots + ((index >> shift) & RADIX_TREE_MAP_MASK);
-                node = rcu_dereference_raw(*slot);
-                if (node == NULL)
-                        return NULL;
-                if (!radix_tree_is_indirect_ptr(node))
-                        break;
-                node = indirect_to_ptr(node);
+        while (radix_tree_is_indirect_ptr(node)) {
+                unsigned offset;
 
+                if (node == RADIX_TREE_RETRY)
+                        goto restart;
+                parent = indirect_to_ptr(node);
                 shift -= RADIX_TREE_MAP_SHIFT;
-                height--;
-        } while (height > 0);
+                offset = (index >> shift) & RADIX_TREE_MAP_MASK;
+                offset = radix_tree_descend(parent, &node, offset);
+                slot = parent->slots + offset;
+        }
 
         if (nodep)
                 *nodep = parent;