Re: memcmp-sse4.S EqualHappy bug

[OndÅej BÃlka <neleai at seznam dot cz>]

On Wed, Jun 17, 2015 at 08:59:52PM +0200, Szabolcs Nagy wrote:
> * 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)

More precisely impossible without very big hammer. My most effective
solution would be syscall that marks affected pages as read only to
suspend threads that try to write into them before doing comparison You need
simultaneous load of both memory areas which hardware doesn't support.

Without that there would still be race, simplest example would be

char x[4];
memcmp(x,x+1,1)

where another thread just does following:
*((int *)x) = 1;
memcmp read x[0] == 1
*((int *)x) = 256;
memcmp read x[1] == 1