linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Qian Cai <quic_qiancai@quicinc.com>
To: Liam Howlett <liam.howlett@oracle.com>
Cc: "maple-tree@lists.infradead.org" <maple-tree@lists.infradead.org>,
	"linux-mm@kvack.org" <linux-mm@kvack.org>,
	"linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
	Andrew Morton <akpm@linux-foundation.org>,
	"Yu Zhao" <yuzhao@google.com>
Subject: Re: [PATCH v8 00/70] Introducing the Maple Tree
Date: Wed, 27 Apr 2022 12:10:33 -0400	[thread overview]
Message-ID: <20220427161033.GA1935@qian> (raw)
In-Reply-To: <20220426150616.3937571-1-Liam.Howlett@oracle.com>

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
  __do_sys_munlockall
  do_syscall_64
  entry_SYSCALL_64_after_hwframe
 RIP: 0033:0x7f3105611a3d
 Code: 5b 41 5c c3 66 0f 1f 84 00 00 00 00 00 f3 0f 1e fa 48 89 f8 48 89 f7 48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 4c 8b 4c 24 08 0f 05 <48> 3d 01 f0 ff ff 738
 RSP: 002b:00007ffeefae7c68 EFLAGS: 00000246 ORIG_RAX: 0000000000000098
 RAX: ffffffffffffffda RBX: 0000000000000002 RCX: 00007f3105611a3d
 RDX: 00000000ffff0000 RSI: ffffffffffffafff RDI: 0000009357075a39
 RBP: 00007f3103f94000 R08: 00000000fffffff7 R09: 000000000000006b
 R10: fffffffffffffffd R11: 0000000000000246 R12: 0000000000000098
 R13: 00007f31054f06c0 R14: 00007f3103f94058 R15: 00007f3103f94000
  </TASK>

 Allocated by task 1351:
  kasan_save_stack
  __kasan_slab_alloc
  kmem_cache_alloc_bulk
  mas_alloc_nodes
  mas_preallocate
  __vma_adjust
  __split_vma
  do_mas_align_munmap.constprop.0
  __vm_munmap
  __x64_sys_munmap
  do_syscall_64
  entry_SYSCALL_64_after_hwframe

 Freed by task 1351:
  kasan_save_stack
  kasan_set_track
  kasan_set_free_info
  ____kasan_slab_free
  slab_free_freelist_hook
  kmem_cache_free_bulk.part.0
  mas_destroy
  mas_store_prealloc
  __vma_adjust
  vma_merge
  mlock_fixup
  apply_mlockall_flags
  __do_sys_munlockall
  do_syscall_64
  entry_SYSCALL_64_after_hwframe

 The buggy address belongs to the object at ffff88811c5e9c00
  which belongs to the cache maple_node of size 256
 The buggy address is located 0 bytes inside of
  256-byte region [ffff88811c5e9c00, ffff88811c5e9d00)

 The buggy address belongs to the physical page:
 page:ffffea0004717a00 refcount:1 mapcount:0 mapping:0000000000000000 index:0x0 pfn:0x11c5e8
 head:ffffea0004717a00 order:2 compound_mapcount:0 compound_pincount:0
 flags: 0x200000000010200(slab|head|node=0|zone=2)
 raw: 0200000000010200 ffffea0004f8da08 ffffea0004676a08 ffff888100050940
 raw: 0000000000000000 0000000000150015 00000001ffffffff 0000000000000000
 page dumped because: kasan: bad access detected

 Memory state around the buggy address:
  ffff88811c5e9b00: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
  ffff88811c5e9b80: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
 >ffff88811c5e9c00: fa fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb
                    ^
  ffff88811c5e9c80: fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb
  ffff88811c5e9d00: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
 ==================================================================
 Disabling lock debugging due to kernel taint
 general protection fault, probably for non-canonical address 0xdffffc0000000001: 0000 [#1] PREEMPT SMP KASAN PTI
 KASAN: null-ptr-deref in range [0x0000000000000008-0x000000000000000f]
 CPU: 5 PID: 1351 Comm: trinity-c0 Tainted: G    B             5.18.0-rc4-next-20220427 #3
 Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-5.fc35 04/01/2014
 RIP: 0010:mas_ascend
 Code: cb 18 41 89 d3 48 83 cb 04 41 83 f3 01 40 84 ed 40 0f 95 c7 41 20 fb 74 26 83 ee 01 48 63 f6 48 8d 14 f1 48 89 d6 48 c1 ee 03 <42> 80 3c 3e 00 0f 854
 RSP: 0018:ffffc9000279fc78 EFLAGS: 00010202
 RAX: 0000000000000000 RBX: ffff888106dc3504 RCX: 0000000000000000
 RDX: 0000000000000008 RSI: 0000000000000001 RDI: ffff88811d42e201
 RBP: 0000000000000002 R08: 0000000000000000 R09: ffff88810f723300
 R10: ffffffffffffffff R11: 0000000000000001 R12: ffffc9000279fe78
 R13: 0000000000000000 R14: ffff888106dc3500 R15: dffffc0000000000
 FS:  00007f31054f0740(0000) GS:ffff8882d2e80000(0000) knlGS:0000000000000000
 CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
 CR2: 00007f3104db847c CR3: 0000000127e80002 CR4: 0000000000370ee0
 DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
 DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400
 Call Trace:
  <TASK>
  mas_next_node
  mas_find
  apply_mlockall_flags
  __do_sys_munlockall
  do_syscall_64
  entry_SYSCALL_64_after_hwframe
 RIP: 0033:0x7f3105611a3d
 Code: 5b 41 5c c3 66 0f 1f 84 00 00 00 00 00 f3 0f 1e fa 48 89 f8 48 89 f7 48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 4c 8b 4c 24 08 0f 05 <48> 3d 01 f0 ff ff 738
 RSP: 002b:00007ffeefae7c68 EFLAGS: 00000246 ORIG_RAX: 0000000000000098
 RAX: ffffffffffffffda RBX: 0000000000000002 RCX: 00007f3105611a3d
 RDX: 00000000ffff0000 RSI: ffffffffffffafff RDI: 0000009357075a39
 RBP: 00007f3103f94000 R08: 00000000fffffff7 R09: 000000000000006b
 R10: fffffffffffffffd R11: 0000000000000246 R12: 0000000000000098
 R13: 00007f31054f06c0 R14: 00007f3103f94058 R15: 00007f3103f94000
  </TASK>
 Modules linked in:
 ---[ end trace 0000000000000000 ]---
 RIP: 0010:mas_ascend
 Code: cb 18 41 89 d3 48 83 cb 04 41 83 f3 01 40 84 ed 40 0f 95 c7 41 20 fb 74 26 83 ee 01 48 63 f6 48 8d 14 f1 48 89 d6 48 c1 ee 03 <42> 80 3c 3e 00 0f 854
 RSP: 0018:ffffc9000279fc78 EFLAGS: 00010202
 RAX: 0000000000000000 RBX: ffff888106dc3504 RCX: 0000000000000000
 RDX: 0000000000000008 RSI: 0000000000000001 RDI: ffff88811d42e201
 RBP: 0000000000000002 R08: 0000000000000000 R09: ffff88810f723300
 R10: ffffffffffffffff R11: 0000000000000001 R12: ffffc9000279fe78
 R13: 0000000000000000 R14: ffff888106dc3500 R15: dffffc0000000000
 FS:  00007f31054f0740(0000) GS:ffff8882d2e80000(0000) knlGS:0000000000000000
 CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
 CR2: 00007f3104db847c CR3: 0000000127e80002 CR4: 0000000000370ee0
 DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
 DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400
 Kernel panic - not syncing: Fatal exception
 Kernel Offset: 0x15400000 from 0xffffffff81000000 (relocation range: 0xffffffff80000000-0xffffffffbfffffff)

  parent reply	other threads:[~2022-04-27 16:15 UTC|newest]

Thread overview: 114+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-04-26 15:06 [PATCH v8 00/70] Introducing the Maple Tree Liam Howlett
2022-04-26 15:06 ` [PATCH v8 01/70] radix tree test suite: add pr_err define Liam Howlett
2022-04-26 15:06 ` [PATCH v8 02/70] radix tree test suite: add kmem_cache_set_non_kernel() Liam Howlett
2022-04-26 15:06 ` [PATCH v8 05/70] radix tree test suite: add lockdep_is_held to header Liam Howlett
2022-04-26 15:06 ` [PATCH v8 03/70] radix tree test suite: add allocation counts and size to kmem_cache Liam Howlett
2022-04-26 15:06 ` [PATCH v8 04/70] radix tree test suite: add support for slab bulk APIs Liam Howlett
2022-04-26 15:06 ` [PATCH v8 06/70] mips: rename mt_init to mips_mt_init Liam Howlett
2022-04-26 15:06 ` [PATCH v8 07/70] Maple Tree: add new data structure Liam Howlett
2022-04-27 15:45   ` Liam Howlett
2022-04-26 15:06 ` [PATCH v8 08/70] lib/test_maple_tree: add testing for maple tree Liam Howlett
2022-04-26 15:06 ` [PATCH v8 09/70] mm: start tracking VMAs with " Liam Howlett
2022-04-26 15:06 ` [PATCH v8 10/70] mm: add VMA iterator Liam Howlett
2022-04-26 15:06 ` [PATCH v8 12/70] mm/mmap: use the maple tree in find_vma() instead of the rbtree Liam Howlett
2022-04-26 15:06 ` [PATCH v8 11/70] mmap: use the VMA iterator in count_vma_pages_range() Liam Howlett
2022-04-26 15:06 ` [PATCH v8 13/70] mm/mmap: use the maple tree for find_vma_prev() instead of the rbtree Liam Howlett
2022-04-26 15:06 ` [PATCH v8 14/70] mm/mmap: use maple tree for unmapped_area{_topdown} Liam Howlett
2022-04-26 15:06 ` [PATCH v8 15/70] kernel/fork: use maple tree for dup_mmap() during forking Liam Howlett
2022-04-26 15:06 ` [PATCH v8 17/70] proc: remove VMA rbtree use from nommu Liam Howlett
2022-04-26 15:06 ` [PATCH v8 16/70] damon: Convert __damon_va_three_regions to use the VMA iterator Liam Howlett
2022-05-03 23:40   ` SeongJae Park
2022-04-26 15:06 ` [PATCH v8 18/70] mm: remove rb tree Liam Howlett
2022-04-26 15:06 ` [PATCH v8 21/70] mm: optimize find_exact_vma() to use vma_lookup() Liam Howlett
2022-04-26 15:06 ` [PATCH v8 20/70] xen: use vma_lookup() in privcmd_ioctl_mmap() Liam Howlett
2022-04-26 15:06 ` [PATCH v8 19/70] mmap: change zeroing of maple tree in __vma_adjust() Liam Howlett
2022-04-26 15:06 ` [PATCH v8 22/70] mm/khugepaged: optimize collapse_pte_mapped_thp() by using vma_lookup() Liam Howlett
2022-04-26 15:06 ` [PATCH v8 23/70] mm/mmap: change do_brk_flags() to expand existing VMA and add do_brk_munmap() Liam Howlett
2022-04-28 16:09   ` Guenter Roeck
2022-04-28 16:35     ` Liam Howlett
2022-04-28 17:13       ` Guenter Roeck
2022-04-28 20:19   ` Guenter Roeck
2022-04-29  0:38     ` Liam Howlett
2022-04-29  1:16       ` Andrew Morton
2022-05-02  0:14         ` Liam Howlett
2022-05-02  0:24           ` Andrew Morton
2022-05-02 10:18             ` Heiko Carstens
2022-05-02 13:31               ` Liam Howlett
2022-05-02 18:50                 ` Heiko Carstens
2022-05-03 19:48                   ` Heiko Carstens
2022-05-03 21:55                     ` Liam Howlett
2022-05-04  7:37                       ` Janosch Frank
2022-05-04 18:31                         ` David Hildenbrand
2022-05-04 18:47                           ` Liam Howlett
2022-06-29  7:04                           ` qemu-system-s390x hang in tcg (was: Re: [PATCH v8 23/70] mm/mmap: change do_brk_flags() to expand existing VMA and add do_brk_munmap()) Sven Schnelle
2022-06-29  8:10                             ` Alex Bennée
2022-06-29 10:46                               ` qemu-system-s390x hang in tcg Sven Schnelle
2022-06-29 12:18                                 ` Sven Schnelle
2022-06-29 14:52                                   ` Alex Bennée
2022-06-30  3:03                                 ` Richard Henderson
2022-05-02  7:08           ` [PATCH v8 23/70] mm/mmap: change do_brk_flags() to expand existing VMA and add do_brk_munmap() Juergen Gross
2022-04-26 15:06 ` [PATCH v8 26/70] mm: remove vmacache Liam Howlett
2022-04-26 15:06 ` [PATCH v8 25/70] mm/mmap: use advanced maple tree API for mmap_region() Liam Howlett
2022-04-26 15:06 ` [PATCH v8 24/70] mm: use maple tree operations for find_vma_intersection() Liam Howlett
2022-04-26 15:06 ` [PATCH v8 27/70] mm: convert vma_lookup() to use mtree_load() Liam Howlett
2022-04-26 15:06 ` [PATCH v8 28/70] mm/mmap: move mmap_region() below do_munmap() Liam Howlett
2022-04-26 15:06 ` [PATCH v8 31/70] arm64: remove mmap linked list from vdso Liam Howlett
2022-04-26 15:06 ` [PATCH v8 29/70] mm/mmap: reorganize munmap to use maple states Liam Howlett
2022-04-26 15:06 ` [PATCH v8 30/70] mm/mmap: change do_brk_munmap() to use do_mas_align_munmap() Liam Howlett
2022-04-26 15:06 ` [PATCH v8 34/70] powerpc: remove mmap linked list walks Liam Howlett
2022-04-26 15:06 ` [PATCH v8 32/70] arm64: Change elfcore for_each_mte_vma() to use VMA iterator Liam Howlett
2022-04-26 15:06 ` [PATCH v8 33/70] parisc: remove mmap linked list from cache handling Liam Howlett
2022-04-26 15:06 ` [PATCH v8 35/70] s390: remove vma linked list walks Liam Howlett
2022-04-26 15:06 ` [PATCH v8 37/70] xtensa: " Liam Howlett
2022-04-26 15:06 ` [PATCH v8 36/70] x86: " Liam Howlett
2022-04-26 15:06 ` [PATCH v8 38/70] cxl: remove vma linked list walk Liam Howlett
2022-04-26 15:06 ` [PATCH v8 39/70] optee: " Liam Howlett
2022-04-26 15:06 ` [PATCH v8 40/70] um: " Liam Howlett
2022-04-26 15:06 ` [PATCH v8 41/70] coredump: " Liam Howlett
2022-04-26 15:06 ` [PATCH v8 43/70] fs/proc/base: use maple tree iterators in place of linked list Liam Howlett
2022-04-26 15:06 ` [PATCH v8 42/70] exec: use VMA iterator instead " Liam Howlett
2022-04-26 15:06 ` [PATCH v8 45/70] userfaultfd: use maple tree iterator to iterate VMAs Liam Howlett
2022-04-27 15:43   ` Liam Howlett
2022-04-26 15:06 ` [PATCH v8 44/70] fs/proc/task_mmu: stop using linked list and highest_vm_end Liam Howlett
2022-04-26 15:06 ` [PATCH v8 48/70] perf: use VMA iterator Liam Howlett
2022-04-26 15:06 ` [PATCH v8 46/70] ipc/shm: use VMA iterator instead of linked list Liam Howlett
2022-04-26 15:06 ` [PATCH v8 47/70] acct: " Liam Howlett
2022-04-26 15:06 ` [PATCH v8 49/70] sched: use maple tree iterator to walk VMAs Liam Howlett
2022-04-26 15:06 ` [PATCH v8 50/70] fork: use VMA iterator Liam Howlett
2022-04-26 15:06 ` [PATCH v8 53/70] mm/khugepaged: stop using vma linked list Liam Howlett
2022-04-26 15:06 ` [PATCH v8 51/70] bpf: remove VMA " Liam Howlett
2022-04-26 15:06 ` [PATCH v8 52/70] mm/gup: use maple tree navigation instead of " Liam Howlett
2022-04-26 15:06 ` [PATCH v8 56/70] mm/memcontrol: stop using mm->highest_vm_end Liam Howlett
2022-04-26 15:06 ` [PATCH v8 55/70] mm/madvise: use vma_find() instead of vma linked list Liam Howlett
2022-04-26 15:06 ` [PATCH v8 54/70] mm/ksm: use vma iterators " Liam Howlett
2022-04-26 15:06 ` [PATCH v8 59/70] mm/mprotect: use maple tree navigation " Liam Howlett
2022-04-26 15:06 ` [PATCH v8 58/70] mm/mlock: use vma iterator and " Liam Howlett
2022-04-26 15:06 ` [PATCH v8 57/70] mm/mempolicy: use vma iterator & maple state " Liam Howlett
2022-04-26 15:06 ` [PATCH v8 61/70] mm/msync: use vma_find() " Liam Howlett
2022-04-26 15:06 ` [PATCH v8 60/70] mm/mremap: use vma_find_intersection() " Liam Howlett
2022-04-26 15:06 ` [PATCH v8 63/70] mm/pagewalk: use vma_find() " Liam Howlett
2022-04-26 15:06 ` [PATCH v8 62/70] mm/oom_kill: use maple tree iterators " Liam Howlett
2022-04-26 15:06 ` [PATCH v8 64/70] mm/swapfile: use vma iterator " Liam Howlett
2022-04-26 15:06 ` [PATCH v8 66/70] nommu: remove uses of VMA " Liam Howlett
2022-04-28 16:05   ` Guenter Roeck
2022-04-28 16:31   ` Guenter Roeck
2022-04-29 20:16     ` Liam Howlett
2022-04-26 15:06 ` [PATCH v8 65/70] i915: use the VMA iterator Liam Howlett
2022-04-26 15:06 ` [PATCH v8 67/70] riscv: use vma iterator for vdso Liam Howlett
2022-04-26 15:06 ` [PATCH v8 68/70] mm: remove the vma linked list Liam Howlett
2022-04-26 15:06 ` [PATCH v8 69/70] mm/mmap: drop range_has_overlap() function Liam Howlett
2022-04-26 15:06 ` [PATCH v8 70/70] mm/mmap.c: pass in mapping to __vma_link_file() Liam Howlett
2022-04-26 20:06 ` [PATCH v8 00/70] Introducing the Maple Tree Andrew Morton
2022-04-26 20:08 ` Andrew Morton
2022-04-26 20:23   ` Matthew Wilcox
2022-04-27 14:08   ` Liam Howlett
2022-04-27 17:33     ` Andrew Morton
2022-04-27 18:12       ` Matthew Wilcox
2022-05-01 20:26         ` Davidlohr Bueso
2022-05-01 23:56           ` Andrew Morton
2022-05-04  0:43             ` Liam Howlett
2022-04-28  2:28       ` Liam Howlett
2022-04-27 16:10 ` Qian Cai [this message]
2022-04-27 16:51   ` Liam Howlett
2022-04-27 20:21     ` Qian Cai
2022-04-27 22:41       ` Liam Howlett

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20220427161033.GA1935@qian \
    --to=quic_qiancai@quicinc.com \
    --cc=akpm@linux-foundation.org \
    --cc=liam.howlett@oracle.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-mm@kvack.org \
    --cc=maple-tree@lists.infradead.org \
    --cc=yuzhao@google.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).