percpu: Fix hint invariant breakage
Subsystems (2)
PATCH 1/1 percpu: Fix hint invariant breakage
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 it.
- if (new contig == contig_hint > scan_hint) && (start < contig_hint_start) && the new contig is not to become a new contig_hint, then scan_hint should be invalidated instead of being updated to the new contig.
This commit fixes this invariant breakage and also optimizes scan_hint by keeping it or updating it when acceptable:
- 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.
--- mm/percpu.c | 60 ++++++++++++++++++++++++++++++++++------------------- 1 file changed, 39 insertions(+), 21 deletions(-)
mm/percpu.c +39 -21
@@ -641,19 +641,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 > block->scan_hint) { +if (block->contig_hint > block->scan_hint || + start < block->scan_hint_start) { 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 { + }else if (start < block->scan_hint_start) { block->scan_hint =0 ; } block->contig_hint_start = start;
@@ -662,20 +656,44 @@ static void pcpu_block_update(struct pcpu_block_md *block, int start, int end)if (block->contig_hint_start && (!start ||__ffs (start) >__ffs (block->contig_hint_start))) { +if (block->contig_hint > block->scan_hint) { +if (start < block->contig_hint_start) { + block->scan_hint = block->contig_hint; + block->scan_hint_start = block->contig_hint_start; + } + }else if (start > block->scan_hint_start) { +/* +* old contig_hint == old scan_hint == contig. +* But, the new contig is farther than the old +* scan_hint so hold the invariant +* scan_hint_start > contig_hint_start iff +* scan_hint == contig_hint. +*/ + block->scan_hint =0 ; + } +/* 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 (block->contig_hint > block->scan_hint) { +if (start < block->contig_hint_start) { +/* +* old scan_hint < contig == old +* contig_hint. But, the new contig is +* before the old contig_hint so hold +* the invariant +* scan_hint_start > contig_hint_start +* iff scan_hint == contig_hint. +*/ + block->scan_hint =0 ; + }else { + block->scan_hint_start = start; + block->scan_hint = contig; + } + }else if (start > block->scan_hint_start) { + block->scan_hint_start = start; + block->scan_hint = contig; + } } }else {/*
Signature · 1 line
2.53.0.1018.g2bb0e51243-goog
Andrew Morton
maintainerQuoted 21 lines · On Fri, 20 Mar 2026 11:52:14 +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 it.- if (new contig ==
contig_hint>scan_hint) && (start <contig_hint_start) && the new contig is not to become a newcontig_hint, thenscan_hintshould be invalidated instead of being updated to the new contig.This commit fixes this invariant breakage and also optimizes
scan_hintby keeping it or updating it when acceptable:- if (new contig >
contig_hint>scan_hint) && (scan_hint_start< new contig start <contig_hint_start), then keepscan_hintinstead of invalidating it.
Quoted 9 lines
- if (new contig >
contig_hint==scan_hint) && (contig_hint_start< new contig start <scan_hint_start), then updatescan_hintto the oldcontig_hintinstead of invalidating it.- if (new contig ==
contig_hint>scan_hint) && (new contig start <contig_hint_start) && the new contig is to become a newcontig_hintdue to its better alignment, then updatescan_hintto the oldcontig_hintinstead of invalidating or keeping it.
Thanks. Does the change have any observable runtime effects?
Was this patch inspired by code inspection?
Quoted 33 lines · On Fri, 20 Mar 2026 11:52:14 +0000 Joonwon Kang <[email protected]> wrote:
Quoted 22 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 it.- if (new contig ==
contig_hint>scan_hint) && (start <contig_hint_start) && the new contig is not to become a newcontig_hint, thenscan_hintshould be invalidated instead of being updated to the new contig.This commit fixes this invariant breakage and also optimizes
scan_hintby keeping it or updating it when acceptable:- if (new contig >
contig_hint>scan_hint) && (scan_hint_start< new contig start <contig_hint_start), then keepscan_hintinstead of invalidating it.Quoted 9 lines
- if (new contig >
contig_hint==scan_hint) && (contig_hint_start< new contig start <scan_hint_start), then updatescan_hintto the oldcontig_hintinstead of invalidating it.- if (new contig ==
contig_hint>scan_hint) && (new contig start <contig_hint_start) && the new contig is to become a newcontig_hintdue to its better alignment, then updatescan_hintto the oldcontig_hintinstead of invalidating or keeping it.
Quoted 3 lines
Thanks. Does the change have any observable runtime effects?
Was this patch inspired by code inspection?
Yes, this change basically comes from manual code review. While there is no benchmark result or others backing up the effects of this change, Dennis may help on that later as he suggested in another review. The main point of this patch should rather be fixing the "theoretical" invariant breakage cases.
Thanks.
Dennis Zhou
maintainerHello,
Quoted 4 lines · Joonwon Kang
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:
First I'd just like to apologize. I spent an hour yesterday trying to remember why the invariant exists and the reality is this code is more clever than it needs to be.
As Andrew asked, how did you come across this? It's pretty obscure so thank you for taking the time to look at it.
Quoted 36 lines
- 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 it.- if (new contig ==
contig_hint>scan_hint) && (start <contig_hint_start) && the new contig is not to become a newcontig_hint, thenscan_hintshould be invalidated instead of being updated to the new contig.This commit fixes this invariant breakage and also optimizes
scan_hintby keeping it or updating it when acceptable:- if (new contig >
contig_hint>scan_hint) && (scan_hint_start< new contig start <contig_hint_start), then keepscan_hintinstead of invalidating it.- if (new contig >
contig_hint==scan_hint) && (contig_hint_start< new contig start <scan_hint_start), then updatescan_hintto the oldcontig_hintinstead of invalidating it.- if (new contig ==
contig_hint>scan_hint) && (new contig start <contig_hint_start) && the new contig is to become a newcontig_hintdue to its better alignment, then updatescan_hintto the oldcontig_hintinstead of invalidating or keeping it.Signed-off-by Joonwon Kang <[email protected]>--- mm/percpu.c | 60 ++++++++++++++++++++++++++++++++++------------------- 1 file changed, 39 insertions(+), 21 deletions(-)mm/percpu.c +0
-0
mm/percpu.c static void pcpu_block_update(struct pcpu_block_md *block, int start, int end) · line 645
Quoted 6 lines
mm/percpu.c +2
-1@@ -641,19 +641,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 > block->scan_hint) { +if (block->contig_hint > block->scan_hint || + start < block->scan_hint_start) {
I think this should be <=.
Given hints as [hint_start, size].
contig_hint = [64, 64]scan_hint = [160, 64]
Free [224, 32].
Without <=, we don't promote the contig_hint and leave the stale scan_hint.
mm/percpu.c static void pcpu_block_update(struct pcpu_block_md *block, int start, int end) · line 650
Quoted 13 lines
mm/percpu.c +1
-8block->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 { + }else if (start < block->scan_hint_start) {
I think this too should be <=.
scan_hint = [16, 8]contig_hint = [32, 96]
free [24, 8]
scan_hint stays [16, 8] instead of being cleared.
Quoted 63 lines
mm/percpu.c +36
-12block->scan_hint =0 ; } block->contig_hint_start = start;@@ -662,20 +656,44 @@ static void pcpu_block_update(struct pcpu_block_md *block, int start, int end)if (block->contig_hint_start && (!start ||__ffs (start) >__ffs (block->contig_hint_start))) { +if (block->contig_hint > block->scan_hint) { +if (start < block->contig_hint_start) { + block->scan_hint = block->contig_hint; + block->scan_hint_start = block->contig_hint_start; + } + }else if (start > block->scan_hint_start) { +/* +* old contig_hint == old scan_hint == contig. +* But, the new contig is farther than the old +* scan_hint so hold the invariant +* scan_hint_start > contig_hint_start iff +* scan_hint == contig_hint. +*/ + block->scan_hint =0 ; + } +/* 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 (block->contig_hint > block->scan_hint) { +if (start < block->contig_hint_start) { +/* +* old scan_hint < contig == old +* contig_hint. But, the new contig is +* before the old contig_hint so hold +* the invariant +* scan_hint_start > contig_hint_start +* iff scan_hint == contig_hint. +*/ + block->scan_hint =0 ; + }else { + block->scan_hint_start = start; + block->scan_hint = contig; + } + }else if (start > block->scan_hint_start) { + block->scan_hint_start = start; + block->scan_hint = contig; + } } }else {/* Signature · 1 line
2.53.0.1018.g2bb0e51243-goog
Ultimately as I re-read this code, it might be nice to rewrite it so that scan_hint can be kept separately. The code is a little too clever with trying to avoid stating new_region overlaps scan_hint or contig_hint.
I recently started shimming out the bitmap code in userspace so hopefully I can test it for performance / correctness more rigorously.
Thanks,
Dennis
Quoted 11 lines
Hello,
Quoted 4 lines · Joonwon Kang
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:First I'd just like to apologize. I spent an hour yesterday trying to remember why the invariant exists and the reality is this code is more clever than it needs to be.
Thanks for taking time for this and sharing more context. While you are at it, I have a fundamental question on the invariant. I had deliberation and discussion on what benefits the invariant gets to the percpu allocator by its existence. My understanding is that if we put contig_hint before scan_hint when they are the same, it is more likely that contig_hint is broken by a future allocation, which leads to a linear scan after the scan_hint for hints update, although we could save scanning upto scan_hint when contig_hint is not broken. On the other hand, if we put scan_hint before contig_hint instead, it is more likely that scan_hint is broken while keeping contig_hint, which does not lead to the linear scan for hints update, although we could not save the scanning that could be saved in the other case.
In other words, if contig_hint breaking allocations occur a lot in general with the current invariant, the performance may more suffer than without the invariant. I also think that there would be no strict reason of having the invariant.
So, could you clarify the necessity of the invariant? If there is no must reason, then I could post another spin-off patch to remove the invariant at all so that we could simplify the code and experiment the result. How do you think?
Quoted 3 lines
As Andrew asked, how did you come across this? It's pretty obscure so thank you for taking the time to look at it.
I came across this issue by manual code review and thanks for saying that.
Quoted 48 lines
Quoted 38 lines
- 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 it.- if (new contig ==
contig_hint>scan_hint) && (start <contig_hint_start) && the new contig is not to become a newcontig_hint, thenscan_hintshould be invalidated instead of being updated to the new contig.This commit fixes this invariant breakage and also optimizes
scan_hintby keeping it or updating it when acceptable:- if (new contig >
contig_hint>scan_hint) && (scan_hint_start< new contig start <contig_hint_start), then keepscan_hintinstead of invalidating it.- if (new contig >
contig_hint==scan_hint) && (contig_hint_start< new contig start <scan_hint_start), then updatescan_hintto the oldcontig_hintinstead of invalidating it.- if (new contig ==
contig_hint>scan_hint) && (new contig start <contig_hint_start) && the new contig is to become a newcontig_hintdue to its better alignment, then updatescan_hintto the oldcontig_hintinstead of invalidating or keeping it.Signed-off-by Joonwon Kang <[email protected]>--- mm/percpu.c | 60 ++++++++++++++++++++++++++++++++++------------------- 1 file changed, 39 insertions(+), 21 deletions(-)mm/percpu.c +0
-0mm/percpu.c static void pcpu_block_update(struct pcpu_block_md *block, int start, int end) · line 645
Quoted 6 lines
mm/percpu.c +2
-1@@ -641,19 +641,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 > block->scan_hint) { +if (block->contig_hint > block->scan_hint || + start < block->scan_hint_start) {I think this should be <=.
Given hints as [hint_start, size].
Quoted 7 lines
contig_hint= [64, 64]scan_hint= [160, 64]Free [224, 32].
Without <=, we don't promote the
contig_hintand leave the stalescan_hint.
Ah, I missed the fact that the new contig could be given overlapping with other hints. Will reconsider the cases and fix it. Thanks.
Quoted 17 lines
Quoted 4 lines
mm/percpu.c +0
-0block->scan_hint_start = block->contig_hint_start; block->scan_hint = block->contig_hint;mm/percpu.c static void pcpu_block_update(struct pcpu_block_md *block, int start, int end) · line 650
Quoted 10 lines
mm/percpu.c +1
-8- }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 { + }else if (start < block->scan_hint_start) {I think this too should be <=.
Quoted 6 lines
scan_hint= [16, 8]contig_hint= [32, 96]free [24, 8]
scan_hintstays [16, 8] instead of being cleared.
Will fix it, thanks.
Quoted 71 lines
Quoted 65 lines
mm/percpu.c +36
-12block->scan_hint =0 ; } block->contig_hint_start = start;@@ -662,20 +656,44 @@ static void pcpu_block_update(struct pcpu_block_md *block, int start, int end)if (block->contig_hint_start && (!start ||__ffs (start) >__ffs (block->contig_hint_start))) { +if (block->contig_hint > block->scan_hint) { +if (start < block->contig_hint_start) { + block->scan_hint = block->contig_hint; + block->scan_hint_start = block->contig_hint_start; + } + }else if (start > block->scan_hint_start) { +/* +* old contig_hint == old scan_hint == contig. +* But, the new contig is farther than the old +* scan_hint so hold the invariant +* scan_hint_start > contig_hint_start iff +* scan_hint == contig_hint. +*/ + block->scan_hint =0 ; + } +/* 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 (block->contig_hint > block->scan_hint) { +if (start < block->contig_hint_start) { +/* +* old scan_hint < contig == old +* contig_hint. But, the new contig is +* before the old contig_hint so hold +* the invariant +* scan_hint_start > contig_hint_start +* iff scan_hint == contig_hint. +*/ + block->scan_hint =0 ; + }else { + block->scan_hint_start = start; + block->scan_hint = contig; + } + }else if (start > block->scan_hint_start) { + block->scan_hint_start = start; + block->scan_hint = contig; + } } }else {/* Signature · 1 line
2.53.0.1018.g2bb0e51243-googUltimately as I re-read this code, it might be nice to rewrite it so that
scan_hintcan be kept separately. The code is a little too clever with trying to avoid statingnew_regionoverlapsscan_hintorcontig_hint.
Quoted 2 lines
I recently started shimming out the bitmap code in userspace so hopefully I can test it for performance / correctness more rigorously.
Thanks for letting me know of this. It would be great if we could test this subtle change around the invariant and the hints.
Quoted 3 lines
Thanks,
Dennis
Dennis Zhou
maintainerHello,
Sorry for the delay, I've been a bit sick.
Quoted 25 lines · Joonwon Kang
Quoted 11 lines
Hello,
Quoted 4 lines · Joonwon Kang
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:First I'd just like to apologize. I spent an hour yesterday trying to remember why the invariant exists and the reality is this code is more clever than it needs to be.
Thanks for taking time for this and sharing more context. While you are at it, I have a fundamental question on the invariant. I had deliberation and discussion on what benefits the invariant gets to the percpu allocator by its existence. My understanding is that if we put
contig_hintbeforescan_hintwhen they are the same, it is more likely thatcontig_hintis broken by a future allocation, which leads to a linear scan after thescan_hintfor hints update, although we could save scanning uptoscan_hintwhencontig_hintis not broken. On the other hand, if we putscan_hintbeforecontig_hintinstead, it is more likely thatscan_hintis broken while keepingcontig_hint, which does not lead to the linear scan for hints update, although we could not save the scanning that could be saved in the other case.
Quoted 5 lines
In other words, if
contig_hintbreaking allocations occur a lot in general with the current invariant, the performance may more suffer than without the invariant. I also think that there would be no strict reason of having the invariant.
I think the original premise is that percpu memory is quite expensive, 1 allocation costs nr_cpus * sizeof(allocation). So we do our best to bin pack at the cost of faster allocations. We could always just break the contig_hint but then over time we could cause more fragmentation.
The case that triggered this was netdev needing 8 byte objects with 16 byte alignment [1].
Quoted 5 lines
So, could you clarify the necessity of the invariant? If there is no must reason, then I could post another spin-off patch to remove the invariant at all so that we could simplify the code and experiment the result. How do you think?
I can't really recall the exact reasoning for the invariant, but it was probably along the lines of wanting to not lose information if possible.
Say an earlier area becomes free that is the same size as the contig_hint but with better alignment, we ant to use that as the contig_hint but then we either have to lose the scan_hint or keep it with the invariant. Given the premise above, I believe we want to continue bin packing, I think the general idea of scanning next time around isn't the worst thing.
Sadly because it's already there, and has worked for quite some time, it's kind of on us today to provide data / reasoning to delete it. I'd wager that some upcoming work is going to change how percpu gives out objects either through some sort of slab caching that we can revisit this more in that context.
Thanks,
Dennis
Quoted 36 lines
Hello,
Sorry for the delay, I've been a bit sick.
Quoted 25 lines · Joonwon Kang
Quoted 11 lines
Hello,
Quoted 4 lines · Joonwon Kang
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:First I'd just like to apologize. I spent an hour yesterday trying to remember why the invariant exists and the reality is this code is more clever than it needs to be.
Thanks for taking time for this and sharing more context. While you are at it, I have a fundamental question on the invariant. I had deliberation and discussion on what benefits the invariant gets to the percpu allocator by its existence. My understanding is that if we put
contig_hintbeforescan_hintwhen they are the same, it is more likely thatcontig_hintis broken by a future allocation, which leads to a linear scan after thescan_hintfor hints update, although we could save scanning uptoscan_hintwhencontig_hintis not broken. On the other hand, if we putscan_hintbeforecontig_hintinstead, it is more likely thatscan_hintis broken while keepingcontig_hint, which does not lead to the linear scan for hints update, although we could not save the scanning that could be saved in the other case.Quoted 5 lines
In other words, if
contig_hintbreaking allocations occur a lot in general with the current invariant, the performance may more suffer than without the invariant. I also think that there would be no strict reason of having the invariant.
Quoted 8 lines
I think the original premise is that percpu memory is quite expensive, 1 allocation costs
nr_cpus* sizeof(allocation). So we do our best to bin pack at the cost of faster allocations. We could always just break thecontig_hintbut then over time we could cause more fragmentation.The case that triggered this was netdev needing 8 byte objects with 16 byte alignment [1].
Thank you for sharing the points about the bin packing. Although I did not fully understand the relationship between breakage of the contig_hint and the fragmentation trend, it may be helpful to reference the case you referred to. I guess you may have missed the link for the reference [1]? Could you help to provide the link, if you intended to leave it?
Quoted 16 lines
Quoted 5 lines
So, could you clarify the necessity of the invariant? If there is no must reason, then I could post another spin-off patch to remove the invariant at all so that we could simplify the code and experiment the result. How do you think?
I can't really recall the exact reasoning for the invariant, but it was probably along the lines of wanting to not lose information if possible.
Say an earlier area becomes free that is the same size as the
contig_hintbut with better alignment, we ant to use that as thecontig_hintbut then we either have to lose thescan_hintor keep it with the invariant. Given the premise above, I believe we want to continue bin packing, I think the general idea of scanning next time around isn't the worst thing.
Quoted 6 lines
Sadly because it's already there, and has worked for quite some time, it's kind of on us today to provide data / reasoning to delete it. I'd wager that some upcoming work is going to change how percpu gives out objects either through some sort of slab caching that we can revisit this more in that context.
Understood and thanks for your detailed explanation. I will keep the invariant as-is unless I have a clear data point to reverse it. I sent the new patch set v3 recently with this in mind. Please help to review it ;)
Thanks,
Joonwon Kang
Dennis Zhou
maintainerQuoted 45 lines · Joonwon Kang
Quoted 36 lines
Hello,
Sorry for the delay, I've been a bit sick.
Quoted 25 lines · Joonwon Kang
Quoted 11 lines
Hello,
Quoted 4 lines · Joonwon Kang
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:First I'd just like to apologize. I spent an hour yesterday trying to remember why the invariant exists and the reality is this code is more clever than it needs to be.
Thanks for taking time for this and sharing more context. While you are at it, I have a fundamental question on the invariant. I had deliberation and discussion on what benefits the invariant gets to the percpu allocator by its existence. My understanding is that if we put
contig_hintbeforescan_hintwhen they are the same, it is more likely thatcontig_hintis broken by a future allocation, which leads to a linear scan after thescan_hintfor hints update, although we could save scanning uptoscan_hintwhencontig_hintis not broken. On the other hand, if we putscan_hintbeforecontig_hintinstead, it is more likely thatscan_hintis broken while keepingcontig_hint, which does not lead to the linear scan for hints update, although we could not save the scanning that could be saved in the other case.Quoted 5 lines
In other words, if
contig_hintbreaking allocations occur a lot in general with the current invariant, the performance may more suffer than without the invariant. I also think that there would be no strict reason of having the invariant.Quoted 8 lines
I think the original premise is that percpu memory is quite expensive, 1 allocation costs
nr_cpus* sizeof(allocation). So we do our best to bin pack at the cost of faster allocations. We could always just break thecontig_hintbut then over time we could cause more fragmentation.The case that triggered this was netdev needing 8 byte objects with 16 byte alignment [1].
Quoted 6 lines
Thank you for sharing the points about the bin packing. Although I did not fully understand the relationship between breakage of the
contig_hintand the fragmentation trend, it may be helpful to reference the case you referred to. I guess you may have missed the link for the reference [1]? Could you help to provide the link, if you intended to leave it?
Ah sorry that's my bad.
My intention behind the scan_hint wasn't to use the scan_hint as an earlier contig_hint, but to prevent us from scanning if we need to break the contig_hint.
[1] https://lore.kernel.org/netdev/CANn89iKb_vW+LA-91RV=zuAqbNycPFUYW54w_S=KZ3HdcWPw6Q@mail.gmail.com/
Quoted 23 lines
Quoted 16 lines
Quoted 5 lines
So, could you clarify the necessity of the invariant? If there is no must reason, then I could post another spin-off patch to remove the invariant at all so that we could simplify the code and experiment the result. How do you think?
I can't really recall the exact reasoning for the invariant, but it was probably along the lines of wanting to not lose information if possible.
Say an earlier area becomes free that is the same size as the
contig_hintbut with better alignment, we ant to use that as thecontig_hintbut then we either have to lose thescan_hintor keep it with the invariant. Given the premise above, I believe we want to continue bin packing, I think the general idea of scanning next time around isn't the worst thing.Quoted 6 lines
Sadly because it's already there, and has worked for quite some time, it's kind of on us today to provide data / reasoning to delete it. I'd wager that some upcoming work is going to change how percpu gives out objects either through some sort of slab caching that we can revisit this more in that context.
Quoted 4 lines
Understood and thanks for your detailed explanation. I will keep the invariant as-is unless I have a clear data point to reverse it. I sent the new patch set v3 recently with this in mind. Please help to review it ;)
Sorry for the delay. Provided a bit of feedback just now. Let me know if you want to discuss more about what we want v4 to look like before spending too much time.
Thanks,
Dennis