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]

Message-ID: <20220225190846.u4fwebimd5ejfdpd@revolver>
Date:   Fri, 25 Feb 2022 19:08:54 +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>
Subject: Re: [PATCH v6 00/71] Introducing the Maple Tree

* Qian Cai <quic_qiancai@...cinc.com> [220224 22:49]:
> 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
> 
> Just a heads-up. I noticed an use-after-free in today's linux-next below. I
> am running out of time to fully triage this, but I noticed this is the only
> series (not sure which revision) heavily touched mm/mmap.c recently there.
> 
>  BUG: KASAN: use-after-free in move_vma.isra.0
>  Read of size 8 at addr ffff0009ce752ac8 by task systemd-logind/1280
> 
>  CPU: 21 PID: 1280 Comm: systemd-logind Not tainted 5.17.0-rc5-next-20220223-dirty #242
>  Hardware name: MiTAC RAPTOR EV-883832-X3-0001/RAPTOR, BIOS 1.6 06/28/2020
>  Call trace:
>   dump_backtrace
>   show_stack
>   dump_stack_lvl
>   print_address_description.constprop.0
>   kasan_report
>   __asan_report_load8_noabort
>   move_vma.isra.0
>   move_vma at /usr/src/linux-next/mm/mremap.c:714
>   __do_sys_mremap
>   __arm64_sys_mremap
>   invoke_syscall
>   el0_svc_common.constprop.0
>   do_el0_svc
>   el0_svc
>   el0t_64_sync_handler
>   el0t_64_sync
> 
>  Allocated by task 1280:
>   kasan_save_stack
>   __kasan_slab_alloc
>   slab_post_alloc_hook
>   kmem_cache_alloc
>   vm_area_alloc
>   vm_area_alloc at /usr/src/linux-next/kernel/fork.c:455
>   mmap_region
>   mmap_region at /usr/src/linux-next/mm/mmap.c:2585
>   do_mmap
>   vm_mmap_pgoff
>   ksys_mmap_pgoff
>   __arm64_sys_mmap
>   invoke_syscall
>   el0_svc_common.constprop.0
>   do_el0_svc
>   el0_svc
>   el0t_64_sync_handler
>   el0t_64_sync
> 
>  Freed by task 1280:
>   kasan_save_stack
>   kasan_set_track
>   kasan_set_free_info
>   __kasan_slab_free
>   kmem_cache_free
>   vm_area_free
>   remove_vma
>   remove_vma at /usr/src/linux-next/mm/mmap.c:187
>   do_mas_align_munmap.isra.0
>   remove_mt at /usr/src/linux-next/mm/mmap.c:2176
>   (inlined by) do_mas_align_munmap at /usr/src/linux-next/mm/mmap.c:2437
>   do_mas_munmap
>   do_mas_munmap at /usr/src/linux-next/mm/mmap.c:2483
>   do_munmap
>   move_vma.isra.0
>   __do_sys_mremap
>   __arm64_sys_mremap
>   invoke_syscall
>   el0_svc_common.constprop.0
>   do_el0_svc
>   el0_svc
>   el0t_64_sync_handler
>   el0t_64_sync
> 
>  The buggy address belongs to the object at ffff0009ce752aa8
>   which belongs to the cache vm_area_struct of size 144
>  The buggy address is located 32 bytes inside of
>   144-byte region [ffff0009ce752aa8, ffff0009ce752b38)
>  The buggy address belongs to the page:
>  page:fffffc002739d400 refcount:1 mapcount:0 mapping:0000000000000000 index:0x0 pfn:0xa4e750
>  head:fffffc002739d400 order:2 compound_mapcount:0 compound_pincount:0
>  memcg:ffff0009ce456e01
>  flags: 0xbfffc0000010200(slab|head|node=0|zone=2|lastcpupid=0xffff)
>  raw: 0bfffc0000010200 fffffc002739f108 fffffc00273a3b08 ffff000800f53380
>  raw: 0000000000000000 0000000000210021 00000001ffffffff ffff0009ce456e01
>  page dumped because: kasan: bad access detected
> 
>  Memory state around the buggy address:
>   ffff0009ce752980: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
>   ffff0009ce752a00: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
>  >ffff0009ce752a80: fc fc fc fc fc fa fb fb fb fb fb fb fb fb fb fb
>                                                ^
>   ffff0009ce752b00: fb fb fb fb fb fb fb fc fc fc fc fc fc fc fc fc
>   ffff0009ce752b80: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc

Thank you for the report.  I will try to reproduce it with a kvm here.

Cheers,
Liam