| 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
| ||
|
Message-Id: <1232801175.4859.61.camel@laptop>
Date: Sat, 24 Jan 2009 13:46:15 +0100
From: Peter Zijlstra <peterz@...radead.org>
To: Wolfram Strepp <wstrepp@....de>
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
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.
>
> 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
>
> In the normal case, the pointers from the nodes to its parents and vice-versa
> have all to be reconnected to its new parents/childs.
> The current code basically ignores this special case, doing the reconnections
> always in the way as if it were the normal case. This is ok, but not optimal.
> The patch re-arranges the lines, such that it makes use of one particular
> feature of the special case: when the node to be deleted is replaced by its successor,
> it pulls it child behind - so no reconnection is necessary. As a result, the
> if-condition, which checks if this child is a NIL-leave, can be omitted.
>
> 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
> / \
>
>
> Signed-off-by: Wolfram Strepp <wstrepp@....de>
>
> ======================================
>
> --- a/lib/rbtree.c
> +++ b/lib/rbtree.c
> @@ -231,22 +231,13 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
> node = node->rb_right;
> while ((left = node->rb_left) != NULL)
> node = left;
> +
> child = node->rb_right;
> 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
> - parent->rb_left = child;
> -
> + /* connect 'node' with its new parent */
> node->rb_parent_color = old->rb_parent_color;
> - node->rb_right = old->rb_right;
> - node->rb_left = old->rb_left;
> -
> if (rb_parent(old))
> {
> if (rb_parent(old)->rb_left == old)
> @@ -256,9 +247,26 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
> } else
> root->rb_node = node;
>
> - rb_set_parent(old->rb_left, node);
> - if (old->rb_right)
> +
> + if (parent == old) {
> + /* special case: 'node' becomes parent, pulling its
> + child up behind --> no re-connecting necessary ! */
> + parent = node;
> + } else {
> + /* replace 'node' with its former child */
> + parent->rb_left = child;
> + if (child)
> + rb_set_parent(child, parent);
> +
> + /* connect 'node' to its new right-hand child */
> + node->rb_right = old->rb_right;
> rb_set_parent(old->rb_right, node);
> + }
> +
> + /* connect 'node' to its new left-hand child */
> + node->rb_left = old->rb_left;
> + rb_set_parent(old->rb_left, node);
> +
> goto color;
> }
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;
}
--
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