[PATCH v6 00/71] Introducing the Maple Tree

Liam Howlett liam.howlett at oracle.com
Fri Feb 25 12:23:41 PST 2022


* Liam Howlett <liam.howlett at oracle.com> [220225 14:09]:
> * Qian Cai <quic_qiancai at quicinc.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.
> 

I just booted an arm64 VM with my build and kasan enabled with no issue.
Could you please send me your config file for the build?

Thanks,
Liam





More information about the maple-tree mailing list