On Sat, Nov 24, 2012 at 9:40 PM, Michel Lespinasse <wal...@google.com> wrote:
> On Thu, Nov 22, 2012 at 9:49 PM, Michel Lespinasse <wal...@google.com> wrote:
>> On Thu, Nov 22, 2012 at 9:14 AM, Sasha Levin <sasha.le...@oracle.com> wrote:
>>> 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.
>
> So I had a quick look at linux-next, and my understanding is that the
> rbtree-interval API in kvm always stores non-overlapping intervals.
> Based on this, the use of augmented rbtrees isn't really justified; it
> is just as easy to use a simple rbtree of intervals sorted by the
> addresses they cover.
>
> This patchset was generated against the current linux-next. I only
> verified that kvm still compiled; obviously this would need more
> testing. On the other hand, there are currently some correctness
> issues in kvm's implementatin of rbtree intervals, so I think this
> simplification should be beneficial.
>
> Michel Lespinasse (3):
> kvm: ensure non-overlapping intervals in rb_int_insert()
> kvm: rb_int_search_single simplification
> kvm: remove max_high field in rb_int_node structure
>
> tools/kvm/include/kvm/rbtree-interval.h | 13 +++--
> tools/kvm/util/rbtree-interval.c | 86
> ++++---------------------------
> 2 files changed, 18 insertions(+), 81 deletions(-)
>
> Sasha, could you please check my logic and apply this to the kvm tree ?
When I've initially added the interval tree I figured we might need to
allow overlapping for future arches which might need it. Since we now
have extra 2 arches I guess we don't really need it. So I guess we're
fine with removing it.
Pekka?
Thanks,
Sasha
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
