Skip to contentSkip to conversation

Introducing the Maple Tree

PATCH Superseded Liam Howlett 3 participants 69 messages Aug 17, 2021 – Aug 31, 2021

Subsystems (41)

v2 of 8 Superseded Latest is v8 →

lore
Share & tools
lore
#0 lore raw

v2 cover 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. 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 series is based on next-20210811 with "remap_file_pages: Use vma_lookup() instead of find_vma()"

Link:
https://github.com/oracle/linux-uek/releases/tag/howlett%2Fmaple%2F20210816

Performance on a 144 core x86:

While still using the mmap_sem, the performance seems fairly similar on real-world workloads, while there are variations in micro-benchmarks.

Increase in performance in the following micro-benchmarks in Hmean:
- wis malloc1-threads: Increase of 13% to 840%
- wis page_fault1-threads: Increase of 1% to 14%
- wis brk1-threads: Disregard, this test is invalid.

Decrease in performance in the following micro-benchmarks in Hmean:
- wis brk1-processes: Decrease of 45% due to RCU required

Mixed:
- wis pthread_mutex1-threads: +11% to -3%
- wis signal1-threads: +6% to -12%
- wis malloc1-processes: +9% to -18% (-18 at 2 processes, increases after)
- wis page_fault3-threads: +8% to -22%

kernbench:

Amean     user-2        884.88 (   0.00%)      882.61 *   0.26%*
Amean     syst-2        157.38 (   0.00%)      161.23 *  -2.45%*
Amean     elsp-2        526.17 (   0.00%)      527.53 *  -0.26%* 
Amean     user-4        919.90 (   0.00%)      910.87 *   0.98%*
Amean     syst-4        166.21 (   0.00%)      170.06 *  -2.32%*
Amean     elsp-4        278.01 (   0.00%)      276.83 *   0.42%*
Amean     user-8        973.23 (   0.00%)      970.73 *   0.26%*
Amean     syst-8        176.70 (   0.00%)      181.00 *  -2.44%*
Amean     elsp-8        152.24 (   0.00%)      153.33 *  -0.72%*
Amean     user-16      1040.15 (   0.00%)     1045.90 *  -0.55%*
Amean     syst-16       185.13 (   0.00%)      191.08 *  -3.21%*
Amean     elsp-16        85.47 (   0.00%)       86.70 *  -1.44%*
Amean     user-32      1189.60 (   0.00%)     1187.91 *   0.14%*
Amean     syst-32       210.02 (   0.00%)      219.46 *  -4.49%*
Amean     elsp-32        53.86 (   0.00%)       53.91 *  -0.08%*
Amean     user-64      1222.05 (   0.00%)     1230.00 *  -0.65%*
Amean     syst-64       213.37 (   0.00%)      223.57 *  -4.78%*
Amean     elsp-64        32.87 (   0.00%)       33.42 *  -1.68%*
Amean     user-128     1618.73 (   0.00%)     1614.52 *   0.26%*
Amean     syst-128      259.72 (   0.00%)      272.95 *  -5.09%*
Amean     elsp-128       25.91 (   0.00%)       25.93 *  -0.08%*

gitcheckout:

Amean     User           0.00 (   0.00%)        0.00 *   0.00%*
Amean     System         8.09 (   0.00%)        7.90 *   2.25%*
Amean     Elapsed       22.89 (   0.00%)       22.50 *   1.74%*
Amean     CPU           93.53 (   0.00%)       93.67 *  -0.14%*

v2 changes:
- Split out unlock_range() into its own cleanup patch, already upstream
- Split off vma_lookup() into its own 22 patches, already upstream
- Fixed locking issue when brk does not change but succeeds. Thanks Suren Baghdasar
- Move locking in brk much earler to match mmap_sem
- Fixed RCU locking issue in mm/khugepaged. Thanks Hillf Danton
- RCU fixes in userfaultfd_release, mlock, munmap, task_mmu, and nommu
- Removed mm_populate_vma() and related patches from this set
- Removed inline of remove_vma_list() from this set as the function is removed
- Fixed comments to all C-based comments as suggested by Peter Zijlstra
- Fixed comments to all C-based comments in test_maple_tree.c as well
- Changed #defines to hex as requested by Peter Zijlstra
- Fixed whitespace error in mas_set_range(). Thanks Peter Zijlstra
- Add Asserts to mas->depth and mte_pivot() range check. Thanks Peter Zijlstra
- Updated comments for mas_alloc_req() and friends. Thanks Peter Zijlstra
- Added back the parent pointer decoding support and added explanations on how the encoding/decoding works. Thanks Peter Zijlstra
- Expanded maple tree height to 31 and added a BUG_ON when exceeding that value. There should be no way to reach 31 high. Thanks Peter Zijlstra
- Added comment on harmless race in mmget_not_zero() - Thanks Suren Baghdasaryan
- Removed debug statement left in during testing - Thanks Suren Baghdasaryan
- Fixed locking in dup_mmap() - Thanks Suren Baghdasaryan
- Changes in the RCU locking in areas that may sleep.
- Added rcu stress testing and fixed maple tree specific issues exposed
- Thanks Paul McKenney for helping with this.
- Large Documentation update.

Patch organization:
Patches 1 to 4 are radix tree test suite additions for maple tree support.

Patch 5 adds the maple tree. Test code is 37000 lines.

Patches 6-11 are the removal of the rbtree from the mm_struct.

Patches 12-18 are the removal of the vmacache from the kernel.

Patches 19-60 are the removal of the vma linked list from the mm_struct.

Patch 61 is a small cleanup from the removal of the vma linked list.

Liam R. Howlett (61):
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 Maple Tree: Add new data structure
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
mm: Remove rb tree.
xen/privcmd: Optimized privcmd_ioctl_mmap() by using vma_lookup()
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() and
    find_vma()

mm/mmap: Use advanced maple tree API for mmap_region()
mm: Remove vmacache
mm/mmap: Move mmap_region() below do_munmap()
mm/mmap: Convert count_vma_pages_range() to use ma_state mm/mmap: Reorganize munmap to use maple states
mm/mmap: Change do_brk_munmap() to use do_mas_align_munmap()
mm: Introduce vma_next() and vma_prev()
arch/arm64: Remove mmap linked list from vdso. arch/parisc: Remove mmap linked list from kernel/cache arch/powerpc: Remove mmap linked list from mm/book3s32/tlb arch/powerpc: Remove mmap linked list from mm/book3s64/subpage_prot arch/s390: Use maple tree iterators instead of linked list. arch/x86: Use maple tree iterators for vdso/vma arch/xtensa: Use maple tree iterators for unmapped area drivers/misc/cxl: Use maple tree iterators for cxl_prefault_vma() drivers/tee/optee: Use maple tree iterators for __check_mem_type() fs/binfmt_elf: Use maple tree iterators for fill_files_note() fs/coredump: Use maple tree iterators in place of linked list fs/exec: Use vma_next() instead of linked list fs/proc/base: Use maple tree iterators in place of linked list fs/proc/task_mmu: Stop using linked list and highest_vm_end fs/userfaultfd: Stop using vma linked list.
ipc/shm: Stop using the vma linked list
kernel/acct: Use maple tree iterators instead of linked list kernel/events/core: Use maple tree iterators instead of linked list kernel/events/uprobes: Use maple tree iterators instead of linked list kernel/sched/fair: Use maple tree iterators instead of linked list kernel/sys: Use maple tree iterators instead of linked list arch/um/kernel/tlb: Stop using linked list
bpf: Remove VMA linked list
mm/gup: Use maple tree navigation instead of linked list mm/khugepaged: Use maple tree iterators instead of vma linked list mm/ksm: Use maple tree iterators instead of vma linked list mm/madvise: Use vma_next instead of vma linked list mm/memcontrol: Stop using mm->highest_vm_end
mm/mempolicy: Use maple tree iterators instead of vma linked list mm/mlock: Use maple tree iterators instead of vma linked list mm/mprotect: Use maple tree navigation instead of vma linked list mm/mremap: Use vma_next() instead of vma linked list mm/msync: Use vma_next() instead of vma linked list mm/oom_kill: Use maple tree iterators instead of vma linked list mm/pagewalk: Use vma_next() instead of vma linked list mm/swapfile: Use maple tree iterator instead of vma linked list
mm: Remove the vma linked list
mm/mmap: Drop range_has_overlap() function

 Documentation/core-api/index.rst              |     1 +
 Documentation/core-api/maple-tree.rst         |   508 +
 MAINTAINERS                                   |    12 +
 arch/arm64/kernel/vdso.c                      |     5 +-
 arch/parisc/kernel/cache.c                    |    15 +-
 arch/powerpc/mm/book3s32/tlb.c                |     5 +-
 arch/powerpc/mm/book3s64/subpage_prot.c       |    15 +-
 arch/s390/configs/debug_defconfig             |     1 -
 arch/s390/mm/gmap.c                           |     8 +-
 arch/um/kernel/tlb.c                          |    16 +-
 arch/x86/entry/vdso/vma.c                     |    12 +-
 arch/x86/kernel/tboot.c                       |     2 +-
 arch/xtensa/kernel/syscall.c                  |     4 +-
 drivers/firmware/efi/efi.c                    |     2 +-
 drivers/misc/cxl/fault.c                      |     6 +-
 drivers/tee/optee/call.c                      |    15 +-
 drivers/xen/privcmd.c                         |     2 +-
 fs/binfmt_elf.c                               |     5 +-
 fs/coredump.c                                 |    13 +-
 fs/exec.c                                     |     9 +-
 fs/proc/base.c                                |     7 +-
 fs/proc/task_mmu.c                            |    48 +-
 fs/proc/task_nommu.c                          |    55 +-
 fs/userfaultfd.c                              |    34 +-
 include/linux/maple_tree.h                    |   474 +
 include/linux/mm.h                            |    54 +-
 include/linux/mm_types.h                      |    31 +-
 include/linux/mm_types_task.h                 |     5 -
 include/linux/sched.h                         |     1 -
 include/linux/sched/mm.h                      |     9 +
 include/linux/vm_event_item.h                 |     4 -
 include/linux/vmacache.h                      |    28 -
 include/linux/vmstat.h                        |     6 -
 include/trace/events/maple_tree.h             |   227 +
 include/trace/events/mmap.h                   |    71 +
 init/main.c                                   |     2 +
 ipc/shm.c                                     |    13 +-
 kernel/acct.c                                 |     8 +-
 kernel/bpf/task_iter.c                        |     6 +-
 kernel/debug/debug_core.c                     |    12 -
 kernel/events/core.c                          |     7 +-
 kernel/events/uprobes.c                       |    25 +-
 kernel/fork.c                                 |    61 +-
 kernel/sched/fair.c                           |    14 +-
 kernel/sys.c                                  |     6 +-
 lib/Kconfig.debug                             |    15 +-
 lib/Makefile                                  |     3 +-
 lib/maple_tree.c                              |  6779 +++
 lib/test_maple_tree.c                         | 37000 ++++++++++++++++
 mm/Makefile                                   |     2 +-
 mm/debug.c                                    |    14 +-
 mm/gup.c                                      |     7 +-
 mm/huge_memory.c                              |     4 +-
 mm/init-mm.c                                  |     4 +-
 mm/internal.h                                 |    81 +-
 mm/khugepaged.c                               |    11 +-
 mm/ksm.c                                      |    26 +-
 mm/madvise.c                                  |     2 +-
 mm/memcontrol.c                               |     6 +-
 mm/memory.c                                   |    33 +-
 mm/mempolicy.c                                |    41 +-
 mm/mlock.c                                    |    21 +-
 mm/mmap.c                                     |  2129 +-
 mm/mprotect.c                                 |    13 +-
 mm/mremap.c                                   |    13 +-
 mm/msync.c                                    |     2 +-
 mm/nommu.c                                    |   120 +-
 mm/oom_kill.c                                 |     5 +-
 mm/pagewalk.c                                 |     2 +-
 mm/swapfile.c                                 |     9 +-
 mm/util.c                                     |    32 -
 mm/vmacache.c                                 |   117 -
 mm/vmstat.c                                   |     4 -
 tools/testing/radix-tree/.gitignore           |     2 +
 tools/testing/radix-tree/Makefile             |    13 +-
 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/maple_tree.h   |     7 +
 tools/testing/radix-tree/linux/slab.h         |     4 +
 tools/testing/radix-tree/maple.c              |    59 +
 .../radix-tree/trace/events/maple_tree.h      |     8 +
 82 files changed, 46975 insertions(+), 1639 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.30.2
#1 lore raw

PATCH v2 1/61 radix tree test suite: Add pr_err define

From: "Liam R. Howlett" <[email protected]>

define pr_err to printk

---
 tools/testing/radix-tree/linux/kernel.h | 1 +
 1 file changed, 1 insertion(+)
tools/testing/radix-tree/linux/kernel.h +1 -0
index 39867fd80c8f..c5c9d05f29da 100644
@@ -14,6 +14,7 @@
 #include "../../../include/linux/kconfig.h"
 
 #define printk printf
+#define pr_err printk
 #define pr_info printk
 #define pr_debug printk
 #define pr_cont printk
Signature · 1 line
2.30.2
#2 lore raw

PATCH v2 2/61 radix tree test suite: Add kmem_cache_set_non_kernel()

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

kmem_cache_set_non_kernel() is a mechanism to allow a certain number of kmem_cache_alloc requests to succeed even when GFP_KERNEL is not set in the flags. This functionality allows for testing different paths though the code.

---
 tools/testing/radix-tree/linux.c | 15 +++++++++++++--
 1 file changed, 13 insertions(+), 2 deletions(-)
tools/testing/radix-tree/linux.c +13 -2
index 2d9c59df60de..00ee01a14652 100644
@@ -24,14 +24,24 @@ struct kmem_cache {
 	int nr_objs;
 	void *objs;
 	void (*ctor)(void *);
+	unsigned int non_kernel;
 };
 
+void kmem_cache_set_non_kernel(struct kmem_cache *cachep, unsigned int val)
+{
+	cachep->non_kernel = val;
+}
+
 void *kmem_cache_alloc(struct kmem_cache *cachep, int gfp)
 {
 	void *p;
 
-	if (!(gfp & __GFP_DIRECT_RECLAIM))
-		return NULL;
+	if (!(gfp & __GFP_DIRECT_RECLAIM)) {
+		if (!cachep->non_kernel)
+			return NULL;
+
+		cachep->non_kernel--;
+	}
 
 	pthread_mutex_lock(&cachep->lock);
 	if (cachep->nr_objs) {
@@ -116,5 +126,6 @@ kmem_cache_create(const char *name, unsigned int size, unsigned int align,
 	ret->nr_objs = 0;
 	ret->objs = NULL;
 	ret->ctor = ctor;
+	ret->non_kernel = 0;
 	return ret;
 }
Signature · 1 line
2.30.2
#3 lore raw

PATCH v2 3/61 radix tree test suite: Add allocation counts and size to kmem_cache

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Add functions to get the number of allocations, and total allocations from a kmem_cache. Also add a function to get the allocated size and a way to zero the total allocations.

---
 tools/testing/radix-tree/linux.c | 27 +++++++++++++++++++++++++++
 1 file changed, 27 insertions(+)
tools/testing/radix-tree/linux.c +27 -0
index 00ee01a14652..f95e71d65f00 100644
@@ -25,6 +25,8 @@ struct kmem_cache {
 	void *objs;
 	void (*ctor)(void *);
 	unsigned int non_kernel;
+	unsigned long nr_allocated;
+	unsigned long nr_tallocated;
 };
 
 void kmem_cache_set_non_kernel(struct kmem_cache *cachep, unsigned int val)
@@ -32,6 +34,26 @@ void kmem_cache_set_non_kernel(struct kmem_cache *cachep, unsigned int val)
 	cachep->non_kernel = val;
 }
 
+unsigned long kmem_cache_get_alloc(struct kmem_cache *cachep)
+{
+	return cachep->size * cachep->nr_allocated;
+}
+
+unsigned long kmem_cache_nr_allocated(struct kmem_cache *cachep)
+{
+	return cachep->nr_allocated;
+}
+
+unsigned long kmem_cache_nr_tallocated(struct kmem_cache *cachep)
+{
+	return cachep->nr_tallocated;
+}
+
+void kmem_cache_zero_nr_tallocated(struct kmem_cache *cachep)
+{
+	cachep->nr_tallocated = 0;
+}
+
 void *kmem_cache_alloc(struct kmem_cache *cachep, int gfp)
 {
 	void *p;
@@ -63,7 +85,9 @@ void *kmem_cache_alloc(struct kmem_cache *cachep, int gfp)
 			memset(p, 0, cachep->size);
 	}
 
+	uatomic_inc(&cachep->nr_allocated);
 	uatomic_inc(&nr_allocated);
+	uatomic_inc(&cachep->nr_tallocated);
 	if (kmalloc_verbose)
 		printf("Allocating %p from slab\n", p);
 	return p;
@@ -73,6 +97,7 @@ void kmem_cache_free(struct kmem_cache *cachep, void *objp)
 {
 	assert(objp);
 	uatomic_dec(&nr_allocated);
+	uatomic_dec(&cachep->nr_allocated);
 	if (kmalloc_verbose)
 		printf("Freeing %p to slab\n", objp);
 	pthread_mutex_lock(&cachep->lock);
@@ -124,6 +149,8 @@ kmem_cache_create(const char *name, unsigned int size, unsigned int align,
 	ret->size = size;
 	ret->align = align;
 	ret->nr_objs = 0;
+	ret->nr_allocated = 0;
+	ret->nr_tallocated = 0;
 	ret->objs = NULL;
 	ret->ctor = ctor;
 	ret->non_kernel = 0;
Signature · 1 line
2.30.2
#4 lore raw

PATCH v2 4/61 radix tree test suite: Add support for slab bulk APIs

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Add support for kmem_cache_free_bulk() and kmem_cache_alloc_bulk() to the radix tree test suite.

---
 tools/testing/radix-tree/linux.c      | 118 +++++++++++++++++++++++++-
 tools/testing/radix-tree/linux/slab.h |   4 +
 2 files changed, 120 insertions(+), 2 deletions(-)
tools/testing/radix-tree/linux.c +116 -2
index f95e71d65f00..3383d748c650 100644
@@ -93,14 +93,13 @@ void *kmem_cache_alloc(struct kmem_cache *cachep, int gfp)
 	return p;
 }
 
-void kmem_cache_free(struct kmem_cache *cachep, void *objp)
+void kmem_cache_free_locked(struct kmem_cache *cachep, void *objp)
 {
 	assert(objp);
 	uatomic_dec(&nr_allocated);
 	uatomic_dec(&cachep->nr_allocated);
 	if (kmalloc_verbose)
 		printf("Freeing %p to slab\n", objp);
-	pthread_mutex_lock(&cachep->lock);
 	if (cachep->nr_objs > 10 || cachep->align) {
 		memset(objp, POISON_FREE, cachep->size);
 		free(objp);
@@ -110,9 +109,80 @@ void kmem_cache_free(struct kmem_cache *cachep, void *objp)
 		node->parent = cachep->objs;
 		cachep->objs = node;
 	}
+}
+
+void kmem_cache_free(struct kmem_cache *cachep, void *objp)
+{
+	pthread_mutex_lock(&cachep->lock);
+	kmem_cache_free_locked(cachep, objp);
+	pthread_mutex_unlock(&cachep->lock);
+}
+
+void kmem_cache_free_bulk(struct kmem_cache *cachep, size_t size, void **list)
+{
+	if (kmalloc_verbose)
+		pr_debug("Bulk free %p[0-%lu]\n", list, size - 1);
+
+	pthread_mutex_lock(&cachep->lock);
+	for (int i = 0; i < size; i++)
+		kmem_cache_free_locked(cachep, list[i]);
 	pthread_mutex_unlock(&cachep->lock);
 }
 
+int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size,
+			  void **p)
+{
+	size_t i;
+
+	if (kmalloc_verbose)
+		pr_debug("Bulk alloc %lu\n", size);
+
+	if (!(gfp & __GFP_DIRECT_RECLAIM)) {
+		if (cachep->non_kernel < size)
+			return 0;
+
+		cachep->non_kernel -= size;
+	}
+
+	pthread_mutex_lock(&cachep->lock);
+	if (cachep->nr_objs >= size) {
+		struct radix_tree_node *node;
+
+		for (i = 0; i < size; i++) {
+			node = cachep->objs;
+			cachep->nr_objs--;
+			cachep->objs = node->parent;
+			p[i] = node;
+			node->parent = NULL;
+		}
+		pthread_mutex_unlock(&cachep->lock);
+	} else {
+		pthread_mutex_unlock(&cachep->lock);
+		for (i = 0; i < size; i++) {
+			if (cachep->align) {
+				posix_memalign(&p[i], cachep->align,
+					       cachep->size * size);
+			} else {
+				p[i] = malloc(cachep->size * size);
+			}
+			if (cachep->ctor)
+				cachep->ctor(p[i]);
+			else if (gfp & __GFP_ZERO)
+				memset(p[i], 0, cachep->size);
+		}
+	}
+
+	for (i = 0; i < size; i++) {
+		uatomic_inc(&nr_allocated);
+		uatomic_inc(&cachep->nr_allocated);
+		uatomic_inc(&cachep->nr_tallocated);
+		if (kmalloc_verbose)
+			printf("Allocating %p from slab\n", p[i]);
+	}
+
+	return size;
+}
+
 void *kmalloc(size_t size, gfp_t gfp)
 {
 	void *ret;
@@ -156,3 +226,47 @@ kmem_cache_create(const char *name, unsigned int size, unsigned int align,
 	ret->non_kernel = 0;
 	return ret;
 }
+
+/*
+ * Test the test infrastructure for kem_cache_alloc/free and bulk counterparts.
+ */
+void test_kmem_cache_bulk(void)
+{
+	int i;
+	void *list[12];
+	static struct kmem_cache *test_cache, *test_cache2;
+
+	/*
+	 * Testing the bulk allocators without aligned kmem_cache to force the
+	 * bulk alloc/free to reuse
+	 */
+	test_cache = kmem_cache_create("test_cache", 256, 0, SLAB_PANIC, NULL);
+
+	for (i = 0; i < 5; i++)
+		list[i] = kmem_cache_alloc(test_cache, __GFP_DIRECT_RECLAIM);
+
+	for (i = 0; i < 5; i++)
+		kmem_cache_free(test_cache, list[i]);
+	assert(test_cache->nr_objs == 5);
+
+	kmem_cache_alloc_bulk(test_cache, __GFP_DIRECT_RECLAIM, 5, list);
+	kmem_cache_free_bulk(test_cache, 5, list);
+
+	for (i = 0; i < 12 ; i++)
+		list[i] = kmem_cache_alloc(test_cache, __GFP_DIRECT_RECLAIM);
+
+	for (i = 0; i < 12; i++)
+		kmem_cache_free(test_cache, list[i]);
+
+	/* The last free will not be kept around */
+	assert(test_cache->nr_objs == 11);
+
+	/* Aligned caches will immediately free */
+	test_cache2 = kmem_cache_create("test_cache2", 128, 128, SLAB_PANIC, NULL);
+
+	kmem_cache_alloc_bulk(test_cache2, __GFP_DIRECT_RECLAIM, 10, list);
+	kmem_cache_free_bulk(test_cache2, 10, list);
+	assert(!test_cache2->nr_objs);
+
+
+}
tools/testing/radix-tree/linux/slab.h +4 -0
index 2958830ce4d7..d7aed1cc6978 100644
@@ -24,4 +24,8 @@ struct kmem_cache *kmem_cache_create(const char *name, unsigned int size,
 			unsigned int align, unsigned int flags,
 			void (*ctor)(void *));
 
+void kmem_cache_free_bulk(struct kmem_cache *cachep, size_t size, void **list);
+int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size,
+			  void **list);
+
 #endif		/* SLAB_H */
Signature · 1 line
2.30.2
#5 lore raw

PATCH v2 5/61 Maple Tree: Add new data structure

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

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.

---
 Documentation/core-api/index.rst              |     1 +
 Documentation/core-api/maple-tree.rst         |   508 +
 MAINTAINERS                                   |    12 +
 include/linux/maple_tree.h                    |   474 +
 include/trace/events/maple_tree.h             |   227 +
 lib/Kconfig.debug                             |     9 +
 lib/Makefile                                  |     3 +-
 lib/maple_tree.c                              |  6779 +++
 lib/test_maple_tree.c                         | 37000 ++++++++++++++++
 tools/testing/radix-tree/.gitignore           |     2 +
 tools/testing/radix-tree/Makefile             |    13 +-
 tools/testing/radix-tree/generated/autoconf.h |     1 +
 tools/testing/radix-tree/linux/maple_tree.h   |     7 +
 tools/testing/radix-tree/maple.c              |    59 +
 .../radix-tree/trace/events/maple_tree.h      |     8 +
 15 files changed, 45100 insertions(+), 3 deletions(-)
 create mode 100644 Documentation/core-api/maple-tree.rst
 create mode 100644 include/linux/maple_tree.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
 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
Documentation/core-api/index.rst +1 -0
index 5de2c7a4b1b3..b487373d8585 100644
@@ -43,6 +43,7 @@ Library functionality that is used throughout the kernel.
    this_cpu_ops
    timekeeping
    errseq
+   maple-tree
 
 Concurrency primitives
 ======================
Documentation/core-api/maple-tree.rst new file +508 -0

508 lines not on this page · raw message

MAINTAINERS +12 -0
index 339ee840d769..5066e76855f7 100644
@@ -11098,6 +11098,18 @@ L:	[email protected]
 S:	Maintained
 W:	http://www.kernel.org/doc/man-pages
 
+MAPLE TREE
+M:	Liam R. Howlett <[email protected]>
+L:	[email protected]
+S:	Supported
+F:	Documentation/core-api/maple_tree.rst
+F:	include/linux/maple_tree.h
+F:	include/trace/events/maple_tree.h
+F:	lib/maple_tree.c
+F:	lib/test_maple_tree.c
+F:	tools/testing/radix-tree/linux/maple_tree.h
+F:	tools/testing/radix-tree/maple.c
+
 MARDUK (CREATOR CI40) DEVICE TREE SUPPORT
 M:	Rahul Bedarkar <[email protected]>
 L:	[email protected]
include/linux/maple_tree.h new file +474 -0

474 lines not on this page · raw message

include/trace/events/maple_tree.h new file +227 -0

227 lines not on this page · raw message

lib/Kconfig.debug +9 -0
index b6b951b0ed46..cdfaafa30ba9 100644
@@ -817,6 +817,15 @@ config DEBUG_VM_RB
 
 	  If unsure, say N.
 
+
+config DEBUG_MAPLE_TREE
+	bool "Debug VM maple trees"
+	depends on DEBUG_VM
+	help
+	  Enable VM maple tree debugging information and extra validations.
+
+	  If unsure, say N.
+
 config DEBUG_VM_PGFLAGS
 	bool "Debug page-flags operations"
 	depends on DEBUG_VM
lib/Makefile +2 -1
index 5efd1b435a37..72c9cb0f0367 100644
@@ -29,7 +29,8 @@ endif
 
 lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 rbtree.o radix-tree.o timerqueue.o xarray.o \
-	 idr.o extable.o sha1.o irq_regs.o argv_split.o \
+	 maple_tree.o idr.o extable.o \
+	 sha1.o irq_regs.o argv_split.o \
 	 flex_proportions.o ratelimit.o show_mem.o \
 	 is_single_threaded.o plist.o decompress.o kobject_uevent.o \
 	 earlycpio.o seq_buf.o siphash.o dec_and_lock.o \
lib/maple_tree.c new file +6779 -0

1,742 lines not on this page · raw message

lib/test_maple_tree.c new file +37000 -0

37,000 lines not on this page · raw message

tools/testing/radix-tree/.gitignore +2 -0
index d971516401e6..c901d96dd013 100644

Lines of this file are not shown. View the raw message.

tools/testing/radix-tree/Makefile +11 -2
index aa6abfe0749c..551937ba6649 100644

Lines of this file are not shown. View the raw message.

tools/testing/radix-tree/generated/autoconf.h +1 -0
index 2218b3cc184e..e7da80350236 100644

Lines of this file are not shown. View the raw message.

tools/testing/radix-tree/linux/maple_tree.h new file +7 -0
new file mode 100644
index 000000000000..89f561e68841

Lines of this file are not shown. View the raw message.

tools/testing/radix-tree/maple.c new file +59 -0

59 lines not on this page · raw message

tools/testing/radix-tree/trace/events/maple_tree.h new file +8 -0
new file mode 100644
index 000000000000..70c7f8d49aa1

Lines of this file are not shown. View the raw message.

The rest of this diff is not shown. View the raw message.

Signature · 1 line
2.30.2

Part of the diff is not shown here. View the raw message.

#6 lore raw

PATCH v2 6/61 mm: Start tracking VMAs with maple tree

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Start tracking the VMAs with the new maple tree structure in parallel with the rb_tree. Add debug and trace events for maple tree operations and duplicate the rb_tree that is created on forks into the maple tree.

In this commit, the maple tree is added to the mm_struct including the mm_init struct, added support in required mm/mmap functions, added tracking in kernel/fork for process forking, and used to find the unmapped_area and checked against what the rbtree finds.

---
 arch/x86/kernel/tboot.c     |   1 +
 drivers/firmware/efi/efi.c  |   1 +
 include/linux/mm.h          |   2 +
 include/linux/mm_types.h    |   2 +
 include/trace/events/mmap.h |  71 +++++++++++
 init/main.c                 |   2 +
 kernel/fork.c               |   4 +
 mm/init-mm.c                |   2 +
 mm/internal.h               |  77 ++++++++++++
 mm/mmap.c                   | 229 +++++++++++++++++++++++++++++++++++-
 10 files changed, 389 insertions(+), 2 deletions(-)
arch/x86/kernel/tboot.c +1 -0
index f9af561c3cd4..6f978f722dff 100644
@@ -98,6 +98,7 @@ void __init tboot_probe(void)
 static pgd_t *tboot_pg_dir;
 static struct mm_struct tboot_mm = {
 	.mm_rb          = RB_ROOT,
+	.mm_mt          = MTREE_INIT(mm_mt, MAPLE_ALLOC_RANGE),
 	.pgd            = swapper_pg_dir,
 	.mm_users       = ATOMIC_INIT(2),
 	.mm_count       = ATOMIC_INIT(1),
drivers/firmware/efi/efi.c +1 -0
index 847f33ffc4ae..1aaecca36e23 100644
@@ -55,6 +55,7 @@ static unsigned long __initdata rt_prop = EFI_INVALID_TABLE_ADDR;
 
 struct mm_struct efi_mm = {
 	.mm_rb			= RB_ROOT,
+	.mm_mt			= MTREE_INIT(mm_mt, MAPLE_ALLOC_RANGE),
 	.mm_users		= ATOMIC_INIT(2),
 	.mm_count		= ATOMIC_INIT(1),
 	.write_protect_seq      = SEQCNT_ZERO(efi_mm.write_protect_seq),
include/linux/mm.h +2 -0
index ce8fc0fd6d6e..80b7af9e725c 100644
@@ -2596,6 +2596,8 @@ extern bool arch_has_descending_max_zone_pfns(void);
 /* nommu.c */
 extern atomic_long_t mmap_pages_allocated;
 extern int nommu_shrink_inode_mappings(struct inode *, size_t, size_t);
+/* maple_tree */
+void vma_store(struct mm_struct *mm, struct vm_area_struct *vma);
 
 /* interval_tree.c */
 void vma_interval_tree_insert(struct vm_area_struct *node,
include/linux/mm_types.h +2 -0
index b9aa9aa99924..b13fa84d5134 100644
@@ -8,6 +8,7 @@
 #include <linux/list.h>
 #include <linux/spinlock.h>
 #include <linux/rbtree.h>
+#include <linux/maple_tree.h>
 #include <linux/rwsem.h>
 #include <linux/completion.h>
 #include <linux/cpumask.h>
@@ -481,6 +482,7 @@ struct kioctx_table;
 struct mm_struct {
 	struct {
 		struct vm_area_struct *mmap;		/* list of VMAs */
+		struct maple_tree mm_mt;
 		struct rb_root mm_rb;
 		u64 vmacache_seqnum;                   /* per-thread vmacache */
 #ifdef CONFIG_MMU
include/trace/events/mmap.h +71 -0

77 lines not on this page · raw message

init/main.c +2 -0
index 4b4897b791fd..f8453261fff9 100644
@@ -116,6 +116,7 @@ static int kernel_init(void *);
 
 extern void init_IRQ(void);
 extern void radix_tree_init(void);
+extern void maple_tree_init(void);
 
 /*
  * Debug helper: via this flag we know that we are in 'early bootup code'
@@ -985,6 +986,7 @@ asmlinkage __visible void __init __no_sanitize_address start_kernel(void)
 		 "Interrupts were enabled *very* early, fixing it\n"))
 		local_irq_disable();
 	radix_tree_init();
+	maple_tree_init();
 
 	/*
 	 * Set up housekeeping before setting up workqueues to allow the unbound
kernel/fork.c +4 -0
index af408d06e1fb..1da5c1b20a60 100644
@@ -593,6 +593,9 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 		rb_link = &tmp->vm_rb.rb_right;
 		rb_parent = &tmp->vm_rb;
 
+		/* Link the vma into the MT */
+		vma_store(mm, tmp);
+
 		mm->map_count++;
 		if (!(tmp->vm_flags & VM_WIPEONFORK))
 			retval = copy_page_range(tmp, mpnt);
@@ -1076,6 +1079,7 @@ static struct mm_struct *mm_init(struct mm_struct *mm, struct task_struct *p,
 {
 	mm->mmap = NULL;
 	mm->mm_rb = RB_ROOT;
+	mt_init_flags(&mm->mm_mt, MAPLE_ALLOC_RANGE);
 	mm->vmacache_seqnum = 0;
 	atomic_set(&mm->mm_users, 1);
 	atomic_set(&mm->mm_count, 1);
mm/init-mm.c +2 -0
index b4a6f38fb51d..e4a058f7e8b6 100644
@@ -1,6 +1,7 @@
 // SPDX-License-Identifier: GPL-2.0
 #include <linux/mm_types.h>
 #include <linux/rbtree.h>
+#include <linux/maple_tree.h>
 #include <linux/rwsem.h>
 #include <linux/spinlock.h>
 #include <linux/list.h>
@@ -28,6 +29,7 @@
  */
 struct mm_struct init_mm = {
 	.mm_rb		= RB_ROOT,
+	.mm_mt		= MTREE_INIT(mm_mt, MAPLE_ALLOC_RANGE),
 	.pgd		= swapper_pg_dir,
 	.mm_users	= ATOMIC_INIT(2),
 	.mm_count	= ATOMIC_INIT(1),
mm/internal.h +77 -0

83 lines not on this page · raw message

mm/mmap.c +227 -2

484 lines not on this page · raw message

Signature · 1 line
2.30.2
#7 lore raw

PATCH v2 7/61 mm/mmap: Use the maple tree in find_vma() instead of the rbtree.

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Using the maple tree interface mt_find() will handle the RCU locking and will start searching at the address up to the limit, ULONG_MAX in this case.

Add kernel documentation to this API.

---
 mm/mmap.c | 28 ++++++++++------------------
 1 file changed, 10 insertions(+), 18 deletions(-)
mm/mmap.c +10 -18
index e891977293fa..899747a75d5c 100644
@@ -2487,10 +2487,16 @@ get_unmapped_area(struct file *file, unsigned long addr, unsigned long len,
 
 EXPORT_SYMBOL(get_unmapped_area);
 
-/* Look up the first VMA which satisfies  addr < vm_end,  NULL if none. */
+/**
+ * find_vma() - Find the VMA for a given address, or the next vma.
+ * @mm: The mm_struct to check
+ * @addr: The address
+ *
+ * Returns: The VMA associated with addr, or the next vma.
+ * May return %NULL in the case of no vma at addr or above.
+ */
 struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
 {
-	struct rb_node *rb_node;
 	struct vm_area_struct *vma;
 
 	mmap_assert_locked(mm);
@@ -2499,24 +2505,10 @@ struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
 	if (likely(vma))
 		return vma;
 
-	rb_node = mm->mm_rb.rb_node;
-
-	while (rb_node) {
-		struct vm_area_struct *tmp;
-
-		tmp = rb_entry(rb_node, struct vm_area_struct, vm_rb);
-
-		if (tmp->vm_end > addr) {
-			vma = tmp;
-			if (tmp->vm_start <= addr)
-				break;
-			rb_node = rb_node->rb_left;
-		} else
-			rb_node = rb_node->rb_right;
-	}
-
+	vma = mt_find(&mm->mm_mt, &addr, ULONG_MAX);
 	if (vma)
 		vmacache_update(addr, vma);
+
 	return vma;
 }
 EXPORT_SYMBOL(find_vma);
Signature · 1 line
2.30.2
#8 lore raw

PATCH v2 8/61 mm/mmap: Use the maple tree for find_vma_prev() instead of the rbtree

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Use the maple tree's advanced API and a maple state to walk the tree for the entry at the address or the next vma, then use the maple state to walk back one entry to find the previous entry. Note, the advanced maple tree interface does not handle the rcu locking.

Add kernel documentation comments for this API.

---
 mm/mmap.c | 27 +++++++++++++++++----------
 1 file changed, 17 insertions(+), 10 deletions(-)
mm/mmap.c +17 -10
index 899747a75d5c..4d996ab2372a 100644
@@ -2513,23 +2513,30 @@ struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
 }
 EXPORT_SYMBOL(find_vma);
 
-/*
- * Same as find_vma, but also return a pointer to the previous VMA in *pprev.
+/**
+ * find_vma_prev() - Find the VMA for a given address, or the next vma and
+ * set %pprev to the previous VMA, if any.
+ * @mm: The mm_struct to check
+ * @addr: The address
+ * @pprev: The pointer to set to the previous VMA
+ *
+ * Returns: The VMA associated with @addr, or the next vma.
+ * May return %NULL in the case of no vma at addr or above.
  */
 struct vm_area_struct *
 find_vma_prev(struct mm_struct *mm, unsigned long addr,
-			struct vm_area_struct **pprev)
+	      struct vm_area_struct **pprev)
 {
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, addr, addr);
 
-	vma = find_vma(mm, addr);
-	if (vma) {
-		*pprev = vma->vm_prev;
-	} else {
-		struct rb_node *rb_node = rb_last(&mm->mm_rb);
+	rcu_read_lock();
+	vma = mas_find(&mas, ULONG_MAX);
+	if (!vma)
+		mas_reset(&mas);
 
-		*pprev = rb_node ? rb_entry(rb_node, struct vm_area_struct, vm_rb) : NULL;
-	}
+	*pprev = mas_prev(&mas, 0);
+	rcu_read_unlock();
 	return vma;
 }
 
Signature · 1 line
2.30.2
#9 lore raw

PATCH v2 9/61 mm/mmap: Use maple tree for unmapped_area{_topdown}

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

The maple tree code was added to find the unmapped area in a previous commit and was checked against what the rbtree returned, but the actual result was never used. Start using the maple tree implementation and remove the rbtree code. Note, the advanced maple tree interface is used so the rcu locking is needed to be handled here or at a higher level.

Add kernel documentation comment for these functions.

---
 mm/mmap.c | 262 ++++++++----------------------------------------------
 1 file changed, 35 insertions(+), 227 deletions(-)
mm/mmap.c +35 -227
index 4d996ab2372a..fac6e2554351 100644
@@ -2053,21 +2053,20 @@ unsigned long mmap_region(struct file *file, unsigned long addr,
 	return error;
 }
 
+/* unmapped_area() Find an area between the low_limit and the high_limit with
+ * the correct alignment and offset, all from @info. Note: current->mm is used
+ * for the search.
+ *
+ * @info: The unmapped area information including the range (low_limit -
+ * hight_limit), the alignment offset and mask.
+ *
+ * Return: A memory address or -ENOMEM.
+ */
 static unsigned long unmapped_area(struct vm_unmapped_area_info *info)
 {
-	/*
-	 * We implement the search by looking for an rbtree node that
-	 * immediately follows a suitable gap. That is,
-	 * - gap_start = vma->vm_prev->vm_end <= info->high_limit - length;
-	 * - gap_end   = vma->vm_start        >= info->low_limit  + length;
-	 * - gap_end - gap_start >= length
-	 */
+	unsigned long length, gap;
 
-	struct mm_struct *mm = current->mm;
-	struct vm_area_struct *vma;
-	unsigned long length, low_limit, high_limit, gap_start, gap_end;
-	unsigned long gap;
-	MA_STATE(mas, &mm->mm_mt, 0, 0);
+	MA_STATE(mas, &current->mm->mm_mt, 0, 0);
 
 	/* Adjust search length to account for worst case alignment overhead */
 	length = info->length + info->align_mask;
@@ -2075,238 +2074,47 @@ static unsigned long unmapped_area(struct vm_unmapped_area_info *info)
 		return -ENOMEM;
 
 	rcu_read_lock();
-	mas_empty_area_rev(&mas, info->low_limit, info->high_limit - 1,
-			   length);
+	if (mas_empty_area(&mas, info->low_limit, info->high_limit - 1,
+				  length)) {
+		rcu_read_unlock();
+		return -ENOMEM;
+	}
 	rcu_read_unlock();
 	gap = mas.index;
 	gap += (info->align_offset - gap) & info->align_mask;
-
-	/* Adjust search limits by the desired length */
-	if (info->high_limit < length)
-		return -ENOMEM;
-	high_limit = info->high_limit - length;
-
-	if (info->low_limit > high_limit)
-		return -ENOMEM;
-	low_limit = info->low_limit + length;
-
-	/* Check if rbtree root looks promising */
-	if (RB_EMPTY_ROOT(&mm->mm_rb))
-		goto check_highest;
-	vma = rb_entry(mm->mm_rb.rb_node, struct vm_area_struct, vm_rb);
-	if (vma->rb_subtree_gap < length)
-		goto check_highest;
-
-	while (true) {
-		/* Visit left subtree if it looks promising */
-		gap_end = vm_start_gap(vma);
-		if (gap_end >= low_limit && vma->vm_rb.rb_left) {
-			struct vm_area_struct *left =
-				rb_entry(vma->vm_rb.rb_left,
-					 struct vm_area_struct, vm_rb);
-			if (left->rb_subtree_gap >= length) {
-				vma = left;
-				continue;
-			}
-		}
-
-		gap_start = vma->vm_prev ? vm_end_gap(vma->vm_prev) : 0;
-check_current:
-		/* Check if current node has a suitable gap */
-		if (gap_start > high_limit)
-			return -ENOMEM;
-		if (gap_end >= low_limit &&
-		    gap_end > gap_start && gap_end - gap_start >= length)
-			goto found;
-
-		/* Visit right subtree if it looks promising */
-		if (vma->vm_rb.rb_right) {
-			struct vm_area_struct *right =
-				rb_entry(vma->vm_rb.rb_right,
-					 struct vm_area_struct, vm_rb);
-			if (right->rb_subtree_gap >= length) {
-				vma = right;
-				continue;
-			}
-		}
-
-		/* Go back up the rbtree to find next candidate node */
-		while (true) {
-			struct rb_node *prev = &vma->vm_rb;
-			if (!rb_parent(prev))
-				goto check_highest;
-			vma = rb_entry(rb_parent(prev),
-				       struct vm_area_struct, vm_rb);
-			if (prev == vma->vm_rb.rb_left) {
-				gap_start = vm_end_gap(vma->vm_prev);
-				gap_end = vm_start_gap(vma);
-				goto check_current;
-			}
-		}
-	}
-
-check_highest:
-	/* Check highest gap, which does not precede any rbtree node */
-	gap_start = mm->highest_vm_end;
-	gap_end = ULONG_MAX;  /* Only for VM_BUG_ON below */
-	if (gap_start > high_limit)
-		return -ENOMEM;
-
-found:
-	/* We found a suitable gap. Clip it with the original low_limit. */
-	if (gap_start < info->low_limit)
-		gap_start = info->low_limit;
-
-	/* Adjust gap address to the desired alignment */
-	gap_start += (info->align_offset - gap_start) & info->align_mask;
-
-	VM_BUG_ON(gap_start + info->length > info->high_limit);
-	VM_BUG_ON(gap_start + info->length > gap_end);
-
-	VM_BUG_ON(gap != gap_start);
-	return gap_start;
-}
-
-static inline unsigned long top_area_aligned(struct vm_unmapped_area_info *info,
-					     unsigned long end)
-{
-	return (end - info->length - info->align_offset) & (~info->align_mask);
+	return gap;
 }
 
+/* unmapped_area_topdown() Find an area between the low_limit and the
+ * high_limit with * the correct alignment and offset at the highest available
+ * address, all from * @info. Note: current->mm is used for the search.
+ *
+ * @info: The unmapped area information including the range (low_limit -
+ * hight_limit), the alignment offset and mask.
+ *
+ * Return: A memory address or -ENOMEM.
+ */
 static unsigned long unmapped_area_topdown(struct vm_unmapped_area_info *info)
 {
-	struct mm_struct *mm = current->mm;
-	struct vm_area_struct *vma = NULL;
-	unsigned long length, low_limit, high_limit, gap_start, gap_end;
-	unsigned long gap;
-
-	MA_STATE(mas, &mm->mm_mt, 0, 0);
-	validate_mm_mt(mm);
+	unsigned long length, gap;
 
+	MA_STATE(mas, &current->mm->mm_mt, 0, 0);
 	/* Adjust search length to account for worst case alignment overhead */
 	length = info->length + info->align_mask;
 	if (length < info->length)
 		return -ENOMEM;
 
 	rcu_read_lock();
-	mas_empty_area_rev(&mas, info->low_limit, info->high_limit - 1,
-		   length);
-	rcu_read_unlock();
-	gap = (mas.index + info->align_mask) & ~info->align_mask;
-	gap -= info->align_offset & info->align_mask;
-
-	/*
-	 * Adjust search limits by the desired length.
-	 * See implementation comment at top of unmapped_area().
-	 */
-	gap_end = info->high_limit;
-	if (gap_end < length)
-		return -ENOMEM;
-	high_limit = gap_end - length;
-
-	if (info->low_limit > high_limit)
+	if (mas_empty_area_rev(&mas, info->low_limit, info->high_limit - 1,
+				length)) {
+		rcu_read_unlock();
 		return -ENOMEM;
-	low_limit = info->low_limit + length;
-
-	/* Check highest gap, which does not precede any rbtree node */
-	gap_start = mm->highest_vm_end;
-	if (gap_start <= high_limit)
-		goto found_highest;
-
-	/* Check if rbtree root looks promising */
-	if (RB_EMPTY_ROOT(&mm->mm_rb))
-		return -ENOMEM;
-	vma = rb_entry(mm->mm_rb.rb_node, struct vm_area_struct, vm_rb);
-	if (vma->rb_subtree_gap < length)
-		return -ENOMEM;
-
-	while (true) {
-		/* Visit right subtree if it looks promising */
-		gap_start = vma->vm_prev ? vm_end_gap(vma->vm_prev) : 0;
-		if (gap_start <= high_limit && vma->vm_rb.rb_right) {
-			struct vm_area_struct *right =
-				rb_entry(vma->vm_rb.rb_right,
-					 struct vm_area_struct, vm_rb);
-			if (right->rb_subtree_gap >= length) {
-				vma = right;
-				continue;
-			}
-		}
-
-check_current:
-		/* Check if current node has a suitable gap */
-		gap_end = vm_start_gap(vma);
-		if (gap_end < low_limit)
-			return -ENOMEM;
-		if (gap_start <= high_limit &&
-		    gap_end > gap_start && gap_end - gap_start >= length)
-			goto found;
-
-		/* Visit left subtree if it looks promising */
-		if (vma->vm_rb.rb_left) {
-			struct vm_area_struct *left =
-				rb_entry(vma->vm_rb.rb_left,
-					 struct vm_area_struct, vm_rb);
-			if (left->rb_subtree_gap >= length) {
-				vma = left;
-				continue;
-			}
-		}
-
-		/* Go back up the rbtree to find next candidate node */
-		while (true) {
-			struct rb_node *prev = &vma->vm_rb;
-			if (!rb_parent(prev))
-				return -ENOMEM;
-			vma = rb_entry(rb_parent(prev),
-				       struct vm_area_struct, vm_rb);
-			if (prev == vma->vm_rb.rb_right) {
-				gap_start = vma->vm_prev ?
-					vm_end_gap(vma->vm_prev) : 0;
-				goto check_current;
-			}
-		}
-	}
-
-found:
-	/* We found a suitable gap. Clip it with the original high_limit. */
-	if (gap_end > info->high_limit)
-		gap_end = info->high_limit;
-
-found_highest:
-	/* Compute highest gap address at the desired alignment */
-	gap_end -= info->length;
-	gap_end -= (gap_end - info->align_offset) & info->align_mask;
-
-	VM_BUG_ON(gap_end < info->low_limit);
-	VM_BUG_ON(gap_end < gap_start);
-
-	if (gap != gap_end) {
-		pr_err("%s: %px Gap was found: mt %lu gap_end %lu\n", __func__,
-		       mm, gap, gap_end);
-		pr_err("window was %lu - %lu size %lu\n", info->high_limit,
-		       info->low_limit, length);
-		pr_err("mas.min %lu max %lu mas.last %lu\n", mas.min, mas.max,
-		       mas.last);
-		pr_err("mas.index %lu align mask %lu offset %lu\n", mas.index,
-		       info->align_mask, info->align_offset);
-		pr_err("rb_find_vma find on %lu => %px (%px)\n", mas.index,
-		       find_vma(mm, mas.index), vma);
-#if defined(CONFIG_DEBUG_MAPLE_TREE)
-		mt_dump(&mm->mm_mt);
-#endif
-		{
-			struct vm_area_struct *dv = mm->mmap;
-
-			while (dv) {
-				printk("vma %px %lu-%lu\n", dv, dv->vm_start, dv->vm_end);
-				dv = dv->vm_next;
-			}
-		}
-		VM_BUG_ON(gap != gap_end);
 	}
+	rcu_read_unlock();
 
-	return gap_end;
+	gap = (mas.index + info->align_mask) & ~info->align_mask;
+	gap -= info->align_offset & info->align_mask;
+	return gap;
 }
 
 /*
Signature · 1 line
2.30.2
#10 lore raw

PATCH v2 10/61 kernel/fork: Use maple tree for dup_mmap() during forking

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

The maple tree was already tracking VMAs in this function by an earlier commit, but the rbtree iterator was being used to iterate the list. Change the iterator to use a maple tree native iterator, rcu locking, and switch to the maple tree advanced API to avoid multiple walks of the tree during insert operations.

anon_vma_fork() may enter the slow path and cause a schedule() call to cause rcu issues. Drop the rcu lock and reacquiring the lock. There is no harm in this approach as the mmap_sem is taken for write/read and held across the schedule() call so the VMAs will not change.

Note that the bulk allocation of nodes is also happening here for performance reasons. The node calculations are done internally to the tree and use the VMA count and assume the worst-case node requirements. The VM_DONT_COPY flag does not allow for the most efficient copy method of the tree and so a bulk loading algorithm is used.

---
 include/linux/mm.h       |  2 --
 include/linux/sched/mm.h |  9 +++++++++
 kernel/fork.c            | 35 +++++++++++++++++++++++++++++------
 mm/mmap.c                |  4 ----
 4 files changed, 38 insertions(+), 12 deletions(-)
include/linux/mm.h +0 -2
index 80b7af9e725c..ce8fc0fd6d6e 100644
@@ -2596,8 +2596,6 @@ extern bool arch_has_descending_max_zone_pfns(void);
 /* nommu.c */
 extern atomic_long_t mmap_pages_allocated;
 extern int nommu_shrink_inode_mappings(struct inode *, size_t, size_t);
-/* maple_tree */
-void vma_store(struct mm_struct *mm, struct vm_area_struct *vma);
 
 /* interval_tree.c */
 void vma_interval_tree_insert(struct vm_area_struct *node,
include/linux/sched/mm.h +9 -0
index fd6e4d14f477..0b8a4f07f3f8 100644
@@ -8,6 +8,7 @@
 #include <linux/mm_types.h>
 #include <linux/gfp.h>
 #include <linux/sync_core.h>
+#include <linux/maple_tree.h>
 
 /*
  * Routines for handling mm_structs
@@ -88,11 +89,19 @@ static inline void mmdrop_lazy_tlb(struct mm_struct *mm)
  */
 static inline void mmget(struct mm_struct *mm)
 {
+	mt_set_in_rcu(&mm->mm_mt);
 	atomic_inc(&mm->mm_users);
 }
 
 static inline bool mmget_not_zero(struct mm_struct *mm)
 {
+	/*
+	 * There is a race below during task tear down that can cause the maple
+	 * tree to enter rcu mode with only a single user.  If this race
+	 * happens, the result would be that the maple tree nodes would remain
+	 * active for an extra RCU read cycle.
+	 */
+	mt_set_in_rcu(&mm->mm_mt);
 	return atomic_inc_not_zero(&mm->mm_users);
 }
 
kernel/fork.c +29 -6
index 1da5c1b20a60..9ef5661abbd1 100644
@@ -477,7 +477,9 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 	struct vm_area_struct *mpnt, *tmp, *prev, **pprev;
 	struct rb_node **rb_link, *rb_parent;
 	int retval;
-	unsigned long charge;
+	unsigned long charge = 0;
+	MA_STATE(old_mas, &oldmm->mm_mt, 0, 0);
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 	LIST_HEAD(uf);
 
 	uprobe_start_dup_mmap();
@@ -511,11 +513,19 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 		goto out;
 
 	prev = NULL;
-	for (mpnt = oldmm->mmap; mpnt; mpnt = mpnt->vm_next) {
+
+	retval = mas_entry_count(&mas, oldmm->map_count);
+	if (retval)
+		goto out;
+
+	rcu_read_lock();
+	mas_for_each(&old_mas, mpnt, ULONG_MAX) {
 		struct file *file;
 
+		rcu_read_unlock();
 		if (mpnt->vm_flags & VM_DONTCOPY) {
 			vm_stat_account(mm, mpnt->vm_flags, -vma_pages(mpnt));
+			rcu_read_lock();
 			continue;
 		}
 		charge = 0;
@@ -525,7 +535,7 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 		 */
 		if (fatal_signal_pending(current)) {
 			retval = -EINTR;
-			goto out;
+			goto loop_out;
 		}
 		if (mpnt->vm_flags & VM_ACCOUNT) {
 			unsigned long len = vma_pages(mpnt);
@@ -553,6 +563,7 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 			tmp->anon_vma = NULL;
 		} else if (anon_vma_fork(tmp, mpnt))
 			goto fail_nomem_anon_vma_fork;
+
 		tmp->vm_flags &= ~(VM_LOCKED | VM_LOCKONFAULT);
 		file = tmp->vm_file;
 		if (file) {
@@ -594,7 +605,11 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 		rb_parent = &tmp->vm_rb;
 
 		/* Link the vma into the MT */
-		vma_store(mm, tmp);
+		mas_lock(&mas);
+		mas.index = tmp->vm_start;
+		mas.last = tmp->vm_end - 1;
+		mas_store(&mas, tmp);
+		mas_unlock(&mas);
 
 		mm->map_count++;
 		if (!(tmp->vm_flags & VM_WIPEONFORK))
@@ -604,10 +619,17 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 			tmp->vm_ops->open(tmp);
 
 		if (retval)
-			goto out;
+			goto loop_out;
+
+		rcu_read_lock();
 	}
+	rcu_read_unlock();
 	/* a new mm has just been created */
 	retval = arch_dup_mmap(oldmm, mm);
+loop_out:
+	rcu_read_lock();
+	mas_destroy(&mas);
+	rcu_read_unlock();
 out:
 	mmap_write_unlock(mm);
 	flush_tlb_mm(oldmm);
@@ -623,7 +645,7 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 fail_nomem:
 	retval = -ENOMEM;
 	vm_unacct_memory(charge);
-	goto out;
+	goto loop_out;
 }
 
 static inline int mm_alloc_pgd(struct mm_struct *mm)
@@ -1149,6 +1171,7 @@ static inline void __mmput(struct mm_struct *mm)
 {
 	VM_BUG_ON(atomic_read(&mm->mm_users));
 
+	mt_clear_in_rcu(&mm->mm_mt);
 	uprobe_clear_state(mm);
 	exit_aio(mm);
 	ksm_exit(mm);
mm/mmap.c +0 -4
index fac6e2554351..cec8ba0b598f 100644
@@ -786,10 +786,6 @@ void vma_mt_store(struct mm_struct *mm, struct vm_area_struct *vma)
 		GFP_KERNEL);
 }
 
-void vma_store(struct mm_struct *mm, struct vm_area_struct *vma) {
-	vma_mt_store(mm, vma);
-}
-
 static void
 __vma_link(struct mm_struct *mm, struct vm_area_struct *vma,
 	struct vm_area_struct *prev, struct rb_node **rb_link,
Signature · 1 line
2.30.2
#11 lore raw

PATCH v2 10/61 kernel/fork: Use maple tree for dup_mmap() during forking

Quoted 8 lines · On Tue, 17 Aug 2021 15:47:11 +0000 Liam R. Howlett wrote:

static inline void mmget(struct mm_struct *mm)
{

include/linux/sched/mm.h +1 -0
+	mt_set_in_rcu(&mm->mm_mt);
 	atomic_inc(&mm->mm_users);
 }
 
 static inline bool mmget_not_zero(struct mm_struct *mm)

include/linux/sched/mm.h static inline void mmdrop_lazy_tlb(struct mm_struct *mm) · line 106

Quoted 10 lines
include/linux/sched/mm.h +7 -0
 {
+	/*
+	 * There is a race below during task tear down that can cause the maple
+	 * tree to enter rcu mode with only a single user.  If this race
+	 * happens, the result would be that the maple tree nodes would remain
+	 * active for an extra RCU read cycle.
+	 */
+	mt_set_in_rcu(&mm->mm_mt);
 	return atomic_inc_not_zero(&mm->mm_users);
 }

Nit, leave the mm with zero refcount intact.

 	if (atomic_inc_not_zero(&mm->mm_users)) {
		mt_set_in_rcu(&mm->mm_mt);
		return true;
	}
	return false;
#12 lore raw

Re: [PATCH v2 10/61] kernel/fork: Use maple tree for dup_mmap() during forking

Quoted 22 lines · Hillf Danton
Quoted 8 lines · On Tue, 17 Aug 2021 15:47:11 +0000 Liam R. Howlett wrote:

static inline void mmget(struct mm_struct *mm)
{

include/linux/sched/mm.h +1 -0
+	mt_set_in_rcu(&mm->mm_mt);
 	atomic_inc(&mm->mm_users);
 }
 
 static inline bool mmget_not_zero(struct mm_struct *mm)

include/linux/sched/mm.h static inline void mmdrop_lazy_tlb(struct mm_struct *mm) · line 106

Quoted 10 lines
include/linux/sched/mm.h +7 -0
 {
+	/*
+	 * There is a race below during task tear down that can cause the maple
+	 * tree to enter rcu mode with only a single user.  If this race
+	 * happens, the result would be that the maple tree nodes would remain
+	 * active for an extra RCU read cycle.
+	 */
+	mt_set_in_rcu(&mm->mm_mt);
 	return atomic_inc_not_zero(&mm->mm_users);
 }

Nit, leave the mm with zero refcount intact.

Quoted 5 lines
 	if (atomic_inc_not_zero(&mm->mm_users)) {
		mt_set_in_rcu(&mm->mm_mt);
		return true;
	}
	return false;

Thanks for looking at this.

I thought about that, but came up with the following scenario:

thread 1 thread 2
mmget(mm)

		mmget_not_zero() enter..
		atomic_inc_not_zero(&mm->mm_users)
mmput(mm)
		mt_set_in_rcu(&mm->mm_mt);
		return true;

So I think the above does not remove the race, but does add instructions to each call to mmget_not_zero(). I thought the race of having nodes sitting around for an rcu read cycle was worth the trade off.

Cheers,
Liam

#13 lore raw

Re: [PATCH v2 10/61] kernel/fork: Use maple tree for dup_mmap() during forking

Quoted 33 lines · On Wed, 18 Aug 2021 14:54:29 +0000 Liam R. Howlett wrote:
Quoted 22 lines · Hillf Danton
Quoted 8 lines · On Tue, 17 Aug 2021 15:47:11 +0000 Liam R. Howlett wrote:

static inline void mmget(struct mm_struct *mm)
{

include/linux/sched/mm.h +1 -0
+	mt_set_in_rcu(&mm->mm_mt);
 	atomic_inc(&mm->mm_users);
 }
 
 static inline bool mmget_not_zero(struct mm_struct *mm)

include/linux/sched/mm.h static inline void mmdrop_lazy_tlb(struct mm_struct *mm) · line 106

Quoted 10 lines
include/linux/sched/mm.h +7 -0
 {
+	/*
+	 * There is a race below during task tear down that can cause the maple
+	 * tree to enter rcu mode with only a single user.  If this race
+	 * happens, the result would be that the maple tree nodes would remain
+	 * active for an extra RCU read cycle.
+	 */
+	mt_set_in_rcu(&mm->mm_mt);
 	return atomic_inc_not_zero(&mm->mm_users);
 }

Nit, leave the mm with zero refcount intact.

Quoted 5 lines
 	if (atomic_inc_not_zero(&mm->mm_users)) {
		mt_set_in_rcu(&mm->mm_mt);
		return true;
	}
	return false;

Thanks for looking at this.

I thought about that, but came up with the following scenario:

Quoted 8 lines

thread 1 thread 2
mmget(mm)

		mmget_not_zero() enter..
		atomic_inc_not_zero(&mm->mm_users)
mmput(mm)
		mt_set_in_rcu(&mm->mm_mt);
		return true;

At first glance, given the above mmget, mmput will not hurt anyone.

Quoted 2 lines

So I think the above does not remove the race, but does add instructions

If the mm refcount drops to one after mmput then it is one before atomic_inc_not_zero() which only ensures the mm is stable afterwards until mmput again.

Quoted 2 lines

to each call to mmget_not_zero(). I thought the race of having nodes sitting around for an rcu read cycle was worth the trade off.

Is one ounce of the mm stability worth two pounds? Or three?

#14 lore raw

Re: [PATCH v2 10/61] kernel/fork: Use maple tree for dup_mmap() during forking

Quoted 43 lines · Hillf Danton
Quoted 33 lines · On Wed, 18 Aug 2021 14:54:29 +0000 Liam R. Howlett wrote:
Quoted 22 lines · Hillf Danton
Quoted 8 lines · On Tue, 17 Aug 2021 15:47:11 +0000 Liam R. Howlett wrote:

static inline void mmget(struct mm_struct *mm)
{

include/linux/sched/mm.h +1 -0
+	mt_set_in_rcu(&mm->mm_mt);
 	atomic_inc(&mm->mm_users);
 }
 
 static inline bool mmget_not_zero(struct mm_struct *mm)

include/linux/sched/mm.h static inline void mmdrop_lazy_tlb(struct mm_struct *mm) · line 106

Quoted 10 lines
include/linux/sched/mm.h +7 -0
 {
+	/*
+	 * There is a race below during task tear down that can cause the maple
+	 * tree to enter rcu mode with only a single user.  If this race
+	 * happens, the result would be that the maple tree nodes would remain
+	 * active for an extra RCU read cycle.
+	 */
+	mt_set_in_rcu(&mm->mm_mt);
 	return atomic_inc_not_zero(&mm->mm_users);
 }

Nit, leave the mm with zero refcount intact.

Quoted 5 lines
 	if (atomic_inc_not_zero(&mm->mm_users)) {
		mt_set_in_rcu(&mm->mm_mt);
		return true;
	}
	return false;

Thanks for looking at this.

I thought about that, but came up with the following scenario:

Quoted 8 lines

thread 1 thread 2
mmget(mm)

		mmget_not_zero() enter..
		atomic_inc_not_zero(&mm->mm_users)
mmput(mm)
		mt_set_in_rcu(&mm->mm_mt);
		return true;
Quoted 1 line

At first glance, given the above mmget, mmput will not hurt anyone.

In the case above, the maple tree enters RCU mode with a single user. This will have the result of nodes being freed in RCU mode which is the same result as what happens as it is written, except the racing thread wins (in this case). I thought this was what you were trying to fix?

Quoted 7 lines
Quoted 3 lines

So I think the above does not remove the race, but does add instructions

If the mm refcount drops to one after mmput then it is one before atomic_inc_not_zero() which only ensures the mm is stable afterwards until mmput again.

Right. The race we are worried about is the zero referenced mm. If mm->mm_users is safe, then mm->mm_mt is also safe.

Quoted 5 lines
Quoted 3 lines

to each call to mmget_not_zero(). I thought the race of having nodes sitting around for an rcu read cycle was worth the trade off.

Is one ounce of the mm stability worth two pounds? Or three?

I don't see a stability problem with the way it is written. Your change does not remove the race. Can you explain how the stability is affected negatively by the way it is written?

Thanks,
Liam

#15 lore raw

Re: [PATCH v2 10/61] kernel/fork: Use maple tree for dup_mmap() during forking

In reply to Hillf Danton
Quoted 93 lines · Hillf Danton
Quoted 64 lines · On Thu, 19 Aug 2021 13:32:58 +0000 Liam R. Howlett wrote:
Quoted 10 lines · Hillf Danton
Quoted 9 lines · On Wed, 18 Aug 2021 14:54:29 +0000 Liam R. Howlett wrote:
Quoted 8 lines · Hillf Danton
Quoted 7 lines · On Tue, 17 Aug 2021 15:47:11 +0000 Liam R. Howlett wrote:

static inline void mmget(struct mm_struct *mm)
{

include/linux/sched/mm.h +1 -0
+	mt_set_in_rcu(&mm->mm_mt);
 	atomic_inc(&mm->mm_users);
 }
Quoted 4 lines
Quoted 4 lines
Quoted 4 lines

Review

Quoted 4 lines

static inline bool mmget_not_zero(struct mm_struct *mm) {

(quoted diff) +2 -0
+	/*
+	 * There is a race below during task tear down that can cause the =

maple

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

Review

Quoted 2 lines
(quoted diff) +2 -0
+	 * tree to enter rcu mode with only a single user.  If this race
+	 * happens, the result would be that the maple tree nodes would re=

main

Quoted 26 lines
Quoted 18 lines
Quoted 8 lines

include/linux/sched/mm.h static inline void mmdrop_lazy_tlb(struct mm_struct *mm) · line 106

Quoted 5 lines
include/linux/sched/mm.h +3 -0
+	 * active for an extra RCU read cycle.
+	 */
+	mt_set_in_rcu(&mm->mm_mt);
 	return atomic_inc_not_zero(&mm->mm_users);
 }

Nit, leave the mm with zero refcount intact.

Quoted 5 lines
 	if (atomic_inc_not_zero(&mm->mm_users)) {
		mt_set_in_rcu(&mm->mm_mt);
		return true;
	}
	return false;

Thanks for looking at this.

I thought about that, but came up with the following scenario:

Quoted 8 lines

thread 1 thread 2
mmget(mm)

		mmget_not_zero() enter..
		atomic_inc_not_zero(&mm->mm_users)
mmput(mm)
		mt_set_in_rcu(&mm->mm_mt);
		return true;
Quoted 2 lines

=20
At first glance, given the above mmget, mmput will not hurt anyone.

In the case above, the maple tree enters RCU mode with a single user. This will have the result of nodes being freed in RCU mode which is the same result as what happens as it is written, except the racing thread wins (in this case). I thought this was what you were trying to fix?

Quoted 7 lines

=20

Quoted 2 lines

So I think the above does not remove the race, but does add instructions

=20
If the mm refcount drops to one after mmput then it is one before atomic_inc_not_zero() which only ensures the mm is stable afterwards until mmput again.

Right. The race we are worried about is the zero referenced mm. If mm->mm_users is safe, then mm->mm_mt is also safe.

Quoted 7 lines
Quoted 5 lines

=20

Quoted 2 lines

to each call to mmget_not_zero(). I thought the race of having nodes sitting around for an rcu read cycle was worth the trade off.

=20
Is one ounce of the mm stability worth two pounds? Or three?

I don't see a stability problem with the way it is written.

On the maple tree side, I see in
[PATCH v2 05/61] Maple Tree: Add new data structure

+ * MAPLE_USE_RCU Operate in read/copy/update mode for multi-readers

<...>

(quoted diff) +12 -0
+/**
+ * mt_set_in_rcu() - Switch the tree to RCU safe mode.
+ */
+static inline void mt_set_in_rcu(struct maple_tree *mt)
+{
+	if (mt_in_rcu(mt))
+		return;
+
+	mtree_lock(mt);
+	mt->ma_flags |= MAPLE_USE_RCU;
+	mtree_unlock(mt);
+}
Quoted 2 lines

and on the mm side, however, if atomic_inc_not_zero(&mm->mm_users) fails then who can be the "RCU multi-readers"?

There wouldn't be one. But the consequence is that the maple tree nodes will remain active for one extra RCU cycle. This is why there is a big comment above mmget_not_zero() explaining how this race exists but will cause no issue.

Quoted 5 lines
Quoted 2 lines

Your change does not remove the race.

If atomic_inc_not_zero() fails then there is no pre-condition in any form for race; if it succeeds then the race window is slammed.

My example shows how we can still end up with the tree being in RCU mode with a single thread. atomic_inc_not_zero() succeeds, then the other thread drops the reference counter before the maple tree enters RCU mode.

Quoted 6 lines
Quoted 3 lines

Can you explain how the stability is affected negatively by the way it is written?

Hard to find the correct answer without knowing why you prefer to update the flags for mm->mm_mt with mm->mm_users dropping down to ground.

I prefer to update the flags for mm->mm_mt first because the fallout is minimal, however the alternative is to increase the execution time for the vast majority of calls. The trade off just isn't worth it, especially since the tree may be left in RCU mode with a single user anyways. There is no stability issue here.

Thank you,
Liam

#16 lore raw

PATCH v2 11/61 mm: Remove rb tree.

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Remove the RB tree and start using the maple tree for vm_area_struct tracking.

Drop validate_mm() calls in expand_upwards() and expand_downwards() as the lock is not held.

---
 arch/x86/kernel/tboot.c    |   1 -
 drivers/firmware/efi/efi.c |   1 -
 fs/proc/task_nommu.c       |  55 ++--
 include/linux/mm.h         |   9 +-
 include/linux/mm_types.h   |  24 +-
 kernel/fork.c              |   8 -
 mm/init-mm.c               |   2 -
 mm/mmap.c                  | 527 ++++++++-----------------------------
 mm/nommu.c                 |  95 +++----
 mm/util.c                  |   8 +
 10 files changed, 185 insertions(+), 545 deletions(-)
arch/x86/kernel/tboot.c +0 -1
index 6f978f722dff..121f28bb2209 100644
@@ -97,7 +97,6 @@ void __init tboot_probe(void)
 
 static pgd_t *tboot_pg_dir;
 static struct mm_struct tboot_mm = {
-	.mm_rb          = RB_ROOT,
 	.mm_mt          = MTREE_INIT(mm_mt, MAPLE_ALLOC_RANGE),
 	.pgd            = swapper_pg_dir,
 	.mm_users       = ATOMIC_INIT(2),
drivers/firmware/efi/efi.c +0 -1
index 1aaecca36e23..2ac01505592a 100644
@@ -54,7 +54,6 @@ static unsigned long __initdata mem_reserve = EFI_INVALID_TABLE_ADDR;
 static unsigned long __initdata rt_prop = EFI_INVALID_TABLE_ADDR;
 
 struct mm_struct efi_mm = {
-	.mm_rb			= RB_ROOT,
 	.mm_mt			= MTREE_INIT(mm_mt, MAPLE_ALLOC_RANGE),
 	.mm_users		= ATOMIC_INIT(2),
 	.mm_count		= ATOMIC_INIT(1),
fs/proc/task_nommu.c +28 -27

129 lines not on this page · raw message

include/linux/mm.h +1 -8
index ce8fc0fd6d6e..701cd8fa7750 100644
@@ -2651,8 +2651,6 @@ extern int __split_vma(struct mm_struct *, struct vm_area_struct *,
 extern int split_vma(struct mm_struct *, struct vm_area_struct *,
 	unsigned long addr, int new_below);
 extern int insert_vm_struct(struct mm_struct *, struct vm_area_struct *);
-extern void __vma_link_rb(struct mm_struct *, struct vm_area_struct *,
-	struct rb_node **, struct rb_node *);
 extern void unlink_file_vma(struct vm_area_struct *);
 extern struct vm_area_struct *copy_vma(struct vm_area_struct **,
 	unsigned long addr, unsigned long len, pgoff_t pgoff,
@@ -2807,12 +2805,7 @@ struct vm_area_struct *find_vma_intersection(struct mm_struct *mm,
 static inline
 struct vm_area_struct *vma_lookup(struct mm_struct *mm, unsigned long addr)
 {
-	struct vm_area_struct *vma = find_vma(mm, addr);
-
-	if (vma && addr < vma->vm_start)
-		vma = NULL;
-
-	return vma;
+       return mtree_load(&mm->mm_mt, addr);
 }
 
 static inline unsigned long vm_start_gap(struct vm_area_struct *vma)
include/linux/mm_types.h +6 -18
index b13fa84d5134..514aca4fe9d4 100644
@@ -405,19 +405,6 @@ struct vm_area_struct {
 
 	/* linked list of VM areas per task, sorted by address */
 	struct vm_area_struct *vm_next, *vm_prev;
-
-	struct rb_node vm_rb;
-
-	/*
-	 * Largest free memory gap in bytes to the left of this VMA.
-	 * Either between this VMA and vma->vm_prev, or between one of the
-	 * VMAs below us in the VMA rbtree and its ->vm_prev. This helps
-	 * get_unmapped_area find a free area of the right size.
-	 */
-	unsigned long rb_subtree_gap;
-
-	/* Second cache line starts here. */
-
 	struct mm_struct *vm_mm;	/* The address space we belong to. */
 
 	/*
@@ -427,6 +414,11 @@ struct vm_area_struct {
 	pgprot_t vm_page_prot;
 	unsigned long vm_flags;		/* Flags, see mm.h. */
 
+	/* Information about our backing store: */
+	unsigned long vm_pgoff;		/* Offset (within vm_file) in PAGE_SIZE
+					 * units
+					 */
+	struct file *vm_file;		/* File we map to (can be NULL). */
 	/*
 	 * For areas with an address space and backing store,
 	 * linkage into the address_space->i_mmap interval tree.
@@ -449,12 +441,9 @@ struct vm_area_struct {
 	/* Function pointers to deal with this struct. */
 	const struct vm_operations_struct *vm_ops;
 
-	/* Information about our backing store: */
-	unsigned long vm_pgoff;		/* Offset (within vm_file) in PAGE_SIZE
-					   units */
-	struct file * vm_file;		/* File we map to (can be NULL). */
 	void * vm_private_data;		/* was vm_pte (shared mem) */
 
+
 #ifdef CONFIG_SWAP
 	atomic_long_t swap_readahead_info;
 #endif
@@ -483,7 +472,6 @@ struct mm_struct {
 	struct {
 		struct vm_area_struct *mmap;		/* list of VMAs */
 		struct maple_tree mm_mt;
-		struct rb_root mm_rb;
 		u64 vmacache_seqnum;                   /* per-thread vmacache */
 #ifdef CONFIG_MMU
 		unsigned long (*get_unmapped_area) (struct file *filp,
kernel/fork.c +0 -8
index 9ef5661abbd1..4311715e9266 100644
@@ -475,7 +475,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 					struct mm_struct *oldmm)
 {
 	struct vm_area_struct *mpnt, *tmp, *prev, **pprev;
-	struct rb_node **rb_link, *rb_parent;
 	int retval;
 	unsigned long charge = 0;
 	MA_STATE(old_mas, &oldmm->mm_mt, 0, 0);
@@ -502,8 +501,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 	mm->exec_vm = oldmm->exec_vm;
 	mm->stack_vm = oldmm->stack_vm;
 
-	rb_link = &mm->mm_rb.rb_node;
-	rb_parent = NULL;
 	pprev = &mm->mmap;
 	retval = ksm_fork(mm, oldmm);
 	if (retval)
@@ -600,10 +597,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 		tmp->vm_prev = prev;
 		prev = tmp;
 
-		__vma_link_rb(mm, tmp, rb_link, rb_parent);
-		rb_link = &tmp->vm_rb.rb_right;
-		rb_parent = &tmp->vm_rb;
-
 		/* Link the vma into the MT */
 		mas_lock(&mas);
 		mas.index = tmp->vm_start;
@@ -1100,7 +1093,6 @@ static struct mm_struct *mm_init(struct mm_struct *mm, struct task_struct *p,
 	struct user_namespace *user_ns)
 {
 	mm->mmap = NULL;
-	mm->mm_rb = RB_ROOT;
 	mt_init_flags(&mm->mm_mt, MAPLE_ALLOC_RANGE);
 	mm->vmacache_seqnum = 0;
 	atomic_set(&mm->mm_users, 1);
mm/init-mm.c +0 -2
index e4a058f7e8b6..e5b2c618cbb6 100644
@@ -1,6 +1,5 @@
 // SPDX-License-Identifier: GPL-2.0
 #include <linux/mm_types.h>
-#include <linux/rbtree.h>
 #include <linux/maple_tree.h>
 #include <linux/rwsem.h>
 #include <linux/spinlock.h>
@@ -28,7 +27,6 @@
  * and size this cpu_bitmask to NR_CPUS.
  */
 struct mm_struct init_mm = {
-	.mm_rb		= RB_ROOT,
 	.mm_mt		= MTREE_INIT(mm_mt, MAPLE_ALLOC_RANGE),
 	.pgd		= swapper_pg_dir,
 	.mm_users	= ATOMIC_INIT(2),
mm/mmap.c +112 -415

883 lines not on this page · raw message

mm/nommu.c +30 -65

152 lines not on this page · raw message

mm/util.c +8 -0
index 2b0ad4e810d5..af8508e07a8e 100644
@@ -287,6 +287,8 @@ void __vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma,
 	vma->vm_next = next;
 	if (next)
 		next->vm_prev = vma;
+	else
+		mm->highest_vm_end = vm_end_gap(vma);
 }
 
 void __vma_unlink_list(struct mm_struct *mm, struct vm_area_struct *vma)
@@ -301,6 +303,12 @@ void __vma_unlink_list(struct mm_struct *mm, struct vm_area_struct *vma)
 		mm->mmap = next;
 	if (next)
 		next->vm_prev = prev;
+	else {
+		if (prev)
+			mm->highest_vm_end = vm_end_gap(prev);
+		else
+			mm->highest_vm_end = 0;
+	}
 }
 
 /* Check if the vma is being used as a stack by this task */
Signature · 1 line
2.30.2
#17 lore raw

Re: [PATCH v2 11/61] mm: Remove rb tree.

Quoted 9 lines · Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Remove the RB tree and start using the maple tree for vm_area_struct tracking.

Drop validate_mm() calls in expand_upwards() and expand_downwards() as the lock is not held.

[...]

Why are we reshuffling the code below? This either needs a good justification or should just be dropped as it introduces noise. Maybe I am missing something important.

Quoted 14 lines

/*

include/linux/mm_types.h +5 -0
@@ -427,6 +414,11 @@ struct vm_area_struct {
  	pgprot_t vm_page_prot;
  	unsigned long vm_flags;		/* Flags, see mm.h. */
 
+	/* Information about our backing store: */
+	unsigned long vm_pgoff;		/* Offset (within vm_file) in PAGE_SIZE
+					 * units
+					 */
+	struct file *vm_file;		/* File we map to (can be NULL). */
  	/*
  	 * For areas with an address space and backing store,
  	 * linkage into the address_space->i_mmap interval tree.

include/linux/mm_types.h struct vm_area_struct { · line 446

Quoted 10 lines
include/linux/mm_types.h +1 -4
@@ -449,12 +441,9 @@ struct vm_area_struct {
  	/* Function pointers to deal with this struct. */
  	const struct vm_operations_struct *vm_ops;
 
-	/* Information about our backing store: */
-	unsigned long vm_pgoff;		/* Offset (within vm_file) in PAGE_SIZE
-					   units */
-	struct file * vm_file;		/* File we map to (can be NULL). */
  	void * vm_private_data;		/* was vm_pte (shared mem) */
 
+

Another unrelated change (there seem to some more in this patch)

Signature · 3 lines
Thanks,

David / dhildenb
#18 lore raw

Re: [PATCH v2 11/61] mm: Remove rb tree.

Quoted 32 lines · David Hildenbrand
Quoted 9 lines · Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Remove the RB tree and start using the maple tree for vm_area_struct tracking.

Drop validate_mm() calls in expand_upwards() and expand_downwards() as the lock is not held.

[...]

Why are we reshuffling the code below? This either needs a good justification or should just be dropped as it introduces noise. Maybe I am missing something important.

Quoted 13 lines

/*

include/linux/mm_types.h +5 -0
@@ -427,6 +414,11 @@ struct vm_area_struct {
  	pgprot_t vm_page_prot;
  	unsigned long vm_flags;		/* Flags, see mm.h. */
+	/* Information about our backing store: */
+	unsigned long vm_pgoff;		/* Offset (within vm_file) in PAGE_SIZE
+					 * units
+					 */
+	struct file *vm_file;		/* File we map to (can be NULL). */
  	/*
  	 * For areas with an address space and backing store,
  	 * linkage into the address_space->i_mmap interval tree.
@@ -449,12 +441,9 @@ struct vm_area_struct {
Quoted 8 lines

include/linux/mm_types.h struct vm_area_struct { · line 446

Quoted 8 lines
include/linux/mm_types.h +1 -4
  	/* Function pointers to deal with this struct. */
  	const struct vm_operations_struct *vm_ops;
-	/* Information about our backing store: */
-	unsigned long vm_pgoff;		/* Offset (within vm_file) in PAGE_SIZE
-					   units */
-	struct file * vm_file;		/* File we map to (can be NULL). */
  	void * vm_private_data;		/* was vm_pte (shared mem) */
+

Thank you, I will drop this from the next revision.

Quoted 2 lines

Another unrelated change (there seem to some more in this patch)

I'll have a look though it again.

Thanks,
Liam

#19 lore raw

PATCH v2 12/61 xen/privcmd: Optimized privcmd_ioctl_mmap() by using vma_lookup()

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

vma_lookup() walks the VMA tree for a specific value, find_vma() will search the tree after walking to a specific value. It is more efficient to only walk to the requested value as this case requires the address to equal the vm_start.

---
 drivers/xen/privcmd.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
drivers/xen/privcmd.c +1 -1
index 720a7b7abd46..5f903ae9af7e 100644
@@ -282,7 +282,7 @@ static long privcmd_ioctl_mmap(struct file *file, void __user *udata)
 						     struct page, lru);
 		struct privcmd_mmap_entry *msg = page_address(page);
 
-		vma = find_vma(mm, msg->va);
+		vma = vma_lookup(mm, msg->va);
 		rc = -EINVAL;
 
 		if (!vma || (msg->va != vma->vm_start) || vma->vm_private_data)
Signature · 1 line
2.30.2
#20 lore raw

PATCH v2 13/61 mm: Optimize find_exact_vma() to use vma_lookup()

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Use vma_lookup() to walk the tree to the start value requested. If the vma at the start does not match, then the answer is NULL and there is no need to look at the next vma the way that find_vma() would.

---
 include/linux/mm.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
include/linux/mm.h +1 -1
index 701cd8fa7750..a3086474d8d2 100644
@@ -2841,7 +2841,7 @@ static inline unsigned long vma_pages(struct vm_area_struct *vma)
 static inline struct vm_area_struct *find_exact_vma(struct mm_struct *mm,
 				unsigned long vm_start, unsigned long vm_end)
 {
-	struct vm_area_struct *vma = find_vma(mm, vm_start);
+	struct vm_area_struct *vma = vma_lookup(mm, vm_start);
 
 	if (vma && (vma->vm_start != vm_start || vma->vm_end != vm_end))
 		vma = NULL;
Signature · 1 line
2.30.2
#21 lore raw

PATCH v2 14/61 mm/khugepaged: Optimize collapse_pte_mapped_thp() by using vma_lookup()

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

vma_lookup() will walk the vma tree once and not continue to look for the next vma. Since the exact vma is checked below, this is a more optimal way of searching.

---
 mm/khugepaged.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
mm/khugepaged.c +1 -1
index 6b9c98ddcd09..3a43610141bb 100644
@@ -1430,7 +1430,7 @@ static int khugepaged_add_pte_mapped_thp(struct mm_struct *mm,
 void collapse_pte_mapped_thp(struct mm_struct *mm, unsigned long addr)
 {
 	unsigned long haddr = addr & HPAGE_PMD_MASK;
-	struct vm_area_struct *vma = find_vma(mm, haddr);
+	struct vm_area_struct *vma = vma_lookup(mm, haddr);
 	struct page *hpage;
 	pte_t *start_pte, *pte;
 	pmd_t *pmd, _pmd;
Signature · 1 line
2.30.2
#22 lore raw

PATCH v2 15/61 mm/mmap: Change do_brk_flags() to expand existing VMA and add do_brk_munmap()

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Avoid allocating a new VMA when it a vma modification can occur. When a brk() can expand or contract a VMA, then the single store operation will only modify one index of the maple tree instead of causing a node to split or coalesce. This avoids unnecessary allocations/frees of maple tree nodes and VMAs.

Use the advanced API for the maple tree to avoid unnecessary walks of the tree.

---
 mm/mmap.c | 278 +++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 224 insertions(+), 54 deletions(-)
mm/mmap.c +224 -54
index 04b9dec91bd2..3d88fc87c289 100644
@@ -190,17 +190,22 @@ static struct vm_area_struct *remove_vma(struct vm_area_struct *vma)
 	return next;
 }
 
-static int do_brk_flags(unsigned long addr, unsigned long request, unsigned long flags,
-		struct list_head *uf);
+static int do_brk_munmap(struct ma_state *mas, struct vm_area_struct *vma,
+			 unsigned long newbrk, unsigned long oldbrk,
+			 struct list_head *uf);
+static int do_brk_flags(struct ma_state *mas, struct vm_area_struct **brkvma,
+			unsigned long addr, unsigned long request,
+			unsigned long flags);
 SYSCALL_DEFINE1(brk, unsigned long, brk)
 {
 	unsigned long newbrk, oldbrk, origbrk;
 	struct mm_struct *mm = current->mm;
-	struct vm_area_struct *next;
+	struct vm_area_struct *brkvma, *next = NULL;
 	unsigned long min_brk;
 	bool populate;
 	bool downgraded = false;
 	LIST_HEAD(uf);
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	if (mmap_write_lock_killable(mm))
 		return -EINTR;
@@ -240,37 +245,60 @@ SYSCALL_DEFINE1(brk, unsigned long, brk)
 		goto success;
 	}
 
-	/*
-	 * Always allow shrinking brk.
-	 * __do_munmap() may downgrade mmap_lock to read.
-	 */
-	if (brk <= mm->brk) {
+	mas_set(&mas, newbrk);
+	mas_lock(&mas);
+	brkvma = mas_walk(&mas);
+	mas_unlock(&mas);
+	if (brkvma) { // munmap necessary, there is something at newbrk.
+		/*
+		 * Always allow shrinking brk.
+		 * do_brk_munmap() may downgrade mmap_lock to read.
+		 */
 		int ret;
 
+		if (brkvma->vm_start >= oldbrk)
+			goto out; // mapping intersects with an existing non-brk vma.
 		/*
-		 * mm->brk must to be protected by write mmap_lock so update it
-		 * before downgrading mmap_lock. When __do_munmap() fails,
-		 * mm->brk will be restored from origbrk.
+		 * mm->brk must to be protected by write mmap_lock.
+		 * do_brk_munmap() may downgrade the lock,  so update it
+		 * before calling do_brk_munmap().
 		 */
 		mm->brk = brk;
-		ret = __do_munmap(mm, newbrk, oldbrk-newbrk, &uf, true);
-		if (ret < 0) {
-			mm->brk = origbrk;
-			goto out;
-		} else if (ret == 1) {
+		mas.last = oldbrk - 1;
+		ret = do_brk_munmap(&mas, brkvma, newbrk, oldbrk, &uf);
+		if (ret == 1)  {
 			downgraded = true;
-		}
-		goto success;
-	}
+			goto success;
+		} else if (!ret)
+			goto success;
 
+		mm->brk = origbrk;
+		goto out;
+	}
+	/* Only check if the next VMA is within the stack_guard_gap of the
+	 * expansion area */
+	next = mas_next(&mas, newbrk + PAGE_SIZE + stack_guard_gap);
 	/* Check against existing mmap mappings. */
-	next = find_vma(mm, oldbrk);
 	if (next && newbrk + PAGE_SIZE > vm_start_gap(next))
 		goto out;
 
+	mas_lock(&mas);
+	brkvma = mas_prev(&mas, mm->start_brk);
+	mas_unlock(&mas);
+	if (brkvma) {
+		if(brkvma->vm_start >= oldbrk)
+			goto out; // Trying to map over another vma.
+
+		if (brkvma->vm_end <= min_brk) {
+			brkvma = NULL;
+			mas_reset(&mas);
+		}
+	}
+
 	/* Ok, looks good - let it rip. */
-	if (do_brk_flags(oldbrk, newbrk-oldbrk, 0, &uf) < 0)
+	if (do_brk_flags(&mas, &brkvma, oldbrk, newbrk - oldbrk, 0) < 0)
 		goto out;
+
 	mm->brk = brk;
 
 success:
@@ -372,16 +400,16 @@ static void validate_mm(struct mm_struct *mm)
 	validate_mm_mt(mm);
 
 	while (vma) {
+#ifdef CONFIG_DEBUG_VM_RB
 		struct anon_vma *anon_vma = vma->anon_vma;
 		struct anon_vma_chain *avc;
-
 		if (anon_vma) {
 			anon_vma_lock_read(anon_vma);
 			list_for_each_entry(avc, &vma->anon_vma_chain, same_vma)
 				anon_vma_interval_tree_verify(avc);
 			anon_vma_unlock_read(anon_vma);
 		}
-
+#endif
 		highest_address = vm_end_gap(vma);
 		vma = vma->vm_next;
 		i++;
@@ -2034,6 +2062,7 @@ EXPORT_SYMBOL(get_unmapped_area);
 struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
 {
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, addr, addr);
 
 	mmap_assert_locked(mm);
 	/* Check the cache first. */
@@ -2041,7 +2070,9 @@ struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
 	if (likely(vma))
 		return vma;
 
-	vma = mt_find(&mm->mm_mt, &addr, ULONG_MAX);
+	rcu_read_lock();
+	vma = mas_find(&mas, -1);
+	rcu_read_unlock();
 	if (vma)
 		vmacache_update(addr, vma);
 
@@ -2526,7 +2557,6 @@ unlock_range(struct vm_area_struct *start, unsigned long limit)
 			mm->locked_vm -= vma_pages(tmp);
 			munlock_vma_pages_all(tmp);
 		}
-
 		tmp = tmp->vm_next;
 	}
 }
@@ -2759,16 +2789,105 @@ SYSCALL_DEFINE5(remap_file_pages, unsigned long, start, unsigned long, size,
 }
 
 /*
- *  this is really a simplified "do_mmap".  it only handles
- *  anonymous maps.  eventually we may be able to do some
- *  brk-specific accounting here.
+ * bkr_munmap() - Unmap a parital vma.
+ * @mas: The maple tree state.
+ * @vma: The vma to be modified
+ * @newbrk: the start of the address to unmap
+ * @oldbrk: The end of the address to unmap
+ * @uf: The userfaultfd list_head
+ *
+ * Returns: 0 on success.
+ * unmaps a partial VMA mapping.  Does not handle alignment, downgrades lock if
+ * possible.
+ */
+static int do_brk_munmap(struct ma_state *mas, struct vm_area_struct *vma,
+			 unsigned long newbrk, unsigned long oldbrk,
+			 struct list_head *uf)
+{
+	struct mm_struct *mm = vma->vm_mm;
+	struct vm_area_struct unmap;
+	unsigned long unmap_pages;
+	int ret = 1;
+
+	arch_unmap(mm, newbrk, oldbrk);
+
+	if (likely(vma->vm_start >= newbrk)) { // remove entire mapping(s)
+		mas_set(mas, newbrk);
+		if (vma->vm_start != newbrk)
+			mas_reset(mas); // cause a re-walk for the first overlap.
+		ret = __do_munmap(mm, newbrk, oldbrk - newbrk, uf, true);
+		goto munmap_full_vma;
+	}
+
+	vma_init(&unmap, mm);
+	unmap.vm_start = newbrk;
+	unmap.vm_end = oldbrk;
+	ret = userfaultfd_unmap_prep(&unmap, newbrk, oldbrk, uf);
+	if (ret)
+		return ret;
+	ret = 1;
+
+	// Change the oldbrk of vma to the newbrk of the munmap area
+	vma_adjust_trans_huge(vma, vma->vm_start, newbrk, 0);
+	if (vma->anon_vma) {
+		anon_vma_lock_write(vma->anon_vma);
+		anon_vma_interval_tree_pre_update_vma(vma);
+	}
+
+	vma->vm_end = newbrk;
+	if (vma_mas_remove(&unmap, mas))
+		goto mas_store_fail;
+
+	vmacache_invalidate(vma->vm_mm);
+	if (vma->anon_vma) {
+		anon_vma_interval_tree_post_update_vma(vma);
+		anon_vma_unlock_write(vma->anon_vma);
+	}
+
+	unmap_pages = vma_pages(&unmap);
+	if (unmap.vm_flags & VM_LOCKED) {
+		mm->locked_vm -= unmap_pages;
+		munlock_vma_pages_range(&unmap, newbrk, oldbrk);
+	}
+
+	mmap_write_downgrade(mm);
+	unmap_region(mm, &unmap, vma, newbrk, oldbrk);
+	/* Statistics */
+	vm_stat_account(mm, unmap.vm_flags, -unmap_pages);
+	if (unmap.vm_flags & VM_ACCOUNT)
+		vm_unacct_memory(unmap_pages);
+
+munmap_full_vma:
+	validate_mm_mt(mm);
+	return ret;
+
+mas_store_fail:
+	vma->vm_end = oldbrk;
+	if (vma->anon_vma) {
+		anon_vma_interval_tree_post_update_vma(vma);
+		anon_vma_unlock_write(vma->anon_vma);
+	}
+	return -ENOMEM;
+}
+
+/*
+ * do_brk_flags() - Increase the brk vma if the flags match.
+ * @mas: The maple tree state.
+ * @addr: The start address
+ * @len: The length of the increase
+ * @vma: The vma,
+ * @flags: The VMA Flags
+ *
+ * Extend the brk VMA from addr to addr + len.  If the VMA is NULL or the flags
+ * do not match then create a new anonymous VMA.  Eventually we may be able to
+ * do some brk-specific accounting here.
  */
-static int do_brk_flags(unsigned long addr, unsigned long len,
-			unsigned long flags, struct list_head *uf)
+static int do_brk_flags(struct ma_state *mas, struct vm_area_struct **brkvma,
+			unsigned long addr, unsigned long len,
+			unsigned long flags)
 {
 	struct mm_struct *mm = current->mm;
-	struct vm_area_struct *vma, *prev;
-	pgoff_t pgoff = addr >> PAGE_SHIFT;
+	struct vm_area_struct *prev = NULL, *vma;
 	int error;
 	unsigned long mapped_addr;
 	validate_mm_mt(mm);
@@ -2786,11 +2905,7 @@ static int do_brk_flags(unsigned long addr, unsigned long len,
 	if (error)
 		return error;
 
-	/* Clear old maps, set up prev and uf */
-	if (munmap_vma_range(mm, addr, len, &prev, uf))
-		return -ENOMEM;
-
-	/* Check against address space limits *after* clearing old maps... */
+	/* Check against address space limits by the changed size */
 	if (!may_expand_vm(mm, flags, len >> PAGE_SHIFT))
 		return -ENOMEM;
 
@@ -2800,28 +2915,65 @@ static int do_brk_flags(unsigned long addr, unsigned long len,
 	if (security_vm_enough_memory_mm(mm, len >> PAGE_SHIFT))
 		return -ENOMEM;
 
-	/* Can we just expand an old private anonymous mapping? */
-	vma = vma_merge(mm, prev, addr, addr + len, flags,
-			NULL, NULL, pgoff, NULL, NULL_VM_UFFD_CTX);
-	if (vma)
-		goto out;
+	mas->last = addr + len - 1;
+	if (*brkvma) {
+		vma = *brkvma;
+		/* Expand the existing vma if possible; almost never a singular
+		 * list, so this will almost always fail. */
 
-	/*
-	 * create a vma struct for an anonymous mapping
-	 */
-	vma = vm_area_alloc(mm);
-	if (!vma) {
-		vm_unacct_memory(len >> PAGE_SHIFT);
-		return -ENOMEM;
+		if ((!vma->anon_vma ||
+		     list_is_singular(&vma->anon_vma_chain)) &&
+		     ((vma->vm_flags & ~VM_SOFTDIRTY) == flags)){
+			mas->index = vma->vm_start;
+
+			vma_adjust_trans_huge(vma, addr, addr + len, 0);
+			if (vma->anon_vma) {
+				anon_vma_lock_write(vma->anon_vma);
+				anon_vma_interval_tree_pre_update_vma(vma);
+			}
+			vma->vm_end = addr + len;
+			vma->vm_flags |= VM_SOFTDIRTY;
+			mas_lock(mas);
+			if (mas_store_gfp(mas, vma, GFP_KERNEL))
+				goto mas_mod_fail;
+
+			mas_unlock(mas);
+			if (vma->anon_vma) {
+				anon_vma_interval_tree_post_update_vma(vma);
+				anon_vma_unlock_write(vma->anon_vma);
+			}
+			khugepaged_enter_vma_merge(vma, flags);
+			goto out;
+		}
+		prev = vma;
 	}
+	mas_lock(mas);
+	mas->index = addr;
+	mas_walk(mas);
+	mas_unlock(mas);
+
+	/* create a vma struct for an anonymous mapping */
+	vma = vm_area_alloc(mm);
+	if (!vma)
+		goto vma_alloc_fail;
 
 	vma_set_anonymous(vma);
 	vma->vm_start = addr;
 	vma->vm_end = addr + len;
-	vma->vm_pgoff = pgoff;
+	vma->vm_pgoff = addr >> PAGE_SHIFT;
 	vma->vm_flags = flags;
 	vma->vm_page_prot = vm_get_page_prot(flags);
-	vma_link(mm, vma, prev);
+	mas_lock(mas);
+	if (vma_mas_store(vma, mas))
+		goto mas_store_fail;
+	mas_unlock(mas);
+
+	if (!prev)
+		prev = mas_prev(mas, 0);
+
+	__vma_link_list(mm, vma, prev);
+	mm->map_count++;
+	*brkvma = vma;
 out:
 	perf_event_mmap(vma);
 	mm->total_vm += len >> PAGE_SHIFT;
@@ -2831,15 +2983,32 @@ static int do_brk_flags(unsigned long addr, unsigned long len,
 	vma->vm_flags |= VM_SOFTDIRTY;
 	validate_mm_mt(mm);
 	return 0;
+
+mas_store_fail:
+	vm_area_free(vma);
+vma_alloc_fail:
+	vm_unacct_memory(len >> PAGE_SHIFT);
+	return -ENOMEM;
+
+mas_mod_fail:
+	mas_unlock(mas);
+	vma->vm_end = addr;
+	if (vma->anon_vma) {
+		anon_vma_interval_tree_post_update_vma(vma);
+		anon_vma_unlock_write(vma->anon_vma);
+	}
+	return -ENOMEM;
+
 }
 
 int vm_brk_flags(unsigned long addr, unsigned long request, unsigned long flags)
 {
 	struct mm_struct *mm = current->mm;
+	struct vm_area_struct *vma = NULL;
 	unsigned long len;
 	int ret;
 	bool populate;
-	LIST_HEAD(uf);
+	MA_STATE(mas, &mm->mm_mt, addr, addr);
 
 	len = PAGE_ALIGN(request);
 	if (len < request)
@@ -2850,10 +3019,11 @@ int vm_brk_flags(unsigned long addr, unsigned long request, unsigned long flags)
 	if (mmap_write_lock_killable(mm))
 		return -EINTR;
 
-	ret = do_brk_flags(addr, len, flags, &uf);
+	// This vma left intentionally blank.
+	mas_walk(&mas);
+	ret = do_brk_flags(&mas, &vma, addr, len, flags);
 	populate = ((mm->def_flags & VM_LOCKED) != 0);
 	mmap_write_unlock(mm);
-	userfaultfd_unmap_complete(mm, &uf);
 	if (populate && !ret)
 		mm_populate(addr, len);
 	return ret;
Signature · 1 line
2.30.2
#23 lore raw

PATCH v2 16/61 mm: Use maple tree operations for find_vma_intersection() and find_vma()

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Move find_vma_intersection() to mmap.c and change implementation to maple tree.

When searching for a vma within a range, it is easier to use the maple tree interface. This means the find_vma() call changes to a special case of the find_vma_intersection().

Exported for kvm module.

---
 include/linux/mm.h | 25 ++++++-------------------
 mm/mmap.c          | 38 ++++++++++++++++++++++++++++----------
 2 files changed, 34 insertions(+), 29 deletions(-)
include/linux/mm.h +6 -19
index a3086474d8d2..10763bd6fccb 100644
@@ -2774,26 +2774,13 @@ extern struct vm_area_struct * find_vma(struct mm_struct * mm, unsigned long add
 extern struct vm_area_struct * find_vma_prev(struct mm_struct * mm, unsigned long addr,
 					     struct vm_area_struct **pprev);
 
-/**
- * find_vma_intersection() - Look up the first VMA which intersects the interval
- * @mm: The process address space.
- * @start_addr: The inclusive start user address.
- * @end_addr: The exclusive end user address.
- *
- * Returns: The first VMA within the provided range, %NULL otherwise.  Assumes
- * start_addr < end_addr.
+/*
+ * Look up the first VMA which intersects the interval [start_addr, end_addr)
+ * NULL if none.  Assume start_addr < end_addr.
  */
-static inline
-struct vm_area_struct *find_vma_intersection(struct mm_struct *mm,
-					     unsigned long start_addr,
-					     unsigned long end_addr)
-{
-	struct vm_area_struct *vma = find_vma(mm, start_addr);
-
-	if (vma && end_addr <= vma->vm_start)
-		vma = NULL;
-	return vma;
-}
+extern struct vm_area_struct *find_vma_intersection(struct mm_struct *mm,
+						    unsigned long start_addr,
+						    unsigned long end_addr);
 
 /**
  * vma_lookup() - Find a VMA at a specific address
mm/mmap.c +28 -10
index 3d88fc87c289..9b86f47f7387 100644
@@ -2052,32 +2052,50 @@ get_unmapped_area(struct file *file, unsigned long addr, unsigned long len,
 EXPORT_SYMBOL(get_unmapped_area);
 
 /**
- * find_vma() - Find the VMA for a given address, or the next vma.
- * @mm: The mm_struct to check
- * @addr: The address
+ * find_vma_intersection() - Look up the first VMA which intersects the interval
+ * @mm: The process address space.
+ * @start_addr: The inclusive start user address.
+ * @end_addr: The exclusive end user address.
  *
- * Returns: The VMA associated with addr, or the next vma.
- * May return %NULL in the case of no vma at addr or above.
+ * Returns: The first VMA within the provided range, %NULL otherwise.  Assumes
+ * start_addr < end_addr.
  */
-struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
+struct vm_area_struct *find_vma_intersection(struct mm_struct *mm,
+					     unsigned long start_addr,
+					     unsigned long end_addr)
 {
 	struct vm_area_struct *vma;
-	MA_STATE(mas, &mm->mm_mt, addr, addr);
+	MA_STATE(mas, &mm->mm_mt, start_addr, start_addr);
 
 	mmap_assert_locked(mm);
 	/* Check the cache first. */
-	vma = vmacache_find(mm, addr);
+	vma = vmacache_find(mm, start_addr);
 	if (likely(vma))
 		return vma;
 
 	rcu_read_lock();
-	vma = mas_find(&mas, -1);
+	vma = mas_find(&mas, end_addr - 1);
 	rcu_read_unlock();
 	if (vma)
-		vmacache_update(addr, vma);
+		vmacache_update(mas.index, vma);
 
 	return vma;
 }
+EXPORT_SYMBOL(find_vma_intersection);
+
+/**
+ * find_vma() - Find the VMA for a given address, or the next vma.
+ * @mm:  The mm_struct to check
+ * @addr: The address
+ *
+ * Returns: The VMA associated with addr, or the next vma.
+ * May return NULL in the case of no vma at addr or above.
+ */
+inline struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
+{
+	// Note find_vma_intersection will decrease 0 to underflow to ULONG_MAX
+	return find_vma_intersection(mm, addr, 0);
+}
 EXPORT_SYMBOL(find_vma);
 
 /**
Signature · 1 line
2.30.2
#24 lore raw

PATCH v2 17/61 mm/mmap: Use advanced maple tree API for mmap_region()

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Changing mmap_region() to use the maple tree state and the advanced maple tree interface allows for a lot less tree walking.

This change removes the last caller of munmap_vma_range(), so drop this unused function.

Add vma_expand() to expand a VMA if possible by doing the necessary hugepage check, uprobe_munmap of files, dcache flush, modifications then undoing the detaches, etc.

Add vma_mas_link() helper to add a VMA to the linked list and maple tree until the linked list is removed.

---
 mm/mmap.c | 258 +++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 206 insertions(+), 52 deletions(-)
mm/mmap.c +206 -52
index 9b86f47f7387..060a372fc812 100644
@@ -503,28 +503,6 @@ static inline struct vm_area_struct *vma_next(struct mm_struct *mm,
 	return vma->vm_next;
 }
 
-/*
- * munmap_vma_range() - munmap VMAs that overlap a range.
- * @mm: The mm struct
- * @start: The start of the range.
- * @len: The length of the range.
- * @pprev: pointer to the pointer that will be set to previous vm_area_struct
- *
- * Find all the vm_area_struct that overlap from @start to
- * @end and munmap them.  Set @pprev to the previous vm_area_struct.
- *
- * Returns: -ENOMEM on munmap failure or 0 on success.
- */
-static inline int
-munmap_vma_range(struct mm_struct *mm, unsigned long start, unsigned long len,
-		 struct vm_area_struct **pprev, struct list_head *uf)
-{
-	// Needs optimization.
-	while (range_has_overlap(mm, start, start + len, pprev))
-		if (do_munmap(mm, start, len, uf))
-			return -ENOMEM;
-	return 0;
-}
 static unsigned long count_vma_pages_range(struct mm_struct *mm,
 		unsigned long addr, unsigned long end)
 {
@@ -604,6 +582,35 @@ void vma_mt_store(struct mm_struct *mm, struct vm_area_struct *vma)
 		GFP_KERNEL);
 }
 
+/*
+ * vma_mas_link() - Link a VMA into an mm
+ * @mm: The mm struct
+ * @vma: The VMA to link in
+ * @mas: The maple state
+ *
+ * Must hold the @mas lock.
+ */
+static void vma_mas_link(struct mm_struct *mm, struct vm_area_struct *vma,
+			 struct ma_state *mas, struct vm_area_struct *prev)
+{
+	struct address_space *mapping = NULL;
+
+	if (vma->vm_file) {
+		mapping = vma->vm_file->f_mapping;
+		i_mmap_lock_write(mapping);
+	}
+
+	vma_mas_store(vma, mas);
+	__vma_link_list(mm, vma, prev);
+	__vma_link_file(vma);
+
+	if (mapping)
+		i_mmap_unlock_write(mapping);
+
+	mm->map_count++;
+	validate_mm(mm);
+}
+
 static void vma_link(struct mm_struct *mm, struct vm_area_struct *vma,
 			struct vm_area_struct *prev)
 {
@@ -639,6 +646,108 @@ static void __insert_vm_struct(struct mm_struct *mm, struct vm_area_struct *vma)
 	mm->map_count++;
 }
 
+/*
+ * vma_expand - Expand an existing VMA
+ * @mas: The maple state
+ * @vma: The vma to expand
+ * @start: The start of the vma
+ * @end: The exclusive end of the vma
+ *
+ * @mas must be locked
+ */
+inline int vma_expand(struct ma_state *mas, struct vm_area_struct *vma,
+		      unsigned long start, unsigned long end, pgoff_t pgoff,
+		      struct vm_area_struct *next)
+{
+	struct mm_struct *mm = vma->vm_mm;
+	struct address_space *mapping = NULL;
+	struct rb_root_cached *root = NULL;
+	struct anon_vma *anon_vma = vma->anon_vma;
+	struct file *file = vma->vm_file;
+	bool remove_next = false;
+	int error;
+
+	if (next && (vma != next) && (end == next->vm_end)) {
+		remove_next = true;
+		if (next->anon_vma && !vma->anon_vma) {
+			vma->anon_vma = next->anon_vma;
+			error = anon_vma_clone(vma, next);
+			if (error)
+				return error;
+		}
+	}
+
+	vma_adjust_trans_huge(vma, start, end, 0);
+
+	if (file) {
+		mapping = file->f_mapping;
+		root = &mapping->i_mmap;
+		uprobe_munmap(vma, vma->vm_start, vma->vm_end);
+		i_mmap_lock_write(mapping);
+	}
+
+	if (anon_vma) {
+		anon_vma_lock_write(anon_vma);
+		anon_vma_interval_tree_pre_update_vma(vma);
+	}
+
+	if (file) {
+		flush_dcache_mmap_lock(mapping);
+		vma_interval_tree_remove(vma, root);
+	}
+
+	vma->vm_start = start;
+	vma->vm_end = end;
+	vma->vm_pgoff = pgoff;
+	/* Note: mas must be pointing to the expanding VMA */
+	vma_mas_store(vma, mas);
+
+	if (file) {
+		vma_interval_tree_insert(vma, root);
+		flush_dcache_mmap_unlock(mapping);
+	}
+
+	/* Expanding over the next vma */
+	if (remove_next) {
+		/* Remove from mm linked list - also updates highest_vm_end */
+		__vma_unlink_list(mm, next);
+
+		/* Kill the cache */
+		vmacache_invalidate(mm);
+
+		if (file)
+			__remove_shared_vm_struct(next, file, mapping);
+
+	} else if (!next) {
+		mm->highest_vm_end = vm_end_gap(vma);
+	}
+
+	if (anon_vma) {
+		anon_vma_interval_tree_post_update_vma(vma);
+		anon_vma_unlock_write(anon_vma);
+	}
+
+	if (file) {
+		i_mmap_unlock_write(mapping);
+		uprobe_mmap(vma);
+	}
+
+	if (remove_next) {
+		if (file) {
+			uprobe_munmap(next, next->vm_start, next->vm_end);
+			fput(file);
+		}
+		if (next->anon_vma)
+			anon_vma_merge(vma, next);
+		mm->map_count--;
+		mpol_put(vma_policy(next));
+		vm_area_free(next);
+	}
+
+	validate_mm(mm);
+	return 0;
+}
+
 /*
  * We cannot adjust vm_start, vm_end, vm_pgoff fields of a vma that
  * is already present in an i_mmap tree without adjusting the tree.
@@ -1622,9 +1731,15 @@ unsigned long mmap_region(struct file *file, unsigned long addr,
 		struct list_head *uf)
 {
 	struct mm_struct *mm = current->mm;
-	struct vm_area_struct *vma, *prev, *merge;
-	int error;
+	struct vm_area_struct *vma = NULL;
+	struct vm_area_struct *prev, *next;
+	pgoff_t pglen = len >> PAGE_SHIFT;
 	unsigned long charged = 0;
+	unsigned long end = addr + len;
+	unsigned long merge_start = addr, merge_end = end;
+	pgoff_t vm_pgoff;
+	int error;
+	MA_STATE(mas, &mm->mm_mt, addr, end - 1);
 
 	/* Check against address space limit. */
 	if (!may_expand_vm(mm, vm_flags, len >> PAGE_SHIFT)) {
@@ -1634,16 +1749,17 @@ unsigned long mmap_region(struct file *file, unsigned long addr,
 		 * MAP_FIXED may remove pages of mappings that intersects with
 		 * requested mapping. Account for the pages it would unmap.
 		 */
-		nr_pages = count_vma_pages_range(mm, addr, addr + len);
+		nr_pages = count_vma_pages_range(mm, addr, end);
 
 		if (!may_expand_vm(mm, vm_flags,
 					(len >> PAGE_SHIFT) - nr_pages))
 			return -ENOMEM;
 	}
 
-	/* Clear old maps, set up prev and uf */
-	if (munmap_vma_range(mm, addr, len, &prev, uf))
+	/* Unmap any existing mapping in the area */
+	if (do_munmap(mm, addr, len, uf))
 		return -ENOMEM;
+
 	/*
 	 * Private writable mapping: check memory availability
 	 */
@@ -1654,14 +1770,50 @@ unsigned long mmap_region(struct file *file, unsigned long addr,
 		vm_flags |= VM_ACCOUNT;
 	}
 
-	/*
-	 * Can we just expand an old mapping?
-	 */
-	vma = vma_merge(mm, prev, addr, addr + len, vm_flags,
-			NULL, file, pgoff, NULL, NULL_VM_UFFD_CTX);
-	if (vma)
-		goto out;
 
+	if (vm_flags & VM_SPECIAL) {
+		rcu_read_lock();
+		prev = mas_prev(&mas, 0);
+		rcu_read_unlock();
+		goto cannot_expand;
+	}
+
+	/* Attempt to expand an old mapping */
+
+	/* Check next */
+	rcu_read_lock();
+	next = mas_next(&mas, ULONG_MAX);
+	rcu_read_unlock();
+	if (next && next->vm_start == end && vma_policy(next) &&
+	    can_vma_merge_before(next, vm_flags, NULL, file, pgoff+pglen,
+				 NULL_VM_UFFD_CTX)) {
+		merge_end = next->vm_end;
+		vma = next;
+		vm_pgoff = next->vm_pgoff - pglen;
+	}
+
+	/* Check prev */
+	rcu_read_lock();
+	prev = mas_prev(&mas, 0);
+	rcu_read_unlock();
+	if (prev && prev->vm_end == addr && !vma_policy(prev) &&
+	    can_vma_merge_after(prev, vm_flags, NULL, file, pgoff,
+				NULL_VM_UFFD_CTX)) {
+		merge_start = prev->vm_start;
+		vma = prev;
+		vm_pgoff = prev->vm_pgoff;
+	}
+
+
+	/* Actually expand, if possible */
+	if (vma &&
+	    !vma_expand(&mas, vma, merge_start, merge_end, vm_pgoff, next)) {
+		khugepaged_enter_vma_merge(prev, vm_flags);
+		goto expanded;
+	}
+
+	mas_set_range(&mas, addr, end - 1);
+cannot_expand:
 	/*
 	 * Determine the object being mapped and call the appropriate
 	 * specific mapper. the address has already been validated, but
@@ -1674,7 +1826,7 @@ unsigned long mmap_region(struct file *file, unsigned long addr,
 	}
 
 	vma->vm_start = addr;
-	vma->vm_end = addr + len;
+	vma->vm_end = end;
 	vma->vm_flags = vm_flags;
 	vma->vm_page_prot = vm_get_page_prot(vm_flags);
 	vma->vm_pgoff = pgoff;
@@ -1706,8 +1858,6 @@ unsigned long mmap_region(struct file *file, unsigned long addr,
 		 *
 		 * Answer: Yes, several device drivers can do it in their
 		 *         f_op->mmap method. -DaveM
-		 * Bug: If addr is changed, prev, rb_link, rb_parent should
-		 *      be updated for vma_link()
 		 */
 		WARN_ON_ONCE(addr != vma->vm_start);
 
@@ -1716,18 +1866,25 @@ unsigned long mmap_region(struct file *file, unsigned long addr,
 		/* If vm_flags changed after call_mmap(), we should try merge vma again
 		 * as we may succeed this time.
 		 */
-		if (unlikely(vm_flags != vma->vm_flags && prev)) {
-			merge = vma_merge(mm, prev, vma->vm_start, vma->vm_end, vma->vm_flags,
-				NULL, vma->vm_file, vma->vm_pgoff, NULL, NULL_VM_UFFD_CTX);
-			if (merge) {
+		if (unlikely(vm_flags != vma->vm_flags && prev &&
+			     prev->vm_end == addr && !vma_policy(prev) &&
+			     can_vma_merge_after(prev, vm_flags, NULL, file,
+						 pgoff, NULL_VM_UFFD_CTX))) {
+			merge_start = prev->vm_start;
+			vm_pgoff = prev->vm_pgoff;
+			if (!vma_expand(&mas, prev, merge_start, merge_end,
+					vm_pgoff, next)) {
 				/* ->mmap() can change vma->vm_file and fput the original file. So
 				 * fput the vma->vm_file here or we would add an extra fput for file
 				 * and cause general protection fault ultimately.
 				 */
 				fput(vma->vm_file);
 				vm_area_free(vma);
-				vma = merge;
-				/* Update vm_flags to pick up the change. */
+				vma = prev;
+				/* Update vm_flags and possible addr to pick up the change. We don't
+				 * warn here if addr changed as the vma is not linked by vma_link().
+				 */
+				addr = vma->vm_start;
 				vm_flags = vma->vm_flags;
 				goto unmap_writable;
 			}
@@ -1751,7 +1908,8 @@ unsigned long mmap_region(struct file *file, unsigned long addr,
 			goto free_vma;
 	}
 
-	vma_link(mm, vma, prev);
+	mas_set(&mas, addr);
+	vma_mas_link(mm, vma, &mas, prev);
 	/* Once vma denies write, undo our temporary denial count */
 	if (file) {
 unmap_writable:
@@ -1760,14 +1918,14 @@ unsigned long mmap_region(struct file *file, unsigned long addr,
 		if (vm_flags & VM_DENYWRITE)
 			allow_write_access(file);
 	}
-out:
+expanded:
 	perf_event_mmap(vma);
 
 	vm_stat_account(mm, vm_flags, len >> PAGE_SHIFT);
 	if (vm_flags & VM_LOCKED) {
 		if ((vm_flags & VM_SPECIAL) || vma_is_dax(vma) ||
-					is_vm_hugetlb_page(vma) ||
-					vma == get_gate_vma(current->mm))
+		    is_vm_hugetlb_page(vma) ||
+		    vma == get_gate_vma(current->mm))
 			vma->vm_flags &= VM_LOCKED_CLEAR_MASK;
 		else
 			mm->locked_vm += (len >> PAGE_SHIFT);
@@ -2605,13 +2763,10 @@ int __do_munmap(struct mm_struct *mm, unsigned long start, size_t len,
 	vma = find_vma_intersection(mm, start, end);
 	if (!vma)
 		return 0;
+
 	prev = vma->vm_prev;
 	/* we have start < vma->vm_end  */
 
-	/* if it doesn't overlap, we have nothing.. */
-	if (vma->vm_start >= end)
-		return 0;
-
 	/*
 	 * If we need to split any vma, do it now to save pain later.
 	 *
@@ -2621,7 +2776,6 @@ int __do_munmap(struct mm_struct *mm, unsigned long start, size_t len,
 	 */
 	if (start > vma->vm_start) {
 		int error;
-
 		/*
 		 * Make sure that map_count on return from munmap() will
 		 * not exceed its limit; but let map_count go just above
Signature · 1 line
2.30.2
#25 lore raw

PATCH v2 18/61 mm: Remove vmacache

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

By using the maple tree and the maple tree state, the vmacache is no longer beneficial and is complicating the VMA code. Remove the vmacache to reduce the work in keeping it up to date and code complexity.

---
 arch/s390/configs/debug_defconfig |   1 -
 fs/exec.c                         |   3 -
 fs/proc/task_mmu.c                |   1 -
 include/linux/mm_types.h          |   1 -
 include/linux/mm_types_task.h     |   5 --
 include/linux/sched.h             |   1 -
 include/linux/vm_event_item.h     |   4 -
 include/linux/vmacache.h          |  28 -------
 include/linux/vmstat.h            |   6 --
 kernel/debug/debug_core.c         |  12 ---
 kernel/fork.c                     |   5 --
 lib/Kconfig.debug                 |  10 ---
 mm/Makefile                       |   2 +-
 mm/debug.c                        |   4 +-
 mm/mmap.c                         |  17 -----
 mm/nommu.c                        |  31 +-------
 mm/vmacache.c                     | 117 ------------------------------
 mm/vmstat.c                       |   4 -
 18 files changed, 6 insertions(+), 246 deletions(-)
 delete mode 100644 include/linux/vmacache.h
 delete mode 100644 mm/vmacache.c
arch/s390/configs/debug_defconfig +0 -1
index b88184019af9..08508d5e805e 100644
@@ -800,7 +800,6 @@ CONFIG_SLUB_DEBUG_ON=y
 CONFIG_SLUB_STATS=y
 CONFIG_DEBUG_STACK_USAGE=y
 CONFIG_DEBUG_VM=y
-CONFIG_DEBUG_VM_VMACACHE=y
 CONFIG_DEBUG_VM_PGFLAGS=y
 CONFIG_DEBUG_MEMORY_INIT=y
 CONFIG_MEMORY_NOTIFIER_ERROR_INJECT=m
fs/exec.c +0 -3
index 816c7e347c9c..9cc6bf3a5f0c 100644
@@ -28,7 +28,6 @@
 #include <linux/file.h>
 #include <linux/fdtable.h>
 #include <linux/mm.h>
-#include <linux/vmacache.h>
 #include <linux/stat.h>
 #include <linux/fcntl.h>
 #include <linux/swap.h>
@@ -1019,8 +1018,6 @@ static int exec_mmap(struct mm_struct *mm)
 	activate_mm(active_mm, mm);
 	if (IS_ENABLED(CONFIG_ARCH_WANT_IRQS_OFF_ACTIVATE_MM))
 		local_irq_enable();
-	tsk->mm->vmacache_seqnum = 0;
-	vmacache_flush(tsk);
 	task_unlock(tsk);
 	if (old_mm) {
 		mmap_read_unlock(old_mm);
fs/proc/task_mmu.c +0 -1
index eb97468dfe4c..ab9b4ff44b54 100644
@@ -1,6 +1,5 @@
 // SPDX-License-Identifier: GPL-2.0
 #include <linux/pagewalk.h>
-#include <linux/vmacache.h>
 #include <linux/hugetlb.h>
 #include <linux/huge_mm.h>
 #include <linux/mount.h>
include/linux/mm_types.h +0 -1
index 514aca4fe9d4..374c48169692 100644
@@ -472,7 +472,6 @@ struct mm_struct {
 	struct {
 		struct vm_area_struct *mmap;		/* list of VMAs */
 		struct maple_tree mm_mt;
-		u64 vmacache_seqnum;                   /* per-thread vmacache */
 #ifdef CONFIG_MMU
 		unsigned long (*get_unmapped_area) (struct file *filp,
 				unsigned long addr, unsigned long len,
include/linux/mm_types_task.h +0 -5
index 1b222f8039d1..418ec7df5f18 100644
@@ -36,11 +36,6 @@
 #define VMACACHE_SIZE (1U << VMACACHE_BITS)
 #define VMACACHE_MASK (VMACACHE_SIZE - 1)
 
-struct vmacache {
-	u64 seqnum;
-	struct vm_area_struct *vmas[VMACACHE_SIZE];
-};
-
 /*
  * When updating this, please also update struct resident_page_types[] in
  * kernel/fork.c
include/linux/sched.h +0 -1
index c7381fa38e22..3f99a38c58da 100644
@@ -791,7 +791,6 @@ struct task_struct {
 	struct mm_struct		*active_mm;
 
 	/* Per-thread vma caching: */
-	struct vmacache			vmacache;
 
 #ifdef SPLIT_RSS_COUNTING
 	struct task_rss_stat		rss_stat;
include/linux/vm_event_item.h +0 -4
index a185cc75ff52..dd9e1e98bdec 100644
@@ -119,10 +119,6 @@ enum vm_event_item { PGPGIN, PGPGOUT, PSWPIN, PSWPOUT,
 		NR_TLB_LOCAL_FLUSH_ALL,
 		NR_TLB_LOCAL_FLUSH_ONE,
 #endif /* CONFIG_DEBUG_TLBFLUSH */
-#ifdef CONFIG_DEBUG_VM_VMACACHE
-		VMACACHE_FIND_CALLS,
-		VMACACHE_FIND_HITS,
-#endif
 #ifdef CONFIG_SWAP
 		SWAP_RA,
 		SWAP_RA_HIT,
include/linux/vmacache.h deleted +0 -28
deleted file mode 100644
index 6fce268a4588..000000000000
@@ -1,28 +0,0 @@
-/* SPDX-License-Identifier: GPL-2.0 */
-#ifndef __LINUX_VMACACHE_H
-#define __LINUX_VMACACHE_H
-
-#include <linux/sched.h>
-#include <linux/mm.h>
-
-static inline void vmacache_flush(struct task_struct *tsk)
-{
-	memset(tsk->vmacache.vmas, 0, sizeof(tsk->vmacache.vmas));
-}
-
-extern void vmacache_update(unsigned long addr, struct vm_area_struct *newvma);
-extern struct vm_area_struct *vmacache_find(struct mm_struct *mm,
-						    unsigned long addr);
-
-#ifndef CONFIG_MMU
-extern struct vm_area_struct *vmacache_find_exact(struct mm_struct *mm,
-						  unsigned long start,
-						  unsigned long end);
-#endif
-
-static inline void vmacache_invalidate(struct mm_struct *mm)
-{
-	mm->vmacache_seqnum++;
-}
-
-#endif /* __LINUX_VMACACHE_H */
include/linux/vmstat.h +0 -6
index 241bd0f53fb9..fcd1b853cbed 100644
@@ -125,12 +125,6 @@ static inline void vm_events_fold_cpu(int cpu)
 #define count_vm_tlb_events(x, y) do { (void)(y); } while (0)
 #endif
 
-#ifdef CONFIG_DEBUG_VM_VMACACHE
-#define count_vm_vmacache_event(x) count_vm_event(x)
-#else
-#define count_vm_vmacache_event(x) do {} while (0)
-#endif
-
 #define __count_zid_vm_events(item, zid, delta) \
 	__count_vm_events(item##_NORMAL - ZONE_NORMAL + zid, delta)
 
kernel/debug/debug_core.c +0 -12
index b4aa6bb6b2bd..6a99dd2c71dc 100644
@@ -53,7 +53,6 @@
 #include <linux/pid.h>
 #include <linux/smp.h>
 #include <linux/mm.h>
-#include <linux/vmacache.h>
 #include <linux/rcupdate.h>
 #include <linux/irq.h>
 
@@ -285,17 +284,6 @@ static void kgdb_flush_swbreak_addr(unsigned long addr)
 	if (!CACHE_FLUSH_IS_SAFE)
 		return;
 
-	if (current->mm) {
-		int i;
-
-		for (i = 0; i < VMACACHE_SIZE; i++) {
-			if (!current->vmacache.vmas[i])
-				continue;
-			flush_cache_range(current->vmacache.vmas[i],
-					  addr, addr + BREAK_INSTR_SIZE);
-		}
-	}
-
 	/* Force flush instruction cache if it was outside the mm */
 	flush_icache_range(addr, addr + BREAK_INSTR_SIZE);
 }
kernel/fork.c +0 -5
index 4311715e9266..0c35460c092e 100644
@@ -42,7 +42,6 @@
 #include <linux/mmu_notifier.h>
 #include <linux/fs.h>
 #include <linux/mm.h>
-#include <linux/vmacache.h>
 #include <linux/nsproxy.h>
 #include <linux/capability.h>
 #include <linux/cpu.h>
@@ -1094,7 +1093,6 @@ static struct mm_struct *mm_init(struct mm_struct *mm, struct task_struct *p,
 {
 	mm->mmap = NULL;
 	mt_init_flags(&mm->mm_mt, MAPLE_ALLOC_RANGE);
-	mm->vmacache_seqnum = 0;
 	atomic_set(&mm->mm_users, 1);
 	atomic_set(&mm->mm_count, 1);
 	seqcount_init(&mm->write_protect_seq);
@@ -1491,9 +1489,6 @@ static int copy_mm(unsigned long clone_flags, struct task_struct *tsk)
 	if (!oldmm)
 		return 0;
 
-	/* initialize the new vmacache entries */
-	vmacache_flush(tsk);
-
 	if (clone_flags & CLONE_VM) {
 		mmget(oldmm);
 		mm = oldmm;
lib/Kconfig.debug +0 -10
index cdfaafa30ba9..b9bf55a9c6bf 100644
@@ -799,16 +799,6 @@ config DEBUG_VM
 
 	  If unsure, say N.
 
-config DEBUG_VM_VMACACHE
-	bool "Debug VMA caching"
-	depends on DEBUG_VM
-	help
-	  Enable this to turn on VMA caching debug information. Doing so
-	  can cause significant overhead, so only enable it in non-production
-	  environments.
-
-	  If unsure, say N.
-
 config DEBUG_VM_RB
 	bool "Debug VM red-black trees"
 	depends on DEBUG_VM
mm/Makefile +1 -1
index 970604ea97dd..95810fb5e032 100644
@@ -50,7 +50,7 @@ obj-y			:= filemap.o mempool.o oom_kill.o fadvise.o \
 			   readahead.o swap.o truncate.o vmscan.o shmem.o \
 			   util.o mmzone.o vmstat.o backing-dev.o \
 			   mm_init.o percpu.o slab_common.o \
-			   compaction.o vmacache.o \
+			   compaction.o \
 			   interval_tree.o list_lru.o workingset.o \
 			   debug.o gup.o mmap_lock.o $(mmu-y)
 
mm/debug.c +2 -2
index e73fe0a8ec3d..f84662c87b4f 100644
@@ -203,7 +203,7 @@ EXPORT_SYMBOL(dump_vma);
 
 void dump_mm(const struct mm_struct *mm)
 {
-	pr_emerg("mm %px mmap %px seqnum %llu task_size %lu\n"
+	pr_emerg("mm %px mmap %px task_size %lu\n"
 #ifdef CONFIG_MMU
 		"get_unmapped_area %px\n"
 #endif
@@ -231,7 +231,7 @@ void dump_mm(const struct mm_struct *mm)
 		"tlb_flush_pending %d\n"
 		"def_flags: %#lx(%pGv)\n",
 
-		mm, mm->mmap, (long long) mm->vmacache_seqnum, mm->task_size,
+		mm, mm->mmap, mm->task_size,
 #ifdef CONFIG_MMU
 		mm->get_unmapped_area,
 #endif
mm/mmap.c +0 -17
index 060a372fc812..ed9a60d8a006 100644
@@ -13,7 +13,6 @@
 #include <linux/slab.h>
 #include <linux/backing-dev.h>
 #include <linux/mm.h>
-#include <linux/vmacache.h>
 #include <linux/shm.h>
 #include <linux/mman.h>
 #include <linux/pagemap.h>
@@ -712,9 +711,6 @@ inline int vma_expand(struct ma_state *mas, struct vm_area_struct *vma,
 		/* Remove from mm linked list - also updates highest_vm_end */
 		__vma_unlink_list(mm, next);
 
-		/* Kill the cache */
-		vmacache_invalidate(mm);
-
 		if (file)
 			__remove_shared_vm_struct(next, file, mapping);
 
@@ -929,8 +925,6 @@ int __vma_adjust(struct vm_area_struct *vma, unsigned long start,
 
 	if (remove_next) {
 		__vma_unlink_list(mm, next);
-		/* Kill the cache */
-		vmacache_invalidate(mm);
 		if (file)
 			__remove_shared_vm_struct(next, file, mapping);
 	} else if (insert) {
@@ -2226,16 +2220,9 @@ struct vm_area_struct *find_vma_intersection(struct mm_struct *mm,
 	MA_STATE(mas, &mm->mm_mt, start_addr, start_addr);
 
 	mmap_assert_locked(mm);
-	/* Check the cache first. */
-	vma = vmacache_find(mm, start_addr);
-	if (likely(vma))
-		return vma;
-
 	rcu_read_lock();
 	vma = mas_find(&mas, end_addr - 1);
 	rcu_read_unlock();
-	if (vma)
-		vmacache_update(mas.index, vma);
 
 	return vma;
 }
@@ -2628,9 +2615,6 @@ detach_vmas_to_be_unmapped(struct mm_struct *mm, struct vm_area_struct *vma,
 		mm->highest_vm_end = prev ? vm_end_gap(prev) : 0;
 	tail_vma->vm_next = NULL;
 
-	/* Kill the cache */
-	vmacache_invalidate(mm);
-
 	/*
 	 * Do not downgrade mmap_lock if we are next to VM_GROWSDOWN or
 	 * VM_GROWSUP VMA. Such VMAs can change their size under
@@ -3010,7 +2994,6 @@ static int do_brk_munmap(struct ma_state *mas, struct vm_area_struct *vma,
 	if (vma_mas_remove(&unmap, mas))
 		goto mas_store_fail;
 
-	vmacache_invalidate(vma->vm_mm);
 	if (vma->anon_vma) {
 		anon_vma_interval_tree_post_update_vma(vma);
 		anon_vma_unlock_write(vma->anon_vma);
mm/nommu.c +3 -28
index eac5ca450bef..675aee78f8f2 100644
@@ -19,7 +19,6 @@
 #include <linux/export.h>
 #include <linux/mm.h>
 #include <linux/sched/mm.h>
-#include <linux/vmacache.h>
 #include <linux/mman.h>
 #include <linux/swap.h>
 #include <linux/file.h>
@@ -586,22 +585,12 @@ static void add_vma_to_mm(struct mm_struct *mm, struct vm_area_struct *vma)
  */
 static void delete_vma_from_mm(struct vm_area_struct *vma)
 {
-	int i;
-	struct address_space *mapping;
-	struct mm_struct *mm = vma->vm_mm;
-	struct task_struct *curr = current;
 	MA_STATE(mas, &vma->vm_mm->mm_mt, 0, 0);
 
-	mm->map_count--;
-	for (i = 0; i < VMACACHE_SIZE; i++) {
-		/* if the vma is cached, invalidate the entire cache */
-		if (curr->vmacache.vmas[i] == vma) {
-			vmacache_invalidate(mm);
-			break;
-		}
-	}
+	vma->vm_mm->map_count--;
 	/* remove the VMA from the mapping */
 	if (vma->vm_file) {
+		struct address_space *mapping;
 		mapping = vma->vm_file->f_mapping;
 
 		i_mmap_lock_write(mapping);
@@ -613,7 +602,7 @@ static void delete_vma_from_mm(struct vm_area_struct *vma)
 
 	/* remove from the MM's tree and list */
 	vma_mas_remove(vma, &mas);
-	__vma_unlink_list(mm, vma);
+	__vma_unlink_list(vma->vm_mm, vma);
 }
 
 /*
@@ -638,18 +627,10 @@ struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
 	struct vm_area_struct *vma;
 	MA_STATE(mas, &mm->mm_mt, addr, addr);
 
-	/* check the cache first */
-	vma = vmacache_find(mm, addr);
-	if (likely(vma))
-		return vma;
-
 	rcu_read_lock();
 	vma = mas_walk(&mas);
 	rcu_read_unlock();
 
-	if (vma)
-		vmacache_update(addr, vma);
-
 	return vma;
 }
 EXPORT_SYMBOL(find_vma);
@@ -684,11 +665,6 @@ static struct vm_area_struct *find_vma_exact(struct mm_struct *mm,
 	unsigned long end = addr + len;
 	MA_STATE(mas, &mm->mm_mt, addr, addr);
 
-	/* check the cache first */
-	vma = vmacache_find_exact(mm, addr, end);
-	if (vma)
-		return vma;
-
 	rcu_read_lock();
 	vma = mas_walk(&mas);
 	rcu_read_unlock();
@@ -699,7 +675,6 @@ static struct vm_area_struct *find_vma_exact(struct mm_struct *mm,
 	if (vma->vm_end != end)
 		return NULL;
 
-	vmacache_update(addr, vma);
 	return vma;
 }
 
mm/vmacache.c deleted +0 -117

117 lines not on this page · raw message

mm/vmstat.c +0 -4
index 3b6a69496f48..e536f9f9f569 100644
@@ -1369,10 +1369,6 @@ const char * const vmstat_text[] = {
 	"nr_tlb_local_flush_one",
 #endif /* CONFIG_DEBUG_TLBFLUSH */
 
-#ifdef CONFIG_DEBUG_VM_VMACACHE
-	"vmacache_find_calls",
-	"vmacache_find_hits",
-#endif
 #ifdef CONFIG_SWAP
 	"swap_ra",
 	"swap_ra_hit",
Signature · 1 line
2.30.2
#26 lore raw

PATCH v2 19/61 mm/mmap: Move mmap_region() below do_munmap()

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Relocation of code for the next commit. There should be no changes here.

---
 mm/mmap.c | 482 +++++++++++++++++++++++++++---------------------------
 1 file changed, 241 insertions(+), 241 deletions(-)
mm/mmap.c +241 -241
index ed9a60d8a006..ef618dfd1d94 100644
@@ -1720,247 +1720,6 @@ static inline int accountable_mapping(struct file *file, vm_flags_t vm_flags)
 	return (vm_flags & (VM_NORESERVE | VM_SHARED | VM_WRITE)) == VM_WRITE;
 }
 
-unsigned long mmap_region(struct file *file, unsigned long addr,
-		unsigned long len, vm_flags_t vm_flags, unsigned long pgoff,
-		struct list_head *uf)
-{
-	struct mm_struct *mm = current->mm;
-	struct vm_area_struct *vma = NULL;
-	struct vm_area_struct *prev, *next;
-	pgoff_t pglen = len >> PAGE_SHIFT;
-	unsigned long charged = 0;
-	unsigned long end = addr + len;
-	unsigned long merge_start = addr, merge_end = end;
-	pgoff_t vm_pgoff;
-	int error;
-	MA_STATE(mas, &mm->mm_mt, addr, end - 1);
-
-	/* Check against address space limit. */
-	if (!may_expand_vm(mm, vm_flags, len >> PAGE_SHIFT)) {
-		unsigned long nr_pages;
-
-		/*
-		 * MAP_FIXED may remove pages of mappings that intersects with
-		 * requested mapping. Account for the pages it would unmap.
-		 */
-		nr_pages = count_vma_pages_range(mm, addr, end);
-
-		if (!may_expand_vm(mm, vm_flags,
-					(len >> PAGE_SHIFT) - nr_pages))
-			return -ENOMEM;
-	}
-
-	/* Unmap any existing mapping in the area */
-	if (do_munmap(mm, addr, len, uf))
-		return -ENOMEM;
-
-	/*
-	 * Private writable mapping: check memory availability
-	 */
-	if (accountable_mapping(file, vm_flags)) {
-		charged = len >> PAGE_SHIFT;
-		if (security_vm_enough_memory_mm(mm, charged))
-			return -ENOMEM;
-		vm_flags |= VM_ACCOUNT;
-	}
-
-
-	if (vm_flags & VM_SPECIAL) {
-		rcu_read_lock();
-		prev = mas_prev(&mas, 0);
-		rcu_read_unlock();
-		goto cannot_expand;
-	}
-
-	/* Attempt to expand an old mapping */
-
-	/* Check next */
-	rcu_read_lock();
-	next = mas_next(&mas, ULONG_MAX);
-	rcu_read_unlock();
-	if (next && next->vm_start == end && vma_policy(next) &&
-	    can_vma_merge_before(next, vm_flags, NULL, file, pgoff+pglen,
-				 NULL_VM_UFFD_CTX)) {
-		merge_end = next->vm_end;
-		vma = next;
-		vm_pgoff = next->vm_pgoff - pglen;
-	}
-
-	/* Check prev */
-	rcu_read_lock();
-	prev = mas_prev(&mas, 0);
-	rcu_read_unlock();
-	if (prev && prev->vm_end == addr && !vma_policy(prev) &&
-	    can_vma_merge_after(prev, vm_flags, NULL, file, pgoff,
-				NULL_VM_UFFD_CTX)) {
-		merge_start = prev->vm_start;
-		vma = prev;
-		vm_pgoff = prev->vm_pgoff;
-	}
-
-
-	/* Actually expand, if possible */
-	if (vma &&
-	    !vma_expand(&mas, vma, merge_start, merge_end, vm_pgoff, next)) {
-		khugepaged_enter_vma_merge(prev, vm_flags);
-		goto expanded;
-	}
-
-	mas_set_range(&mas, addr, end - 1);
-cannot_expand:
-	/*
-	 * Determine the object being mapped and call the appropriate
-	 * specific mapper. the address has already been validated, but
-	 * not unmapped, but the maps are removed from the list.
-	 */
-	vma = vm_area_alloc(mm);
-	if (!vma) {
-		error = -ENOMEM;
-		goto unacct_error;
-	}
-
-	vma->vm_start = addr;
-	vma->vm_end = end;
-	vma->vm_flags = vm_flags;
-	vma->vm_page_prot = vm_get_page_prot(vm_flags);
-	vma->vm_pgoff = pgoff;
-
-	if (file) {
-		if (vm_flags & VM_DENYWRITE) {
-			error = deny_write_access(file);
-			if (error)
-				goto free_vma;
-		}
-		if (vm_flags & VM_SHARED) {
-			error = mapping_map_writable(file->f_mapping);
-			if (error)
-				goto allow_write_and_free_vma;
-		}
-
-		/* ->mmap() can change vma->vm_file, but must guarantee that
-		 * vma_link() below can deny write-access if VM_DENYWRITE is set
-		 * and map writably if VM_SHARED is set. This usually means the
-		 * new file must not have been exposed to user-space, yet.
-		 */
-		vma->vm_file = get_file(file);
-		error = call_mmap(file, vma);
-		file = vma->vm_file;
-		if (error)
-			goto unmap_and_free_vma;
-
-		/* Can addr have changed??
-		 *
-		 * Answer: Yes, several device drivers can do it in their
-		 *         f_op->mmap method. -DaveM
-		 */
-		WARN_ON_ONCE(addr != vma->vm_start);
-
-		addr = vma->vm_start;
-
-		/* If vm_flags changed after call_mmap(), we should try merge vma again
-		 * as we may succeed this time.
-		 */
-		if (unlikely(vm_flags != vma->vm_flags && prev &&
-			     prev->vm_end == addr && !vma_policy(prev) &&
-			     can_vma_merge_after(prev, vm_flags, NULL, file,
-						 pgoff, NULL_VM_UFFD_CTX))) {
-			merge_start = prev->vm_start;
-			vm_pgoff = prev->vm_pgoff;
-			if (!vma_expand(&mas, prev, merge_start, merge_end,
-					vm_pgoff, next)) {
-				/* ->mmap() can change vma->vm_file and fput the original file. So
-				 * fput the vma->vm_file here or we would add an extra fput for file
-				 * and cause general protection fault ultimately.
-				 */
-				fput(vma->vm_file);
-				vm_area_free(vma);
-				vma = prev;
-				/* Update vm_flags and possible addr to pick up the change. We don't
-				 * warn here if addr changed as the vma is not linked by vma_link().
-				 */
-				addr = vma->vm_start;
-				vm_flags = vma->vm_flags;
-				goto unmap_writable;
-			}
-		}
-
-		vm_flags = vma->vm_flags;
-	} else if (vm_flags & VM_SHARED) {
-		error = shmem_zero_setup(vma);
-		if (error)
-			goto free_vma;
-	} else {
-		vma_set_anonymous(vma);
-	}
-
-	/* Allow architectures to sanity-check the vm_flags */
-	if (!arch_validate_flags(vma->vm_flags)) {
-		error = -EINVAL;
-		if (file)
-			goto unmap_and_free_vma;
-		else
-			goto free_vma;
-	}
-
-	mas_set(&mas, addr);
-	vma_mas_link(mm, vma, &mas, prev);
-	/* Once vma denies write, undo our temporary denial count */
-	if (file) {
-unmap_writable:
-		if (vm_flags & VM_SHARED)
-			mapping_unmap_writable(file->f_mapping);
-		if (vm_flags & VM_DENYWRITE)
-			allow_write_access(file);
-	}
-expanded:
-	perf_event_mmap(vma);
-
-	vm_stat_account(mm, vm_flags, len >> PAGE_SHIFT);
-	if (vm_flags & VM_LOCKED) {
-		if ((vm_flags & VM_SPECIAL) || vma_is_dax(vma) ||
-		    is_vm_hugetlb_page(vma) ||
-		    vma == get_gate_vma(current->mm))
-			vma->vm_flags &= VM_LOCKED_CLEAR_MASK;
-		else
-			mm->locked_vm += (len >> PAGE_SHIFT);
-	}
-
-	if (file)
-		uprobe_mmap(vma);
-
-	/*
-	 * New (or expanded) vma always get soft dirty status.
-	 * Otherwise user-space soft-dirty page tracker won't
-	 * be able to distinguish situation when vma area unmapped,
-	 * then new mapped in-place (which must be aimed as
-	 * a completely new data area).
-	 */
-	vma->vm_flags |= VM_SOFTDIRTY;
-
-	vma_set_page_prot(vma);
-
-	return addr;
-
-unmap_and_free_vma:
-	fput(vma->vm_file);
-	vma->vm_file = NULL;
-
-	/* Undo any partial mapping done by a device driver. */
-	unmap_region(mm, vma, prev, vma->vm_start, vma->vm_end);
-	charged = 0;
-	if (vm_flags & VM_SHARED)
-		mapping_unmap_writable(file->f_mapping);
-allow_write_and_free_vma:
-	if (vm_flags & VM_DENYWRITE)
-		allow_write_access(file);
-free_vma:
-	vm_area_free(vma);
-unacct_error:
-	if (charged)
-		vm_unacct_memory(charged);
-	return error;
-}
-
 /* unmapped_area() Find an area between the low_limit and the high_limit with
  * the correct alignment and offset, all from @info. Note: current->mm is used
  * for the search.
@@ -2825,6 +2584,247 @@ int do_munmap(struct mm_struct *mm, unsigned long start, size_t len,
 	return __do_munmap(mm, start, len, uf, false);
 }
 
+unsigned long mmap_region(struct file *file, unsigned long addr,
+		unsigned long len, vm_flags_t vm_flags, unsigned long pgoff,
+		struct list_head *uf)
+{
+	struct mm_struct *mm = current->mm;
+	struct vm_area_struct *vma = NULL;
+	struct vm_area_struct *prev, *next;
+	pgoff_t pglen = len >> PAGE_SHIFT;
+	unsigned long charged = 0;
+	unsigned long end = addr + len;
+	unsigned long merge_start = addr, merge_end = end;
+	pgoff_t vm_pgoff;
+	int error;
+	MA_STATE(mas, &mm->mm_mt, addr, end - 1);
+
+	/* Check against address space limit. */
+	if (!may_expand_vm(mm, vm_flags, len >> PAGE_SHIFT)) {
+		unsigned long nr_pages;
+
+		/*
+		 * MAP_FIXED may remove pages of mappings that intersects with
+		 * requested mapping. Account for the pages it would unmap.
+		 */
+		nr_pages = count_vma_pages_range(mm, addr, end);
+
+		if (!may_expand_vm(mm, vm_flags,
+					(len >> PAGE_SHIFT) - nr_pages))
+			return -ENOMEM;
+	}
+
+	/* Unmap any existing mapping in the area */
+	if (do_munmap(mm, addr, len, uf))
+		return -ENOMEM;
+
+	/*
+	 * Private writable mapping: check memory availability
+	 */
+	if (accountable_mapping(file, vm_flags)) {
+		charged = len >> PAGE_SHIFT;
+		if (security_vm_enough_memory_mm(mm, charged))
+			return -ENOMEM;
+		vm_flags |= VM_ACCOUNT;
+	}
+
+
+	if (vm_flags & VM_SPECIAL) {
+		rcu_read_lock();
+		prev = mas_prev(&mas, 0);
+		rcu_read_unlock();
+		goto cannot_expand;
+	}
+
+	/* Attempt to expand an old mapping */
+
+	/* Check next */
+	rcu_read_lock();
+	next = mas_next(&mas, ULONG_MAX);
+	rcu_read_unlock();
+	if (next && next->vm_start == end && vma_policy(next) &&
+	    can_vma_merge_before(next, vm_flags, NULL, file, pgoff+pglen,
+				 NULL_VM_UFFD_CTX)) {
+		merge_end = next->vm_end;
+		vma = next;
+		vm_pgoff = next->vm_pgoff - pglen;
+	}
+
+	/* Check prev */
+	rcu_read_lock();
+	prev = mas_prev(&mas, 0);
+	rcu_read_unlock();
+	if (prev && prev->vm_end == addr && !vma_policy(prev) &&
+	    can_vma_merge_after(prev, vm_flags, NULL, file, pgoff,
+				NULL_VM_UFFD_CTX)) {
+		merge_start = prev->vm_start;
+		vma = prev;
+		vm_pgoff = prev->vm_pgoff;
+	}
+
+
+	/* Actually expand, if possible */
+	if (vma &&
+	    !vma_expand(&mas, vma, merge_start, merge_end, vm_pgoff, next)) {
+		khugepaged_enter_vma_merge(prev, vm_flags);
+		goto expanded;
+	}
+
+	mas_set_range(&mas, addr, end - 1);
+cannot_expand:
+	/*
+	 * Determine the object being mapped and call the appropriate
+	 * specific mapper. the address has already been validated, but
+	 * not unmapped, but the maps are removed from the list.
+	 */
+	vma = vm_area_alloc(mm);
+	if (!vma) {
+		error = -ENOMEM;
+		goto unacct_error;
+	}
+
+	vma->vm_start = addr;
+	vma->vm_end = end;
+	vma->vm_flags = vm_flags;
+	vma->vm_page_prot = vm_get_page_prot(vm_flags);
+	vma->vm_pgoff = pgoff;
+
+	if (file) {
+		if (vm_flags & VM_DENYWRITE) {
+			error = deny_write_access(file);
+			if (error)
+				goto free_vma;
+		}
+		if (vm_flags & VM_SHARED) {
+			error = mapping_map_writable(file->f_mapping);
+			if (error)
+				goto allow_write_and_free_vma;
+		}
+
+		/* ->mmap() can change vma->vm_file, but must guarantee that
+		 * vma_link() below can deny write-access if VM_DENYWRITE is set
+		 * and map writably if VM_SHARED is set. This usually means the
+		 * new file must not have been exposed to user-space, yet.
+		 */
+		vma->vm_file = get_file(file);
+		error = call_mmap(file, vma);
+		file = vma->vm_file;
+		if (error)
+			goto unmap_and_free_vma;
+
+		/* Can addr have changed??
+		 *
+		 * Answer: Yes, several device drivers can do it in their
+		 *         f_op->mmap method. -DaveM
+		 */
+		WARN_ON_ONCE(addr != vma->vm_start);
+
+		addr = vma->vm_start;
+
+		/* If vm_flags changed after call_mmap(), we should try merge vma again
+		 * as we may succeed this time.
+		 */
+		if (unlikely(vm_flags != vma->vm_flags && prev &&
+			     prev->vm_end == addr && !vma_policy(prev) &&
+			     can_vma_merge_after(prev, vm_flags, NULL, file,
+						 pgoff, NULL_VM_UFFD_CTX))) {
+			merge_start = prev->vm_start;
+			vm_pgoff = prev->vm_pgoff;
+			if (!vma_expand(&mas, prev, merge_start, merge_end,
+					vm_pgoff, next)) {
+				/* ->mmap() can change vma->vm_file and fput the original file. So
+				 * fput the vma->vm_file here or we would add an extra fput for file
+				 * and cause general protection fault ultimately.
+				 */
+				fput(vma->vm_file);
+				vm_area_free(vma);
+				vma = prev;
+				/* Update vm_flags and possible addr to pick up the change. We don't
+				 * warn here if addr changed as the vma is not linked by vma_link().
+				 */
+				addr = vma->vm_start;
+				vm_flags = vma->vm_flags;
+				goto unmap_writable;
+			}
+		}
+
+		vm_flags = vma->vm_flags;
+	} else if (vm_flags & VM_SHARED) {
+		error = shmem_zero_setup(vma);
+		if (error)
+			goto free_vma;
+	} else {
+		vma_set_anonymous(vma);
+	}
+
+	/* Allow architectures to sanity-check the vm_flags */
+	if (!arch_validate_flags(vma->vm_flags)) {
+		error = -EINVAL;
+		if (file)
+			goto unmap_and_free_vma;
+		else
+			goto free_vma;
+	}
+
+	mas_set(&mas, addr);
+	vma_mas_link(mm, vma, &mas, prev);
+	/* Once vma denies write, undo our temporary denial count */
+	if (file) {
+unmap_writable:
+		if (vm_flags & VM_SHARED)
+			mapping_unmap_writable(file->f_mapping);
+		if (vm_flags & VM_DENYWRITE)
+			allow_write_access(file);
+	}
+expanded:
+	perf_event_mmap(vma);
+
+	vm_stat_account(mm, vm_flags, len >> PAGE_SHIFT);
+	if (vm_flags & VM_LOCKED) {
+		if ((vm_flags & VM_SPECIAL) || vma_is_dax(vma) ||
+		    is_vm_hugetlb_page(vma) ||
+		    vma == get_gate_vma(current->mm))
+			vma->vm_flags &= VM_LOCKED_CLEAR_MASK;
+		else
+			mm->locked_vm += (len >> PAGE_SHIFT);
+	}
+
+	if (file)
+		uprobe_mmap(vma);
+
+	/*
+	 * New (or expanded) vma always get soft dirty status.
+	 * Otherwise user-space soft-dirty page tracker won't
+	 * be able to distinguish situation when vma area unmapped,
+	 * then new mapped in-place (which must be aimed as
+	 * a completely new data area).
+	 */
+	vma->vm_flags |= VM_SOFTDIRTY;
+
+	vma_set_page_prot(vma);
+
+	return addr;
+
+unmap_and_free_vma:
+	fput(vma->vm_file);
+	vma->vm_file = NULL;
+
+	/* Undo any partial mapping done by a device driver. */
+	unmap_region(mm, vma, prev, vma->vm_start, vma->vm_end);
+	charged = 0;
+	if (vm_flags & VM_SHARED)
+		mapping_unmap_writable(file->f_mapping);
+allow_write_and_free_vma:
+	if (vm_flags & VM_DENYWRITE)
+		allow_write_access(file);
+free_vma:
+	vm_area_free(vma);
+unacct_error:
+	if (charged)
+		vm_unacct_memory(charged);
+	return error;
+}
+
 static int __vm_munmap(unsigned long start, size_t len, bool downgrade)
 {
 	int ret;
Signature · 1 line
2.30.2
#27 lore raw

PATCH v2 20/61 mm/mmap: Convert count_vma_pages_range() to use ma_state

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

mmap_region() uses a maple state to do all the work so convert the static inline count_vma_pages_range() to use the same structure.

---
 mm/mmap.c | 27 +++++++++++++++++++--------
 1 file changed, 19 insertions(+), 8 deletions(-)
mm/mmap.c +19 -8
index ef618dfd1d94..d01659a64b86 100644
@@ -502,30 +502,41 @@ static inline struct vm_area_struct *vma_next(struct mm_struct *mm,
 	return vma->vm_next;
 }
 
-static unsigned long count_vma_pages_range(struct mm_struct *mm,
-		unsigned long addr, unsigned long end)
+/*
+ * count_vma_pages_range() - Count the number of pages in a range.
+ * @mas: The maple state
+ *
+ * The start and end address are in the @mas
+ * @mas must be locked.
+ */
+static unsigned long count_vma_pages_range(struct ma_state *mas)
 {
 	unsigned long nr_pages = 0;
 	struct vm_area_struct *vma;
 	unsigned long vm_start, vm_end;
-	MA_STATE(mas, &mm->mm_mt, addr, addr);
+	unsigned long end = mas->last;
+	unsigned long addr = mas->index;
+	struct ma_state ma_count = *mas;
 
+	rcu_read_lock();
 	/* Find first overlapping mapping */
-	vma = mas_find(&mas, end - 1);
+	vma = mas_find(&ma_count, end);
 	if (!vma)
-		return 0;
+		goto unlock;
 
 	vm_start = vma->vm_start;
 	vm_end = vma->vm_end;
-	nr_pages = (min(end, vm_end) - max(addr, vm_start)) >> PAGE_SHIFT;
+	nr_pages = (min(end + 1, vm_end) - max(addr, vm_start)) >> PAGE_SHIFT;
 
 	/* Iterate over the rest of the overlaps */
-	mas_for_each(&mas, vma, end) {
+	mas_for_each(&ma_count, vma, end) {
 		vm_start = vma->vm_start;
 		vm_end = vma->vm_end;
 		nr_pages += (min(end, vm_end) - vm_start) >> PAGE_SHIFT;
 	}
 
+unlock:
+	rcu_read_unlock();
 	return nr_pages;
 }
 
@@ -2607,7 +2618,7 @@ unsigned long mmap_region(struct file *file, unsigned long addr,
 		 * MAP_FIXED may remove pages of mappings that intersects with
 		 * requested mapping. Account for the pages it would unmap.
 		 */
-		nr_pages = count_vma_pages_range(mm, addr, end);
+		nr_pages = count_vma_pages_range(&mas);
 
 		if (!may_expand_vm(mm, vm_flags,
 					(len >> PAGE_SHIFT) - nr_pages))
Signature · 1 line
2.30.2
#28 lore raw

PATCH v2 21/61 mm/mmap: Reorganize munmap to use maple states

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Remove __do_munmap() in favour of do_munmap(), do_mas_munmap(), and do_mas_align_munmap().

do_munmap() is a wrapper to create a maple state for any callers that have not been converted to the maple tree.

do_mas_munmap() takes a maple state to mumap a range. This is just a small function which checks for error conditions and aligns the end of the range.

do_mas_align_munmap() uses the aligned range to mumap a range. do_mas_align_munmap() starts with the first VMA in the range, then finds the last VMA in the range. Both start and end are split if necessary. Then the VMAs are unlocked and removed from the linked list at the same time. Followed by a single tree operation of overwriting the area in with a NULL. Finally, the detached list is unmapped and freed.

By reorganizing the munmap calls as outlined, it is now possible to avoid extra work of aligning pre-aligned callers which are known to be safe, avoid extra VMA lookups or tree walks for modifications.

detach_vmas_to_be_unmapped() is no longer used, so drop this code.

---
 include/linux/mm.h |   5 +-
 mm/mmap.c          | 212 +++++++++++++++++++++++++++------------------
 mm/mremap.c        |   7 +-
 3 files changed, 134 insertions(+), 90 deletions(-)
include/linux/mm.h +3 -2
index 10763bd6fccb..e14d07649007 100644
@@ -2702,8 +2702,9 @@ extern unsigned long mmap_region(struct file *file, unsigned long addr,
 extern unsigned long do_mmap(struct file *file, unsigned long addr,
 	unsigned long len, unsigned long prot, unsigned long flags,
 	unsigned long pgoff, unsigned long *populate, struct list_head *uf);
-extern int __do_munmap(struct mm_struct *, unsigned long, size_t,
-		       struct list_head *uf, bool downgrade);
+extern int do_mas_munmap(struct ma_state *mas, struct mm_struct *mm,
+			 unsigned long start, size_t len, struct list_head *uf,
+			 bool downgrade);
 extern int do_munmap(struct mm_struct *, unsigned long, size_t,
 		     struct list_head *uf);
 extern int do_madvise(struct mm_struct *mm, unsigned long start, size_t len_in, int behavior);
mm/mmap.c +127 -85

303 lines not on this page · raw message

mm/mremap.c +4 -3
index c0b6c41b7b78..f48ccfcf3217 100644
@@ -948,14 +948,15 @@ SYSCALL_DEFINE5(mremap, unsigned long, addr, unsigned long, old_len,
 	/*
 	 * Always allow a shrinking remap: that just unmaps
 	 * the unnecessary pages..
-	 * __do_munmap does all the needed commit accounting, and
+	 * do_mas_munmap does all the needed commit accounting, and
 	 * downgrades mmap_lock to read if so directed.
 	 */
 	if (old_len >= new_len) {
 		int retval;
+		MA_STATE(mas, &mm->mm_mt, addr + new_len, addr + new_len);
 
-		retval = __do_munmap(mm, addr+new_len, old_len - new_len,
-				  &uf_unmap, true);
+		retval = do_mas_munmap(&mas, mm, addr + new_len,
+				       old_len - new_len, &uf_unmap, true);
 		if (retval < 0 && old_len != new_len) {
 			ret = retval;
 			goto out;
Signature · 1 line
2.30.2
#29 lore raw

PATCH v2 22/61 mm/mmap: Change do_brk_munmap() to use do_mas_align_munmap()

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

do_brk_munmap() has already aligned the address and has a maple tree state to be used. Use the new do_mas_align_munmap() to avoid unnecessary alignment and error checks.

---
 mm/mmap.c | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)
mm/mmap.c +7 -3
index 4fdeed164381..150d9e9c0a68 100644
@@ -3019,12 +3019,16 @@ static int do_brk_munmap(struct ma_state *mas, struct vm_area_struct *vma,
 	struct mm_struct *mm = vma->vm_mm;
 	struct vm_area_struct unmap;
 	unsigned long unmap_pages;
-	int ret = 1;
+	int ret;
 
 	arch_unmap(mm, newbrk, oldbrk);
 
-	if (likely(vma->vm_start >= newbrk)) { // remove entire mapping(s)
-		ret = do_mas_munmap(mas, mm, newbrk, oldbrk-newbrk, uf, true);
+	if (likely((vma->vm_end < oldbrk) ||
+		   ((vma->vm_start == newbrk) && (vma->vm_end == oldbrk)))) {
+		// remove entire mapping(s)
+		mas->last = oldbrk - 1;
+		ret = do_mas_align_munmap(mas, vma, mm, newbrk, oldbrk, uf,
+					  true);
 		goto munmap_full_vma;
 	}
 
Signature · 1 line
2.30.2
#30 lore raw

PATCH v2 23/61 mm: Introduce vma_next() and vma_prev()

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Rename internal vma_next() to _vma_next().

---
 include/linux/mm.h | 12 ++++++++++++
 mm/mmap.c          | 12 ++++++------
 2 files changed, 18 insertions(+), 6 deletions(-)
include/linux/mm.h +12 -0
index e14d07649007..7a5eb1fbb488 100644
@@ -2796,6 +2796,18 @@ struct vm_area_struct *vma_lookup(struct mm_struct *mm, unsigned long addr)
        return mtree_load(&mm->mm_mt, addr);
 }
 
+static inline struct vm_area_struct *vma_next(struct mm_struct *mm,
+			const struct vm_area_struct *vma)
+{
+	return mt_next(&mm->mm_mt, vma->vm_end - 1, ULONG_MAX);
+}
+
+static inline struct vm_area_struct *vma_prev(struct mm_struct *mm,
+			const struct vm_area_struct *vma)
+{
+	return mt_prev(&mm->mm_mt, vma->vm_start, 0);
+}
+
 static inline unsigned long vm_start_gap(struct vm_area_struct *vma)
 {
 	unsigned long vm_start = vma->vm_start;
mm/mmap.c +6 -6
index 150d9e9c0a68..afef4af1c621 100644
@@ -485,7 +485,7 @@ bool range_has_overlap(struct mm_struct *mm, unsigned long start,
 }
 
 /*
- * vma_next() - Get the next VMA.
+ * _vma_next() - Get the next VMA or the first.
  * @mm: The mm_struct.
  * @vma: The current vma.
  *
@@ -493,7 +493,7 @@ bool range_has_overlap(struct mm_struct *mm, unsigned long start,
  *
  * Returns: The next VMA after @vma.
  */
-static inline struct vm_area_struct *vma_next(struct mm_struct *mm,
+static inline struct vm_area_struct *_vma_next(struct mm_struct *mm,
 					 struct vm_area_struct *vma)
 {
 	if (!vma)
@@ -1182,7 +1182,7 @@ struct vm_area_struct *vma_merge(struct mm_struct *mm,
 	if (vm_flags & VM_SPECIAL)
 		return NULL;
 
-	next = vma_next(mm, prev);
+	next = _vma_next(mm, prev);
 	area = next;
 	if (area && area->vm_end == end)		/* cases 6, 7, 8 */
 		next = next->vm_next;
@@ -2347,7 +2347,7 @@ static void unmap_region(struct mm_struct *mm,
 		struct vm_area_struct *vma, struct vm_area_struct *prev,
 		unsigned long start, unsigned long end)
 {
-	struct vm_area_struct *next = vma_next(mm, prev);
+	struct vm_area_struct *next = _vma_next(mm, prev);
 	struct mmu_gather tlb;
 
 	lru_add_drain();
@@ -2501,7 +2501,7 @@ do_mas_align_munmap(struct ma_state *mas, struct vm_area_struct *vma,
 		if (error)
 			return error;
 		prev = vma;
-		vma = vma_next(mm, prev);
+		vma = _vma_next(mm, prev);
 		mas->index = start;
 		mas_reset(mas);
 	} else {
@@ -2518,7 +2518,7 @@ do_mas_align_munmap(struct ma_state *mas, struct vm_area_struct *vma,
 		int error = __split_vma(mm, last, end, 1);
 		if (error)
 			return error;
-		vma = vma_next(mm, prev);
+		vma = _vma_next(mm, prev);
 		mas_reset(mas);
 	}
 
Signature · 1 line
2.30.2
#31 lore raw

PATCH v2 24/61 arch/arm64: Remove mmap linked list from vdso.

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Start using the maple tree

---
 arch/arm64/kernel/vdso.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)
arch/arm64/kernel/vdso.c +4 -1
index a61fc4f989b3..57ea81fbe04b 100644
@@ -136,10 +136,12 @@ int vdso_join_timens(struct task_struct *task, struct time_namespace *ns)
 {
 	struct mm_struct *mm = task->mm;
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	mmap_read_lock(mm);
 
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	rcu_read_lock();
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		unsigned long size = vma->vm_end - vma->vm_start;
 
 		if (vma_is_special_mapping(vma, vdso_info[VDSO_ABI_AA64].dm))
@@ -149,6 +151,7 @@ int vdso_join_timens(struct task_struct *task, struct time_namespace *ns)
 			zap_page_range(vma, vma->vm_start, size);
 #endif
 	}
+	rcu_read_unlock();
 
 	mmap_read_unlock(mm);
 	return 0;
Signature · 1 line
2.30.2
#32 lore raw

PATCH v2 25/61 arch/parisc: Remove mmap linked list from kernel/cache

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Start using the maple tree

---
 arch/parisc/kernel/cache.c | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)
arch/parisc/kernel/cache.c +12 -3
index 39e02227e231..f6316aafba10 100644
@@ -519,9 +519,13 @@ static inline unsigned long mm_total_size(struct mm_struct *mm)
 {
 	struct vm_area_struct *vma;
 	unsigned long usize = 0;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
-	for (vma = mm->mmap; vma; vma = vma->vm_next)
+	rcu_read_lock();
+	mas_for_each(&mas, vma, ULONG_MAX)
 		usize += vma->vm_end - vma->vm_start;
+	rcu_read_unlock();
+
 	return usize;
 }
 
@@ -547,6 +551,7 @@ void flush_cache_mm(struct mm_struct *mm)
 {
 	struct vm_area_struct *vma;
 	pgd_t *pgd;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	/* Flushing the whole cache on each cpu takes forever on
 	   rp3440, etc.  So, avoid it if the mm isn't too big.  */
@@ -559,17 +564,20 @@ void flush_cache_mm(struct mm_struct *mm)
 	}
 
 	if (mm->context == mfsp(3)) {
-		for (vma = mm->mmap; vma; vma = vma->vm_next) {
+		rcu_read_lock();
+		mas_for_each(&mas, vma, ULONG_MAX) {
 			flush_user_dcache_range_asm(vma->vm_start, vma->vm_end);
 			if (vma->vm_flags & VM_EXEC)
 				flush_user_icache_range_asm(vma->vm_start, vma->vm_end);
 			flush_tlb_range(vma, vma->vm_start, vma->vm_end);
 		}
+		rcu_read_unlock();
 		return;
 	}
 
 	pgd = mm->pgd;
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	rcu_read_lock();
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		unsigned long addr;
 
 		for (addr = vma->vm_start; addr < vma->vm_end;
@@ -589,6 +597,7 @@ void flush_cache_mm(struct mm_struct *mm)
 			}
 		}
 	}
+	rcu_read_unlock();
 }
 
 void flush_cache_range(struct vm_area_struct *vma,
Signature · 1 line
2.30.2
#33 lore raw

PATCH v2 26/61 arch/powerpc: Remove mmap linked list from mm/book3s32/tlb

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Start using the maple tree

---
 arch/powerpc/mm/book3s32/tlb.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)
arch/powerpc/mm/book3s32/tlb.c +4 -1
index 19f0ef950d77..2c8b991de8e8 100644
@@ -81,6 +81,7 @@ EXPORT_SYMBOL(hash__flush_range);
 void hash__flush_tlb_mm(struct mm_struct *mm)
 {
 	struct vm_area_struct *mp;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	/*
 	 * It is safe to go down the mm's list of vmas when called
@@ -88,8 +89,10 @@ void hash__flush_tlb_mm(struct mm_struct *mm)
 	 * unmap_region or exit_mmap, but not from vmtruncate on SMP -
 	 * but it seems dup_mmap is the only SMP case which gets here.
 	 */
-	for (mp = mm->mmap; mp != NULL; mp = mp->vm_next)
+	rcu_read_lock();
+	mas_for_each(&mas, mp, ULONG_MAX)
 		hash__flush_range(mp->vm_mm, mp->vm_start, mp->vm_end);
+	rcu_read_unlock();
 }
 EXPORT_SYMBOL(hash__flush_tlb_mm);
 
Signature · 1 line
2.30.2
#34 lore raw

PATCH v2 27/61 arch/powerpc: Remove mmap linked list from mm/book3s64/subpage_prot

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Start using the maple tree

---
 arch/powerpc/mm/book3s64/subpage_prot.c | 15 ++++-----------
 1 file changed, 4 insertions(+), 11 deletions(-)
arch/powerpc/mm/book3s64/subpage_prot.c +4 -11
index 60c6ea16a972..51722199408e 100644
@@ -149,25 +149,18 @@ static void subpage_mark_vma_nohuge(struct mm_struct *mm, unsigned long addr,
 				    unsigned long len)
 {
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, addr, addr);
 
 	/*
 	 * We don't try too hard, we just mark all the vma in that range
 	 * VM_NOHUGEPAGE and split them.
 	 */
-	vma = find_vma(mm, addr);
-	/*
-	 * If the range is in unmapped range, just return
-	 */
-	if (vma && ((addr + len) <= vma->vm_start))
-		return;
-
-	while (vma) {
-		if (vma->vm_start >= (addr + len))
-			break;
+	rcu_read_lock();
+	mas_for_each(&mas, vma, addr + len) {
 		vma->vm_flags |= VM_NOHUGEPAGE;
 		walk_page_vma(vma, &subpage_walk_ops, NULL);
-		vma = vma->vm_next;
 	}
+	rcu_read_unlock();
 }
 #else
 static void subpage_mark_vma_nohuge(struct mm_struct *mm, unsigned long addr,
Signature · 1 line
2.30.2
#35 lore raw

PATCH v2 28/61 arch/s390: Use maple tree iterators instead of linked list.

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 arch/s390/mm/gmap.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)
arch/s390/mm/gmap.c +6 -2
index 9bb2c7512cd5..77879744d652 100644
@@ -2502,8 +2502,10 @@ static const struct mm_walk_ops thp_split_walk_ops = {
 static inline void thp_split_mm(struct mm_struct *mm)
 {
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
-	for (vma = mm->mmap; vma != NULL; vma = vma->vm_next) {
+	/* Must hold mm_mt lock already */
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		vma->vm_flags &= ~VM_HUGEPAGE;
 		vma->vm_flags |= VM_NOHUGEPAGE;
 		walk_page_vma(vma, &thp_split_walk_ops, NULL);
@@ -2571,8 +2573,10 @@ int gmap_mark_unmergeable(void)
 	struct mm_struct *mm = current->mm;
 	struct vm_area_struct *vma;
 	int ret;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	/* Must hold mm_mt lock already */
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		ret = ksm_madvise(vma, vma->vm_start, vma->vm_end,
 				  MADV_UNMERGEABLE, &vma->vm_flags);
 		if (ret)
Signature · 1 line
2.30.2
#36 lore raw

PATCH v2 29/61 arch/x86: Use maple tree iterators for vdso/vma

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 arch/x86/entry/vdso/vma.c | 12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)
arch/x86/entry/vdso/vma.c +10 -2
index 235a5794296a..c0b160a9585d 100644
@@ -128,15 +128,19 @@ int vdso_join_timens(struct task_struct *task, struct time_namespace *ns)
 	struct mm_struct *mm = task->mm;
 	struct vm_area_struct *vma;
 
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
+
 	mmap_read_lock(mm);
+	rcu_read_lock();
 
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		unsigned long size = vma->vm_end - vma->vm_start;
 
 		if (vma_is_special_mapping(vma, &vvar_mapping))
 			zap_page_range(vma, vma->vm_start, size);
 	}
 
+	rcu_read_unlock();
 	mmap_read_unlock(mm);
 	return 0;
 }
@@ -354,6 +358,7 @@ int map_vdso_once(const struct vdso_image *image, unsigned long addr)
 {
 	struct mm_struct *mm = current->mm;
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	mmap_write_lock(mm);
 	/*
@@ -363,13 +368,16 @@ int map_vdso_once(const struct vdso_image *image, unsigned long addr)
 	 * We could search vma near context.vdso, but it's a slowpath,
 	 * so let's explicitly check all VMAs to be completely sure.
 	 */
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	mas_lock(&mas);
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		if (vma_is_special_mapping(vma, &vdso_mapping) ||
 				vma_is_special_mapping(vma, &vvar_mapping)) {
+			mas_unlock(&mas);
 			mmap_write_unlock(mm);
 			return -EEXIST;
 		}
 	}
+	mas_unlock(&mas);
 	mmap_write_unlock(mm);
 
 	return map_vdso(image, addr);
Signature · 1 line
2.30.2
#37 lore raw

PATCH v2 30/61 arch/xtensa: Use maple tree iterators for unmapped area

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 arch/xtensa/kernel/syscall.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)
arch/xtensa/kernel/syscall.c +3 -1
index 201356faa7e6..118fe0ca7594 100644
@@ -58,6 +58,7 @@ unsigned long arch_get_unmapped_area(struct file *filp, unsigned long addr,
 		unsigned long len, unsigned long pgoff, unsigned long flags)
 {
 	struct vm_area_struct *vmm;
+	MA_STATE(mas, &mm->mm_mt, addr, addr);
 
 	if (flags & MAP_FIXED) {
 		/* We do not accept a shared mapping if it would violate
@@ -79,7 +80,8 @@ unsigned long arch_get_unmapped_area(struct file *filp, unsigned long addr,
 	else
 		addr = PAGE_ALIGN(addr);
 
-	for (vmm = find_vma(current->mm, addr); ; vmm = vmm->vm_next) {
+	/* Must hold mm_mt lock */
+	mas_for_each(&mas, vmm, ULONG_MAX) {
 		/* At this point:  (!vmm || addr < vmm->vm_end). */
 		if (TASK_SIZE - len < addr)
 			return -ENOMEM;
Signature · 1 line
2.30.2
#38 lore raw

PATCH v2 31/61 drivers/misc/cxl: Use maple tree iterators for cxl_prefault_vma()

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 drivers/misc/cxl/fault.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)
drivers/misc/cxl/fault.c +5 -1
index 60c829113299..60a33b953ef4 100644
@@ -313,6 +313,7 @@ static void cxl_prefault_vma(struct cxl_context *ctx)
 	struct vm_area_struct *vma;
 	int rc;
 	struct mm_struct *mm;
+	MA_STATE(mas, NULL, 0, 0);
 
 	mm = get_mem_context(ctx);
 	if (mm == NULL) {
@@ -321,8 +322,10 @@ static void cxl_prefault_vma(struct cxl_context *ctx)
 		return;
 	}
 
+	mas.tree = &mm->mm_mt;
 	mmap_read_lock(mm);
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	rcu_read_lock();
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		for (ea = vma->vm_start; ea < vma->vm_end;
 				ea = next_segment(ea, slb.vsid)) {
 			rc = copro_calculate_slb(mm, ea, &slb);
@@ -336,6 +339,7 @@ static void cxl_prefault_vma(struct cxl_context *ctx)
 			last_esid = slb.esid;
 		}
 	}
+	rcu_read_unlock();
 	mmap_read_unlock(mm);
 
 	mmput(mm);
Signature · 1 line
2.30.2
#39 lore raw

PATCH v2 32/61 drivers/tee/optee: Use maple tree iterators for __check_mem_type()

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 drivers/tee/optee/call.c | 15 +++++++++++----
 1 file changed, 11 insertions(+), 4 deletions(-)
drivers/tee/optee/call.c +11 -4
index 945f03da0223..071ff5d9c059 100644
@@ -582,11 +582,18 @@ static bool is_normal_memory(pgprot_t p)
 
 static int __check_mem_type(struct vm_area_struct *vma, unsigned long end)
 {
-	while (vma && is_normal_memory(vma->vm_page_prot)) {
-		if (vma->vm_end >= end)
-			return 0;
-		vma = vma->vm_next;
+	MA_STATE(mas, &vma->vm_mm->mm_mt, vma->vm_start, vma->vm_start);
+
+
+	rcu_read_lock();
+	mas_for_each(&mas, vma, end) {
+		if (!is_normal_memory(vma->vm_page_prot))
+		    break;
 	}
+	rcu_read_unlock();
+
+	if (!vma)
+		return 0;
 
 	return -EINVAL;
 }
Signature · 1 line
2.30.2
#40 lore raw

PATCH v2 33/61 fs/binfmt_elf: Use maple tree iterators for fill_files_note()

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 fs/binfmt_elf.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)
fs/binfmt_elf.c +4 -1
index 439ed81e755a..4a13324aaba1 100644
@@ -1614,6 +1614,7 @@ static int fill_files_note(struct memelfnote *note)
 	user_long_t *data;
 	user_long_t *start_end_ofs;
 	char *name_base, *name_curpos;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	/* *Estimated* file count and total data size needed */
 	count = mm->map_count;
@@ -1638,7 +1639,8 @@ static int fill_files_note(struct memelfnote *note)
 	name_base = name_curpos = ((char *)data) + names_ofs;
 	remaining = size - names_ofs;
 	count = 0;
-	for (vma = mm->mmap; vma != NULL; vma = vma->vm_next) {
+	rcu_read_lock();
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		struct file *file;
 		const char *filename;
 
@@ -1667,6 +1669,7 @@ static int fill_files_note(struct memelfnote *note)
 		*start_end_ofs++ = vma->vm_pgoff;
 		count++;
 	}
+	rcu_read_unlock();
 
 	/* Now we know exact count of files, can store it */
 	data[0] = count;
Signature · 1 line
2.30.2
#41 lore raw

PATCH v2 34/61 fs/coredump: Use maple tree iterators in place of linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 fs/coredump.c | 13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)
fs/coredump.c +7 -6
index 4b3c75732c97..584a9742aa27 100644
@@ -1063,10 +1063,10 @@ static unsigned long vma_dump_size(struct vm_area_struct *vma,
 	return vma->vm_end - vma->vm_start;
 }
 
-static struct vm_area_struct *first_vma(struct task_struct *tsk,
+static struct vm_area_struct *first_vma(struct mm_struct *mm,
 					struct vm_area_struct *gate_vma)
 {
-	struct vm_area_struct *ret = tsk->mm->mmap;
+	struct vm_area_struct *ret = find_vma(mm, 0);
 
 	if (ret)
 		return ret;
@@ -1077,12 +1077,13 @@ static struct vm_area_struct *first_vma(struct task_struct *tsk,
  * Helper function for iterating across a vma list.  It ensures that the caller
  * will visit `gate_vma' prior to terminating the search.
  */
-static struct vm_area_struct *next_vma(struct vm_area_struct *this_vma,
+static struct vm_area_struct *next_vma(struct mm_struct *mm,
+				       struct vm_area_struct *this_vma,
 				       struct vm_area_struct *gate_vma)
 {
 	struct vm_area_struct *ret;
 
-	ret = this_vma->vm_next;
+	ret = vma_next(mm, this_vma);
 	if (ret)
 		return ret;
 	if (this_vma == gate_vma)
@@ -1120,8 +1121,8 @@ int dump_vma_snapshot(struct coredump_params *cprm, int *vma_count,
 		return -ENOMEM;
 	}
 
-	for (i = 0, vma = first_vma(current, gate_vma); vma != NULL;
-			vma = next_vma(vma, gate_vma), i++) {
+	for (i = 0, vma = first_vma(mm, gate_vma); vma != NULL;
+			vma = next_vma(mm, vma, gate_vma), i++) {
 		struct core_vma_metadata *m = (*vma_meta) + i;
 
 		m->start = vma->vm_start;
Signature · 1 line
2.30.2
#42 lore raw

PATCH v2 35/61 fs/exec: Use vma_next() instead of linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 fs/exec.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
fs/exec.c +4 -2
index 9cc6bf3a5f0c..d3eb43866e1e 100644
@@ -680,6 +680,7 @@ static int shift_arg_pages(struct vm_area_struct *vma, unsigned long shift)
 	unsigned long length = old_end - old_start;
 	unsigned long new_start = old_start - shift;
 	unsigned long new_end = old_end - shift;
+	struct vm_area_struct *next;
 	struct mmu_gather tlb;
 
 	BUG_ON(new_start > new_end);
@@ -707,12 +708,13 @@ static int shift_arg_pages(struct vm_area_struct *vma, unsigned long shift)
 
 	lru_add_drain();
 	tlb_gather_mmu(&tlb, mm);
+	next = vma_next(mm, vma);
 	if (new_end > old_start) {
 		/*
 		 * when the old and new regions overlap clear from new_end.
 		 */
 		free_pgd_range(&tlb, new_end, old_end, new_end,
-			vma->vm_next ? vma->vm_next->vm_start : USER_PGTABLES_CEILING);
+			next ? next->vm_start : USER_PGTABLES_CEILING);
 	} else {
 		/*
 		 * otherwise, clean from old_start; this is done to not touch
@@ -721,7 +723,7 @@ static int shift_arg_pages(struct vm_area_struct *vma, unsigned long shift)
 		 * for the others its just a little faster.
 		 */
 		free_pgd_range(&tlb, old_start, old_end, new_end,
-			vma->vm_next ? vma->vm_next->vm_start : USER_PGTABLES_CEILING);
+			next ? next->vm_start : USER_PGTABLES_CEILING);
 	}
 	tlb_finish_mmu(&tlb);
 
Signature · 1 line
2.30.2
#43 lore raw

PATCH v2 36/61 fs/proc/base: Use maple tree iterators in place of linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 fs/proc/base.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
fs/proc/base.c +6 -1
index 533d5836eb9a..4f7e7c8abfd8 100644
@@ -2318,6 +2318,7 @@ proc_map_files_readdir(struct file *file, struct dir_context *ctx)
 	GENRADIX(struct map_files_info) fa;
 	struct map_files_info *p;
 	int ret;
+	MA_STATE(mas, NULL, 0, 0);
 
 	genradix_init(&fa);
 
@@ -2343,8 +2344,10 @@ proc_map_files_readdir(struct file *file, struct dir_context *ctx)
 		mmput(mm);
 		goto out_put_task;
 	}
+	rcu_read_lock();
 
 	nr_files = 0;
+	mas.tree = &mm->mm_mt;
 
 	/*
 	 * We need two passes here:
@@ -2356,7 +2359,8 @@ proc_map_files_readdir(struct file *file, struct dir_context *ctx)
 	 * routine might require mmap_lock taken in might_fault().
 	 */
 
-	for (vma = mm->mmap, pos = 2; vma; vma = vma->vm_next) {
+	pos = 2;
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		if (!vma->vm_file)
 			continue;
 		if (++pos <= ctx->pos)
@@ -2374,6 +2378,7 @@ proc_map_files_readdir(struct file *file, struct dir_context *ctx)
 		p->end = vma->vm_end;
 		p->mode = vma->vm_file->f_mode;
 	}
+	rcu_read_unlock();
 	mmap_read_unlock(mm);
 	mmput(mm);
 
Signature · 1 line
2.30.2
#44 lore raw

PATCH v2 37/61 fs/proc/task_mmu: Stop using linked list and highest_vm_end

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Remove references to mm_struct linked list and highest_vm_end for when they are removed

---
 fs/proc/task_mmu.c | 47 ++++++++++++++++++++++++++++------------------
 1 file changed, 29 insertions(+), 18 deletions(-)
fs/proc/task_mmu.c +29 -18
index ab9b4ff44b54..bea4d54ae90a 100644
@@ -164,14 +164,13 @@ static void *m_start(struct seq_file *m, loff_t *ppos)
 static void *m_next(struct seq_file *m, void *v, loff_t *ppos)
 {
 	struct proc_maps_private *priv = m->private;
-	struct vm_area_struct *next, *vma = v;
+	struct vm_area_struct *next = NULL, *vma = v;
 
-	if (vma == priv->tail_vma)
-		next = NULL;
-	else if (vma->vm_next)
-		next = vma->vm_next;
-	else
-		next = priv->tail_vma;
+	if (vma != priv->tail_vma) {
+		next = vma_next(vma->vm_mm, vma);
+		if (!next)
+			next = priv->tail_vma;
+	}
 
 	*ppos = next ? next->vm_start : -1UL;
 
@@ -840,16 +839,16 @@ static int show_smaps_rollup(struct seq_file *m, void *v)
 {
 	struct proc_maps_private *priv = m->private;
 	struct mem_size_stats mss;
-	struct mm_struct *mm;
+	struct mm_struct *mm = priv->mm;
 	struct vm_area_struct *vma;
-	unsigned long last_vma_end = 0;
+	unsigned long vma_start = 0, last_vma_end = 0;
 	int ret = 0;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	priv->task = get_proc_task(priv->inode);
 	if (!priv->task)
 		return -ESRCH;
 
-	mm = priv->mm;
 	if (!mm || !mmget_not_zero(mm)) {
 		ret = -ESRCH;
 		goto out_put_task;
@@ -862,8 +861,14 @@ static int show_smaps_rollup(struct seq_file *m, void *v)
 		goto out_put_mm;
 
 	hold_task_mempolicy(priv);
+	rcu_read_lock();
+	vma = mas_find(&mas, 0);
+
+	if (unlikely(!vma))
+		goto empty_set;
 
-	for (vma = priv->mm->mmap; vma;) {
+	vma_start = vma->vm_start;
+	do {
 		smap_gather_stats(vma, &mss, 0);
 		last_vma_end = vma->vm_end;
 
@@ -872,12 +877,15 @@ static int show_smaps_rollup(struct seq_file *m, void *v)
 		 * access it for write request.
 		 */
 		if (mmap_lock_is_contended(mm)) {
+			rcu_read_unlock();
+			mas_pause(&mas);
 			mmap_read_unlock(mm);
 			ret = mmap_read_lock_killable(mm);
 			if (ret) {
 				release_task_mempolicy(priv);
 				goto out_put_mm;
 			}
+			rcu_read_lock();
 
 			/*
 			 * After dropping the lock, there are four cases to
@@ -915,7 +923,7 @@ static int show_smaps_rollup(struct seq_file *m, void *v)
 			 *    contains last_vma_end.
 			 *    Iterate VMA' from last_vma_end.
 			 */
-			vma = find_vma(mm, last_vma_end - 1);
+			vma = mas_find(&mas, ULONG_MAX);
 			/* Case 3 above */
 			if (!vma)
 				break;
@@ -929,16 +937,16 @@ static int show_smaps_rollup(struct seq_file *m, void *v)
 				smap_gather_stats(vma, &mss, last_vma_end);
 		}
 		/* Case 2 above */
-		vma = vma->vm_next;
-	}
+	} while ((vma = mas_find(&mas, ULONG_MAX)) != NULL);
 
-	show_vma_header_prefix(m, priv->mm->mmap->vm_start,
-			       last_vma_end, 0, 0, 0, 0);
+empty_set:
+	show_vma_header_prefix(m, vma_start, last_vma_end, 0, 0, 0, 0);
 	seq_pad(m, ' ');
 	seq_puts(m, "[rollup]\n");
 
 	__show_smap(m, &mss, true);
 
+	rcu_read_unlock();
 	release_task_mempolicy(priv);
 	mmap_read_unlock(mm);
 
@@ -1226,6 +1234,7 @@ static ssize_t clear_refs_write(struct file *file, const char __user *buf,
 		return -ESRCH;
 	mm = get_task_mm(task);
 	if (mm) {
+		MA_STATE(mas, &mm->mm_mt, 0, 0);
 		struct mmu_notifier_range range;
 		struct clear_refs_private cp = {
 			.type = type,
@@ -1245,19 +1254,21 @@ static ssize_t clear_refs_write(struct file *file, const char __user *buf,
 		}
 
 		if (type == CLEAR_REFS_SOFT_DIRTY) {
-			for (vma = mm->mmap; vma; vma = vma->vm_next) {
+			mas_lock(&mas);
+			mas_for_each(&mas, vma, ULONG_MAX) {
 				if (!(vma->vm_flags & VM_SOFTDIRTY))
 					continue;
 				vma->vm_flags &= ~VM_SOFTDIRTY;
 				vma_set_page_prot(vma);
 			}
+			mas_unlock(&mas);
 
 			inc_tlb_flush_pending(mm);
 			mmu_notifier_range_init(&range, MMU_NOTIFY_SOFT_DIRTY,
 						0, NULL, mm, 0, -1UL);
 			mmu_notifier_invalidate_range_start(&range);
 		}
-		walk_page_range(mm, 0, mm->highest_vm_end, &clear_refs_walk_ops,
+		walk_page_range(mm, 0, -1, &clear_refs_walk_ops,
 				&cp);
 		if (type == CLEAR_REFS_SOFT_DIRTY) {
 			mmu_notifier_invalidate_range_end(&range);
Signature · 1 line
2.30.2
#45 lore raw

PATCH v2 38/61 fs/userfaultfd: Stop using vma linked list.

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Don't use the mm_struct linked list or the vma->vm_next in prep for removal

---
 fs/userfaultfd.c | 34 +++++++++++++++++++++++++++-------
 1 file changed, 27 insertions(+), 7 deletions(-)
fs/userfaultfd.c +27 -7
index 003f0d31743e..bd181f922999 100644
@@ -606,14 +606,18 @@ static void userfaultfd_event_wait_completion(struct userfaultfd_ctx *ctx,
 	if (release_new_ctx) {
 		struct vm_area_struct *vma;
 		struct mm_struct *mm = release_new_ctx->mm;
+		MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 		/* the various vma->vm_userfaultfd_ctx still points to it */
 		mmap_write_lock(mm);
-		for (vma = mm->mmap; vma; vma = vma->vm_next)
+		mas_lock(&mas);
+		mas_for_each(&mas, vma, ULONG_MAX) {
 			if (vma->vm_userfaultfd_ctx.ctx == release_new_ctx) {
 				vma->vm_userfaultfd_ctx = NULL_VM_UFFD_CTX;
 				vma->vm_flags &= ~__VM_UFFD_FLAGS;
 			}
+		}
+		mas_unlock(&mas);
 		mmap_write_unlock(mm);
 
 		userfaultfd_ctx_put(release_new_ctx);
@@ -798,7 +802,10 @@ int userfaultfd_unmap_prep(struct vm_area_struct *vma,
 			   unsigned long start, unsigned long end,
 			   struct list_head *unmaps)
 {
-	for ( ; vma && vma->vm_start < end; vma = vma->vm_next) {
+	MA_STATE(mas, &vma->vm_mm->mm_mt, vma->vm_start, vma->vm_start);
+
+	rcu_read_lock();
+	mas_for_each(&mas, vma, end) {
 		struct userfaultfd_unmap_ctx *unmap_ctx;
 		struct userfaultfd_ctx *ctx = vma->vm_userfaultfd_ctx.ctx;
 
@@ -817,6 +824,7 @@ int userfaultfd_unmap_prep(struct vm_area_struct *vma,
 		unmap_ctx->end = end;
 		list_add_tail(&unmap_ctx->list, unmaps);
 	}
+	rcu_read_unlock();
 
 	return 0;
 }
@@ -848,6 +856,7 @@ static int userfaultfd_release(struct inode *inode, struct file *file)
 	/* len == 0 means wake all */
 	struct userfaultfd_wake_range range = { .len = 0, };
 	unsigned long new_flags;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	WRITE_ONCE(ctx->released, true);
 
@@ -863,9 +872,11 @@ static int userfaultfd_release(struct inode *inode, struct file *file)
 	 * taking the mmap_lock for writing.
 	 */
 	mmap_write_lock(mm);
+	mas_lock(&mas);
 	prev = NULL;
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		cond_resched();
+
 		BUG_ON(!!vma->vm_userfaultfd_ctx.ctx ^
 		       !!(vma->vm_flags & __VM_UFFD_FLAGS));
 		if (vma->vm_userfaultfd_ctx.ctx != ctx) {
@@ -885,6 +896,7 @@ static int userfaultfd_release(struct inode *inode, struct file *file)
 		vma->vm_flags = new_flags;
 		vma->vm_userfaultfd_ctx = NULL_VM_UFFD_CTX;
 	}
+	mas_unlock(&mas);
 	mmap_write_unlock(mm);
 	mmput(mm);
 wakeup:
@@ -1281,6 +1293,7 @@ static int userfaultfd_register(struct userfaultfd_ctx *ctx,
 	bool found;
 	bool basic_ioctls;
 	unsigned long start, end, vma_end;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	user_uffdio_register = (struct uffdio_register __user *) arg;
 
@@ -1323,6 +1336,7 @@ static int userfaultfd_register(struct userfaultfd_ctx *ctx,
 		goto out;
 
 	mmap_write_lock(mm);
+	mas_lock(&mas);
 	vma = find_vma_prev(mm, start, &prev);
 	if (!vma)
 		goto out_unlock;
@@ -1348,7 +1362,8 @@ static int userfaultfd_register(struct userfaultfd_ctx *ctx,
 	 */
 	found = false;
 	basic_ioctls = false;
-	for (cur = vma; cur && cur->vm_start < end; cur = cur->vm_next) {
+	mas_set(&mas, vma->vm_start);
+	mas_for_each(&mas, cur, end) {
 		cond_resched();
 
 		BUG_ON(!!cur->vm_userfaultfd_ctx.ctx ^
@@ -1466,9 +1481,10 @@ static int userfaultfd_register(struct userfaultfd_ctx *ctx,
 	skip:
 		prev = vma;
 		start = vma->vm_end;
-		vma = vma->vm_next;
+		vma = vma_next(mm, vma);
 	} while (vma && vma->vm_start < end);
 out_unlock:
+	mas_unlock(&mas);
 	mmap_write_unlock(mm);
 	mmput(mm);
 	if (!ret) {
@@ -1511,6 +1527,7 @@ static int userfaultfd_unregister(struct userfaultfd_ctx *ctx,
 	bool found;
 	unsigned long start, end, vma_end;
 	const void __user *buf = (void __user *)arg;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	ret = -EFAULT;
 	if (copy_from_user(&uffdio_unregister, buf, sizeof(uffdio_unregister)))
@@ -1529,6 +1546,7 @@ static int userfaultfd_unregister(struct userfaultfd_ctx *ctx,
 		goto out;
 
 	mmap_write_lock(mm);
+	mas_lock(&mas);
 	vma = find_vma_prev(mm, start, &prev);
 	if (!vma)
 		goto out_unlock;
@@ -1554,7 +1572,8 @@ static int userfaultfd_unregister(struct userfaultfd_ctx *ctx,
 	 */
 	found = false;
 	ret = -EINVAL;
-	for (cur = vma; cur && cur->vm_start < end; cur = cur->vm_next) {
+	mas_set(&mas, vma->vm_start);
+	mas_for_each(&mas, cur, end) {
 		cond_resched();
 
 		BUG_ON(!!cur->vm_userfaultfd_ctx.ctx ^
@@ -1640,9 +1659,10 @@ static int userfaultfd_unregister(struct userfaultfd_ctx *ctx,
 	skip:
 		prev = vma;
 		start = vma->vm_end;
-		vma = vma->vm_next;
+		vma = vma_next(mm, vma);
 	} while (vma && vma->vm_start < end);
 out_unlock:
+	mas_unlock(&mas);
 	mmap_write_unlock(mm);
 	mmput(mm);
 out:
Signature · 1 line
2.30.2
#46 lore raw

PATCH v2 39/61 ipc/shm: Stop using the vma linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

When searching for a VMA, a maple state can be used instead of the linked list in the mm_struct

---
 ipc/shm.c | 13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)
ipc/shm.c +7 -6
index ab749be6d8b7..ed6628679679 100644
@@ -1631,6 +1631,7 @@ long ksys_shmdt(char __user *shmaddr)
 	loff_t size = 0;
 	struct file *file;
 	struct vm_area_struct *next;
+	MA_STATE(mas, &mm->mm_mt, addr, addr);
 #endif
 
 	if (addr & ~PAGE_MASK)
@@ -1660,11 +1661,11 @@ long ksys_shmdt(char __user *shmaddr)
 	 * match the usual checks anyway. So assume all vma's are
 	 * above the starting address given.
 	 */
-	vma = find_vma(mm, addr);
 
 #ifdef CONFIG_MMU
+	vma = mas_find(&mas, ULONG_MAX);
 	while (vma) {
-		next = vma->vm_next;
+		next = mas_find(&mas, ULONG_MAX);
 
 		/*
 		 * Check if the starting address would match, i.e. it's
@@ -1703,21 +1704,21 @@ long ksys_shmdt(char __user *shmaddr)
 	 */
 	size = PAGE_ALIGN(size);
 	while (vma && (loff_t)(vma->vm_end - addr) <= size) {
-		next = vma->vm_next;
-
 		/* finding a matching vma now does not alter retval */
 		if ((vma->vm_ops == &shm_vm_ops) &&
 		    ((vma->vm_start - addr)/PAGE_SIZE == vma->vm_pgoff) &&
 		    (vma->vm_file == file))
 			do_munmap(mm, vma->vm_start, vma->vm_end - vma->vm_start, NULL);
-		vma = next;
+
+		vma = mas_find(&mas, addr + size - 1);
 	}
 
 #else	/* CONFIG_MMU */
+	vma = mas_walk(&mas);
 	/* under NOMMU conditions, the exact address to be destroyed must be
 	 * given
 	 */
-	if (vma && vma->vm_start == addr && vma->vm_ops == &shm_vm_ops) {
+	if (vma && vma->vm_ops == &shm_vm_ops) {
 		do_munmap(mm, vma->vm_start, vma->vm_end - vma->vm_start, NULL);
 		retval = 0;
 	}
Signature · 1 line
2.30.2
#47 lore raw

PATCH v2 40/61 kernel/acct: Use maple tree iterators instead of linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 kernel/acct.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)
kernel/acct.c +4 -4
index 23a7ab8e6cbc..32343edc7330 100644
@@ -534,16 +534,16 @@ void acct_collect(long exitcode, int group_dead)
 	struct pacct_struct *pacct = &current->signal->pacct;
 	u64 utime, stime;
 	unsigned long vsize = 0;
+	MA_STATE(mas, &current->mm->mm_mt, 0, 0);
 
 	if (group_dead && current->mm) {
 		struct vm_area_struct *vma;
 
 		mmap_read_lock(current->mm);
-		vma = current->mm->mmap;
-		while (vma) {
+		rcu_read_lock();
+		mas_for_each(&mas, vma, ULONG_MAX)
 			vsize += vma->vm_end - vma->vm_start;
-			vma = vma->vm_next;
-		}
+		rcu_read_unlock();
 		mmap_read_unlock(current->mm);
 	}
 
Signature · 1 line
2.30.2
#48 lore raw

PATCH v2 41/61 kernel/events/core: Use maple tree iterators instead of linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 kernel/events/core.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)
kernel/events/core.c +5 -2
index 1cb1f9b8392e..3ac0918d8e32 100644
@@ -10161,14 +10161,17 @@ static void perf_addr_filter_apply(struct perf_addr_filter *filter,
 				   struct perf_addr_filter_range *fr)
 {
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	rcu_read_lock();
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		if (!vma->vm_file)
 			continue;
 
 		if (perf_addr_filter_vma_adjust(filter, vma, fr))
-			return;
+			break;
 	}
+	rcu_read_unlock();
 }
 
 /*
Signature · 1 line
2.30.2
#49 lore raw

PATCH v2 42/61 kernel/events/uprobes: Use maple tree iterators instead of linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 kernel/events/uprobes.c | 25 ++++++++++++++++++-------
 1 file changed, 18 insertions(+), 7 deletions(-)
kernel/events/uprobes.c +18 -7
index 6357c3580d07..40f5a07d8f16 100644
@@ -356,13 +356,16 @@ static bool valid_ref_ctr_vma(struct uprobe *uprobe,
 static struct vm_area_struct *
 find_ref_ctr_vma(struct uprobe *uprobe, struct mm_struct *mm)
 {
-	struct vm_area_struct *tmp;
+	struct vm_area_struct *tmp = NULL;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
-	for (tmp = mm->mmap; tmp; tmp = tmp->vm_next)
+	rcu_read_lock();
+	mas_for_each(&mas, tmp, ULONG_MAX)
 		if (valid_ref_ctr_vma(uprobe, tmp))
-			return tmp;
+			break;
+	rcu_read_unlock();
 
-	return NULL;
+	return tmp;
 }
 
 static int
@@ -1239,9 +1242,10 @@ static int unapply_uprobe(struct uprobe *uprobe, struct mm_struct *mm)
 {
 	struct vm_area_struct *vma;
 	int err = 0;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	mmap_read_lock(mm);
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		unsigned long vaddr;
 		loff_t offset;
 
@@ -1990,8 +1994,10 @@ bool uprobe_deny_signal(void)
 static void mmf_recalc_uprobes(struct mm_struct *mm)
 {
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	rcu_read_lock();
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		if (!valid_vma(vma, false))
 			continue;
 		/*
@@ -2001,10 +2007,15 @@ static void mmf_recalc_uprobes(struct mm_struct *mm)
 		 * Or this uprobe can be filtered out.
 		 */
 		if (vma_has_uprobes(vma, vma->vm_start, vma->vm_end))
-			return;
+			goto completed;
 	}
+	rcu_read_unlock();
 
 	clear_bit(MMF_HAS_UPROBES, &mm->flags);
+	return;
+
+completed:
+	rcu_read_unlock();
 }
 
 static int is_trap_at_addr(struct mm_struct *mm, unsigned long vaddr)
Signature · 1 line
2.30.2
#50 lore raw

PATCH v2 43/61 kernel/sched/fair: Use maple tree iterators instead of linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 kernel/sched/fair.c | 14 +++++++++++---
 1 file changed, 11 insertions(+), 3 deletions(-)
kernel/sched/fair.c +11 -3
index 44e44c235f1f..154fce44b38a 100644
@@ -2688,6 +2688,7 @@ static void task_numa_work(struct callback_head *work)
 	unsigned long start, end;
 	unsigned long nr_pte_updates = 0;
 	long pages, virtpages;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	SCHED_WARN_ON(p != container_of(work, struct task_struct, numa_work));
 
@@ -2740,13 +2741,17 @@ static void task_numa_work(struct callback_head *work)
 
 	if (!mmap_read_trylock(mm))
 		return;
-	vma = find_vma(mm, start);
+
+	rcu_read_lock();
+	mas_set(&mas, start);
+	vma = mas_find(&mas, ULONG_MAX);
 	if (!vma) {
 		reset_ptenuma_scan(p);
 		start = 0;
-		vma = mm->mmap;
+		mas_set(&mas, start);
 	}
-	for (; vma; vma = vma->vm_next) {
+
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		if (!vma_migratable(vma) || !vma_policy_mof(vma) ||
 			is_vm_hugetlb_page(vma) || (vma->vm_flags & VM_MIXEDMAP)) {
 			continue;
@@ -2791,7 +2796,9 @@ static void task_numa_work(struct callback_head *work)
 			if (pages <= 0 || virtpages <= 0)
 				goto out;
 
+			rcu_read_unlock();
 			cond_resched();
+			rcu_read_lock();
 		} while (end != vma->vm_end);
 	}
 
@@ -2806,6 +2813,7 @@ static void task_numa_work(struct callback_head *work)
 		mm->numa_scan_offset = start;
 	else
 		reset_ptenuma_scan(p);
+	rcu_read_unlock();
 	mmap_read_unlock(mm);
 
 	/*
Signature · 1 line
2.30.2
#51 lore raw

PATCH v2 44/61 kernel/sys: Use maple tree iterators instead of linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 kernel/sys.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)
kernel/sys.c +5 -1
index 6ec50924b517..402d5da903fe 100644
@@ -1876,9 +1876,11 @@ static int prctl_set_mm_exe_file(struct mm_struct *mm, unsigned int fd)
 	err = -EBUSY;
 	if (exe_file) {
 		struct vm_area_struct *vma;
+		MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 		mmap_read_lock(mm);
-		for (vma = mm->mmap; vma; vma = vma->vm_next) {
+		rcu_read_lock();
+		mas_for_each(&mas, vma, ULONG_MAX) {
 			if (!vma->vm_file)
 				continue;
 			if (path_equal(&vma->vm_file->f_path,
@@ -1886,6 +1888,7 @@ static int prctl_set_mm_exe_file(struct mm_struct *mm, unsigned int fd)
 				goto exit_err;
 		}
 
+		rcu_read_unlock();
 		mmap_read_unlock(mm);
 		fput(exe_file);
 	}
@@ -1900,6 +1903,7 @@ static int prctl_set_mm_exe_file(struct mm_struct *mm, unsigned int fd)
 	fdput(exe);
 	return err;
 exit_err:
+	rcu_read_unlock();
 	mmap_read_unlock(mm);
 	fput(exe_file);
 	goto exit;
Signature · 1 line
2.30.2
#52 lore raw

PATCH v2 45/61 arch/um/kernel/tlb: Stop using linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 arch/um/kernel/tlb.c | 16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)
arch/um/kernel/tlb.c +8 -8
index bc38f79ca3a3..0cbbebad70a0 100644
@@ -584,21 +584,21 @@ void flush_tlb_mm_range(struct mm_struct *mm, unsigned long start,
 
 void flush_tlb_mm(struct mm_struct *mm)
 {
-	struct vm_area_struct *vma = mm->mmap;
+	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
-	while (vma != NULL) {
+	/* Must hold mm_mt lock already */
+	mas_for_each(&mas, vma, ULONG_MAX)
 		fix_range(mm, vma->vm_start, vma->vm_end, 0);
-		vma = vma->vm_next;
-	}
 }
 
 void force_flush_all(void)
 {
 	struct mm_struct *mm = current->mm;
-	struct vm_area_struct *vma = mm->mmap;
+	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
-	while (vma != NULL) {
+	/* Must hold mm_mt lock already */
+	mas_for_each(&mas, vma, ULONG_MAX)
 		fix_range(mm, vma->vm_start, vma->vm_end, 1);
-		vma = vma->vm_next;
-	}
 }
Signature · 1 line
2.30.2
#53 lore raw

PATCH v2 46/61 bpf: Remove VMA linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Use vma_next() and remove reference to the start of the linked list

---
 kernel/bpf/task_iter.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)
kernel/bpf/task_iter.c +3 -3
index b68cb5d6d6eb..c1c71adc7c1a 100644
@@ -400,10 +400,10 @@ task_vma_seq_get_next(struct bpf_iter_seq_task_vma_info *info)
 
 	switch (op) {
 	case task_vma_iter_first_vma:
-		curr_vma = curr_task->mm->mmap;
+		curr_vma = find_vma(curr_task->mm, 0);
 		break;
 	case task_vma_iter_next_vma:
-		curr_vma = curr_vma->vm_next;
+		curr_vma = vma_next(curr_vma->vm_mm, curr_vma);
 		break;
 	case task_vma_iter_find_vma:
 		/* We dropped mmap_lock so it is necessary to use find_vma
@@ -417,7 +417,7 @@ task_vma_seq_get_next(struct bpf_iter_seq_task_vma_info *info)
 		if (curr_vma &&
 		    curr_vma->vm_start == info->prev_vm_start &&
 		    curr_vma->vm_end == info->prev_vm_end)
-			curr_vma = curr_vma->vm_next;
+			curr_vma = vma_next(curr_vma->vm_mm, curr_vma);
 		break;
 	}
 	if (!curr_vma) {
Signature · 1 line
2.30.2
#54 lore raw

PATCH v2 47/61 mm/gup: Use maple tree navigation instead of linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 mm/gup.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)
mm/gup.c +3 -4
index 2630ed1bb4f4..7a34765d28d8 100644
@@ -1580,7 +1580,6 @@ int __mm_populate(unsigned long start, unsigned long len, int ignore_errors)
 	long ret = 0;
 
 	end = start + len;
-
 	for (nstart = start; nstart < end; nstart = nend) {
 		/*
 		 * We want to fault in pages for [nstart; end) address range.
@@ -1589,10 +1588,10 @@ int __mm_populate(unsigned long start, unsigned long len, int ignore_errors)
 		if (!locked) {
 			locked = 1;
 			mmap_read_lock(mm);
-			vma = find_vma(mm, nstart);
+			vma = find_vma_intersection(mm, start, end);
 		} else if (nstart >= vma->vm_end)
-			vma = vma->vm_next;
-		if (!vma || vma->vm_start >= end)
+			vma = vma_next(mm, vma);
+		if (!vma)
 			break;
 		/*
 		 * Set [nstart; nend) to intersection of desired address
Signature · 1 line
2.30.2
#55 lore raw

PATCH v2 48/61 mm/khugepaged: Use maple tree iterators instead of vma linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 mm/huge_memory.c | 4 ++--
 mm/khugepaged.c  | 9 ++++++---
 2 files changed, 8 insertions(+), 5 deletions(-)
mm/huge_memory.c +2 -2
index ade81c123d87..b36bea1d5b5d 100644
@@ -2270,11 +2270,11 @@ void vma_adjust_trans_huge(struct vm_area_struct *vma,
 	split_huge_pmd_if_needed(vma, end);
 
 	/*
-	 * If we're also updating the vma->vm_next->vm_start,
+	 * If we're also updating the vma_next(vma)->vm_start,
 	 * check if we need to split it.
 	 */
 	if (adjust_next > 0) {
-		struct vm_area_struct *next = vma->vm_next;
+		struct vm_area_struct *next = vma_next(vma->vm_mm, vma);
 		unsigned long nstart = next->vm_start;
 		nstart += adjust_next;
 		split_huge_pmd_if_needed(next, nstart);
mm/khugepaged.c +6 -3
index 3a43610141bb..27b7f3521d9c 100644
@@ -2075,6 +2075,7 @@ static unsigned int khugepaged_scan_mm_slot(unsigned int pages,
 	struct mm_struct *mm;
 	struct vm_area_struct *vma;
 	int progress = 0;
+	unsigned long address;
 
 	VM_BUG_ON(!pages);
 	lockdep_assert_held(&khugepaged_mm_lock);
@@ -2098,11 +2099,13 @@ static unsigned int khugepaged_scan_mm_slot(unsigned int pages,
 	vma = NULL;
 	if (unlikely(!mmap_read_trylock(mm)))
 		goto breakouterloop_mmap_lock;
-	if (likely(!khugepaged_test_exit(mm)))
-		vma = find_vma(mm, khugepaged_scan.address);
 
 	progress++;
-	for (; vma; vma = vma->vm_next) {
+	if (unlikely(khugepaged_test_exit(mm)))
+		goto breakouterloop_mmap_lock;
+
+	address = khugepaged_scan.address;
+	mt_for_each(&mm->mm_mt, vma, address, ULONG_MAX) {
 		unsigned long hstart, hend;
 
 		cond_resched();
Signature · 1 line
2.30.2
#56 lore raw

PATCH v2 49/61 mm/ksm: Use maple tree iterators instead of vma linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 mm/ksm.c | 26 +++++++++++++++++++-------
 1 file changed, 19 insertions(+), 7 deletions(-)
mm/ksm.c +19 -7
index 08092e6f0b73..1e2218a81bfc 100644
@@ -975,11 +975,14 @@ static int unmerge_and_remove_all_rmap_items(void)
 						struct mm_slot, mm_list);
 	spin_unlock(&ksm_mmlist_lock);
 
-	for (mm_slot = ksm_scan.mm_slot;
-			mm_slot != &ksm_mm_head; mm_slot = ksm_scan.mm_slot) {
+	for (mm_slot = ksm_scan.mm_slot; mm_slot != &ksm_mm_head;
+	     mm_slot = ksm_scan.mm_slot) {
+		MA_STATE(mas, &mm_slot->mm->mm_mt, 0, 0);
+
 		mm = mm_slot->mm;
 		mmap_read_lock(mm);
-		for (vma = mm->mmap; vma; vma = vma->vm_next) {
+		rcu_read_lock();
+		mas_for_each(&mas, vma, ULONG_MAX) {
 			if (ksm_test_exit(mm))
 				break;
 			if (!(vma->vm_flags & VM_MERGEABLE) || !vma->anon_vma)
@@ -991,6 +994,7 @@ static int unmerge_and_remove_all_rmap_items(void)
 		}
 
 		remove_trailing_rmap_items(&mm_slot->rmap_list);
+		rcu_read_unlock();
 		mmap_read_unlock(mm);
 
 		spin_lock(&ksm_mmlist_lock);
@@ -1014,6 +1018,7 @@ static int unmerge_and_remove_all_rmap_items(void)
 	return 0;
 
 error:
+	rcu_read_unlock();
 	mmap_read_unlock(mm);
 	spin_lock(&ksm_mmlist_lock);
 	ksm_scan.mm_slot = &ksm_mm_head;
@@ -2228,6 +2233,7 @@ static struct rmap_item *scan_get_next_rmap_item(struct page **page)
 	struct vm_area_struct *vma;
 	struct rmap_item *rmap_item;
 	int nid;
+	MA_STATE(mas, NULL, 0, 0);
 
 	if (list_empty(&ksm_mm_head.mm_list))
 		return NULL;
@@ -2285,13 +2291,15 @@ static struct rmap_item *scan_get_next_rmap_item(struct page **page)
 	}
 
 	mm = slot->mm;
+	mas.tree = &mm->mm_mt;
+
 	mmap_read_lock(mm);
+	rcu_read_lock();
 	if (ksm_test_exit(mm))
-		vma = NULL;
-	else
-		vma = find_vma(mm, ksm_scan.address);
+		goto no_vmas;
 
-	for (; vma; vma = vma->vm_next) {
+	mas_set(&mas, ksm_scan.address);
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		if (!(vma->vm_flags & VM_MERGEABLE))
 			continue;
 		if (ksm_scan.address < vma->vm_start)
@@ -2319,6 +2327,7 @@ static struct rmap_item *scan_get_next_rmap_item(struct page **page)
 					ksm_scan.address += PAGE_SIZE;
 				} else
 					put_page(*page);
+				rcu_read_unlock();
 				mmap_read_unlock(mm);
 				return rmap_item;
 			}
@@ -2329,6 +2338,7 @@ static struct rmap_item *scan_get_next_rmap_item(struct page **page)
 	}
 
 	if (ksm_test_exit(mm)) {
+no_vmas:
 		ksm_scan.address = 0;
 		ksm_scan.rmap_list = &slot->rmap_list;
 	}
@@ -2357,9 +2367,11 @@ static struct rmap_item *scan_get_next_rmap_item(struct page **page)
 
 		free_mm_slot(slot);
 		clear_bit(MMF_VM_MERGEABLE, &mm->flags);
+		rcu_read_unlock();
 		mmap_read_unlock(mm);
 		mmdrop(mm);
 	} else {
+		rcu_read_unlock();
 		mmap_read_unlock(mm);
 		/*
 		 * mmap_read_unlock(mm) first because after
Signature · 1 line
2.30.2
#57 lore raw

PATCH v2 50/61 mm/madvise: Use vma_next instead of vma linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 mm/madvise.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
mm/madvise.c +1 -1
index 0734db8d53a7..3a6fe7e1b080 100644
@@ -1209,7 +1209,7 @@ int do_madvise(struct mm_struct *mm, unsigned long start, size_t len_in, int beh
 		if (start >= end)
 			goto out;
 		if (prev)
-			vma = prev->vm_next;
+			vma = vma_next(mm, prev);
 		else	/* madvise_remove dropped mmap_lock */
 			vma = find_vma(mm, start);
 	}
Signature · 1 line
2.30.2
#58 lore raw

PATCH v2 51/61 mm/memcontrol: Stop using mm->highest_vm_end

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 mm/memcontrol.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)
mm/memcontrol.c +2 -4
index 3e7c205a1852..943e8554a4bb 100644
@@ -5830,7 +5830,7 @@ static unsigned long mem_cgroup_count_precharge(struct mm_struct *mm)
 	unsigned long precharge;
 
 	mmap_read_lock(mm);
-	walk_page_range(mm, 0, mm->highest_vm_end, &precharge_walk_ops, NULL);
+	walk_page_range(mm, 0, -1, &precharge_walk_ops, NULL);
 	mmap_read_unlock(mm);
 
 	precharge = mc.precharge;
@@ -6128,9 +6128,7 @@ static void mem_cgroup_move_charge(void)
 	 * When we have consumed all precharges and failed in doing
 	 * additional charge, the page walk just aborts.
 	 */
-	walk_page_range(mc.mm, 0, mc.mm->highest_vm_end, &charge_walk_ops,
-			NULL);
-
+	walk_page_range(mc.mm, 0, -1, &charge_walk_ops, NULL);
 	mmap_read_unlock(mc.mm);
 	atomic_dec(&mc.from->moving_account);
 }
Signature · 1 line
2.30.2
#59 lore raw

PATCH v2 52/61 mm/mempolicy: Use maple tree iterators instead of vma linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 mm/mempolicy.c | 41 +++++++++++++++++++++++++----------------
 1 file changed, 25 insertions(+), 16 deletions(-)
mm/mempolicy.c +25 -16
index 9d3afa015fac..c8ded4c7dc93 100644
@@ -377,10 +377,13 @@ void mpol_rebind_task(struct task_struct *tsk, const nodemask_t *new)
 void mpol_rebind_mm(struct mm_struct *mm, nodemask_t *new)
 {
 	struct vm_area_struct *vma;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	mmap_write_lock(mm);
-	for (vma = mm->mmap; vma; vma = vma->vm_next)
+	mas_lock(&mas);
+	mas_for_each(&mas, vma, ULONG_MAX)
 		mpol_rebind_policy(vma->vm_policy, new);
+	mas_unlock(&mas);
 	mmap_write_unlock(mm);
 }
 
@@ -652,7 +655,7 @@ static unsigned long change_prot_numa(struct vm_area_struct *vma,
 static int queue_pages_test_walk(unsigned long start, unsigned long end,
 				struct mm_walk *walk)
 {
-	struct vm_area_struct *vma = walk->vma;
+	struct vm_area_struct *next, *vma = walk->vma;
 	struct queue_pages *qp = walk->private;
 	unsigned long endvma = vma->vm_end;
 	unsigned long flags = qp->flags;
@@ -667,9 +670,10 @@ static int queue_pages_test_walk(unsigned long start, unsigned long end,
 			/* hole at head side of range */
 			return -EFAULT;
 	}
+	next = vma_next(vma->vm_mm, vma);
 	if (!(flags & MPOL_MF_DISCONTIG_OK) &&
 		((vma->vm_end < qp->end) &&
-		(!vma->vm_next || vma->vm_end < vma->vm_next->vm_start)))
+		(!next || vma->vm_end < next->vm_start)))
 		/* hole at middle or tail of range */
 		return -EFAULT;
 
@@ -783,28 +787,28 @@ static int vma_replace_policy(struct vm_area_struct *vma,
 static int mbind_range(struct mm_struct *mm, unsigned long start,
 		       unsigned long end, struct mempolicy *new_pol)
 {
-	struct vm_area_struct *next;
 	struct vm_area_struct *prev;
 	struct vm_area_struct *vma;
 	int err = 0;
 	pgoff_t pgoff;
 	unsigned long vmstart;
 	unsigned long vmend;
+	unsigned long index = start;
 
-	vma = find_vma(mm, start);
+	rcu_read_lock();
+	vma = find_vma_intersection(mm, start, end);
 	VM_BUG_ON(!vma);
 
-	prev = vma->vm_prev;
+	prev = vma_prev(mm, vma);
 	if (start > vma->vm_start)
 		prev = vma;
 
-	for (; vma && vma->vm_start < end; prev = vma, vma = next) {
-		next = vma->vm_next;
+	mt_for_each(&mm->mm_mt, vma, index, end - 1) {
 		vmstart = max(start, vma->vm_start);
 		vmend   = min(end, vma->vm_end);
 
 		if (mpol_equal(vma_policy(vma), new_pol))
-			continue;
+			goto next;
 
 		pgoff = vma->vm_pgoff +
 			((vmstart - vma->vm_start) >> PAGE_SHIFT);
@@ -813,7 +817,6 @@ static int mbind_range(struct mm_struct *mm, unsigned long start,
 				 new_pol, vma->vm_userfaultfd_ctx);
 		if (prev) {
 			vma = prev;
-			next = vma->vm_next;
 			if (mpol_equal(vma_policy(vma), new_pol))
 				continue;
 			/* vma_merge() joined vma && vma->next, case 8 */
@@ -829,13 +832,16 @@ static int mbind_range(struct mm_struct *mm, unsigned long start,
 			if (err)
 				goto out;
 		}
- replace:
+replace:
 		err = vma_replace_policy(vma, new_pol);
 		if (err)
 			goto out;
+next:
+		prev = vma;
 	}
 
- out:
+out:
+	rcu_read_unlock();
 	return err;
 }
 
@@ -1063,6 +1069,7 @@ static int migrate_to_node(struct mm_struct *mm, int source, int dest,
 			   int flags)
 {
 	nodemask_t nmask;
+	struct vm_area_struct *vma;
 	LIST_HEAD(pagelist);
 	int err = 0;
 	struct migration_target_control mtc = {
@@ -1078,8 +1085,9 @@ static int migrate_to_node(struct mm_struct *mm, int source, int dest,
 	 * need migration.  Between passing in the full user address
 	 * space range and MPOL_MF_DISCONTIG_OK, this call can not fail.
 	 */
+	vma = find_vma(mm, 0);
 	VM_BUG_ON(!(flags & (MPOL_MF_MOVE | MPOL_MF_MOVE_ALL)));
-	queue_pages_range(mm, mm->mmap->vm_start, mm->task_size, &nmask,
+	queue_pages_range(mm, vma->vm_start, mm->task_size, &nmask,
 			flags | MPOL_MF_DISCONTIG_OK, &pagelist);
 
 	if (!list_empty(&pagelist)) {
@@ -1208,14 +1216,15 @@ static struct page *new_page(struct page *page, unsigned long start)
 {
 	struct vm_area_struct *vma;
 	unsigned long address;
+	MA_STATE(mas, &current->mm->mm_mt, start, start);
 
-	vma = find_vma(current->mm, start);
-	while (vma) {
+	rcu_read_lock();
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		address = page_address_in_vma(page, vma);
 		if (address != -EFAULT)
 			break;
-		vma = vma->vm_next;
 	}
+	rcu_read_unlock();
 
 	if (PageHuge(page)) {
 		return alloc_huge_page_vma(page_hstate(compound_head(page)),
Signature · 1 line
2.30.2
#60 lore raw

PATCH v2 53/61 mm/mlock: Use maple tree iterators instead of vma linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 mm/mlock.c | 21 +++++++++++----------
 1 file changed, 11 insertions(+), 10 deletions(-)
mm/mlock.c +11 -10
index e263d62ae2d0..a91ea32fb219 100644
@@ -563,6 +563,7 @@ static int apply_vma_lock_flags(unsigned long start, size_t len,
 	unsigned long nstart, end, tmp;
 	struct vm_area_struct *vma, *prev;
 	int error;
+	MA_STATE(mas, &current->mm->mm_mt, start, start);
 
 	VM_BUG_ON(offset_in_page(start));
 	VM_BUG_ON(len != PAGE_ALIGN(len));
@@ -571,11 +572,11 @@ static int apply_vma_lock_flags(unsigned long start, size_t len,
 		return -EINVAL;
 	if (end == start)
 		return 0;
-	vma = find_vma(current->mm, start);
-	if (!vma || vma->vm_start > start)
+	vma = mas_walk(&mas);
+	if (!vma)
 		return -ENOMEM;
 
-	prev = vma->vm_prev;
+	prev = mas_prev(&mas, 0);
 	if (start > vma->vm_start)
 		prev = vma;
 
@@ -597,7 +598,7 @@ static int apply_vma_lock_flags(unsigned long start, size_t len,
 		if (nstart >= end)
 			break;
 
-		vma = prev->vm_next;
+		vma = vma_next(prev->vm_mm, prev);
 		if (!vma || vma->vm_start != nstart) {
 			error = -ENOMEM;
 			break;
@@ -618,15 +619,13 @@ static unsigned long count_mm_mlocked_page_nr(struct mm_struct *mm,
 {
 	struct vm_area_struct *vma;
 	unsigned long count = 0;
+	MA_STATE(mas, &mm->mm_mt, start, start);
 
 	if (mm == NULL)
 		mm = current->mm;
 
-	vma = find_vma(mm, start);
-	if (vma == NULL)
-		return 0;
-
-	for (; vma ; vma = vma->vm_next) {
+	rcu_read_lock();
+	mas_for_each(&mas, vma, start + len) {
 		if (start >= vma->vm_end)
 			continue;
 		if (start + len <=  vma->vm_start)
@@ -641,6 +640,7 @@ static unsigned long count_mm_mlocked_page_nr(struct mm_struct *mm,
 			count += vma->vm_end - vma->vm_start;
 		}
 	}
+	rcu_read_unlock();
 
 	return count >> PAGE_SHIFT;
 }
@@ -741,6 +741,7 @@ static int apply_mlockall_flags(int flags)
 {
 	struct vm_area_struct *vma, *prev = NULL;
 	vm_flags_t to_add = 0;
+	unsigned long addr = 0;
 
 	current->mm->def_flags &= VM_LOCKED_CLEAR_MASK;
 	if (flags & MCL_FUTURE) {
@@ -759,7 +760,7 @@ static int apply_mlockall_flags(int flags)
 			to_add |= VM_LOCKONFAULT;
 	}
 
-	for (vma = current->mm->mmap; vma ; vma = prev->vm_next) {
+	mt_for_each(&current->mm->mm_mt, vma, addr, ULONG_MAX) {
 		vm_flags_t newflags;
 
 		newflags = vma->vm_flags & VM_LOCKED_CLEAR_MASK;
Signature · 1 line
2.30.2
#61 lore raw

PATCH v2 54/61 mm/mprotect: Use maple tree navigation instead of vma linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 mm/mprotect.c | 13 +++++++++----
 1 file changed, 9 insertions(+), 4 deletions(-)
mm/mprotect.c +9 -4
index 883e2cc85cad..a4041d2c0dfb 100644
@@ -528,6 +528,7 @@ static int do_mprotect_pkey(unsigned long start, size_t len,
 	const int grows = prot & (PROT_GROWSDOWN|PROT_GROWSUP);
 	const bool rier = (current->personality & READ_IMPLIES_EXEC) &&
 				(prot & PROT_READ);
+	MA_STATE(mas, &current->mm->mm_mt, start, start);
 
 	start = untagged_addr(start);
 
@@ -559,11 +560,15 @@ static int do_mprotect_pkey(unsigned long start, size_t len,
 	if ((pkey != -1) && !mm_pkey_is_allocated(current->mm, pkey))
 		goto out;
 
-	vma = find_vma(current->mm, start);
+	rcu_read_lock();
+	vma = mas_find(&mas, ULONG_MAX);
 	error = -ENOMEM;
-	if (!vma)
+	if (!vma) {
+		rcu_read_unlock();
 		goto out;
-	prev = vma->vm_prev;
+	}
+	prev = mas_prev(&mas, 0);
+	rcu_read_unlock();
 	if (unlikely(grows & PROT_GROWSDOWN)) {
 		if (vma->vm_start >= end)
 			goto out;
@@ -644,7 +649,7 @@ static int do_mprotect_pkey(unsigned long start, size_t len,
 		if (nstart >= end)
 			goto out;
 
-		vma = prev->vm_next;
+		vma = vma_next(current->mm, prev);
 		if (!vma || vma->vm_start != nstart) {
 			error = -ENOMEM;
 			goto out;
Signature · 1 line
2.30.2
#62 lore raw

PATCH v2 55/61 mm/mremap: Use vma_next() instead of vma linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 mm/mremap.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
mm/mremap.c +4 -2
index f48ccfcf3217..b364d08673b4 100644
@@ -705,7 +705,7 @@ static unsigned long move_vma(struct vm_area_struct *vma,
 	if (excess) {
 		vma->vm_flags |= VM_ACCOUNT;
 		if (split)
-			vma->vm_next->vm_flags |= VM_ACCOUNT;
+			vma_next(mm, vma)->vm_flags |= VM_ACCOUNT;
 	}
 
 	return new_addr;
@@ -864,9 +864,11 @@ static unsigned long mremap_to(unsigned long addr, unsigned long old_len,
 static int vma_expandable(struct vm_area_struct *vma, unsigned long delta)
 {
 	unsigned long end = vma->vm_end + delta;
+	struct vm_area_struct *next;
 	if (end < vma->vm_end) /* overflow */
 		return 0;
-	if (vma->vm_next && vma->vm_next->vm_start < end) /* intersection */
+	next = vma_next(vma->vm_mm, vma);
+	if (next && next->vm_start < end) /* intersection */
 		return 0;
 	if (get_unmapped_area(NULL, vma->vm_start, end - vma->vm_start,
 			      0, MAP_FIXED) & ~PAGE_MASK)
Signature · 1 line
2.30.2
#63 lore raw

PATCH v2 56/61 mm/msync: Use vma_next() instead of vma linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 mm/msync.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
mm/msync.c +1 -1
index 137d1c104f3e..d5fcecc95829 100644
@@ -104,7 +104,7 @@ SYSCALL_DEFINE3(msync, unsigned long, start, size_t, len, int, flags)
 				error = 0;
 				goto out_unlock;
 			}
-			vma = vma->vm_next;
+			vma = vma_next(mm, vma);
 		}
 	}
 out_unlock:
Signature · 1 line
2.30.2
#64 lore raw

PATCH v2 57/61 mm/oom_kill: Use maple tree iterators instead of vma linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 mm/oom_kill.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)
mm/oom_kill.c +4 -1
index 431d38c3bba8..40a01f334735 100644
@@ -519,6 +519,7 @@ bool __oom_reap_task_mm(struct mm_struct *mm)
 {
 	struct vm_area_struct *vma;
 	bool ret = true;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	/*
 	 * Tell all users of get_user/copy_from_user etc... that the content
@@ -528,7 +529,8 @@ bool __oom_reap_task_mm(struct mm_struct *mm)
 	 */
 	set_bit(MMF_UNSTABLE, &mm->flags);
 
-	for (vma = mm->mmap ; vma; vma = vma->vm_next) {
+	rcu_read_lock();
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		if (!can_madv_lru_vma(vma))
 			continue;
 
@@ -560,6 +562,7 @@ bool __oom_reap_task_mm(struct mm_struct *mm)
 			tlb_finish_mmu(&tlb);
 		}
 	}
+	rcu_read_unlock();
 
 	return ret;
 }
Signature · 1 line
2.30.2
#65 lore raw

PATCH v2 58/61 mm/pagewalk: Use vma_next() instead of vma linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 mm/pagewalk.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
mm/pagewalk.c +1 -1
index 9b3db11a4d1d..d3c65a45fca9 100644
@@ -456,7 +456,7 @@ int walk_page_range(struct mm_struct *mm, unsigned long start,
 		} else { /* inside vma */
 			walk.vma = vma;
 			next = min(end, vma->vm_end);
-			vma = vma->vm_next;
+			vma = vma_next(mm, vma);;
 
 			err = walk_page_test(start, next, &walk);
 			if (err > 0) {
Signature · 1 line
2.30.2
#66 lore raw

PATCH v2 59/61 mm/swapfile: Use maple tree iterator instead of vma linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 mm/swapfile.c | 9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)
mm/swapfile.c +8 -1
index e3dcaeecc50f..32c40aa75e85 100644
@@ -2103,17 +2103,24 @@ static int unuse_mm(struct mm_struct *mm, unsigned int type,
 {
 	struct vm_area_struct *vma;
 	int ret = 0;
+	MA_STATE(mas, &mm->mm_mt, 0, 0);
 
 	mmap_read_lock(mm);
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	mas_lock(&mas);
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		if (vma->anon_vma) {
 			ret = unuse_vma(vma, type, frontswap,
 					fs_pages_to_unuse);
 			if (ret)
 				break;
 		}
+
+		mas_unlock(&mas);
+		mas_pause(&mas);
 		cond_resched();
+		mas_lock(&mas);
 	}
+	mas_unlock(&mas);
 	mmap_read_unlock(mm);
 	return ret;
 }
Signature · 1 line
2.30.2
#67 lore raw

PATCH v2 60/61 mm: Remove the vma linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Replace any vm_next use with vma_next().

Update free_pgtables(), unmap_vmas(), and zap_page_range() to use the maple tree.

Use the new free_pgtables() and unmap_vmas() in do_mas_align_munmap(). At the same time, alter the loop to be more compact.

Now that free_pgtables() and unmap_vmas() take a maple tree as an argument, rearrange do_mas_align_munmap() to use the new table to hold the lock

Move mas_lock()/mas_unlock() from vma_mas_store() and into vma_mas_link(). This will allow vma_mas_store() to be used in loops.

Remove __vma_link_list() and __vma_unlink_list() as they are exclusively used to update the linked list

Rework validation of tree as it was depending on the linked list.

---
 fs/proc/task_nommu.c     |   2 +-
 include/linux/mm.h       |   5 +-
 include/linux/mm_types.h |   4 -
 kernel/fork.c            |  13 +-
 mm/debug.c               |  14 +-
 mm/internal.h            |  14 +-
 mm/memory.c              |  33 ++-
 mm/mmap.c                | 531 +++++++++++++++++++--------------------
 mm/nommu.c               |   6 +-
 mm/util.c                |  40 ---
 10 files changed, 305 insertions(+), 357 deletions(-)
fs/proc/task_nommu.c +1 -1
index 8691a1216d1c..be02e8997ddf 100644
@@ -246,7 +246,7 @@ static void *m_next(struct seq_file *m, void *_p, loff_t *pos)
 	struct vm_area_struct *vma = _p;
 
 	*pos = vma->vm_end;
-	return vma->vm_next;
+	return vma_next(vma->vm_mm, vma);
 }
 
 static const struct seq_operations proc_pid_maps_ops = {
include/linux/mm.h +3 -2
index 7a5eb1fbb488..96002be8585d 100644
@@ -1843,8 +1843,9 @@ void zap_vma_ptes(struct vm_area_struct *vma, unsigned long address,
 		  unsigned long size);
 void zap_page_range(struct vm_area_struct *vma, unsigned long address,
 		    unsigned long size);
-void unmap_vmas(struct mmu_gather *tlb, struct vm_area_struct *start_vma,
-		unsigned long start, unsigned long end);
+void unmap_vmas(struct mmu_gather *tlb, struct maple_tree *mt,
+		struct vm_area_struct *start_vma, unsigned long start,
+		unsigned long end);
 
 struct mmu_notifier_range;
 
include/linux/mm_types.h +0 -4
index 374c48169692..428a697db7de 100644
@@ -403,8 +403,6 @@ struct vm_area_struct {
 	unsigned long vm_end;		/* The first byte after our end address
 					   within vm_mm. */
 
-	/* linked list of VM areas per task, sorted by address */
-	struct vm_area_struct *vm_next, *vm_prev;
 	struct mm_struct *vm_mm;	/* The address space we belong to. */
 
 	/*
@@ -470,7 +468,6 @@ struct core_state {
 struct kioctx_table;
 struct mm_struct {
 	struct {
-		struct vm_area_struct *mmap;		/* list of VMAs */
 		struct maple_tree mm_mt;
 #ifdef CONFIG_MMU
 		unsigned long (*get_unmapped_area) (struct file *filp,
@@ -485,7 +482,6 @@ struct mm_struct {
 		unsigned long mmap_compat_legacy_base;
 #endif
 		unsigned long task_size;	/* size of task vm space */
-		unsigned long highest_vm_end;	/* highest vma end address */
 		pgd_t * pgd;
 
 #ifdef CONFIG_MEMBARRIER
kernel/fork.c +1 -12
index 0c35460c092e..e8471b90910b 100644
@@ -364,7 +364,6 @@ struct vm_area_struct *vm_area_dup(struct vm_area_struct *orig)
 		 */
 		*new = data_race(*orig);
 		INIT_LIST_HEAD(&new->anon_vma_chain);
-		new->vm_next = new->vm_prev = NULL;
 	}
 	return new;
 }
@@ -473,7 +472,7 @@ EXPORT_SYMBOL(free_task);
 static __latent_entropy int dup_mmap(struct mm_struct *mm,
 					struct mm_struct *oldmm)
 {
-	struct vm_area_struct *mpnt, *tmp, *prev, **pprev;
+	struct vm_area_struct *mpnt, *tmp, *prev;
 	int retval;
 	unsigned long charge = 0;
 	MA_STATE(old_mas, &oldmm->mm_mt, 0, 0);
@@ -500,7 +499,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 	mm->exec_vm = oldmm->exec_vm;
 	mm->stack_vm = oldmm->stack_vm;
 
-	pprev = &mm->mmap;
 	retval = ksm_fork(mm, oldmm);
 	if (retval)
 		goto out;
@@ -588,14 +586,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 		if (is_vm_hugetlb_page(tmp))
 			reset_vma_resv_huge_pages(tmp);
 
-		/*
-		 * Link in the new vma and copy the page table entries.
-		 */
-		*pprev = tmp;
-		pprev = &tmp->vm_next;
-		tmp->vm_prev = prev;
-		prev = tmp;
-
 		/* Link the vma into the MT */
 		mas_lock(&mas);
 		mas.index = tmp->vm_start;
@@ -1091,7 +1081,6 @@ static void mm_init_uprobes_state(struct mm_struct *mm)
 static struct mm_struct *mm_init(struct mm_struct *mm, struct task_struct *p,
 	struct user_namespace *user_ns)
 {
-	mm->mmap = NULL;
 	mt_init_flags(&mm->mm_mt, MAPLE_ALLOC_RANGE);
 	atomic_set(&mm->mm_users, 1);
 	atomic_set(&mm->mm_count, 1);
mm/debug.c +6 -8
index f84662c87b4f..5b126eb5ef1b 100644
@@ -187,13 +187,11 @@ EXPORT_SYMBOL(dump_page);
 
 void dump_vma(const struct vm_area_struct *vma)
 {
-	pr_emerg("vma %px start %px end %px\n"
-		"next %px prev %px mm %px\n"
+	pr_emerg("vma %px start %px end %px mm %px\n"
 		"prot %lx anon_vma %px vm_ops %px\n"
 		"pgoff %lx file %px private_data %px\n"
 		"flags: %#lx(%pGv)\n",
-		vma, (void *)vma->vm_start, (void *)vma->vm_end, vma->vm_next,
-		vma->vm_prev, vma->vm_mm,
+		vma, (void *)vma->vm_start, (void *)vma->vm_end, vma->vm_mm,
 		(unsigned long)pgprot_val(vma->vm_page_prot),
 		vma->anon_vma, vma->vm_ops, vma->vm_pgoff,
 		vma->vm_file, vma->vm_private_data,
@@ -203,11 +201,11 @@ EXPORT_SYMBOL(dump_vma);
 
 void dump_mm(const struct mm_struct *mm)
 {
-	pr_emerg("mm %px mmap %px task_size %lu\n"
+	pr_emerg("mm %px task_size %lu\n"
 #ifdef CONFIG_MMU
 		"get_unmapped_area %px\n"
 #endif
-		"mmap_base %lu mmap_legacy_base %lu highest_vm_end %lu\n"
+		"mmap_base %lu mmap_legacy_base %lu\n"
 		"pgd %px mm_users %d mm_count %d pgtables_bytes %lu map_count %d\n"
 		"hiwater_rss %lx hiwater_vm %lx total_vm %lx locked_vm %lx\n"
 		"pinned_vm %llx data_vm %lx exec_vm %lx stack_vm %lx\n"
@@ -231,11 +229,11 @@ void dump_mm(const struct mm_struct *mm)
 		"tlb_flush_pending %d\n"
 		"def_flags: %#lx(%pGv)\n",
 
-		mm, mm->mmap, mm->task_size,
+		mm, mm->task_size,
 #ifdef CONFIG_MMU
 		mm->get_unmapped_area,
 #endif
-		mm->mmap_base, mm->mmap_legacy_base, mm->highest_vm_end,
+		mm->mmap_base, mm->mmap_legacy_base,
 		mm->pgd, atomic_read(&mm->mm_users),
 		atomic_read(&mm->mm_count),
 		mm_pgtables_bytes(mm),
mm/internal.h +3 -11
index eb883691709d..c8da57abf19b 100644
@@ -45,8 +45,9 @@ vm_fault_t do_swap_page(struct vm_fault *vmf);
 void folio_rotate_reclaimable(struct folio *folio);
 bool __folio_end_writeback(struct folio *folio);
 
-void free_pgtables(struct mmu_gather *tlb, struct vm_area_struct *start_vma,
-		unsigned long floor, unsigned long ceiling);
+void free_pgtables(struct mmu_gather *tlb, struct maple_tree *mt,
+		   struct vm_area_struct *start_vma, unsigned long floor,
+		   unsigned long ceiling);
 
 static inline bool can_madv_lru_vma(struct vm_area_struct *vma)
 {
@@ -395,9 +396,7 @@ static inline int vma_mas_store(struct vm_area_struct *vma, struct ma_state *mas
 #endif
 	mas->index = vma->vm_start;
 	mas->last = vma->vm_end - 1;
-	mas_lock(mas);
 	ret = mas_store_gfp(mas, vma, GFP_KERNEL);
-	mas_unlock(mas);
 	return ret;
 }
 
@@ -431,17 +430,10 @@ static inline int vma_mas_remove(struct vm_area_struct *vma, struct ma_state *ma
 #endif
 	mas->index = vma->vm_start;
 	mas->last = vma->vm_end - 1;
-	mas_lock(mas);
 	ret = mas_store_gfp(mas, NULL, GFP_KERNEL);
-	mas_unlock(mas);
 	return ret;
 }
 
-/* mm/util.c */
-void __vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma,
-		struct vm_area_struct *prev);
-void __vma_unlink_list(struct mm_struct *mm, struct vm_area_struct *vma);
-
 #ifdef CONFIG_MMU
 extern long populate_vma_page_range(struct vm_area_struct *vma,
 		unsigned long start, unsigned long end, int *locked);
mm/memory.c +24 -9
index 39e7a1495c3c..2d0c8b1066ba 100644
@@ -398,12 +398,21 @@ void free_pgd_range(struct mmu_gather *tlb,
 	} while (pgd++, addr = next, addr != end);
 }
 
-void free_pgtables(struct mmu_gather *tlb, struct vm_area_struct *vma,
-		unsigned long floor, unsigned long ceiling)
+void free_pgtables(struct mmu_gather *tlb, struct maple_tree *mt,
+		   struct vm_area_struct *vma, unsigned long floor,
+		   unsigned long ceiling)
 {
-	while (vma) {
-		struct vm_area_struct *next = vma->vm_next;
+	unsigned long index = vma->vm_end;
+
+	do {
 		unsigned long addr = vma->vm_start;
+		struct vm_area_struct *next;
+
+		/*
+		 * Note: USER_PGTABLES_CEILING may be passed as ceiling and may
+		 * be 0.  This will underflow and is okay.
+		 */
+		next = mt_find(mt, &index, ceiling - 1);
 
 		/*
 		 * Hide vma from rmap and truncate_pagecache before freeing
@@ -422,7 +431,7 @@ void free_pgtables(struct mmu_gather *tlb, struct vm_area_struct *vma,
 			while (next && next->vm_start <= vma->vm_end + PMD_SIZE
 			       && !is_vm_hugetlb_page(next)) {
 				vma = next;
-				next = vma->vm_next;
+				next = mt_find(mt, &index, ceiling - 1);
 				unlink_anon_vmas(vma);
 				unlink_file_vma(vma);
 			}
@@ -430,7 +439,7 @@ void free_pgtables(struct mmu_gather *tlb, struct vm_area_struct *vma,
 				floor, next ? next->vm_start : ceiling);
 		}
 		vma = next;
-	}
+	} while (vma);
 }
 
 int __pte_alloc(struct mm_struct *mm, pmd_t *pmd)
@@ -1616,17 +1625,19 @@ static void unmap_single_vma(struct mmu_gather *tlb,
  * ensure that any thus-far unmapped pages are flushed before unmap_vmas()
  * drops the lock and schedules.
  */
-void unmap_vmas(struct mmu_gather *tlb,
+void unmap_vmas(struct mmu_gather *tlb, struct maple_tree *mt,
 		struct vm_area_struct *vma, unsigned long start_addr,
 		unsigned long end_addr)
 {
 	struct mmu_notifier_range range;
+	unsigned long index = vma->vm_end;
 
 	mmu_notifier_range_init(&range, MMU_NOTIFY_UNMAP, 0, vma, vma->vm_mm,
 				start_addr, end_addr);
 	mmu_notifier_invalidate_range_start(&range);
-	for ( ; vma && vma->vm_start < end_addr; vma = vma->vm_next)
+	do {
 		unmap_single_vma(tlb, vma, start_addr, end_addr, NULL);
+	} while ((vma = mt_find(mt, &index, end_addr - 1)) != NULL);
 	mmu_notifier_invalidate_range_end(&range);
 }
 
@@ -1641,6 +1652,9 @@ void unmap_vmas(struct mmu_gather *tlb,
 void zap_page_range(struct vm_area_struct *vma, unsigned long start,
 		unsigned long size)
 {
+	struct maple_tree *mt = &vma->vm_mm->mm_mt;
+	unsigned long index = vma->vm_end;
+	unsigned long end = start + size;
 	struct mmu_notifier_range range;
 	struct mmu_gather tlb;
 
@@ -1650,8 +1664,9 @@ void zap_page_range(struct vm_area_struct *vma, unsigned long start,
 	tlb_gather_mmu(&tlb, vma->vm_mm);
 	update_hiwater_rss(vma->vm_mm);
 	mmu_notifier_invalidate_range_start(&range);
-	for ( ; vma && vma->vm_start < range.end; vma = vma->vm_next)
+	do {
 		unmap_single_vma(&tlb, vma, start, range.end, NULL);
+	} while ((vma = mt_find(mt, &index, end - 1)) != NULL);
 	mmu_notifier_invalidate_range_end(&range);
 	tlb_finish_mmu(&tlb);
 }
mm/mmap.c +265 -266

1,118 lines not on this page · raw message

mm/nommu.c +2 -4
index 675aee78f8f2..63dd382d09d3 100644
@@ -577,7 +577,6 @@ static void add_vma_to_mm(struct mm_struct *mm, struct vm_area_struct *vma)
 	mas_reset(&mas);
 	/* add the VMA to the tree */
 	vma_mas_store(vma, &mas);
-	__vma_link_list(mm, vma, prev);
 }
 
 /*
@@ -602,7 +601,6 @@ static void delete_vma_from_mm(struct vm_area_struct *vma)
 
 	/* remove from the MM's tree and list */
 	vma_mas_remove(vma, &mas);
-	__vma_unlink_list(vma->vm_mm, vma);
 }
 
 /*
@@ -1415,7 +1413,7 @@ int do_munmap(struct mm_struct *mm, unsigned long start, size_t len, struct list
 				return -EINVAL;
 			if (end == vma->vm_end)
 				goto erase_whole_vma;
-			vma = vma->vm_next;
+			vma =  vma_next(mm, vma);
 		} while (vma);
 		return -EINVAL;
 	} else {
@@ -1472,7 +1470,7 @@ void exit_mmap(struct mm_struct *mm)
 	mm->total_vm = 0;
 
 	while ((vma = mm->mmap)) {
-		mm->mmap = vma->vm_next;
+		mm->mmap = vma_next(mm, vma);
 		delete_vma_from_mm(vma);
 		delete_vma(mm, vma);
 		cond_resched();
mm/util.c +0 -40
index af8508e07a8e..1a420f0742f4 100644
@@ -271,46 +271,6 @@ void *memdup_user_nul(const void __user *src, size_t len)
 }
 EXPORT_SYMBOL(memdup_user_nul);
 
-void __vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma,
-		struct vm_area_struct *prev)
-{
-	struct vm_area_struct *next;
-
-	vma->vm_prev = prev;
-	if (prev) {
-		next = prev->vm_next;
-		prev->vm_next = vma;
-	} else {
-		next = mm->mmap;
-		mm->mmap = vma;
-	}
-	vma->vm_next = next;
-	if (next)
-		next->vm_prev = vma;
-	else
-		mm->highest_vm_end = vm_end_gap(vma);
-}
-
-void __vma_unlink_list(struct mm_struct *mm, struct vm_area_struct *vma)
-{
-	struct vm_area_struct *prev, *next;
-
-	next = vma->vm_next;
-	prev = vma->vm_prev;
-	if (prev)
-		prev->vm_next = next;
-	else
-		mm->mmap = next;
-	if (next)
-		next->vm_prev = prev;
-	else {
-		if (prev)
-			mm->highest_vm_end = vm_end_gap(prev);
-		else
-			mm->highest_vm_end = 0;
-	}
-}
-
 /* Check if the vma is being used as a stack by this task */
 int vma_is_stack_for_current(struct vm_area_struct *vma)
 {
Signature · 1 line
2.30.2
#68 lore raw

PATCH v2 61/61 mm/mmap: Drop range_has_overlap() function

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Since there is no longer a linked list, the range_has_overlap() function is identical to the find_vma_intersection() function. There is only one place that actually needs the previous vma, so just use vma_prev() in that one case.

---
 mm/mmap.c | 51 ++++++++++++---------------------------------------
 1 file changed, 12 insertions(+), 39 deletions(-)
mm/mmap.c +12 -39
index 06666706d5d3..2037a330b072 100644
@@ -435,30 +435,6 @@ anon_vma_interval_tree_post_update_vma(struct vm_area_struct *vma)
 		anon_vma_interval_tree_insert(avc, &avc->anon_vma->rb_root);
 }
 
-/*
- * range_has_overlap() - Check the @start - @end range for overlapping VMAs and
- * sets up a pointer to the previous VMA
- * @mm: the mm struct
- * @start: the start address of the range
- * @end: the end address of the range
- * @pprev: the pointer to the pointer of the previous VMA
- *
- * Returns: True if there is an overlapping VMA, false otherwise
- */
-static inline
-bool range_has_overlap(struct mm_struct *mm, unsigned long start,
-		       unsigned long end, struct vm_area_struct **pprev)
-{
-	struct vm_area_struct *existing;
-
-	MA_STATE(mas, &mm->mm_mt, start, start);
-	rcu_read_lock();
-	existing = mas_find(&mas, end - 1);
-	*pprev = mas_prev(&mas, 0);
-	rcu_read_unlock();
-	return existing ? true : false;
-}
-
 /*
  * count_vma_pages_range() - Count the number of pages in a range.
  * @mas: The maple state
@@ -558,7 +534,7 @@ void vma_mt_store(struct mm_struct *mm, struct vm_area_struct *vma)
  * Must not hold the maple tree lock.
  */
 static void vma_mas_link(struct mm_struct *mm, struct vm_area_struct *vma,
-			 struct ma_state *mas, struct vm_area_struct *prev)
+			 struct ma_state *mas)
 {
 	struct address_space *mapping = NULL;
 
@@ -578,8 +554,7 @@ static void vma_mas_link(struct mm_struct *mm, struct vm_area_struct *vma,
 	mm->map_count++;
 }
 
-static void vma_link(struct mm_struct *mm, struct vm_area_struct *vma,
-			struct vm_area_struct *prev)
+static void vma_link(struct mm_struct *mm, struct vm_area_struct *vma)
 {
 	struct address_space *mapping = NULL;
 
@@ -604,9 +579,7 @@ static void vma_link(struct mm_struct *mm, struct vm_area_struct *vma,
  */
 static void __insert_vm_struct(struct mm_struct *mm, struct vm_area_struct *vma)
 {
-	struct vm_area_struct *prev;
-
-	BUG_ON(range_has_overlap(mm, vma->vm_start, vma->vm_end, &prev));
+	BUG_ON(find_vma_intersection(mm, vma->vm_start, vma->vm_end));
 	vma_mt_store(mm, vma);
 	mm->map_count++;
 }
@@ -2781,7 +2754,7 @@ unsigned long mmap_region(struct file *file, unsigned long addr,
 	}
 
 	mas_set(&mas, addr);
-	vma_mas_link(mm, vma, &mas, prev);
+	vma_mas_link(mm, vma, &mas);
 	/* Once vma denies write, undo our temporary denial count */
 	if (file) {
 unmap_writable:
@@ -3165,7 +3138,7 @@ static int do_brk_flags(struct ma_state *mas, struct ma_state *ma_prev,
 	vma->vm_pgoff = addr >> PAGE_SHIFT;
 	vma->vm_flags = flags;
 	vma->vm_page_prot = vm_get_page_prot(flags);
-	vma_mas_link(mm, vma, mas, NULL);
+	vma_mas_link(mm, vma, mas);
 	*brkvma = vma;
 out:
 	perf_event_mmap(vma);
@@ -3317,9 +3290,7 @@ void exit_mmap(struct mm_struct *mm)
  */
 int insert_vm_struct(struct mm_struct *mm, struct vm_area_struct *vma)
 {
-	struct vm_area_struct *prev;
-
-	if (range_has_overlap(mm, vma->vm_start, vma->vm_end, &prev))
+	if (find_vma_intersection(mm, vma->vm_start, vma->vm_end))
 		return -ENOMEM;
 
 	if ((vma->vm_flags & VM_ACCOUNT) &&
@@ -3343,7 +3314,7 @@ int insert_vm_struct(struct mm_struct *mm, struct vm_area_struct *vma)
 		vma->vm_pgoff = vma->vm_start >> PAGE_SHIFT;
 	}
 
-	vma_link(mm, vma, prev);
+	vma_link(mm, vma);
 	return 0;
 }
 
@@ -3358,7 +3329,8 @@ struct vm_area_struct *copy_vma(struct vm_area_struct **vmap,
 	struct vm_area_struct *vma = *vmap;
 	unsigned long vma_start = vma->vm_start;
 	struct mm_struct *mm = vma->vm_mm;
-	struct vm_area_struct *new_vma, *prev;
+	struct vm_area_struct *new_vma;
+	struct vm_area_struct *prev;
 	bool faulted_in_anon_vma = true;
 
 	validate_mm_mt(mm);
@@ -3371,9 +3343,10 @@ struct vm_area_struct *copy_vma(struct vm_area_struct **vmap,
 		faulted_in_anon_vma = false;
 	}
 
-	if (range_has_overlap(mm, addr, addr + len, &prev))
+	if (find_vma_intersection(mm, addr, addr + len))
 		return NULL;	/* should never get here */
 
+	prev = vma_prev(mm, vma);
 	new_vma = vma_merge(mm, prev, addr, addr + len, vma->vm_flags,
 			    vma->anon_vma, vma->vm_file, pgoff, vma_policy(vma),
 			    vma->vm_userfaultfd_ctx);
@@ -3414,7 +3387,7 @@ struct vm_area_struct *copy_vma(struct vm_area_struct **vmap,
 			get_file(new_vma->vm_file);
 		if (new_vma->vm_ops && new_vma->vm_ops->open)
 			new_vma->vm_ops->open(new_vma);
-		vma_link(mm, new_vma, prev);
+		vma_link(mm, new_vma);
 		*need_rmap_locks = false;
 	}
 	validate_mm_mt(mm);
Signature · 1 line
2.30.2