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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
