radix-tree: fix radix_tree_dump() for multi-order entries

 - Print which indices are covered by every leaf entry
 - Print sibling entries
 - Print the node pointer instead of the slot entry
 - Build by default in userspace, and make it accessible to the test-suite

Signed-off-by: Ross Zwisler <ross.zwisler@linux.intel.com>
Signed-off-by: Matthew Wilcox <willy@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, 29 insertions, 19 deletions

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 8df0df2835b4..a1a44f94c171 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -215,27 +215,36 @@ radix_tree_find_next_bit(const unsigned long *addr,
         return size;
 }
 
-#if 0
-static void dump_node(void *slot, int height, int offset)
+#ifndef __KERNEL__
+static void dump_node(struct radix_tree_node *node, unsigned offset,
+                                unsigned shift, unsigned long index)
 {
-        struct radix_tree_node *node;
-        int i;
-
-        if (!slot)
-                return;
-
-        if (height == 0) {
-                pr_debug("radix entry %p offset %d\n", slot, offset);
-                return;
-        }
+        unsigned long i;
 
-        node = indirect_to_ptr(slot);
         pr_debug("radix node: %p offset %d tags %lx %lx %lx path %x count %d parent %p\n",
-                slot, offset, node->tags[0][0], node->tags[1][0],
-                node->tags[2][0], node->path, node->count, node->parent);
-
-        for (i = 0; i < RADIX_TREE_MAP_SIZE; i++)
-                dump_node(node->slots[i], height - 1, i);
+                node, offset,
+                node->tags[0][0], node->tags[1][0], node->tags[2][0],
+                node->path, node->count, node->parent);
+
+        for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
+                unsigned long first = index | (i << shift);
+                unsigned long last = first | ((1UL << shift) - 1);
+                void *entry = node->slots[i];
+                if (!entry)
+                        continue;
+                if (is_sibling_entry(node, entry)) {
+                        pr_debug("radix sblng %p offset %ld val %p indices %ld-%ld\n",
+                                        entry, i,
+                                        *(void **)indirect_to_ptr(entry),
+                                        first, last);
+                } else if (!radix_tree_is_indirect_ptr(entry)) {
+                        pr_debug("radix entry %p offset %ld indices %ld-%ld\n",
+                                        entry, i, first, last);
+                } else {
+                        dump_node(indirect_to_ptr(entry), i,
+                                        shift - RADIX_TREE_MAP_SHIFT, first);
+                }
+        }
 }
 
 /* For debug */
@@ -246,7 +255,8 @@ static void radix_tree_dump(struct radix_tree_root *root)
                         root->gfp_mask >> __GFP_BITS_SHIFT);
         if (!radix_tree_is_indirect_ptr(root->rnode))
                 return;
-        dump_node(root->rnode, root->height, 0);
+        dump_node(indirect_to_ptr(root->rnode), 0,
+                                (root->height - 1) * RADIX_TREE_MAP_SHIFT, 0);
 }
 #endif