Non-temporal stores (and _mm_stream operations in stdarch) break our memory model

[RalfJung]

I recently discovered this funny little intrinsic with the great comment

Emits a !nontemporal store according to LLVM (see their docs). Probably will never become stable.

Unfortunately, the comment is wrong: this has become stable, through vendor intrinsics like _mm_stream_ps.

Why is that a problem? Well, turns out non-temporal stores completely break our memory model. The following assertion can fail under the current compilation scheme used by LLVM:

static mut DATA: usize = 0;
static INIT: AtomicBool = AtomicBool::new(false);

thread::spawn(|| {
  while INIT.load(Acquire) == false {}
  assert_eq!(DATA, 42); // can this ever fail? that would be bad
});

nontemporal_store(&mut DATA, 42);
INIT.store(true, Release);

The assertion can fail because the CPU may order MOVNT after later MOV (for different locations), so the nontemporal_store might occur after the release store. Sources for this claim:

• Peter Cordes answer here: "A mutex unlock on x86 is sometimes a lock add, in which case that's a full fence for NT stores already. But if you can't rule out a mutex implementation using a simple mov store then you need at least sfence at some point after NT stores, before unlock."
• glibc fixing their memcpy (which uses nontemporal stores) to have a trailing sfence.

This is a big problem -- we have a memory model that says you can use release/acquire operations to synchronize any (including non-atomic) memory accesses, and we have memory accesses which are not properly synchronized by release/acquire operations.

So what could be done?

• Remove nontemporal_store and implement the _mm_stream intrinsics without it and mark them as deprecated to signal that they don't match the expected semantics of the underlying hardware operation. People should use inline assembly instead and then it is their responsibility to have an sfence at the end of their asm block to restore expected synchronization behavior.
• Change the way release stores are compiled such that an sfence is emitted. This is mostly a theoretical option though: this is an ABI-breaking change, at least my understanding of the x86 ABI is that a regular mov is considered to be sufficient synchronization. To make this work reliably all compilers for all languages that have something like release writes need to emit the sfence, or else Rust code cannot be soundly linked with code produced by those other compilers.
• There's a third hypothetical option of adjusting our concurrency memory model to be able to support these operations. But that's (a) a huge design space -- which fences are supposed to interact how with this? We might even have to add a new kind of fence! And (b) modifying the C++ concurrency memory model should be done with utmost care and thorough formal analysis; the current model is the result of a decade worth of research that shouldn't be thrown away lightly.
• Just ignore the problem and hope it doesn't explode? I am not happy with this.

Thanks a lot to @workingjubilee and @the8472 for their help in figuring out the details of nontemporal stores.

Cc @rust-lang/lang @Amanieu

Also see the nomination comment here.

[RalfJung]

I should have also Cc @rust-lang/opsem

[the8472]

I believe there are additional options:

C) have the backend lower the non-temporal store to either

• a regular store
• MOVNT + deferred sfence

whichever seems more beneficial. The sfence can be deferred up to the next atomic release (or stronger) and things that might contain one.

D) add a Safety requirement to the vendor intrinsic.

[digama0]

It's not clear to me that this "breaks the model" as opposed to "extends the model". Why can't we have nontemporal stores as an explicit part of the atomics model, and say that they are not necessarily synchronized by a release-acquire pair to another thread?

[RalfJung]

have the backend lower the non-temporal store to either

Is "deferred sfence" a thing we can tell LLVM to do?

Also I think if we lower _mm_stream_ps in a way that includes an sfence, people will be very surprised. We should rather not expose _mm_stream_ps than expose something that's not the same operation.

add a Safety requirement to the vendor intrinsic.

No that doesn't work. We still need to explain how and why code has UB when it violates safety. Our current memory model has no way to make this code be UB.

This is an intrinsic, not a library function. It is specified by the operational semantics, not a bunch of axioms in the "safety" comment. The safety comment is merely reflecting the constraints that arise from the operational semantics. Making the safety comment the spec would mean making the spec axiomatic and that is something we certainly don't want to do.

Why can't we have nontemporal stores as an explicit part of the atomics model,

We can, but then we'll have to develop our own model. The C++ model does not have such stores.
I don't think we should have our own concurrency model, that well exceeds our capacity. Concurrency models are very hard to get right and being able to inherit all the formal studies of the C++ model is extremely valuable.

And process-wise, we certainly can't have a library feature like stdarch just change the memory model. That requires an RFC. It seems fairly clear that the impact of _mm_stream_ps on the whole language was not realized at the time of stabilization, and I think our only option is to remove this operation again -- or rather, get as close to removing it was we can within our stability guarantees: make it harmless, and deprecate it.

[the8472]

Is "deferred sfence" a thing we can tell LLVM to do?

Not that I know. But it may be something llvm should be doing when a store is annotated with !nontemporal. Unless their memory model already knows how to specify nontemporal + release behavior (which may just be UB) because it's broader than the C++ model.

Also I think if we lower _mm_stream_ps in a way that includes an sfence, people will be very surprised. We should rather not expose _mm_stream_ps than expose something that's not the same operation.

I assume long as the sfence is sunk far enough they might not care. Just like mixing AVX and SSE can result in VZEROUPPER being inserted by the backend.

This is an intrinsic, not a library function.

I see. That distinction isn't always obvious. But it makes sense if we want the compiler to optimize around the intrinsics more than around FFI calls.

We can, but then we'll have to develop our own model. The C++ model does not have such stores.

Can we say we use the C++ model with the modification that an axiom (all stores are ordered with release operations) is turned into a requirement (all stores must be ordered with release operations). That seems minimally invasive.

[CAD97]

This is an intrinsic, not a library function.

nontemporal_store is our intrinsic, but _mm_stream_ps is a vendor intrinsic. If nontemporal_store is to be directly exposed it certainly needs to participate in the operational semantics. But vendor intrinsics are somewhat special.

Vendor intrinsics are sort of halfway between standard Rust and inline asm. The semantics of the vendor intrinsic is whatever asm the vendor says it is, and it's the responsibility of the user of the intrinsic to understand what that means (or doesn't) on the Rust AM and use the intrinsics in a way consistent on the AM. Ideally, writing _mm_stream_ps(ptr, a) and writing asm!("MOVNTPS {ptr}, {a}") (with the correct flags which I haven't bothered figuring out) should be functionally identical, except that the former is potentially better understood by the compiler and doesn't have the monkeypatchable semantics of inline asm.

Is this complicated by the extra function boundaries imposed by us exposing vendor intrinsics as extern "Rust" fn instead of extern "vendor-intrinsic"? Certainly¹, since _mm_stream_ps(ptr, a); _mm_sfence() and asm!("MOVNTPS {ptr}, {a}", "SFENCE") are different, but in a way I think easier to resolve than either fixing compilers to better respect weak/nt memory ordering on x86[_64] or auditing every vendor intrinsic for individually having consistent semantics on the Rust AM.

Slightly reinterpreting: it's perfectly acceptable, even expected for Miri to error when encountering vendor intrinsics. Using them steps outside the AM in a similar manner to inline asm, and as such you're relying on target specifics for coherency and sacrificing the ability to use AM-level sanitizers like Miri except on a best-effort basis.

Footnotes

1. We should ideally consider if we can get away with "fixing" this such that vendor intrinsics can't be made into function pointers and aren't actually functions, to make their special status more evident. Though abusing the ABI marker for intrinsics is still a bit of a bodge, and this doesn't completely resolve the issues since asm!("MOVNTPS {ptr}, {a}"); asm!("SFENCE") still steps the AM in an inconsistent state between the two asm blocks. ↩

[RalfJung]

I see. That distinction isn't always obvious. But it makes sense if we want the compiler to optimize around the intrinsics more than around FFI calls.

FFI calls don't help, FFI calls are only allowed to perform operations that could also be performed by Rust code (insofar as Rust-controlled state is affected). Getting the program into a state where release/acquire synchronization does not work any more is not allowed in any way, not even via FFI.

Like, imagine the following code:

static mut DATA: usize = 0;
static INIT: AtomicBool = AtomicBool::new(false);

thread::spawn(|| {
  while INIT.load(Acquire) == false {}
  let data = DATA;
  if data != data { unreachable_unchecked(); }
});

some_function(&mut DATA, 42);
INIT.store(true, Release);

This code is obviously sound. The compiler is allowed to change this code such that the spawned thread becomes

  while INIT.load(Acquire) == false {}
  if DATA != DATA { unreachable_unchecked(); }

However, if some_function does a non-temporal store, this change can introduce UB! Now the non-temporal store might take effect between the two reads of DATA, and suddenly a value can seem unequal to itself.

Therefore, it is UB to leave an inline assembly block or FFI operation with any "pending non-temporal stores that haven't been guarded by a fence yet". The correctness of compilation relies on this assumption.

Can we say we use the C++ model with the modification that an axiom (all stores are ordered with release operations) is turned into a requirement (all stores must be ordered with release operations). That seems minimally invasive.

No, that's not how defining a memory model works. You'll need to define a new kind of memory access that's even weaker than non-atomic accesses and adjust the entire model to account for them.

The semantics of the vendor intrinsic is whatever asm the vendor says it is,

That doesn't work, they need to be phrased in terms of the Rust AM. Lucky enough they are mostly about what happens to certain values of SIMD type, so the vendor semantics directly translate to Rust AM semantics.

But when it comes to synchronization, this approach falls flat. If _mm_stream_ps was implemented via inline assembly it would be UB.

auditing every vendor intrinsic for individually having consistent semantics on the Rust AM.

There's no way around that, but I hope we don't have many intrinsics that have global synchronization effects.

Slightly reinterpreting: it's perfectly acceptable, even expected for Miri to error when encountering vendor intrinsics. Using them steps outside the AM in a similar manner to inline asm, and as such you're relying on target specifics for coherency and sacrificing the ability to use AM-level sanitizers like Miri except on a best-effort basis.

Even vendor intrinsics are subject to the rule that governs all FFI and inline assembly: you can only do things to Rust-visible state that you could also have done in Rust. _mm_stream_ps violates that rule.