[RFC] Semantics of partially overlapping atomic accesses

IR & Optimizations
1

Motivation / the Problem

So far, the LangRef hasn’t been clear on the semantics of partially overlapping
concurrent atomics in LLVM IR (specifically: a set of accesses marked as
atomic that would be in a data race if they weren’t atomic and not all of
them access the exact same set of bytes).

What loads read is defined in terms of individual bytes, but the memory ordering
constraints are formulated closely to the C/C++ (and Java for unordered)
memory model, where partially overlapping atomics are not possible. It’s not
obvious how concepts like C/C++'s per-location total modification order for
monotonic accesses map to accesses that can partially overlap. While C/C++
relies on the modification order to ensure that atomics cannot tear (i.e.,
atomic reads return bytes from two or more atomic writes), our IR semantics (as
written) currently does not guarantee this in the presence of partially
overlapping accesses.

Proposed Solution

PR #204329 proposes a solution to this problem: It specifies that concurrent
overlapping atomics must access the exact same set of bytes to act atomically.
If they don’t, they form a data race (i.e., participating loads read undef for
affected bytes). This empowers the rest of the specification to imply that
monotonic (or stronger) accesses do not tear. The PR also adds a constraint to
ensure non-tearing for unordered atomic accesses.

Impact on the Project

This assumption is already implicitly baked into the compiler-rt implementation
of the __atomic_load/__atomic_store functions for the typical libcall
lowering for too-wide or misaligned atomic accesses: Before the actual access,
it only locks a lock that is derived from the start byte of the accessed memory
region. If the access crosses a cache-line boundary, this lock does not protect
from interfering partially overlapping atomics that don’t start in the same
cache line.

The proposed semantics implies that transformations that merge adjacent atomic
loads/stores into wider atomic loads/stores are generally incorrect.

Without the requirement that concurrent atomics must access exactly the same or
entirely different bytes, formulating what atomicity, modification orders,
sequential consistency, etc. mean in LLVM IR would become a lot more complicated
(and an open research problem as far as I’m aware).

Open Questions

I’d be interested to hear if this constraint has been implicitly assumed to hold
by the community, or if partially overlapping atomic accesses are assumed to be
well-defined and act atomically.

For awareness: @nhaehnle @ssahasra @Pierre-vh @nikic @jyknight @gonzalobg @efriedma-quic @RalfJung

[RFC] Add elementwise modifier to atomic loads and stores
2

From the Rust perspective, at least some mixed-size atomic accesses must be well-defined, see What about: mixed-size atomic accesses · Issue #345 · rust-lang/unsafe-code-guidelines · GitHub for context. I believe that your proposed LangRef wording still allows this, because the wording change is after the “may see exactly one write” case.

However, I think there is generally a lot of interest to fully support mixed-size atomic accesses in Rust, esp. when it comes to supporting communication across an untrusted boundary, because it’s not possible to control which atomic accesses happen on the other side of the bounary.

An especially important case here would be support mixing of bytewise atomic memcpy with (non-bytewise) atomic accesses of arbitrary size.

So I think this proposal is going in the opposite direction of what we want (which would be proper formalization of mixed-size atomic accesses in the memory model).

3

Thanks, that’s an interesting data point! I agree that my proposal should be compatible with what Ralf proposed in this issue.

Are we sure that anyone implements this correctly and/or that there generally exist (efficient) implementations of this?
As I’ve mentioned in the original post, I think the compiler-rt implementation of __atomic_load/__atomic_store is incorrect if partially overlapping atomics are well-defined.
GCC’s libatomic seems closer to implementing this “correctly” (they lock all the locks for the relevant addresses, see the libat_lock_n (mptr, n); call with the size n in the __atomic_store implementation here), but, as far as I can see, that implementation has to rely on strong implicit assumptions on how memcpy is implemented to interact properly with atomics that the compiler implements with the lock-free fast path. If memcpy was implemented as a simple bytewise loop, such an access could still tear.

4

For Rust specifically, libatomic implementations don’t matter at all, because it requires all atomic operations to be lock-free.

But even beyond that, I believe that what compiler-rt does is fine as long as atomic accesses are aligned to at least the size of the access. In Rust this is a hard requirement. I believe we also at least warn on misaligned atomic accesses in C, but I’m not familiar with what the exact requirements/guarantees in that area are.

Unless I’m missing something, the implementation in compiler-rt would already be incorrect for misaligned atomic accesses, even without any mixed-size atomic accesses being involved. Edit: Thinking about this again, I was wrong about this. If there are no mixed-size accesses, then locking just the lock for the start address is fine…

5

Then there are limits to the maximal size of atomic accesses, right? There won’t be many processors able to support e.g., 1024B atomic accesses without locks.

Yes, I think the compiler-rt implementation is wrong for misaligned accesses of the same size (which would also be a data race in the proposal).
But I think it is also wrong for aligned accesses of different sizes: Say we have an atomic access A that stores 4*N bytes to a 4*N-bytes-aligned address p (for some N) and an atomic access B that stores N bytes to the address p+N (which is N-bytes-aligned).
If N is large enough so that p+N has a different lock than p (at least 16 bytes in the implementation), they use different locks.

6

Yes. The maximum atomic size is platform dependent (and can be zero). In practice, the maximum size is at most 16 bytes.

Yes, for atomics > 16 bytes this is an issue, given the 16 byte lock granularity.

7

FWIW, we document in the Atomics doc that the generic __atomic_store/__atomic_load “can be called with data of any size or alignment”.
I suppose documenting a size upper bound would be a way towards making it correct.

8

Limits are okay, but if they are going to exist, please make them uniform across every architecture. Encoding limitations of the current hardware target in the implementation of the abstraction layer makes things unnecessarily messy for front-end authors, who now need to have tables to figure out when the backend does the operation incorrectly to work around it. It also makes things unnecessarily slow, by forbidding upgrading locks to intrinsics when running on newer processors: GCC explains this in their reasoning for why they created these routines originally: it allows the same code to run correctly and always at the optimal speed regardless of whether the current processor requires a lock or has an intrinsic form for that instruction: https://gcc.gnu.org/wiki/Atomic/GCCMM/LIbrary

Requiring that the front-end only be able to express an operation when the back-end can use an intrinsic is conversely to also force the front-end to only be able to express the operation using a lock on all processors even if the back-end could have been using an intrinsic for modern processors.

9

Another interesting point for this discussion from the GCC docs you’ve shared:

Since lock-free and locked versions cannot be utilized simultaneously on any particular object, the compiler must consistently produce either a library call or lock free instructions for atomic operations on any specific object.

I don’t think we ensure that for mixed size atomics (we’d need to always lower atomics to libcalls unless alias analysis can show that the access cannot alias with one that requires locks), so defining those cases not as a data race means that we break this libatomic library interface.

10

Thank you Fabian for working on this.

I see PR #204329 as a clarification of what I think is the status quo. I’d expect others to disagree with what the status quo is, which is why we should figure out a way to clarify what it is.

I agree with @nikic that we’d probably need to extend the llvm ir memory model to support mixed-size accesses (at least for lock-free accesses).

11

copying from what I wrote on the Rust Zulip thread on this:
one of the main things I’d want from a mixed-size model is that if you do an atomic (volatile?) read on shared memory that some adversarial process is writing to you get valid bytes – not poison or undef.

it’d also be nice to have atomic reads consistently return bytes from the most recent store to those bytes for some DAG-shaped definition of recent, so if you atomicly write a u64, you can atomicly read smaller parts of it and get the values from only one write, no tearing. also if you atomicly read a u64 where there are atomic writes to each 32-bit half, you get at least the equivalent of two 32-bit atomic reads

iirc the linux kernel depends on mixed-size atomics working

12

From the rust conversation that @nikic quoted:

  • it is allowed to do differently-sized atomic accesses to the same location over time,
  • but only if any two not-perfectly-overlapping accesses are completely synchronized through other means (i.e., it is not these accesses themselves that add a happens-before edge, there already exists a happens-before edge through other accesses).
  • Any other kind of mixed-size access is UB.

I seem to be missing something here. If a synchronization (or a happens-before) edge is required anyway, then why is this talking about atomicity at all? Clearly those operations are not concurrent and behave no differently from non-atomic operations don’t need any additional promises compared to non-atomic operations?

In both these cases, the concern seems to be an untrusted/adversarial process concurrently writing to the same location. But atomicity is a contract between two processes, where they both have to honour it. Calling it morally strong in the PTX memory model was not entirely a tongue-in-cheek choice. So what am I missing here? Why should atomics somehow protect against adversarial actions?

13

afaict what they meant is that you can have your program operate in phases, like so:
https://play.rust-lang.org/?version=nightly&mode=debug&edition=2024&gist=72a6b0b63d6252da9b5fdc12de9d533e

#![feature(atomic_from_mut)]
use std::sync::atomic::*;

fn run_across_threads<F: Fn() + Sync>(f: F) {
    std::thread::scope(|s| {
        for _ in 0..4 {
            // spawn 4 threads
            s.spawn(|| f());
        }
        // wait for all 4 threads to complete
    });
}

union U {
    a32: [u32; 2],
    a64: u64,
}

#[unsafe(no_mangle)]
pub fn demo() {
    let mut u = U { a64: 0 };
    // use u as a 64-bit atomic
    {
        let a64: &mut u64 = unsafe { &mut u.a64 };
        let a64: &AtomicU64 = AtomicU64::from_mut(a64);
        run_across_threads(|| {
            a64.fetch_add(1, Ordering::Relaxed);
        });
        // run_across_threads synchronizes before returning
        assert!(4 == a64.load(Ordering::Relaxed));
    }
    // use u as 2 32-bit atomics
    {
        u.a32 = [0, 4];
        let a32: &mut [u32; 2] = unsafe { &mut u.a32 };
        let a32: [&mut u32; 2] = a32.each_mut();
        let a32: [&AtomicU32; 2] = a32.map(|v| &*AtomicU32::from_mut(v));
        run_across_threads(|| {
            a32[0].fetch_add(1, Ordering::Relaxed);
            a32[1].fetch_sub(1, Ordering::Relaxed);
        });
        // run_across_threads synchronizes before returning
        assert!(4 == a32[0].load(Ordering::Relaxed));
        assert!(0 == a32[1].load(Ordering::Relaxed));
    }
}

#[test]
fn test_demo() {
    demo();
}
14

because data races between atomics are allowed without giving UB, so we can treat the adversarial process as doing a bunch of atomic operations to the shared memory since all their non-atomic loads/stores use the same HW-level operations as relaxed atomics.

15

… except if both accesses are a read! Then the accesses are permitted.

1 Like