From 449ca0c95ea261f27b7efd4ca3970a5b4e0fd30d Mon Sep 17 00:00:00 2001 From: Stephen Boyd Date: Tue, 14 May 2019 15:45:56 -0700 Subject: scripts/gdb: add rb tree iterating utilities Implement gdb functions for rb_first(), rb_last(), rb_next(), and rb_prev(). These can be useful to iterate through the kernel's red-black trees. [swboyd@chromium.org: v2] Link: http://lkml.kernel.org/r/20190329220844.38234-4-swboyd@chromium.org Link: http://lkml.kernel.org/r/20190325184522.260535-4-swboyd@chromium.org Signed-off-by: Stephen Boyd Cc: Douglas Anderson Cc: Nikolay Borisov Cc: Kieran Bingham Cc: Jan Kiszka Cc: Jackie Liu Cc: Jason Wessel Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- scripts/gdb/linux/rbtree.py | 177 ++++++++++++++++++++++++++++++++++++++++++++ scripts/gdb/vmlinux-gdb.py | 1 + 2 files changed, 178 insertions(+) create mode 100644 scripts/gdb/linux/rbtree.py diff --git a/scripts/gdb/linux/rbtree.py b/scripts/gdb/linux/rbtree.py new file mode 100644 index 000000000000..39db889b874c --- /dev/null +++ b/scripts/gdb/linux/rbtree.py @@ -0,0 +1,177 @@ +# SPDX-License-Identifier: GPL-2.0 +# +# Copyright 2019 Google LLC. + +import gdb + +from linux import utils + +rb_root_type = utils.CachedType("struct rb_root") +rb_node_type = utils.CachedType("struct rb_node") + + +def rb_first(root): + if root.type == rb_root_type.get_type(): + node = node.address.cast(rb_root_type.get_type().pointer()) + elif root.type != rb_root_type.get_type().pointer(): + raise gdb.GdbError("Must be struct rb_root not {}".format(root.type)) + + node = root['rb_node'] + if node is 0: + return None + + while node['rb_left']: + node = node['rb_left'] + + return node + + +def rb_last(root): + if root.type == rb_root_type.get_type(): + node = node.address.cast(rb_root_type.get_type().pointer()) + elif root.type != rb_root_type.get_type().pointer(): + raise gdb.GdbError("Must be struct rb_root not {}".format(root.type)) + + node = root['rb_node'] + if node is 0: + return None + + while node['rb_right']: + node = node['rb_right'] + + return node + + +def rb_parent(node): + parent = gdb.Value(node['__rb_parent_color'] & ~3) + return parent.cast(rb_node_type.get_type().pointer()) + + +def rb_empty_node(node): + return node['__rb_parent_color'] == node.address + + +def rb_next(node): + if node.type == rb_node_type.get_type(): + node = node.address.cast(rb_node_type.get_type().pointer()) + elif node.type != rb_node_type.get_type().pointer(): + raise gdb.GdbError("Must be struct rb_node not {}".format(node.type)) + + if rb_empty_node(node): + return None + + if node['rb_right']: + node = node['rb_right'] + while node['rb_left']: + node = node['rb_left'] + return node + + parent = rb_parent(node) + while parent and node == parent['rb_right']: + node = parent + parent = rb_parent(node) + + return parent + + +def rb_prev(node): + if node.type == rb_node_type.get_type(): + node = node.address.cast(rb_node_type.get_type().pointer()) + elif node.type != rb_node_type.get_type().pointer(): + raise gdb.GdbError("Must be struct rb_node not {}".format(node.type)) + + if rb_empty_node(node): + return None + + if node['rb_left']: + node = node['rb_left'] + while node['rb_right']: + node = node['rb_right'] + return node.dereference() + + parent = rb_parent(node) + while parent and node == parent['rb_left'].dereference(): + node = parent + parent = rb_parent(node) + + return parent + + +class LxRbFirst(gdb.Function): + """Lookup and return a node from an RBTree + +$lx_rb_first(root): Return the node at the given index. +If index is omitted, the root node is dereferenced and returned.""" + + def __init__(self): + super(LxRbFirst, self).__init__("lx_rb_first") + + def invoke(self, root): + result = rb_first(root) + if result is None: + raise gdb.GdbError("No entry in tree") + + return result + + +LxRbFirst() + + +class LxRbLast(gdb.Function): + """Lookup and return a node from an RBTree. + +$lx_rb_last(root): Return the node at the given index. +If index is omitted, the root node is dereferenced and returned.""" + + def __init__(self): + super(LxRbLast, self).__init__("lx_rb_last") + + def invoke(self, root): + result = rb_last(root) + if result is None: + raise gdb.GdbError("No entry in tree") + + return result + + +LxRbLast() + + +class LxRbNext(gdb.Function): + """Lookup and return a node from an RBTree. + +$lx_rb_next(node): Return the node at the given index. +If index is omitted, the root node is dereferenced and returned.""" + + def __init__(self): + super(LxRbNext, self).__init__("lx_rb_next") + + def invoke(self, node): + result = rb_next(node) + if result is None: + raise gdb.GdbError("No entry in tree") + + return result + + +LxRbNext() + + +class LxRbPrev(gdb.Function): + """Lookup and return a node from an RBTree. + +$lx_rb_prev(node): Return the node at the given index. +If index is omitted, the root node is dereferenced and returned.""" + + def __init__(self): + super(LxRbPrev, self).__init__("lx_rb_prev") + + def invoke(self, node): + result = rb_prev(node) + if result is None: + raise gdb.GdbError("No entry in tree") + + return result + + +LxRbPrev() diff --git a/scripts/gdb/vmlinux-gdb.py b/scripts/gdb/vmlinux-gdb.py index be0efb5dda5b..89e4aa4f8966 100644 --- a/scripts/gdb/vmlinux-gdb.py +++ b/scripts/gdb/vmlinux-gdb.py @@ -30,5 +30,6 @@ else: import linux.config import linux.cpus import linux.lists + import linux.rbtree import linux.proc import linux.constants -- cgit v1.2.3