Re: [PATCH v2 2/3] augmented rbtree: add new RB_DECLARE_CALLBACKS_MAX macro

[Michel Lespinasse]

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.