Linux kernel mirror (for testing)
git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
tjh.dev
kernel
os
linux
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
12import gdb
13
14from linux import utils
15from linux import constants
16
17radix_tree_root_type = utils.CachedType("struct xarray")
18radix_tree_node_type = utils.CachedType("struct xa_node")
19
20def 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
24def 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
30def node_maxindex(node):
31 return (constants.LX_RADIX_TREE_MAP_SIZE << node['shift']) - 1
32
33def resolve_root(root):
34 if root.type == radix_tree_root_type.get_type():
35 return root
36 if root.type == radix_tree_root_type.get_type().pointer():
37 return root.dereference()
38 raise gdb.GdbError("must be {} not {}"
39 .format(radix_tree_root_type.get_type(), root.type))
40
41def lookup(root, index):
42 root = resolve_root(root)
43 node = root['xa_head']
44 if node == 0:
45 return None
46
47 if not (is_internal_node(node)):
48 if (index > 0):
49 return None
50 return node
51
52 node = entry_to_node(node)
53 maxindex = node_maxindex(node)
54
55 if (index > maxindex):
56 return None
57
58 shift = node['shift'] + constants.LX_RADIX_TREE_MAP_SHIFT
59
60 while True:
61 offset = (index >> node['shift']) & constants.LX_RADIX_TREE_MAP_MASK
62 slot = node['slots'][offset]
63
64 if slot == 0:
65 return None
66
67 node = slot.cast(node.type.pointer()).dereference()
68 if node == 0:
69 return None
70
71 shift -= constants.LX_RADIX_TREE_MAP_SHIFT
72 if (shift <= 0):
73 break
74
75 return node
76
77def descend(parent, index):
78 offset = (index >> int(parent["shift"])) & constants.LX_RADIX_TREE_MAP_MASK
79 return offset, parent["slots"][offset]
80
81def load_root(root):
82 node = root["xa_head"]
83 nodep = node
84
85 if is_internal_node(node):
86 node = entry_to_node(node)
87 maxindex = node_maxindex(node)
88 return int(node["shift"]) + constants.LX_RADIX_TREE_MAP_SHIFT, \
89 nodep, maxindex
90
91 return 0, nodep, 0
92
93class RadixTreeIter:
94 def __init__(self, start):
95 self.index = 0
96 self.next_index = start
97 self.node = None
98
99def xa_mk_internal(v):
100 return (v << 2) | 2
101
102LX_XA_RETRY_ENTRY = xa_mk_internal(256)
103LX_RADIX_TREE_RETRY = LX_XA_RETRY_ENTRY
104
105def next_chunk(root, iter):
106 mask = (1 << (utils.get_ulong_type().sizeof * 8)) - 1
107
108 index = iter.next_index
109 if index == 0 and iter.index != 0:
110 return None
111
112 restart = True
113 while restart:
114 restart = False
115
116 _, child, maxindex = load_root(root)
117 if index > maxindex:
118 return None
119 if not child:
120 return None
121
122 if not is_internal_node(child):
123 iter.index = index
124 iter.next_index = (maxindex + 1) & mask
125 iter.node = None
126 return root["xa_head"].address
127
128 while True:
129 node = entry_to_node(child)
130 offset, child = descend(node, index)
131
132 if not child:
133 while True:
134 offset += 1
135 if offset >= constants.LX_RADIX_TREE_MAP_SIZE:
136 break
137 slot = node["slots"][offset]
138 if slot:
139 break
140 index &= ~node_maxindex(node)
141 index = (index + (offset << int(node["shift"]))) & mask
142 if index == 0:
143 return None
144 if offset == constants.LX_RADIX_TREE_MAP_SIZE:
145 restart = True
146 break
147 child = node["slots"][offset]
148
149 if not child:
150 restart = True
151 break
152 if child == LX_XA_RETRY_ENTRY:
153 break
154 if not node["shift"] or not is_internal_node(child):
155 break
156
157 iter.index = (index & ~node_maxindex(node)) | offset
158 iter.next_index = ((index | node_maxindex(node)) + 1) & mask
159 iter.node = node
160
161 return node["slots"][offset].address
162
163def next_slot(slot, iter):
164 mask = (1 << (utils.get_ulong_type().sizeof * 8)) - 1
165 for _ in range(iter.next_index - iter.index - 1):
166 slot += 1
167 iter.index = (iter.index + 1) & mask
168 if slot.dereference():
169 return slot
170 return None
171
172def for_each_slot(root, start=0):
173 iter = RadixTreeIter(start)
174 slot = None
175 while True:
176 if not slot:
177 slot = next_chunk(root, iter)
178 if not slot:
179 break
180 yield iter.index, slot
181 slot = next_slot(slot, iter)
182
183class LxRadixTreeLookup(gdb.Function):
184 """ Lookup and return a node from a RadixTree.
185
186$lx_radix_tree_lookup(root_node [, index]): Return the node at the given index.
187If index is omitted, the root node is dereference and returned."""
188
189 def __init__(self):
190 super(LxRadixTreeLookup, self).__init__("lx_radix_tree_lookup")
191
192 def invoke(self, root, index=0):
193 result = lookup(root, index)
194 if result is None:
195 raise gdb.GdbError("No entry in tree at index {}".format(index))
196
197 return result
198
199class LxRadixTree(gdb.Command):
200 """Show all values stored in a RadixTree."""
201
202 def __init__(self):
203 super(LxRadixTree, self).__init__("lx-radix-tree", gdb.COMMAND_DATA,
204 gdb.COMPLETE_NONE)
205
206 def invoke(self, argument, from_tty):
207 args = gdb.string_to_argv(argument)
208 if len(args) != 1:
209 raise gdb.GdbError("Usage: lx-radix-tree ROOT")
210 root = gdb.parse_and_eval(args[0])
211 for index, slot in for_each_slot(root):
212 gdb.write("[{}] = {}\n".format(index, slot.dereference()))
213
214LxRadixTree()
215LxRadixTreeLookup()