Re: [QUESTION] about the maple tree and current status of mmap_lock scalability

[Matthew Wilcox]

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.