Skip to contentSkip to conversation

selftests/mm: Simplify byte pattern checking in mremap_test

PATCH Superseded Dev Jain 5 participants 11 messages Apr 10 – Apr 14

Subsystems (3)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Dev Jain

author
#0 lore raw

PATCH 1/1 selftests/mm: Simplify byte pattern checking in mremap_test

The original version of mremap_test (7df666253f26: "kselftests: vm: add mremap tests") validated remapped contents byte-by-byte and printed a mismatch index in case the bytes streams are not equal. That made validation expensive in both cases: for "no mismatch" (the common case when mremap is not buggy), it still walked all bytes in C; for "mismatch", it broke out of the loop after printing the mismatch index.

Later, my commit 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution time from minutes to seconds using chunkwise memcmp") tried to optimize both cases by using chunk-wise memcmp() and only scanning bytes within a range which has been determined by memcmp as mismatching.

But get_sqrt() in that commit is buggy: high = mid - 1 is applied unconditionally. This makes the speed of checking the mismatch index suboptimal.

The mismatch index does not provide useful debugging value here: if validation fails, we know mremap behavior is wrong, and the specific byte offset does not make root-causing easier.

So instead of fixing get_sqrt(), bite the bullet, drop mismatch index scanning and just compare the two byte streams with memcmp().

---
Sorry for sending two patchsets the same day - the problem was made known to me today, and I couldn't help myself but fix it immediately, imagine my embarrassment when I found out that I made a typo in the binary search code which I had been writing consistently throughout college :)

Applies on mm-unstable.

 tools/testing/selftests/mm/mremap_test.c | 109 +++--------------------
 1 file changed, 10 insertions(+), 99 deletions(-)
tools/testing/selftests/mm/mremap_test.c +10 -99
index 308576437228c..131d9d6db8679 100644
@@ -76,27 +76,6 @@ enum {
 	.expect_failure = should_fail				\
 }
 
-/* compute square root using binary search */
-static unsigned long get_sqrt(unsigned long val)
-{
-	unsigned long low = 1;
-
-	/* assuming rand_size is less than 1TB */
-	unsigned long high = (1UL << 20);
-
-	while (low <= high) {
-		unsigned long mid = low + (high - low) / 2;
-		unsigned long temp = mid * mid;
-
-		if (temp == val)
-			return mid;
-		if (temp < val)
-			low = mid + 1;
-		high = mid - 1;
-	}
-	return low;
-}
-
 /*
  * Returns false if the requested remap region overlaps with an
  * existing mapping (e.g text, stack) else returns true.
@@ -995,11 +974,9 @@ static long long remap_region(struct config c, unsigned int threshold_mb,
 			      char *rand_addr)
 {
 	void *addr, *tmp_addr, *src_addr, *dest_addr, *dest_preamble_addr = NULL;
-	unsigned long long t, d;
 	struct timespec t_start = {0, 0}, t_end = {0, 0};
 	long long  start_ns, end_ns, align_mask, ret, offset;
 	unsigned long long threshold;
-	unsigned long num_chunks;
 
 	if (threshold_mb == VALIDATION_NO_THRESHOLD)
 		threshold = c.region_size;
@@ -1068,87 +1045,21 @@ static long long remap_region(struct config c, unsigned int threshold_mb,
 		goto clean_up_dest_preamble;
 	}
 
-	/*
-	 * Verify byte pattern after remapping. Employ an algorithm with a
-	 * square root time complexity in threshold: divide the range into
-	 * chunks, if memcmp() returns non-zero, only then perform an
-	 * iteration in that chunk to find the mismatch index.
-	 */
-	num_chunks = get_sqrt(threshold);
-	for (unsigned long i = 0; i < num_chunks; ++i) {
-		size_t chunk_size = threshold / num_chunks;
-		unsigned long shift = i * chunk_size;
-
-		if (!memcmp(dest_addr + shift, rand_addr + shift, chunk_size))
-			continue;
-
-		/* brute force iteration only over mismatch segment */
-		for (t = shift; t < shift + chunk_size; ++t) {
-			if (((char *) dest_addr)[t] != rand_addr[t]) {
-				ksft_print_msg("Data after remap doesn't match at offset %llu\n",
-						t);
-				ksft_print_msg("Expected: %#x\t Got: %#x\n", rand_addr[t] & 0xff,
-						((char *) dest_addr)[t] & 0xff);
-				ret = -1;
-				goto clean_up_dest;
-			}
-		}
-	}
-
-	/*
-	 * if threshold is not divisible by num_chunks, then check the
-	 * last chunk
-	 */
-	for (t = num_chunks * (threshold / num_chunks); t < threshold; ++t) {
-		if (((char *) dest_addr)[t] != rand_addr[t]) {
-			ksft_print_msg("Data after remap doesn't match at offset %llu\n",
-					t);
-			ksft_print_msg("Expected: %#x\t Got: %#x\n", rand_addr[t] & 0xff,
-					((char *) dest_addr)[t] & 0xff);
-			ret = -1;
-			goto clean_up_dest;
-		}
+	/* Verify byte pattern after remapping */
+	if (memcmp(dest_addr, rand_addr, threshold)) {
+		ksft_print_msg("Data after remap doesn't match\n");
+		ret = -1;
+		goto clean_up_dest;
 	}
 
 	/* Verify the dest preamble byte pattern after remapping */
-	if (!c.dest_preamble_size)
-		goto no_preamble;
-
-	num_chunks = get_sqrt(c.dest_preamble_size);
-
-	for (unsigned long i = 0; i < num_chunks; ++i) {
-		size_t chunk_size = c.dest_preamble_size / num_chunks;
-		unsigned long shift = i * chunk_size;
-
-		if (!memcmp(dest_preamble_addr + shift, rand_addr + shift,
-			    chunk_size))
-			continue;
-
-		/* brute force iteration only over mismatched segment */
-		for (d = shift; d < shift + chunk_size; ++d) {
-			if (((char *) dest_preamble_addr)[d] != rand_addr[d]) {
-				ksft_print_msg("Preamble data after remap doesn't match at offset %llu\n",
-						d);
-				ksft_print_msg("Expected: %#x\t Got: %#x\n", rand_addr[d] & 0xff,
-						((char *) dest_preamble_addr)[d] & 0xff);
-				ret = -1;
-				goto clean_up_dest;
-			}
-		}
-	}
-
-	for (d = num_chunks * (c.dest_preamble_size / num_chunks); d < c.dest_preamble_size; ++d) {
-		if (((char *) dest_preamble_addr)[d] != rand_addr[d]) {
-			ksft_print_msg("Preamble data after remap doesn't match at offset %llu\n",
-					d);
-			ksft_print_msg("Expected: %#x\t Got: %#x\n", rand_addr[d] & 0xff,
-					((char *) dest_preamble_addr)[d] & 0xff);
-			ret = -1;
-			goto clean_up_dest;
-		}
+	if (c.dest_preamble_size &&
+	    memcmp(dest_preamble_addr, rand_addr, c.dest_preamble_size)) {
+		ksft_print_msg("Preamble data after remap doesn't match\n");
+		ret = -1;
+		goto clean_up_dest;
 	}
 
-no_preamble:
 	start_ns = t_start.tv_sec * NS_PER_SEC + t_start.tv_nsec;
 	end_ns = t_end.tv_sec * NS_PER_SEC + t_end.tv_nsec;
 	ret = end_ns - start_ns;
Signature · 1 line
2.34.1
#1 lore raw
Quoted 7 lines · Dev Jain

The original version of mremap_test (7df666253f26: "kselftests: vm: add mremap tests") validated remapped contents byte-by-byte and printed a mismatch index in case the bytes streams are not equal. That made validation expensive in both cases: for "no mismatch" (the common case when mremap is not buggy), it still walked all bytes in C; for "mismatch", it broke out of the loop after printing the mismatch index.

Quoted 8 lines

Later, my commit 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution time from minutes to seconds using chunkwise memcmp") tried to optimize both cases by using chunk-wise memcmp() and only scanning bytes within a range which has been determined by memcmp as mismatching.

But get_sqrt() in that commit is buggy: high = mid - 1 is applied unconditionally. This makes the speed of checking the mismatch index suboptimal.

So is that the only problem with 7033c6cc9620: the speed?

Quoted 4 lines

The mismatch index does not provide useful debugging value here: if validation fails, we know mremap behavior is wrong, and the specific byte offset does not make root-causing easier.

Fully agreed.

Quoted 3 lines

So instead of fixing get_sqrt(), bite the bullet, drop mismatch index scanning and just compare the two byte streams with memcmp().

How does this affect the execution time of the test?

Quoted 3 lines
Fixes 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution time

from minutes to seconds using chunkwise memcmp")

?

Quoted 5 lines

---
Sorry for sending two patchsets the same day - the problem was made known to me today, and I couldn't help myself but fix it immediately, imagine my embarrassment when I found out that I made a typo in the binary search code which I had been writing consistently throughout college :)

:)

Quoted 5 lines

Applies on mm-unstable.

 tools/testing/selftests/mm/mremap_test.c | 109 +++--------------------
 1 file changed, 10 insertions(+), 99 deletions(-)

I mean, it certainly looks like a nice cleanup.

Signature · 3 lines
Cheers,

David
author
#2 lore raw
Quoted 13 lines · David Hildenbrand (Arm)
Quoted 12 lines · Dev Jain

The original version of mremap_test (7df666253f26: "kselftests: vm: add mremap tests") validated remapped contents byte-by-byte and printed a mismatch index in case the bytes streams are not equal. That made validation expensive in both cases: for "no mismatch" (the common case when mremap is not buggy), it still walked all bytes in C; for "mismatch", it broke out of the loop after printing the mismatch index.

Later, my commit 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution time from minutes to seconds using chunkwise memcmp") tried to optimize both cases by using chunk-wise memcmp() and only scanning bytes within a range which has been determined by memcmp as mismatching.

Quoted 5 lines
Quoted 3 lines

But get_sqrt() in that commit is buggy: high = mid - 1 is applied unconditionally. This makes the speed of checking the mismatch index suboptimal.

So is that the only problem with 7033c6cc9620: the speed?

Yes.

I'll explain the algorithm in 7033c6cc9620.

The problem statement is: given two buffers of equal length n, find the first mismatch index.

Algorithm: Divide the buffers into sqrt(n) chunks. Do a memcmp() over each chunk. If all of them succeed, the buffers are equal, giving the result in O(sqrt(n)) * t, where t = time taken by memcmp().

Otherwise, worst case is that we find the mismatch in the last chunk. Now brute-force iterate this chunk to find the mismatch. Since chunk size is sqrt(n), complexity is again
sqrt(n) * t + sqrt(n) = O(sqrt(n)) * t.

So if get_sqrt() computes a wrong square root, we lose this time complexity.

Maybe there is an optimal value of x = #number of chunks of the buffer, which may not be sqrt(n).

But given the information we have, a CS course on algorithms will say this is one of the optimal ways to do it.

Quoted 6 lines
Quoted 5 lines

The mismatch index does not provide useful debugging value here: if validation fails, we know mremap behavior is wrong, and the specific byte offset does not make root-causing easier.

Quoted 7 lines

Fully agreed.

Quoted 3 lines

So instead of fixing get_sqrt(), bite the bullet, drop mismatch index scanning and just compare the two byte streams with memcmp().

How does this affect the execution time of the test?

I just checked with ./mremap_test -t 0, the variance is very high on my system.

In the common case of the test passing:

before patch, there are multiple sub-length calls to memcmp. after patch, there is a single full-length call to memcmp.

So the time should reduce but may not be very distinguishable.

Quoted 9 lines
Quoted 4 lines
Fixes 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution time

from minutes to seconds using chunkwise memcmp")

?

Not needed. 7033c6cc9620 does not create any incorrectness in the checking of mismatch index.

Quoted 17 lines
Quoted 6 lines

---
Sorry for sending two patchsets the same day - the problem was made known to me today, and I couldn't help myself but fix it immediately, imagine my embarrassment when I found out that I made a typo in the binary search code which I had been writing consistently throughout college :)

:)

Quoted 5 lines

Applies on mm-unstable.

 tools/testing/selftests/mm/mremap_test.c | 109 +++--------------------
 1 file changed, 10 insertions(+), 99 deletions(-)

I mean, it certainly looks like a nice cleanup.

#3 lore raw
Quoted 64 lines · Dev Jain
Quoted 13 lines · David Hildenbrand (Arm)
Quoted 12 lines · Dev Jain

The original version of mremap_test (7df666253f26: "kselftests: vm: add mremap tests") validated remapped contents byte-by-byte and printed a mismatch index in case the bytes streams are not equal. That made validation expensive in both cases: for "no mismatch" (the common case when mremap is not buggy), it still walked all bytes in C; for "mismatch", it broke out of the loop after printing the mismatch index.

Later, my commit 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution time from minutes to seconds using chunkwise memcmp") tried to optimize both cases by using chunk-wise memcmp() and only scanning bytes within a range which has been determined by memcmp as mismatching.

Quoted 5 lines
Quoted 3 lines

But get_sqrt() in that commit is buggy: high = mid - 1 is applied unconditionally. This makes the speed of checking the mismatch index suboptimal.

So is that the only problem with 7033c6cc9620: the speed?

Yes.

I'll explain the algorithm in 7033c6cc9620.

The problem statement is: given two buffers of equal length n, find the first mismatch index.

Algorithm: Divide the buffers into sqrt(n) chunks. Do a memcmp() over each chunk. If all of them succeed, the buffers are equal, giving the result in O(sqrt(n)) * t, where t = time taken by memcmp().

Otherwise, worst case is that we find the mismatch in the last chunk. Now brute-force iterate this chunk to find the mismatch. Since chunk size is sqrt(n), complexity is again
sqrt(n) * t + sqrt(n) = O(sqrt(n)) * t.

So if get_sqrt() computes a wrong square root, we lose this time complexity.

Maybe there is an optimal value of x = #number of chunks of the buffer, which may not be sqrt(n).

But given the information we have, a CS course on algorithms will say this is one of the optimal ways to do it.

Quoted 6 lines
Quoted 5 lines

The mismatch index does not provide useful debugging value here: if validation fails, we know mremap behavior is wrong, and the specific byte offset does not make root-causing easier.

Quoted 7 lines

Fully agreed.

Quoted 3 lines

So instead of fixing get_sqrt(), bite the bullet, drop mismatch index scanning and just compare the two byte streams with memcmp().

How does this affect the execution time of the test?

I just checked with ./mremap_test -t 0, the variance is very high on my system.

Quoted 6 lines

In the common case of the test passing:

before patch, there are multiple sub-length calls to memcmp. after patch, there is a single full-length call to memcmp.

So the time should reduce but may not be very distinguishable.

My intuition would be the opposite; if you hafve a 4096 byte buffer, I would have thought that a single memcmp would be significantly faster than sqrt(4096) = 64 calls, each over 64 bytes.

If you want to keep the common case fast, but also find the first differing offset on failure, I expect you can exploit the fact that the buffers are all page aligned. With some prompting, Codex gave me this:

---8<---
static size_t first_mismatch_offset(const void *buf1, const void *buf2,
size_t len)

{
	const uint64_t *ptr1 = buf1;
	const uint64_t *ptr2 = buf2;
	size_t word;
	size_t words = len / sizeof(*ptr1);

	assert(!((uintptr_t)buf1 & (sizeof(*ptr1) - 1)));
	assert(!((uintptr_t)buf2 & (sizeof(*ptr2) - 1)));
	assert(!(len & (sizeof(*ptr1) - 1)));

	if (!memcmp(buf1, buf2, len))
		return len;

	for (word = 0; word < words; word++) {
		if (ptr1[word] != ptr2[word]) {
			const unsigned char *bytes1 =
				(const unsigned char *)&ptr1[word];
			const unsigned char *bytes2 =
				(const unsigned char *)&ptr2[word];
			size_t i;

			for (i = 0; i < sizeof(*ptr1); i++) {
				if (bytes1[i] != bytes2[i])
					return word * sizeof(*ptr1) + i;
			}
		}
	}

	return len;
}

---8<---

I've not benchmarked it though...

Thanks,
Ryan

Quoted 32 lines
Quoted 10 lines
Quoted 5 lines
Fixes 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution time

from minutes to seconds using chunkwise memcmp")

?

Not needed. 7033c6cc9620 does not create any incorrectness in the checking of mismatch index.

Quoted 17 lines
Quoted 6 lines

---
Sorry for sending two patchsets the same day - the problem was made known to me today, and I couldn't help myself but fix it immediately, imagine my embarrassment when I found out that I made a typo in the binary search code which I had been writing consistently throughout college :)

:)

Quoted 5 lines

Applies on mm-unstable.

 tools/testing/selftests/mm/mremap_test.c | 109 +++--------------------
 1 file changed, 10 insertions(+), 99 deletions(-)

I mean, it certainly looks like a nice cleanup.

#5 lore raw
In reply to Dev Jain
Quoted 33 lines · Dev Jain
Quoted 13 lines · David Hildenbrand (Arm)
Quoted 12 lines · Dev Jain

The original version of mremap_test (7df666253f26: "kselftests: vm: add mremap tests") validated remapped contents byte-by-byte and printed a mismatch index in case the bytes streams are not equal. That made validation expensive in both cases: for "no mismatch" (the common case when mremap is not buggy), it still walked all bytes in C; for "mismatch", it broke out of the loop after printing the mismatch index.

Later, my commit 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution time from minutes to seconds using chunkwise memcmp") tried to optimize both cases by using chunk-wise memcmp() and only scanning bytes within a range which has been determined by memcmp as mismatching.

Quoted 5 lines
Quoted 3 lines

But get_sqrt() in that commit is buggy: high = mid - 1 is applied unconditionally. This makes the speed of checking the mismatch index suboptimal.

So is that the only problem with 7033c6cc9620: the speed?

Yes.

I'll explain the algorithm in 7033c6cc9620.

The problem statement is: given two buffers of equal length n, find the first mismatch index.

Algorithm: Divide the buffers into sqrt(n) chunks. Do a memcmp() over each chunk. If all of them succeed, the buffers are equal, giving the result in O(sqrt(n)) * t, where t = time taken by memcmp().

Quoted 7 lines

Otherwise, worst case is that we find the mismatch in the last chunk. Now brute-force iterate this chunk to find the mismatch. Since chunk size is sqrt(n), complexity is again
sqrt(n) * t + sqrt(n) = O(sqrt(n)) * t.

So if get_sqrt() computes a wrong square root, we lose this time complexity.

Ah, thanks for clarifying.

Quoted 24 lines

Maybe there is an optimal value of x = #number of chunks of the buffer, which may not be sqrt(n).

But given the information we have, a CS course on algorithms will say this is one of the optimal ways to do it.

Quoted 6 lines
Quoted 5 lines

The mismatch index does not provide useful debugging value here: if validation fails, we know mremap behavior is wrong, and the specific byte offset does not make root-causing easier.

Quoted 7 lines

Fully agreed.

Quoted 3 lines

So instead of fixing get_sqrt(), bite the bullet, drop mismatch index scanning and just compare the two byte streams with memcmp().

How does this affect the execution time of the test?

I just checked with ./mremap_test -t 0, the variance is very high on my system.

Quoted 6 lines

In the common case of the test passing:

before patch, there are multiple sub-length calls to memcmp. after patch, there is a single full-length call to memcmp.

So the time should reduce but may not be very distinguishable.

Okay, so doesn't matter. I agree that we should simplify all that.

The exact index is irrelevant. Whoever wants to debug the test failure could modify the test to find that out. It's one of the tests we don't really expect to fail (often).

Quoted 6 lines
Quoted 6 lines
Quoted 5 lines
Quoted 7 lines
Quoted 4 lines
Fixes 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution time

from minutes to seconds using chunkwise memcmp")

?

Not needed. 7033c6cc9620 does not create any incorrectness in the checking of mismatch index.

Yes, agreed.

I would suggest to rewrite/simplify/clarify the patch description, not talking about "buggy" etc, focusing on the simplification.

"
The original version of mremap_test (7df666253f26: "kselftests: vm: add mremap tests") validated remapped contents byte-by-byte and printed a mismatch index in case the bytes streams didn't match. That was rather inefficient, especially also if the test passed.

Later, commit 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution time from minutes to seconds using chunkwise memcmp") used memcmp() on bigger chunks, to fallback to byte-wise scanning to detect the problematic index only if it discovered a problem.

However, the implementation is overly complicated (e.g., get_sqrt() is currently not optimal) and we don't really have to report the exact
index: whoever debugs the failing test can figure that out.

Let's simplify by just comparing both byte streams with memcmp() and not detecting the exact failed index.
"

Signature · 3 lines
Cheers,

David
#6 lore raw
Quoted 112 lines · On Tue, 14 Apr 2026 10:01:57 +0200 "David Hildenbrand (Arm)"…
Quoted 33 lines · Dev Jain
Quoted 13 lines · David Hildenbrand (Arm)
Quoted 12 lines · Dev Jain

The original version of mremap_test (7df666253f26: "kselftests: vm: add mremap tests") validated remapped contents byte-by-byte and printed a mismatch index in case the bytes streams are not equal. That made validation expensive in both cases: for "no mismatch" (the common case when mremap is not buggy), it still walked all bytes in C; for "mismatch", it broke out of the loop after printing the mismatch index.

Later, my commit 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution time from minutes to seconds using chunkwise memcmp") tried to optimize both cases by using chunk-wise memcmp() and only scanning bytes within a range which has been determined by memcmp as mismatching.

Quoted 5 lines
Quoted 3 lines

But get_sqrt() in that commit is buggy: high = mid - 1 is applied unconditionally. This makes the speed of checking the mismatch index suboptimal.

So is that the only problem with 7033c6cc9620: the speed?

Yes.

I'll explain the algorithm in 7033c6cc9620.

The problem statement is: given two buffers of equal length n, find the first mismatch index.

Algorithm: Divide the buffers into sqrt(n) chunks. Do a memcmp() over each chunk. If all of them succeed, the buffers are equal, giving the result in O(sqrt(n)) * t, where t = time taken by memcmp().

Quoted 7 lines

Otherwise, worst case is that we find the mismatch in the last chunk. Now brute-force iterate this chunk to find the mismatch. Since chunk size is sqrt(n), complexity is again
sqrt(n) * t + sqrt(n) = O(sqrt(n)) * t.

So if get_sqrt() computes a wrong square root, we lose this time complexity.

Ah, thanks for clarifying.

Quoted 24 lines

Maybe there is an optimal value of x = #number of chunks of the buffer, which may not be sqrt(n).

But given the information we have, a CS course on algorithms will say this is one of the optimal ways to do it.

Quoted 6 lines
Quoted 5 lines

The mismatch index does not provide useful debugging value here: if validation fails, we know mremap behavior is wrong, and the specific byte offset does not make root-causing easier.

Quoted 7 lines

Fully agreed.

Quoted 3 lines

So instead of fixing get_sqrt(), bite the bullet, drop mismatch index scanning and just compare the two byte streams with memcmp().

How does this affect the execution time of the test?

I just checked with ./mremap_test -t 0, the variance is very high on my system.

Quoted 6 lines

In the common case of the test passing:

before patch, there are multiple sub-length calls to memcmp. after patch, there is a single full-length call to memcmp.

So the time should reduce but may not be very distinguishable.

Okay, so doesn't matter. I agree that we should simplify all that.

The exact index is irrelevant. Whoever wants to debug the test failure could modify the test to find that out. It's one of the tests we don't really expect to fail (often).

Quoted 6 lines
Quoted 6 lines
Quoted 5 lines
Quoted 7 lines
Quoted 4 lines
Fixes 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution time

from minutes to seconds using chunkwise memcmp")

?

Not needed. 7033c6cc9620 does not create any incorrectness in the checking of mismatch index.

Yes, agreed.

I would suggest to rewrite/simplify/clarify the patch description, not talking about "buggy" etc, focusing on the simplification.

"
The original version of mremap_test (7df666253f26: "kselftests: vm: add mremap tests") validated remapped contents byte-by-byte and printed a mismatch index in case the bytes streams didn't match. That was rather inefficient, especially also if the test passed.

Later, commit 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution time from minutes to seconds using chunkwise memcmp") used memcmp() on bigger chunks, to fallback to byte-wise scanning to detect the problematic index only if it discovered a problem.

Quoted 7 lines

However, the implementation is overly complicated (e.g., get_sqrt() is currently not optimal) and we don't really have to report the exact
index: whoever debugs the failing test can figure that out.

Let's simplify by just comparing both byte streams with memcmp() and not detecting the exact failed index.
"

ISTM that if you get a failure it doesn't really matter how long a second scan takes.
So a simple byte loop that reports the offset and data of the first error and counts the number of errors is more than enough.

David

#7 lore raw
Quoted 78 lines · David Laight
Quoted 75 lines · On Tue, 14 Apr 2026 10:01:57 +0200 "David Hildenbrand (Arm)"…
Quoted 14 lines · Dev Jain

Yes.

I'll explain the algorithm in 7033c6cc9620.

The problem statement is: given two buffers of equal length n, find the first mismatch index.

Algorithm: Divide the buffers into sqrt(n) chunks. Do a memcmp() over each chunk. If all of them succeed, the buffers are equal, giving the result in O(sqrt(n)) * t, where t = time taken by memcmp().

Quoted 7 lines

Otherwise, worst case is that we find the mismatch in the last chunk. Now brute-force iterate this chunk to find the mismatch. Since chunk size is sqrt(n), complexity is again
sqrt(n) * t + sqrt(n) = O(sqrt(n)) * t.

So if get_sqrt() computes a wrong square root, we lose this time complexity.

Ah, thanks for clarifying.

Quoted 11 lines

Maybe there is an optimal value of x = #number of chunks of the buffer, which may not be sqrt(n).

But given the information we have, a CS course on algorithms will say this is one of the optimal ways to do it.

I just checked with ./mremap_test -t 0, the variance is very high on my system.

Quoted 6 lines

In the common case of the test passing:

before patch, there are multiple sub-length calls to memcmp. after patch, there is a single full-length call to memcmp.

So the time should reduce but may not be very distinguishable.

Okay, so doesn't matter. I agree that we should simplify all that.

The exact index is irrelevant. Whoever wants to debug the test failure could modify the test to find that out. It's one of the tests we don't really expect to fail (often).

Quoted 4 lines

Not needed. 7033c6cc9620 does not create any incorrectness in the checking of mismatch index.

Yes, agreed.

I would suggest to rewrite/simplify/clarify the patch description, not talking about "buggy" etc, focusing on the simplification.

"
The original version of mremap_test (7df666253f26: "kselftests: vm: add mremap tests") validated remapped contents byte-by-byte and printed a mismatch index in case the bytes streams didn't match. That was rather inefficient, especially also if the test passed.

Later, commit 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution time from minutes to seconds using chunkwise memcmp") used memcmp() on bigger chunks, to fallback to byte-wise scanning to detect the problematic index only if it discovered a problem.

However, the implementation is overly complicated (e.g., get_sqrt() is currently not optimal) and we don't really have to report the exact
index: whoever debugs the failing test can figure that out.

Quoted 8 lines
Quoted 3 lines

Let's simplify by just comparing both byte streams with memcmp() and not detecting the exact failed index.
"

ISTM that if you get a failure it doesn't really matter how long a second scan takes.
So a simple byte loop that reports the offset and data of the first error and counts the number of errors is more than enough.

That could also be done. But if the stars align and the test actually fails, I am not even sure if the exact index is really helpful. So I'd just drop that index reporting entirely.

Signature · 3 lines
Cheers,

David
Tested-by on v1 1/1
#10 lore raw
In reply to Dev Jain
Quoted 20 lines · Dev Jain

The original version of mremap_test (7df666253f26: "kselftests: vm: add mremap tests") validated remapped contents byte-by-byte and printed a mismatch index in case the bytes streams are not equal. That made validation expensive in both cases: for "no mismatch" (the common case when mremap is not buggy), it still walked all bytes in C; for "mismatch", it broke out of the loop after printing the mismatch index.

Later, my commit 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution time from minutes to seconds using chunkwise memcmp") tried to optimize both cases by using chunk-wise memcmp() and only scanning bytes within a range which has been determined by memcmp as mismatching.

But get_sqrt() in that commit is buggy: high = mid - 1 is applied unconditionally. This makes the speed of checking the mismatch index suboptimal.

The mismatch index does not provide useful debugging value here: if validation fails, we know mremap behavior is wrong, and the specific byte offset does not make root-causing easier.

Quoted 5 lines

So instead of fixing get_sqrt(), bite the bullet, drop mismatch index scanning and just compare the two byte streams with memcmp().

I have tested this patch with

./mremap_test -t 0

and the selftest results are unchanged.

I did not observe any significant change in execution time across multiple runs.

Quoted 153 lines

---
Sorry for sending two patchsets the same day - the problem was made known to me today, and I couldn't help myself but fix it immediately, imagine my embarrassment when I found out that I made a typo in the binary search code which I had been writing consistently throughout college :)

Applies on mm-unstable.

  tools/testing/selftests/mm/mremap_test.c | 109 +++--------------------
  1 file changed, 10 insertions(+), 99 deletions(-)
tools/testing/selftests/mm/mremap_test.c +10 -99
index 308576437228c..131d9d6db8679 100644
@@ -76,27 +76,6 @@ enum {
  	.expect_failure = should_fail				\
  }
 
-/* compute square root using binary search */
-static unsigned long get_sqrt(unsigned long val)
-{
-	unsigned long low = 1;
-
-	/* assuming rand_size is less than 1TB */
-	unsigned long high = (1UL << 20);
-
-	while (low <= high) {
-		unsigned long mid = low + (high - low) / 2;
-		unsigned long temp = mid * mid;
-
-		if (temp == val)
-			return mid;
-		if (temp < val)
-			low = mid + 1;
-		high = mid - 1;
-	}
-	return low;
-}
-
  /*
   * Returns false if the requested remap region overlaps with an
   * existing mapping (e.g text, stack) else returns true.
@@ -995,11 +974,9 @@ static long long remap_region(struct config c, unsigned int threshold_mb,
  			      char *rand_addr)
  {
  	void *addr, *tmp_addr, *src_addr, *dest_addr, *dest_preamble_addr = NULL;
-	unsigned long long t, d;
  	struct timespec t_start = {0, 0}, t_end = {0, 0};
  	long long  start_ns, end_ns, align_mask, ret, offset;
  	unsigned long long threshold;
-	unsigned long num_chunks;
 
  	if (threshold_mb == VALIDATION_NO_THRESHOLD)
  		threshold = c.region_size;
@@ -1068,87 +1045,21 @@ static long long remap_region(struct config c, unsigned int threshold_mb,
  		goto clean_up_dest_preamble;
  	}
 
-	/*
-	 * Verify byte pattern after remapping. Employ an algorithm with a
-	 * square root time complexity in threshold: divide the range into
-	 * chunks, if memcmp() returns non-zero, only then perform an
-	 * iteration in that chunk to find the mismatch index.
-	 */
-	num_chunks = get_sqrt(threshold);
-	for (unsigned long i = 0; i < num_chunks; ++i) {
-		size_t chunk_size = threshold / num_chunks;
-		unsigned long shift = i * chunk_size;
-
-		if (!memcmp(dest_addr + shift, rand_addr + shift, chunk_size))
-			continue;
-
-		/* brute force iteration only over mismatch segment */
-		for (t = shift; t < shift + chunk_size; ++t) {
-			if (((char *) dest_addr)[t] != rand_addr[t]) {
-				ksft_print_msg("Data after remap doesn't match at offset %llu\n",
-						t);
-				ksft_print_msg("Expected: %#x\t Got: %#x\n", rand_addr[t] & 0xff,
-						((char *) dest_addr)[t] & 0xff);
-				ret = -1;
-				goto clean_up_dest;
-			}
-		}
-	}
-
-	/*
-	 * if threshold is not divisible by num_chunks, then check the
-	 * last chunk
-	 */
-	for (t = num_chunks * (threshold / num_chunks); t < threshold; ++t) {
-		if (((char *) dest_addr)[t] != rand_addr[t]) {
-			ksft_print_msg("Data after remap doesn't match at offset %llu\n",
-					t);
-			ksft_print_msg("Expected: %#x\t Got: %#x\n", rand_addr[t] & 0xff,
-					((char *) dest_addr)[t] & 0xff);
-			ret = -1;
-			goto clean_up_dest;
-		}
+	/* Verify byte pattern after remapping */
+	if (memcmp(dest_addr, rand_addr, threshold)) {
+		ksft_print_msg("Data after remap doesn't match\n");
+		ret = -1;
+		goto clean_up_dest;
  	}
 
  	/* Verify the dest preamble byte pattern after remapping */
-	if (!c.dest_preamble_size)
-		goto no_preamble;
-
-	num_chunks = get_sqrt(c.dest_preamble_size);
-
-	for (unsigned long i = 0; i < num_chunks; ++i) {
-		size_t chunk_size = c.dest_preamble_size / num_chunks;
-		unsigned long shift = i * chunk_size;
-
-		if (!memcmp(dest_preamble_addr + shift, rand_addr + shift,
-			    chunk_size))
-			continue;
-
-		/* brute force iteration only over mismatched segment */
-		for (d = shift; d < shift + chunk_size; ++d) {
-			if (((char *) dest_preamble_addr)[d] != rand_addr[d]) {
-				ksft_print_msg("Preamble data after remap doesn't match at offset %llu\n",
-						d);
-				ksft_print_msg("Expected: %#x\t Got: %#x\n", rand_addr[d] & 0xff,
-						((char *) dest_preamble_addr)[d] & 0xff);
-				ret = -1;
-				goto clean_up_dest;
-			}
-		}
-	}
-
-	for (d = num_chunks * (c.dest_preamble_size / num_chunks); d < c.dest_preamble_size; ++d) {
-		if (((char *) dest_preamble_addr)[d] != rand_addr[d]) {
-			ksft_print_msg("Preamble data after remap doesn't match at offset %llu\n",
-					d);
-			ksft_print_msg("Expected: %#x\t Got: %#x\n", rand_addr[d] & 0xff,
-					((char *) dest_preamble_addr)[d] & 0xff);
-			ret = -1;
-			goto clean_up_dest;
-		}
+	if (c.dest_preamble_size &&
+	    memcmp(dest_preamble_addr, rand_addr, c.dest_preamble_size)) {
+		ksft_print_msg("Preamble data after remap doesn't match\n");
+		ret = -1;
+		goto clean_up_dest;
  	}
 
-no_preamble:
  	start_ns = t_start.tv_sec * NS_PER_SEC + t_start.tv_nsec;
  	end_ns = t_end.tv_sec * NS_PER_SEC + t_end.tv_nsec;
  	ret = end_ns - start_ns;
author
#9 lore raw
In reply to David Hildenbrand (Arm)
Quoted 17 lines

I would suggest to rewrite/simplify/clarify the patch description, not talking about "buggy" etc, focusing on the simplification.

"
The original version of mremap_test (7df666253f26: "kselftests: vm: add mremap tests") validated remapped contents byte-by-byte and printed a mismatch index in case the bytes streams didn't match. That was rather inefficient, especially also if the test passed.

Later, commit 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution time from minutes to seconds using chunkwise memcmp") used memcmp() on bigger chunks, to fallback to byte-wise scanning to detect the problematic index only if it discovered a problem.

Quoted 6 lines

However, the implementation is overly complicated (e.g., get_sqrt() is currently not optimal) and we don't really have to report the exact
index: whoever debugs the failing test can figure that out.

Let's simplify by just comparing both byte streams with memcmp() and not detecting the exact failed index.

Thanks, I'll use this!

Quoted 3 lines

"

author
#4 lore raw
In reply to Ryan Roberts
Quoted 114 lines · Ryan Roberts
Quoted 64 lines · Dev Jain
Quoted 13 lines · David Hildenbrand (Arm)
Quoted 12 lines · Dev Jain

The original version of mremap_test (7df666253f26: "kselftests: vm: add mremap tests") validated remapped contents byte-by-byte and printed a mismatch index in case the bytes streams are not equal. That made validation expensive in both cases: for "no mismatch" (the common case when mremap is not buggy), it still walked all bytes in C; for "mismatch", it broke out of the loop after printing the mismatch index.

Later, my commit 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution time from minutes to seconds using chunkwise memcmp") tried to optimize both cases by using chunk-wise memcmp() and only scanning bytes within a range which has been determined by memcmp as mismatching.

Quoted 5 lines
Quoted 3 lines

But get_sqrt() in that commit is buggy: high = mid - 1 is applied unconditionally. This makes the speed of checking the mismatch index suboptimal.

So is that the only problem with 7033c6cc9620: the speed?

Yes.

I'll explain the algorithm in 7033c6cc9620.

The problem statement is: given two buffers of equal length n, find the first mismatch index.

Algorithm: Divide the buffers into sqrt(n) chunks. Do a memcmp() over each chunk. If all of them succeed, the buffers are equal, giving the result in O(sqrt(n)) * t, where t = time taken by memcmp().

Otherwise, worst case is that we find the mismatch in the last chunk. Now brute-force iterate this chunk to find the mismatch. Since chunk size is sqrt(n), complexity is again
sqrt(n) * t + sqrt(n) = O(sqrt(n)) * t.

So if get_sqrt() computes a wrong square root, we lose this time complexity.

Maybe there is an optimal value of x = #number of chunks of the buffer, which may not be sqrt(n).

But given the information we have, a CS course on algorithms will say this is one of the optimal ways to do it.

Quoted 6 lines
Quoted 5 lines

The mismatch index does not provide useful debugging value here: if validation fails, we know mremap behavior is wrong, and the specific byte offset does not make root-causing easier.

Quoted 7 lines

Fully agreed.

Quoted 3 lines

So instead of fixing get_sqrt(), bite the bullet, drop mismatch index scanning and just compare the two byte streams with memcmp().

How does this affect the execution time of the test?

I just checked with ./mremap_test -t 0, the variance is very high on my system.

Quoted 6 lines

In the common case of the test passing:

before patch, there are multiple sub-length calls to memcmp. after patch, there is a single full-length call to memcmp.

So the time should reduce but may not be very distinguishable.

My intuition would be the opposite; if you hafve a 4096 byte buffer, I would have thought that a single memcmp would be significantly faster than sqrt(4096) = 64 calls, each over 64 bytes.

If you want to keep the common case fast, but also find the first differing offset on failure, I expect you can exploit the fact that the buffers are all page aligned. With some prompting, Codex gave me this:

---8<---
static size_t first_mismatch_offset(const void *buf1, const void *buf2,
size_t len)

{
	const uint64_t *ptr1 = buf1;
	const uint64_t *ptr2 = buf2;
	size_t word;
	size_t words = len / sizeof(*ptr1);

	assert(!((uintptr_t)buf1 & (sizeof(*ptr1) - 1)));
	assert(!((uintptr_t)buf2 & (sizeof(*ptr2) - 1)));
	assert(!(len & (sizeof(*ptr1) - 1)));

	if (!memcmp(buf1, buf2, len))
		return len;

	for (word = 0; word < words; word++) {
		if (ptr1[word] != ptr2[word]) {
			const unsigned char *bytes1 =
				(const unsigned char *)&ptr1[word];
			const unsigned char *bytes2 =
				(const unsigned char *)&ptr2[word];
			size_t i;

			for (i = 0; i < sizeof(*ptr1); i++) {
				if (bytes1[i] != bytes2[i])
					return word * sizeof(*ptr1) + i;
			}
		}
	}

	return len;
}
Quoted 3 lines

---8<---

I've not benchmarked it though...

Interesting, thanks Ryan.

It may be faster from a constant-factor PoV - cache, CPU etc not from a time complexity PoV.

But the point is that this is not a problem worthy of solving : )

Quoted 39 lines

Thanks,
Ryan

Quoted 32 lines
Quoted 10 lines
Quoted 5 lines
Fixes 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution time

from minutes to seconds using chunkwise memcmp")

?

Not needed. 7033c6cc9620 does not create any incorrectness in the checking of mismatch index.

Quoted 17 lines
Quoted 6 lines

---
Sorry for sending two patchsets the same day - the problem was made known to me today, and I couldn't help myself but fix it immediately, imagine my embarrassment when I found out that I made a typo in the binary search code which I had been writing consistently throughout college :)

:)

Quoted 5 lines

Applies on mm-unstable.

 tools/testing/selftests/mm/mremap_test.c | 109 +++--------------------
 1 file changed, 10 insertions(+), 99 deletions(-)

I mean, it certainly looks like a nice cleanup.

author
#8 lore raw
In reply to David Laight
Quoted 119 lines · David Laight
Quoted 116 lines · On Tue, 14 Apr 2026 10:01:57 +0200 "David Hildenbrand (Arm)"…
Quoted 33 lines · Dev Jain
Quoted 13 lines · David Hildenbrand (Arm)
Quoted 12 lines · Dev Jain

The original version of mremap_test (7df666253f26: "kselftests: vm: add mremap tests") validated remapped contents byte-by-byte and printed a mismatch index in case the bytes streams are not equal. That made validation expensive in both cases: for "no mismatch" (the common case when mremap is not buggy), it still walked all bytes in C; for "mismatch", it broke out of the loop after printing the mismatch index.

Later, my commit 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution time from minutes to seconds using chunkwise memcmp") tried to optimize both cases by using chunk-wise memcmp() and only scanning bytes within a range which has been determined by memcmp as mismatching.

Quoted 5 lines
Quoted 3 lines

But get_sqrt() in that commit is buggy: high = mid - 1 is applied unconditionally. This makes the speed of checking the mismatch index suboptimal.

So is that the only problem with 7033c6cc9620: the speed?

Yes.

I'll explain the algorithm in 7033c6cc9620.

The problem statement is: given two buffers of equal length n, find the first mismatch index.

Algorithm: Divide the buffers into sqrt(n) chunks. Do a memcmp() over each chunk. If all of them succeed, the buffers are equal, giving the result in O(sqrt(n)) * t, where t = time taken by memcmp().

Quoted 7 lines

Otherwise, worst case is that we find the mismatch in the last chunk. Now brute-force iterate this chunk to find the mismatch. Since chunk size is sqrt(n), complexity is again
sqrt(n) * t + sqrt(n) = O(sqrt(n)) * t.

So if get_sqrt() computes a wrong square root, we lose this time complexity.

Ah, thanks for clarifying.

Quoted 24 lines

Maybe there is an optimal value of x = #number of chunks of the buffer, which may not be sqrt(n).

But given the information we have, a CS course on algorithms will say this is one of the optimal ways to do it.

Quoted 6 lines
Quoted 5 lines

The mismatch index does not provide useful debugging value here: if validation fails, we know mremap behavior is wrong, and the specific byte offset does not make root-causing easier.

Quoted 7 lines

Fully agreed.

Quoted 3 lines

So instead of fixing get_sqrt(), bite the bullet, drop mismatch index scanning and just compare the two byte streams with memcmp().

How does this affect the execution time of the test?

I just checked with ./mremap_test -t 0, the variance is very high on my system.

Quoted 6 lines

In the common case of the test passing:

before patch, there are multiple sub-length calls to memcmp. after patch, there is a single full-length call to memcmp.

So the time should reduce but may not be very distinguishable.

Okay, so doesn't matter. I agree that we should simplify all that.

The exact index is irrelevant. Whoever wants to debug the test failure could modify the test to find that out. It's one of the tests we don't really expect to fail (often).

Quoted 6 lines
Quoted 6 lines
Quoted 5 lines
Quoted 7 lines
Quoted 4 lines
Fixes 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution time

from minutes to seconds using chunkwise memcmp")

?

Not needed. 7033c6cc9620 does not create any incorrectness in the checking of mismatch index.

Yes, agreed.

I would suggest to rewrite/simplify/clarify the patch description, not talking about "buggy" etc, focusing on the simplification.

"
The original version of mremap_test (7df666253f26: "kselftests: vm: add mremap tests") validated remapped contents byte-by-byte and printed a mismatch index in case the bytes streams didn't match. That was rather inefficient, especially also if the test passed.

Later, commit 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution time from minutes to seconds using chunkwise memcmp") used memcmp() on bigger chunks, to fallback to byte-wise scanning to detect the problematic index only if it discovered a problem.

However, the implementation is overly complicated (e.g., get_sqrt() is currently not optimal) and we don't really have to report the exact
index: whoever debugs the failing test can figure that out.

Quoted 8 lines
Quoted 3 lines

Let's simplify by just comparing both byte streams with memcmp() and not detecting the exact failed index.
"

ISTM that if you get a failure it doesn't really matter how long a second scan takes.
So a simple byte loop that reports the offset and data of the first error and counts the number of errors is more than enough.

You are right in saying that it won't matter how long the second scan takes, but it also doesn't matter what is the mismatch offset : ) so let us remove some code while we can!

Quoted 4 lines

David