Re: [PATCH 3/4] scripts/gdb: Add rb tree iterating utilities

[Kieran Bingham]

Hi Stephen,

On 25/03/2019 18:45, Stephen Boyd wrote:
> 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.

I definitely approve of getting data-structure helpers into scripts/gdb,
as it will greatly assist debug options but my last attempt to do this
was with the radix-tree which I had to give up on as the internals were
changing rapidly and caused continuous breakage to the helpers.

Do you foresee any similar issue here? Or is the corresponding RB code
in the kernel fairly 'stable'?


Please could we make sure whomever maintains the RBTree code is aware of
the python implementation?

That said, MAINTAINERS doesn't actually seem to list any ownership over
the rb-tree code, and get_maintainers.pl [0] seems to be pointing at
Andrew as the probable route in for that code so perhaps that's already
in place :D



[0]
> ./scripts/get_maintainer.pl -f ./include/linux/rbtree*
> Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx> (commit_signer:3/2=100%,commit_signer:2/1=100%)
> Sebastian Andrzej Siewior <bigeasy@xxxxxxxxxxxxx> (commit_signer:1/2=50%,authored:1/2=50%,added_lines:1/3=33%,commit_signer:1/1=100%,authored:1/1=100%,added_lines:1/1=100%)
> Wei Yang <richard.weiyang@xxxxxxxxx> (commit_signer:1/2=50%,authored:1/2=50%,added_lines:2/3=67%,removed_lines:2/2=100%)
> linux-kernel@xxxxxxxxxxxxxxx (open list)

--
Regards

Kieran


> 
> Cc: Douglas Anderson <dianders@xxxxxxxxxxxx>
> Cc: Nikolay Borisov <n.borisov.lkml@xxxxxxxxx>
> Cc: Kieran Bingham <kbingham@xxxxxxxxxx>
> Cc: Jan Kiszka <jan.kiszka@xxxxxxxxxxx>
> Cc: Jackie Liu <liuyun01@xxxxxxxxxx> 
> Signed-off-by: Stephen Boyd <swboyd@xxxxxxxxxxxx>
> ---
>  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
> 


-- 
--
Kieran