On Tue, Jul 2, 2019 at 9:09 AM Davidlohr Bueso <[email protected]> wrote: > > On Tue, 02 Jul 2019, Michel Lespinasse wrote: > > >diff --git a/arch/x86/mm/pat_rbtree.c b/arch/x86/mm/pat_rbtree.c > >index fa16036fa592..2afad8e869fc 100644 > >--- a/arch/x86/mm/pat_rbtree.c > >+++ b/arch/x86/mm/pat_rbtree.c > >@@ -54,23 +54,10 @@ static u64 get_subtree_max_end(struct rb_node *node) > > return ret; > > } > > > >-static u64 compute_subtree_max_end(struct memtype *data) > >-{ > >- u64 max_end = data->end, child_max_end; > >- > >- child_max_end = get_subtree_max_end(data->rb.rb_right); > >- if (child_max_end > max_end) > >- max_end = child_max_end; > >- > >- child_max_end = get_subtree_max_end(data->rb.rb_left); > >- if (child_max_end > max_end) > >- max_end = child_max_end; > >- > >- return max_end; > >-} > >+#define NODE_END(node) ((node)->end) > > > >-RB_DECLARE_CALLBACKS(static, memtype_rb_augment_cb, struct memtype, rb, > >- u64, subtree_max_end, compute_subtree_max_end) > >+RB_DECLARE_CALLBACKS_MAX(struct memtype, rb, u64, subtree_max_end, NODE_END, > >+ static, memtype_rb_augment_cb) > > (unrelated to this patch) > > So fyi I've recently been looking at having the whole pat_rbtree use the > (generic) > interval tree api, which would mean less code and more optimized. Of course, > unfortunately they aren't 100% compatible. Fundamentally the concept of > overlaps > are different (pat_rbtree is does not consider overlap when 'node->start == > end' - > same for the test to the right of the node). Thus for example > interval_tree_iter_first() > won't necessarily return the same node as memtype_rb_lowest_match(). > Similarly, > inserting a node with key collisions will have differences wrt what path to > take; > equal 'start' in pat will go to the left, interval_tree to the right. All > this, > I suspect, is inherited from how pat used to work with rbtree+list. > > So generic ones cannot be used and if we just use INTERVAL_TREE_DEFINE > template for > pat and add the ad-hoc code does not make sense wrt cleanup, nor do we get the > optimizations. We could of course, add them manually (by using cached > rbtrees, for > example) and forget about interval_tree altogether; just seems a shame.
Ehhh, I have my own list of gripes about interval tree (I'm responsible for some of these too): - The majority of interval tree users (though either the interval_tree.h or the interval_tree_generic.h API) do not store any overlapping intervals, and as such they really don't have any reason to use an augmented rbtree in the first place. This seems to be true for at least drivers/gpu/drm/amd/amdgpu/amdgpu_mn.c, drivers/gpu/drm/amd/amdgpu/amdgpu_vm.c, drivers/gpu/drm/drm_mm.c, drivers/gpu/drm/radeon/radeon_mn.c, drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.c, and probably (not 100% sure) also drivers/infiniband/hw/hfi1/mmu_rb.c and drivers/vhost/vhost.c. I think the reason they do that is because they like to have the auto-generated insert / remove / iter functions rather than writing their own as they would have to do through the base rbtree API. Not necessarily a huge problem but it is annoying when working on inteval tree to consider that the data structure is not optimal for most of its users. - The intervals are represented as [start, last], where most everything else in the kernel uses [start, end[ (with last == end - 1). The reason it was done that way was for stabbing queries - I thought these would be nicer to represent as a [stab, stab] interval rather than [stab, stab+1[. But, things didn't turn out that way because of huge pages, and we end up with stabbing queries in the [stab, stab + page_size - 1] format, at which point we could just as easily go for [stab, stab + page_size[ representation. Having looked into it, my understanding is that *all* current users of the interval tree API would be better served if the intervals were represented as [start, end[ like everywhere else in the kernel. - interval_tree_generic.h refers to interval_tree.h as being the generic one. I think this is quite confusing. To me interval_tree_generic is the generic implementation (it works with any scalar ITTYPE), and interval_tree.h is the specialized version (it works with unsigned long keys only). Fun fact, interval_tree.[c,h] was initially only meant as sample / test code - I thought everyone would use the generic version. Not a big deal, it's probably better for everyone to use the specialized version when applicable (unless they don't really need overlapping intervals in the first place, but that's a separate gripe). - I don't like that interval tree API forces rb_leftmost caching on its users. I'm not sure what was the use case that motivated it, but I don' think it's a relevant optimization for most users - I can only see a benefit if people are frequently calling the iter_first function with a search interval that is to the left of the leftmost entry, and that doesn't seem to be relevant to the general case (in the general case, maintaining leftmost has a O(1) cost and its benefit is only expected to show up in 1/N cases, ....) Going back to your specific pat_rbtree.c comment, I think using interval trees could still work. The issue with end is the typical one ([start, last] vs [start, end[) which can be worked around by adjusting the end by 1 (still hate having to do that though). The issue with insertion order may possibly not matter, as memtype_rb_check_conflict verifies that any overlapping ranges will have the same configured memory type. So maybe the order doesn't matter in the end ??? Not 100% sure about that one. Do you have any comments on the above gripes and do you think they would be worth addressing ? -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.
