scripts/gdb/linux/rbtree.py

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