linux-kernel - Re: [PATCH v2 2/3] augmented rbtree: add new RB_DECLARE_CALLBACKS

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date:   Wed, 21 Aug 2019 15:18:14 -0700
From:   Michel Lespinasse <walken@...gle.com>
To:     Davidlohr Bueso <dave@...olabs.net>
Cc:     Peter Zijlstra <peterz@...radead.org>,
        David Howells <dhowells@...hat.com>,
        Andrew Morton <akpm@...ux-foundation.org>,
        LKML <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH v2 2/3] augmented rbtree: add new
 RB_DECLARE_CALLBACKS_MAX macro

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.