Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1349020

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

From Kieran Bingham <kieran.bingham@linaro.org>
Newsgroups linux.kernel
Subject [PATCHv3 11/13] scripts/gdb: Add a Radix Tree Parser
Date 2016-03-03 12:50 +0100
Message-ID <r8zVx-6xi-31@gated-at.bofh.it> (permalink)
References <r8zVv-6xi-3@gated-at.bofh.it>
Organization linux.* mail to news gateway

Show all headers | View raw

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@linaro.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@linaro.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

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[PATCHv3 00/13] scripts/gdb: Linux awareness debug commands Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-03 12:50 +0100
  [PATCHv3 11/13] scripts/gdb: Add a Radix Tree Parser Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-03 12:50 +0100
  [PATCHv3 02/13] scripts/gdb: Provide kernel list item generators Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-03 12:50 +0100
  [PATCHv3 05/13] scripts/gdb: Support !CONFIG_MODULES gracefully Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-03 12:50 +0100
  [PATCHv3 01/13] scripts/gdb: Provide linux constants Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-03 12:50 +0100
  [PATCHv3 04/13] scripts/gdb: Provide exception catching parser Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-03 12:50 +0100
  [PATCHv3 13/13] scripts/gdb: Add lx_thread_info_by_pid helper Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-03 12:50 +0100
  [PATCHv3 10/13] scripts/gdb: Add cpu iterators Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-03 12:50 +0100
  [PATCHv3 12/13] scripts/gdb: Add interrupts command Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-03 12:50 +0100
  [PATCHv3 06/13] scripts/gdb: Provide a dentry_name VFS path helper Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-03 12:50 +0100
  [PATCHv3 08/13] scripts/gdb: Add mount point list command Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-03 12:50 +0100
  [PATCHv3 03/13] scripts/gdb: Convert modules usage to lists functions Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-03 12:50 +0100

csiph-web