linux-kernel - Re: [PATCH v8 00/70] 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]

Message-ID: <20220427165139.5s3qcj2u5vqrvwlc@revolver>
Date:   Wed, 27 Apr 2022 16:51:50 +0000
From:   Liam Howlett <liam.howlett@...cle.com>
To:     Qian Cai <quic_qiancai@...cinc.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>,
        Yu Zhao <yuzhao@...gle.com>
Subject: Re: [PATCH v8 00/70] Introducing the Maple Tree

* Qian Cai <quic_qiancai@...cinc.com> [220427 12:10]:
> On Tue, Apr 26, 2022 at 03:06:19PM +0000, Liam Howlett wrote:
> > Andrew,
> > 
> > Please replace the patches in your mglru-maple branch with this set.  It should
> > be a drop in replacement for my patch range with the fixes into these
> > patches.  Adding the preallocation to work around the fs-reclaim LOCKDEP
> > issue caused enough changes to the patches to warrant a respin.
> > 
> > The last patch on the branch is still needed to fix vmscan after mglru
> > is applied.  ee4b1fc24f30 "mm/vmscan: Use VMA_ITERATOR in
> > get_next_vma()"
> > 
> > 
> > Here is the pretty cover letter you requested last time.
> > 
> > ------------------------------------
> > 
> > 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 set is based on v5.18-rc2
> > 
> > git: https://github.com/oracle/linux-uek/tree/howlett/maple/20220426
> > 
> > v8 changes:
> >  - Added preallocations before any potential edits to the tree when holding the
> > i_mmap_lock to avoid fs-reclaim issues on extreme memory pressure.
> >  - Fixed issue in mempolicy mas_for_each() loop.
> >  - Moved static definitions inside ifdef for DEBUG_MAPLE
> >  - Fixed compile warnings reported by build bots
> >  - Moved mas_dfs_preorder() to testing code
> >  - Changed __vma_adjust() to record the highest vma in case 6 instead of
> > finding it twice.
> >  - Fixed locking issue in exit_mmap()
> >  - Fixed up from/s-o-b ordering
> 
> Running some syscall fuzzer would trigger a crash.
> 
>  BUG: KASAN: use-after-free in mas_find
>  ma_dead_node at lib/maple_tree.c:532
>  (inlined by) mas_next_entry at lib/maple_tree.c:4637
>  (inlined by) mas_find at lib/maple_tree.c:5869
>  Read of size 8 at addr ffff88811c5e9c00 by task trinity-c0/1351
> 
>  CPU: 5 PID: 1351 Comm: trinity-c0 Not tainted 5.18.0-rc4-next-20220427 #3
>  Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-5.fc35 04/01/2014
>  Call Trace:
>   <TASK>
>   dump_stack_lvl
>   print_address_description.constprop.0.cold
>   print_report.cold
>   kasan_report
>   mas_find
>   apply_mlockall_flags


Thanks.  This is indeed an issue with 0d43186b36c1 (mm/mlock: use vma
iterator and instead of vma linked list)                                                 

Andrew, Please include this patch as a fix.

Thanks,
Liam

View attachment "0001-mm-mlock-Use-maple-state-in-apply_mlockall_flags.patch" of type "text/x-diff" (1576 bytes)