From patchwork Thu Mar 3 11:41:05 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kieran Bingham X-Patchwork-Id: 63466 Delivered-To: patch@linaro.org Received: by 10.112.199.169 with SMTP id jl9csp2895087lbc; Thu, 3 Mar 2016 03:44:00 -0800 (PST) X-Received: by 10.66.102.70 with SMTP id fm6mr2925575pab.98.1457005440831; Thu, 03 Mar 2016 03:44:00 -0800 (PST) Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id f10si65161127pfd.188.2016.03.03.03.44.00; Thu, 03 Mar 2016 03:44:00 -0800 (PST) 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; 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; dkim=pass header.i=@linaro.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1757599AbcCCLn6 (ORCPT + 30 others); 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 Received: by mail-wm0-f42.google.com with SMTP id l68so127171092wml.0 for ; Thu, 03 Mar 2016 03:41:28 -0800 (PST) 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=MeWqBELdepprB6ficIKN1uOmNAECisBvfA1LXo8fGLc=; b=J4r9zCuJlZTY3dEscrVZpm4iWdsLnzVNrI4UtLDHDm4LcuLpA5wNPqvYpyn3W3IcPs y08D5oDcvRG4qCsgWXLc9b37AC/qyNo7IM8kMK9IxtHJwFRTWxeROJE4dQ0QPOqHFpFo kCXkUU8U9gJWGg514TH1Vr0uVWyvKN/V50SWc= 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=MeWqBELdepprB6ficIKN1uOmNAECisBvfA1LXo8fGLc=; b=Cehv1GI4DRwlsYhALOWWHI053tAPOSJEJDnYfcUq1gT4ytgbr7GmvgUIhoMkIftz5g +ASH5xZJuBHtCsmuxnORJd1BBSi7azgGSiaLICkWQGxxcUv8IfEdbGULucF34efCEOf6 HNpAAL7b+RrONqmm3BbJZKKMNX5ZPVWz9DUUJ4TCLwDQnQeeO3cUPifPwpPtQyrd4jfs X3BgpBRSWCaYTaao4PJoFCZa3Crt7zyzyONKonCKZTVXy9Vnan5ggoCWX6mfQMMy4R1a NHbUybk5e7sAVHXXSVeNs7zcq4khp5wAdsT0Ty7JXqFC+s64lxlNm4ZvZ33O8qd2HRkt RaVg== X-Gm-Message-State: AD7BkJIyddPmMngUWz82qtbtJSLCqXLFKkVtxnOTWjIW8ub0HfaK+8l2zANX2YXJj71H9PTE X-Received: by 10.28.184.78 with SMTP id i75mr3096694wmf.22.1457005287434; Thu, 03 Mar 2016 03:41:27 -0800 (PST) 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 e19sm8570696wmd.1.2016.03.03.03.41.26 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Thu, 03 Mar 2016 03:41:27 -0800 (PST) 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 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. 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 -- 2.5.0 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