Bit-wise reasoning for atomic accesses

[RalfJung]

One of my colleagues came up with an example that breaks at least “if all writes have the same value then use that value”. Using it to break byte requires some creativity.

Consider the following program (two threads running in parallel):

1 {
2 X_na = 1; // meaning "non-atomic write to X"
3 X_na = 0; // consider this the "initialization write"
4 Y_rel = 1; // release-write to Y
5 X_na = 0;
6 }
7 ||
8 {
9   if(Y_acq){ // acquire-read from Y
10      a = X_na;
11  }
12}

When executing line 10, we see two possible writes to pick from (the ones from lines 3 and 5). Both have the same value. However, LLVM can optimize the first thread to remove line 3: That write is redundant because it gets overwritten in line 5, and the fact that there is a release write does not matter because lines 3 and 5 are non-atomic accesses.

---

We can almost, but not quite get there with bytes. Something not too dissimilar from the above situation can still arise with byte. Like, when I do

let mut buf = BytesMut::with_capacity(1);
buf = BytesMut::with_capacity(1024);

and when the compiler inlines all of that and reuses the same storage for the second buffer, the buf.inner.arc will first be KIND_INLINE and then later KIND_VEC (matching lines 2 and 3 of the example above). If we then send a pointer to the buf away, that will look like lines 4 and 9.

The one thing we do not get, I think, is line 5. We can, I guess trigger an atomic write to buf.inner.arc by doing something with buf that would make it change the pointer, but I am not familiar enough with this data structure to say what that would be and I am also not sure if the optimization mentioned above is still legal when line 5 is changed to be atomic (I asked my colleague).

Still, the fact that you can overwrite an existing BytesMut with a new one means that the KIND of one of these pointers can change, if you consider the entire lifetime of the location it is stored into (which you have to). So it’s not like all writes have the same KIND, just the ones that the non-atomic read can choose from – and as the example above shows, that on its own is not sufficient to make your argument work. It might be that BytesMut does something else that would be a sufficient condition, but it’s certainly more complex than we thought.

[gnzlbg]

You are correct that it is a data race according to the LLVM model. It is assuming that, in practice, no chip will randomly set the bits to random values.

Ehm… what this actually is assuming is that LLVM will never be able to tell that this code has an unconditional data-race in a multi-threaded context and can therefore not be reached along with all code leading to it.

We should definitely fill in a missed optimization bug in LLVM with this example (spawning some threads) because all of it should compile to nothing.

---

We should also find out a way to make @carllerche’s example not have UB and still produce efficient code. The unordered ordering definitely looks worth exploring.

[carllerche]

Ehm… what this actually is assuming is that LLVM will never be able to tell that this code has an unconditional data-race in a multi-threaded context and can therefore not be reached along with all code leading to it.

Yes pretty much…

---

I thought more about it, and there is a way that I could probably restructure the internals of Bytes to avoid the race, but it would take a large chunk of work. Unless, in practice, there is a threat today, I don’t think I’ll be able to prioritize the work.

[comex]

It would be nice to know what optimization exactly LLVM is failing to perform. Does LLVM just not coalesce redundant relaxed loads at all, or is there something more subtle going on?

[gnzlbg]

@carllerche do you have a benchmark that shows the 30% perf regression that the comment talks about ?

[carllerche]

The comment mentions 10%. It was a long time ago, but I would guess the benches in the repo would show it.

[comex]

Yep, it doesn’t:

use std::sync::atomic::{Ordering::*, AtomicUsize};
pub fn load_twice(x: &AtomicUsize) -> (usize, usize) {
    let a = x.load(Relaxed);
    let b = x.load(Relaxed);
    (a, b)
}

->

playground::load_twice:
	movq	(%rdi), %rax
	movq	(%rdi), %rdx
	retq

That sucks. It may be possible to partially work around this on rustc’s end by marking the load function with LLVM’s readonly attribute, which is equivalent to __attribute__((pure)) in C. The semantics are that the function can read through its arguments and global state, but must not modify global state and must be deterministic. This means the compiler can fold multiple calls with the same arguments into one if there were no intervening writes. And, based on this C equivalent, LLVM does do so, even if the function is marked always_inline (in which case I feared it would inline the calls before it had a chance to merge them).

In theory we’d like a stricter semantics, where the function can read through its arguments but not read global state. That way, LLVM could theoretically merge reads even if there were intervening writes to other locations, if it could prove the addresses didn’t alias. (This would only be valid for relaxed loads.) Unfortunately, the only stricter option is readnone, aka __attribute__((const)) in C, which requires that the function not read anything from memory, not even from its arguments.

Anyway, as for actually fixing the issue in LLVM, this bug report looks on point:

https://bugs.llvm.org/show_bug.cgi?id=37716

We can definitely do this (see http://wg21.link/n4455), but is this something that you’ve seen happen in real code? I totally believe it can happen, but I’m not super interested in optimizing code which never happens

I went ahead and left a comment there.

[arielb1]

The one thing we do not get, I think, is line 5. We can, I guess trigger an atomic write to buf.inner.arc by doing something with buf that would make it change the pointer, but I am not familiar enough with this data structure to say what that would be and I am also not sure if the optimization mentioned above is still legal when line 5 is changed to be atomic (I asked my colleague).

Can’t you get this pattern of writes with a normal atomic?

// mut s_a: AtomicU32; /* initial value should not matter */
// mut s_b: AtomicPtr<AtomicU32> = AtomicPtr::null();

// mut x: u32

// Thread A

// these stores are non-atomic because we have &mut access
s_a = AtomicU32::new(1);
s_a = AtomicU32::new(0);
// but these store are atomic
s_b.store(&mut s_a, Ordering::Release);
s_a.store(0, Ordering::Relaxed);


// Thread B
let mut x = None;
let tmp = s_a.load(Ordering::Acquire);
if tmp != ptr::null() {
    x = Some((*tmp).load(Ordering::Relaxed));
}

I’m quite sure that here, x should either be None or Some(0). If removing the second non-atomic store (as a Thread A modification, ignoring anything thread B does) would be legal, then thread B could see Some(1) (or worse, Some(uninitialized)).

[RalfJung]

Good point! So the optimization can likely not break bytes. Interesting.

[arielb1]

What we actually want for bytes is some sort of load_freeze, that returns a non-undef value. @RalfJung thinks that having per-bit undef for loads and combining it with LLVM’s freeze would work.

[gnzlbg]

Unfortunately, the only stricter option is readnone , aka __attribute__((const)) in C, which requires that the function not read anything from memory, not even from its arguments.

I’ve needed that in jemalloc-sys: https://github.com/rust-lang/rust/issues/46046#issuecomment-345293572

So maybe having a #[rustc_readonly] attribute would be useful.

[RalfJung]

The comment mentions 10%. It was a long time ago, but I would guess the benches in the repo would show it.

How hard would it be to make experiments with LLVM the unordered ordering for this? I am not sure about how this is formally modeled, but it might actually be the “no-undef-on-read-write-races” that we need.

[carllerche]

If it can be used from Rust, probably not terribly hard.

[josh]

It would help if the Rust compiler had an equivalent to READ_ONCE and WRITE_ONCE as defined in the Linux kernel. Those force the compiler to perform a single load or store respectively, while not using a machine atomic. With those, you can safely make assumptions like “if READ_ONCE races with WRITE_ONCE or an atomic write, you’ll get either the old value or new value, never a mix of both”.

[RalfJung]

@josh The Linux kernel uses volatile accesses for that, and Rust has those.

The problem is that neither LLVM nor C actually specify volatile accesses to have the effect you described when it comes to data races. There is no interaction between the concurrency model and volatile accesses specified.

[josh]

C doesn’t, LLVM doesn’t, but in practice every real architecture does, and thus the Linux kernel does. That’s the reason those primitives exist.

There has been discussion in the C standards committee of standardizing something similar to the Linux kernel’s memory model.

[RalfJung]

every real architecture does

That just doesn’t matter. We are not talking about architecture semantics here, we are talking about programming language semantics. See this example by @alexcrichton for why arguing with architectures just does not make any sense in this discussion.

We need a commitment from LLVM, or else this will be a hack that “happens to work” but remains UB and could stop working any time LLVM adds a new optimization.

[josh]

I’m talking about programming language semantics as well. My point is precisely that we need the facilities to implement READ_ONCE and WRITE_ONCE primitives we can rely on.

C doesn’t specify that interaction with respect to volatile accesses, but in practice that is the interaction on every existing compiler and target, so the Linux kernel counts on that.

[RalfJung]

I agree it’d be reasonable for LLVM to guarantee that a volatile read will never have undef/poison in it, it will always be frozen. These reads cannot be duplicated, after all.

Has anybody ever talked with the LLVM devs about this? Is that something they would be willing to guarantee?

[RalfJung]

I just found this, seems very related: there is no such thing as a “benign” data race. In particular this has an explicit section on “disjoint bit manipulation” (Cc @carllerche)