scripts/gdb/linux/radixtree.py

   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 <[email protected]>
  10 #  Florian Fainelli <[email protected]>
  11
  12 import gdb
  13
  14 from linux import utils
  15 from linux import constants
  16
  17 radix_tree_root_type = utils.CachedType("struct xarray")
  18 radix_tree_node_type = utils.CachedType("struct xa_node")
  19
  20 def 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
  24 def 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
  30 def node_maxindex(node):
  31     return (constants.LX_RADIX_TREE_MAP_SIZE << node['shift']) - 1
  32
  33 def 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
  74 class 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.
  78 If 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
  90 LxRadixTree()