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 lookup(root, index):
34    if root.type == radix_tree_root_type.get_type().pointer():
35        node = root.dereference()
36    elif root.type != radix_tree_root_type.get_type():
37        raise gdb.GdbError("must be {} not {}"
38                           .format(radix_tree_root_type.get_type(), root.type))
39
40    node = root['xa_head']
41    if node == 0:
42        return None
43
44    if not (is_internal_node(node)):
45        if (index > 0):
46            return None
47        return node
48
49    node = entry_to_node(node)
50    maxindex = node_maxindex(node)
51
52    if (index > maxindex):
53        return None
54
55    shift = node['shift'] + constants.LX_RADIX_TREE_MAP_SHIFT
56
57    while True:
58        offset = (index >> node['shift']) & constants.LX_RADIX_TREE_MAP_MASK
59        slot = node['slots'][offset]
60
61        if slot == 0:
62            return None
63
64        node = slot.cast(node.type.pointer()).dereference()
65        if node == 0:
66            return None
67
68        shift -= constants.LX_RADIX_TREE_MAP_SHIFT
69        if (shift <= 0):
70            break
71
72    return node
73
74class LxRadixTree(gdb.Function):
75    """ Lookup and return a node from a RadixTree.
76
77$lx_radix_tree_lookup(root_node [, index]): Return the node at the given index.
78If index is omitted, the root node is dereference and returned."""
79
80    def __init__(self):
81        super(LxRadixTree, self).__init__("lx_radix_tree_lookup")
82
83    def invoke(self, root, index=0):
84        result = lookup(root, index)
85        if result is None:
86            raise gdb.GdbError("No entry in tree at index {}".format(index))
87
88        return result
89
90LxRadixTree()