Re: memcmp-sse4.S EqualHappy bug

[Szabolcs Nagy <nsz at port70 dot net>]

* Andrea Arcangeli <aarcange@redhat.com> [2015-06-17 19:29:03 +0200]:
> last week I run into some problem because of an erratic behavior of
> memcmp/bcmp that returns "0" even thought the two regions are never
> equal at any given time if using the memcmp-sse4.S version (the
> default in most recent Linux on x86-64 hardware with sse4).
> 
> My bug was that I was getting the zeropage sometime erratically mapped
> (that was a bug in the testsuite in userland but I didn't fix that
> yet) so I added a memcmp(page, zeropage, page_size) in the code to
> detect when it would happen. Unfortunately this memcmp started to
> report all zero even when the "page" was not a zeropage, and it kept
> reporting it even after I actually fixed such a bug in the
> testsuite.
> 
> The original testcase was here (not guaranteed permalink but it should
> work for a long while):
> 
> https://git.kernel.org/cgit/linux/kernel/git/andrea/aa.git/tree/tools/testing/selftests/vm/userfaultfd.c?h=userfault21
> 
> I had a contended pthread_mutex_t at the start of the page given as
> parameter to memcmp (that was changing all the time), immediately
> followed by an unsigned long long counter which was never zero at any
> given time.
> 
> Now I reduced the testcase to the minimum and I appended it at the end
> of this email.
> 
> By the C standard I assume this is not a bug because the C language
> assumes everything is single threaded (and if I put a mutex lock
> around the memcmp to prevent the memory to change under it, of course
> it works correctly then). However having memcmp returning 0 when the
> two areas can never zero at any given time (no matter part of the
> memory compared is changing) looks risky. In my case I was testing
> userfaultfd so I had to first think at all sort of tlb flushes or race
> conditions in the kernel before I considered the possibility of memcmp
> being "buggy" (buggy not by C standard terms but still...). I started
> to consider it was memcmp failing after I checked the counter by hand
> to be non zero before starting the memcmp.
> 

c11 has threads and a memory model that makes concurrency issues
observable in standard c.

however you have a data race that is undefined behaviour:

objects passed to memcmp are not supposed to be modified concurrently
without synchronization.

> The problem is that the unrolled loop using sse4 only do ptest so they
> can't return positive negative values directly. When the unrolled loop
> breaks out it jumps to an offset that repeat the test re-reading the
> memory (but this time it will get an equal copy) and it will return 0
> without continuing comparing the rest of the data.
> 

that is unfortunate but i think your test code should be fixed.

(to avoid the observed behaviour the libc would have to guarantee
atomic memcmp which is nontrivial to do)