From nobody Tue Oct 7 12:28:19 2025 Received: from mx0a-001b2d01.pphosted.com (mx0a-001b2d01.pphosted.com [148.163.156.1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 2376D258CCB; Thu, 10 Jul 2025 11:59:48 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=148.163.156.1 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1752148790; cv=none; b=AkeKqkE3SY76+icqLp4XPU2l3bkF2a3SYPMcDwItU7rrAnmzZd2L2PVrnnzb+3fA1ni64rgzbTgGMyfSPQonNnwXQjV8FLBjpaMmydtjS31Mcz0exF9s9yurf/LtyvcmaG17lAaJjXr/QP7ef6M81dZJ6/6avE9KJtFISHZOenY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1752148790; c=relaxed/simple; bh=HygZCDxM2zeQJTGOGX/OGLwqWpEBrXrljJjgH3AvafA=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=YFW+Ws6A45wZf/BPKnlJ1xi61dZ4Z6RcFsT3Dy8W/k1tcB/LKeUHPh5e/Yx9DJJNyzxqVshZYXDIc9C7G3AnXmUg5FkgIs4RWdhhMaJwlzjEgltlsIPOFbg19vXUlM4L94QgItkfw9JmgOxesqVFur+FU3ZvQ75eZH5oT4UIxR4= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=linux.ibm.com; spf=pass smtp.mailfrom=linux.ibm.com; dkim=pass (2048-bit key) header.d=ibm.com header.i=@ibm.com header.b=hSxYnC2I; arc=none smtp.client-ip=148.163.156.1 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=linux.ibm.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=linux.ibm.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ibm.com header.i=@ibm.com header.b="hSxYnC2I" Received: from pps.filterd (m0356517.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 56A87G2j003799; Thu, 10 Jul 2025 11:59:34 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ibm.com; h=cc :content-transfer-encoding:date:from:in-reply-to:message-id :mime-version:references:subject:to; s=pp1; bh=BlCLisSp+PRyi/ShQ z6fSFKLv2M1a/tji3Kf2bETgmU=; b=hSxYnC2IW1oXvaV2FjB9q2FbQgvpih48E wMWlWNQ9QC2/nAVvTvDyYXr0XxsENJROBX1wblDX9JtVOewk6Y8MHzkNdFU4XwSD J1LQTaUfirDPUP4Jti+qEJO1QfVW6vG4gEKJ68b5ccFUuguAIJdL/aafcAlExK5T GOVjKHwx7wUyVehzmquTTP0W3gY9vcigTuU1SiTo1hs697gPMNrwJ4h2ynjSCwSh srC3RSg6foHwsKw0M+9qe21lNHdjWniINeuDNduH9wDgcgpb38g/kaTMa0SF5C46 gOOcPMxLy2zjTVeNXsbIeCuk0LeWanAp2v+MOECOcPQwU1A+f/YJA== Received: from ppma23.wdc07v.mail.ibm.com (5d.69.3da9.ip4.static.sl-reverse.com [169.61.105.93]) by mx0a-001b2d01.pphosted.com (PPS) with ESMTPS id 47pusscq66-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Thu, 10 Jul 2025 11:59:33 +0000 (GMT) Received: from pps.filterd (ppma23.wdc07v.mail.ibm.com [127.0.0.1]) by ppma23.wdc07v.mail.ibm.com (8.18.1.2/8.18.1.2) with ESMTP id 56AAcdFq002847; Thu, 10 Jul 2025 11:59:32 GMT Received: from smtprelay03.fra02v.mail.ibm.com ([9.218.2.224]) by ppma23.wdc07v.mail.ibm.com (PPS) with ESMTPS id 47qfvmnch1-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Thu, 10 Jul 2025 11:59:32 +0000 Received: from smtpav05.fra02v.mail.ibm.com (smtpav05.fra02v.mail.ibm.com [10.20.54.104]) by smtprelay03.fra02v.mail.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 56ABxSIM53084456 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 10 Jul 2025 11:59:28 GMT Received: from smtpav05.fra02v.mail.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 547D32004D; Thu, 10 Jul 2025 11:59:28 +0000 (GMT) Received: from smtpav05.fra02v.mail.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 73CB520043; Thu, 10 Jul 2025 11:59:27 +0000 (GMT) Received: from heavy.ibm.com (unknown [9.87.154.34]) by smtpav05.fra02v.mail.ibm.com (Postfix) with ESMTP; Thu, 10 Jul 2025 11:59:27 +0000 (GMT) From: Ilya Leoshkevich To: Alexei Starovoitov , Daniel Borkmann , Andrii Nakryiko , Jan Kiszka , Kieran Bingham Cc: linux-kernel@vger.kernel.org, bpf@vger.kernel.org, Heiko Carstens , Vasily Gorbik , Alexander Gordeev , Ilya Leoshkevich Subject: [PATCH 1/2] scripts/gdb/radix-tree: add lx-radix-tree-command Date: Thu, 10 Jul 2025 13:53:19 +0200 Message-ID: <20250710115920.47740-2-iii@linux.ibm.com> X-Mailer: git-send-email 2.50.0 In-Reply-To: <20250710115920.47740-1-iii@linux.ibm.com> References: <20250710115920.47740-1-iii@linux.ibm.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-TM-AS-GCONF: 00 X-Authority-Analysis: v=2.4 cv=Vaj3PEp9 c=1 sm=1 tr=0 ts=686fab25 cx=c_pps a=3Bg1Hr4SwmMryq2xdFQyZA==:117 a=3Bg1Hr4SwmMryq2xdFQyZA==:17 a=Wb1JkmetP80A:10 a=VnNF1IyMAAAA:8 a=w8ZYW45Y_G11fWB9lMAA:9 X-Proofpoint-GUID: r5zPK5sibRcr2bvyNJciI4dAc4R6MTJ7 X-Proofpoint-ORIG-GUID: r5zPK5sibRcr2bvyNJciI4dAc4R6MTJ7 X-Proofpoint-Spam-Details-Enc: AW1haW4tMjUwNzEwMDEwMSBTYWx0ZWRfX9i7iB6Cv5EUu mtPxpD42DBctUyW27n8GipPmQFtmRWjvuse4ni3hPku2rADs7i2HBpBXzPYYFT9hH9zZxKqTa7Z 3ege7fLcKY2GGxirUSDUwdNQ94pcw89j9uIsoAmGo3pZLJiiE68WDmFc7Qv+LyCJU7XoAV0IbUT EXvayF8bbOEcWQiahxgUlc2KoRMqM17fXSMavYRP4zrxBHdizOOvxOZlW4Ecmrcv3zhQ9vE55+A 7w3mHw0MX6kW2T1RWdge/xgCOwOwPA9iUgudUUeeMmrxLMFYjbHe5T7MlnpHc7oG3Zgl+CsqJZF G3DEwvSIkCiIo/e7EfdeNl8F5SsIQtgDKMvx+0qsW9PeKCbPfEnOlFFa/HhLGzjsFnMpHwh6kRY O9yzk88gBPbOm0An4Po2uzV0M1WzaP/vKcZsdBx5kAvidso/1etDMdxao2aqZsgsQEtUWR9T X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1099,Hydra:6.1.7,FMLib:17.12.80.40 definitions=2025-07-10_02,2025-07-09_01,2025-03-28_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 priorityscore=1501 mlxlogscore=999 suspectscore=0 clxscore=1015 adultscore=0 lowpriorityscore=0 impostorscore=0 malwarescore=0 bulkscore=0 mlxscore=0 spamscore=0 phishscore=0 classifier=spam authscore=0 authtc=n/a authcc= route=outbound adjust=0 reason=mlx scancount=1 engine=8.19.0-2505280000 definitions=main-2507100101 Content-Type: text/plain; charset="utf-8" Add a function and a command to iterate over radix tree contents. Duplicate the C implementation in Python, but drop support for tagging. Signed-off-by: Ilya Leoshkevich --- scripts/gdb/linux/radixtree.py | 139 +++++++++++++++++++++++++++++++-- 1 file changed, 132 insertions(+), 7 deletions(-) diff --git a/scripts/gdb/linux/radixtree.py b/scripts/gdb/linux/radixtree.py index 074543ac763d..bc2954e45c32 100644 --- a/scripts/gdb/linux/radixtree.py +++ b/scripts/gdb/linux/radixtree.py @@ -30,13 +30,16 @@ def entry_to_node(node): def node_maxindex(node): return (constants.LX_RADIX_TREE_MAP_SIZE << node['shift']) - 1 =20 -def lookup(root, index): +def resolve_root(root): + if root.type =3D=3D radix_tree_root_type.get_type(): + return root if root.type =3D=3D radix_tree_root_type.get_type().pointer(): - node =3D root.dereference() - elif root.type !=3D radix_tree_root_type.get_type(): - raise gdb.GdbError("must be {} not {}" - .format(radix_tree_root_type.get_type(), root.t= ype)) + return root.dereference() + raise gdb.GdbError("must be {} not {}" + .format(radix_tree_root_type.get_type(), root.type)) =20 +def lookup(root, index): + root =3D resolve_root(root) node =3D root['xa_head'] if node =3D=3D 0: return None @@ -71,14 +74,120 @@ def lookup(root, index): =20 return node =20 -class LxRadixTree(gdb.Function): +def descend(parent, index): + offset =3D (index >> int(parent["shift"])) & constants.LX_RADIX_TREE_M= AP_MASK + return offset, parent["slots"][offset] + +def load_root(root): + node =3D root["xa_head"] + nodep =3D node + + if is_internal_node(node): + node =3D entry_to_node(node) + maxindex =3D 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 =3D 0 + self.next_index =3D start + self.node =3D None + +def xa_mk_internal(v): + return (v << 2) | 2 + +LX_XA_RETRY_ENTRY =3D xa_mk_internal(256) +LX_RADIX_TREE_RETRY =3D LX_XA_RETRY_ENTRY + +def next_chunk(root, iter): + mask =3D (1 << (utils.get_ulong_type().sizeof * 8)) - 1 + + index =3D iter.next_index + if index =3D=3D 0 and iter.index !=3D 0: + return None + + restart =3D True + while restart: + restart =3D False + + _, child, maxindex =3D load_root(root) + if index > maxindex: + return None + if not child: + return None + + if not is_internal_node(child): + iter.index =3D index + iter.next_index =3D (maxindex + 1) & mask + iter.node =3D None + return root["xa_head"].address + + while True: + node =3D entry_to_node(child) + offset, child =3D descend(node, index) + + if not child: + while True: + offset +=3D 1 + if offset >=3D constants.LX_RADIX_TREE_MAP_SIZE: + break + slot =3D node["slots"][offset] + if slot: + break + index &=3D ~node_maxindex(node) + index =3D (index + (offset << int(node["shift"]))) & mask + if index =3D=3D 0: + return None + if offset =3D=3D constants.LX_RADIX_TREE_MAP_SIZE: + restart =3D True + break + child =3D node["slots"][offset] + + if not child: + restart =3D True + break + if child =3D=3D LX_XA_RETRY_ENTRY: + break + if not node["shift"] or not is_internal_node(child): + break + + iter.index =3D (index & ~node_maxindex(node)) | offset + iter.next_index =3D ((index | node_maxindex(node)) + 1) & mask + iter.node =3D node + + return node["slots"][offset].address + +def next_slot(slot, iter): + mask =3D (1 << (utils.get_ulong_type().sizeof * 8)) - 1 + for _ in range(iter.next_index - iter.index - 1): + slot +=3D 1 + iter.index =3D (iter.index + 1) & mask + if slot.dereference(): + return slot + return None + +def for_each_slot(root, start=3D0): + iter =3D RadixTreeIter(start) + slot =3D None + while True: + if not slot: + slot =3D next_chunk(root, iter) + if not slot: + break + yield iter.index, slot + slot =3D next_slot(slot, iter) + +class LxRadixTreeLookup(gdb.Function): """ Lookup and return a node from a RadixTree. =20 $lx_radix_tree_lookup(root_node [, index]): Return the node at the given i= ndex. If index is omitted, the root node is dereference and returned.""" =20 def __init__(self): - super(LxRadixTree, self).__init__("lx_radix_tree_lookup") + super(LxRadixTreeLookup, self).__init__("lx_radix_tree_lookup") =20 def invoke(self, root, index=3D0): result =3D lookup(root, index) @@ -87,4 +196,20 @@ If index is omitted, the root node is dereference and r= eturned.""" =20 return result =20 +class LxRadixTree(gdb.Command): + """Show all values stored in a RadixTree.""" + + def __init__(self): + super(LxRadixTree, self).__init__("lx-radix-tree", gdb.COMMAND_DAT= A, + gdb.COMPLETE_NONE) + + def invoke(self, argument, from_tty): + args =3D gdb.string_to_argv(argument) + if len(args) !=3D 1: + raise gdb.GdbError("Usage: lx-radix-tree ROOT") + root =3D gdb.parse_and_eval(args[0]) + for index, slot in for_each_slot(root): + gdb.write("[{}] =3D {}\n".format(index, slot.dereference())) + LxRadixTree() +LxRadixTreeLookup() --=20 2.50.0