linux-kernel - Re: [QUESTION] about the maple tree and current status of mmap

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: <Y63FmaNoLAcdsLaU@casper.infradead.org>
Date:   Thu, 29 Dec 2022 16:51:37 +0000
From:   Matthew Wilcox <willy@...radead.org>
To:     Hyeonggon Yoo <42.hyeyoo@...il.com>
Cc:     linux-mm@...ck.org, liam.howlett@...cle.com, surenb@...gle.com,
        ldufour@...ux.ibm.com, michel@...pinasse.org, vbabka@...e.cz,
        linux-kernel@...r.kernel.org
Subject: Re: [QUESTION] about the maple tree and current status of mmap_lock
 scalability

On Thu, Dec 29, 2022 at 11:22:28PM +0900, Hyeonggon Yoo wrote:
> On Wed, Dec 28, 2022 at 08:50:36PM +0000, Matthew Wilcox wrote:
> > The long term goal is even larger than this.  Ideally, the VMA tree
> > would be protected by a spinlock rather than a mutex. 
> 
> You mean replacing mmap_lock rwsem with a spinlock?
> How is that possible if readers can take it for page fault?

The mmap_lock is taken for many, many things.  So the plan was to
have a spinlock in the maple tree (indeed, there's still one there;
it's just in a union with the lockdep_map_p).  VMA readers would walk
the tree protected only by RCU; VMA writers would take the spinlock
while modifying the tree.  The work Suren, Liam & I are engaged in
still uses the mmap semaphore for writers, but we do walk the tree
under RCU protection.

> > While I've read the RCUVM paper, I wouldn't say it was particularly an
> > inspiration.  The Maple Tree is independent of the VM; it's a general
> > purpose B-tree.
> 
> My intention was to ask how to synchronize with other VMA operations
> after the tree traversal with RCU. (Because it's unreasonable to handle
> page fault in RCU read-side critical section)
> 
> Per-VMA lock seem to solve it by taking the VMA lock in read mode within
> RCU read-side critical section.

Right, but it's a little more complex than that.  The real "lock" on
the VMA is actually a sequence count.  https://lwn.net/Articles/906852/
does a good job of explaining it, but the VMA lock is really there as
a convenient way for the writer to wait for readers to be sufficiently
"finished" with handling the page fault that any conflicting changes
will be correctly retired.

https://www.infradead.org/~willy/linux/store-free-page-faults.html
outlines how I intend to proceed from Suren's current scheme (where
RCU is only used to protect the tree walk) to using RCU for the
entire page fault.