Skip to contentSkip to conversation

further cleanup of vma_merge()

PATCH Superseded Lorenzo Stoakes 3 participants 11 messages Mar 18, 2023 – Mar 20, 2023

Subsystems (2)

v1 of 5 Superseded Latest is v5 →

lore
Share & tools
lore
#0 lore raw

cover further cleanup of vma_merge()

Following on from Vlastimil Babka's patch series "cleanup vma_merge() and improve mergeability tests" which was in turn based on Liam's prior cleanups, this patch series introduces changes discussed in review of Vlastimil's series and goes further in attempting to make the logic as clear as possible.

Nearly all of this should have absolutely no functional impact, however it does add a singular VM_WARN_ON() case.

Lorenzo Stoakes (4):
mm/mmap/vma_merge: further improve prev/next VMA naming mm/mmap/vma_merge: set next to NULL if not applicable mm/mmap/vma_merge: extend invariants, avoid invalid res, vma mm/mmap/vma_merge: be explicit about the non-mergeable case

 mm/mmap.c | 165 +++++++++++++++++++++++++++++++++++-------------------
 1 file changed, 107 insertions(+), 58 deletions(-)

--
2.39.2

#1 lore raw

PATCH 1/4 mm/mmap/vma_merge: further improve prev/next VMA naming

Previously the ASCII diagram above vma_merge() and the accompanying variable naming was rather confusing, however recent efforts by Liam Howlett and Vlastimil Babka have significantly improved matters.

This patch goes a little further - replacing 'X' with 'N' which feels a lot more natural and replacing what was 'N' with 'C' which stands for 'concurrent' VMA.

No word quite describes a VMA that has coincident start as the input span, concurrent, abbreviated to 'curr' (and which can be thought of also as 'current') however fits intuitions well alongside prev and next.

This has no functional impact.

---
 mm/mmap.c | 86 +++++++++++++++++++++++++++----------------------------
 1 file changed, 43 insertions(+), 43 deletions(-)
mm/mmap.c +43 -43
index 042d22e63528..c9834364ac98 100644
@@ -861,44 +861,44 @@ can_vma_merge_after(struct vm_area_struct *vma, unsigned long vm_flags,
  * this area are about to be changed to vm_flags - and the no-change
  * case has already been eliminated.
  *
- * The following mprotect cases have to be considered, where AAAA is
+ * The following mprotect cases have to be considered, where **** is
  * the area passed down from mprotect_fixup, never extending beyond one
- * vma, PPPP is the previous vma, NNNN is a vma that starts at the same
- * address as AAAA and is of the same or larger span, and XXXX the next
- * vma after AAAA:
+ * vma, PPPP is the previous vma, CCCC is a concurrent vma that starts
+ * at the same address as **** and is of the same or larger span, and
+ * NNNN the next vma after ****:
  *
- *     AAAA             AAAA                   AAAA
- *    PPPPPPXXXXXX    PPPPPPXXXXXX       PPPPPPNNNNNN
+ *     ****             ****                   ****
+ *    PPPPPPNNNNNN    PPPPPPNNNNNN       PPPPPPCCCCCC
  *    cannot merge    might become       might become
- *                    PPXXXXXXXXXX       PPPPPPPPPPNN
+ *                    PPNNNNNNNNNN       PPPPPPPPPPCC
  *    mmap, brk or    case 4 below       case 5 below
  *    mremap move:
- *                        AAAA               AAAA
- *                    PPPP    XXXX       PPPPNNNNXXXX
+ *                        ****               ****
+ *                    PPPP    NNNN       PPPPCCCCNNNN
  *                    might become       might become
  *                    PPPPPPPPPPPP 1 or  PPPPPPPPPPPP 6 or
- *                    PPPPPPPPXXXX 2 or  PPPPPPPPXXXX 7 or
- *                    PPPPXXXXXXXX 3     PPPPXXXXXXXX 8
+ *                    PPPPPPPPNNNN 2 or  PPPPPPPPNNNN 7 or
+ *                    PPPPNNNNNNNN 3     PPPPNNNNNNNN 8
  *
- * It is important for case 8 that the vma NNNN overlapping the
- * region AAAA is never going to extended over XXXX. Instead XXXX must
- * be extended in region AAAA and NNNN must be removed. This way in
+ * It is important for case 8 that the vma CCCC overlapping the
+ * region **** is never going to extended over NNNN. Instead NNNN must
+ * be extended in region **** and CCCC must be removed. This way in
  * all cases where vma_merge succeeds, the moment vma_merge drops the
  * rmap_locks, the properties of the merged vma will be already
  * correct for the whole merged range. Some of those properties like
  * vm_page_prot/vm_flags may be accessed by rmap_walks and they must
  * be correct for the whole merged range immediately after the
- * rmap_locks are released. Otherwise if XXXX would be removed and
- * NNNN would be extended over the XXXX range, remove_migration_ptes
+ * rmap_locks are released. Otherwise if NNNN would be removed and
+ * CCCC would be extended over the NNNN range, remove_migration_ptes
  * or other rmap walkers (if working on addresses beyond the "end"
- * parameter) may establish ptes with the wrong permissions of NNNN
- * instead of the right permissions of XXXX.
+ * parameter) may establish ptes with the wrong permissions of CCCC
+ * instead of the right permissions of NNNN.
  *
  * In the code below:
  * PPPP is represented by *prev
- * NNNN is represented by *mid or not represented at all (NULL)
- * XXXX is represented by *next or not represented at all (NULL)
- * AAAA is not represented - it will be merged and the vma containing the
+ * CCCC is represented by *curr or not represented at all (NULL)
+ * NNNN is represented by *next or not represented at all (NULL)
+ * **** is not represented - it will be merged and the vma containing the
  *      area is returned, or the function will return NULL
  */
 struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
@@ -911,7 +911,7 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 {
 	pgoff_t pglen = (end - addr) >> PAGE_SHIFT;
 	pgoff_t vma_pgoff;
-	struct vm_area_struct *mid, *next, *res = NULL;
+	struct vm_area_struct *curr, *next, *res = NULL;
 	struct vm_area_struct *vma, *adjust, *remove, *remove2;
 	int err = -1;
 	bool merge_prev = false;
@@ -930,19 +930,19 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 	if (vm_flags & VM_SPECIAL)
 		return NULL;
 
-	mid = find_vma(mm, prev ? prev->vm_end : 0);
-	if (mid && mid->vm_end == end)			/* cases 6, 7, 8 */
-		next = find_vma(mm, mid->vm_end);
+	curr = find_vma(mm, prev ? prev->vm_end : 0);
+	if (curr && curr->vm_end == end)		/* cases 6, 7, 8 */
+		next = find_vma(mm, curr->vm_end);
 	else
-		next = mid;
+		next = curr;
 
-	/* In cases 1 - 4 there's no NNNN vma */
-	if (mid && end <= mid->vm_start)
-		mid = NULL;
+	/* In cases 1 - 4 there's no CCCC vma */
+	if (curr && end <= curr->vm_start)
+		curr = NULL;
 
 	/* verify some invariant that must be enforced by the caller */
 	VM_WARN_ON(prev && addr <= prev->vm_start);
-	VM_WARN_ON(mid && end > mid->vm_end);
+	VM_WARN_ON(curr && end > curr->vm_end);
 	VM_WARN_ON(addr >= end);
 
 	if (prev) {
@@ -974,21 +974,21 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 		remove = next;				/* case 1 */
 		vma_end = next->vm_end;
 		err = dup_anon_vma(prev, next);
-		if (mid) {				/* case 6 */
-			remove = mid;
+		if (curr) {				/* case 6 */
+			remove = curr;
 			remove2 = next;
 			if (!next->anon_vma)
-				err = dup_anon_vma(prev, mid);
+				err = dup_anon_vma(prev, curr);
 		}
 	} else if (merge_prev) {
 		err = 0;				/* case 2 */
-		if (mid) {
-			err = dup_anon_vma(prev, mid);
-			if (end == mid->vm_end) {	/* case 7 */
-				remove = mid;
+		if (curr) {
+			err = dup_anon_vma(prev, curr);
+			if (end == curr->vm_end) {	/* case 7 */
+				remove = curr;
 			} else {			/* case 5 */
-				adjust = mid;
-				adj_start = (end - mid->vm_start);
+				adjust = curr;
+				adj_start = (end - curr->vm_start);
 			}
 		}
 	} else if (merge_next) {
@@ -1004,10 +1004,10 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 			vma_end = next->vm_end;
 			vma_pgoff = next->vm_pgoff;
 			err = 0;
-			if (mid) {			/* case 8 */
-				vma_pgoff = mid->vm_pgoff;
-				remove = mid;
-				err = dup_anon_vma(next, mid);
+			if (curr) {			/* case 8 */
+				vma_pgoff = curr->vm_pgoff;
+				remove = curr;
+				err = dup_anon_vma(next, curr);
 			}
 		}
 	}
Signature · 1 line
2.39.2
#2 lore raw

PATCH 2/4 mm/mmap/vma_merge: set next to NULL if not applicable

In reply to Lorenzo Stoakes

We are only interested in next if end == next->vm_start (in which case we check to see if we can set merge_next), so perform this check alongside checking whether curr should be set.

This groups all of the simple range checks together and establishes the invariant that, if prev, curr or next are non-NULL then their positions are as expected.

Additionally, use the abstract 'vma' object to look up the possible curr or next VMA in order to avoid any confusion as to what these variables represent - now curr and next are assigned once and only once.

This has no functional impact.

---
 mm/mmap.c | 61 ++++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 49 insertions(+), 12 deletions(-)
mm/mmap.c +49 -12
index c9834364ac98..66893fc72e03 100644
@@ -930,15 +930,53 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 	if (vm_flags & VM_SPECIAL)
 		return NULL;
 
-	curr = find_vma(mm, prev ? prev->vm_end : 0);
-	if (curr && curr->vm_end == end)		/* cases 6, 7, 8 */
-		next = find_vma(mm, curr->vm_end);
-	else
-		next = curr;
+	/*
+	 * If there is a previous VMA specified, find the next, otherwise find
+	 * the first.
+	 */
+	vma = find_vma(mm, prev ? prev->vm_end : 0);
+
+	/*
+	 * Does the input range span an existing VMA? If so, we designate this
+	 * VMA 'curr'. The caller will have ensured that curr->vm_start == addr.
+	 *
+	 * Cases 5 - 8.
+	 */
+	if (vma && end > vma->vm_start) {
+		curr = vma;
 
-	/* In cases 1 - 4 there's no CCCC vma */
-	if (curr && end <= curr->vm_start)
+		/*
+		 * If the addr - end range spans this VMA entirely, then we
+		 * check to see if another VMA follows it.
+		 *
+		 * If it is _immediately_ adjacent (checked below), then we
+		 * designate it 'next' (cases 6 - 8).
+		 */
+		if (curr->vm_end == end)
+			vma = find_vma(mm, curr->vm_end);
+		else
+			/* Case 5. */
+			vma = NULL;
+	} else {
+		/*
+		 * The addr - end range either spans the end of prev or spans no
+		 * VMA at all - in either case we dispense with 'curr' and
+		 * maintain only 'prev' and (possibly) 'next'.
+		 *
+		 * Cases 1 - 4.
+		 */
 		curr = NULL;
+	}
+
+	/*
+	 * We only actually examine the next VMA if it is immediately adjacent
+	 * to end which sits either at the end of a hole (cases 1 - 3), PPPP
+	 * (case 4) or CCCC (cases 6 - 8).
+	 */
+	if (vma && end == vma->vm_start)
+		next = vma;
+	else
+		next = NULL;
 
 	/* verify some invariant that must be enforced by the caller */
 	VM_WARN_ON(prev && addr <= prev->vm_start);
@@ -959,11 +997,10 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 		}
 	}
 	/* Can we merge the successor? */
-	if (next && end == next->vm_start &&
-			mpol_equal(policy, vma_policy(next)) &&
-			can_vma_merge_before(next, vm_flags,
-					     anon_vma, file, pgoff+pglen,
-					     vm_userfaultfd_ctx, anon_name)) {
+	if (next && mpol_equal(policy, vma_policy(next)) &&
+	    can_vma_merge_before(next, vm_flags,
+				 anon_vma, file, pgoff+pglen,
+				 vm_userfaultfd_ctx, anon_name)) {
 		merge_next = true;
 	}
 
Signature · 1 line
2.39.2
#3 lore raw

Re: [PATCH 2/4] mm/mmap/vma_merge: set next to NULL if not applicable

Quoted 11 lines · Lorenzo Stoakes

We are only interested in next if end == next->vm_start (in which case we check to see if we can set merge_next), so perform this check alongside checking whether curr should be set.

This groups all of the simple range checks together and establishes the invariant that, if prev, curr or next are non-NULL then their positions are as expected.

Additionally, use the abstract 'vma' object to look up the possible curr or next VMA in order to avoid any confusion as to what these variables represent - now curr and next are assigned once and only once.

Hi Lorenzo,

Due to the "vma" variable is used as an intermediate member, I feels a bit confusing, so cleanup this patch as below.

If this cleanup patch is issue, please let me know, and then ignore it directly, thanks.

----
From 7dac3ed8c1b747c2edf2a6c867c4e6342c7447c3 Mon Sep 17 00:00:00 2001
From: Vernon Yang <[email protected]>
Date: Mon, 20 Mar 2023 21:38:09 +0800
Subject: [PATCH] mm/mmap/vma_merge: set next to NULL if not applicable-cleanup

Make code logic simpler and more readable.

---
 mm/mmap.c | 23 ++++++-----------------
 1 file changed, 6 insertions(+), 17 deletions(-)
mm/mmap.c +6 -17
index 45bd43225013..78cb96774602 100644
@@ -921,7 +921,7 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 	 * If there is a previous VMA specified, find the next, otherwise find
 	 * the first.
 	 */
-	vma = find_vma(mm, prev ? prev->vm_end : 0);
+	curr = find_vma(mm, prev ? prev->vm_end : 0);
 
 	/*
 	 * Does the input range span an existing VMA? If so, we designate this
@@ -929,21 +929,19 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 	 *
 	 * Cases 5 - 8.
 	 */
-	if (vma && end > vma->vm_start) {
-		curr = vma;
-
+	if (curr && end > curr->vm_start) {
 		/*
 		 * If the addr - end range spans this VMA entirely, then we
 		 * check to see if another VMA follows it.
 		 *
-		 * If it is _immediately_ adjacent (checked below), then we
+		 * If it is immediately adjacent (checked below), then we
 		 * designate it 'next' (cases 6 - 8).
 		 */
 		if (curr->vm_end == end)
-			vma = find_vma(mm, curr->vm_end);
+			next = find_vma(mm, curr->vm_end);
 		else
 			/* Case 5. */
-			vma = NULL;
+			next = NULL;
 	} else {
 		/*
 		 * The addr - end range either spans the end of prev or spans no
@@ -952,19 +950,10 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 		 *
 		 * Cases 1 - 4.
 		 */
+		next = curr;
 		curr = NULL;
 	}
 
-	/*
-	 * We only actually examine the next VMA if it is immediately adjacent
-	 * to end which sits either at the end of a hole (cases 1 - 3), PPPP
-	 * (case 4) or CCCC (cases 6 - 8).
-	 */
-	if (vma && end == vma->vm_start)
-		next = vma;
-	else
-		next = NULL;
-
 	/*
 	 * By default, we return prev. Cases 3, 4, 8 will instead return next
 	 * and cases 3, 8 will also update vma to point at next.

--
2.34.1

Quoted 93 lines

This has no functional impact.

---
 mm/mmap.c | 61 ++++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 49 insertions(+), 12 deletions(-)
mm/mmap.c +49 -13
index c9834364ac98..66893fc72e03 100644
@@ -930,15 +930,53 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 	if (vm_flags & VM_SPECIAL)
 		return NULL;
 
-	curr = find_vma(mm, prev ? prev->vm_end : 0);
-	if (curr && curr->vm_end == end)		/* cases 6, 7, 8 */
-		next = find_vma(mm, curr->vm_end);
-	else
-		next = curr;
+	/*
+	 * If there is a previous VMA specified, find the next, otherwise find
+	 * the first.
+	 */
+	vma = find_vma(mm, prev ? prev->vm_end : 0);
+
+	/*
+	 * Does the input range span an existing VMA? If so, we designate this
+	 * VMA 'curr'. The caller will have ensured that curr->vm_start == addr.
+	 *
+	 * Cases 5 - 8.
+	 */
+	if (vma && end > vma->vm_start) {
+		curr = vma;
 
-	/* In cases 1 - 4 there's no CCCC vma */
-	if (curr && end <= curr->vm_start)
+		/*
+		 * If the addr - end range spans this VMA entirely, then we
+		 * check to see if another VMA follows it.
+		 *
+		 * If it is _immediately_ adjacent (checked below), then we
+		 * designate it 'next' (cases 6 - 8).
+		 */
+		if (curr->vm_end == end)
+			vma = find_vma(mm, curr->vm_end);
+		else
+			/* Case 5. */
+			vma = NULL;
+	} else {
+		/*
+		 * The addr - end range either spans the end of prev or spans no
+		 * VMA at all - in either case we dispense with 'curr' and
+		 * maintain only 'prev' and (possibly) 'next'.
+		 *
+		 * Cases 1 - 4.
+		 */
 		curr = NULL;
+	}
+
+	/*
+	 * We only actually examine the next VMA if it is immediately adjacent
+	 * to end which sits either at the end of a hole (cases 1 - 3), PPPP
+	 * (case 4) or CCCC (cases 6 - 8).
+	 */
+	if (vma && end == vma->vm_start)
+		next = vma;
+	else
+		next = NULL;
 
 	/* verify some invariant that must be enforced by the caller */
 	VM_WARN_ON(prev && addr <= prev->vm_start);
@@ -959,11 +997,10 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 		}
 	}
 	/* Can we merge the successor? */
-	if (next && end == next->vm_start &&
-			mpol_equal(policy, vma_policy(next)) &&
-			can_vma_merge_before(next, vm_flags,
-					     anon_vma, file, pgoff+pglen,
-					     vm_userfaultfd_ctx, anon_name)) {
+	if (next && mpol_equal(policy, vma_policy(next)) &&
+	    can_vma_merge_before(next, vm_flags,
+				 anon_vma, file, pgoff+pglen,
+				 vm_userfaultfd_ctx, anon_name)) {
 		merge_next = true;
 	}
 
 
--

2.39.2

#4 lore raw

Re: [PATCH 2/4] mm/mmap/vma_merge: set next to NULL if not applicable

Quoted 9 lines · Vernon Yang
Quoted 8 lines · Lorenzo Stoakes

We are only interested in next if end == next->vm_start (in which case we check to see if we can set merge_next), so perform this check alongside checking whether curr should be set.

This groups all of the simple range checks together and establishes the invariant that, if prev, curr or next are non-NULL then their positions are as expected.

Quoted 8 lines
Quoted 3 lines

Additionally, use the abstract 'vma' object to look up the possible curr or next VMA in order to avoid any confusion as to what these variables represent - now curr and next are assigned once and only once.

Hi Lorenzo,

Due to the "vma" variable is used as an intermediate member, I feels a bit confusing, so cleanup this patch as below.

Hi Vernon, if you read the commit message you'll see what you're undoing here is exactly what I have done on purpose. The point is to assign each of curr and next once and only once after we've determined which of the two we are assigning to.

You also delete some of the explanation which I added explicitly to make the logic clearer and adjust _punctionation_ neither of which I feel are positive changes.

The point is that existing logic treated either mid or curr as temporary variables that might get reassigned.

By using a temporary value and explaining what we're doing, you can see _why_ we are assigning it.

Quoted 3 lines

If this cleanup patch is issue, please let me know, and then ignore it directly, thanks.

So I'm afraid I am not in favour of your change, though thank you for your interest!

I am happy to get feedback on the change, though I'd suggest commenting on anything you have issues with rather than attempting to rework my change as if we start getting patches within patches it's going to end like inception :)

Cheers, Lorenzo

Quoted 171 lines

----
From 7dac3ed8c1b747c2edf2a6c867c4e6342c7447c3 Mon Sep 17 00:00:00 2001
From: Vernon Yang <[email protected]>
Date: Mon, 20 Mar 2023 21:38:09 +0800
Subject: [PATCH] mm/mmap/vma_merge: set next to NULL if not applicable-cleanup

Make code logic simpler and more readable.

---
 mm/mmap.c | 23 ++++++-----------------
 1 file changed, 6 insertions(+), 17 deletions(-)
mm/mmap.c +6 -18
index 45bd43225013..78cb96774602 100644
@@ -921,7 +921,7 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 	 * If there is a previous VMA specified, find the next, otherwise find
 	 * the first.
 	 */
-	vma = find_vma(mm, prev ? prev->vm_end : 0);
+	curr = find_vma(mm, prev ? prev->vm_end : 0);
 
 	/*
 	 * Does the input range span an existing VMA? If so, we designate this
@@ -929,21 +929,19 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 	 *
 	 * Cases 5 - 8.
 	 */
-	if (vma && end > vma->vm_start) {
-		curr = vma;
-
+	if (curr && end > curr->vm_start) {
 		/*
 		 * If the addr - end range spans this VMA entirely, then we
 		 * check to see if another VMA follows it.
 		 *
-		 * If it is _immediately_ adjacent (checked below), then we
+		 * If it is immediately adjacent (checked below), then we
 		 * designate it 'next' (cases 6 - 8).
 		 */
 		if (curr->vm_end == end)
-			vma = find_vma(mm, curr->vm_end);
+			next = find_vma(mm, curr->vm_end);
 		else
 			/* Case 5. */
-			vma = NULL;
+			next = NULL;
 	} else {
 		/*
 		 * The addr - end range either spans the end of prev or spans no
@@ -952,19 +950,10 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 		 *
 		 * Cases 1 - 4.
 		 */
+		next = curr;
 		curr = NULL;
 	}
 
-	/*
-	 * We only actually examine the next VMA if it is immediately adjacent
-	 * to end which sits either at the end of a hole (cases 1 - 3), PPPP
-	 * (case 4) or CCCC (cases 6 - 8).
-	 */
-	if (vma && end == vma->vm_start)
-		next = vma;
-	else
-		next = NULL;
-
 	/*
 	 * By default, we return prev. Cases 3, 4, 8 will instead return next
 	 * and cases 3, 8 will also update vma to point at next.
--

2.34.1

Quoted 93 lines

This has no functional impact.

---
 mm/mmap.c | 61 ++++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 49 insertions(+), 12 deletions(-)
mm/mmap.c +49 -13
index c9834364ac98..66893fc72e03 100644
@@ -930,15 +930,53 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 	if (vm_flags & VM_SPECIAL)
 		return NULL;
 
-	curr = find_vma(mm, prev ? prev->vm_end : 0);
-	if (curr && curr->vm_end == end)		/* cases 6, 7, 8 */
-		next = find_vma(mm, curr->vm_end);
-	else
-		next = curr;
+	/*
+	 * If there is a previous VMA specified, find the next, otherwise find
+	 * the first.
+	 */
+	vma = find_vma(mm, prev ? prev->vm_end : 0);
+
+	/*
+	 * Does the input range span an existing VMA? If so, we designate this
+	 * VMA 'curr'. The caller will have ensured that curr->vm_start == addr.
+	 *
+	 * Cases 5 - 8.
+	 */
+	if (vma && end > vma->vm_start) {
+		curr = vma;
 
-	/* In cases 1 - 4 there's no CCCC vma */
-	if (curr && end <= curr->vm_start)
+		/*
+		 * If the addr - end range spans this VMA entirely, then we
+		 * check to see if another VMA follows it.
+		 *
+		 * If it is _immediately_ adjacent (checked below), then we
+		 * designate it 'next' (cases 6 - 8).
+		 */
+		if (curr->vm_end == end)
+			vma = find_vma(mm, curr->vm_end);
+		else
+			/* Case 5. */
+			vma = NULL;
+	} else {
+		/*
+		 * The addr - end range either spans the end of prev or spans no
+		 * VMA at all - in either case we dispense with 'curr' and
+		 * maintain only 'prev' and (possibly) 'next'.
+		 *
+		 * Cases 1 - 4.
+		 */
 		curr = NULL;
+	}
+
+	/*
+	 * We only actually examine the next VMA if it is immediately adjacent
+	 * to end which sits either at the end of a hole (cases 1 - 3), PPPP
+	 * (case 4) or CCCC (cases 6 - 8).
+	 */
+	if (vma && end == vma->vm_start)
+		next = vma;
+	else
+		next = NULL;
 
 	/* verify some invariant that must be enforced by the caller */
 	VM_WARN_ON(prev && addr <= prev->vm_start);
@@ -959,11 +997,10 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 		}
 	}
 	/* Can we merge the successor? */
-	if (next && end == next->vm_start &&
-			mpol_equal(policy, vma_policy(next)) &&
-			can_vma_merge_before(next, vm_flags,
-					     anon_vma, file, pgoff+pglen,
-					     vm_userfaultfd_ctx, anon_name)) {
+	if (next && mpol_equal(policy, vma_policy(next)) &&
+	    can_vma_merge_before(next, vm_flags,
+				 anon_vma, file, pgoff+pglen,
+				 vm_userfaultfd_ctx, anon_name)) {
 		merge_next = true;
 	}
 
 
--

2.39.2

#5 lore raw

Re: [PATCH 2/4] mm/mmap/vma_merge: set next to NULL if not applicable

In reply to Lorenzo Stoakes
Quoted 36 lines · Lorenzo Stoakes

We are only interested in next if end == next->vm_start (in which case we check to see if we can set merge_next), so perform this check alongside checking whether curr should be set.

This groups all of the simple range checks together and establishes the invariant that, if prev, curr or next are non-NULL then their positions are as expected.

Additionally, use the abstract 'vma' object to look up the possible curr or next VMA in order to avoid any confusion as to what these variables represent - now curr and next are assigned once and only once.

This has no functional impact.

---
 mm/mmap.c | 61 ++++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 49 insertions(+), 12 deletions(-)
mm/mmap.c +4 -5
index c9834364ac98..66893fc72e03 100644
@@ -930,15 +930,53 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 	if (vm_flags & VM_SPECIAL)
 		return NULL;
 
-	curr = find_vma(mm, prev ? prev->vm_end : 0);
-	if (curr && curr->vm_end == end)		/* cases 6, 7, 8 */
-		next = find_vma(mm, curr->vm_end);
-	else
-		next = curr;
+	/*
+	 * If there is a previous VMA specified, find the next, otherwise find
+	 * the first.
+	 */

mm/mmap.c struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm, · line 946

Quoted 10 lines
mm/mmap.c +10 -0
+	vma = find_vma(mm, prev ? prev->vm_end : 0);
+
+	/*
+	 * Does the input range span an existing VMA? If so, we designate this
+	 * VMA 'curr'. The caller will have ensured that curr->vm_start == addr.
+	 *
+	 * Cases 5 - 8.
+	 */
+	if (vma && end > vma->vm_start) {
+		curr = vma;

It might be better to set:
curr = find_vma_intersection(mm, prev ? prev->vm_end : 0, end);

mm/mmap.c struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm, · line 956

Quoted 12 lines
mm/mmap.c +9 -2
-	/* In cases 1 - 4 there's no CCCC vma */
-	if (curr && end <= curr->vm_start)
+		/*
+		 * If the addr - end range spans this VMA entirely, then we
+		 * check to see if another VMA follows it.
+		 *
+		 * If it is _immediately_ adjacent (checked below), then we
+		 * designate it 'next' (cases 6 - 8).
+		 */
+		if (curr->vm_end == end)
+			vma = find_vma(mm, curr->vm_end);

You can change this to:
next = vma_lookup(mm, curr->vm_end);
Then you don't need to validate below, in this case.

mm/mmap.c struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm, · line 964

Quoted 10 lines
mm/mmap.c +8 -0
+		else
+			/* Case 5. */
+			vma = NULL;
 
 
+	} else {
+		/*
+		 * The addr - end range either spans the end of prev or spans no
+		 * VMA at all - in either case we dispense with 'curr' and
+		 * maintain only 'prev' and (possibly) 'next'.

Possibly next here would be:
next = vma_lookup(mm, end);
I think?

Quoted 5 lines
mm/mmap.c +4 -0
+		 *
+		 * Cases 1 - 4.
+		 */
 		curr = NULL;
+	}

mm/mmap.c struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm, · line 979

Quoted 10 lines
mm/mmap.c +10 -0
+
+	/*
+	 * We only actually examine the next VMA if it is immediately adjacent
+	 * to end which sits either at the end of a hole (cases 1 - 3), PPPP
+	 * (case 4) or CCCC (cases 6 - 8).
+	 */
+	if (vma && end == vma->vm_start)
+		next = vma;
+	else
+		next = NULL;

If I'm correct above, then we can drop this next checking.

Quoted 6 lines
mm/mmap.c +0 -0
 	/* verify some invariant that must be enforced by the caller */
 	VM_WARN_ON(prev && addr <= prev->vm_start);
@@ -959,11 +997,10 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 		}
 	}

mm/mmap.c struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm, · line 1003

Quoted 10 lines
mm/mmap.c +4 -5
 	/* Can we merge the successor? */
-	if (next && end == next->vm_start &&
-			mpol_equal(policy, vma_policy(next)) &&
-			can_vma_merge_before(next, vm_flags,
-					     anon_vma, file, pgoff+pglen,
-					     vm_userfaultfd_ctx, anon_name)) {
+	if (next && mpol_equal(policy, vma_policy(next)) &&
+	    can_vma_merge_before(next, vm_flags,
+				 anon_vma, file, pgoff+pglen,
+				 vm_userfaultfd_ctx, anon_name)) {

I think we can keep this chunk with the next = vma_lookup() changes as well.

Quoted 6 lines
mm/mmap.c +0 -0
 		merge_next = true;
 	}
 
Signature · 1 line
2.39.2
#6 lore raw

Re: [PATCH 2/4] mm/mmap/vma_merge: set next to NULL if not applicable

Quoted 112 lines · Liam R. Howlett
Quoted 36 lines · Lorenzo Stoakes

We are only interested in next if end == next->vm_start (in which case we check to see if we can set merge_next), so perform this check alongside checking whether curr should be set.

This groups all of the simple range checks together and establishes the invariant that, if prev, curr or next are non-NULL then their positions are as expected.

Additionally, use the abstract 'vma' object to look up the possible curr or next VMA in order to avoid any confusion as to what these variables represent - now curr and next are assigned once and only once.

This has no functional impact.

---
 mm/mmap.c | 61 ++++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 49 insertions(+), 12 deletions(-)
mm/mmap.c +4 -5
index c9834364ac98..66893fc72e03 100644
@@ -930,15 +930,53 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 	if (vm_flags & VM_SPECIAL)
 		return NULL;
 
-	curr = find_vma(mm, prev ? prev->vm_end : 0);
-	if (curr && curr->vm_end == end)		/* cases 6, 7, 8 */
-		next = find_vma(mm, curr->vm_end);
-	else
-		next = curr;
+	/*
+	 * If there is a previous VMA specified, find the next, otherwise find
+	 * the first.
+	 */

mm/mmap.c struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm, · line 946

Quoted 10 lines
mm/mmap.c +10 -0
+	vma = find_vma(mm, prev ? prev->vm_end : 0);
+
+	/*
+	 * Does the input range span an existing VMA? If so, we designate this
+	 * VMA 'curr'. The caller will have ensured that curr->vm_start == addr.
+	 *
+	 * Cases 5 - 8.
+	 */
+	if (vma && end > vma->vm_start) {
+		curr = vma;

It might be better to set:
curr = find_vma_intersection(mm, prev ? prev->vm_end : 0, end);

mm/mmap.c struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm, · line 956

Quoted 12 lines
mm/mmap.c +9 -2
-	/* In cases 1 - 4 there's no CCCC vma */
-	if (curr && end <= curr->vm_start)
+		/*
+		 * If the addr - end range spans this VMA entirely, then we
+		 * check to see if another VMA follows it.
+		 *
+		 * If it is _immediately_ adjacent (checked below), then we
+		 * designate it 'next' (cases 6 - 8).
+		 */
+		if (curr->vm_end == end)
+			vma = find_vma(mm, curr->vm_end);

You can change this to:
next = vma_lookup(mm, curr->vm_end);
Then you don't need to validate below, in this case.

mm/mmap.c struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm, · line 964

Quoted 10 lines
mm/mmap.c +8 -0
+		else
+			/* Case 5. */
+			vma = NULL;
 
 
+	} else {
+		/*
+		 * The addr - end range either spans the end of prev or spans no
+		 * VMA at all - in either case we dispense with 'curr' and
+		 * maintain only 'prev' and (possibly) 'next'.

Possibly next here would be:
next = vma_lookup(mm, end);
I think?

Quoted 5 lines
mm/mmap.c +4 -0
+		 *
+		 * Cases 1 - 4.
+		 */
 		curr = NULL;
+	}

mm/mmap.c struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm, · line 979

Quoted 10 lines
mm/mmap.c +10 -0
+
+	/*
+	 * We only actually examine the next VMA if it is immediately adjacent
+	 * to end which sits either at the end of a hole (cases 1 - 3), PPPP
+	 * (case 4) or CCCC (cases 6 - 8).
+	 */
+	if (vma && end == vma->vm_start)
+		next = vma;
+	else
+		next = NULL;

If I'm correct above, then we can drop this next checking.

Quoted 11 lines
mm/mmap.c +0 -4
 	/* verify some invariant that must be enforced by the caller */
 	VM_WARN_ON(prev && addr <= prev->vm_start);
@@ -959,11 +997,10 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 		}
 	}
 	/* Can we merge the successor? */
-	if (next && end == next->vm_start &&
-			mpol_equal(policy, vma_policy(next)) &&
-			can_vma_merge_before(next, vm_flags,
-					     anon_vma, file, pgoff+pglen,
Quoted 15 lines

mm/mmap.c struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm, · line 1003

Quoted 5 lines
mm/mmap.c +4 -1
-					     vm_userfaultfd_ctx, anon_name)) {
+	if (next && mpol_equal(policy, vma_policy(next)) &&
+	    can_vma_merge_before(next, vm_flags,
+				 anon_vma, file, pgoff+pglen,
+				 vm_userfaultfd_ctx, anon_name)) {

I think we can keep this chunk with the next = vma_lookup() changes as well.

Quoted 6 lines
mm/mmap.c +0 -1
 		merge_next = true;
 	}
 
--

2.39.2

Thanks, I will investigate all of these and will try to apply everything that is workable from here + respin.

#7 lore raw

PATCH 3/4 mm/mmap/vma_merge: extend invariants, avoid invalid res, vma

In reply to Lorenzo Stoakes

Previously, vma was an uninitialised variable which was only definitely assigned as a result of the logic covering all possible input cases - for it to have remained uninitialised, prev would have to be NULL, and next would _have_ to be mergeable.

We now reuse vma to assign curr and next, so to be absolutely explicit, ensure this variable is _always_ assigned, and while we're at it remove the redundant assignment of both res and vma (if prev is NULL then we simply assign to NULL).

In addition, we absolutely do rely on addr == curr->vm_start should curr exist, so assert as much.

---
 mm/mmap.c | 19 ++++++++++++++-----
 1 file changed, 14 insertions(+), 5 deletions(-)
mm/mmap.c +14 -5
index 66893fc72e03..e60c637f4e49 100644
@@ -911,7 +911,7 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 {
 	pgoff_t pglen = (end - addr) >> PAGE_SHIFT;
 	pgoff_t vma_pgoff;
-	struct vm_area_struct *curr, *next, *res = NULL;
+	struct vm_area_struct *curr, *next, *res;
 	struct vm_area_struct *vma, *adjust, *remove, *remove2;
 	int err = -1;
 	bool merge_prev = false;
@@ -978,14 +978,18 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 	else
 		next = NULL;
 
-	/* verify some invariant that must be enforced by the caller */
+	/*
+	 * By default, we return prev. Cases 3, 4, 8 will instead return next
+	 * and cases 3, 8 will also update vma to point at next.
+	 */
+	res = vma = prev;
+
+	/* Verify some invariant that must be enforced by the caller. */
 	VM_WARN_ON(prev && addr <= prev->vm_start);
-	VM_WARN_ON(curr && end > curr->vm_end);
+	VM_WARN_ON(curr && (addr != curr->vm_start || end > curr->vm_end));
 	VM_WARN_ON(addr >= end);
 
 	if (prev) {
-		res = prev;
-		vma = prev;
 		vma_start = prev->vm_start;
 		vma_pgoff = prev->vm_pgoff;
 		/* Can we merge the predecessor? */
@@ -996,6 +1000,7 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 			vma_prev(vmi);
 		}
 	}
+
 	/* Can we merge the successor? */
 	if (next && mpol_equal(policy, vma_policy(next)) &&
 	    can_vma_merge_before(next, vm_flags,
@@ -1036,6 +1041,10 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 			adj_start = -(prev->vm_end - addr);
 			err = dup_anon_vma(next, prev);
 		} else {
+			/*
+			 * Note that cases 3 and 8 are the ONLY ones where prev
+			 * is permitted to be (but is not necessarily) NULL.
+			 */
 			vma = next;			/* case 3 */
 			vma_start = addr;
 			vma_end = next->vm_end;
Signature · 1 line
2.39.2
#8 lore raw

PATCH 4/4 mm/mmap/vma_merge: be explicit about the non-mergeable case

In reply to Lorenzo Stoakes

Rather than setting err = -1 and only resetting if we hit merge cases, explicitly check the non-mergeable case to make it abundantly clear that we only proceed with the rest if something is mergeable, default err to 0 and only update if an error might occur.

Additionally set merge_next directly as there is no need for an if() {} statement assigning a boolean.

This has no functional impact.

---
 mm/mmap.c | 25 ++++++++++++++-----------
 1 file changed, 14 insertions(+), 11 deletions(-)
mm/mmap.c +14 -11
index e60c637f4e49..2ac43b2b9a00 100644
@@ -913,7 +913,7 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 	pgoff_t vma_pgoff;
 	struct vm_area_struct *curr, *next, *res;
 	struct vm_area_struct *vma, *adjust, *remove, *remove2;
-	int err = -1;
+	int err = 0;
 	bool merge_prev = false;
 	bool merge_next = false;
 	bool vma_expanded = false;
@@ -1002,12 +1002,15 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 	}
 
 	/* Can we merge the successor? */
-	if (next && mpol_equal(policy, vma_policy(next)) &&
-	    can_vma_merge_before(next, vm_flags,
-				 anon_vma, file, pgoff+pglen,
-				 vm_userfaultfd_ctx, anon_name)) {
-		merge_next = true;
-	}
+	merge_next = next &&
+		mpol_equal(policy, vma_policy(next)) &&
+		can_vma_merge_before(next, vm_flags,
+				     anon_vma, file, pgoff+pglen,
+				     vm_userfaultfd_ctx, anon_name);
+
+	/* Not mergeable. */
+	if (!merge_prev && !merge_next)
+		return NULL;
 
 	remove = remove2 = adjust = NULL;
 	/* Can we merge both the predecessor and the successor? */
@@ -1023,7 +1026,7 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 				err = dup_anon_vma(prev, curr);
 		}
 	} else if (merge_prev) {
-		err = 0;				/* case 2 */
+							/* case 2 */
 		if (curr) {
 			err = dup_anon_vma(prev, curr);
 			if (end == curr->vm_end) {	/* case 7 */
@@ -1033,7 +1036,7 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 				adj_start = (end - curr->vm_start);
 			}
 		}
-	} else if (merge_next) {
+	} else { /* merge_next */
 		res = next;
 		if (prev && addr < prev->vm_end) {	/* case 4 */
 			vma_end = addr;
@@ -1049,7 +1052,7 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 			vma_start = addr;
 			vma_end = next->vm_end;
 			vma_pgoff = next->vm_pgoff;
-			err = 0;
+
 			if (curr) {			/* case 8 */
 				vma_pgoff = curr->vm_pgoff;
 				remove = curr;
@@ -1058,7 +1061,7 @@ struct vm_area_struct *vma_merge(struct vma_iterator *vmi, struct mm_struct *mm,
 		}
 	}
 
-	/* Cannot merge or error in anon_vma clone */
+	/* Error in anon_vma clone. */
 	if (err)
 		return NULL;
 
Signature · 1 line
2.39.2
#9 lore raw
In reply to Lorenzo Stoakes
Quoted 8 lines · Lorenzo Stoakes

Following on from Vlastimil Babka's patch series "cleanup vma_merge() and improve mergeability tests" which was in turn based on Liam's prior cleanups, this patch series introduces changes discussed in review of Vlastimil's series and goes further in attempting to make the logic as clear as possible.

Nearly all of this should have absolutely no functional impact, however it does add a singular VM_WARN_ON() case.

Thanks for looking at this function and adding more clarity. I'm happy to have comments within the code, especially tricky areas. But I find that adding almost 50 lines to this function makes it rather hard to follow.

Can we remove the more obvious comments and possibly reduce the nesting of others so there are less lines?

For example in patch 2:

        /*
         * If there is a previous VMA specified, find the next, otherwise find                                          
         * the first.                                                                                                   
         */ 
        vma = find_vma(mm, prev ? prev->vm_end : 0);

Is rather verbose for something that can be seen in the code itself.

I think we are risking over-documenting what is going on here which is making the code harder to read; the function is pushing 200 lines now.

Quoted 12 lines

Lorenzo Stoakes (4):
mm/mmap/vma_merge: further improve prev/next VMA naming mm/mmap/vma_merge: set next to NULL if not applicable mm/mmap/vma_merge: extend invariants, avoid invalid res, vma mm/mmap/vma_merge: be explicit about the non-mergeable case

 mm/mmap.c | 165 +++++++++++++++++++++++++++++++++++-------------------
 1 file changed, 107 insertions(+), 58 deletions(-)

--
2.39.2

#10 lore raw
Quoted 25 lines · Liam R. Howlett
Quoted 8 lines · Lorenzo Stoakes

Following on from Vlastimil Babka's patch series "cleanup vma_merge() and improve mergeability tests" which was in turn based on Liam's prior cleanups, this patch series introduces changes discussed in review of Vlastimil's series and goes further in attempting to make the logic as clear as possible.

Nearly all of this should have absolutely no functional impact, however it does add a singular VM_WARN_ON() case.

Thanks for looking at this function and adding more clarity. I'm happy to have comments within the code, especially tricky areas. But I find that adding almost 50 lines to this function makes it rather hard to follow.

Can we remove the more obvious comments and possibly reduce the nesting of others so there are less lines?

For example in patch 2:

        /*
         * If there is a previous VMA specified, find the next, otherwise find
         * the first.
         */
        vma = find_vma(mm, prev ? prev->vm_end : 0);
Quoted 18 lines

Is rather verbose for something that can be seen in the code itself.

I think we are risking over-documenting what is going on here which is making the code harder to read; the function is pushing 200 lines now.

Quoted 12 lines

Lorenzo Stoakes (4):
mm/mmap/vma_merge: further improve prev/next VMA naming mm/mmap/vma_merge: set next to NULL if not applicable mm/mmap/vma_merge: extend invariants, avoid invalid res, vma mm/mmap/vma_merge: be explicit about the non-mergeable case

 mm/mmap.c | 165 +++++++++++++++++++++++++++++++++++-------------------
 1 file changed, 107 insertions(+), 58 deletions(-)

--
2.39.2

Sure, I did try not to overdo things (once you start simplifying you can go too far), but it seems like I _did_ go too far on the commenting (perhaps pushing too far the other way).

I will simplify, remove things implied by the code and strip down + respin.