lkml.org 
[lkml]   [2019]   [Mar]   [25]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH 3/4] scripts/gdb: Add rb tree iterating utilities
    Date
    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.

    Cc: Douglas Anderson <dianders@chromium.org>
    Cc: Nikolay Borisov <n.borisov.lkml@gmail.com>
    Cc: Kieran Bingham <kbingham@kernel.org>
    Cc: Jan Kiszka <jan.kiszka@siemens.com>
    Cc: Jackie Liu <liuyun01@kylinos.cn>
    Signed-off-by: Stephen Boyd <swboyd@chromium.org>
    ---
    scripts/gdb/linux/rbtree.py | 169 ++++++++++++++++++++++++++++++++++++
    scripts/gdb/vmlinux-gdb.py | 1 +
    2 files changed, 170 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..fd7b0b961ca1
    --- /dev/null
    +++ b/scripts/gdb/linux/rbtree.py
    @@ -0,0 +1,169 @@
    +# 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
    --
    Sent by a computer through tubes
    \
     
     \ /
      Last update: 2019-03-25 19:46    [W:4.237 / U:1.028 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site