Is augmented rbtree propagation broken?

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

Re: Is augmented rbtree propagation broken?

[Michel Lespinasse]

On Thu, Nov 22, 2012 at 9:14 AM, Sasha Levin <sasha.levin@oracle.com> wrote:
> 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.

You are absolutely correct that one needs to update the ancestors
augmented information on insertion, and that rb_insert_augmented
doesn't do that.

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

What we are supposed to do (and what other call sites are doing), is
that before insertion we do a search down the rbtree to find the
correct insertion point. During that search, we already look at nodes
on the desired path, so it is the ideal time to update their augmented
information as well (max_high in the case you are talking about).

> 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);
>  }

This would work, but would slow down all sites which already take care
of updating the augmented information before calling
rb_insert_augmented, so please don't do that.

The simplest fix would be to add the propagate call where your
rb_insert_augmented() call site is; the better fix would be to do the
update incrementally as you search down the tree for the insertion
point; and the best fix may be to just avoid duplicating that code and
use interval_tree.h (if your keys are longs) or
interval_tree_generic.h to generate the proper insert / remove
functions.

I would send you patches if the code was in linus's tree, but as it's
not I want to ask - what trees do these new augmented rbtree call
sites live in ? Are we talking perf and kvm git trees on kernel.org,
or are there others I should be aware of ?

Also in the case of ioports, are your intervals ever overlapping ?

Thanks,

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.