When mremap() moves a mapping around in memory, it goes to great lengths to
avoid having to walk page tables as this is expensive and
time-consuming.

Rather, if the VMA was faulted (that is vma->anon_vma != NULL), the virtual
page offset stored in the VMA at vma->vm_pgoff will remain the same, as
well all the folio indexes pointed at the associated anon_vma object.

This means the VMA and page tables can simply be moved and this affects the
change (and if we can move page tables at a higher page table level, this
is even faster).

While this is efficient, it does lead to big problems with VMA merging - in
essence it causes faulted anonymous VMAs to not be mergeable under many
circumstances once moved.

This is limiting and leads to both a proliferation of unreclaimable,
unmovable kernel metadata (VMAs, anon_vma's, anon_vma_chain's) and has an
impact on further use of mremap(), which has a requirement that the VMA
moved (which can also be a partial range within a VMA) may span only a
single VMA.

This makes the mergeability or not of VMAs in effect a uAPI concern.

In some use cases, users may wish to accept the overhead of actually going
to the trouble of updating VMAs and folios to affect mremap() moves. Let's
provide them with the choice.

This patch add a new MREMAP_RELOCATE_ANON flag to do just that, which
attempts to perform such an operation. If it is unable to do so, it cleanly
falls back to the usual method.

It carefully takes the rmap locks such that at no time will a racing rmap
user encounter incorrect or missing VMAs.

It is also designed to interact cleanly with the existing mremap() error
fallback mechanism (inverting the remap should the page table move fail).

Also, if we could merge cleanly without such a change, we do so, avoiding
the overhead of the operation if it is not required.

In the instance that no merge may occur when the move is performed, we
still perform the folio and VMA updates to ensure that future mremap() or
mprotect() calls will result in merges.

In this implementation, we simply give up if we encounter large folios. A
subsequent commit will extend the functionality to allow for these cases.

We restrict this flag to purely anonymous memory only.

we separate out the vma_had_uncowed_parents() helper function for checking
in should_relocate_anon() and introduce a vma_had_uncowed_children()
function for the same purpose.

We carefully check for pinned folios in case a caller who holds a pin might
make assumptions about index, mapping fields which we are about to
manipulate.

Signed-off-by: Lorenzo Stoakes <lorenzo.stoakes@oracle.com>
---
 include/uapi/linux/mman.h        |   1 +
 mm/internal.h                    |   1 +
 mm/mremap.c                      | 410 +++++++++++++++++++++++++++++--
 mm/vma.c                         |  78 ++++--
 mm/vma.h                         |  28 ++-
 tools/testing/vma/vma.c          |   5 +-
 tools/testing/vma/vma_internal.h |  33 +++
 7 files changed, 512 insertions(+), 44 deletions(-)

diff --git a/include/uapi/linux/mman.h b/include/uapi/linux/mman.h
index e89d00528f2f..d0542f872e0c 100644
--- a/include/uapi/linux/mman.h
+++ b/include/uapi/linux/mman.h
@@ -9,6 +9,7 @@
 #define MREMAP_MAYMOVE		1
 #define MREMAP_FIXED		2
 #define MREMAP_DONTUNMAP	4
+#define MREMAP_RELOCATE_ANON	8
 
 #define OVERCOMMIT_GUESS		0
 #define OVERCOMMIT_ALWAYS		1
diff --git a/mm/internal.h b/mm/internal.h
index 838f840ded83..a08863169bec 100644
--- a/mm/internal.h
+++ b/mm/internal.h
@@ -46,6 +46,7 @@ struct folio_batch;
 struct pagetable_move_control {
 	struct vm_area_struct *old; /* Source VMA. */
 	struct vm_area_struct *new; /* Destination VMA. */
+	struct vm_area_struct *relocate_locked; /* VMA which is rmap locked. */
 	unsigned long old_addr; /* Address from which the move begins. */
 	unsigned long old_end; /* Exclusive address at which old range ends. */
 	unsigned long new_addr; /* Address to move page tables to. */
diff --git a/mm/mremap.c b/mm/mremap.c
index 7db9da609c84..1d915445026f 100644
--- a/mm/mremap.c
+++ b/mm/mremap.c
@@ -71,6 +71,15 @@ struct vma_remap_struct {
 	unsigned long charged;		/* If VM_ACCOUNT, # pages to account. */
 };
 
+/* Represents local PTE state. */
+struct pte_state {
+	unsigned long old_addr;
+	unsigned long new_addr;
+	unsigned long old_end;
+	pte_t *ptep;
+	spinlock_t *ptl;
+};
+
 static pud_t *get_old_pud(struct mm_struct *mm, unsigned long addr)
 {
 	pgd_t *pgd;
@@ -139,18 +148,50 @@ static pmd_t *alloc_new_pmd(struct mm_struct *mm, unsigned long addr)
 	return pmd;
 }
 
-static void take_rmap_locks(struct vm_area_struct *vma)
+/*
+ * Determine whether the old and new VMAs share the same anon_vma. If so, this
+ * has implications around locking and to avoid deadlock we need to tread
+ * carefully.
+ */
+static bool has_shared_anon_vma(struct pagetable_move_control *pmc)
+{
+	struct vm_area_struct *vma = pmc->old;
+	struct vm_area_struct *locked = pmc->relocate_locked;
+
+	if (!locked)
+		return false;
+
+	return vma->anon_vma->root == locked->anon_vma->root;
+}
+
+static void maybe_take_rmap_locks(struct pagetable_move_control *pmc)
 {
+	struct vm_area_struct *vma;
+	struct anon_vma *anon_vma;
+
+	if (!pmc->need_rmap_locks)
+		return;
+
+	vma = pmc->old;
+	anon_vma = vma->anon_vma;
 	if (vma->vm_file)
 		i_mmap_lock_write(vma->vm_file->f_mapping);
-	if (vma->anon_vma)
-		anon_vma_lock_write(vma->anon_vma);
+	if (anon_vma && !has_shared_anon_vma(pmc))
+		anon_vma_lock_write(anon_vma);
 }
 
-static void drop_rmap_locks(struct vm_area_struct *vma)
+static void maybe_drop_rmap_locks(struct pagetable_move_control *pmc)
 {
-	if (vma->anon_vma)
-		anon_vma_unlock_write(vma->anon_vma);
+	struct vm_area_struct *vma;
+	struct anon_vma *anon_vma;
+
+	if (!pmc->need_rmap_locks)
+		return;
+
+	vma = pmc->old;
+	anon_vma = vma->anon_vma;
+	if (anon_vma && !has_shared_anon_vma(pmc))
+		anon_vma_unlock_write(anon_vma);
 	if (vma->vm_file)
 		i_mmap_unlock_write(vma->vm_file->f_mapping);
 }
@@ -204,8 +245,7 @@ static int move_ptes(struct pagetable_move_control *pmc,
 	 *   serialize access to individual ptes, but only rmap traversal
 	 *   order guarantees that we won't miss both the old and new ptes).
 	 */
-	if (pmc->need_rmap_locks)
-		take_rmap_locks(vma);
+	maybe_take_rmap_locks(pmc);
 
 	/*
 	 * We don't have to worry about the ordering of src and dst
@@ -278,8 +318,7 @@ static int move_ptes(struct pagetable_move_control *pmc,
 	pte_unmap(new_pte - 1);
 	pte_unmap_unlock(old_pte - 1, old_ptl);
 out:
-	if (pmc->need_rmap_locks)
-		drop_rmap_locks(vma);
+	maybe_drop_rmap_locks(pmc);
 	return err;
 }
 
@@ -537,15 +576,14 @@ static __always_inline unsigned long get_extent(enum pgt_entry entry,
  * Should move_pgt_entry() acquire the rmap locks? This is either expressed in
  * the PMC, or overridden in the case of normal, larger page tables.
  */
-static bool should_take_rmap_locks(struct pagetable_move_control *pmc,
-				   enum pgt_entry entry)
+static bool should_take_rmap_locks(enum pgt_entry entry)
 {
 	switch (entry) {
 	case NORMAL_PMD:
 	case NORMAL_PUD:
 		return true;
 	default:
-		return pmc->need_rmap_locks;
+		return false;
 	}
 }
 
@@ -557,11 +595,15 @@ static bool move_pgt_entry(struct pagetable_move_control *pmc,
 			   enum pgt_entry entry, void *old_entry, void *new_entry)
 {
 	bool moved = false;
-	bool need_rmap_locks = should_take_rmap_locks(pmc, entry);
+	bool override_locks = false;
 
-	/* See comment in move_ptes() */
-	if (need_rmap_locks)
-		take_rmap_locks(pmc->old);
+	if (!pmc->need_rmap_locks && should_take_rmap_locks(entry)) {
+		override_locks = true;
+
+		pmc->need_rmap_locks = true;
+		/* See comment in move_ptes() */
+		maybe_take_rmap_locks(pmc);
+	}
 
 	switch (entry) {
 	case NORMAL_PMD:
@@ -585,8 +627,9 @@ static bool move_pgt_entry(struct pagetable_move_control *pmc,
 		break;
 	}
 
-	if (need_rmap_locks)
-		drop_rmap_locks(pmc->old);
+	maybe_drop_rmap_locks(pmc);
+	if (override_locks)
+		pmc->need_rmap_locks = false;
 
 	return moved;
 }
@@ -752,6 +795,209 @@ static unsigned long pmc_progress(struct pagetable_move_control *pmc)
 	return old_addr < orig_old_addr ? 0 : old_addr - orig_old_addr;
 }
 
+/*
+ * If the folio mapped at the specified pte entry can have its index and mapping
+ * relocated, then do so.
+ *
+ * Returns the number of pages we have traversed, or 0 if the operation failed.
+ */
+static unsigned long relocate_anon_pte(struct pagetable_move_control *pmc,
+		struct pte_state *state, bool undo)
+{
+	struct folio *folio;
+	struct vm_area_struct *old, *new;
+	pgoff_t new_index;
+	pte_t pte;
+	unsigned long ret = 1;
+	unsigned long old_addr = state->old_addr;
+	unsigned long new_addr = state->new_addr;
+
+	old = pmc->old;
+	new = pmc->new;
+
+	pte = ptep_get(state->ptep);
+
+	/* Ensure we have truly got an anon folio. */
+	folio = vm_normal_folio(old, old_addr, pte);
+	if (!folio)
+		return ret;
+
+	folio_lock(folio);
+
+	/* No-op. */
+	if (!folio_test_anon(folio) || folio_test_ksm(folio))
+		goto out;
+
+	/*
+	 * This should never be the case as we have already checked to ensure
+	 * that the anon_vma is not forked, and we have just asserted that it is
+	 * anonymous.
+	 */
+	if (WARN_ON_ONCE(folio_maybe_mapped_shared(folio)))
+		goto out;
+	/* The above check should imply these. */
+	VM_WARN_ON_ONCE(folio_mapcount(folio) > folio_nr_pages(folio));
+	VM_WARN_ON_ONCE(!PageAnonExclusive(folio_page(folio, 0)));
+
+	/*
+	 * A pinned folio implies that it will be used for a duration longer
+	 * than that over which the mmap_lock is held, meaning that another part
+	 * of the kernel may be making use of this folio.
+	 *
+	 * Since we are about to manipulate index & mapping fields, we cannot
+	 * safely proceed because whatever has pinned this folio may then
+	 * incorrectly assume these do not change.
+	 */
+	if (folio_maybe_dma_pinned(folio))
+		goto out;
+
+	/*
+	 * This should not happen as we explicitly disallow this, but check
+	 * anyway.
+	 */
+	if (folio_test_large(folio)) {
+		ret = 0;
+		goto out;
+	}
+
+	if (!undo)
+		new_index = linear_page_index(new, new_addr);
+	else
+		new_index = linear_page_index(old, old_addr);
+
+	/*
+	 * The PTL should keep us safe from unmapping, and the fact the folio is
+	 * a PTE keeps the folio referenced.
+	 *
+	 * The mmap/VMA locks should keep us safe from fork and other processes.
+	 *
+	 * The rmap locks should keep us safe from anything happening to the
+	 * VMA/anon_vma.
+	 *
+	 * The folio lock should keep us safe from reclaim, migration, etc.
+	 */
+	folio_move_anon_rmap(folio, undo ? old : new);
+	WRITE_ONCE(folio->index, new_index);
+
+out:
+	folio_unlock(folio);
+	return ret;
+}
+
+static bool pte_done(struct pte_state *state)
+{
+	return state->old_addr >= state->old_end;
+}
+
+static void pte_next(struct pte_state *state, unsigned long nr_pages)
+{
+	state->old_addr += nr_pages * PAGE_SIZE;
+	state->new_addr += nr_pages * PAGE_SIZE;
+	state->ptep += nr_pages;
+}
+
+static bool relocate_anon_ptes(struct pagetable_move_control *pmc,
+		unsigned long extent, pmd_t *pmdp, bool undo)
+{
+	struct mm_struct *mm = current->mm;
+	struct pte_state state = {
+		.old_addr = pmc->old_addr,
+		.new_addr = pmc->new_addr,
+		.old_end = pmc->old_addr + extent,
+	};
+	pte_t *ptep_start;
+	bool ret;
+	unsigned long nr_pages;
+
+	ptep_start = pte_offset_map_lock(mm, pmdp, pmc->old_addr, &state.ptl);
+	/*
+	 * We prevent faults with mmap write lock, hold the rmap lock and should
+	 * not fail to obtain this lock. Just give up if we can't.
+	 */
+	if (!ptep_start)
+		return false;
+
+	state.ptep = ptep_start;
+	for (; !pte_done(&state); pte_next(&state, nr_pages)) {
+		pte_t pte = ptep_get(state.ptep);
+
+		if (pte_none(pte) || !pte_present(pte)) {
+			nr_pages = 1;
+			continue;
+		}
+
+		nr_pages = relocate_anon_pte(pmc, &state, undo);
+		if (!nr_pages) {
+			ret = false;
+			goto out;
+		}
+	}
+
+	ret = true;
+out:
+	pte_unmap_unlock(ptep_start, state.ptl);
+	return ret;
+}
+
+static bool __relocate_anon_folios(struct pagetable_move_control *pmc, bool undo)
+{
+	pud_t *pudp;
+	pmd_t *pmdp;
+	unsigned long extent;
+	struct mm_struct *mm = current->mm;
+
+	if (!pmc->len_in)
+		return true;
+
+	for (; !pmc_done(pmc); pmc_next(pmc, extent)) {
+		pmd_t pmd;
+		pud_t pud;
+
+		extent = get_extent(NORMAL_PUD, pmc);
+
+		pudp = get_old_pud(mm, pmc->old_addr);
+		if (!pudp)
+			continue;
+		pud = pudp_get(pudp);
+
+		if (pud_trans_huge(pud) || pud_devmap(pud))
+			return false;
+
+		extent = get_extent(NORMAL_PMD, pmc);
+		pmdp = get_old_pmd(mm, pmc->old_addr);
+		if (!pmdp)
+			continue;
+		pmd = pmdp_get(pmdp);
+
+		if (is_swap_pmd(pmd) || pmd_trans_huge(pmd) ||
+		    pmd_devmap(pmd))
+			return false;
+
+		if (pmd_none(pmd))
+			continue;
+
+		if (!relocate_anon_ptes(pmc, extent, pmdp, undo))
+			return false;
+	}
+
+	return true;
+}
+
+static bool relocate_anon_folios(struct pagetable_move_control *pmc, bool undo)
+{
+	unsigned long old_addr = pmc->old_addr;
+	unsigned long new_addr = pmc->new_addr;
+	bool ret;
+
+	ret = __relocate_anon_folios(pmc, undo);
+
+	/* Reset state ready for retry. */
+	pmc->old_addr = old_addr;
+	pmc->new_addr = new_addr;
+
+	return ret;
+}
+
 unsigned long move_page_tables(struct pagetable_move_control *pmc)
 {
 	unsigned long extent;
@@ -1132,6 +1378,74 @@ static void unmap_source_vma(struct vma_remap_struct *vrm)
 	}
 }
 
+/*
+ * Should we attempt to relocate anonymous folios to the location that the VMA
+ * is being moved to by updating index and mapping fields accordingly?
+ */
+static bool should_relocate_anon(struct vma_remap_struct *vrm,
+	struct pagetable_move_control *pmc)
+{
+	struct vm_area_struct *old = vrm->vma;
+
+	/* Currently we only do this if requested. */
+	if (!(vrm->flags & MREMAP_RELOCATE_ANON))
+		return false;
+
+	/* We can't deal with special or hugetlb mappings. */
+	if (old->vm_flags & (VM_SPECIAL | VM_HUGETLB))
+		return false;
+
+	/* We only support anonymous mappings. */
+	if (!vma_is_anonymous(old))
+		return false;
+
+	/* If no folios are mapped, then no need to attempt this. */
+	if (!old->anon_vma)
+		return false;
+
+	/*
+	 * If the VMA is referenced by a parent process (i.e. is the child of a
+	 * fork) or exists in a process which has been forked, then the folio
+	 * may be non-exclusively mapped, and thus is non-relocatable.
+	 *
+	 * Note the uncowed children check is sufficient, because we hold the
+	 * mmap lock.
+	 */
+	if (vma_had_uncowed_parents(old) || vma_had_uncowed_children(old))
+		return false;
+
+	/* Otherwise, we're good to go! */
+	return true;
+}
+
+static void lock_new_anon_vma(struct vm_area_struct *new_vma)
+{
+	/*
+	 * We have a new VMA to reassign folios to. We take a lock on
+	 * its anon_vma so reclaim doesn't fail to unmap mappings.
+	 *
+	 * We have acquired a VMA write lock by now (in vma_link()), so
+	 * we do not have to worry about racing faults.
+	 *
+	 * NOTE: we do NOT need to acquire an rmap lock on the old VMA,
+	 * as forks require an mmap write lock, which we hold.
+	 */
+	anon_vma_lock_write(new_vma->anon_vma);
+
+	/*
+	 * lockdep is unable to differentiate between the anon_vma lock we take
+	 * in the old VMA and the one we are taking here in the new VMA.
+	 *
+	 * In each instance where the old VMA might have its anon_vma
+	 * lock taken, we explicitly check to ensure they are not one
+	 * and the same, avoiding deadlock.
+	 *
+	 * Express this to lockdep through a subclass.
+	 */
+	lock_set_subclass(&new_vma->anon_vma->root->rwsem.dep_map, 1,
+			  _THIS_IP_);
+}
+
 /*
  * Copy vrm->vma over to vrm->new_addr possibly adjusting size as part of the
  * process. Additionally handle an error occurring on moving of page tables,
@@ -1151,9 +1465,11 @@ static int copy_vma_and_data(struct vma_remap_struct *vrm,
 	struct vm_area_struct *new_vma;
 	int err = 0;
 	PAGETABLE_MOVE(pmc, NULL, NULL, vrm->addr, vrm->new_addr, vrm->old_len);
+	bool relocate_anon = should_relocate_anon(vrm, &pmc);
 
+again:
 	new_vma = copy_vma(&vma, vrm->new_addr, vrm->new_len, new_pgoff,
-			   &pmc.need_rmap_locks);
+			   &pmc.need_rmap_locks, &relocate_anon);
 	if (!new_vma) {
 		vrm_uncharge(vrm);
 		*new_vma_ptr = NULL;
@@ -1163,12 +1479,59 @@ static int copy_vma_and_data(struct vma_remap_struct *vrm,
 	pmc.old = vma;
 	pmc.new = new_vma;
 
+	if (relocate_anon) {
+		lock_new_anon_vma(new_vma);
+		pmc.relocate_locked = new_vma;
+
+		if (!relocate_anon_folios(&pmc, /* undo= */false)) {
+			unsigned long start = new_vma->vm_start;
+			unsigned long size = new_vma->vm_end - start;
+
+			/* Undo if fails. */
+			relocate_anon_folios(&pmc, /* undo= */true);
+			vrm_stat_account(vrm, vrm->new_len);
+
+			anon_vma_unlock_write(new_vma->anon_vma);
+			pmc.relocate_locked = NULL;
+
+			do_munmap(current->mm, start, size, NULL);
+			relocate_anon = false;
+			goto again;
+		}
+	}
+
 	moved_len = move_page_tables(&pmc);
 	if (moved_len < vrm->old_len)
 		err = -ENOMEM;
 	else if (vma->vm_ops && vma->vm_ops->mremap)
 		err = vma->vm_ops->mremap(new_vma);
 
+	if (unlikely(err && relocate_anon)) {
+		relocate_anon_folios(&pmc, /* undo= */true);
+		anon_vma_unlock_write(new_vma->anon_vma);
+		pmc.relocate_locked = NULL;
+	} else if (relocate_anon /* && !err */) {
+		unsigned long addr = vrm->new_addr;
+		unsigned long end = addr + vrm->new_len;
+		VMA_ITERATOR(vmi, vma->vm_mm, addr);
+		VMG_VMA_STATE(vmg, &vmi, NULL, new_vma, addr, end);
+		struct vm_area_struct *merged;
+
+		/*
+		 * Now we have successfully copied page tables and set up
+		 * folios, we can safely drop the anon_vma lock.
+		 */
+		anon_vma_unlock_write(new_vma->anon_vma);
+		pmc.relocate_locked = NULL;
+
+		/* Let's try merge again... */
+		vmg.prev = vma_prev(&vmi);
+		vma_next(&vmi);
+		merged = vma_merge_existing_range(&vmg);
+		if (merged)
+			new_vma = merged;
+	}
+
 	if (unlikely(err)) {
 		PAGETABLE_MOVE(pmc_revert, new_vma, vma, vrm->new_addr,
 			       vrm->addr, moved_len);
@@ -1486,7 +1849,8 @@ static unsigned long check_mremap_params(struct vma_remap_struct *vrm)
 	unsigned long flags = vrm->flags;
 
 	/* Ensure no unexpected flag values. */
-	if (flags & ~(MREMAP_FIXED | MREMAP_MAYMOVE | MREMAP_DONTUNMAP))
+	if (flags & ~(MREMAP_FIXED | MREMAP_MAYMOVE | MREMAP_DONTUNMAP |
+		      MREMAP_RELOCATE_ANON))
 		return -EINVAL;
 
 	/* Start address must be page-aligned. */
@@ -1501,6 +1865,10 @@ static unsigned long check_mremap_params(struct vma_remap_struct *vrm)
 	if (!PAGE_ALIGN(vrm->new_len))
 		return -EINVAL;
 
+	/* We can't relocate without allowing a move. */
+	if ((flags & MREMAP_RELOCATE_ANON) && !(flags & MREMAP_MAYMOVE))
+		return -EINVAL;
+
 	/* Remainder of checks are for cases with specific new_addr. */
 	if (!vrm_implies_new_addr(vrm))
 		return 0;
diff --git a/mm/vma.c b/mm/vma.c
index 8a6c5e835759..59a7a9273d53 100644
--- a/mm/vma.c
+++ b/mm/vma.c
@@ -57,22 +57,6 @@ struct mmap_state {
 		.state = VMA_MERGE_START,				\
 	}
 
-/*
- * If, at any point, the VMA had unCoW'd mappings from parents, it will maintain
- * more than one anon_vma_chain connecting it to more than one anon_vma. A merge
- * would mean a wider range of folios sharing the root anon_vma lock, and thus
- * potential lock contention, we do not wish to encourage merging such that this
- * scales to a problem.
- */
-static bool vma_had_uncowed_parents(struct vm_area_struct *vma)
-{
-	/*
-	 * The list_is_singular() test is to avoid merging VMA cloned from
-	 * parents. This can improve scalability caused by anon_vma lock.
-	 */
-	return vma && vma->anon_vma && !list_is_singular(&vma->anon_vma_chain);
-}
-
 static inline bool is_mergeable_vma(struct vma_merge_struct *vmg, bool merge_next)
 {
 	struct vm_area_struct *vma = merge_next ? vmg->next : vmg->prev;
@@ -783,8 +767,7 @@ static bool can_merge_remove_vma(struct vm_area_struct *vma)
  * - The caller must hold a WRITE lock on the mm_struct->mmap_lock.
  * - vmi must be positioned within [@vmg->middle->vm_start, @vmg->middle->vm_end).
  */
-static __must_check struct vm_area_struct *vma_merge_existing_range(
-		struct vma_merge_struct *vmg)
+struct vm_area_struct *vma_merge_existing_range(struct vma_merge_struct *vmg)
 {
 	struct vm_area_struct *middle = vmg->middle;
 	struct vm_area_struct *prev = vmg->prev;
@@ -1799,7 +1782,7 @@ int vma_link(struct mm_struct *mm, struct vm_area_struct *vma)
  */
 struct vm_area_struct *copy_vma(struct vm_area_struct **vmap,
 	unsigned long addr, unsigned long len, pgoff_t pgoff,
-	bool *need_rmap_locks)
+	bool *need_rmap_locks, bool *relocate_anon)
 {
 	struct vm_area_struct *vma = *vmap;
 	unsigned long vma_start = vma->vm_start;
@@ -1825,7 +1808,19 @@ struct vm_area_struct *copy_vma(struct vm_area_struct **vmap,
 	vmg.middle = NULL; /* New VMA range. */
 	vmg.pgoff = pgoff;
 	vmg.next = vma_iter_next_rewind(&vmi, NULL);
+
 	new_vma = vma_merge_new_range(&vmg);
+	if (*relocate_anon) {
+		/*
+		 * If merge succeeds, no need to relocate. Otherwise, reset
+		 * pgoff for newly established VMA which we will relocate folios
+		 * to.
+		 */
+		if (new_vma)
+			*relocate_anon = false;
+		else
+			pgoff = addr >> PAGE_SHIFT;
+	}
 
 	if (new_vma) {
 		/*
@@ -1856,7 +1851,9 @@ struct vm_area_struct *copy_vma(struct vm_area_struct **vmap,
 		vma_set_range(new_vma, addr, addr + len, pgoff);
 		if (vma_dup_policy(vma, new_vma))
 			goto out_free_vma;
-		if (anon_vma_clone(new_vma, vma))
+		if (*relocate_anon)
+			new_vma->anon_vma = NULL;
+		else if (anon_vma_clone(new_vma, vma))
 			goto out_free_mempol;
 		if (new_vma->vm_file)
 			get_file(new_vma->vm_file);
@@ -1864,6 +1861,21 @@ struct vm_area_struct *copy_vma(struct vm_area_struct **vmap,
 			new_vma->vm_ops->open(new_vma);
 		if (vma_link(mm, new_vma))
 			goto out_vma_link;
+		/*
+		 * If we're attempting to relocate anonymous VMAs, we
+		 * don't want to reuse an anon_vma as set by
+		 * vm_area_dup(), or copy anon_vma_chain or anything
+		 * like this.
+		 */
+		if (*relocate_anon && __anon_vma_prepare(new_vma)) {
+			/*
+			 * We have already linked this VMA, so we must now unmap
+			 * it to unwind this. This is best effort.
+			 */
+			do_munmap(mm, addr, len, NULL);
+			return NULL;
+		}
+
 		*need_rmap_locks = false;
 	}
 	return new_vma;
@@ -3052,3 +3064,29 @@ int __vm_munmap(unsigned long start, size_t len, bool unlock)
 	userfaultfd_unmap_complete(mm, &uf);
 	return ret;
 }
+
+bool vma_had_uncowed_children(struct vm_area_struct *vma)
+{
+	struct anon_vma *anon_vma = vma ? vma->anon_vma : NULL;
+	bool ret;
+
+	if (!anon_vma)
+		return false;
+
+	/*
+	 * If we're mmap locked then there's no way for this count to change, as
+	 * any such change would require this lock not be held.
+	 */
+	if (rwsem_is_locked(&vma->vm_mm->mmap_lock))
+		return anon_vma->num_children > 1;
+
+	/*
+	 * Any change that would increase the number of children would be
+	 * prevented by a read lock.
+	 */
+	anon_vma_lock_read(anon_vma);
+	ret = anon_vma->num_children > 1;
+	anon_vma_unlock_read(anon_vma);
+
+	return ret;
+}
diff --git a/mm/vma.h b/mm/vma.h
index 149926e8a6d1..954bacedbb48 100644
--- a/mm/vma.h
+++ b/mm/vma.h
@@ -267,6 +267,9 @@ __must_check struct vm_area_struct
 __must_check struct vm_area_struct
 *vma_merge_new_range(struct vma_merge_struct *vmg);
 
+__must_check struct vm_area_struct
+*vma_merge_existing_range(struct vma_merge_struct *vmg);
+
 __must_check struct vm_area_struct
 *vma_merge_extend(struct vma_iterator *vmi,
 		  struct vm_area_struct *vma,
@@ -287,7 +290,7 @@ int vma_link(struct mm_struct *mm, struct vm_area_struct *vma);
 
 struct vm_area_struct *copy_vma(struct vm_area_struct **vmap,
 	unsigned long addr, unsigned long len, pgoff_t pgoff,
-	bool *need_rmap_locks);
+	bool *need_rmap_locks, bool *relocate_anon);
 
 struct anon_vma *find_mergeable_anon_vma(struct vm_area_struct *vma);
 
@@ -505,6 +508,29 @@ struct vm_area_struct *vma_iter_next_rewind(struct vma_iterator *vmi,
 	return next;
 }
 
+/*
+ * If, at any point, the VMA had unCoW'd mappings from parents, it will maintain
+ * more than one anon_vma_chain connecting it to more than one anon_vma. A merge
+ * would mean a wider range of folios sharing the root anon_vma lock, and thus
+ * potential lock contention, we do not wish to encourage merging such that this
+ * scales to a problem.
+ */
+static inline bool vma_had_uncowed_parents(struct vm_area_struct *vma)
+{
+	/*
+	 * The list_is_singular() test is to avoid merging VMA cloned from
+	 * parents. This can improve scalability caused by anon_vma lock.
+	 */
+	return vma && vma->anon_vma && !list_is_singular(&vma->anon_vma_chain);
+}
+
+/*
+ * If, at any point, folios mapped by the VMA had unCoW'd mappings potentially
+ * present in child processes forked from this one, then the underlying mapped
+ * folios may be non-exclusively mapped.
+ */
+bool vma_had_uncowed_children(struct vm_area_struct *vma);
+
 #ifdef CONFIG_64BIT
 
 static inline bool vma_is_sealed(struct vm_area_struct *vma)
diff --git a/tools/testing/vma/vma.c b/tools/testing/vma/vma.c
index 7cfd6e31db10..3d19df8fa17b 100644
--- a/tools/testing/vma/vma.c
+++ b/tools/testing/vma/vma.c
@@ -1543,13 +1543,14 @@ static bool test_copy_vma(void)
 	unsigned long flags = VM_READ | VM_WRITE | VM_MAYREAD | VM_MAYWRITE;
 	struct mm_struct mm = {};
 	bool need_locks = false;
+	bool relocate_anon = false;
 	VMA_ITERATOR(vmi, &mm, 0);
 	struct vm_area_struct *vma, *vma_new, *vma_next;
 
 	/* Move backwards and do not merge. */
 
 	vma = alloc_and_link_vma(&mm, 0x3000, 0x5000, 3, flags);
-	vma_new = copy_vma(&vma, 0, 0x2000, 0, &need_locks);
+	vma_new = copy_vma(&vma, 0, 0x2000, 0, &need_locks, &relocate_anon);
 	ASSERT_NE(vma_new, vma);
 	ASSERT_EQ(vma_new->vm_start, 0);
 	ASSERT_EQ(vma_new->vm_end, 0x2000);
@@ -1562,7 +1563,7 @@ static bool test_copy_vma(void)
 
 	vma = alloc_and_link_vma(&mm, 0, 0x2000, 0, flags);
 	vma_next = alloc_and_link_vma(&mm, 0x6000, 0x8000, 6, flags);
-	vma_new = copy_vma(&vma, 0x4000, 0x2000, 4, &need_locks);
+	vma_new = copy_vma(&vma, 0x4000, 0x2000, 4, &need_locks, &relocate_anon);
 	vma_assert_attached(vma_new);
 
 	ASSERT_EQ(vma_new, vma_next);
diff --git a/tools/testing/vma/vma_internal.h b/tools/testing/vma/vma_internal.h
index 572ab2cea763..3364cd9cabde 100644
--- a/tools/testing/vma/vma_internal.h
+++ b/tools/testing/vma/vma_internal.h
@@ -26,6 +26,7 @@
 #include <linux/mm.h>
 #include <linux/rbtree.h>
 #include <linux/refcount.h>
+#include <linux/rwsem.h>
 
 extern unsigned long stack_guard_gap;
 #ifdef CONFIG_MMU
@@ -172,6 +173,8 @@ struct anon_vma {
 	struct anon_vma *root;
 	struct rb_root_cached rb_root;
 
+	unsigned long num_children;
+
 	/* Test fields. */
 	bool was_cloned;
 	bool was_unlinked;
@@ -227,6 +230,8 @@ struct mm_struct {
 	unsigned long def_flags;
 
 	unsigned long flags; /* Must use atomic bitops to access */
+
+	struct rw_semaphore mmap_lock;
 };
 
 struct file {
@@ -1240,4 +1245,32 @@ static inline int mapping_map_writable(struct address_space *mapping)
 	return 0;
 }
 
+static int do_munmap(struct mm_struct *mm, unsigned long start, size_t len,
+		struct list_head *uf)
+{
+	(void)mm;
+	(void)start;
+	(void)len;
+	(void)uf;
+
+	return 0;
+}
+
+static inline int rwsem_is_locked(struct rw_semaphore *sem)
+{
+	(void)sem;
+
+	return 0;
+}
+
+static inline void anon_vma_lock_read(struct anon_vma *anon_vma)
+{
+	(void)anon_vma;
+}
+
+static inline void anon_vma_unlock_read(struct anon_vma *anon_vma)
+{
+	(void)anon_vma;
+}
+
 #endif	/* __MM_VMA_INTERNAL_H */
-- 
2.49.0

On Tue, Apr 22, 2025 at 09:09:20AM +0100, Lorenzo Stoakes wrote:
[...]
>+bool vma_had_uncowed_children(struct vm_area_struct *vma)
>+{
>+	struct anon_vma *anon_vma = vma ? vma->anon_vma : NULL;
>+	bool ret;
>+
>+	if (!anon_vma)
>+		return false;
>+
>+	/*
>+	 * If we're mmap locked then there's no way for this count to change, as
>+	 * any such change would require this lock not be held.
>+	 */
>+	if (rwsem_is_locked(&vma->vm_mm->mmap_lock))
>+		return anon_vma->num_children > 1;

Hi, Lorenzo

May I have a question here?

>+
>+	/*
>+	 * Any change that would increase the number of children would be
>+	 * prevented by a read lock.
>+	 */
>+	anon_vma_lock_read(anon_vma);
>+	ret = anon_vma->num_children > 1;
>+	anon_vma_unlock_read(anon_vma);
>+
>+	return ret;
>+}

-- 
Wei Yang
Help you, Help me

On Wed, Apr 30, 2025 at 12:47:03AM +0000, Wei Yang wrote:
> On Tue, Apr 22, 2025 at 09:09:20AM +0100, Lorenzo Stoakes wrote:
> [...]
> >+bool vma_had_uncowed_children(struct vm_area_struct *vma)
> >+{
> >+	struct anon_vma *anon_vma = vma ? vma->anon_vma : NULL;
> >+	bool ret;
> >+
> >+	if (!anon_vma)
> >+		return false;
> >+
> >+	/*
> >+	 * If we're mmap locked then there's no way for this count to change, as
> >+	 * any such change would require this lock not be held.
> >+	 */
> >+	if (rwsem_is_locked(&vma->vm_mm->mmap_lock))
> >+		return anon_vma->num_children > 1;
>
> Hi, Lorenzo
>
> May I have a question here?

Just ask the question.

However, with respect, the last drive-by review you gave was not helpful,
so I strongly suggest that this is not a great use of your time.

Again, I _strongly_ suggest you focus on bug fixes or the like.

Thanks.

>
> >+
> >+	/*
> >+	 * Any change that would increase the number of children would be
> >+	 * prevented by a read lock.
> >+	 */
> >+	anon_vma_lock_read(anon_vma);
> >+	ret = anon_vma->num_children > 1;
> >+	anon_vma_unlock_read(anon_vma);
> >+
> >+	return ret;
> >+}
>
> --
> Wei Yang
> Help you, Help me

On Wed, Apr 30, 2025 at 02:15:24PM +0100, Lorenzo Stoakes wrote:
>On Wed, Apr 30, 2025 at 12:47:03AM +0000, Wei Yang wrote:
>> On Tue, Apr 22, 2025 at 09:09:20AM +0100, Lorenzo Stoakes wrote:
>> [...]
>> >+bool vma_had_uncowed_children(struct vm_area_struct *vma)
>> >+{
>> >+	struct anon_vma *anon_vma = vma ? vma->anon_vma : NULL;
>> >+	bool ret;
>> >+
>> >+	if (!anon_vma)
>> >+		return false;
>> >+
>> >+	/*
>> >+	 * If we're mmap locked then there's no way for this count to change, as
>> >+	 * any such change would require this lock not be held.
>> >+	 */
>> >+	if (rwsem_is_locked(&vma->vm_mm->mmap_lock))
>> >+		return anon_vma->num_children > 1;
>>
>> Hi, Lorenzo
>>
>> May I have a question here?
>
>Just ask the question.
>

Thanks.

My question is the function is expected to return true, if we have forked a
vma from this one, right?

IMO there are cases when it has one forked child and anon_vma->num_children == 1,
which means folios are not exclusively mapped. But the function would return
false.

Or maybe I misunderstand the logic here.

>However, with respect, the last drive-by review you gave was not helpful,
>so I strongly suggest that this is not a great use of your time.
>
>Again, I _strongly_ suggest you focus on bug fixes or the like.

Thanks for your suggestion and patience. I would try to focus on bugs and skip
those subtle things.

>
>Thanks.
>
>>
>> >+
>> >+	/*
>> >+	 * Any change that would increase the number of children would be
>> >+	 * prevented by a read lock.
>> >+	 */
>> >+	anon_vma_lock_read(anon_vma);
>> >+	ret = anon_vma->num_children > 1;
>> >+	anon_vma_unlock_read(anon_vma);
>> >+
>> >+	return ret;
>> >+}
>>
>> --
>> Wei Yang
>> Help you, Help me

-- 
Wei Yang
Help you, Help me

On Wed, Apr 30, 2025 at 03:41:19PM +0000, Wei Yang wrote:
> On Wed, Apr 30, 2025 at 02:15:24PM +0100, Lorenzo Stoakes wrote:
> >On Wed, Apr 30, 2025 at 12:47:03AM +0000, Wei Yang wrote:
> >> On Tue, Apr 22, 2025 at 09:09:20AM +0100, Lorenzo Stoakes wrote:
> >> [...]
> >> >+bool vma_had_uncowed_children(struct vm_area_struct *vma)
> >> >+{
> >> >+	struct anon_vma *anon_vma = vma ? vma->anon_vma : NULL;
> >> >+	bool ret;
> >> >+
> >> >+	if (!anon_vma)
> >> >+		return false;
> >> >+
> >> >+	/*
> >> >+	 * If we're mmap locked then there's no way for this count to change, as
> >> >+	 * any such change would require this lock not be held.
> >> >+	 */
> >> >+	if (rwsem_is_locked(&vma->vm_mm->mmap_lock))
> >> >+		return anon_vma->num_children > 1;
> >>
> >> Hi, Lorenzo
> >>
> >> May I have a question here?
> >
> >Just ask the question.
> >
>
> Thanks.
>
> My question is the function is expected to return true, if we have forked a
> vma from this one, right?
>
> IMO there are cases when it has one forked child and anon_vma->num_children == 1,
> which means folios are not exclusively mapped. But the function would return
> false.
>
> Or maybe I misunderstand the logic here.

I mean, it'd be helpful if you delineated which cases these were?

Presumably you're thiking of something like:

1. Process 1: VMA A is established. num_children == 1 (self-reference is counted).
2. Process 2: Process 1 forks, VMA B references A, a->num_children++
3. Process 3: Process 2 forks, VMA C is established (maybe you think b->num_children++?)
4. Unmap vma B, oops, a->num_children == 1 but it still has C!

But that won't happen, as VMA C will be referencing a->anon_vma, so in reality
a->anon_vma->num_children == 3, then after unmap == 2.

References to the originally faulted-in anon_vma is propagated through the
forks.

anon_vma logic is tricky, one of many reasons I want to (significantly) rework
it.

Though sadly there is a lot of _essential_ complexity, I do think we can do
better.

>
> >However, with respect, the last drive-by review you gave was not helpful,
> >so I strongly suggest that this is not a great use of your time.
> >
> >Again, I _strongly_ suggest you focus on bug fixes or the like.
>
> Thanks for your suggestion and patience. I would try to focus on bugs and skip
> those subtle things.

Thanks, you've contributed good bug reports in the past, I'm not just
recommending this for no reason! :)

David's suggested tests are also a positive way forward.

Thanks, Lorenzo

>
> >
> >Thanks.
> >
> >>
> >> >+
> >> >+	/*
> >> >+	 * Any change that would increase the number of children would be
> >> >+	 * prevented by a read lock.
> >> >+	 */
> >> >+	anon_vma_lock_read(anon_vma);
> >> >+	ret = anon_vma->num_children > 1;
> >> >+	anon_vma_unlock_read(anon_vma);
> >> >+
> >> >+	return ret;
> >> >+}
> >>
> >> --
> >> Wei Yang
> >> Help you, Help me
>
> --
> Wei Yang
> Help you, Help me

On Wed, Apr 30, 2025 at 05:07:40PM +0100, Lorenzo Stoakes wrote:
>On Wed, Apr 30, 2025 at 03:41:19PM +0000, Wei Yang wrote:
>> On Wed, Apr 30, 2025 at 02:15:24PM +0100, Lorenzo Stoakes wrote:
>> >On Wed, Apr 30, 2025 at 12:47:03AM +0000, Wei Yang wrote:
>> >> On Tue, Apr 22, 2025 at 09:09:20AM +0100, Lorenzo Stoakes wrote:
>> >> [...]
>> >> >+bool vma_had_uncowed_children(struct vm_area_struct *vma)
>> >> >+{
>> >> >+	struct anon_vma *anon_vma = vma ? vma->anon_vma : NULL;
>> >> >+	bool ret;
>> >> >+
>> >> >+	if (!anon_vma)
>> >> >+		return false;
>> >> >+
>> >> >+	/*
>> >> >+	 * If we're mmap locked then there's no way for this count to change, as
>> >> >+	 * any such change would require this lock not be held.
>> >> >+	 */
>> >> >+	if (rwsem_is_locked(&vma->vm_mm->mmap_lock))
>> >> >+		return anon_vma->num_children > 1;
>> >>
>> >> Hi, Lorenzo
>> >>
>> >> May I have a question here?
>> >
>> >Just ask the question.
>> >
>>
>> Thanks.
>>
>> My question is the function is expected to return true, if we have forked a
>> vma from this one, right?
>>
>> IMO there are cases when it has one forked child and anon_vma->num_children == 1,
>> which means folios are not exclusively mapped. But the function would return
>> false.
>>
>> Or maybe I misunderstand the logic here.
>
>I mean, it'd be helpful if you delineated which cases these were?
>

Sorry, I should be more specific.

>Presumably you're thiking of something like:
>
>1. Process 1: VMA A is established. num_children == 1 (self-reference is counted).
>2. Process 2: Process 1 forks, VMA B references A, a->num_children++
>3. Process 3: Process 2 forks, VMA C is established (maybe you think b->num_children++?)

Maybe this is the key point. Will explain below at ***.

>4. Unmap vma B, oops, a->num_children == 1 but it still has C!
>
>But that won't happen, as VMA C will be referencing a->anon_vma, so in reality
>a->anon_vma->num_children == 3, then after unmap == 2.
>

The case here could be handled well, I am thinking a little different one.

Here is the case I am thinking about. If my understanding is wrong, please
correct me.

	a                  VMA A
	+-----------+      +-----------+
	|           | ---> |         av| == a
	+-----------+      +-----------+
	             \
	              \
	              |\   VMA B
	              | \  +-----------+
	              |  > |         av| == b
	              |    +-----------+
	              \
	               \   VMA C
	                \  +-----------+
	                 > |         av| == c
	                   +-----------+

1. Process 1: VMA A is established, num_children == 1
2. Process 2: Process 1 forks, a->num_children++ and b->num_children == 0
3. Process 3: Process 2 forks, b->num_children++ => b->number_children == 1

If vma_had_uncowed_children(VMA B), we would check b->number_children and
return false since it is not greater than 1. But we do have a child process 3.

***

Come back the b->num_children. After re-read your example, I guess this is the
key point. In anon_vma_fork(), we do anon_vma->parent->num_children++. So when
fork VMA C, we increase b->num_children instead of a->num_children.

To verify this, I did a quick test in my test cases in
test_fork_grand_child[1]. I see b->num_children is increased to 1 after C is
forked. Will reply in that thread and hope that would be helpful to
communicate the case.

Well, if I am not correct, feel free to correct me :-)

[1]: http://lkml.kernel.org/r/20250429090639.784-3-richard.weiyang@gmail.com

>References to the originally faulted-in anon_vma is propagated through the
>forks.
>
>anon_vma logic is tricky, one of many reasons I want to (significantly) rework
>it.
>
>Though sadly there is a lot of _essential_ complexity, I do think we can do
>better.
>

-- 
Wei Yang
Help you, Help me

On Thu, May 01, 2025 at 01:18:45AM +0000, Wei Yang wrote:
> On Wed, Apr 30, 2025 at 05:07:40PM +0100, Lorenzo Stoakes wrote:
> >On Wed, Apr 30, 2025 at 03:41:19PM +0000, Wei Yang wrote:
> >> On Wed, Apr 30, 2025 at 02:15:24PM +0100, Lorenzo Stoakes wrote:
> >> >On Wed, Apr 30, 2025 at 12:47:03AM +0000, Wei Yang wrote:
> >> >> On Tue, Apr 22, 2025 at 09:09:20AM +0100, Lorenzo Stoakes wrote:
> >> >> [...]
> >> >> >+bool vma_had_uncowed_children(struct vm_area_struct *vma)
> >> >> >+{
> >> >> >+	struct anon_vma *anon_vma = vma ? vma->anon_vma : NULL;
> >> >> >+	bool ret;
> >> >> >+
> >> >> >+	if (!anon_vma)
> >> >> >+		return false;
> >> >> >+
> >> >> >+	/*
> >> >> >+	 * If we're mmap locked then there's no way for this count to change, as
> >> >> >+	 * any such change would require this lock not be held.
> >> >> >+	 */
> >> >> >+	if (rwsem_is_locked(&vma->vm_mm->mmap_lock))
> >> >> >+		return anon_vma->num_children > 1;
> >> >>
> >> >> Hi, Lorenzo
> >> >>
> >> >> May I have a question here?
> >> >
> >> >Just ask the question.
> >> >
> >>
> >> Thanks.
> >>
> >> My question is the function is expected to return true, if we have forked a
> >> vma from this one, right?
> >>
> >> IMO there are cases when it has one forked child and anon_vma->num_children == 1,
> >> which means folios are not exclusively mapped. But the function would return
> >> false.
> >>
> >> Or maybe I misunderstand the logic here.
> >
> >I mean, it'd be helpful if you delineated which cases these were?
> >
>
> Sorry, I should be more specific.
>
> >Presumably you're thiking of something like:
> >
> >1. Process 1: VMA A is established. num_children == 1 (self-reference is counted).
> >2. Process 2: Process 1 forks, VMA B references A, a->num_children++
> >3. Process 3: Process 2 forks, VMA C is established (maybe you think b->num_children++?)
>
> Maybe this is the key point. Will explain below at ***.
>
> >4. Unmap vma B, oops, a->num_children == 1 but it still has C!
> >
> >But that won't happen, as VMA C will be referencing a->anon_vma, so in reality
> >a->anon_vma->num_children == 3, then after unmap == 2.
> >
>
> The case here could be handled well, I am thinking a little different one.
>
> Here is the case I am thinking about. If my understanding is wrong, please
> correct me.
>
> 	a                  VMA A
> 	+-----------+      +-----------+
> 	|           | ---> |         av| == a
> 	+-----------+      +-----------+
> 	             \
> 	              \
> 	              |\   VMA B
> 	              | \  +-----------+
> 	              |  > |         av| == b
> 	              |    +-----------+
> 	              \
> 	               \   VMA C
> 	                \  +-----------+
> 	                 > |         av| == c
> 	                   +-----------+
>
> 1. Process 1: VMA A is established, num_children == 1
> 2. Process 2: Process 1 forks, a->num_children++ and b->num_children == 0
> 3. Process 3: Process 2 forks, b->num_children++ => b->number_children == 1
>
> If vma_had_uncowed_children(VMA B), we would check b->number_children and
> return false since it is not greater than 1. But we do have a child process 3.
>
> ***
>
> Come back the b->num_children. After re-read your example, I guess this is the
> key point. In anon_vma_fork(), we do anon_vma->parent->num_children++. So when
> fork VMA C, we increase b->num_children instead of a->num_children.
>
> To verify this, I did a quick test in my test cases in
> test_fork_grand_child[1]. I see b->num_children is increased to 1 after C is
> forked. Will reply in that thread and hope that would be helpful to
> communicate the case.
>
> Well, if I am not correct, feel free to correct me :-)

OK so you've expressed this in a very confusing way and the diagram is
wrong but I think I see the point.

Because of anon_vma reuse logic in anon_vma_clone() we might end up in the
situation where num_children (which strictly reports number of anon_vma
objects whose parent pointer points at that anon_vma) does not actually
correctly reflect the fact that there are multiple mappings of a folio.

I think correct approach is to also look at num_active_vmas which accounts
for this, but I think overall we should move these checks to being a 'best
guess' and remove the WARN_ON() around the multiply-mapped folio
logic. It's fine to just back out if we guesstimated wrong.

I'll also add a bunch of tests to assert specific fork scenarios.

>
> [1]: http://lkml.kernel.org/r/20250429090639.784-3-richard.weiyang@gmail.com
>
> >References to the originally faulted-in anon_vma is propagated through the
> >forks.
> >
> >anon_vma logic is tricky, one of many reasons I want to (significantly) rework
> >it.
> >
> >Though sadly there is a lot of _essential_ complexity, I do think we can do
> >better.
> >
>
> --
> Wei Yang
> Help you, Help me

On Thu, May 01, 2025 at 10:27:47AM +0100, Lorenzo Stoakes wrote:
>On Thu, May 01, 2025 at 01:18:45AM +0000, Wei Yang wrote:
>> On Wed, Apr 30, 2025 at 05:07:40PM +0100, Lorenzo Stoakes wrote:
>> >On Wed, Apr 30, 2025 at 03:41:19PM +0000, Wei Yang wrote:
>> >> On Wed, Apr 30, 2025 at 02:15:24PM +0100, Lorenzo Stoakes wrote:
>> >> >On Wed, Apr 30, 2025 at 12:47:03AM +0000, Wei Yang wrote:
>> >> >> On Tue, Apr 22, 2025 at 09:09:20AM +0100, Lorenzo Stoakes wrote:
>> >> >> [...]
>> >> >> >+bool vma_had_uncowed_children(struct vm_area_struct *vma)
>> >> >> >+{
>> >> >> >+	struct anon_vma *anon_vma = vma ? vma->anon_vma : NULL;
>> >> >> >+	bool ret;
>> >> >> >+
>> >> >> >+	if (!anon_vma)
>> >> >> >+		return false;
>> >> >> >+
>> >> >> >+	/*
>> >> >> >+	 * If we're mmap locked then there's no way for this count to change, as
>> >> >> >+	 * any such change would require this lock not be held.
>> >> >> >+	 */
>> >> >> >+	if (rwsem_is_locked(&vma->vm_mm->mmap_lock))
>> >> >> >+		return anon_vma->num_children > 1;
>> >> >>
>> >> >> Hi, Lorenzo
>> >> >>
>> >> >> May I have a question here?
>> >> >
>> >> >Just ask the question.
>> >> >
>> >>
>> >> Thanks.
>> >>
>> >> My question is the function is expected to return true, if we have forked a
>> >> vma from this one, right?
>> >>
>> >> IMO there are cases when it has one forked child and anon_vma->num_children == 1,
>> >> which means folios are not exclusively mapped. But the function would return
>> >> false.
>> >>
>> >> Or maybe I misunderstand the logic here.
>> >
>> >I mean, it'd be helpful if you delineated which cases these were?
>> >
>>
>> Sorry, I should be more specific.
>>
>> >Presumably you're thiking of something like:
>> >
>> >1. Process 1: VMA A is established. num_children == 1 (self-reference is counted).
>> >2. Process 2: Process 1 forks, VMA B references A, a->num_children++
>> >3. Process 3: Process 2 forks, VMA C is established (maybe you think b->num_children++?)
>>
>> Maybe this is the key point. Will explain below at ***.
>>
>> >4. Unmap vma B, oops, a->num_children == 1 but it still has C!
>> >
>> >But that won't happen, as VMA C will be referencing a->anon_vma, so in reality
>> >a->anon_vma->num_children == 3, then after unmap == 2.
>> >
>>
>> The case here could be handled well, I am thinking a little different one.
>>
>> Here is the case I am thinking about. If my understanding is wrong, please
>> correct me.
>>
>> 	a                  VMA A
>> 	+-----------+      +-----------+
>> 	|           | ---> |         av| == a
>> 	+-----------+      +-----------+
>> 	             \
>> 	              \
>> 	              |\   VMA B
>> 	              | \  +-----------+
>> 	              |  > |         av| == b
>> 	              |    +-----------+
>> 	              \
>> 	               \   VMA C
>> 	                \  +-----------+
>> 	                 > |         av| == c
>> 	                   +-----------+
>>
>> 1. Process 1: VMA A is established, num_children == 1
>> 2. Process 2: Process 1 forks, a->num_children++ and b->num_children == 0
>> 3. Process 3: Process 2 forks, b->num_children++ => b->number_children == 1
>>
>> If vma_had_uncowed_children(VMA B), we would check b->number_children and
>> return false since it is not greater than 1. But we do have a child process 3.
>>
>> ***
>>
>> Come back the b->num_children. After re-read your example, I guess this is the
>> key point. In anon_vma_fork(), we do anon_vma->parent->num_children++. So when
>> fork VMA C, we increase b->num_children instead of a->num_children.
>>
>> To verify this, I did a quick test in my test cases in
>> test_fork_grand_child[1]. I see b->num_children is increased to 1 after C is
>> forked. Will reply in that thread and hope that would be helpful to
>> communicate the case.
>>
>> Well, if I am not correct, feel free to correct me :-)
>
>OK so you've expressed this in a very confusing way and the diagram is
>wrong but I think I see the point.
>

Sorry for my poor expression, while fortunately you get it :-)

>Because of anon_vma reuse logic in anon_vma_clone() we might end up in the
>situation where num_children (which strictly reports number of anon_vma
>objects whose parent pointer points at that anon_vma) does not actually
>correctly reflect the fact that there are multiple mappings of a folio.
>
>I think correct approach is to also look at num_active_vmas which accounts
>for this, but I think overall we should move these checks to being a 'best
>guess' and remove the WARN_ON() around the multiply-mapped folio
>logic. It's fine to just back out if we guesstimated wrong.
>

Would you mind cc me if you would spin another round? I would like to learn
more from your work.

>I'll also add a bunch of tests to assert specific fork scenarios.
>
>>
>> [1]: http://lkml.kernel.org/r/20250429090639.784-3-richard.weiyang@gmail.com
>>
>> >References to the originally faulted-in anon_vma is propagated through the
>> >forks.
>> >
>> >anon_vma logic is tricky, one of many reasons I want to (significantly) rework
>> >it.
>> >
>> >Though sadly there is a lot of _essential_ complexity, I do think we can do
>> >better.
>> >
>>
>> --
>> Wei Yang
>> Help you, Help me

-- 
Wei Yang
Help you, Help me

On Thu, May 01, 2025 at 02:35:01PM +0000, Wei Yang wrote:
> On Thu, May 01, 2025 at 10:27:47AM +0100, Lorenzo Stoakes wrote:
> >On Thu, May 01, 2025 at 01:18:45AM +0000, Wei Yang wrote:
> >> On Wed, Apr 30, 2025 at 05:07:40PM +0100, Lorenzo Stoakes wrote:
> >> >On Wed, Apr 30, 2025 at 03:41:19PM +0000, Wei Yang wrote:
> >> >> On Wed, Apr 30, 2025 at 02:15:24PM +0100, Lorenzo Stoakes wrote:
> >> >> >On Wed, Apr 30, 2025 at 12:47:03AM +0000, Wei Yang wrote:
> >> >> >> On Tue, Apr 22, 2025 at 09:09:20AM +0100, Lorenzo Stoakes wrote:
> >> >> >> [...]
> >> >> >> >+bool vma_had_uncowed_children(struct vm_area_struct *vma)
> >> >> >> >+{
> >> >> >> >+	struct anon_vma *anon_vma = vma ? vma->anon_vma : NULL;
> >> >> >> >+	bool ret;
> >> >> >> >+
> >> >> >> >+	if (!anon_vma)
> >> >> >> >+		return false;
> >> >> >> >+
> >> >> >> >+	/*
> >> >> >> >+	 * If we're mmap locked then there's no way for this count to change, as
> >> >> >> >+	 * any such change would require this lock not be held.
> >> >> >> >+	 */
> >> >> >> >+	if (rwsem_is_locked(&vma->vm_mm->mmap_lock))
> >> >> >> >+		return anon_vma->num_children > 1;
> >> >> >>
> >> >> >> Hi, Lorenzo
> >> >> >>
> >> >> >> May I have a question here?
> >> >> >
> >> >> >Just ask the question.
> >> >> >
> >> >>
> >> >> Thanks.
> >> >>
> >> >> My question is the function is expected to return true, if we have forked a
> >> >> vma from this one, right?
> >> >>
> >> >> IMO there are cases when it has one forked child and anon_vma->num_children == 1,
> >> >> which means folios are not exclusively mapped. But the function would return
> >> >> false.
> >> >>
> >> >> Or maybe I misunderstand the logic here.
> >> >
> >> >I mean, it'd be helpful if you delineated which cases these were?
> >> >
> >>
> >> Sorry, I should be more specific.
> >>
> >> >Presumably you're thiking of something like:
> >> >
> >> >1. Process 1: VMA A is established. num_children == 1 (self-reference is counted).
> >> >2. Process 2: Process 1 forks, VMA B references A, a->num_children++
> >> >3. Process 3: Process 2 forks, VMA C is established (maybe you think b->num_children++?)
> >>
> >> Maybe this is the key point. Will explain below at ***.
> >>
> >> >4. Unmap vma B, oops, a->num_children == 1 but it still has C!
> >> >
> >> >But that won't happen, as VMA C will be referencing a->anon_vma, so in reality
> >> >a->anon_vma->num_children == 3, then after unmap == 2.
> >> >
> >>
> >> The case here could be handled well, I am thinking a little different one.
> >>
> >> Here is the case I am thinking about. If my understanding is wrong, please
> >> correct me.
> >>
> >> 	a                  VMA A
> >> 	+-----------+      +-----------+
> >> 	|           | ---> |         av| == a
> >> 	+-----------+      +-----------+
> >> 	             \
> >> 	              \
> >> 	              |\   VMA B
> >> 	              | \  +-----------+
> >> 	              |  > |         av| == b
> >> 	              |    +-----------+
> >> 	              \
> >> 	               \   VMA C
> >> 	                \  +-----------+
> >> 	                 > |         av| == c
> >> 	                   +-----------+
> >>
> >> 1. Process 1: VMA A is established, num_children == 1
> >> 2. Process 2: Process 1 forks, a->num_children++ and b->num_children == 0
> >> 3. Process 3: Process 2 forks, b->num_children++ => b->number_children == 1
> >>
> >> If vma_had_uncowed_children(VMA B), we would check b->number_children and
> >> return false since it is not greater than 1. But we do have a child process 3.
> >>
> >> ***
> >>
> >> Come back the b->num_children. After re-read your example, I guess this is the
> >> key point. In anon_vma_fork(), we do anon_vma->parent->num_children++. So when
> >> fork VMA C, we increase b->num_children instead of a->num_children.
> >>
> >> To verify this, I did a quick test in my test cases in
> >> test_fork_grand_child[1]. I see b->num_children is increased to 1 after C is
> >> forked. Will reply in that thread and hope that would be helpful to
> >> communicate the case.
> >>
> >> Well, if I am not correct, feel free to correct me :-)
> >
> >OK so you've expressed this in a very confusing way and the diagram is
> >wrong but I think I see the point.
> >
>
> Sorry for my poor expression, while fortunately you get it :-)

No need to apologise haha, thanks for reporting this. This kind of thing is
useful, we always want reports of problems (in this case, ahead of time...).

>
> >Because of anon_vma reuse logic in anon_vma_clone() we might end up in the
> >situation where num_children (which strictly reports number of anon_vma
> >objects whose parent pointer points at that anon_vma) does not actually
> >correctly reflect the fact that there are multiple mappings of a folio.
> >
> >I think correct approach is to also look at num_active_vmas which accounts
> >for this, but I think overall we should move these checks to being a 'best
> >guess' and remove the WARN_ON() around the multiply-mapped folio
> >logic. It's fine to just back out if we guesstimated wrong.
> >
>
> Would you mind cc me if you would spin another round? I would like to learn
> more from your work.

Of course dude, if I reference somebody in a change log I always cc as a matter
of principle :)

Cheers, Lorenzo

>
> >I'll also add a bunch of tests to assert specific fork scenarios.
> >
> >>
> >> [1]: http://lkml.kernel.org/r/20250429090639.784-3-richard.weiyang@gmail.com
> >>
> >> >References to the originally faulted-in anon_vma is propagated through the
> >> >forks.
> >> >
> >> >anon_vma logic is tricky, one of many reasons I want to (significantly) rework
> >> >it.
> >> >
> >> >Though sadly there is a lot of _essential_ complexity, I do think we can do
> >> >better.
> >> >
> >>
> >> --
> >> Wei Yang
> >> Help you, Help me
>
> --
> Wei Yang
> Help you, Help me

OK have dug into this some more with a drgn script to read actual kernel
metadata state and it's simpler than I thought - the root anon_vma is
self-childed, but descendent anon_vma's are not.

We can correct this with a anon_vma->root == anon_vma check. I believe
we're probably safe with anon_vma reuse, because in that instance the
anon_vma would not be mapped a shared folio.

However, to be safe, I will check this, and I as I said previously, I will
add a number of tests explicitly tested forking scenarios.

The respin should have this fully addressed.

Thanks, Lorenzo

On Sat, May 03, 2025 at 03:29:08PM +0100, Lorenzo Stoakes wrote:
> OK have dug into this some more with a drgn script to read actual kernel
> metadata state and it's simpler than I thought - the root anon_vma is
> self-childed, but descendent anon_vma's are not.
>
> We can correct this with a anon_vma->root == anon_vma check. I believe
> we're probably safe with anon_vma reuse, because in that instance the
> anon_vma would not be mapped a shared folio.
>
> However, to be safe, I will check this, and I as I said previously, I will
> add a number of tests explicitly tested forking scenarios.
>
> The respin should have this fully addressed.
>
> Thanks, Lorenzo

Note that in practice, this wouldn't have broken anything, as in this case you
would _have_ to have parent anon_vma's.

The root will hang around even if all VMA's unmapped also, we only clear down
anon_vma's once no references from the anon_vma exist, and by nature everything
below the root must reference it.

But the function is misleading as-is so needs fixing.

As for anon_vma re-use - this is not permitted for root anon_vma's so naturally
it requires a parented anon_vma, which again implies AVC's which the uncowed
parent check would pick up.

Additionally, the reuse implies that the folio is not mapped within the process
that first created the anon_vma, and thus the num_children counts remain correct
across the board.

See https://pastebin.com/raw/q6wzUMLi for a detailed diagram of both scenarios
with anon_vma parameters and linking derived from real-world kernel values
obtained via drgn.

These will form part of the added tests.

Cheers, Lorenzo

On 4/30/25 02:47, Wei Yang wrote:
> On Tue, Apr 22, 2025 at 09:09:20AM +0100, Lorenzo Stoakes wrote:
> [...]
>>+bool vma_had_uncowed_children(struct vm_area_struct *vma)
>>+{
>>+	struct anon_vma *anon_vma = vma ? vma->anon_vma : NULL;
>>+	bool ret;
>>+
>>+	if (!anon_vma)
>>+		return false;
>>+
>>+	/*
>>+	 * If we're mmap locked then there's no way for this count to change, as
>>+	 * any such change would require this lock not be held.
>>+	 */
>>+	if (rwsem_is_locked(&vma->vm_mm->mmap_lock))
>>+		return anon_vma->num_children > 1;
> 
> Hi, Lorenzo
> 
> May I have a question here?

You're missing the actual question :)

>>+
>>+	/*
>>+	 * Any change that would increase the number of children would be
>>+	 * prevented by a read lock.
>>+	 */
>>+	anon_vma_lock_read(anon_vma);
>>+	ret = anon_vma->num_children > 1;
>>+	anon_vma_unlock_read(anon_vma);
>>+
>>+	return ret;
>>+}
>