percpu: Fix wrong chunk hints update
Subsystems (2)
PATCH v5 1/4 percpu: Fix wrong chunk hints update
Chunk end offset was set to a block end offset, which could prevent chunk hints from being updated correctly. It was observed that the chunk free size gets minus or shorter than the actual free size due to this. This commit fixes it.
---
v5: No change.
v4: Add Fixes tag.
v3: Initial version.
mm/percpu.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
mm/percpu.c +1 -1
@@ -1054,7 +1054,7 @@ static void pcpu_block_update_hint_free(struct pcpu_chunk *chunk, int bit_off,else pcpu_block_update (&chunk->chunk_md,pcpu_block_off_to_off (s_index, start), - end); +pcpu_block_off_to_off (e_index, end)); }/**
Signature · 1 line
2.54.0.563.g4f69b47b94-goog
PATCH v5 2/4 percpu: Do not trust hint starts when they are not set
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.
---
v5: No change.
v4: Remove the separate contig_hint == 0 case and handle the case in the
following code. Add more checks for scan_hint.
v3: Initial version.
mm/percpu.c | 20 +++++++++++++------- 1 file changed, 13 insertions(+), 7 deletions(-)
mm/percpu.c +13 -7
@@ -640,12 +640,13 @@ 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 && 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) { + }else if (block->scan_hint && + start < block->scan_hint_start) {/* * The old contig_hint == scan_hint. But, the * new contig is larger so hold the invariant
@@ -664,10 +665,12 @@ static void pcpu_block_update(struct pcpu_block_md *block, int start, int end) __ffs(start) > __ffs(block->contig_hint_start))) {/* start has a better alignment so use it */ block->contig_hint_start = start; -if (start < block->scan_hint_start && +if (block->scan_hint && + start < block->scan_hint_start && block->contig_hint > block->scan_hint) block->scan_hint =0 ; - } else if (start > block->scan_hint_start || + } else if ((block->scan_hint && + start > block->scan_hint_start) || block->contig_hint > block->scan_hint) {/* * Knowing contig == contig_hint, update the scan_hint
@@ -845,7 +848,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 +893,8 @@ 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 +927,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,
Signature · 1 line
2.54.0.563.g4f69b47b94-goog
PATCH v5 3/4 percpu: Introduce struct pcpu_region
In reply to Joonwon KangThe new struct is introduced to prevent mis-use of hint start and size and improve readability.
---
v5: Add missing change for mm/percpu-stats.c.
v4: Initial version.
mm/percpu-internal.h | 24 +++-- mm/percpu-stats.c | 2 +- mm/percpu.c | 244 ++++++++++++++++++++----------------------- 3 files changed, 131 insertions(+), 139 deletions(-)
mm/percpu-internal.h +15 -9
@@ -6,6 +6,15 @@#include <linux/percpu.h> #include <linux/memcontrol.h> +/* +* pcpu region represents a hint region. +* A region is only valid when @size is greater than 0. +*/ +struct pcpu_region { +int start; +int size; +}; +/* * pcpu_block_md is the metadata block struct. * Each chunk's bitmap is split into a number of full blocks.
@@ -13,17 +22,14 @@* * The scan hint is the largest known contiguous area before the contig hint. * It is not necessarily the actual largest contig hint though. There is an -* invariant that the scan_hint_start > contig_hint_start iff -* scan_hint == contig_hint. This is necessary because when scanning forward, -* we don't know if a new contig hint would be better than the current one. +* invariant that the scan_hint.start > contig_hint.start iff +* scan_hint.size == contig_hint.size. This is necessary because when scanning +* forward, we don't know if a new contig hint would be better than the current +* one. */ struct pcpu_block_md { -int scan_hint;/* scan hint for block */ -int scan_hint_start;/* block relative starting -position of the scan hint */ -int contig_hint;/* contig hint for block */ -int contig_hint_start;/* block relative starting -position of the contig hint */ +struct pcpu_region scan_hint;/* scan hint for block */ +struct pcpu_region contig_hint;/* contig hint for block */ int left_free;/* size of free space along the left side of the block */ int right_free;/* size of free space along
mm/percpu-stats.c +1 -1
@@ -122,7 +122,7 @@ static void chunk_map_stats(struct seq_file *m, struct pcpu_chunk *chunk,P ("empty_pop_pages" , chunk->nr_empty_pop_pages);P ("first_bit" , chunk_md->first_free);P ("free_bytes" , chunk->free_bytes); -P ("contig_bytes" , chunk_md->contig_hint *PCPU_MIN_ALLOC_SIZE ); +P ("contig_bytes" , chunk_md->contig_hint.size *PCPU_MIN_ALLOC_SIZE );P ("sum_frag" , sum_frag);P ("max_frag" , max_frag);P ("cur_min_alloc" , cur_min_alloc);
mm/percpu.c +115 -129
422 lines not on this page · raw message
Signature · 1 line
2.54.0.563.g4f69b47b94-goog
PATCH v5 4/4 percpu: Fix hint invariant breakage
In reply to Joonwon KangThe 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:
- 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.
---
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 | 119 +++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 94 insertions(+), 25 deletions(-)
mm/percpu.c +94 -25
@@ -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) +{ +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, + }; + +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. +*/ +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) 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,41 @@ 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 ; + } +/* 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) { +/* +* old scan_hint.size < new contig size +* == old contig_hint.size. But, the new +* contig is before the old contig_hint +* so hold the invariant +* scan_hint.start > contig_hint.start +* iff scan_hint.size == +* contig_hint.size. +*/ + block->scan_hint.size =0 ; + }else { + block->scan_hint = free; + } + }else if (free.start > block->scan_hint.start) { + block->scan_hint = free; + } } }else {/*
Signature · 1 line
2.54.0.563.g4f69b47b94-goog
Andrew Morton
maintainerRe: [PATCH v5 4/4] percpu: Fix hint invariant breakage
Quoted 9 lines · On Sun, 10 May 2026 07:21:49 +0000 Joonwon Kang <[email protected]> wrote:
The invariant "
scan_hint_start>contig_hint_startif and only ifscan_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 newcontig_hintdue to its better alignment, thenscan_hintshould be invalidated instead of keeping the old value.
Quoted 5 lines
- if (new contig ==
contig_hint>scan_hint) && (new contig start <contig_hint_start) && the new contig is not to become a newcontig_hint, thenscan_hintshould be not updated to the new contig.This commit mainly fixes this invariant breakage and includes more:
Thanks. AI review asked a single question:
https://sashiko.dev/#/patchset/[email protected]
Re: [PATCH v5 4/4] percpu: Fix hint invariant breakage
Quoted 11 lines · On Sun, 10 May 2026 07:21:49 +0000 Joonwon Kang <[email protected]> wrote:
Quoted 10 lines
The invariant "
scan_hint_start>contig_hint_startif and only ifscan_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 newcontig_hintdue to its better alignment, thenscan_hintshould be invalidated instead of keeping the old value.
Quoted 8 lines
Quoted 5 lines
- if (new contig ==
contig_hint>scan_hint) && (new contig start <contig_hint_start) && the new contig is not to become a newcontig_hint, thenscan_hintshould be not updated to the new contig.This commit mainly fixes this invariant breakage and includes more:
Thanks. AI review asked a single question:
https://sashiko.dev/#/patchset/[email protected]
Thanks for sharing it. Let me answer it inline.
Quoted 39 lines
Quoted 4 lines
mm/percpu.c +0
-0[ ... ]
Quoted 4 lines
mm/percpu.c +0
-0@@ -661,21 +710,41 @@ 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))) {[ ... ]
Quoted 18 lines
mm/percpu.c +3
-13/* 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) {mm/percpu.c static void pcpu_block_update(struct pcpu_block_md *block, int start, int end) · line 741
Quoted 10 lines
mm/percpu.c +10
-0+/* +* old scan_hint.size < new contig size +* == old contig_hint.size. But, the new +* contig is before the old contig_hint +* so hold the invariant +* scan_hint.start > contig_hint.start +* iff scan_hint.size == +* contig_hint.size. +*/ + block->scan_hint.size =0 ;Does this code unnecessarily invalidate the existing
scan_hintby setting its
Quoted 8 lines
size to 0?
Sinceblock->contig_hint.size>block->scan_hint.sizein this branch, it appears the existingscan_hintalready satisfies the invariant. While updatingscan_hintto free would violate the invariant because free.start < contig_hint.start, simply retaining the oldscan_hintrather than actively zeroing it seems to preserve the invariant.
Could we leave the existingscan_hintintact here instead of clearing it to prevent a regression from losing a valid allocator hint?
If the old scan_hint is before the new free region, it makes sense to leave the old scan_hint as-is and I don't see much demerit of it. If the old scan_hint is after the new free region, however, leaving the old scan_hint as-is is more likely to break the contig_hint later and I guess it is still better to scan from 0 in that case. So, let me more diverge in this case.
Thanks,
Joonwon Kang
Quoted 7 lines
Quoted 7 lines
mm/percpu.c +6
-0+ }else { + block->scan_hint = free; + } + }else if (free.start > block->scan_hint.start) { + block->scan_hint = free; + } }