1 # SPDX-License-Identifier: GPL-2.0
5 # Copyright (c) 2016 Linaro Ltd
6 # Copyright (c) 2023 Broadcom
14 from linux import utils
15 from linux import constants
17 radix_tree_root_type = utils.CachedType("struct xarray")
18 radix_tree_node_type = utils.CachedType("struct xa_node")
20 def is_internal_node(node):
21 long_type = utils.get_long_type()
22 return ((node.cast(long_type) & constants.LX_RADIX_TREE_ENTRY_MASK) == constants.LX_RADIX_TREE_INTERNAL_NODE)
24 def entry_to_node(node):
25 long_type = utils.get_long_type()
27 indirect_ptr = node.cast(long_type) & ~constants.LX_RADIX_TREE_INTERNAL_NODE
28 return indirect_ptr.cast(radix_tree_node_type.get_type().pointer())
30 def node_maxindex(node):
31 return (constants.LX_RADIX_TREE_MAP_SIZE << node['shift']) - 1
33 def lookup(root, index):
34 if root.type == radix_tree_root_type.get_type().pointer():
35 node = root.dereference()
36 elif root.type != radix_tree_root_type.get_type():
37 raise gdb.GdbError("must be {} not {}"
38 .format(radix_tree_root_type.get_type(), root.type))
40 node = root['xa_head']
44 if not (is_internal_node(node)):
49 node = entry_to_node(node)
50 maxindex = node_maxindex(node)
52 if (index > maxindex):
55 shift = node['shift'] + constants.LX_RADIX_TREE_MAP_SHIFT
58 offset = (index >> node['shift']) & constants.LX_RADIX_TREE_MAP_MASK
59 slot = node['slots'][offset]
64 node = slot.cast(node.type.pointer()).dereference()
68 shift -= constants.LX_RADIX_TREE_MAP_SHIFT
74 class LxRadixTree(gdb.Function):
75 """ Lookup and return a node from a RadixTree.
77 $lx_radix_tree_lookup(root_node [, index]): Return the node at the given index.
78 If index is omitted, the root node is dereference and returned."""
81 super(LxRadixTree, self).__init__("lx_radix_tree_lookup")
83 def invoke(self, root, index=0):
84 result = lookup(root, index)
86 raise gdb.GdbError("No entry in tree at index {}".format(index))