mapletree.py

  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