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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253# SPDX-License-Identifier: GPL-2.0## Maple tree helpers## Copyright (c) 2025 Broadcom## Authors:# Florian Fainelli <florian.fainelli@broadcom.com>
import gdb
from linux import utilsfrom linux import constantsfrom linux import xarray
maple_tree_root_type = utils.CachedType("struct maple_tree")maple_node_type = utils.CachedType("struct maple_node")maple_enode_type = utils.CachedType("void")
maple_dense = 0maple_leaf_64 = 1maple_range_64 = 2maple_arange_64 = 3
class Mas(object): ma_active = 0 ma_start = 1 ma_root = 2 ma_none = 3 ma_pause = 4 ma_overflow = 5 ma_underflow = 6 ma_error = 7
def __init__(self, mt, first, end): if mt.type == maple_tree_root_type.get_type().pointer(): self.tree = mt.dereference() elif mt.type != maple_tree_root_type.get_type(): raise gdb.GdbError("must be {} not {}" .format(maple_tree_root_type.get_type().pointer(), mt.type)) self.tree = mt self.index = first self.last = end self.node = None self.status = self.ma_start self.min = 0 self.max = -1
def is_start(self): # mas_is_start() return self.status == self.ma_start
def is_ptr(self): # mas_is_ptr() return self.status == self.ma_root
def is_none(self): # mas_is_none() return self.status == self.ma_none
def root(self): # mas_root() return self.tree['ma_root'].cast(maple_enode_type.get_type().pointer())
def start(self): # mas_start() if self.is_start() is False: return None
self.min = 0 self.max = ~0
while True: self.depth = 0 root = self.root() if xarray.xa_is_node(root): self.depth = 0 self.status = self.ma_active self.node = mte_safe_root(root) self.offset = 0 if mte_dead_node(self.node) is True: continue
return None
self.node = None # Empty tree if root is None: self.status = self.ma_none self.offset = constants.LX_MAPLE_NODE_SLOTS return None
# Single entry tree self.status = self.ma_root self.offset = constants.LX_MAPLE_NODE_SLOTS
if self.index != 0: return None
return root
return None
def reset(self): # mas_reset() self.status = self.ma_start self.node = None
def mte_safe_root(node): if node.type != maple_enode_type.get_type().pointer(): raise gdb.GdbError("{} must be {} not {}" .format(mte_safe_root.__name__, maple_enode_type.get_type().pointer(), node.type)) ulong_type = utils.get_ulong_type() indirect_ptr = node.cast(ulong_type) & ~0x2 val = indirect_ptr.cast(maple_enode_type.get_type().pointer()) return val
def mte_node_type(entry): ulong_type = utils.get_ulong_type() val = None if entry.type == maple_enode_type.get_type().pointer(): val = entry.cast(ulong_type) elif entry.type == ulong_type: val = entry else: raise gdb.GdbError("{} must be {} not {}" .format(mte_node_type.__name__, maple_enode_type.get_type().pointer(), entry.type)) return (val >> 0x3) & 0xf
def ma_dead_node(node): if node.type != maple_node_type.get_type().pointer(): raise gdb.GdbError("{} must be {} not {}" .format(ma_dead_node.__name__, maple_node_type.get_type().pointer(), node.type)) ulong_type = utils.get_ulong_type() parent = node['parent'] indirect_ptr = node['parent'].cast(ulong_type) & ~constants.LX_MAPLE_NODE_MASK return indirect_ptr == node
def mte_to_node(enode): ulong_type = utils.get_ulong_type() if enode.type == maple_enode_type.get_type().pointer(): indirect_ptr = enode.cast(ulong_type) elif enode.type == ulong_type: indirect_ptr = enode else: raise gdb.GdbError("{} must be {} not {}" .format(mte_to_node.__name__, maple_enode_type.get_type().pointer(), enode.type)) indirect_ptr = indirect_ptr & ~constants.LX_MAPLE_NODE_MASK return indirect_ptr.cast(maple_node_type.get_type().pointer())
def mte_dead_node(enode): if enode.type != maple_enode_type.get_type().pointer(): raise gdb.GdbError("{} must be {} not {}" .format(mte_dead_node.__name__, maple_enode_type.get_type().pointer(), enode.type)) node = mte_to_node(enode) return ma_dead_node(node)
def ma_is_leaf(tp): result = tp < maple_range_64 return tp < maple_range_64
def mt_pivots(t): if t == maple_dense: return 0 elif t == maple_leaf_64 or t == maple_range_64: return constants.LX_MAPLE_RANGE64_SLOTS - 1 elif t == maple_arange_64: return constants.LX_MAPLE_ARANGE64_SLOTS - 1
def ma_pivots(node, t): if node.type != maple_node_type.get_type().pointer(): raise gdb.GdbError("{}: must be {} not {}" .format(ma_pivots.__name__, maple_node_type.get_type().pointer(), node.type)) if t == maple_arange_64: return node['ma64']['pivot'] elif t == maple_leaf_64 or t == maple_range_64: return node['mr64']['pivot'] else: return None
def ma_slots(node, tp): if node.type != maple_node_type.get_type().pointer(): raise gdb.GdbError("{}: must be {} not {}" .format(ma_slots.__name__, maple_node_type.get_type().pointer(), node.type)) if tp == maple_arange_64: return node['ma64']['slot'] elif tp == maple_range_64 or tp == maple_leaf_64: return node['mr64']['slot'] elif tp == maple_dense: return node['slot'] else: return None
def mt_slot(mt, slots, offset): ulong_type = utils.get_ulong_type() return slots[offset].cast(ulong_type)
def mtree_lookup_walk(mas): ulong_type = utils.get_ulong_type() n = mas.node
while True: node = mte_to_node(n) tp = mte_node_type(n) pivots = ma_pivots(node, tp) end = mt_pivots(tp) offset = 0 while True: if pivots[offset] >= mas.index: break if offset >= end: break offset += 1
slots = ma_slots(node, tp) n = mt_slot(mas.tree, slots, offset) if ma_dead_node(node) is True: mas.reset() return None break
if ma_is_leaf(tp) is True: break
return n
def mtree_load(mt, index): ulong_type = utils.get_ulong_type() # MT_STATE(...) mas = Mas(mt, index, index) entry = None
while True: entry = mas.start() if mas.is_none(): return None
if mas.is_ptr(): if index != 0: entry = None return entry
entry = mtree_lookup_walk(mas) if entry is None and mas.is_start(): continue else: break
if xarray.xa_is_zero(entry): return None
return entry