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

[Joonwon Kang <joonwonkang@google.com>]

Appreciate your insightful reviews!

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

Agree that this commit is doing much of work. However, when I tried only
fixing the scan_hint issues without refactoring earlier, I realized that
the overlapping cases were also not being handled properly in this
function. Without handling the overlapping cases, there could be other
hidden scan_hint breakage issues. Handling the overlapping cases required
restructuring of the function, which led to the changes to the code that
were also required for resolving the scan_hint issues. Let me see if I
can decently split them.

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

It will be great if we introduce the struct. I will do it as a separate
patch in v4.

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

Acknowledged.

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

Hmm, with this, if contig_hint == scan_hint && new_region overlaps only
with contig_hint && the entire overlapped region > contig_hint, then we
will have a wrong scan_hint, i.e. new contig_hint_start < scan_hint_start
even though new contig_hint > scan_hint.

But, I can see your point here. Let me see if I can get rid of cand_1 and
cand_2.

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

Thanks,
Joonwon Kang