# Bit-wise reasoning for atomic accesses

**URL:** <https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853>\
**Category:** Unsafe Code Guidelines\
**Created:** [November 17, 2018, 10:19am UTC](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853 "2018-11-17T10:19:37Z")\
**Posts on this page:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![comex](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/comex/32/2587_2.png) [@comex](https://internals.rust-lang.org/u/comex)\
**Post date:** [November 20, 2018, 2:48am UTC](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853/21 "2018-11-20T02:48:45Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![gnzlbg](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/gnzlbg/32/3858_2.png) [@gnzlbg](https://internals.rust-lang.org/u/gnzlbg)\
**Post date:** [November 20, 2018, 8:14am UTC](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853/22 "2018-11-20T08:14:53Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![carllerche](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/carllerche/32/530_2.png) [@carllerche](https://internals.rust-lang.org/u/carllerche)\
**Post date:** [November 20, 2018, 3:22pm UTC](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853/23 "2018-11-20T15:22:41Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![comex](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/comex/32/2587_2.png) [@comex](https://internals.rust-lang.org/u/comex)\
**Post date:** [November 21, 2018, 12:28am UTC](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853/24 "2018-11-21T00:28:31Z")

</div>

Yep, it doesn't:

```rust
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)
}

```

-\>

```rust
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](https://gcc.godbolt.org/z/z1e60B), 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](https://bugs.llvm.org/show_bug.cgi?id=37716)

> [@JF Bastien](#):
>
> We can definitely do this (see [N4455 No Sane Compiler Would Optimize Atomics](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.

---

<div class="post-metadata">

**Author:** ![arielb1](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/arielb1/32/3044_2.png) [@arielb1](https://internals.rust-lang.org/u/arielb1)\
**Post date:** [November 26, 2018, 9:51am UTC](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853/25 "2018-11-26T09:51:00Z")

</div>

> [@RalfJung](#):
>
> 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?

```Rust
// 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)`).

---

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [November 26, 2018, 11:30am UTC](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853/26 "2018-11-26T11:30:54Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![arielb1](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/arielb1/32/3044_2.png) [@arielb1](https://internals.rust-lang.org/u/arielb1)\
**Post date:** [November 26, 2018, 11:45am UTC](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853/27 "2018-11-26T11:45:35Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![gnzlbg](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/gnzlbg/32/3858_2.png) [@gnzlbg](https://internals.rust-lang.org/u/gnzlbg)\
**Post date:** [November 27, 2018, 6:19pm UTC](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853/28 "2018-11-27T18:19:15Z")

</div>

> [@comex](#):
>
> 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`: [liballoc\_jemalloc nallocx should be ReadOnly · Issue #46046 · rust-lang/rust · GitHub](https://github.com/rust-lang/rust/issues/46046#issuecomment-345293572)

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

---

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [December 13, 2018, 5:01pm UTC](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853/29 "2018-12-13T17:01:52Z")

</div>

> [@carllerche](#):
>
> 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.

---

<div class="post-metadata">

**Author:** ![carllerche](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/carllerche/32/530_2.png) [@carllerche](https://internals.rust-lang.org/u/carllerche)\
**Post date:** [December 13, 2018, 7:12pm UTC](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853/30 "2018-12-13T19:12:36Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![josh](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/josh/32/5934_2.png) [@josh](https://internals.rust-lang.org/u/josh)\
**Post date:** [December 14, 2018, 7:57pm UTC](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853/31 "2018-12-14T19:57:26Z")

</div>

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”.

---

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [December 15, 2018, 9:57am UTC](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853/32 "2018-12-15T09:57:58Z")

</div>

@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.

---

<div class="post-metadata">

**Author:** ![josh](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/josh/32/5934_2.png) [@josh](https://internals.rust-lang.org/u/josh)\
**Post date:** [December 15, 2018, 10:04am UTC](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853/33 "2018-12-15T10:04:35Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [December 15, 2018, 10:49am UTC](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853/34 "2018-12-15T10:49:24Z")

</div>

> [@josh](#):
>
> 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](https://github.com/rust-lang/rust/issues/32976#issuecomment-446775360) 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.

---

<div class="post-metadata">

**Author:** ![josh](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/josh/32/5934_2.png) [@josh](https://internals.rust-lang.org/u/josh)\
**Post date:** [December 15, 2018, 10:57am UTC](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853/35 "2018-12-15T10:57:57Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [December 15, 2018, 12:10pm UTC](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853/36 "2018-12-15T12:10:00Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [February 23, 2019, 12:59pm UTC](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853/37 "2019-02-23T12:59:52Z")

</div>

I just found this, seems very related: [there is no such thing as a “benign” data race](http://hboehm.info/boehm-hotpar11.pdf). In particular this has an explicit section on “disjoint bit manipulation” (Cc @carllerche)

---

<div class="post-metadata">

**Author:** ![comex](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/comex/32/2587_2.png) [@comex](https://internals.rust-lang.org/u/comex)\
**Post date:** [February 23, 2019, 5:50pm UTC](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853/38 "2019-02-23T17:50:00Z")

</div>

Note that the example in that section is valid for normal reads/writes, in which case a racing read that could observe the speculative store would be undefined behavior, but not if the read and write are both atomic (even if relaxed), in which case the read is guaranteed to observe some value that was previously written.

---

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [February 24, 2019, 11:45am UTC](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853/39 "2019-02-24T11:45:32Z")

</div>

Sure, relaxed accesses don’t make a data race (just a race condition, and these are allowed).

But this thread is precisely about code using a non-atomic (volatile) racy access.

---

<div class="post-metadata">

**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\
**Post date:** [May 25, 2019, 11:45am UTC](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853/40 "2019-05-25T11:45:32Z")

</div>

Closed on May 25, 2019, 11:45am UTC

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.

[Previous page](https://internals.rust-lang.org/t/bit-wise-reasoning-for-atomic-accesses/8853.md?page=1)