* [to-be-updated] percpu-fix-hint-invariant-breakage.patch removed from -mm tree
@ 2026-05-18 17:54 Andrew Morton
0 siblings, 0 replies; 2+ messages in thread
From: Andrew Morton @ 2026-05-18 17:54 UTC (permalink / raw)
To: mm-commits, joonwonkang, akpm
The quilt patch titled
Subject: percpu: fix hint invariant breakage
has been removed from the -mm tree. Its filename was
percpu-fix-hint-invariant-breakage.patch
This patch was dropped because an updated version will be issued
------------------------------------------------------
From: Joonwon Kang <joonwonkang@google.com>
Subject: percpu: fix hint invariant breakage
Date: Sun, 10 May 2026 07:21:49 +0000
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:
- 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.
Link: https://lore.kernel.org/20260510072149.1279887-4-joonwonkang@google.com
Signed-off-by: Joonwon Kang <joonwonkang@google.com>
Cc: Christoph Lameter <cl@linux.com>
Cc: Dennis Zhou <dennis@kernel.org>
Cc: Tejun Heo <tj@kernel.org>
Cc: <dodam@google.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---
mm/percpu.c | 119 +++++++++++++++++++++++++++++++++++++++-----------
1 file changed, 94 insertions(+), 25 deletions(-)
--- a/mm/percpu.c~percpu-fix-hint-invariant-breakage
+++ a/mm/percpu.c
@@ -616,6 +616,20 @@ static inline bool pcpu_region_overlap(s
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(s
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 pcp
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 pcp
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 {
/*
_
Patches currently in -mm which might be from joonwonkang@google.com are
a.patch
^ permalink raw reply [flat|nested] 2+ messages in thread
* [to-be-updated] percpu-fix-hint-invariant-breakage.patch removed from -mm tree
@ 2026-05-29 4:51 Andrew Morton
0 siblings, 0 replies; 2+ messages in thread
From: Andrew Morton @ 2026-05-29 4:51 UTC (permalink / raw)
To: mm-commits, tj, dennis, joonwonkang, akpm
The quilt patch titled
Subject: percpu: fix hint invariant breakage
has been removed from the -mm tree. Its filename was
percpu-fix-hint-invariant-breakage.patch
This patch was dropped because an updated version will be issued
------------------------------------------------------
From: Joonwon Kang <joonwonkang@google.com>
Subject: percpu: fix hint invariant breakage
Date: Wed, 13 May 2026 08:51:16 +0000
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:
- 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.
Link: https://lore.kernel.org/20260513085117.1024175-4-joonwonkang@google.com
Signed-off-by: Joonwon Kang <joonwonkang@google.com>
Cc: Dennis Zhou <dennis@kernel.org>
Cc: Tejun Heo <tj@kernel.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---
mm/percpu.c | 118 +++++++++++++++++++++++++++++++++++++++-----------
1 file changed, 93 insertions(+), 25 deletions(-)
--- a/mm/percpu.c~percpu-fix-hint-invariant-breakage
+++ a/mm/percpu.c
@@ -616,6 +616,20 @@ static inline bool pcpu_region_overlap(s
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(s
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 pcp
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,40 @@ static void pcpu_block_update(struct pcp
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) {
+ block->scan_hint = free;
+ } else if (block->scan_hint.size &&
+ free.start < block->scan_hint.start) {
+ /*
+ * old scan_hint.size < new contig size
+ * == old contig_hint.size. But, the new
+ * contig is before the old scan_hint
+ * so invalidate the scan_hint to
+ * protect the contig_hint.
+ */
+ block->scan_hint.size = 0;
+ }
+ } else if (free.start > block->scan_hint.start) {
+ block->scan_hint = free;
+ }
}
} else {
/*
_
Patches currently in -mm which might be from joonwonkang@google.com are
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2026-05-29 4:51 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-05-29 4:51 [to-be-updated] percpu-fix-hint-invariant-breakage.patch removed from -mm tree Andrew Morton
-- strict thread matches above, loose matches on Subject: below --
2026-05-18 17:54 Andrew Morton
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.