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

From: Michel Lespinasse <walken@google.com>
To: Jason Gunthorpe <jgg@ziepe.ca>
Cc: Davidlohr Bueso <dave@stgolabs.net>,
	Andrew Morton <akpm@linux-foundation.org>,
	 Peter Zijlstra <peterz@infradead.org>,
	LKML <linux-kernel@vger.kernel.org>,
	 linux-mm <linux-mm@kvack.org>,
	dri-devel@lists.freedesktop.org,  linux-rdma@vger.kernel.org
Subject: Re: [PATCH -next 00/11] lib/interval-tree: move to half closed intervals
Date: Fri, 4 Oct 2019 06:15:11 -0700	[thread overview]
Message-ID: <CANN689G3chM1FjFPdCNm9_OQxazs7YP1PuZLpqGtq=qzaZ0Hbw@mail.gmail.com> (raw)
In-Reply-To: <20191004002609.GB1492@ziepe.ca>

Hi Jason,

On Thu, Oct 3, 2019 at 5:26 PM Jason Gunthorpe <jgg@ziepe.ca> wrote:
> Hurm, this is not entirely accurate. Most users do actually want
> overlapping and multiple ranges. I just studied this extensively:

(Just curious, are you the person we discussed this with after the
Maple Tree talk at LPC 2019 ?)

I think we have two separate API problems there:
- overlapping vs non-overlapping intervals (the interval tree API
supports overlapping intervals, but some users are confused about
this)
- closed vs half-open interval definitions

It looks like you have been looking mostly at the first issue, which I
expect could simplify several interval tree users considerably, while
Davidlohr is addressing the second issue here.

> 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.

Do you have a handle on what usnic is doing with its intervals ?
usnic_uiom_insert_interval() has some complicated logic to avoid
having overlapping intervals, which is very confusing to me.

> 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 :\
>
> Is it really necessary to make such churn for such a tiny API change?

My take is that this (Davidlohr's) patch series does not necessarily
need to be applied all at once - we could get the first change in
(adding the interval_tree_gen.h header), and convert the first few
users, without getting them all at once, as long as we have a plan for
finishing the work. So, if you have cleanups in progress in some of
the files, just tell us which ones and we can leave them out from the
first pass.

Thanks,

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.