* [PATCH v3 2/3] percpu: Do not trust hint starts when they are not set
2026-04-10 17:44 [PATCH v3 1/3] percpu: Fix wrong chunk hints update Joonwon Kang
@ 2026-04-10 17:44 ` Joonwon Kang
2026-04-10 17:44 ` [PATCH v3 3/3] percpu: Fix hint invariant breakage Joonwon Kang
1 sibling, 0 replies; 3+ messages in thread
From: Joonwon Kang @ 2026-04-10 17:44 UTC (permalink / raw)
To: dennis, tj, cl; +Cc: akpm, linux-mm, linux-kernel, dodam, Joonwon Kang
contig_hint_start can be trusted outside the hint update function since
it will be updated everytime contig_hint is broken. On the other hand,
scan_hint_start might still be invalid anywhere in the code due to the
broken scan_hint not being updated promptly. If those starts are trusted
when they are not set, it could lead to false invalidation or update of
the hints.
Signed-off-by: Joonwon Kang <joonwonkang@google.com>
---
v3: Initial version.
mm/percpu.c | 15 ++++++++++++---
1 file changed, 12 insertions(+), 3 deletions(-)
diff --git a/mm/percpu.c b/mm/percpu.c
index 3ecd86096641..f16533ed4a49 100644
--- a/mm/percpu.c
+++ b/mm/percpu.c
@@ -638,6 +638,13 @@ static void pcpu_block_update(struct pcpu_block_md *block, int start, int end)
if (end == block->nr_bits)
block->right_free = contig;
+ if (block->contig_hint == 0) {
+ block->contig_hint = contig;
+ block->contig_hint_start = start;
+ block->scan_hint = 0;
+ return;
+ }
+
if (contig > block->contig_hint) {
/* promote the old contig_hint to be the new scan_hint */
if (start > block->contig_hint_start) {
@@ -845,7 +852,8 @@ static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off,
PCPU_BITMAP_BLOCK_BITS,
s_off + bits);
- if (pcpu_region_overlap(s_block->scan_hint_start,
+ if (s_block->scan_hint &&
+ pcpu_region_overlap(s_block->scan_hint_start,
s_block->scan_hint_start + s_block->scan_hint,
s_off,
s_off + bits))
@@ -889,7 +897,7 @@ static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off,
/* reset the block */
e_block++;
} else {
- if (e_off > e_block->scan_hint_start)
+ if (e_block->scan_hint && e_off > e_block->scan_hint_start)
e_block->scan_hint = 0;
e_block->left_free = 0;
@@ -922,7 +930,8 @@ static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off,
if (nr_empty_pages)
pcpu_update_empty_pages(chunk, -nr_empty_pages);
- if (pcpu_region_overlap(chunk_md->scan_hint_start,
+ if (chunk_md->scan_hint &&
+ pcpu_region_overlap(chunk_md->scan_hint_start,
chunk_md->scan_hint_start +
chunk_md->scan_hint,
bit_off,
--
2.53.0.1213.gd9a14994de-goog
^ permalink raw reply related [flat|nested] 3+ messages in thread* [PATCH v3 3/3] percpu: Fix hint invariant breakage
2026-04-10 17:44 [PATCH v3 1/3] percpu: Fix wrong chunk hints update Joonwon Kang
2026-04-10 17:44 ` [PATCH v3 2/3] percpu: Do not trust hint starts when they are not set Joonwon Kang
@ 2026-04-10 17:44 ` Joonwon Kang
1 sibling, 0 replies; 3+ messages in thread
From: Joonwon Kang @ 2026-04-10 17:44 UTC (permalink / raw)
To: dennis, tj, cl; +Cc: akpm, linux-mm, linux-kernel, dodam, Joonwon Kang
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
^ permalink raw reply related [flat|nested] 3+ messages in thread