lkml.org 
[lkml]   [2012]   [Dec]   [10]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
Date
SubjectRe: [PATCH 0/3] remove kvm's use of augmented rbtree
Ping?

On Sun, Nov 25, 2012 at 5:14 PM, Sasha Levin <levinsasha928@gmail.com> wrote:
> On Sat, Nov 24, 2012 at 9:40 PM, Michel Lespinasse <walken@google.com> wrote:
>> On Thu, Nov 22, 2012 at 9:49 PM, Michel Lespinasse <walken@google.com> wrote:
>>> On Thu, Nov 22, 2012 at 9:14 AM, Sasha Levin <sasha.levin@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


\
 
 \ /
  Last update: 2012-12-10 17:41    [W:0.573 / U:0.056 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site