Skip to contentSkip to conversation

percpu: Fix wrong chunk hints update

PATCH Superseded Joonwon Kang 2 participants 8 messages Apr 10 – Apr 29

Subsystems (2)

v3 of 6 Superseded Latest is v6 →

lore
Share & tools
lore
#0 lore raw

PATCH v3 1/3 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.

---
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.53.0.1213.gd9a14994de-goog
#1 lore raw

PATCH v3 2/3 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.

---
v3: Initial version.

 mm/percpu.c | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)
mm/percpu.c +12 -3
index 3ecd86096641..f16533ed4a49 100644
@@ -638,6 +638,13 @@ static void pcpu_block_update(struct pcpu_block_md *block, int start, int end)
 	if (end == block->nr_bits)
 		block->right_free = contig;
 
+	if (block->contig_hint == 0) {
+		block->contig_hint = contig;
+		block->contig_hint_start = start;
+		block->scan_hint = 0;
+		return;
+	}
+
 	if (contig > block->contig_hint) {
 		/* promote the old contig_hint to be the new scan_hint */
 		if (start > block->contig_hint_start) {
@@ -845,7 +852,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 +897,7 @@ 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 +930,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.53.0.1213.gd9a14994de-goog
maintainer
#2 lore raw

Re: [PATCH v3 2/3] percpu: Do not trust hint starts when they are not set

Quoted 19 lines · Joonwon Kang

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.

---
v3: Initial version.

 mm/percpu.c | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)
mm/percpu.c +0 -0
index 3ecd86096641..f16533ed4a49 100644

mm/percpu.c static void pcpu_block_update(struct pcpu_block_md *block, int start, int end) · line 647

Quoted 10 lines
mm/percpu.c +7 -0
@@ -638,6 +638,13 @@ static void pcpu_block_update(struct pcpu_block_md *block, int start, int end)
 	if (end == block->nr_bits)
 		block->right_free = contig;
 
+	if (block->contig_hint == 0) {
+		block->contig_hint = contig;
+		block->contig_hint_start = start;
+		block->scan_hint = 0;
+		return;
+	}
+

This change isn't described in the commit log. I'd prefer to clean up the logic below than adding this additional if empty case.

Quoted 35 lines
mm/percpu.c +5 -3
 	if (contig > block->contig_hint) {
 		/* promote the old contig_hint to be the new scan_hint */
 		if (start > block->contig_hint_start) {
@@ -845,7 +852,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 +897,7 @@ 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 +930,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.53.0.1213.gd9a14994de-goog
#3 lore raw

Re: [PATCH v3 2/3] percpu: Do not trust hint starts when they are not set

Hi, I am sorry for the late response. I was occupied by other issues lately.

Quoted 23 lines · Joonwon Kang
Quoted 22 lines

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.

---
v3: Initial version.

 mm/percpu.c | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)
mm/percpu.c +0 -0
index 3ecd86096641..f16533ed4a49 100644
@@ -638,6 +638,13 @@ static void pcpu_block_update(struct pcpu_block_md *block, int start, int end)
 	if (end == block->nr_bits)
 		block->right_free = contig;
 
Quoted 11 lines

mm/percpu.c static void pcpu_block_update(struct pcpu_block_md *block, int start, int end) · line 647

Quoted 7 lines
mm/percpu.c +7 -0
+	if (block->contig_hint == 0) {
+		block->contig_hint = contig;
+		block->contig_hint_start = start;
+		block->scan_hint = 0;
+		return;
+	}
+

This change isn't described in the commit log. I'd prefer to clean up the logic below than adding this additional if empty case.

Oh, by the commit message I meant indirectly that contig_scan_hint should not be trusted inside this hint update function while it can be outside. Let me clean up the logic below instead of changing the commit message. Since the control flow will always reach the first if-block below when contig_hint is zero, it should be simple enough. Thanks!

Quoted 35 lines
Quoted 35 lines
mm/percpu.c +5 -3
 	if (contig > block->contig_hint) {
 		/* promote the old contig_hint to be the new scan_hint */
 		if (start > block->contig_hint_start) {
@@ -845,7 +852,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 +897,7 @@ 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 +930,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.53.0.1213.gd9a14994de-goog
#4 lore raw

PATCH v3 3/3 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:

- Refactor the percpu block update code to make it more visible on what to consider, e.g. when the new contig overlaps with the old contig_hint or 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.

---
v2 -> 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.

v1 -> v2: Consider cases where the new contig overlaps with the existing
contig_hint or scan_hint.

 mm/percpu.c | 130 ++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 90 insertions(+), 40 deletions(-)
mm/percpu.c +90 -40
index f16533ed4a49..d5b0b4863ffe 100644
@@ -629,7 +629,27 @@ static inline bool pcpu_region_overlap(int a, int b, int x, int y)
  */
 static void pcpu_block_update(struct pcpu_block_md *block, int start, int end)
 {
-	int contig = end - start;
+	int contig;
+	int scan_hint_cand_1 = 0;
+	int scan_hint_cand_1_start = 0;
+	int scan_hint_cand_2 = 0;
+	int scan_hint_cand_2_start = 0;
+	bool overlap_with_contig_hint = pcpu_region_overlap(start, end,
+		block->contig_hint_start,
+		block->contig_hint_start + block->contig_hint);
+	bool overlap_with_scan_hint = pcpu_region_overlap(start, end,
+		block->scan_hint_start,
+		block->scan_hint_start + block->scan_hint);
+
+	if (block->contig_hint && overlap_with_contig_hint) {
+		start = min(start, block->contig_hint_start);
+		end = max(end, block->contig_hint_start + block->contig_hint);
+	}
+	if (block->scan_hint && overlap_with_scan_hint) {
+		start = min(start, block->scan_hint_start);
+		end = max(end, block->scan_hint_start + block->scan_hint);
+	}
+	contig = end - start;
 
 	block->first_free = min(block->first_free, start);
 	if (start == 0)
@@ -646,56 +666,86 @@ 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) {
-				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 {
-			block->scan_hint = 0;
+		if (!overlap_with_contig_hint) {
+			scan_hint_cand_1 = block->contig_hint;
+			scan_hint_cand_1_start = block->contig_hint_start;
 		}
-		block->contig_hint_start = start;
+
 		block->contig_hint = contig;
+		block->contig_hint_start = start;
 	} else if (contig == block->contig_hint) {
 		if (block->contig_hint_start &&
 		    (!start ||
 		     __ffs(start) > __ffs(block->contig_hint_start))) {
-			/* start has a better alignment so use it */
+			scan_hint_cand_1 = block->contig_hint;
+			scan_hint_cand_1_start = block->contig_hint_start;
+
+			/* 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 (!overlap_with_contig_hint) {
+				scan_hint_cand_1 = contig;
+				scan_hint_cand_1_start = start;
+			}
 		}
 	} else {
 		/*
-		 * The region is smaller than the contig_hint.  So only update
-		 * the scan_hint if it is larger than or equal and farther than
-		 * the current scan_hint.
+		 * Consider only when the new contig is larger than or equal to
+		 * the old scan hint.
 		 */
-		if ((start < block->contig_hint_start &&
-		     (contig > block->scan_hint ||
-		      (contig == block->scan_hint &&
-		       start > block->scan_hint_start)))) {
-			block->scan_hint_start = start;
-			block->scan_hint = contig;
+		if (contig >= block->scan_hint) {
+			scan_hint_cand_1 = contig;
+			scan_hint_cand_1_start = start;
+		}
+	}
+
+	if (block->scan_hint &&
+	    !pcpu_region_overlap(start, end, block->scan_hint_start,
+				 block->scan_hint_start + block->scan_hint)) {
+		scan_hint_cand_2 = block->scan_hint;
+		scan_hint_cand_2_start = block->scan_hint_start;
+	}
+
+	/* Make scan_hint_cand_1 be the best candidate for the new scan hint. */
+	if ((scan_hint_cand_2 > scan_hint_cand_1) ||
+	    (scan_hint_cand_2 == scan_hint_cand_1 &&
+	     scan_hint_cand_2_start > scan_hint_cand_1_start)) {
+		int tmp_hint = scan_hint_cand_1;
+		int tmp_hint_start = scan_hint_cand_1_start;
+
+		scan_hint_cand_1 = scan_hint_cand_2;
+		scan_hint_cand_1_start = scan_hint_cand_2_start;
+		scan_hint_cand_2 = tmp_hint;
+		scan_hint_cand_2_start = tmp_hint_start;
+	}
+
+	/*
+	 * At this point, it is guaranteed that none of the scan hint
+	 * candidates overlaps with the new contig hint while they may overlap
+	 * with the old scan hint, and that the first candidate is larger in
+	 * size or, it equal, farther than the second one.
+	 */
+
+	if (block->contig_hint > scan_hint_cand_1) {
+		if (scan_hint_cand_1_start < block->contig_hint_start) {
+			block->scan_hint = scan_hint_cand_1;
+			block->scan_hint_start = scan_hint_cand_1_start;
+		} else if (scan_hint_cand_2_start < block->contig_hint_start) {
+			block->scan_hint = scan_hint_cand_2;
+			block->scan_hint_start = scan_hint_cand_2_start;
+		} else {
+			block->scan_hint = 0;
+		}
+	} else if (block->contig_hint == scan_hint_cand_1) {
+		if (scan_hint_cand_1_start > block->contig_hint_start) {
+			block->scan_hint = scan_hint_cand_1;
+			block->scan_hint_start = scan_hint_cand_1_start;
+		} else if (scan_hint_cand_2 < block->contig_hint &&
+			   scan_hint_cand_2_start < scan_hint_cand_1_start) {
+			block->scan_hint = scan_hint_cand_2;
+			block->scan_hint_start = scan_hint_cand_2_start;
+		} else {
+			block->scan_hint = 0;
 		}
 	}
 }
Signature · 1 line
2.53.0.1213.gd9a14994de-goog
maintainer
#5 lore raw

Re: [PATCH v3 3/3] percpu: Fix hint invariant breakage

Quoted 13 lines · 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.

Quoted 6 lines

This commit mainly fixes this invariant breakage and includes more:

- Refactor the percpu block update code to make it more visible on what to consider, e.g. when the new contig overlaps with the old contig_hint or scan_hint.

Could you please split this up between the fixing the scan_hint issues and then refactoring. That way this commit isn't doing too much.

Quoted 36 lines

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

---
v2 -> 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.

v1 -> v2: Consider cases where the new contig overlaps with the existing
contig_hint or scan_hint.

 mm/percpu.c | 130 ++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 90 insertions(+), 40 deletions(-)
mm/percpu.c +0 -0
index f16533ed4a49..d5b0b4863ffe 100644

mm/percpu.c static inline bool pcpu_region_overlap(int a, int b, int x, int y) · line 636

Quoted 9 lines
mm/percpu.c +5 -1
@@ -629,7 +629,27 @@ static inline bool pcpu_region_overlap(int a, int b, int x, int y)
  */
 static void pcpu_block_update(struct pcpu_block_md *block, int start, int end)
 {
-	int contig = end - start;
+	int contig;
+	int scan_hint_cand_1 = 0;
+	int scan_hint_cand_1_start = 0;
+	int scan_hint_cand_2 = 0;
+	int scan_hint_cand_2_start = 0;

I'm not really a fan of this cand_1 and cand_2. Re-reading all this code. I think I really should have introduced something like:

struct pcpu_region {
    int start;
    int size;
}

It's really easy to mix contig_hint and contig_hint_start. If you don't mind, it would be ideal if we could introduce it but it might be a non-trivial amount of refactor.

I'd say the shortest path forward would be to do just to fix the scan_hint issues.

mm/percpu.c static inline bool pcpu_region_overlap(int a, int b, int x, int y) · line 643

Quoted 7 lines
mm/percpu.c +7 -0
+	bool overlap_with_contig_hint = pcpu_region_overlap(start, end,
+		block->contig_hint_start,
+		block->contig_hint_start + block->contig_hint);
+	bool overlap_with_scan_hint = pcpu_region_overlap(start, end,
+		block->scan_hint_start,
+		block->scan_hint_start + block->scan_hint);
+

This one isn't used again so we should probably just inline it.

Quoted 126 lines
mm/percpu.c +69 -39
+	if (block->contig_hint && overlap_with_contig_hint) {
+		start = min(start, block->contig_hint_start);
+		end = max(end, block->contig_hint_start + block->contig_hint);
+	}
+	if (block->scan_hint && overlap_with_scan_hint) {
+		start = min(start, block->scan_hint_start);
+		end = max(end, block->scan_hint_start + block->scan_hint);
+	}
+	contig = end - start;
 
 	block->first_free = min(block->first_free, start);
 	if (start == 0)
@@ -646,56 +666,86 @@ 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) {
-				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 {
-			block->scan_hint = 0;
+		if (!overlap_with_contig_hint) {
+			scan_hint_cand_1 = block->contig_hint;
+			scan_hint_cand_1_start = block->contig_hint_start;
 		}
-		block->contig_hint_start = start;
+
 		block->contig_hint = contig;
+		block->contig_hint_start = start;
 	} else if (contig == block->contig_hint) {
 		if (block->contig_hint_start &&
 		    (!start ||
 		     __ffs(start) > __ffs(block->contig_hint_start))) {
-			/* start has a better alignment so use it */
+			scan_hint_cand_1 = block->contig_hint;
+			scan_hint_cand_1_start = block->contig_hint_start;
+
+			/* 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 (!overlap_with_contig_hint) {
+				scan_hint_cand_1 = contig;
+				scan_hint_cand_1_start = start;
+			}
 		}
 	} else {
 		/*
-		 * The region is smaller than the contig_hint.  So only update
-		 * the scan_hint if it is larger than or equal and farther than
-		 * the current scan_hint.
+		 * Consider only when the new contig is larger than or equal to
+		 * the old scan hint.
 		 */
-		if ((start < block->contig_hint_start &&
-		     (contig > block->scan_hint ||
-		      (contig == block->scan_hint &&
-		       start > block->scan_hint_start)))) {
-			block->scan_hint_start = start;
-			block->scan_hint = contig;
+		if (contig >= block->scan_hint) {
+			scan_hint_cand_1 = contig;
+			scan_hint_cand_1_start = start;
+		}
+	}
+
+	if (block->scan_hint &&
+	    !pcpu_region_overlap(start, end, block->scan_hint_start,
+				 block->scan_hint_start + block->scan_hint)) {
+		scan_hint_cand_2 = block->scan_hint;
+		scan_hint_cand_2_start = block->scan_hint_start;
+	}
+
+	/* Make scan_hint_cand_1 be the best candidate for the new scan hint. */
+	if ((scan_hint_cand_2 > scan_hint_cand_1) ||
+	    (scan_hint_cand_2 == scan_hint_cand_1 &&
+	     scan_hint_cand_2_start > scan_hint_cand_1_start)) {
+		int tmp_hint = scan_hint_cand_1;
+		int tmp_hint_start = scan_hint_cand_1_start;
+
+		scan_hint_cand_1 = scan_hint_cand_2;
+		scan_hint_cand_1_start = scan_hint_cand_2_start;
+		scan_hint_cand_2 = tmp_hint;
+		scan_hint_cand_2_start = tmp_hint_start;
+	}
+
+	/*
+	 * At this point, it is guaranteed that none of the scan hint
+	 * candidates overlaps with the new contig hint while they may overlap
+	 * with the old scan hint, and that the first candidate is larger in
+	 * size or, it equal, farther than the second one.
+	 */
+
+	if (block->contig_hint > scan_hint_cand_1) {
+		if (scan_hint_cand_1_start < block->contig_hint_start) {
+			block->scan_hint = scan_hint_cand_1;
+			block->scan_hint_start = scan_hint_cand_1_start;
+		} else if (scan_hint_cand_2_start < block->contig_hint_start) {
+			block->scan_hint = scan_hint_cand_2;
+			block->scan_hint_start = scan_hint_cand_2_start;
+		} else {
+			block->scan_hint = 0;
+		}
+	} else if (block->contig_hint == scan_hint_cand_1) {

mm/percpu.c static void pcpu_block_update(struct pcpu_block_md *block, int start, int end) · line 749

Quoted 10 lines
mm/percpu.c +9 -0
+		if (scan_hint_cand_1_start > block->contig_hint_start) {
+			block->scan_hint = scan_hint_cand_1;
+			block->scan_hint_start = scan_hint_cand_1_start;
+		} else if (scan_hint_cand_2 < block->contig_hint &&
+			   scan_hint_cand_2_start < scan_hint_cand_1_start) {
+			block->scan_hint = scan_hint_cand_2;
+			block->scan_hint_start = scan_hint_cand_2_start;
+		} else {
+			block->scan_hint = 0;
 		}

This seems easier to invert and do something like this:

Probably something like:

bool overlap_contig_hint = pcpu_region_overlap(new_region, scan_hint); bool overlap_scan_hint = pcpu_region_overlap(new_region, scan_hint);

if (overlap_scan_hint) {
    scan_hint = 0;
}
if (overlap_contig_hint) {
    contig_hint = new_region;
    return;
}

// Now the new_region is distinct from the contig_hint and then can do // the standard logic here.

if (new_region > contig_hint) { }
else if (new_region == contig_hint) {}
else {}

What do you think? I think makes cand_1 and cand_2 not necessary.

Quoted 5 lines
mm/percpu.c +0 -0
 	}
 }
Signature · 1 line
2.53.0.1213.gd9a14994de-goog

Thanks,
Dennis

#6 lore raw

Re: [PATCH v3 3/3] percpu: Fix hint invariant breakage

Appreciate your insightful reviews!

Quoted 16 lines · Joonwon Kang
Quoted 15 lines

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:

Quoted 8 lines
Quoted 4 lines

- Refactor the percpu block update code to make it more visible on what to consider, e.g. when the new contig overlaps with the old contig_hint or scan_hint.

Could you please split this up between the fixing the scan_hint issues and then refactoring. That way this commit isn't doing too much.

Agree that this commit is doing much of work. However, when I tried only fixing the scan_hint issues without refactoring earlier, I realized that the overlapping cases were also not being handled properly in this function. Without handling the overlapping cases, there could be other hidden scan_hint breakage issues. Handling the overlapping cases required restructuring of the function, which led to the changes to the code that were also required for resolving the scan_hint issues. Let me see if I can decently split them.

Quoted 54 lines
Quoted 36 lines

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

---
v2 -> 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.

v1 -> v2: Consider cases where the new contig overlaps with the existing
contig_hint or scan_hint.

 mm/percpu.c | 130 ++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 90 insertions(+), 40 deletions(-)
mm/percpu.c +0 -0
index f16533ed4a49..d5b0b4863ffe 100644

mm/percpu.c static inline bool pcpu_region_overlap(int a, int b, int x, int y) · line 636

Quoted 9 lines
mm/percpu.c +5 -1
@@ -629,7 +629,27 @@ static inline bool pcpu_region_overlap(int a, int b, int x, int y)
  */
 static void pcpu_block_update(struct pcpu_block_md *block, int start, int end)
 {
-	int contig = end - start;
+	int contig;
+	int scan_hint_cand_1 = 0;
+	int scan_hint_cand_1_start = 0;
+	int scan_hint_cand_2 = 0;
+	int scan_hint_cand_2_start = 0;

I'm not really a fan of this cand_1 and cand_2. Re-reading all this code. I think I really should have introduced something like:

struct pcpu_region {
    int start;
    int size;
}
Quoted 7 lines

It's really easy to mix contig_hint and contig_hint_start. If you don't mind, it would be ideal if we could introduce it but it might be a non-trivial amount of refactor.

I'd say the shortest path forward would be to do just to fix the scan_hint issues.

It will be great if we introduce the struct. I will do it as a separate patch in v4.

Quoted 10 lines

mm/percpu.c static inline bool pcpu_region_overlap(int a, int b, int x, int y) · line 643

Quoted 7 lines
mm/percpu.c +7 -0
+	bool overlap_with_contig_hint = pcpu_region_overlap(start, end,
+		block->contig_hint_start,
+		block->contig_hint_start + block->contig_hint);
+	bool overlap_with_scan_hint = pcpu_region_overlap(start, end,
+		block->scan_hint_start,
+		block->scan_hint_start + block->scan_hint);
+

This one isn't used again so we should probably just inline it.

Acknowledged.

Quoted 154 lines
Quoted 126 lines
mm/percpu.c +69 -39
+	if (block->contig_hint && overlap_with_contig_hint) {
+		start = min(start, block->contig_hint_start);
+		end = max(end, block->contig_hint_start + block->contig_hint);
+	}
+	if (block->scan_hint && overlap_with_scan_hint) {
+		start = min(start, block->scan_hint_start);
+		end = max(end, block->scan_hint_start + block->scan_hint);
+	}
+	contig = end - start;
 
 	block->first_free = min(block->first_free, start);
 	if (start == 0)
@@ -646,56 +666,86 @@ 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) {
-				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 {
-			block->scan_hint = 0;
+		if (!overlap_with_contig_hint) {
+			scan_hint_cand_1 = block->contig_hint;
+			scan_hint_cand_1_start = block->contig_hint_start;
 		}
-		block->contig_hint_start = start;
+
 		block->contig_hint = contig;
+		block->contig_hint_start = start;
 	} else if (contig == block->contig_hint) {
 		if (block->contig_hint_start &&
 		    (!start ||
 		     __ffs(start) > __ffs(block->contig_hint_start))) {
-			/* start has a better alignment so use it */
+			scan_hint_cand_1 = block->contig_hint;
+			scan_hint_cand_1_start = block->contig_hint_start;
+
+			/* 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 (!overlap_with_contig_hint) {
+				scan_hint_cand_1 = contig;
+				scan_hint_cand_1_start = start;
+			}
 		}
 	} else {
 		/*
-		 * The region is smaller than the contig_hint.  So only update
-		 * the scan_hint if it is larger than or equal and farther than
-		 * the current scan_hint.
+		 * Consider only when the new contig is larger than or equal to
+		 * the old scan hint.
 		 */
-		if ((start < block->contig_hint_start &&
-		     (contig > block->scan_hint ||
-		      (contig == block->scan_hint &&
-		       start > block->scan_hint_start)))) {
-			block->scan_hint_start = start;
-			block->scan_hint = contig;
+		if (contig >= block->scan_hint) {
+			scan_hint_cand_1 = contig;
+			scan_hint_cand_1_start = start;
+		}
+	}
+
+	if (block->scan_hint &&
+	    !pcpu_region_overlap(start, end, block->scan_hint_start,
+				 block->scan_hint_start + block->scan_hint)) {
+		scan_hint_cand_2 = block->scan_hint;
+		scan_hint_cand_2_start = block->scan_hint_start;
+	}
+
+	/* Make scan_hint_cand_1 be the best candidate for the new scan hint. */
+	if ((scan_hint_cand_2 > scan_hint_cand_1) ||
+	    (scan_hint_cand_2 == scan_hint_cand_1 &&
+	     scan_hint_cand_2_start > scan_hint_cand_1_start)) {
+		int tmp_hint = scan_hint_cand_1;
+		int tmp_hint_start = scan_hint_cand_1_start;
+
+		scan_hint_cand_1 = scan_hint_cand_2;
+		scan_hint_cand_1_start = scan_hint_cand_2_start;
+		scan_hint_cand_2 = tmp_hint;
+		scan_hint_cand_2_start = tmp_hint_start;
+	}
+
+	/*
+	 * At this point, it is guaranteed that none of the scan hint
+	 * candidates overlaps with the new contig hint while they may overlap
+	 * with the old scan hint, and that the first candidate is larger in
+	 * size or, it equal, farther than the second one.
+	 */
+
+	if (block->contig_hint > scan_hint_cand_1) {
+		if (scan_hint_cand_1_start < block->contig_hint_start) {
+			block->scan_hint = scan_hint_cand_1;
+			block->scan_hint_start = scan_hint_cand_1_start;
+		} else if (scan_hint_cand_2_start < block->contig_hint_start) {
+			block->scan_hint = scan_hint_cand_2;
+			block->scan_hint_start = scan_hint_cand_2_start;
+		} else {
+			block->scan_hint = 0;
+		}
+	} else if (block->contig_hint == scan_hint_cand_1) {

mm/percpu.c static void pcpu_block_update(struct pcpu_block_md *block, int start, int end) · line 749

Quoted 10 lines
mm/percpu.c +9 -0
+		if (scan_hint_cand_1_start > block->contig_hint_start) {
+			block->scan_hint = scan_hint_cand_1;
+			block->scan_hint_start = scan_hint_cand_1_start;
+		} else if (scan_hint_cand_2 < block->contig_hint &&
+			   scan_hint_cand_2_start < scan_hint_cand_1_start) {
+			block->scan_hint = scan_hint_cand_2;
+			block->scan_hint_start = scan_hint_cand_2_start;
+		} else {
+			block->scan_hint = 0;
 		}

This seems easier to invert and do something like this:

Probably something like:

bool overlap_contig_hint = pcpu_region_overlap(new_region, scan_hint); bool overlap_scan_hint = pcpu_region_overlap(new_region, scan_hint);

if (overlap_scan_hint) {
    scan_hint = 0;
}
if (overlap_contig_hint) {
    contig_hint = new_region;
    return;
}
Quoted 9 lines

// Now the new_region is distinct from the contig_hint and then can do // the standard logic here.

if (new_region > contig_hint) { }
else if (new_region == contig_hint) {}
else {}

What do you think? I think makes cand_1 and cand_2 not necessary.

Hmm, with this, if contig_hint == scan_hint && new_region overlaps only with contig_hint && the entire overlapped region > contig_hint, then we will have a wrong scan_hint, i.e. new contig_hint_start < scan_hint_start even though new contig_hint > scan_hint.

But, I can see your point here. Let me see if I can get rid of cand_1 and cand_2.

Quoted 5 lines
Quoted 5 lines
mm/percpu.c +0 -0
 	}
 }
Signature · 1 line
2.53.0.1213.gd9a14994de-goog

Thanks,
Joonwon Kang

maintainer Reviewed-by on v3 1/3
#7 lore raw
In reply to Joonwon Kang

Hello,

Quoted 17 lines · Joonwon Kang

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.

---
v3: Initial version.

 mm/percpu.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
mm/percpu.c +0 -0
index 81462ce5866e..3ecd86096641 100644

mm/percpu.c static void pcpu_block_update_hint_free(struct pcpu_chunk *chunk, int bit_off, · line 1058

Quoted 6 lines
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));
 }

This needs a fixes tag for:

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

Thanks,
Dennis

Quoted 5 lines
mm/percpu.c +0 -0
 /**
Signature · 1 line
2.53.0.1213.gd9a14994de-goog