Messages in this thread | | | Date | Tue, 13 Aug 2019 17:06:16 -0700 | From | Davidlohr Bueso <> | Subject | Re: [PATCH v2 2/3] augmented rbtree: add new RB_DECLARE_CALLBACKS_MAX macro |
| |
On Tue, 02 Jul 2019, Michel Lespinasse wrote: >Ehhh, I have my own list of gripes about interval tree (I'm >responsible for some of these too):
Sorry just getting back to this.
> >- 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.
I think the patch I sent earlier will add to your unhappiness.
> >- 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, ....)
Right, so this was done originally for optimizing range locking which needed to do the iter_first a lot. fwiw pat_rbtree tree could also use it before insertion. While I did not examine the other users of interval_tree, I considered it overall worthwhile having; it comes at pretty much no cost and the extra footprint has not been a problem so far for users.
> >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.
I've sent out a patch.
Thanks, Davidlohr
| |