Re: [PATCH v3 3/3] percpu: Fix hint invariant breakage

[Dennis Zhou <dennis@kernel.org>]

On Fri, Apr 10, 2026 at 05:44:17PM +0000, Joonwon Kang wrote:
> The invariant "scan_hint_start > contig_hint_start if and only if
> scan_hint == contig_hint" should be kept for hint management. However,
> it could be broken in some cases:
> 
>   - if (new contig == contig_hint == scan_hint) && (contig_hint_start <
>     scan_hint_start < new contig start) && the new contig is to become a
>     new contig_hint due to its better alignment, then scan_hint should
>     be invalidated instead of keeping the old value.
> 
>   - if (new contig == contig_hint > scan_hint) && (new contig start <
>     contig_hint_start) && the new contig is not to become a new
>     contig_hint, then scan_hint should be not updated to the new contig.
> 
> This commit mainly fixes this invariant breakage and includes more:
> 
>   - Refactor the percpu block update code to make it more visible on
>     what to consider, e.g. when the new contig overlaps with the old
>     contig_hint or scan_hint.
> 

Could you please split this up between the fixing the scan_hint issues
and then refactoring. That way this commit isn't doing too much.

>   - Merge the new contig with other hints when it overlaps with them and
>     treat it as a whole free region instead of a separate small region.
> 
>   - Fix the invariant breakage and also optimizes scan_hint further.
>     Some of the optimization cases when no overlap occurs are:
> 
>     - if (new contig > contig_hint > scan_hint) && (scan_hint_start < new
>       contig start < contig_hint_start), then keep scan_hint instead of
>       invalidating it.
> 
>     - if (new contig > contig_hint == scan_hint) && (contig_hint_start <
>       new contig start < scan_hint_start), then update scan_hint to the
>       old contig_hint instead of invalidating it.
> 
>     - if (new contig == contig_hint > scan_hint) && (new contig start <
>       contig_hint_start) && the new contig is to become a new contig_hint
>       due to its better alignment, then update scan_hint to the old
>       contig_hint instead of invalidating or keeping it.
> 
> Signed-off-by: Joonwon Kang <joonwonkang@google.com>
> ---
> v2 -> v3: Merge the new contig with other hints when it overlaps with
>   them and treat it as a whole free region instead of a separate small
>   region.
> 
> v1 -> v2: Consider cases where the new contig overlaps with the existing
>   contig_hint or scan_hint.
> 
>  mm/percpu.c | 130 ++++++++++++++++++++++++++++++++++++----------------
>  1 file changed, 90 insertions(+), 40 deletions(-)
> 
> diff --git a/mm/percpu.c b/mm/percpu.c
> index f16533ed4a49..d5b0b4863ffe 100644
> --- a/mm/percpu.c
> +++ b/mm/percpu.c
> @@ -629,7 +629,27 @@ static inline bool pcpu_region_overlap(int a, int b, int x, int y)
>   */
>  static void pcpu_block_update(struct pcpu_block_md *block, int start, int end)
>  {
> -	int contig = end - start;
> +	int contig;
> +	int scan_hint_cand_1 = 0;
> +	int scan_hint_cand_1_start = 0;
> +	int scan_hint_cand_2 = 0;
> +	int scan_hint_cand_2_start = 0;

I'm not really a fan of this cand_1 and cand_2. Re-reading all this
code. I think I really should have introduced something like:

struct pcpu_region {
    int start;
    int size;
}

It's really easy to mix contig_hint and contig_hint_start. If you don't
mind, it would be ideal if we could introduce it but it might be a
non-trivial amount of refactor.

I'd say the shortest path forward would be to do just to fix the
scan_hint issues.

> +	bool overlap_with_contig_hint = pcpu_region_overlap(start, end,
> +		block->contig_hint_start,
> +		block->contig_hint_start + block->contig_hint);
> +	bool overlap_with_scan_hint = pcpu_region_overlap(start, end,
> +		block->scan_hint_start,
> +		block->scan_hint_start + block->scan_hint);
> +

This one isn't used again so we should probably just inline it.

> +	if (block->contig_hint && overlap_with_contig_hint) {
> +		start = min(start, block->contig_hint_start);
> +		end = max(end, block->contig_hint_start + block->contig_hint);
> +	}
> +	if (block->scan_hint && overlap_with_scan_hint) {
> +		start = min(start, block->scan_hint_start);
> +		end = max(end, block->scan_hint_start + block->scan_hint);
> +	}
> +	contig = end - start;
>  
>  	block->first_free = min(block->first_free, start);
>  	if (start == 0)
> @@ -646,56 +666,86 @@ static void pcpu_block_update(struct pcpu_block_md *block, int start, int end)
>  	}
>  
>  	if (contig > block->contig_hint) {
> -		/* promote the old contig_hint to be the new scan_hint */
> -		if (start > block->contig_hint_start) {
> -			if (block->contig_hint > block->scan_hint) {
> -				block->scan_hint_start =
> -					block->contig_hint_start;
> -				block->scan_hint = block->contig_hint;
> -			} else if (start < block->scan_hint_start) {
> -				/*
> -				 * The old contig_hint == scan_hint.  But, the
> -				 * new contig is larger so hold the invariant
> -				 * scan_hint_start < contig_hint_start.
> -				 */
> -				block->scan_hint = 0;
> -			}
> -		} else {
> -			block->scan_hint = 0;
> +		if (!overlap_with_contig_hint) {
> +			scan_hint_cand_1 = block->contig_hint;
> +			scan_hint_cand_1_start = block->contig_hint_start;
>  		}
> -		block->contig_hint_start = start;
> +
>  		block->contig_hint = contig;
> +		block->contig_hint_start = start;
>  	} else if (contig == block->contig_hint) {
>  		if (block->contig_hint_start &&
>  		    (!start ||
>  		     __ffs(start) > __ffs(block->contig_hint_start))) {
> -			/* start has a better alignment so use it */
> +			scan_hint_cand_1 = block->contig_hint;
> +			scan_hint_cand_1_start = block->contig_hint_start;
> +
> +			/* Start has a better alignment so use it. */
>  			block->contig_hint_start = start;
> -			if (start < block->scan_hint_start &&
> -			    block->contig_hint > block->scan_hint)
> -				block->scan_hint = 0;
> -		} else if (start > block->scan_hint_start ||
> -			   block->contig_hint > block->scan_hint) {
> -			/*
> -			 * Knowing contig == contig_hint, update the scan_hint
> -			 * if it is farther than or larger than the current
> -			 * scan_hint.
> -			 */
> -			block->scan_hint_start = start;
> -			block->scan_hint = contig;
> +		} else {
> +			if (!overlap_with_contig_hint) {
> +				scan_hint_cand_1 = contig;
> +				scan_hint_cand_1_start = start;
> +			}
>  		}
>  	} else {
>  		/*
> -		 * The region is smaller than the contig_hint.  So only update
> -		 * the scan_hint if it is larger than or equal and farther than
> -		 * the current scan_hint.
> +		 * Consider only when the new contig is larger than or equal to
> +		 * the old scan hint.
>  		 */
> -		if ((start < block->contig_hint_start &&
> -		     (contig > block->scan_hint ||
> -		      (contig == block->scan_hint &&
> -		       start > block->scan_hint_start)))) {
> -			block->scan_hint_start = start;
> -			block->scan_hint = contig;
> +		if (contig >= block->scan_hint) {
> +			scan_hint_cand_1 = contig;
> +			scan_hint_cand_1_start = start;
> +		}
> +	}
> +
> +	if (block->scan_hint &&
> +	    !pcpu_region_overlap(start, end, block->scan_hint_start,
> +				 block->scan_hint_start + block->scan_hint)) {
> +		scan_hint_cand_2 = block->scan_hint;
> +		scan_hint_cand_2_start = block->scan_hint_start;
> +	}
> +
> +	/* Make scan_hint_cand_1 be the best candidate for the new scan hint. */
> +	if ((scan_hint_cand_2 > scan_hint_cand_1) ||
> +	    (scan_hint_cand_2 == scan_hint_cand_1 &&
> +	     scan_hint_cand_2_start > scan_hint_cand_1_start)) {
> +		int tmp_hint = scan_hint_cand_1;
> +		int tmp_hint_start = scan_hint_cand_1_start;
> +
> +		scan_hint_cand_1 = scan_hint_cand_2;
> +		scan_hint_cand_1_start = scan_hint_cand_2_start;
> +		scan_hint_cand_2 = tmp_hint;
> +		scan_hint_cand_2_start = tmp_hint_start;
> +	}
> +
> +	/*
> +	 * At this point, it is guaranteed that none of the scan hint
> +	 * candidates overlaps with the new contig hint while they may overlap
> +	 * with the old scan hint, and that the first candidate is larger in
> +	 * size or, it equal, farther than the second one.
> +	 */
> +
> +	if (block->contig_hint > scan_hint_cand_1) {
> +		if (scan_hint_cand_1_start < block->contig_hint_start) {
> +			block->scan_hint = scan_hint_cand_1;
> +			block->scan_hint_start = scan_hint_cand_1_start;
> +		} else if (scan_hint_cand_2_start < block->contig_hint_start) {
> +			block->scan_hint = scan_hint_cand_2;
> +			block->scan_hint_start = scan_hint_cand_2_start;
> +		} else {
> +			block->scan_hint = 0;
> +		}
> +	} else if (block->contig_hint == scan_hint_cand_1) {
> +		if (scan_hint_cand_1_start > block->contig_hint_start) {
> +			block->scan_hint = scan_hint_cand_1;
> +			block->scan_hint_start = scan_hint_cand_1_start;
> +		} else if (scan_hint_cand_2 < block->contig_hint &&
> +			   scan_hint_cand_2_start < scan_hint_cand_1_start) {
> +			block->scan_hint = scan_hint_cand_2;
> +			block->scan_hint_start = scan_hint_cand_2_start;
> +		} else {
> +			block->scan_hint = 0;
>  		}


This seems easier to invert and do something like this:

Probably something like:

bool overlap_contig_hint = pcpu_region_overlap(new_region, scan_hint);
bool overlap_scan_hint = pcpu_region_overlap(new_region, scan_hint);

if (overlap_scan_hint) {
    scan_hint = 0;
}

if (overlap_contig_hint) {
    contig_hint = new_region;
    return;
}

// Now the new_region is distinct from the contig_hint and then can do
// the standard logic here.

if (new_region > contig_hint) { }
else if (new_region == contig_hint) {}
else {}

What do you think? I think makes cand_1 and cand_2 not necessary.

>  	}
>  }
> -- 
> 2.53.0.1213.gd9a14994de-goog
> 

Thanks,
Dennis