linux-kernel - Re: [PATCH v8 00/70] Introducing the Maple Tree

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <20220504004253.3vimieelrinmwqww@revolver>
Date:   Wed, 4 May 2022 00:43:00 +0000
From:   Liam Howlett <liam.howlett@...cle.com>
To:     Andrew Morton <akpm@...ux-foundation.org>
CC:     Davidlohr Bueso <dave@...olabs.net>,
        Matthew Wilcox <willy@...radead.org>,
        "maple-tree@...ts.infradead.org" <maple-tree@...ts.infradead.org>,
        "linux-mm@...ck.org" <linux-mm@...ck.org>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        Yu Zhao <yuzhao@...gle.com>
Subject: Re: [PATCH v8 00/70] Introducing the Maple Tree

* Andrew Morton <akpm@...ux-foundation.org> [220501 19:56]:
> On Sun, 1 May 2022 13:26:34 -0700 Davidlohr Bueso <dave@...olabs.net> wrote:
> 
> > On Wed, 27 Apr 2022, Matthew Wilcox wrote:
> > 
> > >On Wed, Apr 27, 2022 at 10:33:31AM -0700, Andrew Morton wrote:
> > >> On Wed, 27 Apr 2022 14:08:39 +0000 Liam Howlett <liam.howlett@...cle.com> wrote:
> > >> > The benchmarks are around the same as they have always been.
> > >>
> > >> So it's presently a wash.
> > >>
> > >> That makes "the plan" (below) really critical, otherwise there seems
> > >> little point in merging this code at this time?
> > >>
> > >> Please send me many very soothing words about how confident we should
> > >> be that the plan will be implemented and that it shall be good?
> > >
> > >Yes, performance-wise it's a wash.  However, Davidlohr was very
> > >impressed that it was a wash because we're actually getting rid of three
> > >data structures here; the linked list, the rbtree and the vmacache.
> > >His opinion was that we should push the maple tree in now, in advance
> > >of the future RCU uses.
> > 
> > Yes I like the maple tree, and at this stage I don't think we can ask
> > for more from this series wrt the MM - albeit there seems to still be
> > some folks reporting breakage. Fundamentally I see Liam's work to (re)move
> > complexity out of the MM (not to say that the actual maple tree is not
> > complex) by consolidating the three complimentary data structures very
> > much worth it considering performance does not take a hit. This was
> > very much a turn off with the range locking approach, which worst case
> > scenario incurred in prohibitive overhead. Also as Liam and Matthew
> > have mentioned, RCU opens up a lot of nice performance opportunities,
> > and in addition academia[1] has shown outstanding scalability of address
> > spaces with the foundation of replacing the locked rbtree with RCU
> > aware trees.
> 
> Thanks.   That sounded like a wordy acked-by to me? :)
> 
> Liam, I think the above is useful background for the [0/N].
> 
> > [1] https://pdos.csail.mit.edu/papers/rcuvm:asplos12.pdf
> 
> As is that.  The paper seems shockingly relevant.  Do we know the
> authors or is it a cosmic coincidence?
> 

Cosmic coincidence.  We designed our tree with the intention of solving
the hardest problem first.  Upon settling on a b-tree variant and a
rough outline, we researched ranged based b-trees and RCU b-trees and
did find that article.  So it was nice to find reassurances that we were
on the right path, but our design choice of using ranges made that paper
unusable for us.

Thanks,
Liam