Add a function and a command to iterate over radix tree contents.
Duplicate the C implementation in Python, but drop support for tagging.
Signed-off-by: Ilya Leoshkevich <iii@xxxxxxxxxxxxx>
---
scripts/gdb/linux/radixtree.py | 139 +++++++++++++++++++++++++++++++--
1 file changed, 132 insertions(+), 7 deletions(-)
diff --git a/scripts/gdb/linux/radixtree.py b/scripts/gdb/linux/radixtree.py
index 074543ac763d..bc2954e45c32 100644
--- a/scripts/gdb/linux/radixtree.py
+++ b/scripts/gdb/linux/radixtree.py
@@ -30,13 +30,16 @@ def entry_to_node(node):
def node_maxindex(node):
return (constants.LX_RADIX_TREE_MAP_SIZE << node['shift']) - 1
-def lookup(root, index):
+def resolve_root(root):
+ if root.type == radix_tree_root_type.get_type():
+ return root
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))
+ return root.dereference()
+ raise gdb.GdbError("must be {} not {}"
+ .format(radix_tree_root_type.get_type(), root.type))
+def lookup(root, index):
+ root = resolve_root(root)
node = root['xa_head']
if node == 0:
return None
@@ -71,14 +74,120 @@ def lookup(root, index):
return node
-class LxRadixTree(gdb.Function):
+def descend(parent, index):
+ offset = (index >> int(parent["shift"])) & constants.LX_RADIX_TREE_MAP_MASK
+ return offset, parent["slots"][offset]
+
+def load_root(root):
+ node = root["xa_head"]
+ nodep = node
+
+ if is_internal_node(node):
+ node = entry_to_node(node)
+ maxindex = node_maxindex(node)
+ return int(node["shift"]) + constants.LX_RADIX_TREE_MAP_SHIFT, \
+ nodep, maxindex
+
+ return 0, nodep, 0
+
+class RadixTreeIter:
+ def __init__(self, start):
+ self.index = 0
+ self.next_index = start
+ self.node = None
+
+def xa_mk_internal(v):
+ return (v << 2) | 2
+
+LX_XA_RETRY_ENTRY = xa_mk_internal(256)
+LX_RADIX_TREE_RETRY = LX_XA_RETRY_ENTRY
+
+def next_chunk(root, iter):
+ mask = (1 << (utils.get_ulong_type().sizeof * 8)) - 1
+
+ index = iter.next_index
+ if index == 0 and iter.index != 0:
+ return None
+
+ restart = True
+ while restart:
+ restart = False
+
+ _, child, maxindex = load_root(root)
+ if index > maxindex:
+ return None
+ if not child:
+ return None
+
+ if not is_internal_node(child):
+ iter.index = index
+ iter.next_index = (maxindex + 1) & mask
+ iter.node = None
+ return root["xa_head"].address
+
+ while True:
+ node = entry_to_node(child)
+ offset, child = descend(node, index)
+
+ if not child:
+ while True:
+ offset += 1
+ if offset >= constants.LX_RADIX_TREE_MAP_SIZE:
+ break
+ slot = node["slots"][offset]
+ if slot:
+ break
+ index &= ~node_maxindex(node)
+ index = (index + (offset << int(node["shift"]))) & mask
+ if index == 0:
+ return None
+ if offset == constants.LX_RADIX_TREE_MAP_SIZE:
+ restart = True
+ break
+ child = node["slots"][offset]
+
+ if not child:
+ restart = True
+ break
+ if child == LX_XA_RETRY_ENTRY:
+ break
+ if not node["shift"] or not is_internal_node(child):
+ break
+
+ iter.index = (index & ~node_maxindex(node)) | offset
+ iter.next_index = ((index | node_maxindex(node)) + 1) & mask
+ iter.node = node
+
+ return node["slots"][offset].address
+
+def next_slot(slot, iter):
+ mask = (1 << (utils.get_ulong_type().sizeof * 8)) - 1
+ for _ in range(iter.next_index - iter.index - 1):
+ slot += 1
+ iter.index = (iter.index + 1) & mask
+ if slot.dereference():
+ return slot
+ return None
+
+def for_each_slot(root, start=0):
+ iter = RadixTreeIter(start)
+ slot = None
+ while True:
+ if not slot:
+ slot = next_chunk(root, iter)
+ if not slot:
+ break
+ yield iter.index, slot
+ slot = next_slot(slot, iter)
+
+class LxRadixTreeLookup(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")
+ super(LxRadixTreeLookup, self).__init__("lx_radix_tree_lookup")
def invoke(self, root, index=0):
result = lookup(root, index)
@@ -87,4 +196,20 @@ If index is omitted, the root node is dereference and returned."""
return result
+class LxRadixTree(gdb.Command):
+ """Show all values stored in a RadixTree."""
+
+ def __init__(self):
+ super(LxRadixTree, self).__init__("lx-radix-tree", gdb.COMMAND_DATA,
+ gdb.COMPLETE_NONE)
+
+ def invoke(self, argument, from_tty):
+ args = gdb.string_to_argv(argument)
+ if len(args) != 1:
+ raise gdb.GdbError("Usage: lx-radix-tree ROOT")
+ root = gdb.parse_and_eval(args[0])
+ for index, slot in for_each_slot(root):
+ gdb.write("[{}] = {}\n".format(index, slot.dereference()))
+
LxRadixTree()
+LxRadixTreeLookup()
--
2.50.0
