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;
Date:   Wed, 21 Aug 2019 15:18:14 -0700
From:   Michel Lespinasse <walken@google.com>
To:     Davidlohr Bueso <dave@stgolabs.net>
Cc:     Peter Zijlstra <peterz@infradead.org>,
        David Howells <dhowells@redhat.com>,
        Andrew Morton <akpm@linux-foundation.org>,
        LKML <linux-kernel@vger.kernel.org>
Subject: Re: [PATCH v2 2/3] augmented rbtree: add new
 RB_DECLARE_CALLBACKS_MAX macro
Message-ID: <20190821221814.GB99147@google.com>
References: <20190702075819.34787-1-walken@google.com>
 <20190702075819.34787-3-walken@google.com>
 <20190702160913.ptg4p2jyb6ih43hb@linux-r8p5>
 <CANN689HVDJXKEwB80yPAVwvRwnV4HfiucQVAho=dupKM_iKozw@mail.gmail.com>
 <20190814000616.sd4mxwsewhqqz6ra@linux-r8p5>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20190814000616.sd4mxwsewhqqz6ra@linux-r8p5>
User-Agent: Mutt/1.10.1 (2018-07-13)
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

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.