Re: [PATCH] selftests/mm: Simplify byte pattern checking in mremap_test

[Dev Jain <dev.jain@arm.com>]

On 14/04/26 12:57 am, David Hildenbrand (Arm) wrote:
> On 4/10/26 16:30, Dev Jain wrote:
>> 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.
> 
> 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.

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

> 
>>
>> Reported-by: Sarthak Sharma <sarthak.sharma@arm.com>
>> Signed-off-by: Dev Jain <dev.jain@arm.com>
> 
> 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.

> 
>> ---
>> 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(-)
> 
> I mean, it certainly looks like a nice cleanup.
>