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