1449ca0c9SStephen Boyd# SPDX-License-Identifier: GPL-2.0 2449ca0c9SStephen Boyd# 3449ca0c9SStephen Boyd# Copyright 2019 Google LLC. 4449ca0c9SStephen Boyd 5449ca0c9SStephen Boydimport gdb 6449ca0c9SStephen Boyd 7449ca0c9SStephen Boydfrom linux import utils 8449ca0c9SStephen Boyd 9449ca0c9SStephen Boydrb_root_type = utils.CachedType("struct rb_root") 10449ca0c9SStephen Boydrb_node_type = utils.CachedType("struct rb_node") 11449ca0c9SStephen Boyd 12449ca0c9SStephen Boyd 13449ca0c9SStephen Boyddef rb_first(root): 14449ca0c9SStephen Boyd if root.type == rb_root_type.get_type(): 1550e36be1SAymeric Agon-Rambosson node = root.address.cast(rb_root_type.get_type().pointer()) 16449ca0c9SStephen Boyd elif root.type != rb_root_type.get_type().pointer(): 17449ca0c9SStephen Boyd raise gdb.GdbError("Must be struct rb_root not {}".format(root.type)) 18449ca0c9SStephen Boyd 19449ca0c9SStephen Boyd node = root['rb_node'] 20*a3ec9f38SNick Desaulniers if node == 0: 21449ca0c9SStephen Boyd return None 22449ca0c9SStephen Boyd 23449ca0c9SStephen Boyd while node['rb_left']: 24449ca0c9SStephen Boyd node = node['rb_left'] 25449ca0c9SStephen Boyd 26449ca0c9SStephen Boyd return node 27449ca0c9SStephen Boyd 28449ca0c9SStephen Boyd 29449ca0c9SStephen Boyddef rb_last(root): 30449ca0c9SStephen Boyd if root.type == rb_root_type.get_type(): 3150e36be1SAymeric Agon-Rambosson node = root.address.cast(rb_root_type.get_type().pointer()) 32449ca0c9SStephen Boyd elif root.type != rb_root_type.get_type().pointer(): 33449ca0c9SStephen Boyd raise gdb.GdbError("Must be struct rb_root not {}".format(root.type)) 34449ca0c9SStephen Boyd 35449ca0c9SStephen Boyd node = root['rb_node'] 36*a3ec9f38SNick Desaulniers if node == 0: 37449ca0c9SStephen Boyd return None 38449ca0c9SStephen Boyd 39449ca0c9SStephen Boyd while node['rb_right']: 40449ca0c9SStephen Boyd node = node['rb_right'] 41449ca0c9SStephen Boyd 42449ca0c9SStephen Boyd return node 43449ca0c9SStephen Boyd 44449ca0c9SStephen Boyd 45449ca0c9SStephen Boyddef rb_parent(node): 46449ca0c9SStephen Boyd parent = gdb.Value(node['__rb_parent_color'] & ~3) 47449ca0c9SStephen Boyd return parent.cast(rb_node_type.get_type().pointer()) 48449ca0c9SStephen Boyd 49449ca0c9SStephen Boyd 50449ca0c9SStephen Boyddef rb_empty_node(node): 51449ca0c9SStephen Boyd return node['__rb_parent_color'] == node.address 52449ca0c9SStephen Boyd 53449ca0c9SStephen Boyd 54449ca0c9SStephen Boyddef rb_next(node): 55449ca0c9SStephen Boyd if node.type == rb_node_type.get_type(): 56449ca0c9SStephen Boyd node = node.address.cast(rb_node_type.get_type().pointer()) 57449ca0c9SStephen Boyd elif node.type != rb_node_type.get_type().pointer(): 58449ca0c9SStephen Boyd raise gdb.GdbError("Must be struct rb_node not {}".format(node.type)) 59449ca0c9SStephen Boyd 60449ca0c9SStephen Boyd if rb_empty_node(node): 61449ca0c9SStephen Boyd return None 62449ca0c9SStephen Boyd 63449ca0c9SStephen Boyd if node['rb_right']: 64449ca0c9SStephen Boyd node = node['rb_right'] 65449ca0c9SStephen Boyd while node['rb_left']: 66449ca0c9SStephen Boyd node = node['rb_left'] 67449ca0c9SStephen Boyd return node 68449ca0c9SStephen Boyd 69449ca0c9SStephen Boyd parent = rb_parent(node) 70449ca0c9SStephen Boyd while parent and node == parent['rb_right']: 71449ca0c9SStephen Boyd node = parent 72449ca0c9SStephen Boyd parent = rb_parent(node) 73449ca0c9SStephen Boyd 74449ca0c9SStephen Boyd return parent 75449ca0c9SStephen Boyd 76449ca0c9SStephen Boyd 77449ca0c9SStephen Boyddef rb_prev(node): 78449ca0c9SStephen Boyd if node.type == rb_node_type.get_type(): 79449ca0c9SStephen Boyd node = node.address.cast(rb_node_type.get_type().pointer()) 80449ca0c9SStephen Boyd elif node.type != rb_node_type.get_type().pointer(): 81449ca0c9SStephen Boyd raise gdb.GdbError("Must be struct rb_node not {}".format(node.type)) 82449ca0c9SStephen Boyd 83449ca0c9SStephen Boyd if rb_empty_node(node): 84449ca0c9SStephen Boyd return None 85449ca0c9SStephen Boyd 86449ca0c9SStephen Boyd if node['rb_left']: 87449ca0c9SStephen Boyd node = node['rb_left'] 88449ca0c9SStephen Boyd while node['rb_right']: 89449ca0c9SStephen Boyd node = node['rb_right'] 90449ca0c9SStephen Boyd return node.dereference() 91449ca0c9SStephen Boyd 92449ca0c9SStephen Boyd parent = rb_parent(node) 93449ca0c9SStephen Boyd while parent and node == parent['rb_left'].dereference(): 94449ca0c9SStephen Boyd node = parent 95449ca0c9SStephen Boyd parent = rb_parent(node) 96449ca0c9SStephen Boyd 97449ca0c9SStephen Boyd return parent 98449ca0c9SStephen Boyd 99449ca0c9SStephen Boyd 100449ca0c9SStephen Boydclass LxRbFirst(gdb.Function): 101449ca0c9SStephen Boyd """Lookup and return a node from an RBTree 102449ca0c9SStephen Boyd 103449ca0c9SStephen Boyd$lx_rb_first(root): Return the node at the given index. 104449ca0c9SStephen BoydIf index is omitted, the root node is dereferenced and returned.""" 105449ca0c9SStephen Boyd 106449ca0c9SStephen Boyd def __init__(self): 107449ca0c9SStephen Boyd super(LxRbFirst, self).__init__("lx_rb_first") 108449ca0c9SStephen Boyd 109449ca0c9SStephen Boyd def invoke(self, root): 110449ca0c9SStephen Boyd result = rb_first(root) 111449ca0c9SStephen Boyd if result is None: 112449ca0c9SStephen Boyd raise gdb.GdbError("No entry in tree") 113449ca0c9SStephen Boyd 114449ca0c9SStephen Boyd return result 115449ca0c9SStephen Boyd 116449ca0c9SStephen Boyd 117449ca0c9SStephen BoydLxRbFirst() 118449ca0c9SStephen Boyd 119449ca0c9SStephen Boyd 120449ca0c9SStephen Boydclass LxRbLast(gdb.Function): 121449ca0c9SStephen Boyd """Lookup and return a node from an RBTree. 122449ca0c9SStephen Boyd 123449ca0c9SStephen Boyd$lx_rb_last(root): Return the node at the given index. 124449ca0c9SStephen BoydIf index is omitted, the root node is dereferenced and returned.""" 125449ca0c9SStephen Boyd 126449ca0c9SStephen Boyd def __init__(self): 127449ca0c9SStephen Boyd super(LxRbLast, self).__init__("lx_rb_last") 128449ca0c9SStephen Boyd 129449ca0c9SStephen Boyd def invoke(self, root): 130449ca0c9SStephen Boyd result = rb_last(root) 131449ca0c9SStephen Boyd if result is None: 132449ca0c9SStephen Boyd raise gdb.GdbError("No entry in tree") 133449ca0c9SStephen Boyd 134449ca0c9SStephen Boyd return result 135449ca0c9SStephen Boyd 136449ca0c9SStephen Boyd 137449ca0c9SStephen BoydLxRbLast() 138449ca0c9SStephen Boyd 139449ca0c9SStephen Boyd 140449ca0c9SStephen Boydclass LxRbNext(gdb.Function): 141449ca0c9SStephen Boyd """Lookup and return a node from an RBTree. 142449ca0c9SStephen Boyd 143449ca0c9SStephen Boyd$lx_rb_next(node): Return the node at the given index. 144449ca0c9SStephen BoydIf index is omitted, the root node is dereferenced and returned.""" 145449ca0c9SStephen Boyd 146449ca0c9SStephen Boyd def __init__(self): 147449ca0c9SStephen Boyd super(LxRbNext, self).__init__("lx_rb_next") 148449ca0c9SStephen Boyd 149449ca0c9SStephen Boyd def invoke(self, node): 150449ca0c9SStephen Boyd result = rb_next(node) 151449ca0c9SStephen Boyd if result is None: 152449ca0c9SStephen Boyd raise gdb.GdbError("No entry in tree") 153449ca0c9SStephen Boyd 154449ca0c9SStephen Boyd return result 155449ca0c9SStephen Boyd 156449ca0c9SStephen Boyd 157449ca0c9SStephen BoydLxRbNext() 158449ca0c9SStephen Boyd 159449ca0c9SStephen Boyd 160449ca0c9SStephen Boydclass LxRbPrev(gdb.Function): 161449ca0c9SStephen Boyd """Lookup and return a node from an RBTree. 162449ca0c9SStephen Boyd 163449ca0c9SStephen Boyd$lx_rb_prev(node): Return the node at the given index. 164449ca0c9SStephen BoydIf index is omitted, the root node is dereferenced and returned.""" 165449ca0c9SStephen Boyd 166449ca0c9SStephen Boyd def __init__(self): 167449ca0c9SStephen Boyd super(LxRbPrev, self).__init__("lx_rb_prev") 168449ca0c9SStephen Boyd 169449ca0c9SStephen Boyd def invoke(self, node): 170449ca0c9SStephen Boyd result = rb_prev(node) 171449ca0c9SStephen Boyd if result is None: 172449ca0c9SStephen Boyd raise gdb.GdbError("No entry in tree") 173449ca0c9SStephen Boyd 174449ca0c9SStephen Boyd return result 175449ca0c9SStephen Boyd 176449ca0c9SStephen Boyd 177449ca0c9SStephen BoydLxRbPrev() 178