[PATCH] mm/vma: avoid redundant file rmap tree re-insert on new_below=0 split

[PATCH] mm/vma: avoid redundant file rmap tree re-insert on new_below=0 split

[Pan Deng]

Splitting a file-backed VMA removes it from the mapping's i_mmap interval
tree and re-inserts it, two O(log n) walks with rebalancing, all inside
the i_mmap_rwsem write-side critical section.  For a file mapped by many
processes that lock is a single serialization point, so the cost translates
into reduced exec throughput.

While the re-insert is needed whenever the sort key changes, it is not for
a new_below=0 split: there the new VMA takes the upper half and only the
original VMA's vm_end shrinks, so vma_start_pgoff(), the sort key of the
interval tree, stays constant and the VMA is already in the correct
position.

This change skips the re-insert for that case.  vma_prepare() no longer
removes vp->vma from the tree; instead vma_complete() detects that case and
only recomputes shared.rb_subtree_last up the ancestor chain.  Everything
else keeps the remove + re-insert path.

The case is detected by comparing vma_start_pgoff(vp->insert) against
vma_start_pgoff(vp->vma): only a new_below=0 split leaves the former
greater.  __split_vma() adjusts pgoff via vma_add_pgoff(new,
linear_page_delta(vma, addr)), and linear_page_delta() is
(addr - vm_start) >> PAGE_SHIFT with addr strictly inside the VMA, so the
delta is at least one page and the new VMA's pgoff is strictly greater.
For new_below=1 the two are initially equal and vp->vma's pgoff then
increases, so the comparison is false both before and after the caller's
endpoint updates, and the original path is taken.

Inferring the case this way keeps the change small: struct vma_prepare
gains no field and no caller changes.

Moving the remove() out of vma_prepare() leaves vp->vma in the tree with a
possibly stale sort key across the caller's endpoint updates, so
vma_complete() re-keys it *before* inserting vp->adj_next: otherwise that
key-driven descent could place adj_next in the wrong subtree.

Measured on v7.3-rc4, on a 2-socket 192C/384T system running UnixBench
execl (384 concurrent execve of the same binary), dropping the redundant
remove + re-insert yields ~14% higher throughput by shortening the
i_mmap_rwsem write-side critical section during the file VMA splits that
execve performs on the shared libraries.

Signed-off-by: Pan Deng <pan.deng@intel.com>
Reviewed-by: Tianyou Li <tianyou.li@intel.com>
Reviewed-by: Wangyang Guo <wangyang.guo@intel.com>
Reviewed-by: Zhiguo Zhou <zhiguo.zhou@intel.com>
Reviewed-by: Tim Chen <tim.c.chen@linux.intel.com>
Assisted-by: LLM
---
 include/linux/mm.h                |  1 +
 mm/interval_tree.c                | 13 ++++++++
 mm/vma.c                          | 54 +++++++++++++++++++++++++++++--
 mm/vma.h                          |  1 +
 tools/testing/vma/include/stubs.h |  4 +++
 5 files changed, 71 insertions(+), 2 deletions(-)

diff --git a/include/linux/mm.h b/include/linux/mm.h
index dd09c438fa23..baf489343f86 100644
--- a/include/linux/mm.h
+++ b/include/linux/mm.h
@@ -4181,6 +4181,7 @@ void mapping_rmap_tree_insert_after(struct vm_area_struct *vma,
 				    struct address_space *mapping);
 void mapping_rmap_tree_remove(struct vm_area_struct *vma,
 			      struct address_space *mapping);
+void mapping_rmap_tree_propagate(struct vm_area_struct *vma);
 struct vm_area_struct *
 mapping_rmap_tree_iter_first(struct address_space *mapping,
 			     pgoff_t pgoff_start, pgoff_t pgoff_last);
diff --git a/mm/interval_tree.c b/mm/interval_tree.c
index 7bbbf15cfbf0..3b81c990aab2 100644
--- a/mm/interval_tree.c
+++ b/mm/interval_tree.c
@@ -64,6 +64,19 @@ void mapping_rmap_tree_remove(struct vm_area_struct *vma,
 	__mapping_rmap_tree_remove(vma, &mapping->i_mmap);
 }
 
+/*
+ * Recompute shared.rb_subtree_last for vma and its ancestors, for a vma whose
+ * interval changed but whose vma_start_pgoff() (the tree's sort key) did not.
+ * The NULL stop node makes the walk run up to the root, though it ends early
+ * once the recomputed value stops changing.
+ *
+ * Wrapper because INTERVAL_TREE_DEFINE() above declares the callbacks static.
+ */
+void mapping_rmap_tree_propagate(struct vm_area_struct *vma)
+{
+	__mapping_rmap_tree_augment.propagate(&vma->shared.rb, NULL);
+}
+
 struct vm_area_struct *
 mapping_rmap_tree_iter_first(struct address_space *mapping,
 			     pgoff_t pgoff_start, pgoff_t pgoff_last)
diff --git a/mm/vma.c b/mm/vma.c
index f29abb30956b..e1dbfd5094cd 100644
--- a/mm/vma.c
+++ b/mm/vma.c
@@ -365,11 +365,43 @@ static void vma_prepare(struct vma_prepare *vp)
 
 	if (vp->file) {
 		flush_dcache_mmap_lock(vp->mapping);
-		mapping_rmap_tree_remove(vp->vma, vp->mapping);
+		/* vp->vma is re-keyed by vma_complete(), if it needs to be. */
 		if (vp->adj_next)
 			mapping_rmap_tree_remove(vp->adj_next, vp->mapping);
 	}
+}
 
+/*
+ * vma_split_keeps_rmap_key() - Check if vp->vma keeps its file rmap tree key
+ * @vp: The vma_prepare struct
+ *
+ * True only for a new_below=0 __split_vma(): the new VMA takes the upper half,
+ * so its vma_start_pgoff() is strictly greater, while vp->vma's (its key in the
+ * file rmap interval tree) is unchanged and its tree position still correct, so
+ * only shared.rb_subtree_last has to be recomputed.
+ *
+ * Relies on vp->insert being assigned by __split_vma() only; the check below
+ * catches a second assignment site whose VMA does not abut vp->vma.
+ */
+static bool vma_split_keeps_rmap_key(const struct vma_prepare *vp)
+{
+	if (!vp->insert ||
+	    vma_start_pgoff(vp->insert) <= vma_start_pgoff(vp->vma))
+		return false;
+
+	/*
+	 * Today only a new_below=0 __split_vma() reaches here, where the new
+	 * VMA abuts vp->vma at the split point once the caller has updated
+	 * vp->vma->vm_end.  If a future vp->insert user ever violates that,
+	 * fall back to the safe remove + re-insert instead of trusting the
+	 * fast path.
+	 */
+	if (vp->insert->vm_start != vp->vma->vm_end) {
+		VM_WARN_ON_ONCE(1);
+		return false;
+	}
+
+	return true;
 }
 
 /*
@@ -384,9 +416,27 @@ static void vma_complete(struct vma_prepare *vp, struct vma_iterator *vmi,
 			 struct mm_struct *mm)
 {
 	if (vp->file) {
+		if (vma_split_keeps_rmap_key(vp)) {
+			/*
+			 * Split paths go through init_vma_prep(), which
+			 * passes a NULL vmg, so vp->adj_next is never set.
+			 */
+			VM_WARN_ON_ONCE(vp->adj_next);
+			mapping_rmap_tree_propagate(vp->vma);
+		} else {
+			/*
+			 * Re-key vp->vma *before* the insert of vp->adj_next
+			 * below, so that the latter descends a valid
+			 * search tree: vp->vma is the only node left in
+			 * the tree that may carry a stale sort key
+			 * (vp->adj_next itself was removed in
+			 * vma_prepare()).
+			 */
+			mapping_rmap_tree_remove(vp->vma, vp->mapping);
+			mapping_rmap_tree_insert(vp->vma, vp->mapping);
+		}
 		if (vp->adj_next)
 			mapping_rmap_tree_insert(vp->adj_next, vp->mapping);
-		mapping_rmap_tree_insert(vp->vma, vp->mapping);
 		flush_dcache_mmap_unlock(vp->mapping);
 	}
 
diff --git a/mm/vma.h b/mm/vma.h
index 024fabe63560..3f791e4d13f6 100644
--- a/mm/vma.h
+++ b/mm/vma.h
@@ -23,6 +23,7 @@ struct vma_prepare {
 	struct file *file;
 	struct address_space *mapping;
 	struct anon_vma *anon_vma;
+	/* Set by __split_vma() only; see vma_split_keeps_rmap_key(). */
 	struct vm_area_struct *insert;
 	struct vm_area_struct *remove;
 	struct vm_area_struct *remove2;
diff --git a/tools/testing/vma/include/stubs.h b/tools/testing/vma/include/stubs.h
index d6136e19a8af..3b5184aeee54 100644
--- a/tools/testing/vma/include/stubs.h
+++ b/tools/testing/vma/include/stubs.h
@@ -267,6 +267,10 @@ static inline void mapping_rmap_tree_remove(struct vm_area_struct *vma,
 {
 }
 
+static inline void mapping_rmap_tree_propagate(struct vm_area_struct *vma)
+{
+}
+
 static inline void flush_dcache_mmap_unlock(struct address_space *mapping)
 {
 }
-- 
2.43.5