[PATCH v6 00/71] Introducing the Maple Tree

[Liam Howlett]

* Vasily Gorbik <gor at linux.ibm.com> [220226 21:23]:
> On Tue, Feb 15, 2022 at 02:37:44PM +0000, Liam Howlett 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.
> > 
> > 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.
> > 
> > This patch is based on v5.17-rc4
> > 
> > git: https://github.com/oracle/linux-uek/tree/howlett/maple/20220214
> 
> Hi Liam,
> 
> this patch series completely breaks s390. Besides endianess issue
> in maple trees reported here:
> 
> https://lore.kernel.org/all/your-ad-here.call-01645924312-ext-0398@work.hours/
> 
> and with this endianess issue fixed (fixup from here ^^^) we still get numerous
> KASAN reports starting with
> 
> [PATCH v6 10/71] mm: Start tracking VMAs with maple tree

Thanks for looking at this.  That commit had two issues which I was
debugging on parisc for most of last week.  The first is that I was not
actually writing the stack expansion to the maple tree in that commit -
it was added in a later commit.  The second issue which was most likely
causing your crashes was the calculation for the gap in
unmapped_area_topdown().

With the maple tree (3dea5db7fbb5), I am able to boot parisc and s390
virtual machines.  Although, the issue which Hugh discusses in detail
still exists [1].  The latest maple tree can be found on github [2].  I
am still investigating why the heap changed locations on parisc to
ensure it's not of issue.

1: https://lore.kernel.org/all/5f8f4f-ad63-eb-fd73-d48748af8a76@google.com/
2: https://github.com/oracle/linux-uek/tree/maple/mainline

Regards,
Liam