1 # SPDX-License-Identifier: GPL-2.0 1 # SPDX-License-Identifier: GPL-2.0
2 # 2 #
3 # Copyright 2019 Google LLC. 3 # Copyright 2019 Google LLC.
4 4
5 import gdb 5 import gdb
6 6
7 from linux import utils 7 from linux import utils
8 8
9 rb_root_type = utils.CachedType("struct rb_roo 9 rb_root_type = utils.CachedType("struct rb_root")
10 rb_node_type = utils.CachedType("struct rb_nod 10 rb_node_type = utils.CachedType("struct rb_node")
11 11
12 def rb_inorder_for_each(root): <<
13 def inorder(node): <<
14 if node: <<
15 yield from inorder(node['rb_left'] <<
16 yield node <<
17 yield from inorder(node['rb_right' <<
18 <<
19 yield from inorder(root['rb_node']) <<
20 <<
21 def rb_inorder_for_each_entry(root, gdbtype, m <<
22 for node in rb_inorder_for_each(root): <<
23 yield utils.container_of(node, gdbtype <<
24 12
25 def rb_first(root): 13 def rb_first(root):
26 if root.type == rb_root_type.get_type(): 14 if root.type == rb_root_type.get_type():
27 node = root.address.cast(rb_root_type. 15 node = root.address.cast(rb_root_type.get_type().pointer())
28 elif root.type != rb_root_type.get_type(). 16 elif root.type != rb_root_type.get_type().pointer():
29 raise gdb.GdbError("Must be struct rb_ 17 raise gdb.GdbError("Must be struct rb_root not {}".format(root.type))
30 18
31 node = root['rb_node'] 19 node = root['rb_node']
32 if node == 0: 20 if node == 0:
33 return None 21 return None
34 22
35 while node['rb_left']: 23 while node['rb_left']:
36 node = node['rb_left'] 24 node = node['rb_left']
37 25
38 return node 26 return node
39 27
40 28
41 def rb_last(root): 29 def rb_last(root):
42 if root.type == rb_root_type.get_type(): 30 if root.type == rb_root_type.get_type():
43 node = root.address.cast(rb_root_type. 31 node = root.address.cast(rb_root_type.get_type().pointer())
44 elif root.type != rb_root_type.get_type(). 32 elif root.type != rb_root_type.get_type().pointer():
45 raise gdb.GdbError("Must be struct rb_ 33 raise gdb.GdbError("Must be struct rb_root not {}".format(root.type))
46 34
47 node = root['rb_node'] 35 node = root['rb_node']
48 if node == 0: 36 if node == 0:
49 return None 37 return None
50 38
51 while node['rb_right']: 39 while node['rb_right']:
52 node = node['rb_right'] 40 node = node['rb_right']
53 41
54 return node 42 return node
55 43
56 44
57 def rb_parent(node): 45 def rb_parent(node):
58 parent = gdb.Value(node['__rb_parent_color 46 parent = gdb.Value(node['__rb_parent_color'] & ~3)
59 return parent.cast(rb_node_type.get_type() 47 return parent.cast(rb_node_type.get_type().pointer())
60 48
61 49
62 def rb_empty_node(node): 50 def rb_empty_node(node):
63 return node['__rb_parent_color'] == node.a 51 return node['__rb_parent_color'] == node.address
64 52
65 53
66 def rb_next(node): 54 def rb_next(node):
67 if node.type == rb_node_type.get_type(): 55 if node.type == rb_node_type.get_type():
68 node = node.address.cast(rb_node_type. 56 node = node.address.cast(rb_node_type.get_type().pointer())
69 elif node.type != rb_node_type.get_type(). 57 elif node.type != rb_node_type.get_type().pointer():
70 raise gdb.GdbError("Must be struct rb_ 58 raise gdb.GdbError("Must be struct rb_node not {}".format(node.type))
71 59
72 if rb_empty_node(node): 60 if rb_empty_node(node):
73 return None 61 return None
74 62
75 if node['rb_right']: 63 if node['rb_right']:
76 node = node['rb_right'] 64 node = node['rb_right']
77 while node['rb_left']: 65 while node['rb_left']:
78 node = node['rb_left'] 66 node = node['rb_left']
79 return node 67 return node
80 68
81 parent = rb_parent(node) 69 parent = rb_parent(node)
82 while parent and node == parent['rb_right' 70 while parent and node == parent['rb_right']:
83 node = parent 71 node = parent
84 parent = rb_parent(node) 72 parent = rb_parent(node)
85 73
86 return parent 74 return parent
87 75
88 76
89 def rb_prev(node): 77 def rb_prev(node):
90 if node.type == rb_node_type.get_type(): 78 if node.type == rb_node_type.get_type():
91 node = node.address.cast(rb_node_type. 79 node = node.address.cast(rb_node_type.get_type().pointer())
92 elif node.type != rb_node_type.get_type(). 80 elif node.type != rb_node_type.get_type().pointer():
93 raise gdb.GdbError("Must be struct rb_ 81 raise gdb.GdbError("Must be struct rb_node not {}".format(node.type))
94 82
95 if rb_empty_node(node): 83 if rb_empty_node(node):
96 return None 84 return None
97 85
98 if node['rb_left']: 86 if node['rb_left']:
99 node = node['rb_left'] 87 node = node['rb_left']
100 while node['rb_right']: 88 while node['rb_right']:
101 node = node['rb_right'] 89 node = node['rb_right']
102 return node.dereference() 90 return node.dereference()
103 91
104 parent = rb_parent(node) 92 parent = rb_parent(node)
105 while parent and node == parent['rb_left'] 93 while parent and node == parent['rb_left'].dereference():
106 node = parent 94 node = parent
107 parent = rb_parent(node) 95 parent = rb_parent(node)
108 96
109 return parent 97 return parent
110 98
111 99
112 class LxRbFirst(gdb.Function): 100 class LxRbFirst(gdb.Function):
113 """Lookup and return a node from an RBTree 101 """Lookup and return a node from an RBTree
114 102
115 $lx_rb_first(root): Return the node at the giv 103 $lx_rb_first(root): Return the node at the given index.
116 If index is omitted, the root node is derefere 104 If index is omitted, the root node is dereferenced and returned."""
117 105
118 def __init__(self): 106 def __init__(self):
119 super(LxRbFirst, self).__init__("lx_rb 107 super(LxRbFirst, self).__init__("lx_rb_first")
120 108
121 def invoke(self, root): 109 def invoke(self, root):
122 result = rb_first(root) 110 result = rb_first(root)
123 if result is None: 111 if result is None:
124 raise gdb.GdbError("No entry in tr 112 raise gdb.GdbError("No entry in tree")
125 113
126 return result 114 return result
127 115
128 116
129 LxRbFirst() 117 LxRbFirst()
130 118
131 119
132 class LxRbLast(gdb.Function): 120 class LxRbLast(gdb.Function):
133 """Lookup and return a node from an RBTree 121 """Lookup and return a node from an RBTree.
134 122
135 $lx_rb_last(root): Return the node at the give 123 $lx_rb_last(root): Return the node at the given index.
136 If index is omitted, the root node is derefere 124 If index is omitted, the root node is dereferenced and returned."""
137 125
138 def __init__(self): 126 def __init__(self):
139 super(LxRbLast, self).__init__("lx_rb_ 127 super(LxRbLast, self).__init__("lx_rb_last")
140 128
141 def invoke(self, root): 129 def invoke(self, root):
142 result = rb_last(root) 130 result = rb_last(root)
143 if result is None: 131 if result is None:
144 raise gdb.GdbError("No entry in tr 132 raise gdb.GdbError("No entry in tree")
145 133
146 return result 134 return result
147 135
148 136
149 LxRbLast() 137 LxRbLast()
150 138
151 139
152 class LxRbNext(gdb.Function): 140 class LxRbNext(gdb.Function):
153 """Lookup and return a node from an RBTree 141 """Lookup and return a node from an RBTree.
154 142
155 $lx_rb_next(node): Return the node at the give 143 $lx_rb_next(node): Return the node at the given index.
156 If index is omitted, the root node is derefere 144 If index is omitted, the root node is dereferenced and returned."""
157 145
158 def __init__(self): 146 def __init__(self):
159 super(LxRbNext, self).__init__("lx_rb_ 147 super(LxRbNext, self).__init__("lx_rb_next")
160 148
161 def invoke(self, node): 149 def invoke(self, node):
162 result = rb_next(node) 150 result = rb_next(node)
163 if result is None: 151 if result is None:
164 raise gdb.GdbError("No entry in tr 152 raise gdb.GdbError("No entry in tree")
165 153
166 return result 154 return result
167 155
168 156
169 LxRbNext() 157 LxRbNext()
170 158
171 159
172 class LxRbPrev(gdb.Function): 160 class LxRbPrev(gdb.Function):
173 """Lookup and return a node from an RBTree 161 """Lookup and return a node from an RBTree.
174 162
175 $lx_rb_prev(node): Return the node at the give 163 $lx_rb_prev(node): Return the node at the given index.
176 If index is omitted, the root node is derefere 164 If index is omitted, the root node is dereferenced and returned."""
177 165
178 def __init__(self): 166 def __init__(self):
179 super(LxRbPrev, self).__init__("lx_rb_ 167 super(LxRbPrev, self).__init__("lx_rb_prev")
180 168
181 def invoke(self, node): 169 def invoke(self, node):
182 result = rb_prev(node) 170 result = rb_prev(node)
183 if result is None: 171 if result is None:
184 raise gdb.GdbError("No entry in tr 172 raise gdb.GdbError("No entry in tree")
185 173
186 return result 174 return result
187 175
188 176
189 LxRbPrev() 177 LxRbPrev()
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.