Something went wrong. Try again.
Linux kernel mirror (for testing) git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216# SPDX-License-Identifier: GPL-2.0## Radix Tree Parser## Copyright (c) 2016 Linaro Ltd# Copyright (c) 2023 Broadcom## Authors:# Kieran Bingham <kieran.bingham@linaro.org># Florian Fainelli <f.fainelli@gmail.com>
import gdb
from linux import utilsfrom linux import constants
radix_tree_root_type = utils.CachedType("struct xarray")radix_tree_node_type = utils.CachedType("struct xa_node")
def is_internal_node(node): long_type = utils.get_long_type() return ((node.cast(long_type) & constants.LX_RADIX_TREE_ENTRY_MASK) == constants.LX_RADIX_TREE_INTERNAL_NODE)
def entry_to_node(node): long_type = utils.get_long_type() node_type = node.type indirect_ptr = node.cast(long_type) & ~constants.LX_RADIX_TREE_INTERNAL_NODE return indirect_ptr.cast(radix_tree_node_type.get_type().pointer())
def node_maxindex(node): return (constants.LX_RADIX_TREE_MAP_SIZE << node['shift']) - 1
def resolve_root(root): if root.type == radix_tree_root_type.get_type(): return root if root.type == radix_tree_root_type.get_type().pointer(): return root.dereference() raise gdb.GdbError("must be {} not {}" .format(radix_tree_root_type.get_type(), root.type))
def lookup(root, index): root = resolve_root(root) node = root['xa_head'] if node == 0: return None
if not (is_internal_node(node)): if (index > 0): return None return node
node = entry_to_node(node) maxindex = node_maxindex(node)
if (index > maxindex): return None
shift = node['shift'] + constants.LX_RADIX_TREE_MAP_SHIFT
while True: offset = (index >> node['shift']) & constants.LX_RADIX_TREE_MAP_MASK slot = node['slots'][offset]
if slot == 0: return None
node = slot.cast(node.type.pointer()).dereference() if node == 0: return None
shift -= constants.LX_RADIX_TREE_MAP_SHIFT if (shift <= 0): break
return node
def descend(parent, index): offset = (index >> int(parent["shift"])) & constants.LX_RADIX_TREE_MAP_MASK return offset, parent["slots"][offset]
def load_root(root): node = root["xa_head"] nodep = node
if is_internal_node(node): node = entry_to_node(node) maxindex = node_maxindex(node) return int(node["shift"]) + constants.LX_RADIX_TREE_MAP_SHIFT, \ nodep, maxindex
return 0, nodep, 0
class RadixTreeIter: def __init__(self, start): self.index = 0 self.next_index = start self.node = None
def xa_mk_internal(v): return (v << 2) | 2
LX_XA_RETRY_ENTRY = xa_mk_internal(256)LX_RADIX_TREE_RETRY = LX_XA_RETRY_ENTRY
def next_chunk(root, iter): mask = (1 << (utils.get_ulong_type().sizeof * 8)) - 1
index = iter.next_index if index == 0 and iter.index != 0: return None
restart = True while restart: restart = False
_, child, maxindex = load_root(root) if index > maxindex: return None if not child: return None
if not is_internal_node(child): iter.index = index iter.next_index = (maxindex + 1) & mask iter.node = None return root["xa_head"].address
while True: node = entry_to_node(child) offset, child = descend(node, index)
if not child: while True: offset += 1 if offset >= constants.LX_RADIX_TREE_MAP_SIZE: break slot = node["slots"][offset] if slot: break index &= ~node_maxindex(node) index = (index + (offset << int(node["shift"]))) & mask if index == 0: return None if offset == constants.LX_RADIX_TREE_MAP_SIZE: restart = True break child = node["slots"][offset]
if not child: restart = True break if child == LX_XA_RETRY_ENTRY: break if not node["shift"] or not is_internal_node(child): break
iter.index = (index & ~node_maxindex(node)) | offset iter.next_index = ((index | node_maxindex(node)) + 1) & mask iter.node = node
return node["slots"][offset].address
def next_slot(slot, iter): mask = (1 << (utils.get_ulong_type().sizeof * 8)) - 1 for _ in range(iter.next_index - iter.index - 1): slot += 1 iter.index = (iter.index + 1) & mask if slot.dereference(): return slot return None
def for_each_slot(root, start=0): iter = RadixTreeIter(start) slot = None while True: if not slot: slot = next_chunk(root, iter) if not slot: break yield iter.index, slot slot = next_slot(slot, iter)
class LxRadixTreeLookup(gdb.Function): """ Lookup and return a node from a RadixTree.
$lx_radix_tree_lookup(root_node [, index]): Return the node at the given index.If index is omitted, the root node is dereference and returned."""
def __init__(self): super(LxRadixTreeLookup, self).__init__("lx_radix_tree_lookup")
def invoke(self, root, index=0): result = lookup(root, index) if result is None: raise gdb.GdbError("No entry in tree at index {}".format(index))
return result
class LxRadixTree(gdb.Command): """Show all values stored in a RadixTree."""
def __init__(self): super(LxRadixTree, self).__init__("lx-radix-tree", gdb.COMMAND_DATA, gdb.COMPLETE_NONE)
def invoke(self, argument, from_tty): args = gdb.string_to_argv(argument) if len(args) != 1: raise gdb.GdbError("Usage: lx-radix-tree ROOT") root = gdb.parse_and_eval(args[0]) for index, slot in for_each_slot(root): gdb.write("[{}] = {}\n".format(index, slot.dereference()))
LxRadixTree()LxRadixTreeLookup()