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
