Chapter 43 — Below the Mutex

Chapter 43 — Below the Mutex

Two chapters of this book disagree about the same callback. Chapter 29 fixes a callback that arrives on a foreign thread with a mutex and a push_back, and that fix is right. Chapter 36 shows a callback on a deadline thread and says it may allocate nothing, lock nothing, and block on nothing — so Chapter 29's fix is that chapter's bug. Both pitfalls sections say so and point at each other, which routes the prohibition and leaves the question open: once the deadline thread may not take a lock, how does data reach it at all? This chapter is the answer, and it is narrower than the title suggests. It is one structure — a bounded hand-off between exactly one producer and exactly one consumer — and the two words of std::atomic vocabulary that make it correct. Writing lock-free structures in general is not this book's job; using one, inside a plug-in that ships, is.

The deadline path, and who is allowed to wait

Chapter 36's rule follows from one property: every mechanism on its list has a worst case you do not control. A mutex is the clearest case, and the failure has a name — priority inversion. The deadline thread runs at the highest priority the host can give it. A worker thread takes the mutex, and the scheduler, seeing a low-priority thread doing nothing special, preempts it for something else. Now the deadline thread arrives, wants the mutex, and waits — not for the worker's ten instructions, but for however long the scheduler takes to get back to a thread it considers unimportant. The host's deadline passes. Nothing in your code was slow. The lock was held for a microsecond and the wait lasted a millisecond, and the thread that paid was the one that could not afford to.

So the hand-off has to have an asymmetry built in. The worker thread — the UI thread, the file reader, the network receiver — may wait: if there is no room for its sample, it can block, retry, or drop, and any of those is fine. The deadline thread may not wait for anything, ever: if there is nothing to read, that is an answer and it returns. A structure with that asymmetry, where the deadline side has a bounded, lock-free, allocation-free path in every case, is what this chapter builds.

Surprise for C# devs: you have used this structure without seeing it. A bounded Channel<T> with BoundedChannelFullMode.DropWrite is the same idea with a runtime underneath, and ConcurrentQueue<T> its unbounded, many-producer cousin; and C#'s volatile — a read with acquire semantics, a write with release semantics, under the CLR's memory model — is exactly the pair of memory orders this chapter teaches. The false friend is the other direction: C++'s volatile means none of that (Chapter 29's pitfall), and the word you reach for by reflex is the one that does nothing here.

The hand-off

One producer, one consumer, a fixed ring of slots, and two indices. The whole reason it needs no lock is in the first sentence: each index has exactly one writer. The producer alone advances tail_; the consumer alone advances head_. Neither ever needs to change something the other is changing — the only question left is when the other thread gets to see it, and that is a question about memory ordering, not about mutual exclusion.

#pragma once
#include <atomic>
#include <cstddef>
#include <type_traits>

// The distance two counters must keep so that two cores do not fight over
// one cache line. Appendix L owns the argument about the number: it is the
// distance this code CHOSE, not a fact about every machine. 128 covers the
// common 64-byte line twice over and Apple silicon's physical 128-byte line
// once - the library's constant reports 256 there, deliberately generous.
inline constexpr std::size_t kSeparation = 128;

// A bounded single-producer, single-consumer queue. Exactly one thread ever
// calls TryPush, exactly one ever calls TryPop, and that is the whole reason
// it needs no lock: each index has ONE writer, so the only question is when
// the other thread gets to see it - which is what the memory orders answer.
// One slot is always kept empty, so "full" and "empty" are told apart by the
// indices alone: Capacity is N - 1.
template <class T, std::size_t N>
class SpscQueue {
    static_assert(N > 1, "an SpscQueue needs at least two slots: one is always kept empty");
    // The deadline side copies a slot out. A T whose copy allocates or
    // throws would put the allocator back on the path this queue exists to
    // keep it off - and in interrupt context there is no path to put it on.
    static_assert(std::is_trivially_copyable_v<T>, "slots are copied on the deadline path: the element type must be trivially copyable");
    // An atomic that is not lock-free takes a lock in disguise, and a lock is
    // what this whole file exists to avoid. On every desktop target a size_t
    // is lock-free; the assert is for the target where it is not.
    static_assert(std::atomic<std::size_t>::is_always_lock_free, "the indices must be lock-free, or the queue takes a lock on the deadline path");

public:
    static constexpr std::size_t Capacity = N - 1;

    // Producer thread only. Returns false when the ring is full: the caller
    // decides whether to wait, retry or drop - this side may be allowed to
    // wait, and this function never does it on the caller's behalf.
    bool TryPush(const T& value) noexcept {
        const std::size_t tail = tail_.load(std::memory_order_relaxed);   // mine: nobody else writes it
        const std::size_t next = tail + 1 == N ? 0 : tail + 1;
        if (next == head_.load(std::memory_order_acquire)) {              // the consumer's: acquire, so
            return false;                                                  // the slot it freed is really free
        }
        slots_[tail] = value;                                              // write the slot...
        tail_.store(next, std::memory_order_release);                      // ...THEN publish it: release
        return true;                                                       // orders the slot before the index
    }

    // Consumer thread only - the deadline thread, or the interrupt handler.
    // Returns false when the ring is empty. Never waits, never allocates,
    // never blocks: every line here is bounded.
    bool TryPop(T& out) noexcept {
        const std::size_t head = head_.load(std::memory_order_relaxed);   // mine
        if (head == tail_.load(std::memory_order_acquire)) {              // the producer's: acquire pairs
            return false;                                                  // with its release, so the slot
        }                                                                  // is visible before the index is
        out = slots_[head];
        head_.store(head + 1 == N ? 0 : head + 1, std::memory_order_release);   // the slot is free: release,
        return true;                                                             // so the producer's acquire sees it
    }

private:
    // Each index on its own line: the producer writes tail_ and the consumer
    // writes head_, and two cores writing one line take turns owning it.
    alignas(kSeparation) std::atomic<std::size_t> head_{0};
    alignas(kSeparation) std::atomic<std::size_t> tail_{0};
    alignas(kSeparation) alignas(T) T slots_[N] = {};   // the stricter of the two wins
};

Read TryPush as three steps: check for room, write the slot, publish the index. The third step is the one that matters. The slot is a plain T written with a plain assignment; the index is atomic. Without the release on the store, nothing orders the slot write before the index write — the compiler may reorder them, and so may the CPU, and a consumer that sees the new index may then read the old contents of the slot. With it, every write before the store is visible to any thread whose acquire load reads the stored value. TryPop's acquire load of tail_ is that thread: the pair is the whole synchronization, and the slot travels across it. The same pair runs the other way for head_, so the producer's acquire sees a freed slot only after the consumer has finished copying out of it.

Three things the listing refuses, each with a static_assert, because each would put back what the queue exists to remove. The element type must be trivially copyable: the consumer copies a slot, and a copy that allocates is an allocation on the deadline path. The index type must be lock-free: an atomic that is not is_always_lock_free takes a lock, which is the thing you were avoiding, in disguise. And the ring keeps one slot empty, so full and empty are distinguishable from the two indices alone — the alternative is a third counter that both sides write, and a counter both sides write is the shared state this design was built to avoid.

The picture, both directions at once — the second is the section on interrupt context, below:

What memory_order buys, measured

Chapter 29's std::atomic<int> counter{0} with ++counter used the default order, and never said what it was. The default is memory_order_seq_cst — every such operation takes its place in one total order that every thread agrees on — and it is correct for the queue above: replace every acquire and release with the default and nothing breaks. The question is what the weaker orders buy, and the answer is machine-dependent, which is why this book measures rather than asserts it. Here is what one store and one load compile to, at -O2, for each order, on the two machines CI runs on:

Order	arm64 (Apple silicon) store / load	x86-64 store / load
relaxed	str / ldr	mov / mov
release / acquire	stlr / ldapr (ldar unless the target has RCpc, Armv8.3)	mov / mov
seq_cst (the default)	stlr / ldar	xchg (or mov + mfence) / mov

Two different lessons in one table. On x86-64 the hardware already orders every store after every earlier store and every load after every earlier load — total store order — so a release store and an acquire load are plain movs, free, and the only thing the default costs you is that xchg: a full fence on every seq_cst store, tens of cycles, once per push and once per pop. On arm64 there is no such free lunch: the hardware reorders freely, a release store is a distinct instruction (stlr) that stops it, and the default and release cost the same for a store — an acquire load is the one place the weaker order is cheaper there, ldapr against the ldar that must also wait for earlier stlrs. So on x86 the weaker orders buy speed on every store, on arm64 a little on every load — and relaxed on arm64 buys you a bug. check_platform_claims.sh compiles that table on both platforms and reads the instructions back.

The bug is worth seeing, because it is the one Chapter 29 said you cannot test for. Take the ring above, change every order to relaxed, number every sample, and run it on this Apple-silicon machine:

stale: got seq 46983, expected 47047

Sixty-four behind — the ring has sixty-four slots — which is to say the consumer read the sample that occupied that slot one lap ago. The index had advanced; the slot had not, as far as this core could see. Six of eight runs at -O0, five of five at -O2, padded or not, and the same program with acquire and release restored delivered every sample in order in every run. On x86-64 the relaxed version passes — the hardware's ordering hides the missing one, which is the oldest bug report there is, works on my machine, with an instruction set for a machine. check_platform_claims.sh holds both: the stale read must appear on arm64 within a dozen runs, and must not on x86-64.

And the third sanitizer? It reported Chapter 29's kind of race — a flag stored relaxed and a value read after it — every time. On the ring its verdict depended on things that had nothing to do with the bug. At -O0, where an eight-byte struct slot is copied through memcpy, this toolchain's TSan reported nothing for that copy in any shape tried; at -O1 the same relaxed ring was reported every time; and the lab's own harness, whose consumer drains a bounded batch per tick, was never reported at any level. TSan finds unsynchronized accesses, and a memory order that is merely too weak leaves the accesses in place and removes the ordering between them — whether the tool sees the pair depends on how the accesses were lowered and when the two threads reach them. The judge for a wrong memory order is the harness's sequence check on a machine that reorders — which is why the lab's main.cpp numbers every sample, and why its TSan build is a second check of the code rather than the check of the order.

Trap: relaxed is not "a bit faster". It is no ordering at all with respect to every other location, and a program that uses it to publish data is broken on the arm64 machine your customers increasingly have, while passing every test on the x86-64 machine you develop on. Use relaxed for a counter nobody reads together with anything else — the lab's interrupt count — and for a thread's read of its own index. Everything that publishes uses release; everything that consumes uses acquire.

Two indices, two cache lines

The three alignas(kSeparation) in the listing are Appendix L's row on the cache line two counters share, applied. head_ is written by one core and tail_ by the other; if they sit in one cache line, every write by either core invalidates the other core's copy of the line, and two threads touching two different variables pay for a shared one. Separating them costs a few hundred bytes of padding per queue and nothing else. The number is the interesting part — Appendix L found std::hardware_destructive_interference_size reporting 256 on the machine this chapter was written on, where everybody types 64 — so the constant here is named for what it is, the distance this code chose. 128 is that choice: two lines' worth on the common 64-byte hardware, and on Apple silicon the physical line, which is 128 bytes, and half of what the library's constant reports there, because that constant is deliberately generous. Appendix L owns the argument; a reader shipping to that hardware measures, as that page did, rather than trusting either number.

The judge

Chapter 36's instrument, an allocation counter in a replaced operator new, judged that chapter's fix. It counted the whole process, which was right for a harness with one thread of interest. Here the worker is allowed to allocate and the deadline thread is not, so the counter has to ask which thread it is on — and thread_local is the only way it can, since nothing else identifies the caller inside a replaced allocator:

// Chapter 36's instrument, given a thread. That harness counted the whole
// process, which was right for a process with one thread of interest; here
// the worker is ALLOWED to allocate and the deadline thread is not, so the
// counter asks which thread it is on. thread_local is the only way it can:
// nothing else identifies the caller inside a replaced operator new.
namespace {
thread_local bool t_on_deadline_path = false;
long g_deadline_allocs = 0;              // written by the deadline thread only
void* volatile g_sink = nullptr;         // an allocation stored here cannot be elided

void* CountedAlloc(std::size_t size) {
    if (t_on_deadline_path) {
        ++g_deadline_allocs;
    }
    if (void* p = std::malloc(size)) {
        return p;
    }
    throw std::bad_alloc{};
}
}   // namespace

// Both forms, the lesson Recipe 49 paid for: under ASan new[] does not route
// through the scalar replacement, and a heap copy made by an array new
// would pass a counter that replaced only one.
void* operator new(std::size_t size) { return CountedAlloc(size); }
void* operator new[](std::size_t size) { return CountedAlloc(size); }
void operator delete(void* p) noexcept { std::free(p); }
void operator delete(void* p, std::size_t) noexcept { std::free(p); }
void operator delete[](void* p) noexcept { std::free(p); }
void operator delete[](void* p, std::size_t) noexcept { std::free(p); }

The first phase of the harness is the worker-to-deadline-thread direction. It checks the bound single-threaded first — Capacity pushes succeed, the next is refused, one pop makes room for exactly one more — because that is a claim about the structure and one a timing cannot muddy. Then the threads: the worker pushes two hundred thousand numbered samples, waiting when the ring is full because it is the thread that can; the deadline thread drains a bounded number per tick, which is what a deadline callback does, and returns. Every wait has a deadline, for Chapter 38's reason — a hand-off that stopped delivering would stop CI rather than fail it:

// Phase 1: a worker thread produces, the deadline thread consumes. The
// worker may wait when the ring is full - it is the thread that CAN. The
// consumer drains a bounded number of samples per tick, which is what a
// deadline callback does: bounded work, then return to the host.
void WorkerToDeadlineThread() {
    constexpr std::uint32_t kItems = 200000;
    constexpr int kPerTick = 32;
    SpscQueue<Sample, 64> queue;

    // The bound, single-threaded first, because it is a claim about the
    // structure and not about timing: Capacity pushes succeed, the next is
    // refused, one pop makes room for exactly one more.
    for (std::uint32_t i = 0; i < queue.Capacity; ++i) {
        Check(queue.TryPush(Sample{i, 0.0f}), "the ring accepts Capacity samples");
    }
    Check(!queue.TryPush(Sample{99, 0.0f}), "the ring refuses the sample past Capacity");
    Sample popped{};
    Check(queue.TryPop(popped) && popped.seq == 0, "TryPop hands back the oldest sample");
    Check(queue.TryPush(Sample{99, 0.0f}), "one pop makes room for exactly one push");
    while (queue.TryPop(popped)) {
    }

    std::atomic<long> retries{0};                   // full-ring waits, on the worker's side
    std::atomic<bool> give_up{false};               // set when the consumer's deadline expires,
    std::thread worker([&] {                        // so a ring that never delivers cannot leave
        for (std::uint32_t i = 0; i < kItems; ++i) {   // join() waiting forever: three broken rings
                                                    // hung this harness rather than failing it
            const Sample s{i, static_cast<float>(i) * 0.5f};
            while (!queue.TryPush(s)) {             // full: the worker waits, the
                if (give_up.load(std::memory_order_relaxed)) {   // deadline side never does
                    return;
                }
                retries.fetch_add(1, std::memory_order_relaxed);
                std::this_thread::yield();
            }
        }
    });

    t_on_deadline_path = true;                      // from here to the join, this thread is the deadline thread
    // A positive control first: one deliberate allocation must be counted,
    // or the zero below would be the instrument's silence rather than the
    // code's innocence (the flag line above is one edit from making it so).
    const long control = g_deadline_allocs;
    g_sink = new int;                            // through a volatile sink: a bare new/delete
    delete static_cast<int*>(g_sink);            // pair is one the optimizer may elide
    Check(g_deadline_allocs == control + 1, "the counter sees an allocation on this thread");
    const long allocs_before = g_deadline_allocs;
    const auto deadline = std::chrono::steady_clock::now() + std::chrono::seconds(30);
    std::uint32_t expect = 0;
    long ticks = 0;
    long empty_ticks = 0;
    bool in_order = true;
    while (expect < kItems && !Expired(deadline)) {
        int drained = 0;
        Sample s{};
        while (drained < kPerTick && queue.TryPop(s)) {   // bounded work per tick
            if (s.seq != expect) {
                in_order = false;
            }
            ++expect;
            ++drained;
        }
        if (drained == 0) {
            ++empty_ticks;                          // nothing to do is a valid tick
        }
        ++ticks;
    }
    const long allocs_during = g_deadline_allocs - allocs_before;
    t_on_deadline_path = false;
    give_up.store(true, std::memory_order_relaxed);   // a no-op unless the deadline expired
    worker.join();

    Check(expect == kItems, "every sample the worker produced arrived (no deadline expired)");
    // A wrong memory order shows up here as a stale slot - but only on a
    // machine that reorders, and then not on every run. This check is the
    // ring's judge for the CODE; the judge for the ORDER is
    // check_platform_claims.sh's relaxed-ring section, a dozen runs on arm64.
    Check(in_order, "every sample arrived in the order it was produced, none twice");
    Check(allocs_during == 0, "the deadline thread allocated nothing across the whole session");
    std::printf("worker -> deadline thread: %u samples, %ld ticks (%ld empty), %ld full-ring retries by the worker, %ld allocations on the deadline thread\n",
                kItems, ticks, empty_ticks, retries.load(), allocs_during);
}

Three assertions, and each catches a different mistake. Every sample arrived — nothing was lost to a full ring or a stalled consumer. Every sample arrived in order and once — the memory orders did their job, on this machine. And the deadline thread allocated nothing, across the whole session, which is the number Chapter 36 said a timing cannot give you. On this machine the phase prints something like 200000 samples, 12122 ticks (4086 empty), 181 full-ring retries by the worker, 0 allocations on the deadline thread: the ring filled and the worker waited, the ring emptied and the consumer returned, and neither event cost the deadline thread anything.

Now put Chapter 29's fix on the deadline thread and watch what the judge can and cannot see. A Sink with a mutex and a std::vector, the worker locking and pushing, the deadline thread locking and reading:

struct Sink {
    std::mutex m;
    std::vector<Sample> samples;     // grows on the worker's side
};

// The deadline thread's tick. The counter reads zero: nothing here
// allocates on THIS thread. The lock is the bug, and no counter sees it.
void Tick(Sink& sink) {
    std::lock_guard<std::mutex> g(sink.m);     // held by a worker the scheduler
    for (const Sample& s : sink.samples) {     // has just preempted: the
        Consume(s);                            // deadline thread waits for it
    }
    sink.samples.clear();
}

The counter stays at zero for the deadline thread, because the vector grows on the worker's side — run it and it does. The judge is silent on the lock. That silence is the honest limit of this instrument: an allocation counter sees allocations, and a lock is not one. What sees a lock on a deadline path is the tool Chapter 36's "In the wild" named and this book's baseline toolchain does not yet ship, RealtimeSanitizer — and, until then, the review question who could be holding this when I arrive? asked at every lock_guard on a thread with a deadline.

From interrupt context — Shape 4's other addition

Chapter 16's Bestiary said Shape 4, the embedded HAL, is Shape 1 with two additions, and then taught one of them: Chapter 32 is the whole of "ownership is initialization order". The other — callbacks may run in interrupt context — has been one sentence for the entire book. This is where it is paid, because it is this chapter's rule under a harder deadline, and the same structure answers it.

An interrupt handler does not run on a thread of its own. It runs on whatever the processor was doing when the interrupt arrived — in the middle of your main loop, between any two instructions — to completion, and then the loop resumes as if nothing happened. That single fact turns each of Chapter 36's should nots into a cannot:

• It cannot block, on anything, ever. A deadline thread that takes a lock held by a worker waits until the worker is scheduled. An interrupt handler that takes a lock held by the code it interrupted waits until that code runs again — and that code cannot run until the handler returns. That is a deadlock with one thread, and no sanitizer names it, as the listing at the end of this section shows. The allocator is a lock too (Chapter 36), so "no allocation" stops being advice about latency and becomes a rule about not freezing the device.
• It cannot take a context pointer. A handler has the signature the hardware gives it — or the vendor's table does — and no void* rides along. Chapter 18's trampoline pattern has nothing to cast. Everything a handler touches must therefore be reachable by name, at namespace scope, and must exist before main runs: static storage, constant-initialized, never a local of anything.
• Nothing it touches may take a lock — the shared state is lock-free atomics or volatile sig_atomic_t. An atomic that is is_always_lock_free is safe to use from a handler; one that is not takes a lock, and the previous rule applies. The queue's static_assert is that requirement written down.

The hand-off out of interrupt context is the queue above, unchanged, with the handler as producer. The one change is in policy: the handler cannot wait when the ring is full, so it drops the sample and counts the drop — and the count is what tells you the ring was too small, which is a design decision the main loop can act on, where a hung device is not.

A desktop has no interrupts you can register from user space, but it has the thing that behaves like one: a POSIX signal handler, which interrupts the thread wherever it is, runs to completion on that thread with no context pointer, and is subject to exactly the same three rules (POSIX even publishes the list of functions it may call, and malloc is not on it). The lab's second phase is that: a timer signal every millisecond, a handler that pushes into a queue in static storage, and the main loop draining it — the interrupt count relaxed, because nothing is published through it, and the drop count relaxed for the same reason:

// Phase 2: the producer is an interrupt. A timer signal interrupts the main
// loop wherever it happens to be, the handler runs to completion on the
// SAME thread, and the loop resumes - which is exactly an ISR's relationship
// to the code it preempts. Everything the handler touches is at namespace
// scope, because a handler, like an ISR, takes no context pointer: it can
// only reach what exists before main runs.
SpscQueue<Sample, 16> g_from_interrupt;           // static storage: exists before main
std::atomic<std::uint32_t> g_interrupts{0};       // lock-free, so it is safe here
std::atomic<std::uint32_t> g_interrupt_drops{0};

void OnTimerInterrupt(int) {
    // Bounded, lock-free, allocation-free, and it never waits: if the ring
    // is full, the sample is dropped and the drop is counted. An interrupt
    // that waits for the loop it interrupted waits forever.
    const std::uint32_t n = g_interrupts.fetch_add(1, std::memory_order_relaxed);
    if (!g_from_interrupt.TryPush(Sample{n, 1.0f})) {
        g_interrupt_drops.fetch_add(1, std::memory_order_relaxed);
    }
}

void InterruptToMainLoop() {
    constexpr std::uint32_t kWanted = 200;

    struct sigaction action = {};
    action.sa_handler = &OnTimerInterrupt;
    sigemptyset(&action.sa_mask);
    sigaction(SIGALRM, &action, nullptr);

    struct itimerval every_ms = {};
    every_ms.it_value.tv_usec = 1000;
    every_ms.it_interval.tv_usec = 1000;
    setitimer(ITIMER_REAL, &every_ms, nullptr);    // from here, the handler can run between any two lines

    t_on_deadline_path = true;                      // the handler runs on THIS thread, so it is counted too
    const long control = g_deadline_allocs;         // the same positive control as phase 1
    g_sink = new int;                            // through a volatile sink: a bare new/delete
    delete static_cast<int*>(g_sink);            // pair is one the optimizer may elide
    Check(g_deadline_allocs == control + 1, "the counter sees an allocation on this thread");
    const long allocs_before = g_deadline_allocs;
    const auto deadline = std::chrono::steady_clock::now() + std::chrono::seconds(30);
    std::uint32_t received = 0;
    std::uint32_t last_seq = 0;
    bool in_order = true;
    Sample s{};
    // First, the loop is BUSY for a quarter of a second - a long draw on a
    // real main loop - while the interrupts keep coming: more of them than
    // the ring has slots, so the drop policy is exercised rather than
    // merely compiled. (The sleep returns early on each interrupt, so it
    // is re-issued until the time has really passed.)
    const auto busy_until = std::chrono::steady_clock::now() + std::chrono::milliseconds(250);
    while (!Expired(busy_until)) {
        struct timespec nap = {0, 5 * 1000 * 1000};
        nanosleep(&nap, nullptr);
    }
    while (received < kWanted && !Expired(deadline)) {
        while (g_from_interrupt.TryPop(s)) {        // a dropped sample leaves a gap in seq,
            if (received > 0 && s.seq <= last_seq) {   // never a repeat and never a step back
                in_order = false;
            }
            last_seq = s.seq;
            ++received;
        }
    }
    const long allocs_during = g_deadline_allocs - allocs_before;
    t_on_deadline_path = false;

    struct itimerval off = {};
    setitimer(ITIMER_REAL, &off, nullptr);          // stop the interrupts...
    action.sa_handler = SIG_DFL;
    sigaction(SIGALRM, &action, nullptr);           // ...then uninstall: the order matters
    while (g_from_interrupt.TryPop(s)) {            // what the last interrupts left in the ring
        ++received;
    }
    const std::uint32_t after_stop = g_interrupts.load();
    struct timespec settle = {0, 20 * 1000 * 1000};
    nanosleep(&settle, nullptr);                    // twenty timer periods: any survivor would fire
    Check(g_interrupts.load() == after_stop, "no interrupt arrived after the timer was stopped and the handler uninstalled");

    const std::uint32_t fired = g_interrupts.load();
    const std::uint32_t dropped = g_interrupt_drops.load();
    Check(received >= kWanted, "the main loop received the samples the interrupts produced (no deadline expired)");
    Check(in_order, "every interrupt's sample arrived in order, none twice");
    Check(dropped > 0, "the busy stretch overflowed the ring, so the drop policy was exercised");
    Check(received + dropped == fired, "every interrupt either delivered its sample or counted a drop");
    Check(allocs_during == 0, "neither the handler nor the loop it interrupted allocated");
    std::printf("interrupt -> main loop: %u interrupts, %u samples received, %u dropped on a full ring, %ld allocations\n",
                fired, received, dropped, allocs_during);
}

The handler runs on the main thread, so the same thread-local counter judges it — and 0 allocations there is a claim about the handler and the loop it interrupted, since the counter cannot tell them apart and does not need to. The harness also keeps the loop busy for a quarter of a second before it drains, so more interrupts arrive than the ring has slots and the drop count is exercised rather than merely compiled: on this machine, some four hundred interrupts, two hundred delivered and the rest counted, every one accounted for. What the harness cannot check is the version that hangs. Take Chapter 29's fix into the handler, and let the interrupt arrive while the loop is inside its own critical section — which, over a long enough session, it will:

#include <csignal>
#include <cstdio>
#include <mutex>
#include <vector>

static std::mutex g_m;
static std::vector<int> g_samples;

static void OnTick(int) {
    std::lock_guard<std::mutex> g(g_m);      // Chapter 29's fix, in a handler
    g_samples.push_back(1);
}

int main() {
    std::signal(SIGALRM, &OnTick);
    {
        std::lock_guard<std::mutex> g(g_m);  // the main loop is inside its critical section...
        g_samples.push_back(0);
        raise(SIGALRM);                      // ...when the interrupt arrives
    }
    std::printf("samples: %zu\n", g_samples.size());
    return 0;
}

It never prints. One thread, waiting for itself — the standard calls a lock in a handler undefined, and on both libcs the definition it gets is a deadlock; plain, under ASan/UBSan and under TSan, the process simply sits there, and every sanitizer sits with it. check_platform_claims.sh asserts the plain build's hang, bounded, on both platforms — the sanitized builds hang the same way, and were run by hand — because a demonstration whose only outcome is silence needs a script that treats silence as the answer.

The rule for the reader who never ships to a microcontroller: this shape reaches the desktop. A CAN stack or a Modbus library calls your receive callback from its driver context, a kernel-mode audio driver's callback is one, and any vendor header that says "must return within N microseconds" or "do not call any API function from this callback" is telling you, in its own words, that you are in this section.

Pitfalls

• A std::function in the slot. It looks like a queue of work, and it allocates on assignment for any callable larger than its small buffer — on the producer's side, which the counter permits, and on the consumer's the moment the slot is copied out. The slot is trivially copyable, which the static_assert enforces; if what crosses is work, cross a small integer or enum that names it and keep the work on the deadline side, preallocated.
• A bounded queue that waits when full — on the wrong side. The producer blocking is fine and the consumer blocking is the bug, and the API above cannot express either: both return false and leave the decision to the caller. A queue whose Pop blocks when empty is a condition variable with a different name, and it belongs on the worker's side of the world.
• Two producers. Register the trampoline for two devices, or let a second thread post into the same ring, and the invariant that made it lock-free — one writer per index — is gone. The failure is silent and rare, which is the worst kind. A multi-producer queue is a different structure with a compare-and-swap in it; the day you need one, take it from a library that publishes its proof, and Chapter 27's rules for a dependency apply.
• reserve as a guarantee. A std::vector that was reserved for a thousand samples allocates on the thousand-and-first push_back, on whichever thread happened to push it, on whatever day the load went up. Preallocation is a fixed-size array or a ring, not a hint to a container.
• relaxed for speed on the machine that hides it. The table above: on x86-64 nothing is lost, and the test passes; on arm64 the sample arrives one lap old. The order that publishes is release, always, and the cost on the machine where it is not free is the cost of being correct there.
• A lock in a signal handler or an interrupt — or a printf, or a std::string. Each is a lock the interrupted code may hold. The three ways to know you are in this context: the callback has no context pointer, the vendor's header says how fast you must return, or the word ISR, interrupt or driver context appears anywhere near the registration function.
• Testing on one instruction set. Every claim in this chapter with a platform in it was found by running on the other one. If the deadline path ships to arm64, it is tested on arm64, and the sequence check is the assertion.

Key principle: "Data reaches a deadline thread through a bounded ring with one producer and one consumer, never through a lock: the writer publishes with release, the reader takes with acquire, the deadline side never waits, and an interrupt handler is the same rule with waiting removed entirely — nothing it touches may block, and everything it touches exists before main."

In the wild

The structure above is the one every real-time codebase ends up owning, usually under a name. PortAudio ships it as PaUtilRingBuffer, JUCE as AbstractFifo, and the Linux kernel as kfifo; boost::lockfree::spsc_queue and the widely copied ReaderWriterQueue are the same two indices with more engineering around the corners, and every game engine's render thread receives its frame through one — a double or triple buffer is a ring with two or three slots. The microcontroller world has its own spelling for the interrupt half: FreeRTOS's xQueueSendFromISR is TryPush with the drop policy built in, and every HAL's "defer to the main loop" pattern is this chapter's second phase. C# arrived at the same shape from the other direction: Channel.CreateBounded with a drop mode, and the Volatile.Read/Volatile.Write pair that low-latency .NET code uses where a lock would stall the audio thread — acquire and release with the runtime's names on them. And the tool that turns this chapter's rules into a build failure is arriving: RealtimeSanitizer, in recent Clang, aborts the run the moment a function marked [[clang::nonblocking]] allocates or locks — Chapter 36's counter and this chapter's lock rule, promoted into the sanitizer family, for the day the baseline toolchain catches up.

In Rust

Rust took its Ordering — Relaxed, Acquire, Release, SeqCst — from C++11 by name and meaning, so the table above reads unchanged. What changes is who checks the invariant: a Rust ring's slots would be UnsafeCells, and the two-thread access to them an unsafe block whose safety comment is the sentence "one writer per index" — the compiler will not let the structure exist without someone writing that argument down. That is the difference in a sentence: in C++ the invariant is a comment the sanitizer sometimes checks; in Rust it is a comment the compiler demands.

Try it

The task card is exercises/deadlinelab/TASK.md; spsc_queue.h and main.cpp beside it are the worked result, so do the card cold first and compare afterwards.

1. Build the ring from the constraints — one producer, one consumer, a fixed array, two atomic indices, TryPush and TryPop that never wait — before reading the listing. Decide how full and empty are told apart, and where each memory order goes, and write down why for each one.
2. Judge it with the harness. Number every sample. Check order, completeness, and zero allocations on the consumer's thread, and give every wait a deadline.
3. Weaken it. Change every order to relaxed and run twenty times. On arm64 you will see the stale slot; on x86-64 you will see nothing, which is the more important observation. Restore the orders and confirm the stale read is gone.
4. Put Chapter 29's fix on the deadline thread — a mutex and a vector — and watch the allocation counter stay at zero. Say what the judge cannot see, and what could.
5. Make the producer an interrupt. A timer signal, a handler with no context pointer, a queue in static storage, a drop count. Then, on the card, take a lock in the handler and watch the process stop — under all three sanitizers.
6. Stretch: size the ring from the drop count. Shrink the interrupt phase's ring until drops appear, and reason about the relationship between the interrupt rate, the loop's worst-case iteration, and the ring size. That relationship is the design, and it is the number a vendor's "must return within N microseconds" is asking you to compute.