From patchwork Wed Mar 30 12:00:49 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kieran Bingham X-Patchwork-Id: 64692 Delivered-To: patch@linaro.org Received: by 10.112.199.169 with SMTP id jl9csp2550648lbc; Wed, 30 Mar 2016 05:02:28 -0700 (PDT) X-Received: by 10.66.118.106 with SMTP id kl10mr12382509pab.78.1459339347992; Wed, 30 Mar 2016 05:02:27 -0700 (PDT) Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id c17si6120396pfd.70.2016.03.30.05.02.27; Wed, 30 Mar 2016 05:02:27 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE dis=NONE) header.from=linaro.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753369AbcC3MCH (ORCPT + 29 others); Wed, 30 Mar 2016 08:02:07 -0400 Received: from mail-wm0-f46.google.com ([74.125.82.46]:38313 "EHLO mail-wm0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752960AbcC3MBR (ORCPT ); Wed, 30 Mar 2016 08:01:17 -0400 Received: by mail-wm0-f46.google.com with SMTP id 20so67578421wmh.1 for ; Wed, 30 Mar 2016 05:01:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=5pyFVrWl5llsZJmagsJGzJonbORDquuAxpbB2cNTjtc=; b=G+rhAY6IAr/tb8YBdHO+p485thsw0SJ562286s3sAcGhLUdpPs8XX0S4XWp+z73T3e zjPOfckPc1JGQkoIatywHVsM/hfEaxgxomFnoxBkkSix9DbH8LL/xKVQ4hIZG8zBzTdx JBG+RrR6uSCGbUwLh1QOP3g9+mmu375CqcJjY= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=5pyFVrWl5llsZJmagsJGzJonbORDquuAxpbB2cNTjtc=; b=jUhP8T/obKKR+SghPQmpR1cPWQJJ1w/T4ENchHpDpT0JjDMMJX47guqn5z3Mhr+ieK sjLdHPmRzVlh2m2jbHMIOvs5AEI+Mj7jp9r+3EjU+oZgkCkGI3crMRL36SyR3L4lPlVc lGQPOvuPFkWksFV8LxXfeaQAUyr8GGanm6V2Gex+aIVCRRwWoJCVSZdg5h92ucaGoRXr srnvsm+kUtHnWyIQ0J8tMTBsSgzt+stkA6K2BOk9lMbYVNzAg2axF4iKu893z497AeA3 oPAKkOPLuVzI9LQoAwZQE+1+Me7tXVlBWKwaNUryLWFWA7+CgW4BMAtgNCSCqj69vIs5 Azow== X-Gm-Message-State: AD7BkJIM2KNikw1lwrWN/qxUKrwdWlB6njgEwNKA5fXt8dkyg/i8fq06YnZ7C9xsAHZ7iwY9 X-Received: by 10.194.190.6 with SMTP id gm6mr9162495wjc.115.1459339275830; Wed, 30 Mar 2016 05:01:15 -0700 (PDT) Received: from localhost.localdomain (cpc87017-aztw30-2-0-cust65.18-1.cable.virginm.net. [92.232.232.66]) by smtp.gmail.com with ESMTPSA id e190sm1175530wma.15.2016.03.30.05.01.15 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 30 Mar 2016 05:01:15 -0700 (PDT) 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: [PATCHv4 10/12] scripts/gdb: Add a Radix Tree Parser Date: Wed, 30 Mar 2016 13:00:49 +0100 Message-Id: <1459339251-29611-11-git-send-email-kieran.bingham@linaro.org> X-Mailer: git-send-email 2.5.0 In-Reply-To: <1459339251-29611-1-git-send-email-kieran.bingham@linaro.org> References: <1459339251-29611-1-git-send-email-kieran.bingham@linaro.org> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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. Usage: The function lx_radix_tree_lookup, must be given a symbol of type struct radix_tree_root, and an index into that tree. The object returned is a generic integer value, and must be cast correctly to the type based on the storage in the data structure. For example, to print the irq descriptor in the sparse irq_desc_tree at index 18, try the following: (gdb) print (struct irq_desc)$lx_radix_tree_lookup(irq_desc_tree, 18) Signed-off-by: Kieran Bingham --- Changes since v3: - Added a lookup function helper - Provide type checking on lookup() - Remove outdated comment regarding RCU dereference --- scripts/gdb/linux/constants.py.in | 6 +++ scripts/gdb/linux/radixtree.py | 97 +++++++++++++++++++++++++++++++++++++++ scripts/gdb/vmlinux-gdb.py | 1 + 3 files changed, 104 insertions(+) create mode 100644 scripts/gdb/linux/radixtree.py -- 2.5.0 diff --git a/scripts/gdb/linux/constants.py.in b/scripts/gdb/linux/constants.py.in index 57213ad8cf75..07e6c2befe36 100644 --- a/scripts/gdb/linux/constants.py.in +++ b/scripts/gdb/linux/constants.py.in @@ -14,6 +14,7 @@ #include #include +#include /* We need to stringify expanded macros so that they can be parsed */ @@ -51,3 +52,8 @@ LX_VALUE(MNT_NOATIME) LX_VALUE(MNT_NODIRATIME) LX_VALUE(MNT_RELATIME) +/* 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) diff --git a/scripts/gdb/linux/radixtree.py b/scripts/gdb/linux/radixtree.py new file mode 100644 index 000000000000..0fdef4e2971a --- /dev/null +++ b/scripts/gdb/linux/radixtree.py @@ -0,0 +1,97 @@ +# +# 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): + if root.type == radix_tree_root_type.get_type().pointer(): + root = root.dereference() + elif root.type != radix_tree_root_type.get_type(): + raise gdb.GdbError("Must be struct radix_tree_root not {}" + .format(root.type)) + + 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] + + 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 + + +class LxRadixTree(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 dereferenced and returned.""" + + def __init__(self): + super(LxRadixTree, 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 + +LxRadixTree() 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