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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Thu,  3 Mar 2016 11:41:05 +0000
From:	Kieran Bingham <kieran.bingham@...aro.org>
To:	jan.kiszka@...mens.com, linux-kernel@...r.kernel.org
Cc:	lee.jones@...aro.org, peter.griffin@...aro.org,
	maxime.coquelin@...com, Kieran Bingham <kieran.bingham@...aro.org>
Subject: [PATCHv3 11/13] scripts/gdb: Add a Radix Tree Parser

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@...aro.org>
---
 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@...aro.org>
+#
+# 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