85 Operations that do not split — <stdatomic.h>

85.1 The lost update — confirmed with the eyes#

/* A race condition and an atomic operation — the same work counted twice. */
#include <stdatomic.h>
#include <stdio.h>
#include <threads.h>

#define THREADS 4
#define BUMPS   200000

static long        plain;   /* a plain long — unprotected */
static atomic_long safe;    /* an atomic long     */

static int worker(void *unused)
{
    (void)unused;
    for (int i = 0; i < BUMPS; i++) {
        plain = plain + 1;                    /* read-add-write: it comes apart */
        atomic_fetch_add(&safe, 1);           /* it happens as one lump      */
    }
    return 0;
}

int main(void)
{
    thrd_t t[THREADS];

    for (int i = 0; i < THREADS; i++)
        thrd_create(&t[i], worker, NULL);
    for (int i = 0; i < THREADS; i++)
        thrd_join(t[i], NULL);

    long expected = (long)THREADS * BUMPS;
    printf("expected   : %ld\n", expected);
    printf("unprotected: %ld%s\n", plain, plain == expected ? "" : "  <- counts were lost");
    printf("atomic     : %ld\n", (long)safe);

    printf("\nis atomic_long lock-free? %s\n",
           atomic_is_lock_free(&safe) ? "yes" : "no");
    return 0;
}

expected   : 800000
unprotected: 275764  <- counts were lost
atomic     : 800000

is atomic_long lock-free? yes

Four strands turned the same loop 200,000 times each. The expected value is 800,000, but the unprotected long did not even get near it. The vanished share differs on every run — and this non-determinism is precisely the character of this class of bug. A loss that does not reproduce.

The atomic variable’s side is exactly 800,000 every time. Because atomic_fetch_add performs “read-add-write” as one lump that cannot be split. The name atom means just that — that which is not split further.

85.2 Why volatile is not the answer#

In code that has long used C one often sees the practice of exchanging signals between strands with volatile int flag;. It is a wrong practice now. What volatile promises is one thing only — the compiler will not remove or merge these accesses. As will be seen in chapter 54, its purpose was hardware registers (places whose value changes from outside).

There are two things volatile does not promise. Atomicity — the x++ of a volatile long x; is still three steps and splits. And ordering and visibility — it does not prevent the CPU from changing the order of writes or from being late to show them to another core.

Summed up: volatile for hardware registers, atomic types or mutexes for sharing between strands. Java’s and C#‘s volatile share only the name and differ in meaning (there it really does guarantee visibility), so bringing the habits of those languages into C is a common passage to accidents.

85.3 Atomic types and operations#

Using them is simple. Attach _Atomic before the type, or use the names the header gives (atomic_int, atomic_long, atomic_bool, atomic_size_t …).

#include <stdatomic.h>
atomic_int  counter = 0;      /* = _Atomic int */
_Atomic long total;

The operations are called as functions (or macros of those names). Using the ordinary operators (++, +=) also behaves atomically, but the fact of being atomic is not visible in the code and so is easy for a reader to miss, which is why the explicit functions are recommended.

That fetch_add returns the previous value is a place often confused. To obtain “which number this is”, use the return value; to know “how much it is now”, it is the return value plus the increment, or a separate atomic_load — and the latter may change again in the meantime.

85.3.1 CAS — “if it is still what I saw, change it”#

An operation like fetch_add performs one fixed update. Real updates usually carry a condition: “raise it unless it would pass the limit”, “replace it if it is larger than the current value”, “move to the next state only from this one”. Each of those is three steps — read, decide, write — and someone can cut in between them.

Hence compare-and-swap (CAS). The idea fits in one sentence.

If the value I read is still there, change it. Otherwise change nothing and tell me.

In C it is atomic_compare_exchange_strong (and _weak), with this contract:

bool atomic_compare_exchange_strong(A *object, C *expected, C desired);

• If object’s current value equals *expected — it stores desired and returns true.
• If it differs — it changes nothing and returns false, but ★ writes the current value into *expected (§7.17.7.4 p3).

That second bullet shapes how the function is used. A failure hands you the fresh value, so there is no need to re-read before trying again — which is why CAS is almost always written as a loop.

int cur = atomic_load(&x);
int next;
do {
    next = f(cur);                                     /* any update rule at all */
} while (!atomic_compare_exchange_weak(&x, &cur, next));

★ Those five lines are why CAS is the universal tool. Whatever stands in for f — a conditional increment, a maximum, a state-machine transition — that update becomes atomic. Even fetch_add could be built this way; there is simply no reason to, when the hardware offers it directly.

That second row is precisely the “spurious failure” of the question below. The reservation is held on the location, not the value, so another core touching the same cache line — or a single interrupt — is enough to drop it.

if (atomic_load(&count) < LIMIT)      /* ① read and */
    atomic_fetch_add(&count, 1);      /* ② add — somebody cuts in between */

int cur = atomic_load(&count);
do {
    if (cur >= LIMIT) break;                 /* limit check and update as one lump */
} while (!atomic_compare_exchange_weak(&count, &cur, cur + 1));

85.4 Memory order — not touching it is the default#

85.4.1 Why “order” is a question at all#

Atomicity was “does not split”. Ordering is a different question: do others see things in the order I wrote them?

The answer is no, and there are two culprits.

1. The compiler reorders. Looking at one strand alone the result is the same, so it rewrites the sequence into a faster one (the editor of chapter 14).
2. The CPU reorders too. It gathers stores in a buffer before letting them out, and runs whichever instruction is ready first (chapter 13).

Neither is ever noticed by a program running alone: it reads back its own writes correctly. The problem shows only when another strand is watching.

Figure 85.1 — If the flag is visible, is the data written before it visible too?

Figure 85.1 is that situation. The writer fills in the data and raises a flag; the reader sees the flag and reads the data. Obvious to a human — yet without ordering the flag may arrive before the data, and the reader takes the “it is ready” signal and reads what was there before.

85.4.2 The pair builds a wall — release and acquire#

Hence the pair. The writer raises the flag with release, the reader reads it with acquire.

/* writer */                           /* reader */
data = 42;                             if (atomic_load_explicit(
atomic_store_explicit(                       &flag, memory_order_acquire)) {
    &flag, 1, memory_order_release);       use(data);     /* guaranteed to be 42 */
                                       }

Each word names a direction. release means “the writes before this point cannot sink below it”; acquire means “the reads after this point cannot rise above it”. One side alone achieves nothing — the wall stands only when the two pair up.

★ And what the pair guarantees is not merely the flag. If the flag is visible, then everything written before it is visible too. So the data itself need not be atomic: data above is a plain int.

85.4.3 Is ordering free? — measure it#

“The most expensive” invites the question: how expensive? Compiling the same C for two machines makes the answer visible.

★ The first two rows are character for character the same on x86, because that machine already keeps that order. Which yields this chapter’s most practical warning: code that wrongly uses relaxed runs perfectly when tested on x86. The same code on RISC-V or ARM runs without the fence and becomes a bug nobody can reproduce.

The third row costs on both machines. That is why the default is safe and dear.

If no order is specified, as in atomic_fetch_add(&x, 1), the strongest order, sequential consistency (memory_order_seq_cst), is used. It means every strand sees the order of atomic operations as one consistent story, and it is the model easiest for a human to reason about. In exchange it is the most expensive.

C provides six orders. We learn their faces from a table — most programs need only the default.

The two most common practical uses are these. First, the producer-consumer flag: fill the data and then raise the flag with release, and the consumer sees the flag with acquire and then reads the data. This pair guarantees “if the flag is visible the data is visible too.” Second, a pure statistics counter: only the final sum need be right and there is no need to order it against other data, so relaxed is exactly the right tool.

atomic_store_explicit(&ready, 1, memory_order_relaxed);   /* the flag */

85.5 The phrase “lock-free”#

That is what the example’s last line asked with atomic_is_lock_free. If an atomic type is handled by a single CPU instruction it is lock-free, and if not the library uses a hidden lock behind the scenes. On today’s mainstream machines integers of pointer size or smaller are mostly lock-free. Wrap a large struct in _Atomic, on the other hand, and — the syntax passes but — a hidden lock attaches and performance can become unexpectedly bad.

85.6 Where to use it and where not to#

85.7 When the holder stops — priority inversion and spinlocks#

Where atomic operations are not the answer, a lock is. And a lock carries a danger of a different kind from atomicity: the holder being unable to make progress.

=== Priority inversion — the low blocks the high

Take three tasks: urgent (high priority), ordinary (medium), idle (low).

1. The idle task takes a lock.
2. The urgent task wakes and asks for the same lock — it blocks. So far, normal.
3. Then the ordinary task wakes and pushes the idle task aside, being higher.
4. Now the idle task cannot run, cannot release the lock, and the urgent task stays blocked.

The outcome is upside down: the urgent task has effectively been beaten by the ordinary one. This is priority inversion. Nothing is wrong with the lock and nothing about atomicity broke — two rules, priorities and locking, met and undid each other.

The cure is to lift the holder. Priority inheritance raises the lock holder to the priority of whoever is blocked on it, so the middle task cannot push it aside and the holder finishes and releases quickly.

85.7.1 The same illness, another face — spinlocks in user space#

A spinlock waits by spinning rather than sleeping. When the critical section is very short this wins, because sleeping and waking costs more. That calculation rests on one assumption: the holder will not be taken off the CPU in the meantime.

Inside a kernel that assumption can be enforced — switch preemption off for a moment. User space has no such device. If the scheduler takes the holder away, every waiter burns CPU making no progress. The root is the same as priority inversion: the holder stopped.

We have seen operations that do not split. The next chapter is a tool in the opposite direction — C23′s checked arithmetic, which asks according to the contract whether an operation overflowed its vessel.