Skip to content

Introducing the Maple Tree

Liam Howlett damon linux-mm lkml qemu-devel 8 versions – In review

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v8 Latest70 patches 43 repliesIn review
  2. v770 patches 28 repliesSuperseded
  3. v671 patches 28 repliesSuperseded
Earlier versions · 5
VersionPostedPatchesRepliesStatus
v570 patches12 repliesSuperseded
v466 patches114 repliesSuperseded
v366 patches0 repliesSuperseded
v261 patches2 repliesSuperseded
v194 patches42 repliesSuperseded

Changes in v8 from the cover letter

- 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

Patches in v8 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/70radix tree test suite: add pr_err definetools/testing/radix-tree/linux/kernel.h+1 -00 replies
2/70radix tree test suite: add kmem_cache_set_non_kernel()tools/testing/radix-tree/linux.c+13 -20 replies
3/70radix tree test suite: add allocation counts and size to kmem_cachetools/testing/radix-tree/linux.c+27 -00 replies
4/70radix tree test suite: add support for slab bulk APIstools/include/linux/slab.h tools/testing/radix-tree/linux.c+120 -20 replies
5/70radix tree test suite: add lockdep_is_held to headertools/testing/radix-tree/linux/lockdep.h+2 -00 replies
6/70mips: rename mt_init to mips_mt_initarch/mips/kernel/mips-mt.c+2 -20 replies
7/70Maple Tree: add new data structureDocumentation/core-api/index.rst Documentation/core-api/maple_tree.rst MAINTAINERS +11 more+8094 -11 reply
8/70lib/test_maple_tree: add testing for maple treelib/test_maple_tree.c tools/testing/radix-tree/Makefile+37861 -20 replies
9/70mm: start tracking VMAs with maple treearch/x86/kernel/tboot.c drivers/firmware/efi/efi.c include/linux/mm.h +6 more+361 -140 replies
10/70mm: add VMA iteratorinclude/linux/mm.h include/linux/mm_types.h mm/mmap.c+57 -50 replies
11/70mmap: use the VMA iterator in count_vma_pages_range()mm/mmap.c+7 -170 replies
12/70mm/mmap: use the maple tree in find_vma() instead of the rbtree.mm/mmap.c+10 -180 replies
13/70mm/mmap: use the maple tree for find_vma_prev() instead of the rbtreemm/mmap.c+17 -100 replies
14/70mm/mmap: use maple tree for unmapped_area{_topdown}mm/mmap.c+32 -2210 replies
15/70kernel/fork: use maple tree for dup_mmap() during forkinginclude/linux/mm.h kernel/fork.c mm/mmap.c+19 -90 replies
16/70damon: Convert __damon_va_three_regions to use the VMA iteratormm/damon/vaddr-test.h mm/damon/vaddr.c+40 -501 reply
17/70proc: remove VMA rbtree use from nommufs/proc/task_nommu.c+21 -240 replies
18/70mm: remove rb tree.arch/x86/kernel/tboot.c drivers/firmware/efi/efi.c include/linux/mm.h +6 more+143 -4880 replies
19/70mmap: change zeroing of maple tree in __vma_adjust()mm/mmap.c+19 -80 replies
20/70xen: use vma_lookup() in privcmd_ioctl_mmap()drivers/xen/privcmd.c+1 -10 replies
21/70mm: optimize find_exact_vma() to use vma_lookup()include/linux/mm.h+1 -10 replies
22/70mm/khugepaged: optimize collapse_pte_mapped_thp() by using vma_lookup()mm/khugepaged.c+1 -10 replies
23/70mm/mmap: change do_brk_flags() to expand existing VMA and add do_brk_munmap()mm/mmap.c+223 -5823 replies
24/70mm: use maple tree operations for find_vma_intersection()include/linux/mm.h mm/mmap.c mm/nommu.c+44 -180 replies
25/70mm/mmap: use advanced maple tree API for mmap_region()mm/mmap.c+198 -470 replies
26/70mm: remove vmacachefs/exec.c fs/proc/task_mmu.c include/linux/mm_types.h +14 more+9 -2680 replies
27/70mm: convert vma_lookup() to use mtree_load()include/linux/mm.h+1 -60 replies
28/70mm/mmap: move mmap_region() below do_munmap()mm/mmap.c+238 -2380 replies
29/70mm/mmap: reorganize munmap to use maple statesinclude/linux/mm.h mm/mmap.c mm/mremap.c+153 -880 replies
30/70mm/mmap: change do_brk_munmap() to use do_mas_align_munmap()mm/mmap.c+3 -20 replies
31/70arm64: remove mmap linked list from vdsoarch/arm64/kernel/vdso.c+2 -10 replies
32/70arm64: Change elfcore for_each_mte_vma() to use VMA iteratorarch/arm64/kernel/elfcore.c+10 -60 replies
33/70parisc: remove mmap linked list from cache handlingarch/parisc/kernel/cache.c+5 -20 replies
34/70powerpc: remove mmap linked list walksarch/powerpc/kernel/vdso.c arch/powerpc/mm/book3s32/tlb.c arch/powerpc/mm/book3s64/subpage_prot.c+11 -190 replies
35/70s390: remove vma linked list walksarch/s390/kernel/vdso.c arch/s390/mm/gmap.c+6 -30 replies
36/70x86: remove vma linked list walksarch/x86/entry/vdso/vma.c+5 -40 replies
37/70xtensa: remove vma linked list walksarch/xtensa/kernel/syscall.c+12 -60 replies
38/70cxl: remove vma linked list walkdrivers/misc/cxl/fault.c+15 -300 replies
39/70optee: remove vma linked list walkdrivers/tee/optee/call.c+10 -80 replies
40/70um: remove vma linked list walkarch/um/kernel/tlb.c+6 -80 replies
41/70coredump: remove vma linked list walkfs/coredump.c+12 -220 replies
42/70exec: use VMA iterator instead of linked listfs/exec.c+6 -30 replies
43/70fs/proc/base: use maple tree iterators in place of linked listfs/proc/base.c+4 -10 replies
44/70fs/proc/task_mmu: stop using linked list and highest_vm_endfs/proc/internal.h fs/proc/task_mmu.c+42 -330 replies
45/70userfaultfd: use maple tree iterator to iterate VMAsfs/userfaultfd.c include/linux/userfaultfd_k.h mm/mmap.c+36 -271 reply
46/70ipc/shm: use VMA iterator instead of linked listipc/shm.c+10 -110 replies
47/70acct: use VMA iterator instead of linked listkernel/acct.c+5 -60 replies
48/70perf: use VMA iteratorkernel/events/core.c kernel/events/uprobes.c+8 -40 replies
49/70sched: use maple tree iterator to walk VMAskernel/sched/fair.c+7 -30 replies
50/70fork: use VMA iteratorkernel/fork.c+5 -20 replies
51/70bpf: remove VMA linked listkernel/bpf/task_iter.c+5 -50 replies
52/70mm/gup: use maple tree navigation instead of linked listmm/gup.c+4 -30 replies
53/70mm/khugepaged: stop using vma linked listmm/huge_memory.c mm/khugepaged.c+10 -50 replies
54/70mm/ksm: use vma iterators instead of vma linked listmm/ksm.c+11 -70 replies
55/70mm/madvise: use vma_find() instead of vma linked listmm/madvise.c+1 -10 replies
56/70mm/memcontrol: stop using mm->highest_vm_endmm/memcontrol.c+2 -40 replies
57/70mm/mempolicy: use vma iterator & maple state instead of vma linked listmm/mempolicy.c+32 -240 replies
58/70mm/mlock: use vma iterator and instead of vma linked listmm/mlock.c+18 -160 replies
59/70mm/mprotect: use maple tree navigation instead of vma linked listmm/mprotect.c+4 -30 replies
60/70mm/mremap: use vma_find_intersection() instead of vma linked listmm/mremap.c+3 -20 replies
61/70mm/msync: use vma_find() instead of vma linked listmm/msync.c+1 -10 replies
62/70mm/oom_kill: use maple tree iterators instead of vma linked listmm/oom_kill.c+2 -10 replies
63/70mm/pagewalk: use vma_find() instead of vma linked listmm/pagewalk.c+1 -10 replies
64/70mm/swapfile: use vma iterator instead of vma linked listmm/swapfile.c+3 -10 replies
65/70i915: use the VMA iteratordrivers/gpu/drm/i915/gem/i915_gem_userptr.c+5 -90 replies
66/70nommu: remove uses of VMA linked listmm/nommu.c+11 -43 replies
67/70riscv: use vma iterator for vdsoarch/riscv/kernel/vdso.c+2 -10 replies
68/70mm: remove the vma linked listinclude/linux/mm.h include/linux/mm_types.h kernel/fork.c +6 more+218 -3390 replies
69/70mm/mmap: drop range_has_overlap() functionmm/mmap.c+1 -270 replies
70/70mm/mmap.c: pass in mapping to __vma_link_file()mm/mmap.c+14 -190 replies

Reviews trailers per patch

34 of 70 patches have a Reviewed-by or Acked-by.

PatchVlastimil BabkaDavid HowellsCatalin MarinasSeongJae Park
1/70
2/70
3/70
4/70
5/70
6/70
7/70T-b
8/70
9/70
10/70A-b
11/70A-b
12/70A-b
13/70A-b
14/70
15/70A-b
16/70R-b
17/70A-b
18/70
19/70
20/70A-b
21/70R-b
22/70R-b
23/70
24/70
25/70
26/70A-b
27/70A-b
28/70
29/70
30/70
31/70A-b
32/70A-b
33/70A-b
34/70R-b
35/70A-b
36/70A-b
37/70
38/70A-b
39/70A-b
40/70
41/70
42/70
43/70
44/70
45/70
46/70
47/70A-b
48/70A-b
49/70A-b
50/70A-b
51/70
52/70
53/70
54/70
55/70A-b
56/70
57/70
58/70
59/70A-b
60/70A-b
61/70A-b
62/70A-b
63/70A-b
64/70A-b
65/70A-b
66/70A-b
67/70
68/70
69/70A-b
70/70

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes. Scroll the table sideways for all 4 reviewers.

Read the v8 thread

Cover letter [PATCH v8 00/70] Introducing the Maple Tree

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

v7: https://lore.kernel.org/linux-mm/[email protected]/
v6: https://lore.kernel.org/linux-mm/[email protected]/
v5: https://lore.kernel.org/linux-mm/[email protected]/
v4: https://lore.kernel.org/linux-mm/[email protected]/
v3: https://lore.kernel.org/linux-mm/[email protected]/
v2: https://lore.kernel.org/linux-mm/[email protected]/
v1: https://lore.kernel.org/linux-mm/[email protected]/

Liam R. Howlett (45):
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
mips: rename mt_init to mips_mt_init
Maple Tree: add new data structure
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 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         |   218 +
 MAINTAINERS                                   |    12 +
 arch/arm64/kernel/elfcore.c                   |    16 +-
 arch/arm64/kernel/vdso.c                      |     3 +-
 arch/mips/kernel/mips-mt.c                    |     4 +-
 arch/parisc/kernel/cache.c                    |     7 +-
 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                              |    49 +-
 include/linux/maple_tree.h                    |   685 +
 include/linux/mm.h                            |    74 +-
 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                   |    71 +
 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                                 |    58 +-
 kernel/sched/fair.c                           |    10 +-
 lib/Kconfig.debug                             |    17 +-
 lib/Makefile                                  |     3 +-
 lib/maple_tree.c                              |  6964 +++
 lib/test_maple_tree.c                         | 37854 ++++++++++++++++
 mm/Makefile                                   |     2 +-
 mm/damon/vaddr-test.h                         |    37 +-
 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                                 |    42 +-
 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                                    |    34 +-
 mm/mmap.c                                     |  2079 +-
 mm/mprotect.c                                 |     7 +-
 mm/mremap.c                                   |    22 +-
 mm/msync.c                                    |     2 +-
 mm/nommu.c                                    |   135 +-
 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      |     3 +
 89 files changed, 47833 insertions(+), 1823 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
Signature · 1 line
2.35.1