[PATCHv3 11/13] scripts/gdb: Add a Radix Tree Parser

[Kieran Bingham]

Linux makes use of the Radix Tree data structure to store pointers indexed
by integer values. This structure is utilised across many structures in
the kernel including the IRQ descriptor tables, and several filesystems.

This module provides a method to lookup values from a structure given
its head node.

Signed-off-by: Kieran Bingham <kieran.bingham@xxxxxxxxxx>
---
 scripts/gdb/linux/constants.py.in |  7 +++-
 scripts/gdb/linux/radixtree.py    | 74 +++++++++++++++++++++++++++++++++++++++
 scripts/gdb/vmlinux-gdb.py        |  1 +
 3 files changed, 81 insertions(+), 1 deletion(-)
 create mode 100644 scripts/gdb/linux/radixtree.py

diff --git a/scripts/gdb/linux/constants.py.in b/scripts/gdb/linux/constants.py.in
index 66562a8242bd..b38b9085c702 100644
--- a/scripts/gdb/linux/constants.py.in
+++ b/scripts/gdb/linux/constants.py.in
@@ -21,7 +21,7 @@
 #include <linux/mount.h>
 #include <linux/huge_mm.h>
 #include <linux/vmalloc.h>
-
+#include <linux/radix-tree.h>
 
 /* We need to stringify expanded macros so that they can be parsed */
 
@@ -71,6 +71,11 @@ LX_GDBPARSED(VMALLOC_TOTAL)
 /* linux/swap.h */
 LX_GDBPARSED(MAX_SWAPFILES)
 
+/* linux/radix-tree.h */
+LX_VALUE(RADIX_TREE_INDIRECT_PTR)
+LX_GDBPARSED(RADIX_TREE_HEIGHT_MASK)
+LX_GDBPARSED(RADIX_TREE_MAP_SHIFT)
+LX_GDBPARSED(RADIX_TREE_MAP_MASK)
 
 /* Kernel Configs */
 LX_CONFIG(CONFIG_HIGHMEM)
diff --git a/scripts/gdb/linux/radixtree.py b/scripts/gdb/linux/radixtree.py
new file mode 100644
index 000000000000..299d171e3571
--- /dev/null
+++ b/scripts/gdb/linux/radixtree.py
@@ -0,0 +1,74 @@
+#
+# gdb helper commands and functions for Linux kernel debugging
+#
+#  Radix Tree Parser
+#
+# Copyright (c) 2016 Linaro Ltd
+#
+# Authors:
+#  Kieran Bingham <kieran.bingham@xxxxxxxxxx>
+#
+# This work is licensed under the terms of the GNU GPL version 2.
+#
+
+import gdb
+
+from linux import utils
+from linux import constants
+
+radix_tree_root_type = utils.CachedType("struct radix_tree_root")
+radix_tree_node_type = utils.CachedType("struct radix_tree_node")
+
+
+def is_indirect_ptr(node):
+    long_type = utils.get_long_type()
+    return (node.cast(long_type) & constants.LX_RADIX_TREE_INDIRECT_PTR)
+
+
+def indirect_to_ptr(node):
+    long_type = utils.get_long_type()
+    node_type = node.type
+    indirect_ptr = node.cast(long_type) & ~constants.LX_RADIX_TREE_INDIRECT_PTR
+    return indirect_ptr.cast(node_type)
+
+
+def maxindex(height):
+    height = height & constants.LX_RADIX_TREE_HEIGHT_MASK
+    return gdb.parse_and_eval("height_to_maxindex["+str(height)+"]")
+
+
+def lookup(root, index):
+    node = root['rnode']
+    if node is 0:
+        return None
+
+    if not (is_indirect_ptr(node)):
+        if (index > 0):
+            return None
+        return node
+
+    node = indirect_to_ptr(node)
+
+    height = node['path'] & constants.LX_RADIX_TREE_HEIGHT_MASK
+    if (index > maxindex(height)):
+        return None
+
+    shift = (height-1) * constants.LX_RADIX_TREE_MAP_SHIFT
+
+    while True:
+        new_index = (index >> shift) & constants.LX_RADIX_TREE_MAP_MASK
+        slot = node['slots'][new_index]
+
+        # Below needs a bit more verification ...
+        # node = rcu_dereference_raw(*slot);
+        node = slot.cast(node.type.pointer()).dereference()
+        if node is 0:
+            return None
+
+        shift -= constants.LX_RADIX_TREE_MAP_SHIFT
+        height -= 1
+
+        if (height <= 0):
+            break
+
+    return node
diff --git a/scripts/gdb/vmlinux-gdb.py b/scripts/gdb/vmlinux-gdb.py
index 6e0b0afd888a..3a80ad6eecad 100644
--- a/scripts/gdb/vmlinux-gdb.py
+++ b/scripts/gdb/vmlinux-gdb.py
@@ -31,3 +31,4 @@ else:
     import linux.lists
     import linux.proc
     import linux.constants
+    import linux.radixtree
-- 
2.5.0