selftests/mm: Simplify byte pattern checking in mremap_test
Subsystems (3)
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
@@ -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
David Hildenbrand (Arm)
maintainerQuoted 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-wisememcmp()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 - 1is 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 withmemcmp().
How does this affect the execution time of the test?
Quoted 3 lines
Reported-by Sarthak Sharma <[email protected]>Signed-off-by Dev Jain <[email protected]>
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
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-wisememcmp()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 - 1is 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 withmemcmp().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
Reported-by Sarthak Sharma <[email protected]>Signed-off-by Dev Jain <[email protected]>Fixes 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution timefrom 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.
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-wisememcmp()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 - 1is 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 bymemcmp().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 withmemcmp().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
Reported-by Sarthak Sharma <[email protected]>Signed-off-by Dev Jain <[email protected]>Fixes 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution timefrom minutes to seconds using chunkwise memcmp")
?
Not needed.
7033c6cc9620does 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.
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-wisememcmp()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 - 1is 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 bymemcmp().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 withmemcmp().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<---
staticsize_tfirst_mismatch_offset(const void *buf1, const void *buf2,
size_tlen){ 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,
RyanQuoted 32 lines
Quoted 10 lines
Quoted 5 lines
Reported-by Sarthak Sharma <[email protected]>Signed-off-by Dev Jain <[email protected]>Fixes 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution timefrom minutes to seconds using chunkwise memcmp")
?
Not needed.
7033c6cc9620does 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.
David Hildenbrand (Arm)
maintainerQuoted 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-wisememcmp()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 - 1is 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 bymemcmp().
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 withmemcmp().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
Reported-by Sarthak Sharma <[email protected]>Signed-off-by Dev Jain <[email protected]>
Quoted 7 lines
Quoted 4 lines
Fixes 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution timefrom minutes to seconds using chunkwise memcmp")
?
Not needed.
7033c6cc9620does 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
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-wisememcmp()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 - 1is 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 bymemcmp().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 withmemcmp().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
Reported-by Sarthak Sharma <[email protected]>Signed-off-by Dev Jain <[email protected]>Quoted 7 lines
Quoted 4 lines
Fixes 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution timefrom minutes to seconds using chunkwise memcmp")
?
Not needed.
7033c6cc9620does 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 ofmremap_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") usedmemcmp()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
David Hildenbrand (Arm)
maintainerQuoted 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 bymemcmp().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.
7033c6cc9620does 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 ofmremap_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") usedmemcmp()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
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-wisememcmp()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 - 1is 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 bymemcmp().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 withmemcmp().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
Reported-by Sarthak Sharma <[email protected]>Signed-off-by Dev Jain <[email protected]>Quoted 7 lines
Quoted 4 lines
Fixes 7033c6cc9620 ("selftests/mm: mremap_test: optimize execution timefrom minutes to seconds using chunkwise memcmp")
?
Not needed.
7033c6cc9620does 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 ofmremap_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") usedmemcmp()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
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 ofmremap_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") usedmemcmp()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
"
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-wisememcmp()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 - 1is 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 withmemcmp().Reported-by Sarthak Sharma <[email protected]>Signed-off-by Dev Jain <[email protected]>
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@@ -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;