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

[Peter Zijlstra]

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@xxxxxxxxx>
---
 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@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/