linux-kernel - [PATCH 1/2] Optimization of function rb

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <20090120215556.74580@gmx.net>
Date:	Tue, 20 Jan 2009 22:55:56 +0100
From:	"Wolfram Strepp" <wstrepp@....de>
To:	linux-kernel@...r.kernel.org
Cc:	dwmw2@...radead.org, akpm@...ux-foundation.org
Subject: [PATCH 1/2] Optimization of function rb_erase() in lib/rbtree.c

Hello,

i have reviewed the code of the rb-tree implementation
in the kernel, and distilled two small patches for file lib/rbtree.c,
which optimize and cleanup the code of functions rb_erase() and __rb_erase_color().
In summary, there are 5 if()-conditions which can be eliminated.
The patches reduce the code size (normal kernel build on x86)
of this functions by 23 bytes, or 4.5 %.

So although this is not a dramatic change, i think its worth it,
given the many places in the kernel where it is used
(and given the fact that processors dont like if-conditions).

The patches are tested on x86.

------------------------------------------

The first patch was already posted some years ago, see:
http://lkml.org/lkml/2002/11/22/146
and:
http://lkml.org/lkml/2002/11/24/122

It was finally merged by the original author of the rb-tree
implementation, Andrea Arcangeli, in one of his kernel trees.
Citing from http://lkml.org/lkml/2002/12/25/51:

>Only in 2.4.21pre2aa1: 00_rbtree-cleanups-1
>
>	Merged rbtree cleanups/microoptimizations from Érsek László after
>	verifying their math correctness also with the help of Paolo Carlini
>	and of some gentle reminder from Rusty, they are obviously right,
>	thanks.

But obviousely, it never found is way into the mainline kernel,
so here it is again.

Signed-off-by: Wolfram Strepp <wstrepp@....de>

====================================================
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -163,17 +163,14 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 			{
 				if (!other->rb_right || rb_is_black(other->rb_right))
 				{
-					struct rb_node *o_left;
-					if ((o_left = other->rb_left))
-						rb_set_black(o_left);
+					rb_set_black(other->rb_left);
 					rb_set_red(other);
 					__rb_rotate_right(other, root);
 					other = parent->rb_right;
 				}
 				rb_set_color(other, rb_color(parent));
 				rb_set_black(parent);
-				if (other->rb_right)
-					rb_set_black(other->rb_right);
+				rb_set_black(other->rb_right);
 				__rb_rotate_left(parent, root);
 				node = root->rb_node;
 				break;
@@ -200,17 +197,14 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
 			{
 				if (!other->rb_left || rb_is_black(other->rb_left))
 				{
-					register struct rb_node *o_right;
-					if ((o_right = other->rb_right))
-						rb_set_black(o_right);
+					rb_set_black(other->rb_right);
 					rb_set_red(other);
 					__rb_rotate_left(other, root);
 					other = parent->rb_left;
 				}
 				rb_set_color(other, rb_color(parent));
 				rb_set_black(parent);
-				if (other->rb_left)
-					rb_set_black(other->rb_left);
+				rb_set_black(other->rb_left);
 				__rb_rotate_right(parent, root);
 				node = root->rb_node;
 				break;

-- 
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/