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

Dennis Zhou
2026-04-22T00:04:25Z

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