xref: /linux-6.15/scripts/gdb/linux/radixtree.py (revision bb970707) 
1#
2# gdb helper commands and functions for Linux kernel debugging
3#
4#  Radix Tree Parser
5#
6# Copyright (c) 2016 Linaro Ltd
7#
8# Authors:
9#  Kieran Bingham <[email protected]>
10#
11# This work is licensed under the terms of the GNU GPL version 2.
12#
13
14import gdb
15
16from linux import utils
17from linux import constants
18
19radix_tree_root_type = utils.CachedType("struct radix_tree_root")
20radix_tree_node_type = utils.CachedType("struct radix_tree_node")
21
22
23def is_indirect_ptr(node):
24    long_type = utils.get_long_type()
25    return (node.cast(long_type) & constants.LX_RADIX_TREE_INDIRECT_PTR)
26
27
28def indirect_to_ptr(node):
29    long_type = utils.get_long_type()
30    node_type = node.type
31    indirect_ptr = node.cast(long_type) & ~constants.LX_RADIX_TREE_INDIRECT_PTR
32    return indirect_ptr.cast(node_type)
33
34
35def maxindex(height):
36    height = height & constants.LX_RADIX_TREE_HEIGHT_MASK
37    return gdb.parse_and_eval("height_to_maxindex["+str(height)+"]")
38
39
40def lookup(root, index):
41    if root.type == radix_tree_root_type.get_type().pointer():
42        root = root.dereference()
43    elif root.type != radix_tree_root_type.get_type():
44        raise gdb.GdbError("Must be struct radix_tree_root not {}"
45                           .format(root.type))
46
47    node = root['rnode']
48    if node is 0:
49        return None
50
51    if not (is_indirect_ptr(node)):
52        if (index > 0):
53            return None
54        return node
55
56    node = indirect_to_ptr(node)
57
58    height = node['path'] & constants.LX_RADIX_TREE_HEIGHT_MASK
59    if (index > maxindex(height)):
60        return None
61
62    shift = (height-1) * constants.LX_RADIX_TREE_MAP_SHIFT
63
64    while True:
65        new_index = (index >> shift) & constants.LX_RADIX_TREE_MAP_MASK
66        slot = node['slots'][new_index]
67
68        node = slot.cast(node.type.pointer()).dereference()
69        if node is 0:
70            return None
71
72        shift -= constants.LX_RADIX_TREE_MAP_SHIFT
73        height -= 1
74
75        if (height <= 0):
76            break
77
78    return node
79
80
81class LxRadixTree(gdb.Function):
82    """ Lookup and return a node from a RadixTree.
83
84$lx_radix_tree_lookup(root_node [, index]): Return the node at the given index.
85If index is omitted, the root node is dereferenced and returned."""
86
87    def __init__(self):
88        super(LxRadixTree, self).__init__("lx_radix_tree_lookup")
89
90    def invoke(self, root, index=0):
91        result = lookup(root, index)
92        if result is None:
93            raise gdb.GdbError("No entry in tree at index {}".format(index))
94
95        return result
96
97LxRadixTree()
98