scripts/gdb/linux/radixtree.py

# 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 utils
from 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()