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: <20220428022808.dqsvccr4ogezo5yb@revolver>
Date:   Thu, 28 Apr 2022 02:28:18 +0000
From:   Liam Howlett <liam.howlett@...cle.com>
To:     Andrew Morton <akpm@...ux-foundation.org>
CC:     "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>,
        Matthew Wilcox <willy@...radead.org>
Subject: Re: [PATCH v8 00/70] Introducing the Maple Tree

* Andrew Morton <akpm@...ux-foundation.org> [220427 13:33]:
> On Wed, 27 Apr 2022 14:08:39 +0000 Liam Howlett <liam.howlett@...cle.com> wrote:
> 
> > > > 
> > > > The tree has a branching factor of 10 for non-leaf nodes and 16 for leaf
> > > > nodes.  With the increased branching factor, it is significantly shorter than
> > > > the rbtree so it has fewer cache misses.  The removal of the linked list
> > > > between subsequent entries also reduces the cache misses and the need to pull
> > > > in the previous and next VMA during many tree alterations.
> > > 
> > > Do we have any quantitative testing results?
> > 
> > I was waiting for the mmtests sweep to complete before sending them but
> > I didn't want to hold up Yu Zhao's testing of the combined tree as it
> > has proved useful already. Please don't include the results in the first
> > commit as it wouldn't make much sense.  If you intend to put them in a
> > commit message, please put them in the patch introducing the maple tree.
> 
> I did that.
> 
> > 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?

There are a number of reasons to merge at this time.  First, as Matthew
said, we have more than one user so having the tree upstream would
obviously help them out.  Second, we can make sure this much (maple tree
+ vma tracking) works for everyone before we enable VMA RCU and play
even more with the locking scenarios.  The third reason is to get more
community input into "the plan" to ensure the maple tree is beneficial
in the most common execution paths and capture corner cases.

> 
> 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?

Tea, warmth, fresh bread.

As we know, VMAs are rarely written and mostly read.  This plan removes
the majority of the slow down on readers.  The only slow down is when a
reader conflicts with a writer.  We are actually slower on writes - we
allocate nodes for the tree vs having it embedded in the VMA itself and
we do more work in calculating the gaps, but we are actually fast enough
to hide that on the read side.  Once the writers stop blocking the
readers it shall be good.  We need this step to get to using the maple
tree in RCU mode to make this happen.

> 
> > > 
> > > What's the plan on utilizing this to further reduce mmap_lock contention?
> > 
> > The plan is to get to the point where we use the maple tree in RCU mode.
> > Readers will not block for writers.  A single write operation will be
> > allowed at a time.  A reader re-walks if stale data is encountered. VMAs
> > would be RCU enabled and this mode would be entered once multiple tasks
> > are using the mm_struct.  I can go into more details if you want.
> 
> Uh, that's very important information.  It's really the whole point
> of the patchset!   I added this to the [0/n] changelog.

Yes, but that's not what the patch set does today.  I didn't want to
include The Plan until it exists.  I'd like to think that what we have
here is worth while on its own and a good start - but a start to
something big.  It's hard enough to get people to look at 70 patches,
doubly so for an RFC of 70.  The interest from others in using a tree
with an easy interface seems like a win as well.

I also have some side goals such as the removal of __vma_adjust() for
code readability.


Thanks,
Liam