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