linux-kernel - Re: [PATCH] rbtree: undo augmented damage -v2

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: <1275412748.27810.27883.camel@twins>
Date:	Tue, 01 Jun 2010 19:19:08 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Venkatesh Pallipadi <venki@...gle.com>
Cc:	mingo@...hat.com, hpa@...or.com, linux-kernel@...r.kernel.org,
	suresh.b.siddha@...el.com, tglx@...utronix.de,
	linux-tip-commits@...r.kernel.org,
	Fabio Checconi <fabio@...dalf.sssup.it>
Subject: Re: [PATCH] rbtree: undo augmented damage -v2

On Tue, 2010-06-01 at 10:00 -0700, Venkatesh Pallipadi wrote:
> I am not seeing how this can cover all the callbacks we will need to
> maintain the augmented tree property. May be I am missing something.

Yes, indeed, how about the below delta, which my eevdf code did do but I
overlooked on the conversion to the PAT code.

That removes the break as you said, but also adds code to update the
child nodes when walking up the path.

So in your rotation case:

    G             P
   / \    -->    / \
  P   U         N   G
 /        <--        \
N                     U

Say we take the right rotation, then the traversal up from N to P will
find that since N was the left child of P and it has a right child (G)
it will also update G.

Signed-off-by: Peter Zijlstra <a.p.zijlstra@...llo.nl>
---
 arch/x86/mm/pat_rbtree.c |   23 ++++++++++++-----------
 1 files changed, 12 insertions(+), 11 deletions(-)

diff --git a/arch/x86/mm/pat_rbtree.c b/arch/x86/mm/pat_rbtree.c
index f537087..ca19aae 100644
--- a/arch/x86/mm/pat_rbtree.c
+++ b/arch/x86/mm/pat_rbtree.c
@@ -81,20 +81,21 @@ static void update_node_max_end(struct rb_node *node)
 /* Update 'subtree_max_end' for a node and all its ancestors */
 static void update_path_max_end(struct rb_node *node)
 {
-	u64 old_max_end, new_max_end;
+	struct rb_node *parent;
 
-	while (node) {
-		struct memtype *data = container_of(node, struct memtype, rb);
-
-		old_max_end = data->subtree_max_end;
-		update_node_max_end(node);
-		new_max_end = data->subtree_max_end;
+up:
+	update_node_max_end(node);
+	parent = rb_parent(node);
+	if (!parent)
+		return;
 
-		if (new_max_end == old_max_end)
-			break;
+	if (node == parent->rb_left && parent->rb_right)
+		update_node_max_end(parent->rb_right);
+	else if (parent->rb_left)
+		update_node_max_end(parent->rb_left);
 
-		node = rb_parent(node);
-	}
+	node = parent;
+	goto up;
 }
 
 /* Find the first (lowest start addr) overlapping range from rb tree */

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