1 # SPDX-License-Identifier: GPL-2.0 1 # SPDX-License-Identifier: GPL-2.0
2 # 2 #
3 # Radix Tree Parser 3 # Radix Tree Parser
4 # 4 #
5 # Copyright (c) 2016 Linaro Ltd 5 # Copyright (c) 2016 Linaro Ltd
6 # Copyright (c) 2023 Broadcom 6 # Copyright (c) 2023 Broadcom
7 # 7 #
8 # Authors: 8 # Authors:
9 # Kieran Bingham <kieran.bingham@linaro.org> 9 # Kieran Bingham <kieran.bingham@linaro.org>
10 # Florian Fainelli <f.fainelli@gmail.com> 10 # Florian Fainelli <f.fainelli@gmail.com>
11 11
12 import gdb 12 import gdb
13 13
14 from linux import utils 14 from linux import utils
15 from linux import constants 15 from linux import constants
16 16
17 radix_tree_root_type = utils.CachedType("struc 17 radix_tree_root_type = utils.CachedType("struct xarray")
18 radix_tree_node_type = utils.CachedType("struc 18 radix_tree_node_type = utils.CachedType("struct xa_node")
19 19
20 def is_internal_node(node): 20 def is_internal_node(node):
21 long_type = utils.get_long_type() 21 long_type = utils.get_long_type()
22 return ((node.cast(long_type) & constants. 22 return ((node.cast(long_type) & constants.LX_RADIX_TREE_ENTRY_MASK) == constants.LX_RADIX_TREE_INTERNAL_NODE)
23 23
24 def entry_to_node(node): 24 def entry_to_node(node):
25 long_type = utils.get_long_type() 25 long_type = utils.get_long_type()
26 node_type = node.type 26 node_type = node.type
27 indirect_ptr = node.cast(long_type) & ~con 27 indirect_ptr = node.cast(long_type) & ~constants.LX_RADIX_TREE_INTERNAL_NODE
28 return indirect_ptr.cast(radix_tree_node_t 28 return indirect_ptr.cast(radix_tree_node_type.get_type().pointer())
29 29
30 def node_maxindex(node): 30 def node_maxindex(node):
31 return (constants.LX_RADIX_TREE_MAP_SIZE < 31 return (constants.LX_RADIX_TREE_MAP_SIZE << node['shift']) - 1
32 32
33 def lookup(root, index): 33 def lookup(root, index):
34 if root.type == radix_tree_root_type.get_t 34 if root.type == radix_tree_root_type.get_type().pointer():
35 node = root.dereference() 35 node = root.dereference()
36 elif root.type != radix_tree_root_type.get 36 elif root.type != radix_tree_root_type.get_type():
37 raise gdb.GdbError("must be {} not {}" 37 raise gdb.GdbError("must be {} not {}"
38 .format(radix_tree_ 38 .format(radix_tree_root_type.get_type(), root.type))
39 39
40 node = root['xa_head'] 40 node = root['xa_head']
41 if node == 0: 41 if node == 0:
42 return None 42 return None
43 43
44 if not (is_internal_node(node)): 44 if not (is_internal_node(node)):
45 if (index > 0): 45 if (index > 0):
46 return None 46 return None
47 return node 47 return node
48 48
49 node = entry_to_node(node) 49 node = entry_to_node(node)
50 maxindex = node_maxindex(node) 50 maxindex = node_maxindex(node)
51 51
52 if (index > maxindex): 52 if (index > maxindex):
53 return None 53 return None
54 54
55 shift = node['shift'] + constants.LX_RADIX 55 shift = node['shift'] + constants.LX_RADIX_TREE_MAP_SHIFT
56 56
57 while True: 57 while True:
58 offset = (index >> node['shift']) & co 58 offset = (index >> node['shift']) & constants.LX_RADIX_TREE_MAP_MASK
59 slot = node['slots'][offset] 59 slot = node['slots'][offset]
60 60
61 if slot == 0: 61 if slot == 0:
62 return None 62 return None
63 63
64 node = slot.cast(node.type.pointer()). 64 node = slot.cast(node.type.pointer()).dereference()
65 if node == 0: 65 if node == 0:
66 return None 66 return None
67 67
68 shift -= constants.LX_RADIX_TREE_MAP_S 68 shift -= constants.LX_RADIX_TREE_MAP_SHIFT
69 if (shift <= 0): 69 if (shift <= 0):
70 break 70 break
71 71
72 return node 72 return node
73 73
74 class LxRadixTree(gdb.Function): 74 class LxRadixTree(gdb.Function):
75 """ Lookup and return a node from a RadixT 75 """ Lookup and return a node from a RadixTree.
76 76
77 $lx_radix_tree_lookup(root_node [, index]): Re 77 $lx_radix_tree_lookup(root_node [, index]): Return the node at the given index.
78 If index is omitted, the root node is derefere 78 If index is omitted, the root node is dereference and returned."""
79 79
80 def __init__(self): 80 def __init__(self):
81 super(LxRadixTree, self).__init__("lx_ 81 super(LxRadixTree, self).__init__("lx_radix_tree_lookup")
82 82
83 def invoke(self, root, index=0): 83 def invoke(self, root, index=0):
84 result = lookup(root, index) 84 result = lookup(root, index)
85 if result is None: 85 if result is None:
86 raise gdb.GdbError("No entry in tr 86 raise gdb.GdbError("No entry in tree at index {}".format(index))
87 87
88 return result 88 return result
89 89
90 LxRadixTree() 90 LxRadixTree()
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.