Re: [PATCH v2 1/2] mm/ksm: align smart scan skips with the scan number

["Xu Xin (vivo)" <xu.xin@linux.dev>]

On Thu, Nov 05, 2026 at 04:36:14AM -0500, Qiliang Yuan wrote:
> Smart scan skips pages that KSM has failed to de-duplicate for a while.
> Once a page is three scans old, its rmap_item counts down its own number
> of scans to skip, 1, 2, 4 and then 8 as it ages, so an old page is looked
> at every ninth scan.
> 
> The unstable tree is rebuilt on every scan, so two identical pages that
> are not in the stable tree yet can only be merged in a scan that looks
> at both. Each countdown runs from when its own page became mergeable, so
> two pages that became mergeable at different times end up on different
> phases and, once both are old, may never be looked at in the same scan
> again. They then stay unmerged for as long as they live. Making a page
> mergeable, waiting for 0 to 20 full scans before doing the same with an
> identical page, 20 times for each wait, and checking the pair after
> another 64 full scans shows this, on two boots per kernel:
> 
>                                 before            after
>   pairs merged (of 420)         329 / 317         420 / 420
>   64M of unique pages skipped   89.0% / 89.1%     87.5% / 87.5%
>   ksmd CPU time per scan        6.25 / 6.25 ms    6.88 / 7.03 ms
> 
> Pick the skipped scans by the global scan number instead, with periods
> of 2, 4 and 8 scans. The periods being powers of two, every old page is
> looked at on each scan that is a multiple of 8, whatever its age, so any
> two pages meet at least every eighth scan. The longest period goes from
> nine scans to eight, which costs 10-12% more ksmd time on memory that
> never merges.
> 
> Fixes: 5e924ff54d08 ("mm/ksm: add "smart" page scanning mode")
> Signed-off-by: Qiliang Yuan <odys.yuan@gmail.com>
> ---
>  mm/ksm.c | 24 ++++++++++--------------
>  1 file changed, 10 insertions(+), 14 deletions(-)

Brilliant design.
By using the global ksm_scan.seqnr as a unified time base, this patch eliminates
the out-of-sync problem of the original per-page skip counters.

It guarantees that any two pages will be processed in the same scan at least once
every 8 scans — the least common multiple of all scan periods — which completely
resolves the permanent de-duplication failure.

Admittedly, this comes at the cost of shrinking the longest scan interval from 9
to 8 scans, raising the scan frequency for aged pages by roughly 12.5%. But I
believe this is a very reasonable trade-off for correctness. So

Reviewed-by: Xu Xin (vivo) <xu.xin@linux.dev>


Besides, can we add a extra description about new smart_scan algorithm that we
missed in Documentation/mm/ksm.rst?

> 
> diff --git a/mm/ksm.c b/mm/ksm.c
> index dbfb8f98b1892..a97d7563c2124 100644
> --- a/mm/ksm.c
> +++ b/mm/ksm.c
> @@ -196,7 +196,6 @@ struct ksm_stable_node {
>   * @head: pointer to stable_node heading this list in the stable tree
>   * @hlist: link into hlist of rmap_items hanging off that stable_node
>   * @age: number of scan iterations since creation (unstable node)
> - * @remaining_skips: how many scans to skip (unstable node)
>   * @linear_page_index: the original page's index before merged by KSM (stable node)
>   */
>  struct ksm_rmap_item {
> @@ -213,7 +212,6 @@ struct ksm_rmap_item {
>  		struct {
>  			unsigned int oldchecksum;
>  			rmap_age_t age;
> -			rmap_age_t remaining_skips;
>  		};			/* when unstable */
>  		unsigned long linear_page_index;    /* for reverse mapping, when stable */
>  	};
> @@ -2446,16 +2444,14 @@ static struct ksm_rmap_item *get_next_rmap_item(struct ksm_mm_slot *mm_slot,
>  }
>  
>  /*
> - * Calculate skip age for the ksm page age. The age determines how often
> - * de-duplicating has already been tried unsuccessfully. If the age is
> - * smaller, the scanning of this page is skipped for less scans.
> + * Calculate how often a page of the given ksm page age is scanned. The age
> + * determines how often de-duplicating has already been tried
> + * unsuccessfully. The older the page, the fewer scans look at it.
>   *
>   * @age: rmap_item age of page
>   */
> -static unsigned int skip_age(rmap_age_t age)
> +static unsigned int scan_period(rmap_age_t age)
>  {
> -	if (age <= 3)
> -		return 1;
>  	if (age <= 5)
>  		return 2;
>  	if (age <= 8)
> @@ -2505,17 +2501,17 @@ static bool should_skip_rmap_item(struct folio *folio,
>  		return false;
>  
>  	/*
> -	 * Are we still allowed to skip? If not, then don't skip it
> -	 * and determine how much more often we are allowed to skip next.
> +	 * The unstable tree is rebuilt on every scan, so two identical pages
> +	 * can only be merged if both are looked at in the same scan. Pick the
> +	 * scans by the global scan number rather than per page: the periods
> +	 * are powers of two, so pages of any age meet on every scan that is a
> +	 * multiple of the longest one.
>  	 */
> -	if (!rmap_item->remaining_skips) {
> -		rmap_item->remaining_skips = skip_age(age);
> +	if (!(ksm_scan.seqnr & (scan_period(age) - 1)))
>  		return false;
> -	}
>  
>  	/* Skip this page */
>  	ksm_pages_skipped++;
> -	rmap_item->remaining_skips--;
>  	remove_rmap_item_from_tree(rmap_item);
>  	return true;
>  }
> 
> -- 
> 2.43.0
>