On Tue, Aug 13, 2019 at 05:06:16PM -0700, Davidlohr Bueso wrote: > On Tue, 02 Jul 2019, Michel Lespinasse wrote: > > - 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.
Not really, I think the pat conversion is a good idea though I am confused about the interval definitions (open or closed ?) in your patch set. > > - 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. Do you have any thoughts about changing the interval tree definitions to use half-open intervals like everywhere else in the kernel ? -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.
