Understand C11 Memory Ordering: relaxed, acquire, release, seq_cst

Topic Overview

Atomics and Happens-Before

C11 stdatomic.h and C++ std::atomic expose memory_order_relaxed, acquire, release, and seq_cst. Lock-free stacks, queues, and reference counts rely on pairing release stores with acquire loads so published data is visible without mutex overhead. Getting ordering wrong produces bugs that reproduce only on ARM or under load.

Orders You Actually Need

relaxed for pure counters. release after writing payload, acquire before reading it. seq_cst is the safe default when learning; tighten later for performance.

cCopy
Loading…

• Data races on non-atomic fields remain undefined even with fences
• atomic_thread_fence is rarely needed when every access uses atomics
• x86 TSO is stronger than ARM; code that works on Intel may break on Apple silicon
• Use ThreadSanitizer when possible

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will implement a flag synchronization pattern using acquire/release atomics. This exercise asks you to publish a struct pointer safely without a mutex.

Your Task

Litmus tests are tiny multi-threaded programs used to pin down exactly what a memory model allows. Write a checker that enumerates every outcome of a litmus test under three models: sequential consistency (sc), x86 tso, and a relaxed model with C11-style acquire/release and fences. Use it to see why store buffering needs a fence on x86, and why message passing needs release/acquire on weakly ordered CPUs.

Input

cCopy
Loading…

Operations: W x v (store), Wrel x v (release store), Wsc x v, R x r (load into register r), Racq x r (acquire load), Rsc x r, and F (full fence). Memory starts at 0. Register names are global to the test.

Model

An execution is an interleaving of all operations in which each load reads the latest store to its location (memory is multi-copy atomic). Within a thread, a later operation B may execute before an earlier operation A only if the model permits reordering the pair:

• sc: never.
• Any model: never across an F between them, and never for two accesses to the same location.
• tso: only a store followed by a load (store→load), and neither is sc.
• relaxed: any pair, unless both are sc, A is an acquire load (nothing moves above it), or B is a release store (nothing moves below it).

Enumerate every execution that respects the pairs that must stay ordered, and collect the distinct final register values.

Output

cCopy
Loading…

• Outcomes are sorted by register values in order of first appearance, and each lists every register.
• check echoes its arguments exactly as typed.
• Errors: bad operation: TEXT, thread: at most 4 threads, thread: at most 8 operations in total, model: sc, tso or relaxed, check: unknown register, and check: run a model first.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Enumerate exhaustively (a DFS over "which ready operation runs next"). Random sampling misses rare outcomes.
2. Express each model only as a "may these two operations reorder?" predicate, and share all the other machinery.

Hidden tests cover message passing under tso and relaxed with and without release/acquire, load buffering, IRIW with plain and acquire loads, sc operations, fences in relaxed mode, and malformed operations.