lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date:   Tue, 26 Mar 2019 08:52:10 +0000
From:   Kieran Bingham <kbingham@...nel.org>
To:     Stephen Boyd <swboyd@...omium.org>,
        Andrew Morton <akpm@...ux-foundation.org>
Cc:     linux-kernel@...r.kernel.org,
        Masahiro Yamada <yamada.masahiro@...ionext.com>,
        Douglas Anderson <dianders@...omium.org>,
        Nikolay Borisov <n.borisov.lkml@...il.com>,
        Jan Kiszka <jan.kiszka@...mens.com>,
        Jackie Liu <liuyun01@...inos.cn>
Subject: Re: [PATCH 3/4] scripts/gdb: Add rb tree iterating utilities

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@...ux-foundation.org> (commit_signer:3/2=100%,commit_signer:2/1=100%)
> Sebastian Andrzej Siewior <bigeasy@...utronix.de> (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@...il.com> (commit_signer:1/2=50%,authored:1/2=50%,added_lines:2/3=67%,removed_lines:2/2=100%)
> linux-kernel@...r.kernel.org (open list)

--
Regards

Kieran


> 
> Cc: Douglas Anderson <dianders@...omium.org>
> Cc: Nikolay Borisov <n.borisov.lkml@...il.com>
> Cc: Kieran Bingham <kbingham@...nel.org>
> Cc: Jan Kiszka <jan.kiszka@...mens.com>
> Cc: Jackie Liu <liuyun01@...inos.cn> 
> Signed-off-by: Stephen Boyd <swboyd@...omium.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
> 


-- 
--
Kieran

Powered by blists - more mailing lists