Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
MIME-Version: 1.0
References: <20190813224620.31005-1-dave@stgolabs.net> <20190813224620.31005-2-dave@stgolabs.net>
 <20190821215707.GA99147@google.com> <20190822044936.qusm5zgjdf6n5fds@linux-r8p5>
In-Reply-To: <20190822044936.qusm5zgjdf6n5fds@linux-r8p5>
From:   Michel Lespinasse <walken@google.com>
Date:   Thu, 22 Aug 2019 13:24:15 -0700
Message-ID: <CANN689H0qtpi8ZH7rxUWAVaDVdSxtaPbuQ3KL2JgXLUCX4dWmQ@mail.gmail.com>
Subject: Re: [PATCH 1/3] x86,mm/pat: Use generic interval trees
To:     Davidlohr Bueso <dave@stgolabs.net>
Cc:     Ingo Molnar <mingo@kernel.org>,
        Thomas Gleixner <tglx@linutronix.de>,
        Peter Zijlstra <peterz@infradead.org>,
        Andrew Morton <akpm@linux-foundation.org>, x86@kernel.org,
        LKML <linux-kernel@vger.kernel.org>,
        Davidlohr Bueso <dbueso@suse.de>
Content-Type: text/plain; charset="UTF-8"
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

On Wed, Aug 21, 2019 at 9:49 PM Davidlohr Bueso <dave@stgolabs.net> 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.