memcmp-sse4.S EqualHappy bug

[Torvald Riegel]

On Thu, 2015-06-18 at 16:52 +0200, Andrea Arcangeli wrote:
> On Thu, Jun 18, 2015 at 04:23:35PM +0200, Torvald Riegel wrote:
> > There are a few differences to your memcmp test case though.  If
> > barrier() is a compiler barrier, this should "remove" prior knowledge
> > the compiler has about memory.  Second, you access volatile-qualified
> > data, which at least requires to do the accesses byte-wise or similar.
> > Does the memcmp test case also fail when you acess volatiles?
> 
> Actually the kernel code in the __builtin_memcpy case removes the
> volatile qualifier.

yeah, never mind...

> On a side note it's not normal to use READ_ONCE/WRITE_ONCE on
> objects larger than sizeof(long) and it would warn at build time but
> it would build successfully.
> 
> Changing my testcase like this just creates warning about volatile
> warning: passing argument 1 of ‘memset’ discards ‘volatile’ qualifier
> from pointer target type, etc... it still builds and fail at runtime
> like before. I added another barrier as well but it can't make a
> difference, the problem is very clear and how to prevent this
> practical problem is clear too. As long as memcmp-sse4.S is called
> there's nothing the compiler can do to prevent this problem from
> materializing.

Yeah, but if there were a memcmp that would respect volatile, then it
could make a difference.

> > Note that I'm not saying that this is guaranteed to work.  It's still UB
> > if there is a data race.  However, in practice, this might just continue
> > to work.
> 
> READ_ONCE/WRITE_ONCE are only used if there is going to be a data
> race, otherwise they're never used.

I know.  Technically, data races are UB, yet that a particular compiler
does something that works for you can still happen.

> > Userland programs should really try to transition to atomics and the
> > C11/C++11 memory model or just the __atomic builtins, if possible.
> 
> We should look into that.
> 
> Without a way to access non-atomic regions with C

I assume regions means memory regions not of atomic type(s).

What do you mean by "with C"?  Do you mean plain accesses, or just C
code?  If you just want to snapshot data for RCU, using atomic loads
with memory_order_relaxed is fine.  This could be put into a custom
memcpy.

> , RCU in the kernel
> cannot work. But if memcpy in the kernel has to behave sane (and not
> break out of the loop too happily) in presence of not-atomic changes
> to the memory, then I don't see why memcmp in userland is different.

I was distinguishing userland because userland should just rely on C11
and its memory model, IMO.  I don't have a strong opinion on what the
kernel should do, so I simply didn't want to comment on the latter.

> Also note there is also an userspace RCU, I don't know exactly how
> that works because I never used it, but the whole concept of RCU is to
> allow C language to access not-atomic regions of memory and to get
> away with it.

In general, this cannot work.  There might be compiler optimizations
that expect that they can safely reload data that is not accessed
through atomics nor is of atomic type.  Those can make a lot of sense
considering average code, but would break in this particular case. 

> And if that way is memcpy, I don't see what's
> fundamentally different about memcpy being required to cope with that,
> but memcmp not.

If there is a way for the compiler to see that the data accessed
speculatively in RCU can be modified concurrently, things are fine.
This could be explicitly atomic accesses, a custom memcpy or such, etc.
The stock memcpy assumes non-atomic data though, and data-race-freedom.

> I totally see why memcmp-sse4.S is safe by the standard, just the
> standard is not the only way to gain performance, RCU is required to
> scale 100% in SMP, pthread_mutex_rwlock wouldn't scale, so it's
> unthinkable to get rid of READ_ONCE/WRITE_ONCE. Switching to __atomic
> would be fine, and if __atomic can make memcpy (and IMHO memcmp)
> behave in a way they won't happily return too soon on __atomic
> builtins, it'd be great.

The __atomic builtins are all you need to implement concurrent code.
The kernel's memory model might be more fine-grained than what C11
offers currently (e.g., data dependences: memory_order_consume is
broken, and the kernel keeps its fingers crossed that the compiler will
not do what it would be actually allowed to do; I've been working with
Paul McKenney on this...).  Nonetheless, besides those potential
performance differences on some archs, it's all there.

BTW, I'm wondering what your memcmp would actually do internally, and
what it would guarantee precisely.  It can't just use relaxed-MO reads /
read_once without further barriers, because this won't guarantee
anything in face of multiple concurrent updaters; if using just
relaxed-MO reads, memcmp might read a snapshot that never existed in any
seq-cst ordering of all individual loads and stores on this memory
region.