mm/ksm: use per-VMA locking for find_mergeable_vma()

[PATCH 0/4] mm/ksm: use per-VMA locking for find_mergeable_vma()

Posted by xu.xin16@zte.com.cn 2 weeks ago

From: Xu Xin (ZTE) <xu.xin@linux.dev>

KSM scans VM_MERGEABLE VMAs and currently protects each scan with
mmap_read_lock(). Per-VMA locking allows KSM to read-lock only the VMA
it is actually interested in, so that unrelated mmap()/munmap() activity
in the same mm no longer blocks ksmd.

This series is organized as follows:

  Patch 1 removes an unused 'vma' member from struct folio_walk.  It has
  never been used since its introduction and is pure cleanup.

  Patch 2 adds a 'walk_lock' member to struct folio_walk and extends
  folio_walk_start() to assert the required locking mode.  Existing
  callers are converted to pass PGWALK_RDLOCK, so there is no functional
  change.  This prepares folio_walk_start() for callers that hold a
  per-VMA read lock instead of mmap_read_lock(), which is needed by the
  Patch 4. No functional change.

  Patch 3 tranforms the boolean 'lock_vma' into the enum 'page_walk_lock'
  without any behavior changed, which is prepared for the Patch 4 to use
  per-VMA locking. No functional change.

  Patch 4 introduces find_mergeable_vma_locked(), which uses the
  universal per-VMA locking helper vma_start_read_unlocked() to look up
  and read-lock a VM_MERGEABLE VMA without taking mmap_read_lock().  All
  KSM call sites that previously used find_mergeable_vma() under
  mmap_read_lock() are converted to the new helper, and the locking in
  get_mergeable_page() is switched to PGWALK_VMA_RDLOCK_VERIFY so that
  folio_walk_start() can verify the per-VMA lock is held.

A microbenchmark was run to measure the time KSM takes to merge a
victim region under mmap_lock contention. Under interference from 4 churner
threads, the merge time of the per-VMA KSM-optimized kernel is
significantly reduced by 50%.

Xu Xin (4):
  mm/pagewalk: delete the unused member
  mm: make folio_walk_start()'s locking asserts scalable
  mm/ksm: make break_ksm() more scalable
  mm/ksm: add find_mergeable_vma_locked() to use per-VMA locking

 arch/s390/mm/fault.c     |  4 +-
 include/linux/pagewalk.h |  2 +-
 kernel/events/uprobes.c  |  4 +-
 mm/huge_memory.c         |  4 +-
 mm/ksm.c                 | 85 ++++++++++++++++++++++++----------------
 mm/migrate.c             |  8 +++-
 mm/pagewalk.c            | 10 ++++-
 mm/rmap.c                |  4 +-
 8 files changed, 79 insertions(+), 42 deletions(-)

-- 
2.25.1

[PATCH RFC 0/3] mm/ksm: scan with per-VMA locks

Posted by Longlong Xia 1 week, 6 days ago

From: Longlong Xia <xialonglong@kylinos.cn>

This work was developed independently before I saw the above series.
After comparing the two implementations, I found that the approaches
overlap, so I am posting this draft version as an alternative 
implementation and would be happy to combine the useful parts.

  The main differences are:

  - use per-VMA locking in the ksmd VMA scanner;
  - revalidate the mmap-lock sequence before skipping the fallback walk;
  - avoid repeating a completed VMA traversal when no candidate page is
    found.

Benchmark (QEMU q35, TCG multi-thread, 4 vCPUs, 8 GiB, x86_64 guest on
Ubuntu 24.04, 7.3-rc2 base, CONFIG_KSM=y + CONFIG_PER_VMA_LOCK=y;
victim: 32 MiB anon, 2048 unique pages x4 duplicates,
pages_to_scan=100000, sleep_millisecs=0, 3 runs each; churners: 4
threads mmap/munmaping 256 MiB in the same mm. Microbenchmark as
posted in [3]; relative numbers only, TCG is not native hardware):

                       0 churners      4 churners (mean)   
  7.3-rc2              1.21-1.41 s     90.9 s             
  + patch 2/3          1.41 s          48.7 s   (-46%)   
  + patch 2/3 + 3/3    1.21-1.41 s     30.1 s   (-67%)  


 1. mm/pagewalk: allow folio_walk_start() under a vma read lock

 2. mm/ksm: use the VMA lock when looking up mergeable pages

 3. mm/ksm: scan VMAs with per-VMA locks

Link:https://lore.kernel.org/all/5cd47bc3-bc3d-473c-80d0-8be8b7b79881@163.com/

Longlong Xia (3):
  mm/pagewalk: allow folio_walk_start() under a vma read lock
  mm/ksm: use the VMA lock when looking up mergeable pages
  mm/ksm: scan VMAs with per-VMA locks

 include/linux/pagewalk.h |   3 +
 mm/ksm.c                 | 166 ++++++++++++++++++++++++++++++++++++---
 mm/pagewalk.c            |  11 ++-
 3 files changed, 166 insertions(+), 14 deletions(-)

base-commit: df2908090cda368b01ff43709f51890076c56157
-- 
2.43.0

Re: [PATCH RFC 0/3] mm/ksm: scan with per-VMA locks

Posted by xu.xin16@zte.com.cn 1 week, 5 days ago

> From: Longlong Xia <xialonglong@kylinos.cn>
> 
> This work was developed independently before I saw the above series.
> After comparing the two implementations, I found that the approaches
> overlap, so I am posting this draft version as an alternative 
> implementation and would be happy to combine the useful parts.
> 
>   The main differences are:
> 
>   - use per-VMA locking in the ksmd VMA scanner;
>   - revalidate the mmap-lock sequence before skipping the fallback walk;
>   - avoid repeating a completed VMA traversal when no candidate page is
>     found.
> 
> Benchmark (QEMU q35, TCG multi-thread, 4 vCPUs, 8 GiB, x86_64 guest on
> Ubuntu 24.04, 7.3-rc2 base, CONFIG_KSM=y + CONFIG_PER_VMA_LOCK=y;
> victim: 32 MiB anon, 2048 unique pages x4 duplicates,
> pages_to_scan=100000, sleep_millisecs=0, 3 runs each; churners: 4
> threads mmap/munmaping 256 MiB in the same mm. Microbenchmark as
> posted in [3]; relative numbers only, TCG is not native hardware):
> 
>                        0 churners      4 churners (mean)   
>   7.3-rc2              1.21-1.41 s     90.9 s             
>   + patch 2/3          1.41 s          48.7 s   (-46%)   
>   + patch 2/3 + 3/3    1.21-1.41 s     30.1 s   (-67%)  
> 
> 
>  1. mm/pagewalk: allow folio_walk_start() under a vma read lock
> 
>  2. mm/ksm: use the VMA lock when looking up mergeable pages
> 
>  3. mm/ksm: scan VMAs with per-VMA locks
> 

it seems your patches may not be rebased on the latest mm-unstable or linux-next. 
It might also be worth double-checking any AI-generated code before sending it out.

I also noticed that the content of patches 1 and 2 is already included in my patch series.
Perhaps it would be better to focus on my series for those and I'd appreciate your help
reviewing them. For patch 3, feel free to start a separate email thread if that works better.

Thanks

[PATCH RFC 1/3] mm/pagewalk: allow folio_walk_start() under a vma read lock

Posted by Longlong Xia 1 week, 6 days ago

From: Longlong Xia <xialonglong@kylinos.cn>

Allow folio_walk_start() to use a vma read lock by replacing
mmap_assert_locked() with vma_assert_locked().  This lets KSM look
up pages without taking the mmap read lock.

The vma lock stabilizes the mapping, while page table locks serialize
entry updates.  Callers walking another mm under the vma lock must
also hold an mm_users reference to prevent exit_mmap() from freeing
the page tables.

Assisted-by: Zcode:GLM-5.3
Signed-off-by: Longlong Xia <xialonglong@kylinos.cn>
---
 include/linux/pagewalk.h |  3 +++
 mm/pagewalk.c            | 11 +++++++++--
 2 files changed, 12 insertions(+), 2 deletions(-)

diff --git a/include/linux/pagewalk.h b/include/linux/pagewalk.h
index b41d7265c01b..cafd7b15f480 100644
--- a/include/linux/pagewalk.h
+++ b/include/linux/pagewalk.h
@@ -151,6 +151,9 @@ typedef int __bitwise folio_walk_flags_t;
 /* Walk shared zeropages (small + huge) as well. */
 #define FW_ZEROPAGE			((__force folio_walk_flags_t)BIT(0))
 
+/* The caller holds the VMA read lock instead of the mmap lock. */
+#define FW_VMA_LOCKED			((__force folio_walk_flags_t)BIT(1))
+
 enum folio_walk_level {
 	FW_LEVEL_PTE,
 	FW_LEVEL_PMD,
diff --git a/mm/pagewalk.c b/mm/pagewalk.c
index cc07fcf50e87..57ffaf2a85b8 100644
--- a/mm/pagewalk.c
+++ b/mm/pagewalk.c
@@ -894,7 +894,11 @@ int walk_page_mapping(struct address_space *mapping, pgoff_t first_index,
  * huge_ptep_set_*, ...). Note that the page table entry stored in @fw might
  * not correspond to the first physical entry of a logical hugetlb entry.
  *
- * The mmap lock must be held in read mode.
+ * The mmap lock must be held in read mode.  Alternatively, with
+ * CONFIG_PER_VMA_LOCK and @FW_VMA_LOCKED, the vma lock may be held in read mode: the
+ * page tables of a read-locked vma cannot be torn down while the mm has
+ * users, so a caller that walks an mm other than its own must also hold a
+ * mm_users reference for the duration of the walk.
  *
  * Return: folio pointer on success, otherwise NULL.
  */
@@ -912,7 +916,10 @@ struct folio *folio_walk_start(struct folio_walk *fw,
 	pgd_t *pgdp;
 	p4d_t *p4dp;
 
-	mmap_assert_locked(vma->vm_mm);
+	if (flags & FW_VMA_LOCKED)
+		vma_assert_locked(vma);
+	else
+		mmap_assert_locked(vma->vm_mm);
 	vma_pgtable_walk_begin(vma);
 
 	if (WARN_ON_ONCE(addr < vma->vm_start || addr >= vma->vm_end))
-- 
2.43.0

[PATCH RFC 2/3] mm/ksm: use the VMA lock when looking up mergeable pages

Posted by Longlong Xia 1 week, 6 days ago

From: Longlong Xia <xialonglong@kylinos.cn>

get_mergeable_page() currently takes mm->mmap_lock for every unstable-tree
lookup, so KSM is serialized with layout changes to unrelated VMAs. Try
lock_vma_under_rcu() while holding an mm_users reference and walk the page
tables under that VMA's read lock. Retain the mmap read-lock path as a
fallback when the VMA cannot be locked or per-VMA locking is disabled.

Extend folio_walk_start() to verify a VMA read lock and keep the mm_users
reference across the walk, since a VMA lock alone does not prevent
exit_mmap() from freeing page tables. Drop the reference before waiting for
mmap_lock on the fallback path so an exiting mm is not delayed.

Assisted-by: Zcode:GLM-5.3
Signed-off-by: Longlong Xia <xialonglong@kylinos.cn>
---
 mm/ksm.c | 64 +++++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 52 insertions(+), 12 deletions(-)

diff --git a/mm/ksm.c b/mm/ksm.c
index 49d48d1e0998..aee1a1b49b1b 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -811,21 +811,20 @@ static void break_cow(struct ksm_rmap_item *rmap_item)
 	mmap_read_unlock(mm);
 }
 
-static struct page *get_mergeable_page(struct ksm_rmap_item *rmap_item)
+/*
+ * Get the page that @addr maps in @vma, with an elevated reference, or NULL
+ * when the address no longer maps an anon page.  The caller must hold a lock
+ * that stabilizes @vma: either the mmap read lock, or the vma read lock
+ * together with an mm_users reference.
+ */
+static struct page *__get_mergeable_page(struct vm_area_struct *vma,
+					 unsigned long addr, folio_walk_flags_t flags)
 {
-	struct mm_struct *mm = rmap_item->mm;
-	unsigned long addr = rmap_item->address;
-	struct vm_area_struct *vma;
-	struct page *page = NULL;
 	struct folio_walk fw;
+	struct page *page = NULL;
 	struct folio *folio;
 
-	mmap_read_lock(mm);
-	vma = find_mergeable_vma(mm, addr);
-	if (!vma)
-		goto out;
-
-	folio = folio_walk_start(&fw, vma, addr, 0);
+	folio = folio_walk_start(&fw, vma, addr, flags);
 	if (folio) {
 		if (!folio_is_zone_device(folio) &&
 		    folio_test_anon(folio)) {
@@ -834,11 +833,52 @@ static struct page *get_mergeable_page(struct ksm_rmap_item *rmap_item)
 		}
 		folio_walk_end(&fw, vma);
 	}
-out:
 	if (page) {
 		flush_anon_page(vma, page, addr);
 		flush_dcache_page(page);
 	}
+	return page;
+}
+
+static struct page *get_mergeable_page(struct ksm_rmap_item *rmap_item)
+{
+	struct mm_struct *mm = rmap_item->mm;
+	unsigned long addr = rmap_item->address;
+	struct vm_area_struct *vma;
+	struct page *page = NULL;
+
+	/*
+	 * Try the vma lock before the mmap lock, so that ksmd does not queue
+	 * behind a writer that changes the address space layout anywhere in
+	 * this mm: the vma lock only contends with modification of this very
+	 * vma.  Pin mm_users for the walk: exit_mmap() frees the page tables
+	 * under the mmap lock alone, so a vma read lock cannot keep it away,
+	 * but an mm_users reference can; the pin also stands in for the
+	 * ksm_test_exit() check of find_mergeable_vma() on this path.  Drop
+	 * it again before waiting for the mmap lock below, so that an exiting
+	 * mm is not delayed by us.
+	 */
+	if (IS_ENABLED(CONFIG_PER_VMA_LOCK) && mmget_not_zero(mm)) {
+		vma = lock_vma_under_rcu(mm, addr);
+		if (vma) {
+			if ((vma->vm_flags & VM_MERGEABLE) && vma->anon_vma)
+				page = __get_mergeable_page(vma, addr, FW_VMA_LOCKED);
+			vma_end_read(vma);
+			mmput_async(mm);
+			return page;
+		}
+		mmput_async(mm);
+	}
+
+	/*
+	 * The vma is being modified, or CONFIG_PER_VMA_LOCK is off: take the
+	 * mmap read lock as before.  We are prepared to wait rather than skip
+	 * this page, so a contended mm only slows down its own merging.
+	 */
+	mmap_read_lock(mm);
+	vma = find_mergeable_vma(mm, addr);
+	if (vma)
+		page = __get_mergeable_page(vma, addr, 0);
 	mmap_read_unlock(mm);
 	return page;
 }
-- 
2.43.0

[PATCH RFC 3/3] mm/ksm: scan VMAs with per-VMA locks

Posted by Longlong Xia 1 week, 6 days ago

From: Longlong Xia <xialonglong@kylinos.cn>

KSM currently holds mm->mmap_lock while scanning the VMAs of an mm. Use
lock_next_vma() and walk_page_range_vma() to acquire each VMA's read lock
and release it after finding a candidate page, allowing unrelated VMA
updates to proceed while ksmd scans.

Pin mm_users for the duration of the lockless VMA traversal to keep page
tables alive, and retain the mmap-lock scan as a fallback when a VMA lock
cannot be acquired or per-VMA locking is disabled. Allocation failures
preserve the existing early-stop semantics. This reduces mmap_lock
contention for workloads with concurrent address-space updates while
preserving existing scan semantics.

When the per-VMA scan completes without finding a candidate, remember the
complete traversal and revalidate the mmap-lock sequence before entering
the fallback. If the address space is unchanged, skip the duplicate VMA
walk; if a VMA writer raced with the traversal, restart the fallback walk.

Assisted-by: Zcode:GLM-5.3
Signed-off-by: Longlong Xia <xialonglong@kylinos.cn>
---
 mm/ksm.c | 107 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 107 insertions(+)

diff --git a/mm/ksm.c b/mm/ksm.c
index aee1a1b49b1b..2c0b2adb83d4 100644
--- a/mm/ksm.c
+++ b/mm/ksm.c
@@ -2647,6 +2647,98 @@ static struct mm_walk_ops ksm_next_page_ops = {
 	.walk_lock = PGWALK_RDLOCK,
 };
 
+#ifdef CONFIG_PER_VMA_LOCK
+static const struct mm_walk_ops ksm_next_page_vma_ops = {
+	.pmd_entry = ksm_next_page_pmd_entry,
+	.walk_lock = PGWALK_VMA_RDLOCK_VERIFY,
+};
+
+/* Return true when a candidate was processed, including allocation failure. */
+static bool scan_get_next_rmap_item_vma(struct ksm_mm_slot *mm_slot,
+		struct page **page, struct ksm_rmap_item **result,
+		bool *complete, unsigned int *mm_wr_seq)
+{
+	struct mm_struct *mm = mm_slot->slot.mm;
+	unsigned long address = ksm_scan.address;
+	struct vm_area_struct *vma;
+	struct vma_iterator vmi;
+	bool done = false;
+	bool mmap_unlocked;
+
+	if (!mmget_not_zero(mm))
+		return false;
+
+	mmap_unlocked = mmap_lock_speculate_try_begin(mm, mm_wr_seq);
+
+	for (;;) {
+		rcu_read_lock();
+		vma_iter_init(&vmi, mm, address);
+		vma = lock_next_vma(mm, &vmi, address);
+		rcu_read_unlock();
+		if (IS_ERR_OR_NULL(vma))
+			break;
+
+		address = vma->vm_end;
+		if (!(vma->vm_flags & VM_MERGEABLE))
+			goto next_vma;
+		if (ksm_scan.address < vma->vm_start)
+			ksm_scan.address = vma->vm_start;
+		if (!vma->anon_vma)
+			ksm_scan.address = vma->vm_end;
+
+		while (ksm_scan.address < vma->vm_end) {
+			struct ksm_next_page_arg arg;
+			struct ksm_rmap_item *rmap_item;
+			int found;
+
+			found = walk_page_range_vma(vma, ksm_scan.address,
+					vma->vm_end, &ksm_next_page_vma_ops, &arg);
+			if (found <= 0) {
+				VM_WARN_ON_ONCE(found < 0);
+				ksm_scan.address = vma->vm_end;
+				break;
+			}
+
+			ksm_scan.address = arg.addr;
+			flush_anon_page(vma, arg.page, arg.addr);
+			flush_dcache_page(arg.page);
+			rmap_item = get_next_rmap_item(mm_slot,
+					ksm_scan.rmap_list, arg.addr);
+			if (rmap_item) {
+				ksm_scan.rmap_list = &rmap_item->rmap_list;
+				if (should_skip_rmap_item(arg.folio, rmap_item)) {
+					folio_put(arg.folio);
+					ksm_scan.address += PAGE_SIZE;
+					cond_resched();
+					continue;
+				}
+				ksm_scan.address += PAGE_SIZE;
+				*page = arg.page;
+			} else {
+				folio_put(arg.folio);
+			}
+			*result = rmap_item;
+			done = true;
+			vma_end_read(vma);
+			goto out;
+		}
+next_vma:
+		/*
+		 * Don't advance ksm_scan.address for VMAs the mmap-lock loop
+		 * skips with a plain continue: the cursor has to stay 0 when
+		 * this mm holds no VM_MERGEABLE vma, so the fallback walk can
+		 * remove the mm from the scan list at the end of the pass.
+		 */
+		vma_end_read(vma);
+		cond_resched();
+	}
+	*complete = mmap_unlocked && !vma;
+out:
+	mmput_async(mm);
+	return done;
+}
+#endif
+
 static struct ksm_rmap_item *scan_get_next_rmap_item(struct page **page)
 {
 	struct mm_struct *mm;
@@ -2655,6 +2747,9 @@ static struct ksm_rmap_item *scan_get_next_rmap_item(struct page **page)
 	struct vm_area_struct *vma;
 	struct ksm_rmap_item *rmap_item;
 	struct vma_iterator vmi;
+	bool skip_vma_scan = false;
+	bool vma_scan_complete = false;
+	unsigned int mm_wr_seq;
 	int nid;
 
 	if (list_empty(&ksm_mm_head.slot.mm_node))
@@ -2719,12 +2814,23 @@ static struct ksm_rmap_item *scan_get_next_rmap_item(struct page **page)
 
 	slot = &mm_slot->slot;
 	mm = slot->mm;
+#ifdef CONFIG_PER_VMA_LOCK
+	rmap_item = NULL;
+	if (scan_get_next_rmap_item_vma(mm_slot, page, &rmap_item,
+			&vma_scan_complete, &mm_wr_seq))
+		return rmap_item;
+#endif
+	/* Recheck the end of the scan under mmap_lock before removing the mm. */
 	vma_iter_init(&vmi, mm, ksm_scan.address);
 
 	mmap_read_lock(mm);
+	if (vma_scan_complete && !mmap_lock_speculate_retry(mm, mm_wr_seq))
+		skip_vma_scan = true;
 	if (ksm_test_exit(mm))
 		goto no_vmas;
 
+	if (skip_vma_scan)
+		goto scan_cleanup;
 	for_each_vma(vmi, vma) {
 		if (!(vma->vm_flags & VM_MERGEABLE))
 			continue;
@@ -2785,6 +2891,7 @@ static struct ksm_rmap_item *scan_get_next_rmap_item(struct page **page)
 		}
 	}
 
+scan_cleanup:
 	if (ksm_test_exit(mm)) {
 no_vmas:
 		ksm_scan.address = 0;
-- 
2.43.0