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

Joonwon Kang
2026-04-10T17:44:27Z

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.

- 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;
+ 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);
+
+ 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;
}
}
}
--
2.53.0.1213.gd9a14994de-goog