All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH v12 00/69] Introducing the Maple Tree
@ 2022-07-20  2:17 Liam Howlett
  2022-07-20  2:17 ` [PATCH v12 02/69] radix tree test suite: add pr_err define Liam Howlett
                   ` (69 more replies)
  0 siblings, 70 replies; 85+ messages in thread
From: Liam Howlett @ 2022-07-20  2:17 UTC (permalink / raw)
  To: maple-tree, linux-mm, linux-kernel, Andrew Morton, Hugh Dickins; +Cc: Yu Zhao

Hello,

This is the v11 + fixes.  I used the mm-unstable branch and patched in
place.

git: https://github.com/oracle/linux-uek/tree/howlett/maple/20220719

Patch series "Introducing the Maple Tree".

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.  If you use an rbtree with other data
structures to improve performance or an interval tree to track
non-overlapping ranges, then this is for you.

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.

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_lock contention.

The plan is to get to the point where we use the maple tree in RCU mode.
Readers will not block for writers.  A single write operation will be
allowed at a time.  A reader re-walks if stale data is encountered.  VMAs
would be RCU enabled and this mode would be entered once multiple tasks
are using the mm_struct.

Davidlor said

: Yes I like the maple tree, and at this stage I don't think we can ask for
: more from this series wrt the MM - albeit there seems to still be some
: folks reporting breakage.  Fundamentally I see Liam's work to (re)move
: complexity out of the MM (not to say that the actual maple tree is not
: complex) by consolidating the three complimentary data structures very
: much worth it considering performance does not take a hit.  This was very
: much a turn off with the range locking approach, which worst case scenario
: incurred in prohibitive overhead.  Also as Liam and Matthew have
: mentioned, RCU opens up a lot of nice performance opportunities, and in
: addition academia[1] has shown outstanding scalability of address spaces
: with the foundation of replacing the locked rbtree with RCU aware trees.

A similar work has been discovered in the academic press

	https://pdos.csail.mit.edu/papers/rcuvm:asplos12.pdf

Sheer coincidence.  We designed our tree with the intention of solving the
hardest problem first.  Upon settling on a b-tree variant and a rough
outline, we researched ranged based b-trees and RCU b-trees and did find
that article.  So it was nice to find reassurances that we were on the
right path, but our design choice of using ranges made that paper unusable
for us.

Changes:
 - maple_tree: Fix bitwise for logical operator in mas_validate_limits()
   - Thanks Dan Carpenter
 - maple_tree: Drop typedef from header - Thanks Matthew Wilcox and Li
   Hongyu
 - maple_tree: Fix mas_empty_area() wrapping - Thanks Sven Schnelle
 - mm/mmap: Drop VM_BUG_ON() until better tested - Thanks Yu Zhao
 - mmap: Fix hugetlb accounting error in __split_vma()
 - mmap: remove unroll from vma_expand() - Thanks Hugh Dickins
 - mmap: remove unroll from __vma_adjust() - Thanks Hugh Dickins
 - mmap: remove do_brk_munmap() optimization - Thanks Hugh Dickins

v11: https://lore.kernel.org/linux-mm/20220717024615.2106835-1-Liam.Howlett@oracle.com/
v10: https://lore.kernel.org/linux-mm/20220621204632.3370049-1-Liam.Howlett@oracle.com/
v9: https://lore.kernel.org/lkml/20220504010716.661115-1-Liam.Howlett@oracle.com/
...and
https://lore.kernel.org/lkml/20220504011215.661968-1-Liam.Howlett@oracle.com/

v8: https://lore.kernel.org/lkml/20220426150616.3937571-1-Liam.Howlett@oracle.com/
v7: https://lore.kernel.org/linux-mm/20220404143501.2016403-8-Liam.Howlett@oracle.com/
v6: https://lore.kernel.org/linux-mm/20220215143728.3810954-1-Liam.Howlett@oracle.com/
v5: https://lore.kernel.org/linux-mm/20220202024137.2516438-1-Liam.Howlett@oracle.com/
v4: https://lore.kernel.org/linux-mm/20211201142918.921493-1-Liam.Howlett@oracle.com/
v3: https://lore.kernel.org/linux-mm/20211005012959.1110504-1-Liam.Howlett@oracle.com/
v2: https://lore.kernel.org/linux-mm/20210817154651.1570984-1-Liam.Howlett@oracle.com/
v1: https://lore.kernel.org/linux-mm/20210428153542.2814175-1-Liam.Howlett@Oracle.com/

Liam R. Howlett (44):
  Maple Tree: add new data structure
  radix tree test suite: add pr_err define
  radix tree test suite: add kmem_cache_set_non_kernel()
  radix tree test suite: add allocation counts and size to kmem_cache
  radix tree test suite: add support for slab bulk APIs
  radix tree test suite: add lockdep_is_held to header
  lib/test_maple_tree: add testing for maple tree
  mm: start tracking VMAs with maple tree
  mm/mmap: use the maple tree in find_vma() instead of the rbtree.
  mm/mmap: use the maple tree for find_vma_prev() instead of the rbtree
  mm/mmap: use maple tree for unmapped_area{_topdown}
  kernel/fork: use maple tree for dup_mmap() during forking
  damon: convert __damon_va_three_regions to use the VMA iterator
  mm: remove rb tree.
  mmap: change zeroing of maple tree in __vma_adjust()
  xen: use vma_lookup() in privcmd_ioctl_mmap()
  mm: optimize find_exact_vma() to use vma_lookup()
  mm/khugepaged: optimize collapse_pte_mapped_thp() by using
    vma_lookup()
  mm/mmap: change do_brk_flags() to expand existing VMA and add
    do_brk_munmap()
  mm: use maple tree operations for find_vma_intersection()
  mm/mmap: use advanced maple tree API for mmap_region()
  mm: remove vmacache
  mm: convert vma_lookup() to use mtree_load()
  mm/mmap: move mmap_region() below do_munmap()
  mm/mmap: reorganize munmap to use maple states
  mm/mmap: change do_brk_munmap() to use do_mas_align_munmap()
  arm64: Change elfcore for_each_mte_vma() to use VMA iterator
  fs/proc/base: use maple tree iterators in place of linked list
  userfaultfd: use maple tree iterator to iterate VMAs
  ipc/shm: use VMA iterator instead of linked list
  bpf: remove VMA linked list
  mm/gup: use maple tree navigation instead of linked list
  mm/madvise: use vma_find() instead of vma linked list
  mm/memcontrol: stop using mm->highest_vm_end
  mm/mempolicy: use vma iterator & maple state instead of vma linked
    list
  mm/mprotect: use maple tree navigation instead of vma linked list
  mm/mremap: use vma_find_intersection() instead of vma linked list
  mm/msync: use vma_find() instead of vma linked list
  mm/oom_kill: use maple tree iterators instead of vma linked list
  mm/swapfile: use vma iterator instead of vma linked list
  riscv: use vma iterator for vdso
  mm: remove the vma linked list
  mm/mmap: drop range_has_overlap() function
  mm/mmap.c: pass in mapping to __vma_link_file()

Matthew Wilcox (Oracle) (25):
  mm: add VMA iterator
  mmap: use the VMA iterator in count_vma_pages_range()
  proc: remove VMA rbtree use from nommu
  arm64: remove mmap linked list from vdso
  parisc: remove mmap linked list from cache handling
  powerpc: remove mmap linked list walks
  s390: remove vma linked list walks
  x86: remove vma linked list walks
  xtensa: remove vma linked list walks
  cxl: remove vma linked list walk
  optee: remove vma linked list walk
  um: remove vma linked list walk
  coredump: remove vma linked list walk
  exec: use VMA iterator instead of linked list
  fs/proc/task_mmu: stop using linked list and highest_vm_end
  acct: use VMA iterator instead of linked list
  perf: use VMA iterator
  sched: use maple tree iterator to walk VMAs
  fork: use VMA iterator
  mm/khugepaged: stop using vma linked list
  mm/ksm: use vma iterators instead of vma linked list
  mm/mlock: use vma iterator and maple state instead of vma linked list
  mm/pagewalk: use vma_find() instead of vma linked list
  i915: use the VMA iterator
  nommu: remove uses of VMA linked list

 Documentation/core-api/index.rst              |     1 +
 Documentation/core-api/maple_tree.rst         |   217 +
 MAINTAINERS                                   |    12 +
 arch/arm64/kernel/elfcore.c                   |    16 +-
 arch/arm64/kernel/vdso.c                      |     3 +-
 arch/parisc/kernel/cache.c                    |     9 +-
 arch/powerpc/kernel/vdso.c                    |     6 +-
 arch/powerpc/mm/book3s32/tlb.c                |    11 +-
 arch/powerpc/mm/book3s64/subpage_prot.c       |    13 +-
 arch/riscv/kernel/vdso.c                      |     3 +-
 arch/s390/kernel/vdso.c                       |     3 +-
 arch/s390/mm/gmap.c                           |     6 +-
 arch/um/kernel/tlb.c                          |    14 +-
 arch/x86/entry/vdso/vma.c                     |     9 +-
 arch/x86/kernel/tboot.c                       |     2 +-
 arch/xtensa/kernel/syscall.c                  |    18 +-
 drivers/firmware/efi/efi.c                    |     2 +-
 drivers/gpu/drm/i915/gem/i915_gem_userptr.c   |    14 +-
 drivers/misc/cxl/fault.c                      |    45 +-
 drivers/tee/optee/call.c                      |    18 +-
 drivers/xen/privcmd.c                         |     2 +-
 fs/coredump.c                                 |    34 +-
 fs/exec.c                                     |    12 +-
 fs/proc/base.c                                |     5 +-
 fs/proc/internal.h                            |     2 +-
 fs/proc/task_mmu.c                            |    74 +-
 fs/proc/task_nommu.c                          |    45 +-
 fs/userfaultfd.c                              |    62 +-
 include/linux/maple_tree.h                    |   684 +
 include/linux/mm.h                            |    78 +-
 include/linux/mm_types.h                      |    43 +-
 include/linux/mm_types_task.h                 |    12 -
 include/linux/sched.h                         |     1 -
 include/linux/userfaultfd_k.h                 |     7 +-
 include/linux/vm_event_item.h                 |     4 -
 include/linux/vmacache.h                      |    28 -
 include/linux/vmstat.h                        |     6 -
 include/trace/events/maple_tree.h             |   123 +
 include/trace/events/mmap.h                   |    73 +
 init/main.c                                   |     2 +
 ipc/shm.c                                     |    21 +-
 kernel/acct.c                                 |    11 +-
 kernel/bpf/task_iter.c                        |    10 +-
 kernel/debug/debug_core.c                     |    12 -
 kernel/events/core.c                          |     3 +-
 kernel/events/uprobes.c                       |     9 +-
 kernel/fork.c                                 |    57 +-
 kernel/sched/fair.c                           |    10 +-
 lib/Kconfig.debug                             |    17 +-
 lib/Makefile                                  |     3 +-
 lib/maple_tree.c                              |  7102 +++
 lib/test_maple_tree.c                         | 38206 ++++++++++++++++
 mm/Makefile                                   |     2 +-
 mm/damon/vaddr-test.h                         |    36 +-
 mm/damon/vaddr.c                              |    53 +-
 mm/debug.c                                    |    14 +-
 mm/gup.c                                      |     7 +-
 mm/huge_memory.c                              |     4 +-
 mm/init-mm.c                                  |     4 +-
 mm/internal.h                                 |     8 +-
 mm/khugepaged.c                               |    13 +-
 mm/ksm.c                                      |    18 +-
 mm/madvise.c                                  |     2 +-
 mm/memcontrol.c                               |     6 +-
 mm/memory.c                                   |    33 +-
 mm/mempolicy.c                                |    56 +-
 mm/mlock.c                                    |    35 +-
 mm/mmap.c                                     |  2156 +-
 mm/mprotect.c                                 |     7 +-
 mm/mremap.c                                   |    22 +-
 mm/msync.c                                    |     2 +-
 mm/nommu.c                                    |   249 +-
 mm/oom_kill.c                                 |     3 +-
 mm/pagewalk.c                                 |     2 +-
 mm/swapfile.c                                 |     4 +-
 mm/util.c                                     |    32 -
 mm/vmacache.c                                 |   117 -
 mm/vmstat.c                                   |     4 -
 tools/include/linux/slab.h                    |     4 +
 tools/testing/radix-tree/.gitignore           |     2 +
 tools/testing/radix-tree/Makefile             |     9 +-
 tools/testing/radix-tree/generated/autoconf.h |     1 +
 tools/testing/radix-tree/linux.c              |   160 +-
 tools/testing/radix-tree/linux/kernel.h       |     1 +
 tools/testing/radix-tree/linux/lockdep.h      |     2 +
 tools/testing/radix-tree/linux/maple_tree.h   |     7 +
 tools/testing/radix-tree/maple.c              |    59 +
 .../radix-tree/trace/events/maple_tree.h      |     5 +
 88 files changed, 48439 insertions(+), 1880 deletions(-)
 create mode 100644 Documentation/core-api/maple_tree.rst
 create mode 100644 include/linux/maple_tree.h
 delete mode 100644 include/linux/vmacache.h
 create mode 100644 include/trace/events/maple_tree.h
 create mode 100644 lib/maple_tree.c
 create mode 100644 lib/test_maple_tree.c
 delete mode 100644 mm/vmacache.c
 create mode 100644 tools/testing/radix-tree/linux/maple_tree.h
 create mode 100644 tools/testing/radix-tree/maple.c
 create mode 100644 tools/testing/radix-tree/trace/events/maple_tree.h

-- 
2.35.1

^ permalink raw reply	[flat|nested] 85+ messages in thread

end of thread, other threads:[~2022-08-02 10:38 UTC | newest]

Thread overview: 85+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-07-20  2:17 [PATCH v12 00/69] Introducing the Maple Tree Liam Howlett
2022-07-20  2:17 ` [PATCH v12 02/69] radix tree test suite: add pr_err define Liam Howlett
2022-07-20  2:17 ` [PATCH v12 03/69] radix tree test suite: add kmem_cache_set_non_kernel() Liam Howlett
2022-07-20  2:17 ` [PATCH v12 01/69] Maple Tree: add new data structure Liam Howlett
2022-07-20  2:17 ` [PATCH v12 05/69] radix tree test suite: add support for slab bulk APIs Liam Howlett
2022-07-20  2:17 ` [PATCH v12 04/69] radix tree test suite: add allocation counts and size to kmem_cache Liam Howlett
2022-07-20  2:17 ` [PATCH v12 06/69] radix tree test suite: add lockdep_is_held to header Liam Howlett
2022-07-20  2:17 ` [PATCH v12 07/69] lib/test_maple_tree: add testing for maple tree Liam Howlett
2022-07-20  2:17 ` [PATCH v12 08/69] mm: start tracking VMAs with " Liam Howlett
2022-07-27  0:28   ` Nathan Chancellor
2022-07-28  0:34     ` Liam Howlett
2022-07-29 15:41       ` Liam Howlett
2022-07-29 17:02         ` Nathan Chancellor
2022-07-29 20:13           ` Liam Howlett
2022-07-20  2:17 ` [PATCH v12 10/69] mmap: use the VMA iterator in count_vma_pages_range() Liam Howlett
2022-07-20  2:17 ` [PATCH v12 09/69] mm: add VMA iterator Liam Howlett
2022-07-20  2:17 ` [PATCH v12 13/69] mm/mmap: use maple tree for unmapped_area{_topdown} Liam Howlett
2022-07-20  2:17 ` [PATCH v12 11/69] mm/mmap: use the maple tree in find_vma() instead of the rbtree Liam Howlett
2022-07-20  2:17 ` [PATCH v12 12/69] mm/mmap: use the maple tree for find_vma_prev() " Liam Howlett
2022-07-20  2:17 ` [PATCH v12 14/69] kernel/fork: use maple tree for dup_mmap() during forking Liam Howlett
2022-07-20  2:17 ` [PATCH v12 16/69] proc: remove VMA rbtree use from nommu Liam Howlett
2022-07-20  2:17 ` [PATCH v12 15/69] damon: convert __damon_va_three_regions to use the VMA iterator Liam Howlett
2022-07-20  2:17 ` [PATCH v12 18/69] mmap: change zeroing of maple tree in __vma_adjust() Liam Howlett
2022-07-20  2:17 ` [PATCH v12 17/69] mm: remove rb tree Liam Howlett
2022-07-20  2:17 ` [PATCH v12 19/69] xen: use vma_lookup() in privcmd_ioctl_mmap() Liam Howlett
2022-07-20  2:17 ` [PATCH v12 20/69] mm: optimize find_exact_vma() to use vma_lookup() Liam Howlett
2022-07-20  2:17 ` [PATCH v12 22/69] mm/mmap: change do_brk_flags() to expand existing VMA and add do_brk_munmap() Liam Howlett
2022-07-23 15:01   ` Dmitry Osipenko
2022-07-25 14:01     ` Liam Howlett
2022-07-25 18:49       ` Liam Howlett
2022-07-25 19:13         ` Dmitry Osipenko
2022-07-28  0:57           ` Liam Howlett
2022-07-28 16:56             ` Dmitry Osipenko
2022-07-20  2:17 ` [PATCH v12 21/69] mm/khugepaged: optimize collapse_pte_mapped_thp() by using vma_lookup() Liam Howlett
2022-07-20  2:17 ` [PATCH v12 24/69] mm/mmap: use advanced maple tree API for mmap_region() Liam Howlett
2022-07-20  2:17 ` [PATCH v12 23/69] mm: use maple tree operations for find_vma_intersection() Liam Howlett
2022-07-20  2:17 ` [PATCH v12 27/69] mm/mmap: move mmap_region() below do_munmap() Liam Howlett
2022-07-20  2:17 ` [PATCH v12 26/69] mm: convert vma_lookup() to use mtree_load() Liam Howlett
2022-07-20  2:17 ` [PATCH v12 25/69] mm: remove vmacache Liam Howlett
2022-07-20  2:17 ` [PATCH v12 28/69] mm/mmap: reorganize munmap to use maple states Liam Howlett
2022-07-20  2:17 ` [PATCH v12 30/69] arm64: remove mmap linked list from vdso Liam Howlett
2022-07-20  2:17 ` [PATCH v12 29/69] mm/mmap: change do_brk_munmap() to use do_mas_align_munmap() Liam Howlett
2022-07-20  2:17 ` [PATCH v12 33/69] powerpc: remove mmap linked list walks Liam Howlett
2022-08-02 10:36   ` Christophe Leroy
2022-08-02 10:36     ` Christophe Leroy
2022-08-02 10:36   ` Fwd: " Christophe Leroy
2022-07-20  2:17 ` [PATCH v12 31/69] arm64: Change elfcore for_each_mte_vma() to use VMA iterator Liam Howlett
2022-07-20  2:17 ` [PATCH v12 32/69] parisc: remove mmap linked list from cache handling Liam Howlett
2022-07-20  2:17 ` [PATCH v12 36/69] xtensa: remove vma linked list walks Liam Howlett
2022-07-20  2:17 ` [PATCH v12 34/69] s390: " Liam Howlett
2022-07-20  2:17 ` [PATCH v12 35/69] x86: " Liam Howlett
2022-07-20  2:17 ` [PATCH v12 38/69] optee: remove vma linked list walk Liam Howlett
2022-07-20  2:17 ` [PATCH v12 40/69] coredump: " Liam Howlett
2022-07-20  2:17 ` [PATCH v12 39/69] um: " Liam Howlett
2022-07-20  2:17 ` [PATCH v12 37/69] cxl: " Liam Howlett
2022-07-20  2:17 ` [PATCH v12 43/69] fs/proc/task_mmu: stop using linked list and highest_vm_end Liam Howlett
2022-07-20  2:17 ` [PATCH v12 44/69] userfaultfd: use maple tree iterator to iterate VMAs Liam Howlett
2022-07-20  2:17 ` [PATCH v12 41/69] exec: use VMA iterator instead of linked list Liam Howlett
2022-07-20  2:17 ` [PATCH v12 42/69] fs/proc/base: use maple tree iterators in place " Liam Howlett
2022-07-20  2:17 ` [PATCH v12 46/69] acct: use VMA iterator instead " Liam Howlett
2022-07-20  2:17 ` [PATCH v12 47/69] perf: use VMA iterator Liam Howlett
2022-07-20  2:17 ` [PATCH v12 45/69] ipc/shm: use VMA iterator instead of linked list Liam Howlett
2022-07-20  2:17 ` [PATCH v12 50/69] bpf: remove VMA " Liam Howlett
2022-07-20  2:17 ` [PATCH v12 51/69] mm/gup: use maple tree navigation instead of " Liam Howlett
2022-07-20  2:17 ` [PATCH v12 49/69] fork: use VMA iterator Liam Howlett
2022-07-20  2:17 ` [PATCH v12 48/69] sched: use maple tree iterator to walk VMAs Liam Howlett
2022-07-20  2:18 ` [PATCH v12 54/69] mm/madvise: use vma_find() instead of vma linked list Liam Howlett
2022-07-20  2:18 ` [PATCH v12 52/69] mm/khugepaged: stop using " Liam Howlett
2022-07-20  2:18 ` [PATCH v12 53/69] mm/ksm: use vma iterators instead of " Liam Howlett
2022-07-20  2:18 ` [PATCH v12 58/69] mm/mprotect: use maple tree navigation " Liam Howlett
2022-07-20  2:18 ` [PATCH v12 57/69] mm/mlock: use vma iterator and maple state " Liam Howlett
2022-07-20  2:18 ` [PATCH v12 55/69] mm/memcontrol: stop using mm->highest_vm_end Liam Howlett
2022-07-20  2:18 ` [PATCH v12 56/69] mm/mempolicy: use vma iterator & maple state instead of vma linked list Liam Howlett
2022-07-20  2:18 ` [PATCH v12 60/69] mm/msync: use vma_find() " Liam Howlett
2022-07-20  2:18 ` [PATCH v12 61/69] mm/oom_kill: use maple tree iterators " Liam Howlett
2022-07-20  2:18 ` [PATCH v12 59/69] mm/mremap: use vma_find_intersection() " Liam Howlett
2022-07-20  2:18 ` [PATCH v12 62/69] mm/pagewalk: use vma_find() " Liam Howlett
2022-07-20  2:18 ` [PATCH v12 63/69] mm/swapfile: use vma iterator " Liam Howlett
2022-07-20  2:18 ` [PATCH v12 65/69] nommu: remove uses of VMA " Liam Howlett
2022-07-20  2:18 ` [PATCH v12 64/69] i915: use the VMA iterator Liam Howlett
2022-07-20  2:18 ` [PATCH v12 68/69] mm/mmap: drop range_has_overlap() function Liam Howlett
2022-07-20  2:18 ` [PATCH v12 67/69] mm: remove the vma linked list Liam Howlett
2022-07-20  2:18 ` [PATCH v12 66/69] riscv: use vma iterator for vdso Liam Howlett
2022-07-20  2:18 ` [PATCH v12 69/69] mm/mmap.c: pass in mapping to __vma_link_file() Liam Howlett
2022-07-20  5:09 ` [PATCH v12 00/69] Introducing the Maple Tree Andrew Morton

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.