Skip to contentSkip to conversation

percpu: Fix wrong chunk hints update

PATCH Superseded Joonwon Kang 2 participants 6 messages May 6 – May 10

Subsystems (2)

v4 of 6 Superseded Latest is v6 →

lore
Share & tools
lore
#0 lore raw

PATCH v4 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.

Fixes 92c14cab4326 ("percpu: convert chunk hints to be based on pcpu_block_md")

---
v4: Add Fixes tag.
v3: Initial version.

 mm/percpu.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
mm/percpu.c +1 -1
index 81462ce5866e..3ecd86096641 100644
@@ -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.545.g6539524ca2-goog
#1 lore raw

PATCH v4 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.

---
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
index 3ecd86096641..0f6dd5260f56 100644
@@ -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.545.g6539524ca2-goog
#2 lore raw

PATCH v4 3/4 percpu: Introduce struct pcpu_region

In reply to Joonwon Kang

The new struct is introduced to prevent mis-use of hint start and size and improve readability.

---
v4: Initial version.

 mm/percpu-internal.h |  24 ++--
 mm/percpu.c          | 279 +++++++++++++++++++++----------------------
 2 files changed, 148 insertions(+), 155 deletions(-)
mm/percpu-internal.h +15 -9
index 4b3d6ec43703..dd95ec2c243a 100644
@@ -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.c +133 -146

486 lines not on this page · raw message

Signature · 1 line
2.54.0.545.g6539524ca2-goog
#3 lore raw

PATCH v4 4/4 percpu: Fix hint invariant breakage

In reply to 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:

- Handle the cases where the new contig overlaps with contig_hint or with scan_hint. Merge the new contig with the hints in that case and treat it as a whole free 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.

---
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
index 0f5648669cac..549448754afe 100644
@@ -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.545.g6539524ca2-goog
maintainer
#4 lore raw
In reply to Joonwon Kang
Quoted 4 lines · On Wed, 6 May 2026 14:20:56 +0000 Joonwon Kang <[email protected]> wrote:

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.

AI review:

	https://sashiko.dev/#/patchset/[email protected]

The first comment seems valid:

CC mm/percpu-stats.o
mm/percpu-stats.c: In function 'chunk_map_stats':
mm/percpu-stats.c:125:9: error: aggregate value used where an integer was expected

  125 |         P("contig_bytes", chunk_md->contig_hint * PCPU_MIN_ALLOC_SIZE);
      |         ^
#5 lore raw
Quoted 10 lines · On Wed, 6 May 2026 14:20:56 +0000 Joonwon Kang <[email protected]> wrote:
Quoted 5 lines

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.

AI review:

	https://sashiko.dev/#/patchset/[email protected]
Quoted 7 lines

The first comment seems valid:

CC mm/percpu-stats.o
mm/percpu-stats.c: In function 'chunk_map_stats':
mm/percpu-stats.c:125:9: error: aggregate value used where an integer was expected

  125 |         P("contig_bytes", chunk_md->contig_hint * PCPU_MIN_ALLOC_SIZE);
      |         ^

Indeed, thanks for catching this out. I missed running the allyesconfig build. Will send a new version.

The fact that the patches are now being reviewed by AI is interesting! Is there any website or link that I can access to see how AI is reviewing my patches every time I send a patch? or is it something that is not very public yet?

Thanks,
Joonwon Kang