1 # SPDX-License-Identifier: GPL-2.0
2 #
3 # Radix Tree Parser
4 #
5 # Copyright (c) 2016 Linaro Ltd
6 # Copyright (c) 2023 Broadcom
7 #
8 # Authors:
9 # Kieran Bingham <kieran.bingham@linaro.org>
10 # Florian Fainelli <f.fainelli@gmail.com>
11
12 import gdb
13
14 from linux import utils
15 from linux import constants
16
17 radix_tree_root_type = utils.CachedType("struct xarray")
18 radix_tree_node_type = utils.CachedType("struct xa_node")
19
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)
23
24 def entry_to_node(node):
25 long_type = utils.get_long_type()
26 node_type = node.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())
29
30 def node_maxindex(node):
31 return (constants.LX_RADIX_TREE_MAP_SIZE << node['shift']) - 1
32
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))
39
40 node = root['xa_head']
41 if node == 0:
42 return None
43
44 if not (is_internal_node(node)):
45 if (index > 0):
46 return None
47 return node
48
49 node = entry_to_node(node)
50 maxindex = node_maxindex(node)
51
52 if (index > maxindex):
53 return None
54
55 shift = node['shift'] + constants.LX_RADIX_TREE_MAP_SHIFT
56
57 while True:
58 offset = (index >> node['shift']) & constants.LX_RADIX_TREE_MAP_MASK
59 slot = node['slots'][offset]
60
61 if slot == 0:
62 return None
63
64 node = slot.cast(node.type.pointer()).dereference()
65 if node == 0:
66 return None
67
68 shift -= constants.LX_RADIX_TREE_MAP_SHIFT
69 if (shift <= 0):
70 break
71
72 return node
73
74 class LxRadixTree(gdb.Function):
75 """ Lookup and return a node from a RadixTree.
76
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."""
79
80 def __init__(self):
81 super(LxRadixTree, self).__init__("lx_radix_tree_lookup")
82
83 def invoke(self, root, index=0):
84 result = lookup(root, index)
85 if result is None:
86 raise gdb.GdbError("No entry in tree at index {}".format(index))
87
88 return result
89
90 LxRadixTree()
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.