Re: [PATCH 1/3] x86,mm/pat: Use generic interval trees

[Michel Lespinasse]

On Wed, Aug 21, 2019 at 9:49 PM Davidlohr Bueso <dave@xxxxxxxxxxxx> wrote:
> On Wed, 21 Aug 2019, Michel Lespinasse wrote:
> >I'm not sure where to go with this - would it make sense to add a new
> >interval tree header file that uses [start,end) intervals (with the
> >thought of eventually converting all current interval tree users to it)
> >instead of adding one more use of the less-natural [start,last]
> >interval trees ?
>
> It might be the safest way, although I really hate having another
> header file for interval_tree... The following is a diffstat of a
> tentative conversion (I'll send the patch separately); I'm not sure
> if a single shot conversion would be acceptable, albeit with relevant
> maintainer acks.

That would make sense to me. Maybe doing it all in a single commit is
too hard to review or bisect, but having a small series that
duplicates the interval tree header at the start and removes the old
(closed intervals) version at the end looks like it would work IMO.

> >At first, I thought that you were handling that by removing 1 from the
> >end of the interval, to adjust between the PAT and interval tree
> >definitions. But, I don't see you doing that anywhere.
>
> This should have been my first approach.
>
> >Then, I thought that you were using [start, end( intervals everywhere,
> >and the interval tree functions memtype_interval_iter_first and
> >memtype_interval_iter_next would just return too many candidate
> >matches as as you are passing "end" instead of "last" == end-1 as the
> >interval endpoint, but then you would filter out the extra intervals
> >using is_node_overlap(). But, if that is the case, then I don't
> >understand why you need to redefine is_node_overlap() here.
>
> My original expectation was to actually remove a lot more of pat_rbtree,
> including the is_node_overlap() and the filtering. Yes, I think this can
> be done if the interval-tree is converted to [a,b[ and we can thus
> just iterate the tree seamlessly.

All right. So, my preference would be if we can use a version of
interval trees that would work natively with half open intervals, as
we discussed above. But, if that seems like too much change, I would
also be ready to approve a version of pat_interval.c that would adjust
the interval endpoint to compensate for the interval tree's use of
closed intervals. I think either way, I can't approve the current
version as it's too much of an in-between which makes it hard to
follow IMO.

> I think doing the conversion you suggested to [a,b[ for all users, then
> redoing this series on top of that would be the way to move forward.

That would be ideal; hopefully you don't see the vma_interval_tree
thing as blocking this approach ?

Thanks,

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