Re: [PATCH -next 00/11] lib/interval-tree: move to half closed intervals

[Davidlohr Bueso]

On Thu, 03 Oct 2019, Jason Gunthorpe wrote:

> On Thu, Oct 03, 2019 at 01:18:47PM -0700, Davidlohr Bueso wrote:
> > Hi,
> >
> > It has been discussed[1,2] that almost all users of interval trees would better
> > be served if the intervals were actually not [a,b], but instead [a, b). This
> > series attempts to convert all callers by way of transitioning from using
> > "interval_tree_generic.h" to "interval_tree_gen.h". Once all users are converted,
> > we remove the former.
> >
> > Patch 1: adds a call that will make patch 8 easier to review by introducing stab
> >          queries for the vma interval tree.
> >
> > Patch 2: adds the new interval_tree_gen.h which is the same as the old one but
> >          uses [a,b) intervals.
> >
> > Patch 3-9: converts, in baby steps (as much as possible), each interval tree to
> > 	   the new [a,b) one. It is done this way also to maintain bisectability.
> > 	   Most conversions are pretty straightforward, however, there are some
> > 	   creative ways in which some callers use the interval 'end' when going
> > 	   through intersecting ranges within a tree. Ie: patch 3, 6 and 9.
> >
> > Patch 10: deletes the interval_tree_generic.h header; there are no longer any users.
> >
> > Patch 11: finally simplifies x86 pat tree to use the new interval tree machinery.
> >
> > This has been lightly tested, and certainly not on driver paths that do non
> > trivial conversions. Also needs more eyeballs as conversions can be easily
> > missed (even when I've tried mitigating this by renaming the endpoint from 'last'
> > to 'end' in each corresponding structure).
> >
> > Because this touches a lot of drivers, I'm Cc'ing the whole thing to a couple of
> > relevant lists (mm, dri, rdma); sorry if you consider this spam.
> >
> > Applies on top of today's linux-next tree. Please consider for v5.5.
> >
> > Thanks!
> >
> > [1] https://lore.kernel.org/lkml/CANN689HVDJXKEwB80yPAVwvRwnV4HfiucQVAho=dupKM_iKozw@xxxxxxxxxxxxxx/
>
> Hurm, this is not entirely accurate. Most users do actually want
> overlapping and multiple ranges. I just studied this extensively:
>
> radeon_mn actually wants overlapping but seems to mis-understand the
> interval_tree API and actively tries hard to prevent overlapping at
> great cost and complexity. I have a patch to delete all of this and
> just be overlapping.
>
> amdgpu_mn copied the wrongness from radeon_mn
>
> All the DRM drivers are basically the same here, tracking userspace
> controlled VAs, so overlapping is essential
>
> hfi1/mmu_rb definitely needs overlapping as it is dealing with
> userspace VA ranges under control of userspace. As do the other
> infiniband users.
>
> vhost probably doesn't overlap in the normal case, but again userspace
> could trigger overlap in some pathalogical case.
>
> The [start,last] allows the interval to cover up to ULONG_MAX. I don't
> know if this is needed however. Many users are using userspace VAs
> here. Is there any kernel configuration where ULONG_MAX is a valid
> userspace pointer? Ie 32 bit 4G userspace? I don't know.
>
> Many users seemed to have bugs where they were taking a userspace
> controlled start + length and converting them into a start/end for
> interval tree without overflow protection (woops)
>
> Also I have a series already cooking to delete several of these
> interval tree users, which will terribly conflict with this :\

I have no problem redoing after your changes; if it's worth it
at all.

> Is it really necessary to make such churn for such a tiny API change?

I agree, and was kind of expecting this. In general the diffstat ended
up being larger than I initially hoped for. Maybe after your removals
I can look into this again.

Thanks,
Davidlohr