linux-kernel - Re: [PATCH v6 00/71] Introducing the Maple Tree

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Mon, 28 Feb 2022 14:56:42 +0000
From:   Liam Howlett <liam.howlett@...cle.com>
To:     Vasily Gorbik <gor@...ux.ibm.com>
CC:     "maple-tree@...ts.infradead.org" <maple-tree@...ts.infradead.org>,
        "linux-mm@...ck.org" <linux-mm@...ck.org>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Heiko Carstens <hca@...ux.ibm.com>,
        Alexander Gordeev <agordeev@...ux.ibm.com>,
        Mark Brown <broonie@...nel.org>,
        Stephen Rothwell <sfr@...b.auug.org.au>
Subject: Re: [PATCH v6 00/71] Introducing the Maple Tree

* Vasily Gorbik <gor@...ux.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