[PATCH] percpu: Fix hint invariant breakage

[Joonwon Kang <joonwonkang@google.com>]

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.

Signed-off-by: Joonwon Kang <joonwonkang@google.com>
---
 mm/percpu.c | 60 ++++++++++++++++++++++++++++++++++-------------------
 1 file changed, 39 insertions(+), 21 deletions(-)

diff --git a/mm/percpu.c b/mm/percpu.c
index 81462ce5866e..a0e4f8acb7c2 100644
--- a/mm/percpu.c
+++ b/mm/percpu.c
@@ -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 {
 		/*
-- 
2.53.0.1018.g2bb0e51243-goog