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