Re: [PATCH v6 4/4] percpu: Fix hint invariant breakage

[Dennis Zhou <dennis@kernel.org>]

On Wed, May 13, 2026 at 08:51:16AM +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.

I think keeping scan_hint should be fine here? I guess what's the harm,
I'm seeing a setup like:

[old_contig_hint, ..., scan_hint, .... , contig_hint]

The large scan_hint just says we should try to bin pack, we use
first_free rather than jumping past it. See pcpu_next_hint().

> 
>   - 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.

Similar to the above, the goal is just to say hey we should scan from
first_free.

> 
> This commit mainly fixes this invariant breakage and includes more:
> 
>   - Handle the cases where the new contig overlaps with the contig_hint
>     or with scan_hint.
> 
>   - 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>
> ---
> v6: Diverge more when the new contig size is the same as the old
>     contig_hint size but greater than the old scan_hint, does not become a
>     new contig_hint and is before the old contig_hint.
> v5: No change.
> v4: Refactor code by removing the scan_hint candidates and handle the
>     overlapping cases where the new contig meets with the hints on the
>     border.
> 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.
> v2: Consider the cases where the new contig overlaps with the existing
>     contig_hint or scan_hint. Introduce the scan_hint candidates to
>     calculate new scan_hint.
> v1: Initial version.
> 
>  mm/percpu.c | 118 +++++++++++++++++++++++++++++++++++++++++-----------
>  1 file changed, 93 insertions(+), 25 deletions(-)
> 
> diff --git a/mm/percpu.c b/mm/percpu.c
> index 89b7f33500cf..1a0e1e84d92a 100644
> --- a/mm/percpu.c
> +++ b/mm/percpu.c
> @@ -616,6 +616,20 @@ static inline bool pcpu_region_overlap(struct pcpu_region a,
>  	return (a.start < b.start + b.size) && (b.start < a.start + a.size);
>  }
>  
> +/*
> + * pcpu_region_concat - determines if two regions meet on the border
> + * @a: first region
> + * @b: second region
> + *
> + * This is used to determine if the hint region [a.start, a.start + a.size)
> + * meets with the allocated region [b.start, b.start + b.size) on the border.
> + */
> +static inline bool pcpu_region_concat(struct pcpu_region a,
> +				      struct pcpu_region b)

Can we name this something like pcpu_region_adjacent(). concat is a bit
confusing as I think of string concat.

> +{
> +	return (a.start == b.start + b.size) || (b.start == a.start + a.size);
> +}
> +
>  /**
>   * pcpu_block_update - updates a block given a free area
>   * @block: block of interest
> @@ -629,6 +643,40 @@ static inline bool pcpu_region_overlap(struct pcpu_region a,
>  static void pcpu_block_update(struct pcpu_block_md *block, int start, int end)
>  {
>  	struct pcpu_region free = { .start = start, .size = end - start };
> +	bool overlap_with_contig_hint =
> +		block->contig_hint.size &&
> +		(pcpu_region_overlap(block->contig_hint, free) ||
> +		 pcpu_region_concat(block->contig_hint, free));
> +
> +	if (block->scan_hint.size &&
> +	    (pcpu_region_overlap(block->scan_hint, free) ||
> +	     pcpu_region_concat(block->scan_hint, free))) {
> +		start = min(start, block->scan_hint.start);
> +		end = max(end, block->scan_hint.start + block->scan_hint.size);
> +		free = (struct pcpu_region){
> +			.start = start,
> +			.size = end - start,
> +		};
> +
> +		block->scan_hint.size = 0;
> +	}
> +
> +	if (overlap_with_contig_hint) {
> +		start = min(start, block->contig_hint.start);
> +		end = max(end,
> +			  block->contig_hint.start + block->contig_hint.size);
> +		free = (struct pcpu_region){
> +			.start = start,
> +			.size = end - start,
> +		};

It seems like you want a function more like:

struct pcpu_region pcpu_merge_regions(struct pcpu_region a,
    struct pcpu_region b);

Then earlier we can call:
pcpu_merge_regions(free, scan_hint);
pcpu_merge_regions(free, contig_hint);

and then avoid introducing pcpu_region_concat().

> +
> +		if (block->scan_hint.size &&
> +		    free.size > block->scan_hint.size &&
> +		    block->scan_hint.start > free.start)
> +			block->scan_hint.size = 0;
> +
> +		block->contig_hint = free;
> +	}
>  
>  	block->first_free = min(block->first_free, free.start);
>  	if (free.start == 0)
> @@ -637,23 +685,24 @@ static void pcpu_block_update(struct pcpu_block_md *block, int start, int end)
>  	if (free.start + free.size == block->nr_bits)
>  		block->right_free = free.size;
>  
> +	if (overlap_with_contig_hint)
> +		return;
> +
> +	/*
> +	 * At this point, it is guaranteed that the new contig does neither
> +	 * overlap with contig_hint nor with scan_hint.
> +	 */
> +

nit: ^ remove the extra new line here.

>  	if (free.size > block->contig_hint.size) {
>  		/* promote the old contig_hint to be the new scan_hint */
>  		if (block->contig_hint.size &&
>  		    free.start > block->contig_hint.start) {
> -			if (block->contig_hint.size > block->scan_hint.size) {
> +			if (block->contig_hint.size > block->scan_hint.size ||
> +			    free.start < block->scan_hint.start)

I don't think this condition matters? Wouldn't we want to always promote
here.

>  				block->scan_hint = block->contig_hint;
> -			} else if (block->scan_hint.size &&
> -				   free.start < block->scan_hint.start) {
> -				/*
> -				 * The old contig_hint.size == scan_hint.size.
> -				 * But, the new contig is larger so hold the
> -				 * invariant scan_hint.start <
> -				 * contig_hint.start.
> -				 */
> -				block->scan_hint.size = 0;
> -			}
> -		} else {
> +		} else if (!block->contig_hint.size ||
> +			   (block->scan_hint.size &&
> +			    free.start < block->scan_hint.start)) {
>  			block->scan_hint.size = 0;
>  		}
>  		block->contig_hint = free;
> @@ -661,21 +710,40 @@ static void pcpu_block_update(struct pcpu_block_md *block, int start, int end)
>  		if (block->contig_hint.start &&
>  		    (!free.start ||
>  		     __ffs(free.start) > __ffs(block->contig_hint.start))) {
> +			if (block->contig_hint.size > block->scan_hint.size) {
> +				if (free.start < block->contig_hint.start)
> +					block->scan_hint = block->contig_hint;
> +			} else if (free.start > block->scan_hint.start) {
> +				/*
> +				 * old contig_hint.size == old scan_hint.size
> +				 * == new contig size. But, the new contig is
> +				 * farther than the old scan_hint so hold the
> +				 * invariant scan_hint.start > contig_hint.start
> +				 * iff scan_hint.size == contig_hint.size.
> +				 */
> +				block->scan_hint.size = 0;

I think this is the one I disagreed with in the commit message.

> +			}
> +
>  			/* new start has a better alignment so use it */
>  			block->contig_hint.start = free.start;
> -			if (block->scan_hint.size &&
> -			    free.start < block->scan_hint.start &&
> -			    block->contig_hint.size > block->scan_hint.size)
> -				block->scan_hint.size = 0;
> -		} else if ((block->scan_hint.size &&
> -			    free.start > block->scan_hint.start) ||
> -			   block->contig_hint.size > block->scan_hint.size) {
> -			/*
> -			 * Knowing new contig size == contig_hint.size, update
> -			 * the scan_hint if it is farther than or larger than
> -			 * the current scan_hint.
> -			 */
> -			block->scan_hint = free;
> +		} else {
> +			if (block->contig_hint.size > block->scan_hint.size) {
> +				if (free.start > block->contig_hint.start) {
> +					block->scan_hint = free;
> +				} else if (block->scan_hint.size &&
> +					   free.start < block->scan_hint.start) {
> +					/*
> +					 * old scan_hint.size < new contig size
> +					 * == old contig_hint.size. But, the new
> +					 * contig is before the old scan_hint
> +					 * so invalidate the scan_hint to
> +					 * protect the contig_hint.
> +					 */
> +					block->scan_hint.size = 0;

Why would we not take scan_hint = free here?

> +				}
> +			} else if (free.start > block->scan_hint.start) {
> +				block->scan_hint = free;
> +			}
>  		}
>  	} else {
>  		/*
> -- 
> 2.54.0.563.g4f69b47b94-goog
> 

I think I'm struggling a bit between what changes are correctness
related vs optimizations vs code readability.

Maybe when you address the comments, it might be good to split this
commit up.

Thanks,
Dennis