Memory Ordering in Rust

Memory Orderings in Rust

In concurrent programming, memory orderings define how threads perceive and interact with shared memory operations. Modern CPUs and compilers optimize memory accesses aggressively, often reordering them to improve performance. Rust provides fine-grained control over these interactions through the std::sync::atomic::Ordering enum.

Memory Model and CPU Guarantees

CPUs provide varying guarantees on memory ordering, ranging from weak to strongly ordered models. Most modern desktop CPUs (e.g., x86-64) follow strong ordering, but this behavior isn’t universal. Rust abstracts over hardware differences, implementing the C++20 memory model for atomics to ensure portable, predictable behavior across architectures.

The core concept is happens-before relationships, ensuring that specific operations on one thread are visible to other threads in a defined order.

The std::sync::atomic::Ordering Enum

Rust’s atomic operations provide five levels of memory ordering to manage synchronization and visibility across threads:

• Relaxed
• Acquire
• Release
• Acquire-Release (AcqRel)
• Sequentially Consistent (SeqCst)

Relaxed

Relaxed ordering ensures atomicity but makes no guarantees about the ordering of memory operations between threads. It is ideal for operations where only the value matters, not the order in which threads see changes.

use std::sync::atomic::{AtomicUsize, Ordering};
 
let counter = AtomicUsize::new(0);
 
// Multiple threads increment the counter without synchronization
std::thread::spawn(|| {
    counter.fetch_add(1, Ordering::Relaxed);
});

In this example, the counter increments atomically, but the visibility of these increments across threads is undefined.

Acquire and Release

Acquire and Release establish ordering guarantees for shared memory:

• Acquire ensures that all writes by other threads before a Release are visible to the acquiring thread.
• Release ensures that all writes by the releasing thread become visible to threads performing subsequent Acquire operations.

Example: Producer-Consumer with Acquire and Release

use std::sync::atomic::{AtomicUsize, Ordering};
use std::thread;
 
static FLAG: AtomicUsize = AtomicUsize::new(0);
static DATA: AtomicUsize = AtomicUsize::new(0);
 
fn main() {
    // Producer thread
    let producer = thread::spawn(|| {
        DATA.store(42, Ordering::Relaxed);
        FLAG.store(1, Ordering::Release); // Marks data as ready
    });
 
    // Consumer thread
    let consumer = thread::spawn(|| {
        while FLAG.load(Ordering::Acquire) == 0 {} // Wait for data
        println!("DATA: {}", DATA.load(Ordering::Relaxed)); // Guaranteed to see 42
    });
 
    producer.join().unwrap();
    consumer.join().unwrap();
}

Here, the Release on FLAG ensures that the write to DATA is visible to the consumer after the Acquire on FLAG.

Acquire-Release (AcqRel)

Acquire-Release combines the guarantees of Acquire and Release, enabling bidirectional synchronization. This is essential in operations like fetch-and-add, where both reading and writing shared memory are involved.

use std::sync::atomic::{AtomicUsize, Ordering};
 
let counter = AtomicUsize::new(0);
 
// Thread A
counter.fetch_add(1, Ordering::AcqRel); // Ensures updates are visible in both directions

Sequentially Consistent (SeqCst)

SeqCst provides the strongest guarantees, ensuring a single global order for all atomic operations across all threads. It is the simplest to reason about but comes with a performance cost.

use std::sync::atomic::{AtomicBool, Ordering};
 
let flag = AtomicBool::new(false);
 
let handle = std::thread::spawn(|| {
    while !flag.load(Ordering::SeqCst) {}
    println!("Flag set!");
});
 
flag.store(true, Ordering::SeqCst);
handle.join().unwrap();

SeqCst ensures that all threads observe operations in the same order.

Why Relaxed Operations Don’t Synchronize

Relaxed operations don’t create happens-before relationships. For example, in a producer-consumer model, a Relaxed load may see the flag updated but not the associated data, leading to undefined behavior.

Lock-Free Queue Example

A common use case for Acquire-Release is in implementing lock-free data structures, such as a single-producer, single-consumer queue.

use std::sync::atomic::{AtomicPtr, Ordering};
use std::ptr;
 
struct Node {
    value: usize,
    next: AtomicPtr<Node>,
}
 
struct Queue {
    tail: AtomicPtr<Node>,
}
 
impl Queue {
    fn enqueue(&self, new_node: *mut Node) {
        unsafe {
            new_node.as_ref().unwrap().next.store(ptr::null_mut(), Ordering::Relaxed);
            let prev_tail = self.tail.swap(new_node, Ordering::AcqRel);
            prev_tail.as_ref().unwrap().next.store(new_node, Ordering::Release);
        }
    }
}

In this example:

• Relaxed initializes next without ordering requirements.
• AcqRel ensures the tail pointer is correctly updated in both directions.
• Release ensures subsequent consumers see the correct next pointer.

Summary of Guarantees

• Relaxed: Atomicity only, no ordering guarantees.
• Acquire: Synchronizes reads; ensures visibility of prior writes.
• Release: Synchronizes writes; ensures visibility to subsequent reads.
• AcqRel: Combines Acquire and Release for bidirectional synchronization.
• SeqCst: Enforces a single, global order across all threads.