[PATCH v2 1/2] scripts/gdb: Fix radix tree lookup pointer handling

[Ting-Han Hou <ue081723@gmail.com>]

lookup() casts each slot to a pointer to a node pointer and then
dereferences it. Since the slot already contains an entry pointer,
this reads the entry's contents as another pointer instead of
returning the entry itself. Internal entries also keep their tag
bits when descending, so multi-level trees are read from the wrong
address and $lx_radix_tree_lookup() fails with a memory error.

Sibling, retry and zero entries carry the same internal tag but are
small integers rather than node pointers, so the tag alone must not
decide whether to descend. A page cache populated with large folios
has a sibling entry in every slot but the first of each folio.

Walk the tree the way xas_load() does: descend only through entries
that xa_is_node() would accept, follow sibling entries to the
canonical slot of a multi-index entry, and treat retry and zero
entries like empty slots since they hold no data. Remove the explicit
shift counter, as traversal now follows the entry type.

Fixes: b7235d6bb516 ("scripts/gdb: add a Radix Tree Parser")
Assisted-by: LLM
Signed-off-by: Ting-Han Hou <ue081723@gmail.com>
---
Changes in v2:
- Handle XArray sibling, retry and zero entries, which carry the
  internal tag but are not node pointers. v1 passed them to
  entry_to_node() and the next node['shift'] read raised a GDB
  MemoryError (reported by Sashiko). Added is_node(), is_sibling()
  and sibling_offset() helpers modelled on xa_is_node(),
  xa_is_sibling() and xa_to_sibling().
- Sent as patch 1/2 of a series with git send-email.

Tested with GDB 17.1 against standalone GCC-built C fixtures using the
xarray/xa_node field layout, with XA_CHUNK_SHIFT=4 and 6. These are
synthetic debugger fixtures, not a booted kernel or a kernel core dump.

The fixtures cover empty/direct roots, one- to three-level trees,
zero-filled payloads, value entries, absent/out-of-range indices,
struct/pointer roots, the GDB convenience function, and multi-index
entries with sibling entries both in a leaf node and at the root level
of a two-level tree, plus retry and zero entries. Before this patch 26
of the 38 checks fail for each chunk size (wrong value, missed slot or
MemoryError); the v1 patch fails the 7 sibling/retry/zero checks with
a MemoryError; with this patch all 38 pass for both chunk sizes.

The lx-radix-tree iterator in the same file has not been changed.

 scripts/gdb/linux/radixtree.py | 66 ++++++++++++++++++++--------------
 1 file changed, 40 insertions(+), 26 deletions(-)

diff --git a/scripts/gdb/linux/radixtree.py b/scripts/gdb/linux/radixtree.py
index bc2954e45c32..8ce9936dfa50 100644
--- a/scripts/gdb/linux/radixtree.py
+++ b/scripts/gdb/linux/radixtree.py
@@ -27,6 +27,24 @@ def entry_to_node(node):
     indirect_ptr = node.cast(long_type) & ~constants.LX_RADIX_TREE_INTERNAL_NODE
     return indirect_ptr.cast(radix_tree_node_type.get_type().pointer())
 
+def is_node(entry):
+    # Like xa_is_node(): internal entries below 4096 are sibling, retry
+    # or zero entries rather than pointers to a struct xa_node.
+    ulong_type = utils.get_ulong_type()
+    return is_internal_node(entry) and entry.cast(ulong_type) > 4096
+
+def is_sibling(entry):
+    # Like xa_is_sibling(): a multi-index entry occupies several slots,
+    # and all but the first hold a sibling entry that encodes the offset
+    # of the first one.
+    ulong_type = utils.get_ulong_type()
+    return is_internal_node(entry) and entry.cast(ulong_type) < \
+        xa_mk_internal(constants.LX_RADIX_TREE_MAP_SIZE - 1)
+
+def sibling_offset(entry):
+    ulong_type = utils.get_ulong_type()
+    return int(entry.cast(ulong_type)) >> 2
+
 def node_maxindex(node):
     return (constants.LX_RADIX_TREE_MAP_SIZE << node['shift']) - 1
 
@@ -40,39 +58,35 @@ def resolve_root(root):
 
 def lookup(root, index):
     root = resolve_root(root)
-    node = root['xa_head']
-    if node == 0:
-        return None
+    entry = root['xa_head']
 
-    if not (is_internal_node(node)):
-        if (index > 0):
+    if is_node(entry):
+        node = entry_to_node(entry)
+        if index > node_maxindex(node):
             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]
+        # Walk down the tree like xas_load() does.
+        while True:
+            offset = (index >> node['shift']) & constants.LX_RADIX_TREE_MAP_MASK
+            entry = node['slots'][offset]
 
-        if slot == 0:
-            return None
+            while is_sibling(entry):
+                entry = node['slots'][sibling_offset(entry)]
+                if node['shift'] and is_node(entry):
+                    # xas_descend() turns this into a retry entry.
+                    return None
 
-        node = slot.cast(node.type.pointer()).dereference()
-        if node == 0:
-            return None
+            if not is_node(entry) or node['shift'] == 0:
+                break
+            node = entry_to_node(entry)
+    elif index > 0:
+        return None
 
-        shift -= constants.LX_RADIX_TREE_MAP_SHIFT
-        if (shift <= 0):
-            break
+    # Empty slots and retry or zero entries hold no data.
+    if entry == 0 or is_internal_node(entry):
+        return None
 
-    return node
+    return entry
 
 def descend(parent, index):
     offset = (index >> int(parent["shift"])) & constants.LX_RADIX_TREE_MAP_MASK
-- 
2.53.0