Commit | Line | Data |
---|---|---|
e127a73d KB |
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() |