diff options
Diffstat (limited to 'scripts/gdb/linux/radixtree.py')
| -rw-r--r-- | scripts/gdb/linux/radixtree.py | 215 |
1 files changed, 215 insertions, 0 deletions
diff --git a/scripts/gdb/linux/radixtree.py b/scripts/gdb/linux/radixtree.py new file mode 100644 index 000000000000..bc2954e45c32 --- /dev/null +++ b/scripts/gdb/linux/radixtree.py @@ -0,0 +1,215 @@ +# 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 resolve_root(root): + if root.type == radix_tree_root_type.get_type(): + return root + if root.type == radix_tree_root_type.get_type().pointer(): + 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 + + 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] + + if slot == 0: + return None + + 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 + +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(LxRadixTreeLookup, 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 + +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() |