How do Release & Acquire memory ordering actually work?

help
1

I’ve been digging into the documentation for Rust's Atomic types at Rust Atomics and Locks by Mara Bos, but I’m still struggling to wrap my head around how Acquire and Release ordering actually works.

I have a few specific points of confusion that I’m trying to clear up:

  • Do they always come in pairs? Must Acquire and Release always be used together, or can I just use one at the end of a sequence?
  • Does the order matter for preceding operations? If I use Acquire for the final load, does it matter what ordering I used for the operations that came before it?
  • What about Relaxed? Can I use Relaxed for the preceding operations as long as the final operation uses Acquire?

My current mental model is that as long as the final load uses Acquire, the previous operations don't strictly need to be synchronized. I assume Relaxed provides just enough logic to ensure the threads are running, but it doesn't guarantee the same memory visibility.
Honestly, I’m still not entirely sure how this flows in practice.

use std::sync::atomic::{AtomicBool, AtomicU64, Ordering::{Acquire, Relaxed, Release}};
use std::thread;

static VALUE: AtomicU64 = AtomicU64::new(0);
static READY: AtomicBool = AtomicBool::new(false);

fn main() {
    thread::spawn(|| {
        VALUE.store(42, Relaxed);   // We use Relaxed here because we don't care about memory ordering for this value, and it's more performant. Since it's not a flag, Relaxed is sufficient.
        READY.store(true, Release); // This is our final write. We use Release to ensure that the other thread sees the previous store to VALUE.
    });

    while !READY.load(Acquire) {}   // Since this is the first load from a different thread, we use Acquire. This ensures that subsequent reads in this thread will see the correct values, even those marked as Relaxed.
    println!("{}", VALUE.load(Relaxed)); // This is guaranteed to be 42.
}

Here are my thoughts:

  • I understand that Release only affects subsequent Acquire operations (whether in the same thread or a different thread, as long as they synchronize on the same atomic variable).
  • Acquire affects the local thread where it is called. Once we load the READY flag with Acquire, the memory synchronization is established. For subsequent loads in this thread, even if they target a different atomic value, we don't necessarily need another Acquire because the happens-before relationship is already set.
    Am I correct ?
2

Your questions are rather general, it is hard to answer them without seeing the specific code.

Regarding a "mental model", Acquire means the thread is going to be reading shared data and needs to see writes from another thread, can also be read as acquiring a lock. Release means the thread has finished writing shared data, and writes need to be flushed so another thread sees them. It also needs to be understood that the synchronisation applies to a specific atomic variable, but that usually comes quite naturally.

3

Mara Bos' excellent book Rust Atomics and Locks has a whole chapter on it.

4

You need to think in terms of happens-before relationships.

  • All operations on a single thread happen-before each other intuitively, even in the presence of signals
  • Different threads have to synchronize. Both of them have their local chains of already synchronized operations, thus one point is enough to say: "all those operations happen before all those operations"
  • No, Release and Acquire don't come in pairs. There can be SeqCst or AcqRel too. Also, several Aquire operations can synchronize with one Release.

If I use Acquire for the final load, does it matter what ordering I used for the operations that came before it?

You should synchronize during or before the first load. Because this load will happen-before other loads, as they are on the same threads. If you'll synchronize only the last one, all previous ones will get garbage.

Can I use Relaxed for the preceding operations as long as the final operation uses Acquire

No, but you can do it the other way around: Acquire goes first, not as final

Your code is technically correct, but it can be improved:

use std::sync::atomic::{AtomicBool, AtomicU64, Ordering::{Acquire, Relaxed, Release}, fence};
use std::thread;

static VALUE: AtomicU64 = AtomicU64::new(0);
static READY: AtomicBool = AtomicBool::new(false);

fn main() {
    thread::spawn(|| {
        VALUE.store(42, Relaxed);   // We use Relaxed here because we don't care about memory ordering for this value, and it's more performant. Since it's not a flag, Relaxed is sufficient.
        READY.store(true, Release); // This is our final write. We use Release to ensure that the other thread sees the previous store to VALUE.
    });

    while !READY.load(Relaxed) {}  // Each atomic variable is sequentially consistent, we can load it with Relaxed 
    fence(Aquire); // Once we know that the thread is finished, establish a happens-before relationship.
    println!("{}", VALUE.load(Relaxed)); // This is guaranteed to be 42.
}

Btw, while I can explain Acquire and Release, I don't really get SeqCst and every sourse I see just handwaved it, including Mara's book. :sweat_smile:

5

Different threads have to synchronize. Both of them have their local chains of already synchronized operations, thus one point is enough to say: "all those operations happen before all those operations"

Except that is not actually quite true. Let's assume we have thread A and thread B. Thread A writes to two different memory locations after each other, let's say location 1 and then location 2. What can now happen is that thread B observes a write to location 2 before it observes the write to location 1.

(At least on non-TSO memory models, such as SPARC PSO or ARM, not on x86-64 since it uses TSO)

If I have time a bit later I'll add a conceptual explanation how this "works in hardware" ( at least as a mental model and what is observable, we of course don't have the exact hardware implementation the vendors use ).

6

I'm not sure how this is related to the quote. I only meant this:

A: op_a_1, op_a_2, op_a_3, op_a_4, op_a_5
B: op_b_1, op_b_2, op_b_3, op_b_4, op_b_5

Assume op_b_3 synchronized with op_a_3, so op_a_3 happens before op_b_3 . After this point op_b_4 and op_b_5 can be sure about op_a_1 sbd op_a_2, as well as their order.

Is this contradicting your statement somehow?

7

If you actually want to understand how - and, perhaps even more importantly, why - it works, you'll have to do your own research on 1) cache coherence protocols; 2) MESI in particular, which is the standard implemented across the board in all of the modern ISA's, albeit with manufacturer-specific variations/extensions: MESIF for Intel / MOESI for AMD; 3) store buffers; 4) invalidation queues; 5) out-of-order execution; 6) memory barriers/fences; and if you insist on digging even deeper still by that point: 7) compiler and/or language-specific memory model, abstracting away all of the above.

I'd love to be able to point out a single piece resource out there that doesn't shy away from blending together the language-specific "write X to get Y" passages alongside the hardware-specific machinery that makes it all possible, myself; yet I am yet to discover any that would come anywhere close.

On the other hand, if the idea of doing your own deep dive into all of the points listed previously doesn't spark nearly as much joy as the idea of simply knowing and/or remembering when/where you should be tagging/fencing any given atomic operation with an Acquire/Release label, you might want to finish Mara's book first. Some of the questions you've brought up are addressed multiple times in the book, and if you didn't pay much attention while skimming through it, it's quite unlikely that anyone replying to you here will be able to clarify things any further still.

Don't beat yourself up if it doesn't "click" for you immediately, though. It is quite a convoluted topic, way too often presented in an even more convoluted manner, in no small part thanks to all of the exceedingly convoluted abstractions, abstracting away even their own attempts at abstraction. "Fence X on thread A establishes a 'happens-before' relationship with the fence Y on thread B if and only if ..." is not quite what our brains have evolved to handle over the last few million years.

Give yourself some time, and some ample room for experiments. Start with a bad-very-bad-never-do-this-ever-bad static mut data race, and gradually build it up to the point where you can see what your Release / Acquire semantics do for you; instead of trying to reverse-engineer some compiler-lover's thesis on safe memory modelling in modern system-level languages, hastily crammed into barely a handful of lines in the documentation.

8

The distinction is around observed sequences of operations.

With all orderings other than SeqCst, each atomic has a sequence of operations on it that all threads agree upon, but two threads can disagree on the ordering of a pair of atomics.

For example, if you have two atomics, A and B, both initialized to 0, and thread 1 does Release stores of 1 then 2 to atomic A, while thread 2 does Release stores of 3 then 4 to atomic B, all threads will agree that atomic A took on values 0, 1 and then 2 in sequence (noting that they might skip some entries in this sequence - you might only ever see 2, but you'll never see 1 then 0 then 2), while atomic B took on values 0, 3 and 4 in sequence (again, noting the possibility of skipping values but not reordering). But, it's possible for one thread doing Acquire loads of A and B to see the combined set being:

A B
0 0
1 0
2 0
2 3
2 4

while another thread doing Acquire loads sees:

A B
0 0
0 3
1 3
1 4
2 4

Both of these are consistent with the orderings defined by thread 1 and thread 2's Release stores (if you go down a column, you never see the atomic go "backwards" in the sequence), but it's possible for two threads to disagree on what pairs of values can be observed; you could have one thread see (A, B) = (2, 0), while another thread can never see (A, B) = (2, 0), but can see (A, B) = (1, 4), which is impossible to observe on a thread that's already observed (A, B) = (2, 0).

SeqCst requires that there's only one sequence of SeqCst writes that all threads using SeqCst reads agree on (in addition to all SeqCst writes being Releases and all SeqCst reads being Acquires); if you changed from Release stores and Acquire loads to SeqCst for both, only one of those tables could possibly be valid, and thus you know that if you're seeing (A, B) = (1, 4), another thread that does a SeqCst load cannot observe (A, B) = (2, 0) or (A, B) = (2, 3) (since that would mean that the other thread is observing a different sequence of writes to you).

This is rarely valuable in practice; reasoning about the state of threads based on a single atomic is tricky enough, without trying to reason about the state of threads based on multiple atomics at once - and, in fact, while writing this post, I've had to take quite a lot of care to not accidentally assert something false.

Edit: And that last sentence was prophetic. I didn't write something false per-se, but I made a statement that was overconstrained - it's not just that a thread that reads (A, B) = (1 , 4) can be certain that no thread after it can read (A, B) = (2, 0), but the stronger statement that if I can read (A, B) = (1, 4), no thread can read or have read (A, B) = (2, 0), nor can a thread read or have read (A, B) = (2, 3).

9

Under this assumption your logic works, yes.

However imagine if they didn't synchronize (as in, you didn't use Acquire-Release semantics for the two operations, but instead Relaxed!), and assume that op_b_3 managed to observe the result of op_a_3 (using relaxed semantics). You might think this implies it executed after op_a_3, but it is not actually guaranteed to see the result of op_a_1 or op_a_2 since no happens-before relation was created between them.

10

And as an aside; my edit is the underlying problem with "use SeqCst unless you know weaker works" as a default position. The guarantee SeqCst provides is surprisingly far-reaching, and even when I'm thinking about it, I find it hard to get it completely right - my mistake was, thankfully, harmless, but still a mistake that could have suppressed desirable optimizations (e.g. I've seen loop-invariant code motion suppressed by SeqCst when Relaxed would have been plenty good enough for the use case - just reading an AtomicBool to see if we should do another iteration or end early and clean up).

11

It is a great canary in code. If I see SeqCst in a code review it almost certainly means the author doesn't know what they are doing, and I need to be extra careful. :laughing:

In fact I have never seen a legitimate use case for it, though I believe there is one published algorithm that supposedly needs it.

12

Note that it's not only about hardware, IIUC the compiler also may reorder relaxed writes in thread A if it's able to prove that the order is not observed in this thread, so even on x86 you may see write 2 before write 1.

13

I've had precisely one use case for it. Taking code that used vector clocks over the network, and changing it so that each node in the system was multithreaded, rather than single-threaded.

Lots of the codebase already had assumptions that the vector clock could not go backwards, only forwards (when it receives an updated vector clock from another node, or when a node updates its element of the vector clock), and it was a lot easier to handle this by using SeqCst to get the global guarantee than it would have been to audit all the existing single-threaded code to confirm that nothing would go wrong if code in a node seeing the other nodes at clock (1, 2, 3, 4, 5, …) assumed that no other code running on this node could see (2, 1, 3, 4, 5, …).

Had I had a lot more time, the audit would have been the better move, but legacy code is a pain to audit and fix, and time pressures win out.

14

AFAIK code with fetch_add(1, Relaxed) is also guaranteed to observe monotonically rising counter, so I think you just confirmed the @Vorpal's point. "I did not bother with a proper model of my system" is hardly a "legitimate use case" for SeqCst.

15

I think you misunderstand the system (which I no longer have access to, so this is paraphrased). I had a vector clock, which is an array of values, not a single atomic (it's one value per node in the system). It looked a lot like the following in single-threaded Rust:

pub struct VectorClock<const NODES: usize> {
    my_index: usize,
    nodes: [u64; NODES],
}

impl<const NODES: usize> VectorClock<NODES> {
    pub fn incoming_clock(&mut self, incoming_clock: &[u64; NODES]) {
        for (my_node, incoming_node) in self.nodes.iter_mut().zip(incoming_clock.nodes) {
            *my_node = (*my_node).max(incoming_node);
        }
    }

    pub fn time_has_passed(&mut self) -> u64 {
        self.nodes[self.my_index] += 1;
        self.local_time()
    }
    
    pub fn time_on_node(&self, node: usize) -> u64 {
        self.nodes[node]
    }

    pub fn local_time(&self) -> u64 {
        self.time_on_node(self.my_index)
    }
}

The problem I was facing is that the code I wanted to make multi-threaded assumed in a lot of places that it would be impossible for code on this node to see any element in the vector clock go backwards - clocks only go forwards. Putting it all inside an RwLock worked, but resulted in a lot of unwanted synchronization (and associated slow-down) whenever a packet arrived, because all the threads would have to wait until incoming_clock finished writing, even if they only wanted to call time_has_passed() or local_time().

It did, however, work just fine as long as there was a consistent global order; the solution was to change it to look more like:

pub struct VectorClock<const NODES: usize> {
    my_index: usize,
    nodes: [AtomicU64; NODES],
}

impl<const NODES: usize> VectorClock<NODES> {
    pub fn incoming_clock(&mut self, incoming_clock: &[u64; NODES]) {
        for (my_node, incoming_node) in self.nodes.iter_mut().zip(incoming_clock) {
            my_node.fetch_max(*incoming_node, Ordering::SeqCst);
        }
    }

    pub fn time_has_passed(&mut self) -> u64 {
        self.nodes[self.my_index].fetch_add(1, Ordering::SeqCst)
    }
    
    pub fn time_on_node(&self, node: usize) -> u64 {
        self.nodes[node].load(Ordering::SeqCst)
    }

    pub fn local_time(&self) -> u64 {
        self.time_on_node(self.my_index)
    }
}

This stopped the synchronization effect whenever a new clock arrived - yes, we still had the slowdown caused by atomics (they're not free), but we could profile to find code that was doing too much with the vector clock, and improve it, while separately doing a big push to remove the vector clock from places that didn't need it.

16

Depending on how often these change (I have only vaguely heard of vector clocks, not the domain I work in), I would suggest RCU, especially if you can have a single updater and many readers.

RCU (and hazard pointers to a lesser extent) is an underappreciated form of synchronization. The fastest synchronization is no synchronization after all. I can recommend Is Parallel Programming Hard, And, If So, What Can You Do About It? on this topic (specifically chapter 5 on how to count in parallel is a great eye opener to the various tradeoffs in parallelism). Do be warned it is written with a C[1] audience in mind.

  1. Linux kernel C even ↩︎

17

The system updated the clock every time anything read a packet with vector clock from a remote node, and many readers. We had to rule out RCU anyway because of the patent minefield that still existed around it at the time, but it probably wouldn't have helped a huge amount because of the number of required synchronization points that existed in the implementations of algorithms in use (since in a single-threaded setup, the synchronization points were "free" - they were a consequence of polling for incoming packets from other nodes, and not something you cared to minimize as a result).

Had I had time, I'd have audited the whole codebase to be sure that the synchronization was purely accidental, which would have allowed me to make the various algorithms work with deliberately taken snapshots of the vector clock (even less synchronization than RCU), instead of requiring synchronization every time it changed. At least in theory, assuming no-one did anything foolish, it should have been OK for each algorithm to produce output based on newer data than its vector clock says it could have had, but when the people writing the code were mostly not software people, assuming no-one did anything foolish is not a safe assumption (not that it'd have been that safe if they were software people, either).

18

Ah, if you have multiple writers, the problem is much harder. If this is updated often but only a single writer, a seqlock could also have been a really good fit when I think it over.

Multiple writers and updating often is a hard problem though.

19

Yeah - and the effort to fix it to only have one thread (at most) writing to the vector clock was equivalent to the effort of ensuring that the implementations cope fine with a possibly out-of-date snapshot of the vector clock (which is entirely feasible - none of the algorithms had a hard requirement that the clock was up to date, but some of the implementations took shortcuts based on that assumption).

As is so often the case when maintaining legacy codebases, you discover situations where someone made assumptions that were reasonable at the time, but aren't reasonable any more.