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

Groups > linux.kernel > #1367142

[PATCHv4 10/12] scripts/gdb: Add a Radix Tree Parser

From Kieran Bingham <kieran.bingham@linaro.org>
Newsgroups linux.kernel
Subject [PATCHv4 10/12] scripts/gdb: Add a Radix Tree Parser
Date 2016-03-30 14:10 +0200
Message-ID <rin6G-57W-5@gated-at.bofh.it> (permalink)
References <rin6G-57W-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.

Usage:

The function lx_radix_tree_lookup, must be given a symbol of type
struct radix_tree_root, and an index into that tree.

The object returned is a generic integer value, and must be cast
correctly to the type based on the storage in the data structure.

For example, to print the irq descriptor in the sparse irq_desc_tree at
index 18, try the following:

 (gdb) print (struct irq_desc)$lx_radix_tree_lookup(irq_desc_tree, 18)

Signed-off-by: Kieran Bingham <kieran.bingham@linaro.org>

---
Changes since v3:
 - Added a lookup function helper
 - Provide type checking on lookup()
 - Remove outdated comment regarding RCU dereference
---
 scripts/gdb/linux/constants.py.in |  6 +++
 scripts/gdb/linux/radixtree.py    | 97 +++++++++++++++++++++++++++++++++++++++
 scripts/gdb/vmlinux-gdb.py        |  1 +
 3 files changed, 104 insertions(+)
 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 57213ad8cf75..07e6c2befe36 100644
--- a/scripts/gdb/linux/constants.py.in
+++ b/scripts/gdb/linux/constants.py.in
@@ -14,6 +14,7 @@
 
 #include <linux/fs.h>
 #include <linux/mount.h>
+#include <linux/radix-tree.h>
 
 /* We need to stringify expanded macros so that they can be parsed */
 
@@ -51,3 +52,8 @@ LX_VALUE(MNT_NOATIME)
 LX_VALUE(MNT_NODIRATIME)
 LX_VALUE(MNT_RELATIME)
 
+/* 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)
diff --git a/scripts/gdb/linux/radixtree.py b/scripts/gdb/linux/radixtree.py
new file mode 100644
index 000000000000..0fdef4e2971a
--- /dev/null
+++ b/scripts/gdb/linux/radixtree.py
@@ -0,0 +1,97 @@
+#
+# 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):
+    if root.type == radix_tree_root_type.get_type().pointer():
+        root = root.dereference()
+    elif root.type != radix_tree_root_type.get_type():
+        raise gdb.GdbError("Must be struct radix_tree_root not {}"
+                           .format(root.type))
+
+    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]
+
+        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
+
+
+class LxRadixTree(gdb.Function):
+    """ Lookup and return a node from a RadixTree.
+
+$lx_radix_tree_lookup(root_node [, index]): Return the node at the given index.
+If index is omitted, the root node is dereferenced and returned."""
+
+    def __init__(self):
+        super(LxRadixTree, self).__init__("lx_radix_tree_lookup")
+
+    def invoke(self, root, index=0):
+        result = lookup(root, index)
+        if result is None:
+            raise gdb.GdbError("No entry in tree at index {}".format(index))
+
+        return result
+
+LxRadixTree()
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

[PATCHv4 00/12] gdb/scripts: Linux awareness debug commands Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-30 14:10 +0200
  [PATCHv4 10/12] scripts/gdb: Add a Radix Tree Parser Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-30 14:10 +0200
  [PATCHv4 12/12] scripts/gdb: Add lx_thread_info_by_pid helper Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-30 14:10 +0200
  [PATCHv4 05/12] scripts/gdb: Support !CONFIG_MODULES gracefully Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-30 14:10 +0200
  [PATCHv4 09/12] scripts/gdb: Add cpu iterators Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-30 14:10 +0200
  [PATCHv4 01/12] scripts/gdb: Provide linux constants Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-30 14:10 +0200
    Re: [PATCHv4 01/12] scripts/gdb: Provide linux constants Jan Kiszka <jan.kiszka@siemens.com> - 2016-03-30 23:10 +0200
  [PATCHv4 06/12] scripts/gdb: Provide a dentry_name VFS path helper Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-30 14:10 +0200
  [PATCHv4 02/12] scripts/gdb: Provide kernel list item generators Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-30 14:10 +0200
  [PATCHv4 07/12] scripts/gdb: Add io resource readers Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-30 14:10 +0200
  [PATCHv4 08/12] scripts/gdb: Add mount point list command Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-30 14:10 +0200
  [PATCHv4 11/12] scripts/gdb: Add documentation example for radix tree Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-30 14:10 +0200
  [PATCHv4 04/12] scripts/gdb: Provide exception catching parser Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-30 14:10 +0200
  [PATCHv4 03/12] scripts/gdb: Convert modules usage to lists functions Kieran Bingham <kieran.bingham@linaro.org> - 2016-03-30 14:10 +0200

csiph-web