radixtree.py

  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()