Atomic operations and data races

3.3 Indivisible: atomic operations and data races

The smallest thing two threads can share safely is one value that neither of them ever sees half written. That property is atomicity. This section covers the instructions that provide it, what they cost, and the rule Rust builds on top of them.

Loads and stores that cannot tear

A load or store is atomic when no other thread can observe it half done: a reader sees the whole old value or the whole new one, never a mixture. On x86-64 and AArch64 an aligned load or store of 1, 2, 4 or 8 bytes is atomic in hardware, because an aligned value of that size never crosses a line and the cache moves it in one piece. A 16-byte struct is written by two stores, and a reader that runs between them sees half of each. A value that straddles two lines can be torn the same way.

Rust’s atomic types, AtomicBool, AtomicU32, AtomicU64, AtomicPtr and the rest, guarantee the alignment. Every access through them takes an ordering argument, which says what else the access keeps in order. With Relaxed, the weakest ordering, atomicity and nothing more (the other orderings come later), load and store compile to the ordinary mov on x86-64 and the ordinary ldr and str on AArch64. Stronger orderings can change the instruction: on AArch64 an ordered load or store becomes ldar or stlr, and on x86-64 the strictest kind of store becomes xchg. What the type always changes is the compiler’s behaviour. The compiler must preserve the memory model’s permitted observable behaviour; atomicity does not require every source access to become a separate machine instruction. In particular, do not use an assumed one-to-one mapping as a benchmark guarantee.

Read-modify-write

Most sharing needs more than a load or a store. Incrementing a shared counter takes three steps, load the value, add one, store the result, and two threads doing it at once can interleave:

A read-modify-write (RMW) instruction does all three steps as one, with no other core able to act between them. On x86-64 it is an ordinary instruction with a lock prefix: lock add, lock xadd, lock cmpxchg; xchg with a memory operand is locked without the prefix. The core first waits for its store buffer to empty. Then it makes the line one the core owns, holding the only copy, and refuses to hand it to any other core until the instruction has read, changed and written it. Because of that first step, every locked instruction is also a full barrier: no load or store crosses it in either direction.

AArch64 has two ways. The original is a pair of instructions, load-exclusive and store-exclusive (ldxr and stxr). The load marks the line in a per-core monitor, and the store succeeds only if no other core wrote the line in between, so an RMW is a loop that retries until the store succeeds: load-linked, store-conditional, or LL/SC. Since Armv8.1 the Large System Extensions (LSE) add single instructions, ldadd, swp and cas, which the cache system carries out, on some designs at the shared cache rather than in the core.

Rust exposes the RMWs as methods on the atomic types: fetch_add, fetch_sub, fetch_and, fetch_or, fetch_xor, fetch_max, fetch_min and swap, each returning the value it replaced. Each takes the same ordering argument as a load or a store, and nothing in this section depends on which one.

Compare-and-swap

One RMW is general enough to build all the others: compare-and-swap (CAS). It takes an expected value and a new one, and in one indivisible step it writes the new value only if the current value equals the expected one, reporting which happened. In Rust it is compare_exchange(expected, new, success_ordering, failure_ordering), which returns Ok(previous) if it wrote and Err(actual) if it found something else. On x86-64 it is lock cmpxchg; on AArch64 it is cas with LSE, or an LL/SC loop without. compare_exchange_weak is allowed to fail even when the value matched, which an LL/SC loop occasionally does, and it is the cheaper choice inside a loop that retries anyway. A lock is a CAS from free to taken. A lock-free stack uses CAS on its top, together with a protocol for safe node access and reuse. And fetch_max on x86, which has no instruction for it, is a CAS in a loop.

Data races, and why Rust refuses them

A data race is two threads accessing the same location at the same time, at least one of them writing, at least one of them with an ordinary non-atomic access, and nothing in the program ordering the two. An unsynchronised increment on ordinary memory is one. Separate atomic load/store increments can also lose updates, but that is a logical race rather than a data race. The real damage is worse than a lost update, because the compiler assumes data races never happen. It optimises each thread as if no other thread could see or change its non-atomic memory: it keeps values in registers, merges and reorders stores, and may read a value twice and get two answers. So C, C++ and Rust all make a data race undefined behaviour. A program that contains one means nothing at all, and no particular wrong answer is promised.

Rust goes further: without unsafe, a data race cannot be written. Three rules do it. A &mut T is exclusive, and conflicting accesses must respect that exclusivity, including while the borrow is reborrowed. A &T is shared and read-only, unless the type is built on UnsafeCell, the one primitive through which memory reached by a shared reference may be changed; the atomic types, Mutex and Cell all wrap one. And two marker traits govern threads. A type is Send if a value of it may move to another thread, and Sync if a shared reference to it may be used from several threads at once. Cell and RefCell change their contents through & without any synchronisation, so they are not Sync; the atomic types are Sync, and Mutex<T> is Sync when T: Send. The compiler enforces these bounds; unsafe implementations must uphold them.

unsafe code can still race, through raw pointers or an UnsafeCell reached from two threads. That is where lock-free structures live, and there the guarantee passes from the compiler to the programmer.

What it costs

On a line the core already owns, a locked RMW takes about 20 cycles on recent Intel cores and fewer on AMD’s: about 5 ns, against about 1 ns for a plain store. Two things add to that. The first is the store-buffer drain. If the buffer holds stores still waiting for their lines, the RMW waits for all of them, so its cost depends on the stores before it, up to a full line transfer or a DRAM miss. The second is the line itself. If another core wrote it last, the RMW waits for it to cross: 50–100 ns on one socket. On AArch64 an LSE atomic costs a similar handful of nanoseconds; an LL/SC loop costs the same when nobody interferes and repeats when somebody does. On x86 the price is the same whatever ordering the source asks for, because the lock prefix already orders everything.

Worked example: one order-id counter, two strategies

Two strategy threads, pinned to cores 2 and 3, send orders through one gateway. Every order needs a client order id that is unique for the session, and the exchange rejects a duplicate. The ids come from one shared counter. The broken version uses let id = next_id.load(Relaxed); next_id.store(id + 1, Relaxed);.

Each access is atomic, and the pair is not. When one market move wakes both strategies, both can load the same id, both send it, and the second order is rejected. let id = next_id.fetch_add(1, Relaxed); makes the pair one step: every call gets a different id until integer wraparound. The session must end or allocate a new namespace before ids repeat.

The cost depends on which thread drew last. A strategy drawing ids in a run, with the line in its own L1, pays about 5 ns an id. When the two strategies alternate, each fetch_add finds the line in the other core and waits for it: 50–100 ns an id, a tenth of the budget, for one integer. They alternate most at exactly the moments that matter, because a market move wakes both. And an order is not one value: an id, a price and a quantity are three, and atomicity says nothing about the order in which another thread sees them.

Seeing it

cargo asm, from the cargo-show-asm crate, prints the assembly of one function, and on a stock x86 box a function that calls fetch_add shows lock xadd (lock add if the result is unused), compare_exchange shows lock cmpxchg, and the Relaxed and SeqCst versions of each are the same instruction. Built for aarch64-unknown-linux-gnu, the same functions call small helpers such as __aarch64_ldadd8_relax, which pick LSE or LL/SC when the program starts; on an ARM box, grep -m1 -o atomics /proc/cpuinfo printing atomics says the LSE instructions are there to be picked. On Intel cores, perf stat -e mem_inst_retired.lock_loads counts the locked instructions a program retired, and a thread that does one RMW per message shows one per message. That count times 5 ns is the floor; every one that found its line on another core cost a transfer, 50–100 ns, instead, and how many did is set by how the threads were interleaved, not by the code.