Is augmented rbtree propagation broken?

[Sasha Levin]

Hi Michel,

I've noticed a bug regarding search of ioports in the KVM tool. Since the KVM tool is
using kernel's augmented rbtree implementation to represent an interval rbtree I dug a
bit into the new implementation in the kernel, and noticed the following odd behaviour.

Let's take a simple case where we have 2 intervals with the 3rd parameter being the
'max_high' field used by interval rbtrees: (1,2,0) , (3,4,0). Let's add them one by one:

1.		 (1,2,2)
		/	\
	     NULL	NULL

2.		 (1,2,4)
		/	\
	     NULL	(3,4,4)

On the 2nd stage we'd expect that the new (3,4) interval will be added to the right
subtree (which happens correctly), and that the insertion will be propagated to the
root of the tree to update max_high (which doesn't happen).

Basically, at stage 2, the tree we're left with is:

		 (1,2,2)
		/	\
	     NULL	(3,4,4)

Which is wrong.

I suspect that this happens because we never propagate upon insertion, which sounds
quite odd to me, but I might be missing something.

The following patch fixed the problem for me:

diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h
index 214caa3..5cfdca6 100644
--- a/include/linux/rbtree_augmented.h
+++ b/include/linux/rbtree_augmented.h
@@ -47,6 +47,7 @@ rb_insert_augmented(struct rb_node *node, struct rb_root *root,
                    const struct rb_augment_callbacks *augment)
 {
        __rb_insert_augmented(node, root, augment->rotate);
+       augment->propagate(node, NULL);
 }


Thanks,
Sasha
--
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/