Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1757598AbcCCLn6 (ORCPT ); Thu, 3 Mar 2016 06:43:58 -0500 Received: from mail-wm0-f42.google.com ([74.125.82.42]:35228 "EHLO mail-wm0-f42.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750976AbcCCLl2 (ORCPT ); Thu, 3 Mar 2016 06:41:28 -0500 From: Kieran Bingham To: jan.kiszka@siemens.com, linux-kernel@vger.kernel.org Cc: lee.jones@linaro.org, peter.griffin@linaro.org, maxime.coquelin@st.com, Kieran Bingham Subject: [PATCHv3 11/13] scripts/gdb: Add a Radix Tree Parser Date: Thu, 3 Mar 2016 11:41:05 +0000 Message-Id: <1457005267-843-12-git-send-email-kieran.bingham@linaro.org> X-Mailer: git-send-email 2.5.0 In-Reply-To: <1457005267-843-1-git-send-email-kieran.bingham@linaro.org> References: <1457005267-843-1-git-send-email-kieran.bingham@linaro.org> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 3780 Lines: 131 Linux makes use of the Radix Tree data structure to store pointers indexed by integer values. This structure is utilised across many structures in the kernel including the IRQ descriptor tables, and several filesystems. This module provides a method to lookup values from a structure given its head node. Signed-off-by: Kieran Bingham --- scripts/gdb/linux/constants.py.in | 7 +++- scripts/gdb/linux/radixtree.py | 74 +++++++++++++++++++++++++++++++++++++++ scripts/gdb/vmlinux-gdb.py | 1 + 3 files changed, 81 insertions(+), 1 deletion(-) create mode 100644 scripts/gdb/linux/radixtree.py diff --git a/scripts/gdb/linux/constants.py.in b/scripts/gdb/linux/constants.py.in index 66562a8242bd..b38b9085c702 100644 --- a/scripts/gdb/linux/constants.py.in +++ b/scripts/gdb/linux/constants.py.in @@ -21,7 +21,7 @@ #include #include #include - +#include /* We need to stringify expanded macros so that they can be parsed */ @@ -71,6 +71,11 @@ LX_GDBPARSED(VMALLOC_TOTAL) /* linux/swap.h */ LX_GDBPARSED(MAX_SWAPFILES) +/* linux/radix-tree.h */ +LX_VALUE(RADIX_TREE_INDIRECT_PTR) +LX_GDBPARSED(RADIX_TREE_HEIGHT_MASK) +LX_GDBPARSED(RADIX_TREE_MAP_SHIFT) +LX_GDBPARSED(RADIX_TREE_MAP_MASK) /* Kernel Configs */ LX_CONFIG(CONFIG_HIGHMEM) diff --git a/scripts/gdb/linux/radixtree.py b/scripts/gdb/linux/radixtree.py new file mode 100644 index 000000000000..299d171e3571 --- /dev/null +++ b/scripts/gdb/linux/radixtree.py @@ -0,0 +1,74 @@ +# +# gdb helper commands and functions for Linux kernel debugging +# +# Radix Tree Parser +# +# Copyright (c) 2016 Linaro Ltd +# +# Authors: +# Kieran Bingham +# +# This work is licensed under the terms of the GNU GPL version 2. +# + +import gdb + +from linux import utils +from linux import constants + +radix_tree_root_type = utils.CachedType("struct radix_tree_root") +radix_tree_node_type = utils.CachedType("struct radix_tree_node") + + +def is_indirect_ptr(node): + long_type = utils.get_long_type() + return (node.cast(long_type) & constants.LX_RADIX_TREE_INDIRECT_PTR) + + +def indirect_to_ptr(node): + long_type = utils.get_long_type() + node_type = node.type + indirect_ptr = node.cast(long_type) & ~constants.LX_RADIX_TREE_INDIRECT_PTR + return indirect_ptr.cast(node_type) + + +def maxindex(height): + height = height & constants.LX_RADIX_TREE_HEIGHT_MASK + return gdb.parse_and_eval("height_to_maxindex["+str(height)+"]") + + +def lookup(root, index): + node = root['rnode'] + if node is 0: + return None + + if not (is_indirect_ptr(node)): + if (index > 0): + return None + return node + + node = indirect_to_ptr(node) + + height = node['path'] & constants.LX_RADIX_TREE_HEIGHT_MASK + if (index > maxindex(height)): + return None + + shift = (height-1) * constants.LX_RADIX_TREE_MAP_SHIFT + + while True: + new_index = (index >> shift) & constants.LX_RADIX_TREE_MAP_MASK + slot = node['slots'][new_index] + + # Below needs a bit more verification ... + # node = rcu_dereference_raw(*slot); + node = slot.cast(node.type.pointer()).dereference() + if node is 0: + return None + + shift -= constants.LX_RADIX_TREE_MAP_SHIFT + height -= 1 + + if (height <= 0): + break + + return node diff --git a/scripts/gdb/vmlinux-gdb.py b/scripts/gdb/vmlinux-gdb.py index 6e0b0afd888a..3a80ad6eecad 100644 --- a/scripts/gdb/vmlinux-gdb.py +++ b/scripts/gdb/vmlinux-gdb.py @@ -31,3 +31,4 @@ else: import linux.lists import linux.proc import linux.constants + import linux.radixtree -- 2.5.0