aboutsummaryrefslogtreecommitdiffstats
path: root/mm
diff options
authorJoonwon Kang <joonwonkang@google.com>2026-05-13 08:51:16 +0000
committerAndrew Morton <akpm@linux-foundation.org>2026-05-28 21:32:00 -0700
commit6da68942eaff5a31e7fb78140d1f9e37124e707a (patch)
tree36e099d2f9e16fe5652bd8afd4fa16895bc9d638 /mm
parentf1b39de04bf225ddbad9cb64de50a141d134d0d5 (diff)
downloadlinux-next-history-6da68942eaff5a31e7fb78140d1f9e37124e707a.tar.gz
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 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>
Diffstat (limited to 'mm')
-rw-r--r--mm/percpu.c118
1 files changed, 93 insertions, 25 deletions
diff --git a/mm/percpu.c b/mm/percpu.c
index 35e058f56a6fd..71a85d7245c7b 100644
--- a/mm/percpu.c
+++ b/mm/percpu.c
@@ -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,40 @@ 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) {
+ 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 {
/*
generated by cgit 1.3-korg (git 2.53.0) at 2026-06-01 04:05:05 +0000