From: Liam Howlett <liam.howlett@oracle.com>
To: "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>, Hugh Dickins <hughd@google.com>
Subject: [PATCH v11 00/69] Introducing the Maple Tree
Date: Sun, 17 Jul 2022 02:46:32 +0000 [thread overview]
Message-ID: <20220717024615.2106835-1-Liam.Howlett@oracle.com> (raw)
Hello,
This is the v10 + fixes and a few clean ups. I used the mm-unstable
branch and patched in place.
git: https://github.com/oracle/linux-uek/tree/howlett/maple/20220716
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 underflow in mas_spanning_rebalance() - Thanks Yu
Zhao
- maple_tree: Fix mas_spanning_rebalance() corner case - Thanks Yu Zhao
- mmap: Reorder validate_mm_mt() checks
- VMA iterator: Add underscores and parentheses - Thanks David
Hildenbrand
- maple_tree: Add underscores and parentheses - Thanks David
Hildenbrand
- maple_tree: Fix sparse reported issues
- mmap: Fix locking issues in vma_expand - Thanks Hugh Dickins
- mmap: Fix reutrn on maple tree dexpand fail in brk() - Thanks Hugh
Dickins
- maple_tree: Fix mas_empty_area_rev() search exhaustion at root node -
Thanks Alexander Gordeev
- maple_tree: Fix out of bounds access on mas_wr_node_walk() - Thanks
Yu Zhao
- mmap: Fix __vma_adjust() issue on memory failure
- maple_tree: Fix stale data copy in mas_wr_node_store()
- mmap: Change comments to be more specific - Thanks David Hildenbrand
- mmap: Use PHYS_PFN() where necessary - Thanks David Hildenbrand
- Removed %px use in patches that only existed in the series
- Fixed a few checkscript reports.
- Added necessary tests to cover all bugs found.
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 | 686 +
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 | 2206 +-
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, 48494 insertions(+), 1877 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
next reply other threads:[~2022-07-17 2:46 UTC|newest]
Thread overview: 76+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-07-17 2:46 Liam Howlett [this message]
2022-07-17 2:46 ` [PATCH v11 02/69] radix tree test suite: add pr_err define Liam Howlett
2022-07-17 2:46 ` [PATCH v11 01/69] Maple Tree: add new data structure Liam Howlett
2022-07-17 2:46 ` [PATCH v11 03/69] radix tree test suite: add kmem_cache_set_non_kernel() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 04/69] radix tree test suite: add allocation counts and size to kmem_cache Liam Howlett
2022-07-17 2:46 ` [PATCH v11 05/69] radix tree test suite: add support for slab bulk APIs Liam Howlett
2022-07-17 2:46 ` [PATCH v11 06/69] radix tree test suite: add lockdep_is_held to header Liam Howlett
2022-07-17 2:46 ` [PATCH v11 07/69] lib/test_maple_tree: add testing for maple tree Liam Howlett
2022-07-17 2:46 ` [PATCH v11 10/69] mmap: use the VMA iterator in count_vma_pages_range() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 09/69] mm: add VMA iterator Liam Howlett
2022-07-17 2:46 ` [PATCH v11 08/69] mm: start tracking VMAs with maple tree Liam Howlett
2022-07-17 2:46 ` [PATCH v11 11/69] mm/mmap: use the maple tree in find_vma() instead of the rbtree Liam Howlett
2022-07-17 2:46 ` [PATCH v11 12/69] mm/mmap: use the maple tree for find_vma_prev() " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 13/69] mm/mmap: use maple tree for unmapped_area{_topdown} Liam Howlett
2022-07-17 2:46 ` [PATCH v11 16/69] proc: remove VMA rbtree use from nommu Liam Howlett
2022-07-17 2:46 ` [PATCH v11 15/69] damon: convert __damon_va_three_regions to use the VMA iterator Liam Howlett
2022-07-17 2:46 ` [PATCH v11 14/69] kernel/fork: use maple tree for dup_mmap() during forking Liam Howlett
2022-07-17 2:46 ` [PATCH v11 18/69] mmap: change zeroing of maple tree in __vma_adjust() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 17/69] mm: remove rb tree Liam Howlett
2022-07-17 2:46 ` [PATCH v11 19/69] xen: use vma_lookup() in privcmd_ioctl_mmap() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 20/69] mm: optimize find_exact_vma() to use vma_lookup() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 22/69] mm/mmap: change do_brk_flags() to expand existing VMA and add do_brk_munmap() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 21/69] mm/khugepaged: optimize collapse_pte_mapped_thp() by using vma_lookup() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 23/69] mm: use maple tree operations for find_vma_intersection() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 24/69] mm/mmap: use advanced maple tree API for mmap_region() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 25/69] mm: remove vmacache Liam Howlett
2022-07-17 2:46 ` [PATCH v11 26/69] mm: convert vma_lookup() to use mtree_load() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 27/69] mm/mmap: move mmap_region() below do_munmap() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 29/69] mm/mmap: change do_brk_munmap() to use do_mas_align_munmap() Liam Howlett
2022-07-17 2:46 ` [PATCH v11 28/69] mm/mmap: reorganize munmap to use maple states Liam Howlett
2022-07-17 2:46 ` [PATCH v11 30/69] arm64: remove mmap linked list from vdso Liam Howlett
2022-07-17 2:46 ` [PATCH v11 31/69] arm64: Change elfcore for_each_mte_vma() to use VMA iterator Liam Howlett
2022-07-17 2:46 ` [PATCH v11 32/69] parisc: remove mmap linked list from cache handling Liam Howlett
2022-07-17 2:46 ` [PATCH v11 34/69] s390: remove vma linked list walks Liam Howlett
2022-07-17 2:46 ` [PATCH v11 33/69] powerpc: remove mmap " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 36/69] xtensa: remove vma " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 37/69] cxl: remove vma linked list walk Liam Howlett
2022-07-17 2:46 ` [PATCH v11 35/69] x86: remove vma linked list walks Liam Howlett
2022-07-17 2:46 ` [PATCH v11 39/69] um: remove vma linked list walk Liam Howlett
2022-07-17 2:46 ` [PATCH v11 38/69] optee: " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 41/69] exec: use VMA iterator instead of linked list Liam Howlett
2022-07-17 2:46 ` [PATCH v11 40/69] coredump: remove vma linked list walk Liam Howlett
2022-07-17 2:46 ` [PATCH v11 44/69] userfaultfd: use maple tree iterator to iterate VMAs Liam Howlett
2022-07-17 2:46 ` [PATCH v11 42/69] fs/proc/base: use maple tree iterators in place of linked list Liam Howlett
2022-07-17 2:46 ` [PATCH v11 43/69] fs/proc/task_mmu: stop using linked list and highest_vm_end Liam Howlett
2022-07-17 2:46 ` [PATCH v11 46/69] acct: use VMA iterator instead of linked list Liam Howlett
2022-07-17 2:46 ` [PATCH v11 47/69] perf: use VMA iterator Liam Howlett
2022-07-17 2:46 ` [PATCH v11 45/69] ipc/shm: use VMA iterator instead of linked list Liam Howlett
2022-07-17 2:46 ` [PATCH v11 49/69] fork: use VMA iterator Liam Howlett
2022-07-17 2:46 ` [PATCH v11 48/69] sched: use maple tree iterator to walk VMAs Liam Howlett
2022-07-17 2:46 ` [PATCH v11 50/69] bpf: remove VMA linked list Liam Howlett
2022-07-17 2:46 ` [PATCH v11 54/69] mm/madvise: use vma_find() instead of vma " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 53/69] mm/ksm: use vma iterators " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 51/69] mm/gup: use maple tree navigation instead of " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 52/69] mm/khugepaged: stop using vma " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 57/69] mm/mlock: use vma iterator and maple state instead of " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 55/69] mm/memcontrol: stop using mm->highest_vm_end Liam Howlett
2022-07-17 2:46 ` [PATCH v11 56/69] mm/mempolicy: use vma iterator & maple state instead of vma linked list Liam Howlett
2022-07-17 2:46 ` [PATCH v11 59/69] mm/mremap: use vma_find_intersection() " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 60/69] mm/msync: use vma_find() " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 58/69] mm/mprotect: use maple tree navigation " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 63/69] mm/swapfile: use vma iterator " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 62/69] mm/pagewalk: use vma_find() " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 61/69] mm/oom_kill: use maple tree iterators " Liam Howlett
2022-07-17 2:46 ` [PATCH v11 64/69] i915: use the VMA iterator Liam Howlett
2022-07-17 2:46 ` [PATCH v11 67/69] mm: remove the vma linked list Liam Howlett
2022-07-17 2:46 ` [PATCH v11 66/69] riscv: use vma iterator for vdso Liam Howlett
2022-07-17 2:46 ` [PATCH v11 65/69] nommu: remove uses of VMA linked list Liam Howlett
2022-07-17 2:46 ` [PATCH v11 68/69] mm/mmap: drop range_has_overlap() function Liam Howlett
2022-07-17 2:46 ` [PATCH v11 69/69] mm/mmap.c: pass in mapping to __vma_link_file() Liam Howlett
2022-07-17 4:20 ` [PATCH v11 00/69] Introducing the Maple Tree Andrew Morton
2022-07-17 5:57 ` Yu Zhao
2022-07-17 12:42 ` Liam Howlett
2022-07-17 13:06 ` Liam Howlett
2022-07-17 18:55 ` Yu Zhao
2022-07-17 13:01 ` 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=20220717024615.2106835-1-Liam.Howlett@oracle.com \
--to=liam.howlett@oracle.com \
--cc=akpm@linux-foundation.org \
--cc=hughd@google.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).