Andrew, Please merge this patch set into the mm tree. Changes: - Removed mips rename patch to allow maple tree data structure to be the first patch - Moved pretty cover letter to the first patch - Boot tested m68k and s390 builds - Had to disable KASAN for s390 due to qemu bug [1] - Added error paths for preallocation failures - Added error path for brk failure instead of dropping dead code - Added s-o-b SeongJae Park to damon patch It is based off the mm-stable branch. 1. https://lore.kernel.org/linux-mm/YnGHJ7oroqF+v1u+@osiris/ 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 | 218 + MAINTAINERS | 12 + arch/arm64/kernel/elfcore.c | 16 +- arch/arm64/kernel/vdso.c | 3 +- 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 | 55 +- 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 | 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 | 6965 +++ 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 | 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 | 2129 +- 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 + 88 files changed, 47857 insertions(+), 1820 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
