scripts/gdb/linux/radixtree.py

   1 #
   2 # gdb helper commands and functions for Linux kernel debugging
   3 #
   4 #  Radix Tree Parser
   5 #
   6 # Copyright (c) 2016 Linaro Ltd
   7 #
   8 # Authors:
   9 #  Kieran Bingham <kieran.bingham@linaro.org>
  10 #
  11 # This work is licensed under the terms of the GNU GPL version 2.
  12 #
  13
  14 import gdb
  15
  16 from linux import utils
  17 from linux import constants
  18
  19 radix_tree_root_type = utils.CachedType("struct radix_tree_root")
  20 radix_tree_node_type = utils.CachedType("struct radix_tree_node")
  21
  22
  23 def is_indirect_ptr(node):
  24     long_type = utils.get_long_type()
  25     return (node.cast(long_type) & constants.LX_RADIX_TREE_INDIRECT_PTR)
  26
  27
  28 def indirect_to_ptr(node):
  29     long_type = utils.get_long_type()
  30     node_type = node.type
  31     indirect_ptr = node.cast(long_type) & ~constants.LX_RADIX_TREE_INDIRECT_PTR
  32     return indirect_ptr.cast(node_type)
  33
  34
  35 def maxindex(height):
  36     height = height & constants.LX_RADIX_TREE_HEIGHT_MASK
  37     return gdb.parse_and_eval("height_to_maxindex["+str(height)+"]")
  38
  39
  40 def lookup(root, index):
  41     if root.type == radix_tree_root_type.get_type().pointer():
  42         root = root.dereference()
  43     elif root.type != radix_tree_root_type.get_type():
  44         raise gdb.GdbError("Must be struct radix_tree_root not {}"
  45                            .format(root.type))
  46
  47     node = root['rnode']
  48     if node is 0:
  49         return None
  50
  51     if not (is_indirect_ptr(node)):
  52         if (index > 0):
  53             return None
  54         return node
  55
  56     node = indirect_to_ptr(node)
  57
  58     height = node['path'] & constants.LX_RADIX_TREE_HEIGHT_MASK
  59     if (index > maxindex(height)):
  60         return None
  61
  62     shift = (height-1) * constants.LX_RADIX_TREE_MAP_SHIFT
  63
  64     while True:
  65         new_index = (index >> shift) & constants.LX_RADIX_TREE_MAP_MASK
  66         slot = node['slots'][new_index]
  67
  68         node = slot.cast(node.type.pointer()).dereference()
  69         if node is 0:
  70             return None
  71
  72         shift -= constants.LX_RADIX_TREE_MAP_SHIFT
  73         height -= 1
  74
  75         if (height <= 0):
  76             break
  77
  78     return node
  79
  80
  81 class LxRadixTree(gdb.Function):
  82     """ Lookup and return a node from a RadixTree.
  83
  84 $lx_radix_tree_lookup(root_node [, index]): Return the node at the given index.
  85 If index is omitted, the root node is dereferenced and returned."""
  86
  87     def __init__(self):
  88         super(LxRadixTree, self).__init__("lx_radix_tree_lookup")
  89
  90     def invoke(self, root, index=0):
  91         result = lookup(root, index)
  92         if result is None:
  93             raise gdb.GdbError("No entry in tree at index {}".format(index))
  94
  95         return result
  96
  97 LxRadixTree()