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# Maple tree helpers
4#
5# Copyright (c) 2025 Broadcom
6#
7# Authors:
8# Florian Fainelli <florian.fainelli@broadcom.com>
9
10import gdb
11
12from linux import utils
13from linux import constants
14from linux import xarray
15
16maple_tree_root_type = utils.CachedType("struct maple_tree")
17maple_node_type = utils.CachedType("struct maple_node")
18maple_enode_type = utils.CachedType("void")
19
20maple_dense = 0
21maple_leaf_64 = 1
22maple_range_64 = 2
23maple_arange_64 = 3
24
25class Mas(object):
26 ma_active = 0
27 ma_start = 1
28 ma_root = 2
29 ma_none = 3
30 ma_pause = 4
31 ma_overflow = 5
32 ma_underflow = 6
33 ma_error = 7
34
35 def __init__(self, mt, first, end):
36 if mt.type == maple_tree_root_type.get_type().pointer():
37 self.tree = mt.dereference()
38 elif mt.type != maple_tree_root_type.get_type():
39 raise gdb.GdbError("must be {} not {}"
40 .format(maple_tree_root_type.get_type().pointer(), mt.type))
41 self.tree = mt
42 self.index = first
43 self.last = end
44 self.node = None
45 self.status = self.ma_start
46 self.min = 0
47 self.max = -1
48
49 def is_start(self):
50 # mas_is_start()
51 return self.status == self.ma_start
52
53 def is_ptr(self):
54 # mas_is_ptr()
55 return self.status == self.ma_root
56
57 def is_none(self):
58 # mas_is_none()
59 return self.status == self.ma_none
60
61 def root(self):
62 # mas_root()
63 return self.tree['ma_root'].cast(maple_enode_type.get_type().pointer())
64
65 def start(self):
66 # mas_start()
67 if self.is_start() is False:
68 return None
69
70 self.min = 0
71 self.max = ~0
72
73 while True:
74 self.depth = 0
75 root = self.root()
76 if xarray.xa_is_node(root):
77 self.depth = 0
78 self.status = self.ma_active
79 self.node = mte_safe_root(root)
80 self.offset = 0
81 if mte_dead_node(self.node) is True:
82 continue
83
84 return None
85
86 self.node = None
87 # Empty tree
88 if root is None:
89 self.status = self.ma_none
90 self.offset = constants.LX_MAPLE_NODE_SLOTS
91 return None
92
93 # Single entry tree
94 self.status = self.ma_root
95 self.offset = constants.LX_MAPLE_NODE_SLOTS
96
97 if self.index != 0:
98 return None
99
100 return root
101
102 return None
103
104 def reset(self):
105 # mas_reset()
106 self.status = self.ma_start
107 self.node = None
108
109def mte_safe_root(node):
110 if node.type != maple_enode_type.get_type().pointer():
111 raise gdb.GdbError("{} must be {} not {}"
112 .format(mte_safe_root.__name__, maple_enode_type.get_type().pointer(), node.type))
113 ulong_type = utils.get_ulong_type()
114 indirect_ptr = node.cast(ulong_type) & ~0x2
115 val = indirect_ptr.cast(maple_enode_type.get_type().pointer())
116 return val
117
118def mte_node_type(entry):
119 ulong_type = utils.get_ulong_type()
120 val = None
121 if entry.type == maple_enode_type.get_type().pointer():
122 val = entry.cast(ulong_type)
123 elif entry.type == ulong_type:
124 val = entry
125 else:
126 raise gdb.GdbError("{} must be {} not {}"
127 .format(mte_node_type.__name__, maple_enode_type.get_type().pointer(), entry.type))
128 return (val >> 0x3) & 0xf
129
130def ma_dead_node(node):
131 if node.type != maple_node_type.get_type().pointer():
132 raise gdb.GdbError("{} must be {} not {}"
133 .format(ma_dead_node.__name__, maple_node_type.get_type().pointer(), node.type))
134 ulong_type = utils.get_ulong_type()
135 parent = node['parent']
136 indirect_ptr = node['parent'].cast(ulong_type) & ~constants.LX_MAPLE_NODE_MASK
137 return indirect_ptr == node
138
139def mte_to_node(enode):
140 ulong_type = utils.get_ulong_type()
141 if enode.type == maple_enode_type.get_type().pointer():
142 indirect_ptr = enode.cast(ulong_type)
143 elif enode.type == ulong_type:
144 indirect_ptr = enode
145 else:
146 raise gdb.GdbError("{} must be {} not {}"
147 .format(mte_to_node.__name__, maple_enode_type.get_type().pointer(), enode.type))
148 indirect_ptr = indirect_ptr & ~constants.LX_MAPLE_NODE_MASK
149 return indirect_ptr.cast(maple_node_type.get_type().pointer())
150
151def mte_dead_node(enode):
152 if enode.type != maple_enode_type.get_type().pointer():
153 raise gdb.GdbError("{} must be {} not {}"
154 .format(mte_dead_node.__name__, maple_enode_type.get_type().pointer(), enode.type))
155 node = mte_to_node(enode)
156 return ma_dead_node(node)
157
158def ma_is_leaf(tp):
159 result = tp < maple_range_64
160 return tp < maple_range_64
161
162def mt_pivots(t):
163 if t == maple_dense:
164 return 0
165 elif t == maple_leaf_64 or t == maple_range_64:
166 return constants.LX_MAPLE_RANGE64_SLOTS - 1
167 elif t == maple_arange_64:
168 return constants.LX_MAPLE_ARANGE64_SLOTS - 1
169
170def ma_pivots(node, t):
171 if node.type != maple_node_type.get_type().pointer():
172 raise gdb.GdbError("{}: must be {} not {}"
173 .format(ma_pivots.__name__, maple_node_type.get_type().pointer(), node.type))
174 if t == maple_arange_64:
175 return node['ma64']['pivot']
176 elif t == maple_leaf_64 or t == maple_range_64:
177 return node['mr64']['pivot']
178 else:
179 return None
180
181def ma_slots(node, tp):
182 if node.type != maple_node_type.get_type().pointer():
183 raise gdb.GdbError("{}: must be {} not {}"
184 .format(ma_slots.__name__, maple_node_type.get_type().pointer(), node.type))
185 if tp == maple_arange_64:
186 return node['ma64']['slot']
187 elif tp == maple_range_64 or tp == maple_leaf_64:
188 return node['mr64']['slot']
189 elif tp == maple_dense:
190 return node['slot']
191 else:
192 return None
193
194def mt_slot(mt, slots, offset):
195 ulong_type = utils.get_ulong_type()
196 return slots[offset].cast(ulong_type)
197
198def mtree_lookup_walk(mas):
199 ulong_type = utils.get_ulong_type()
200 n = mas.node
201
202 while True:
203 node = mte_to_node(n)
204 tp = mte_node_type(n)
205 pivots = ma_pivots(node, tp)
206 end = mt_pivots(tp)
207 offset = 0
208 while True:
209 if pivots[offset] >= mas.index:
210 break
211 if offset >= end:
212 break
213 offset += 1
214
215 slots = ma_slots(node, tp)
216 n = mt_slot(mas.tree, slots, offset)
217 if ma_dead_node(node) is True:
218 mas.reset()
219 return None
220 break
221
222 if ma_is_leaf(tp) is True:
223 break
224
225 return n
226
227def mtree_load(mt, index):
228 ulong_type = utils.get_ulong_type()
229 # MT_STATE(...)
230 mas = Mas(mt, index, index)
231 entry = None
232
233 while True:
234 entry = mas.start()
235 if mas.is_none():
236 return None
237
238 if mas.is_ptr():
239 if index != 0:
240 entry = None
241 return entry
242
243 entry = mtree_lookup_walk(mas)
244 if entry is None and mas.is_start():
245 continue
246 else:
247 break
248
249 if xarray.xa_is_zero(entry):
250 return None
251
252 return entry