lkml.org 
[lkml]   [2022]   [Feb]   [28]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
SubjectRe: [PATCH v6 00/71] Introducing the Maple Tree
Date
* Vasily Gorbik <gor@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
\
 
 \ /
  Last update: 2022-02-28 15:58    [W:0.515 / U:0.484 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site