linux-kernel - [PATCH 09/13] rbtree: optimize color flips and parent fetching in rb_insert

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-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <1341876923-12469-10-git-send-email-walken@google.com>
Date:	Mon,  9 Jul 2012 16:35:19 -0700
From:	Michel Lespinasse <walken@...gle.com>
To:	aarcange@...hat.com, dwmw2@...radead.org, riel@...hat.com,
	peterz@...radead.org, daniel.santos@...ox.com, axboe@...nel.dk,
	ebiederm@...ssion.com
Cc:	linux-mm@...ck.org, akpm@...ux-foundation.org,
	linux-kernel@...r.kernel.org, torvalds@...ux-foundation.org
Subject: [PATCH 09/13] rbtree: optimize color flips and parent fetching in rb_insert_color()

- Use the newly introduced rb_set_parent_color() function to flip the color
  of nodes whose parent is already known.
- Optimize rb_parent() when the node is known to be red - there is no need
  to mask out the color in that case.
- Flipping gparent's color to red requires us to fetch its rb_parent_color
  field, so we can reuse it as the parent value for the next loop iteration.

Signed-off-by: Michel Lespinasse <walken@...gle.com>
---
 lib/rbtree.c |   26 ++++++++++++++++----------
 1 files changed, 16 insertions(+), 10 deletions(-)

diff --git a/lib/rbtree.c b/lib/rbtree.c
index f668886..56369d8 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -47,6 +47,11 @@ static inline void rb_set_parent_color(struct rb_node *rb,
 	rb->rb_parent_color = (unsigned long)p | color;
 }
 
+static inline struct rb_node *rb_red_parent(struct rb_node *red)
+{
+	return (struct rb_node *)red->rb_parent_color;
+}
+
 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
 {
 	struct rb_node *right = node->rb_right;
@@ -116,7 +121,7 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
 
 void rb_insert_color(struct rb_node *node, struct rb_root *root)
 {
-	struct rb_node *parent, *gparent, *tmp;
+	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
 
 	while (true) {
 		/*
@@ -126,23 +131,23 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 		 * Otherwise, take some corrective action as we don't
 		 * want a red root or two consecutive red nodes.
 		 */
-		parent = rb_parent(node);
 		if (!parent) {
-			rb_set_black(node);
+			rb_set_parent_color(node, NULL, RB_BLACK);
 			break;
 		} else if (rb_is_black(parent))
 			break;
 
-		gparent = rb_parent(parent);
+		gparent = rb_red_parent(parent);
 
 		if (parent == gparent->rb_left) {
 			tmp = gparent->rb_right;
 			if (tmp && rb_is_red(tmp)) {
 				/* Case 1 - color flips */
-				rb_set_black(tmp);
-				rb_set_black(parent);
-				rb_set_red(gparent);
+				rb_set_parent_color(tmp, gparent, RB_BLACK);
+				rb_set_parent_color(parent, gparent, RB_BLACK);
 				node = gparent;
+				parent = rb_parent(node);
+				rb_set_parent_color(node, parent, RB_RED);
 				continue;
 			}
 
@@ -168,10 +173,11 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
 			tmp = gparent->rb_left;
 			if (tmp && rb_is_red(tmp)) {
 				/* Case 1 - color flips */
-				rb_set_black(tmp);
-				rb_set_black(parent);
-				rb_set_red(gparent);
+				rb_set_parent_color(tmp, gparent, RB_BLACK);
+				rb_set_parent_color(parent, gparent, RB_BLACK);
 				node = gparent;
+				parent = rb_parent(node);
+				rb_set_parent_color(node, parent, RB_RED);
 				continue;
 			}
 
-- 
1.7.7.3

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