Kieran Bingham | e127a73 | 2016-05-23 16:25:07 -0700 | [diff] [blame^] | 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() |