| 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 linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Sat, 24 Jan 2009 17:53:57 +0100
From: "Wolfram Strepp" <wstrepp@....de>
To: Peter Zijlstra <peterz@...radead.org>
Cc: linux-kernel@...r.kernel.org, dwmw2@...radead.org,
akpm@...ux-foundation.org
Subject: Re: [PATCH 2/2] Optimization of function rb_erase() in lib/rbtree.c
Hello Peter,
> On Tue, 2009-01-20 at 22:58 +0100, Wolfram Strepp wrote:
> > This patch reorganizes some lines, and therefore one if-condition
> > can be omitted. Here an explanation.
> OK, this patch is better done in smaller steps.
>
> I'll have to admit to not having tested any of the below patches, but
> they represent how I went about understanding your patch.
>
> ---
> Subject: rbtree: code movement
> From: Peter Zijlstra <a.p.zijlstra@...llo.nl>
> Date: Sat Jan 24 13:14:11 CET 2009
>
> Move some code around in order to make the next change more obvious.
>
> Signed-off-by: Peter Zijlstra <a.p.zijlstra@...llo.nl>
> ---
> lib/rbtree.c | 19 ++++++++++---------
> 1 file changed, 10 insertions(+), 9 deletions(-)
>
> Index: linux-2.6/lib/rbtree.c
> ===================================================================
> --- linux-2.6.orig/lib/rbtree.c
> +++ linux-2.6/lib/rbtree.c
> @@ -237,6 +237,16 @@ void rb_erase(struct rb_node *node, stru
> node = node->rb_right;
> while ((left = node->rb_left) != NULL)
> node = left;
> +
> + if (rb_parent(old))
> + {
> + if (rb_parent(old)->rb_left == old)
> + rb_parent(old)->rb_left = node;
> + else
> + rb_parent(old)->rb_right = node;
> + } else
> + root->rb_node = node;
> +
> child = node->rb_right;
> parent = rb_parent(node);
> color = rb_color(node);
> @@ -253,15 +263,6 @@ void rb_erase(struct rb_node *node, stru
> node->rb_right = old->rb_right;
> node->rb_left = old->rb_left;
>
> - if (rb_parent(old))
> - {
> - if (rb_parent(old)->rb_left == old)
> - rb_parent(old)->rb_left = node;
> - else
> - rb_parent(old)->rb_right = node;
> - } else
> - root->rb_node = node;
> -
> rb_set_parent(old->rb_left, node);
> if (old->rb_right)
> rb_set_parent(old->rb_right, node);
>
>
> -------------------
>
> Subject: rbtree: optimize a special case in rb_erase()
> From: Wolfram Strepp <wstrepp@....de>
> Date: Sat Jan 24 13:17:04 CET 2009
>
> There are two cases when a node is erased:
> 'normal case': the successor is not the right-hand-child of the node to be
> erased
> 'special case': the successor is the right-hand child of the node to be
> erased
>
> Here some ascii-art, with following symbols (referring to the code):
> O: node to be deleted
> N: the successor of O
> P: parent of N
> C: child of N
> L: some other node
>
> normal case:
>
> O N
> / \ / \
> / \ / \
> L \ L \
> / \ P ----> / \ P
> / \ / \
> / /
> N C
> \ / \
> \
> C
> / \
>
>
> special case:
> O|P N
> / \ / \
> / \ / \
> L \ L \
> / \ N ----> / C
> \ / \
> \
> C
> / \
>
> Notice that for the special case we don't have to reconnect C to N.
>
> Signed-off-by: Wolfram Strepp <wstrepp@....de>
> Signed-off-by: Peter Zijlstra <a.p.zijlstra@...llo.nl>
> ---
> lib/rbtree.c | 8 ++++----
> 1 file changed, 4 insertions(+), 4 deletions(-)
>
> Index: linux-2.6/lib/rbtree.c
> ===================================================================
> --- linux-2.6.orig/lib/rbtree.c
> +++ linux-2.6/lib/rbtree.c
> @@ -251,13 +251,13 @@ void rb_erase(struct rb_node *node, stru
> parent = rb_parent(node);
> color = rb_color(node);
>
> - if (child)
> - rb_set_parent(child, parent);
> if (parent == old) {
> - parent->rb_right = child;
> parent = node;
> - } else
> + } else {
> + if (child)
> + rb_set_parent(child, parent);
> parent->rb_left = child;
> + }
>
> node->rb_parent_color = old->rb_parent_color;
> node->rb_right = old->rb_right;
>
>
> --------------
>
> Subject: rbtree: further optimize the special case
> From: Wolfram Strepp <wstrepp@....de>
> Date: Sat Jan 24 13:30:39 CET 2009
>
>
> normal case:
>
> O N
> / \ / \
> / \ / \
> L \ L \
> / \ P ----> / \ P
> / \ / \
> / /
> N C
> \ / \
> \
> C
> / \
>
>
> special case:
> O|P N
> / \ / \
> / \ / \
> L \ L \
> / \ N ----> / C
> \ / \
> \
> C
> / \
>
> Notice that for the special case we don't have to reconnect N to C.
>
> Furthermore, notice that the initial checks:
>
> if (!node->rb_left)
> child = node->rb_right;
> else if (!node->rb_right)
> child = node->rb_left;
> else
> {
> ...
> }
>
> guarantee that old->rb_right is set in the final else branch, therefore
> we can omit checking that again.
>
> Signed-off-by: Wolfram Strepp <wstrepp@....de>
> Signed-off-by: Peter Zijlstra <a.p.zijlstra@...llo.nl>
> ---
> lib/rbtree.c | 8 ++++----
> 1 file changed, 4 insertions(+), 4 deletions(-)
>
> Index: linux-2.6/lib/rbtree.c
> ===================================================================
> --- linux-2.6.orig/lib/rbtree.c
> +++ linux-2.6/lib/rbtree.c
> @@ -257,15 +257,15 @@ void rb_erase(struct rb_node *node, stru
> if (child)
> rb_set_parent(child, parent);
> parent->rb_left = child;
> +
> + node->rb_right = old->rb_right;
> + rb_set_parent(old->rb_right, node);
> }
>
> node->rb_parent_color = old->rb_parent_color;
> - node->rb_right = old->rb_right;
> node->rb_left = old->rb_left;
> -
> rb_set_parent(old->rb_left, node);
> - if (old->rb_right)
> - rb_set_parent(old->rb_right, node);
> +
> goto color;
> }
>
>
I'm fine with your reorganization.
Im just building a kernel to test it, but quite sure it will work.
Regards,
Wolfram
--
Psssst! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists