[PATCH] scripts/gdb: add a Radix Tree Parser

[PATCH] scripts/gdb: add a Radix Tree Parser

[Florian Fainelli]

From: Kieran Bingham <kieran.bingham@linaro.org>

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)

This script previously existed under commit
e127a73d41ac471d7e3ba950cf128f42d6ee3448 ("scripts/gdb: add a Radix Tree
Parser") and was later reverted with
b447e02548a3304c47b78b5e2d75a4312a8f17e1i (Revert "scripts/gdb: add a
Radix Tree Parser").

This version expects the XArray based radix tree implementation and has
been verified using QEMU/x86 on Linux 6.3-rc5.

Signed-off-by: Kieran Bingham <kieran.bingham@linaro.org>
[florian: revive and update for xarray implementation]
Signed-off-by: Florian Fainelli <f.fainelli@gmail.com>
---
 scripts/gdb/linux/constants.py.in |  8 +++
 scripts/gdb/linux/radixtree.py    | 87 +++++++++++++++++++++++++++++++
 scripts/gdb/vmlinux-gdb.py        |  1 +
 3 files changed, 96 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 2efbec6b6b8d..6c886deb0b18 100644
--- a/scripts/gdb/linux/constants.py.in
+++ b/scripts/gdb/linux/constants.py.in
@@ -17,6 +17,7 @@
 #include <linux/hrtimer.h>
 #include <linux/mount.h>
 #include <linux/of_fdt.h>
+#include <linux/radix-tree.h>
 #include <linux/threads.h>
 
 /* We need to stringify expanded macros so that they can be parsed */
@@ -68,6 +69,13 @@ LX_VALUE(NR_CPUS)
 /* linux/of_fdt.h> */
 LX_VALUE(OF_DT_HEADER)
 
+/* linux/radix-tree.h */
+LX_GDBPARSED(RADIX_TREE_ENTRY_MASK)
+LX_GDBPARSED(RADIX_TREE_INTERNAL_NODE)
+LX_GDBPARSED(RADIX_TREE_MAP_SIZE)
+LX_GDBPARSED(RADIX_TREE_MAP_SHIFT)
+LX_GDBPARSED(RADIX_TREE_MAP_MASK)
+
 /* Kernel Configs */
 LX_CONFIG(CONFIG_GENERIC_CLOCKEVENTS)
 LX_CONFIG(CONFIG_GENERIC_CLOCKEVENTS_BROADCAST)
diff --git a/scripts/gdb/linux/radixtree.py b/scripts/gdb/linux/radixtree.py
new file mode 100644
index 000000000000..3ca2db7fbbac
--- /dev/null
+++ b/scripts/gdb/linux/radixtree.py
@@ -0,0 +1,87 @@
+# SPDX-License-Identifier: GPL-2.0
+#
+#  Radix Tree Parser
+#
+# Copyright (c) 2016 Linaro Ltd
+# Copyright (c) 2023 Broadcom
+#
+# Authors:
+#  Kieran Bingham <kieran.bingham@linaro.org>
+#  Florian Fainelli <f.fainelli@gmail.com>
+
+import gdb
+
+from linux import utils
+from linux import constants
+
+radix_tree_root_type = utils.CachedType("struct xarray")
+radix_tree_node_type = utils.CachedType("struct xa_node")
+
+def is_internal_node(node):
+    long_type = utils.get_long_type()
+    return ((node.cast(long_type) & constants.LX_RADIX_TREE_ENTRY_MASK) == constants.LX_RADIX_TREE_INTERNAL_NODE)
+
+def entry_to_node(node):
+    long_type = utils.get_long_type()
+    node_type = node.type
+    indirect_ptr = node.cast(long_type) & ~constants.LX_RADIX_TREE_INTERNAL_NODE
+    return indirect_ptr.cast(radix_tree_node_type.get_type().pointer())
+
+def node_maxindex(node):
+    return (constants.LX_RADIX_TREE_MAP_SIZE << node['shift']) - 1
+
+def lookup(root, index):
+    if root.type == radix_tree_root_type.get_type().pointer():
+        node = root.dereference()
+    elif root.type != radix_tree_root_type.get_type():
+        raise gdb.GdbError("must be {} not {}"
+                           .format(radix_tree_root_type.get_type(), root.type))
+
+    node = root['xa_head']
+    if node == 0:
+        return None
+
+    if not (is_internal_node(node)):
+        if (index > 0):
+            return None
+        return node
+
+    node = entry_to_node(node)
+    maxindex = node_maxindex(node)
+
+    if (index > maxindex):
+        return None
+
+    shift = node['shift'] + constants.LX_RADIX_TREE_MAP_SHIFT
+
+    while True:
+        offset = (index >> node['shift']) & constants.LX_RADIX_TREE_MAP_MASK
+        slot = node['slots'][offset]
+
+        node = slot.cast(node.type.pointer()).dereference()
+        if node == 0:
+            return None
+
+        shift -= constants.LX_RADIX_TREE_MAP_SHIFT
+        if (shift <= 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 dereference 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 3a5b44cd6bfe..4a5056f2c247 100644
--- a/scripts/gdb/vmlinux-gdb.py
+++ b/scripts/gdb/vmlinux-gdb.py
@@ -38,3 +38,4 @@ else:
     import linux.genpd
     import linux.device
     import linux.mm
+    import linux.radixtree
-- 
2.34.1

Re: [PATCH] scripts/gdb: add a Radix Tree Parser

[Florian Fainelli]

On 4/4/23 14:40, Florian Fainelli wrote:
[snip]
> +    shift = node['shift'] + constants.LX_RADIX_TREE_MAP_SHIFT
> +
> +    while True:
> +        offset = (index >> node['shift']) & constants.LX_RADIX_TREE_MAP_MASK
> +        slot = node['slots'][offset]

We need to check for slot == 0 here, unless there are other comments, I 
will spin a v2 with that change.
-- 
Florian