[PATCH v6 00/71] Introducing the Maple Tree

[Matthew Wilcox]

On Wed, Feb 23, 2022 at 04:35:09PM +0000, Mel Gorman wrote:
> On Wed, Feb 16, 2022 at 08:24:34PM +0000, Matthew Wilcox wrote:
> > 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.
> 
> I'm way behind and only got around to looking at SPF properly today. Maple
> is working its way up my list and I need to gather new data but I did
> have old data queued from a time when I thought I would get around to
> maple tree soon.  The big result that stood was was brk performance from
> will-it-scale but for processes specifically

Yup, we know about the brk1 regression.  It's a really unrealistic
benchmark, which is why we added brk2.  To quote the commit message:

    Linux has this horrendously complicated anon_vma structure that you don't
    care about, but the upshot is that after calling fork(), each process
    that calls brk() gets a _new_ VMA created.  That is, after calling brk()
    the first time, the process address space looks like this:

    557777fab000-557777ff0000 rw-p 00000000 00:00 0                          [heap]
    557777ff0000-557777ff1000 rw-p 00000000 00:00 0                          [heap]

    so what brk1 is actually testing is how long it takes to create & destroy
    a new VMA.  This does not match what most programs do -- most will call
    exec() which resets the anon_vma structures and starts each program off
    with its own heap.  And if you do have a multi-process program which
    uses brk(), chances are it doesn't just oscillate betwee zero and one
    extra pages of heap compared to its parent.

    A better test starts out by allocating one page on the heap and then
    throbs between one and two pages instead of throbbing between zero and
    one page.  That means we're actually testing expanding and contracting
    the heap instead of creating and destroying a new heap.

    For realism, I wanted to add actually accessing the memory in the new
    heap, but that doesn't work for the threaded case -- another thread
    might remove the memory you just allocated while you're allocating it.
    Threaded programs give each thread its own heap anyway, so this is
    kind of a pointless syscall to ask about its threaded scalability.
    
    Anyway, here's brk2.c.  It is not very different from brk1.c, but the
    performance results are quite different (actually worse by about 10-15%).