xref: /linux/scripts/gdb/linux/mapletree.py (revision 3f31a806a62e44f7498e2d17719c03f816553f11) 
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
253