[PATCH v6 00/71] Introducing the Maple Tree

[Matthew Wilcox]

On Wed, Feb 16, 2022 at 11:47:00AM -0800, Andrew Morton wrote:
> On Tue, 15 Feb 2022 14:37:44 +0000 Liam Howlett <liam.howlett at oracle.com> wrote:
> 
> > The maple tree is an RCU-safe range based B-tree designed to use modern
> > processor cache efficiently.  There are a number of places in the kernel
> > that a non-overlapping range-based tree would be beneficial, especially
> > one with a simple interface.  The first user that is covered in this
> > patch set is the vm_area_struct, where three data structures are
> > replaced by the maple tree: the augmented rbtree, the vma cache, and the
> > linked list of VMAs in the mm_struct.  The long term goal is to reduce
> > or remove the mmap_sem contention.
> 
> Has a path been chosen which gets us from here to significant reduction
> in mmap_lock overhead?
> 
> If so, what's the plan and what must be done?

I would say there are still competing ideas for how that is to be done.

First, the Maple Tree is independent (to a certain extent) of all the
approaches to reducing mmap_lock overhead.  It's a better data structure
for VMA lookup than the rbtree.  Set against that, it has higher overhead
for modifications.  That means that benchmarks which primarily measure
modification overhead see worse performance.  We believe this is not
representative of real workloads, and indeed we see ~parity on workloads
like git and make -jN.

The advantage to this patch set is that we get rid of the vmacache
entirely, we get rid of the doubly-linked list chaining VMAs together
and we get rid of the rbtree usage.  And we add a new generic data
structure that hopefully I can point people towards instead of using
the XArray inappropriately.

Both of the approaches to avoiding taking the mmap_lock in the fault path
will benefit from using the maple tree for VMAs.  Fewer cache misses and
RCU safety are things we all want.  The maple tree will also benefit
if/when either approach is merged; because modifications to the maple
tree are more heavyweight than the rbtree, they block readers for longer.


The SPF approach is further along.  It has been tested in the past with
the maple tree, but not in the most recent iteration of either.  It
doesn't rely on the maple tree, but it does benefit.

The RCU-freeing-of-VMAs approach that I favour has not received much
attention.  I've been busy with other things ;-)  It offers much more
opportunity for performance improvement, but will take longer to arrive.