Ping?
On Sun, Nov 25, 2012 at 5:14 PM, Sasha Levin <[email protected]> wrote: > On Sat, Nov 24, 2012 at 9:40 PM, Michel Lespinasse <[email protected]> wrote: >> On Thu, Nov 22, 2012 at 9:49 PM, Michel Lespinasse <[email protected]> wrote: >>> On Thu, Nov 22, 2012 at 9:14 AM, Sasha Levin <[email protected]> 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 [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
