🔗 Concurrency & Lock-Free Programming
Sharing state correctly and fast: races, locks and their costs, atomics and CAS, the memory model applied, SPSC/MPMC rings, the ABA problem, RCU, and false sharing.
10.1 Why concurrency is hard
Sequential code lets us pretend there is one timeline. Statement A runs, then statement B, then statement C. The machine may pipeline, cache, speculate, and reorder internally, but the program is explained as if one actor walks through the text. Concurrency removes that comfort. Now there are many actors, each with its own program counter, registers, cache state, interrupts, preemption points, and view of memory. The question is no longer only "what does this line do?" but "what else might be running, and what can it observe?"
The simplest failure is a lost update. Two CPUs read x == 7, both compute 8, and both store 8; one increment disappeared. More subtle failures come from checking one location and acting on another. A producer may publish a pointer before the object is fully initialized. A consumer may see a descriptor marked ready before DMA buffer contents are visible to the CPU. A driver may ring a NIC doorbell before transmit descriptors have reached coherent memory. Nothing in the source text says "do this wrong"; the bug lives between independent timelines.
This is why shared mutable state is the central danger. If two execution contexts access the same memory and at least one writes, the accesses need an ordering rule. In C and C++, an unsynchronized data race is not merely "probably wrong"; it gives the implementation freedom that can make the program's behavior undefined. In kernel and driver work the problem is wider than language rules: ordering must also cross CPU cores, compiler optimizers, cache coherency, MMIO stores, DMA engines, interrupts, and sometimes PCIe transactions.
Concurrency bugs are hard because most executions are innocent. The bad interleaving may require a receive interrupt between two ordinary instructions, a store buffer draining late, or a queue wrapping after millions of packets. Logging often changes timing enough to hide the bug. Tests that pass a billion times can still miss the ordering that corrupts a ring entry or frees a buffer while another core still holds a reference.
The toolkit in this chapter is a way to make those timelines explicit. Locks create regions where only one actor may mutate protected state. Atomics give individual operations well-defined indivisibility. Compare-and-swap updates state only if the world still matches the value observed. Memory ordering gives names to publication, visibility, and dependence. Rings, RCU, and reclamation schemes build higher-level protocols from those pieces. The goal is not to memorize tricks; it is to state the ownership and ordering contract so precisely that the hardware, compiler, and next engineer all have the same story.
Sources
10.3 Mutual exclusion and locks
Mutual exclusion is the simplest answer to shared mutable state: arrange that only one thread of control can execute a particular piece of code at a time. The protected code is the critical section. The lock is not protecting code by magic; it is protecting an invariant. For a receive queue with head, tail, and descriptors, the invariant might be "these descriptors are software-owned; those are hardware-owned or free." A critical section is the interval during which that invariant may be temporarily false.
A mutex is a sleeping lock. If thread A holds the mutex and thread B tries to take it, B blocks: the scheduler can deschedule B and run something else. This is the usual default in process context when the critical section may take more than a tiny amount of time, may fault, may allocate memory with blocking flags, or may call into code whose latency is not bounded. A mutex also gives synchronization: in C++ terms, unlocking a std::mutex synchronizes with a later successful lock of the same mutex.
A spinlock is a non-sleeping lock. If the lock is held, the waiter repeatedly checks until it can acquire it. Spinning wastes CPU cycles, but avoids the scheduler path and is usable where sleeping is illegal. That matters in kernel and driver code. An interrupt handler, a softirq/NAPI path in the wrong context, or code running with preemption disabled cannot sleep waiting for a mutex. If the lock protects state shared with interrupt context, the primitive may also have to disable local interrupts, otherwise the CPU could interrupt itself, re-enter the driver, and deadlock on its own lock.
The practical rule is not "spinlocks are faster." It is "spinlocks are for short, bounded, non-sleeping critical sections." Updating a queue pointer or flipping a device-state flag can be reasonable. Walking a large list, copying packet payloads, waiting for firmware, printing diagnostics, or calling arbitrary callbacks under a spinlock is a design bug. A spinning waiter burns a core; on an overloaded system that can make the lock holder run later, not sooner.
The cost of locking has several layers. In the uncontended fast path, a lock is usually an atomic read-modify-write on a cache line plus ordering constraints. That is already more expensive than an ordinary load or store because the line must be obtained in an exclusive state. Under contention, the lock line becomes a serialization point: every acquirer modifies the same line, so the interconnect, not the ALU, becomes the bottleneck. With a mutex, contention can also mean scheduler work: sleeping a thread, selecting another, later waking the waiter, and rebuilding its cache footprint.
Locking can also create convoying. Suppose a thread holds a hot lock and is descheduled, page-faults, or is delayed behind a lower-priority task. Other threads pile up behind it. When the lock is released, many waiters may wake or compete, causing cache invalidations and context switches. Throughput collapses because progress is coupled to the slowest lock holder. In networking this can appear as a queue lock that works at low packet rates and then burns CPU at high rates, or as a transmit path where many producers serialize on one shared ring.
Deadlock is the failure mode where waiting has no possible future completion. The classic Coffman conditions describe when resource deadlock can occur:
- Mutual exclusion: at least one resource can be held by only one participant at a time.
- Hold and wait: a participant holds one resource while trying to acquire another.
- No preemption: the system cannot forcibly take the resource away safely.
- Circular wait: there is a cycle: A waits for B's resource, B waits for C's, and C waits for A's.
Locks naturally provide mutual exclusion and no preemption. Many systems also need hold-and-wait: a driver may hold a device lock while taking a queue lock, or a network path may hold a socket lock while entering driver code. Deadlock prevention therefore usually attacks circular wait. The common method is a global lock ordering rule: acquire device_lock before queue_lock, acquire lower-addressed bucket locks before higher-addressed ones, and avoid callbacks into upper layers while holding lower-layer locks.
A small example shows the shape of the problem:
lock(a);
lock(b);
/* update invariant involving a and b */
unlock(b);
unlock(a);
This is safe only if all code that takes both locks takes them in the same order. If another path does lock(b); lock(a);, testing may pass for months and then hang under a rare timing interleaving.
The deepest cost of locking is design coupling. A lock defines a serialization domain. One coarse lock is easy to reason about but limits parallelism and increases convoy risk. Fine-grained locks improve parallelism but increase ordering complexity, cache-line traffic, and deadlock surface. Low-level networking code often avoids the dilemma by partitioning ownership: per-RX-queue state, per-TX-queue state, per-CPU counters, and single-producer/single-consumer rings. The cheapest critical section is the one removed by a better ownership rule.
Sources
10.4 Atomics and compare-and-swap
Atomic operations are the smallest synchronization tools most lock-free algorithms are built from. An ordinary load or store says only "read this object" or "write this object" in the single-threaded abstract machine. An atomic load or store says more: this object may be touched concurrently, and this access participates in a defined inter-thread protocol. That does not make the algorithm correct, but it removes the first fatal problem: the access itself is no longer a data race.
There are three broad families. An atomic load reads one value indivisibly. An atomic store writes one value indivisibly. An atomic read-modify-write operation, usually shortened to RMW, reads the current value and writes a derived value as one indivisible operation with respect to other atomic operations on the same object. That "as one" is the essential property. If two threads both execute atomic_fetch_add(&x, 1), the final value increases by two; the increments do not collapse into the lost-update pattern where both threads read the same old value and both store the same new value. By contrast, x = x + 1 is a load, an add in a register, and a store, with room for another CPU to interleave.
The central RMW primitive is compare-and-swap, usually called CAS. In C11 it is spelled as compare-exchange: compare the atomic object with an expected value; if it matches, replace it with a desired value; if it does not match, report failure and tell the caller what value was actually found. CAS is optimistic concurrency: threads may race, but only the thread whose view is still current is allowed to commit.
int old = atomic_load_explicit(&x, memory_order_relaxed);
for (;;) {
int new = old + 1;
if (atomic_compare_exchange_weak_explicit(&x, &old, new,
memory_order_relaxed, memory_order_relaxed))
break;
/* On failure, old has been overwritten with the current value of x. */
}
This is the canonical CAS retry loop. It starts with a snapshot, computes a candidate next state, then tries to install it. If another CPU updated x first, the compare fails and old is updated to the observed value. The next iteration computes from that value. The weak form is allowed to fail spuriously on some implementations, so it belongs naturally in a loop. The strong form avoids spurious failure in the abstract interface, but it can still fail because another thread really changed the object.
fetch_add is often better than a CAS loop when the operation is exactly addition. It communicates intent, gives the compiler and CPU the direct primitive they may already have, and avoids hand-written retry code. Similar RMW operations include exchange, fetch-subtract, fetch-or, fetch-and, and fetch-xor. These build reference counts, sequence numbers, bit flags, queue indices, once-only state transitions, and ownership claims. The relaxed order is enough only when the atomic object itself is the whole fact being communicated; if an increment publishes a descriptor, pointer, or buffer ownership, the ordering has to say that too.
In low-level networking code, these primitives often sit behind kernel wrappers rather than C11 names. A per-queue packet counter can use fetch_add because the order of increments may not matter. A transmit path may use an atomic bit operation to claim a queue-stopped flag. A completion path may use CAS to move a state machine from ARMED to RUNNING only if an interrupt or poll loop has not already done so. A reference count on a buffer must be atomic because the final decrement is the point where freeing becomes legal. PCI Express even defines optional AtomicOp transactions such as FetchAdd, Swap, and CAS for operations targeting memory space, though drivers should still use the operating system's atomic, DMA, and MMIO accessors for the domain being synchronized.
The hard part is that lock-free code is still shared-state code. CAS protects one object-sized transition; it does not automatically protect every object named by that transition. If a stack head changes from pointer A to pointer B, CAS can make the head update atomic, but it does not by itself solve when the old node may be freed. If a ring index advances atomically, descriptor contents still need a publication rule so the consumer or NIC does not see the new index before the descriptor is ready.
A practical lock-free building block therefore has three parts: an atomic state variable, a rule for valid state transitions, and a memory-ordering contract around the data protected by those transitions. A flag may move from 0 to 1 exactly once; a reference count may never be resurrected after reaching zero; a producer index may advance only after the corresponding slot is initialized. The atomic operation gives indivisibility, the transition rule gives meaning, and the ordering contract, covered next, makes the surrounding data visible at the right time.
The discipline is to keep atomic state small, explicit, and boring. Use fetch_add for counters, atomic bit operations for flags, exchange for handoff, and CAS when the update is conditional on the exact previous state. When the loop becomes complicated, re-check the invariant.
Sources
10.5 The memory model, applied
Atomicity answers only one question: did this object get read or written without tearing? A memory model answers the next question: if one CPU sees this atomic value change, which other ordinary memory writes is it also entitled to see? That second question is where most lock-free code lives. A queue index, ready flag, descriptor ownership bit, or pointer is rarely the data itself. It is a signal that some other data has been prepared.
The useful first principle is that CPUs and compilers may move independent memory operations unless the program gives them a reason not to. A store to pkt->len, a store to pkt->data[0], and a store to ready may look ordered in C source, but source order alone is only a within-thread rule. It creates no inter-thread visibility rule. Another core may observe the flag before the payload is visible.
Acquire and release are the common low-cost constraints for this kind of message passing. A release operation says: all ordinary loads and stores before this point must become visible before the release is observed. An acquire operation says: after I observe the released value, later loads and stores in this thread must not float before that observation, and they may rely on the earlier writes that were released. Release usually belongs on the publishing store. Acquire usually belongs on the consuming load.
The pair matters. A release store by itself does not broadcast truth. An acquire load by itself does not refresh every cache line. The synchronization edge is created when an acquire load reads the value written by the release store, or reads a later value in the same release sequence. That edge is called synchronizes-with in the C and C++ models, and it contributes to the broader happens-before relation. Once A happens-before B, the memory effects of A must be visible to B as the abstract machine specifies.
The publication idiom is therefore simple and powerful:
struct packet {
uint32_t len;
uint8_t data[1500];
};
_Atomic(struct packet *) published;
void producer(struct packet *p)
{
p->len = 64;
p->data[0] = 0x45;
atomic_store_explicit(&published, p, memory_order_release);
}
void consumer(void)
{
struct packet *p =
atomic_load_explicit(&published, memory_order_acquire);
if (p != NULL)
handle(p->data, p->len);
}
If the consumer's acquire load returns the pointer stored by the producer's release store, then the initialization of len and data happens-before the consumer dereferences p. Those fields do not need to be atomic merely because another thread reads them. The producer writes them before publishing, and the consumer reads them only after acquiring the publication.
This is not the same as volatile. In standard C, volatile is about observable accesses, such as device registers or signal interaction. It does not make an operation atomic, and it does not establish inter-thread synchronization for ordinary shared data. Driver code often uses volatile-like accessors for MMIO because the compiler must really emit the register access, but ordering normal memory against CPUs or devices is still expressed with atomics, barriers, DMA APIs, or architecture-specific primitives.
NIC work makes the distinction concrete. When a transmit path fills a descriptor, it writes buffer address, length, checksum flags, and ownership state into memory that the device or another CPU will read. The publication operation might be a producer index update, an ownership bit, or a doorbell write. The invariant is the same as the pointer example: descriptor contents first, publication second. If the consumer is another CPU, a release store to the queue tail paired with an acquire load of that tail is often the right shape. In Linux that may appear as smp_store_release() and smp_load_acquire().
When the consumer is a device rather than a CPU, C acquire/release atomics are not enough by themselves, because the C memory model describes threads of execution, not PCIe transaction ordering or DMA visibility. Drivers use DMA mapping and I/O barrier rules to ensure descriptor writes reach the point where the device can see them before the MMIO doorbell is written. The reasoning is still publication reasoning, but the primitive is chosen for the observer: CPU acquire/release for CPU observers, DMA and MMIO barriers for device observers.
Another common mistake is to put acquire and release on wrong variables. The acquire load must read the value from the release sequence of the same atomic object used for publication. If a producer stores ready with release, but the consumer spins on unrelated count with acquire and later reads ready relaxed, there is no release/acquire pair on ready. You may have atomic operations, but not the happens-before edge you thought you had.
The practical test is to draw the arrow. Identify the ordinary writes that prepare the object. Identify the atomic or barrier operation that publishes it. Identify the operation that observes that publication. Then ask: does the observer's later use of the object sit after an acquire or equivalent barrier that actually pairs with the publisher's release? If yes, the code has a memory-order argument. If not, the code has hope, timing, and probably an intermittent bug.
Sources
10.6 The SPSC ring buffer
A ring buffer is the smallest useful lock-free queue because it removes two hard problems: allocation and contention between writers. The storage is a fixed array. One thread is the only producer and advances head; one thread is the only consumer and advances tail. Since each index has exactly one writer, neither side needs compare-and-swap to update its own position. The other side's index is only observed to decide whether progress is possible.
Start with N slots and two monotonically increasing unsigned counters:
struct spsc {
_Atomic unsigned head;
_Atomic unsigned tail;
void *slot[N];
};
head names the next slot the producer fills. tail names the next slot the consumer drains. The number of queued elements is head - tail, computed in unsigned arithmetic. This works as long as the queue capacity is less than half the counter range, so wraparound cannot make an old distance indistinguishable from a new one. In real code these counters are commonly uint32_t or uint64_t.
The physical array index is the logical counter reduced modulo N. If N is a power of two, reduction is just a mask:
slot[head & (N - 1)] = item;
That mask is not merely a micro-optimization. It also makes the invariant obvious: logical time keeps increasing, while physical storage cycles through 0 to N - 1. Many NIC descriptor rings work this way. A driver and device, or a poll-mode thread and an application thread, exchange fixed descriptors by advancing positions around a bounded circular array.
There are two common full/empty conventions. The simpler one sacrifices one slot: empty is head == tail; full is head - tail == N - 1. That lets code which stores only masked indices distinguish full from empty, because the visible indices are never equal in the full state. With monotonically increasing counters, we can use all N slots: empty is head == tail; full is head - tail == N.
The producer's push path is therefore:
bool push(struct spsc *q, void *item) {
unsigned head = atomic_load_explicit(&q->head, memory_order_relaxed);
unsigned tail = atomic_load_explicit(&q->tail, memory_order_acquire);
if (head - tail == N)
return false;
q->slot[head & (N - 1)] = item;
atomic_store_explicit(&q->head, head + 1, memory_order_release);
return true;
}
The consumer is the mirror image:
bool pop(struct spsc *q, void **out) {
unsigned tail = atomic_load_explicit(&q->tail, memory_order_relaxed);
unsigned head = atomic_load_explicit(&q->head, memory_order_acquire);
if (head == tail)
return false;
*out = q->slot[tail & (N - 1)];
atomic_store_explicit(&q->tail, tail + 1, memory_order_release);
return true;
}
The relaxed loads of the thread's own index are enough because only that thread writes that index. No other thread can race it from head to head + 1 or from tail to tail + 1. The acquire loads of the opposite index are needed because the opposite index is a publication variable. When the producer stores an item into a slot and then performs a release store to head, it is saying: the slot contents are ready before this new head value becomes usable. When the consumer observes that head with an acquire load, its read of the slot must not move before the observation of availability, and it must see the writes published before the release.
The same argument runs in reverse for freeing space. The consumer reads a slot, finishes using that queue entry, and release-stores the new tail. The producer acquire-loads tail before deciding that a slot is free to overwrite. Without this ordering, a weakly ordered machine could make the producer see the updated tail before the consumer's earlier read of the slot had been ordered, allowing overwrite too early. On x86 this often appears to work with ordinary loads and stores because the hardware memory model is relatively strong, but correct low-level code has to state the ordering it relies on. Drivers and packet-processing libraries are ported across Arm, x86, and accelerators; accidental ordering is how a queue passes stress tests on one server and loses packets on another.
Notice what this queue does not do. It does not protect multiple producers from choosing the same head, and it does not protect multiple consumers from choosing the same tail. Adding atomic_fetch_add is not a complete fix, because reserving a slot and publishing a slot become separate events, and consumers must not observe holes. The SPSC ring's power comes from the ownership discipline: one writer per index, fixed storage, and release/acquire only where ownership crosses between threads.
In NIC work, this discipline shows up everywhere. A receive path may have one entity replenishing buffers and one entity consuming completed descriptors. A transmit path may have one software producer filling descriptors and one completion path reclaiming them. The ring turns coordination into arithmetic plus two publication points. Get the arithmetic wrong and you get an off-by-one full condition. Get the ordering wrong and the failure is timing-dependent: a consumer sees a new index but stale data, or a producer reuses a descriptor whose previous owner was not done.
Sources
10.7 MPMC rings and the ABA problem
An SPSC ring is easy to reason about because each index has one writer. The producer owns tail, the consumer owns head, and the main subtlety is making data visible before publishing the index. A multiple-producer, multiple-consumer ring removes that comfort. Several CPUs may try to reserve the same producer slot or consume the same completed slot. The shared indices become allocation variables.
The usual tool is a compare-and-swap loop. A producer reads tail, checks that advancing it would not overrun head, then tries to change tail from the observed value to tail + 1. If the CAS succeeds, this producer owns that logical slot. If it fails, another producer won. Consumers do the symmetric operation on head.
for (;;) {
old = atomic_load_explicit(&tail, memory_order_relaxed);
if (old - atomic_load_explicit(&head, memory_order_acquire) == size)
return FULL;
if (atomic_compare_exchange_weak_explicit(&tail, &old, old + 1,
memory_order_acquire, memory_order_relaxed))
break;
}
slot = old & mask;
This reserves a position; it does not make the slot contents valid. Practical MPMC array queues add per-slot state: a sequence number, generation counter, valid bit, or descriptor ownership bit. The producer reserves a ticket, writes the element, then publishes with a release store. A consumer reserves a ticket, waits until the slot state says this ticket's data is present, reads it, then marks the slot empty for a later lap. The index CAS decides who owns a slot; per-slot state says which lap the slot belongs to.
The ABA problem is the failure mode where "same bits" are mistaken for "same state." CAS asks only whether the memory word still equals the value observed earlier. Suppose a thread reads A, is preempted, and other threads change the word from A to B and back to A. When the first thread resumes, its CAS from A to a new value may succeed even though the situation changed.
In bounded rings, ABA usually appears as index wrap or slot reuse. If a ring has 1024 entries and the software records only index & 1023, slot 7 today is indistinguishable from slot 7 one full lap later. A delayed consumer may see "slot 7 is full" and read later data. A delayed producer may similarly believe a slot is empty because the visible bit pattern has returned to an earlier value. This matters directly in NIC and driver code: descriptor rings are reused forever, and ownership may pass driver to device to driver millions of times per second.
The bounded-ring fix is a generation counter or per-slot sequence number. Instead of storing only full or empty, each slot stores the logical ticket expected for that slot. A producer with ticket t may use slot t & mask only when the sequence says t; after writing data it stores t + 1 to publish. A consumer with ticket t waits for t + 1; after reading, it stores t + size to mark the slot free for the next lap. The array index repeats quickly, but the sequence value should not. With a wide unsigned counter, wrap is practically unreachable; with a narrow hardware field, the driver must prove that wrap cannot fool any delayed observer.
Pointer-based queues and freelists have a sharper ABA hazard because storage can be freed and reused at the same address. A pop operation may read head = p and next = p->next; another CPU pops p, frees it, allocates a different node at the same address, and pushes it back. The first CPU sees head still equal to p, its CAS succeeds, and it links the structure using stale next.
One fix is a tagged pointer: CAS a pair, not just a pointer. The pair is (ptr, count), and each successful update increments count. If ptr changes from A to B and back to A, the count changes, so the old CAS fails. Some systems pack the count into unused pointer bits; others use a double-width CAS. The cost is portability and careful handling of counter wrap.
Another fix is hazard pointers. Before dereferencing a node read from a shared pointer, a thread publishes that address in a per-thread hazard slot, then rereads the shared pointer to confirm it is still protecting the same node. Removed nodes go to a retire list. Reclamation scans the hazard slots and frees only nodes that no thread has announced. Hazard pointers do not stop a logical value from changing A to B to A, but they stop memory at address A from being reused while a delayed CPU may still rely on the old object.
These mechanisms are complementary. CAS gives atomic ownership of an index or pointer. Release and acquire ordering make owned data visible in order. Generation counters and tagged pointers distinguish repeated bit patterns from repeated logical states. Hazard pointers keep storage lifetime from invalidating an earlier observation. MPMC rings in networking code need this discipline because they combine concurrency, DMA ownership, cache locality, and bounded memory reuse.
Sources
10.8 RCU and deferred reclamation
RCU begins with a lifetime problem. Suppose many CPUs need to read a shared object, such as a routing entry, receive-side scaling table, flow rule, or callback list. A writer occasionally needs to replace or remove one of those objects. A reader-writer lock would make the rule simple, but on a hot packet path even an uncontended reader lock can be too much. It adds cache-line traffic to a shared lock word, and it lets slow readers delay unrelated readers.
Read-copy-update changes the shape of the problem. Readers do not protect the object by incrementing its reference count or by modifying a lock. Instead, a reader enters an RCU read-side critical section, fetches an RCU-protected pointer, and uses the object reached by that pointer. The writer allocates or prepares a replacement, initializes it privately, then publishes the new pointer with release-like ordering. New readers can find the new object. Old readers may still be walking through the old one.
That split is the core idea: update the name first, reclaim the old storage later.
rcu_read_lock();
p = rcu_dereference(global_rule);
if (p != NULL)
use_rule(p);
rcu_read_unlock();
On the update side, the shape is:
new = build_replacement(old);
rcu_assign_pointer(global_rule, new);
synchronize_rcu();
free(old);
The API names above are Linux kernel names, but the reasoning is general. rcu_assign_pointer() is the publication operation: the object must be fully initialized before the pointer becomes visible. rcu_dereference() is the consuming operation: the reader must not let the compiler or CPU fetch fields from the object before it has safely fetched the pointer. In C11 terms this resembles release/acquire publication, although production RCU also deals with compiler dependencies, architecture rules, preemption, and scheduling.
The remarkable property is that readers can be wait-free in the usual algorithmic sense: a reader does bounded local work and does not spin, retry a CAS loop, take a contended lock, or wait for a writer. In some Linux RCU flavors, rcu_read_lock() and rcu_read_unlock() compile to extremely small operations. The reader pays mainly for ordinary loads and whatever ordering primitive rcu_dereference() requires.
The writer pays instead. If it removes object A from the shared structure at time T, no reader that starts after T should be able to find A through the public pointer. But readers that started before T might already hold a local copy of A's address. Freeing A immediately would create a use-after-free.
RCU solves that with a grace period. A grace period is long enough that every RCU read-side critical section already in progress at the start has finished. After that, any reader still running must have started after the removal and therefore cannot have obtained the removed object through the old pointer. At that point the old object may be freed, or a callback such as call_rcu() may run to free it asynchronously. The safety rule is not "wait until no readers exist anywhere." It is narrower: wait until all pre-existing readers are gone.
New readers may continue to run throughout the grace period. Writers do not need to stop the world, and readers do not need to announce which exact object they are looking at. The RCU implementation only has to detect quiescent states: points where a CPU or thread is known not to be inside an RCU read-side critical section. In a kernel, context switches, user-mode transitions, idle states, and explicit read-side unlocks can all contribute, depending on the RCU flavor.
Deferred reclamation is the other half of the pattern. CAS can change a pointer atomically, but it cannot tell you when the old pointee is dead. Reference counting can answer that, but every reader must modify a shared count, which is exactly the cache-line traffic RCU is trying to avoid. Hazard pointers answer it by having readers publish the addresses they might dereference. Epoch and RCU schemes move the bookkeeping away from the common dereference path and make reclamation a delayed activity.
RCU fits best when reads dominate writes, readers can tolerate a slightly old version, and updates can be expressed as replacement or unlinking rather than arbitrary in-place mutation. It is a poor fit when readers need a strict transaction with writers, when grace-period backlog becomes memory pressure, or when writers mutate fields that readers inspect without additional synchronization. RCU protects pointer reachability and lifetime; it does not make every field inside the object race-free.
For NIC and driver work, the appeal is direct. Fast paths often consult read-mostly state while interrupts, NAPI poll loops, control-plane threads, and teardown paths run concurrently. A receive path might look up a filter rule while an admin thread replaces the filter table. A transmit path might dereference queue configuration while ethtool or reset installs a new configuration. RCU keeps the packet path close to ordinary loads, while the slower control path absorbs copying, pointer publication, grace-period waiting, and deferred freeing. That is the right trade when nanoseconds on every packet matter more than occasional update latency.
Sources
10.9 False sharing and cache-aware concurrency
The memory model tells you when communication between threads is correct. It does not tell you whether that communication is cheap. False sharing is the classic example: two threads touch different C objects, with no data race and no logical sharing, yet the hardware treats them as shared because they live in the same cache line.
A cache does not track ownership byte by byte. It tracks blocks, normally called cache lines. On mainstream x86-64 systems the line size is commonly 64 bytes, though portable code should not assume that blindly. If core 0 repeatedly increments producer_count and core 1 repeatedly increments consumer_count, and those counters occupy different words in the same line, every store has a wider effect than the source code suggests. To modify its word, a core must obtain the cache line in a writable coherence state. That invalidates or downgrades other cores' copies of the same line. When the other core stores, it must obtain the line back. The line ping-pongs even though neither core reads the other counter.
This is false sharing because the program variables are independent. It is still real sharing to the coherence protocol. The cost is not merely an L1 miss; it can be a cross-core or cross-socket ownership transfer, with pipeline stalls, interconnect traffic, and sometimes NUMA penalties. In a low-level networking path this can dominate useful work. A receive interrupt counter, NAPI statistic, queue producer index, queue consumer index, and doorbell shadow may each look like a tiny scalar. Put hot fields for different CPUs on one line and a 100 Gbit/s datapath can spend surprising time moving ownership of bookkeeping cache lines instead of moving packets.
The same issue appears in lock-free queues. In an SPSC ring, the producer mostly writes head and reads tail; the consumer mostly writes tail and reads head. If head and tail sit next to each other, each side's write-mostly variable can evict the other's read-mostly view. Acquire/release operations order memory; they do not change coherence granularity.
The smallest reproducible example is simple:
struct bad_counters {
volatile unsigned long rx_packets;
volatile unsigned long tx_packets;
};
If one CPU updates rx_packets and another updates tx_packets, those fields will usually share a line. volatile is shown only to stop a benchmark from optimizing the stores away; it is not a synchronization primitive or a cure. In real concurrent C code, these might be atomics, per-CPU counters, or fields protected by different locks. The cache-line effect is about addresses and write frequency.
A cache-aware layout separates fields by writer. One direct C pattern is to align and pad each hot object so that no two such objects share a line:
#define CACHELINE_SIZE 64
struct cacheline_counter {
_Alignas(CACHELINE_SIZE) unsigned long value;
char pad[CACHELINE_SIZE - sizeof(unsigned long)];
};
struct queue_state {
struct cacheline_counter producer_head;
struct cacheline_counter consumer_tail;
};
Production code should avoid open-coded padding where the platform or project already provides a cache-line annotation. The Linux kernel has cache-line alignment macros for this class of problem. In portable C++, std::hardware_destructive_interference_size exists for the same intent. In C, choose a project constant from the target ABI or runtime discovery, then enforce it with _Alignas, static_assert, and tests that check sizeof and offsetof. The object must start on a line boundary, and its size or stride must keep the next hot object off that line. Aligning a member but then packing another hot member into the tail padding defeats the point.
Detection starts with suspicion and measurement. The smell is poor scaling despite little lock contention: two threads run fast alone, slower together, and CPU time disappears into memory stalls. Look for adjacent hot fields written by different CPUs, especially in arrays indexed by CPU, queue, ring, or worker id. A per-thread array of uint64_t counters[ncpu] can be bad if adjacent CPUs update adjacent elements; an array of padded counter structs is often better.
On Linux, perf c2c is built for cache-to-cache and HITM analysis. HITM means a load was satisfied from a cache line modified in another core's cache, a strong clue for contested line ownership. A typical workflow is to record the workload, report the hottest contended lines, then map offsets back to structure fields. For kernel and driver work, the report can point at the cache line, function, source line, and access offset. Once you have a candidate, confirm by changing only layout: add alignment or split the structure, rerun the workload, and check throughput and cache-to-cache events.
Padding is not free. It increases memory footprint, reduces cache density, and can make cold data worse. The rule is not "pad everything"; it is "separate independently written hot fields." Keep read-mostly fields together. Keep fields written by the same CPU together. Separate fields written frequently by different CPUs. For NIC rings this often means distinct cache lines for producer-owned indexes, consumer-owned indexes, per-queue statistics, and doorbell shadows, while descriptors remain densely packed for DMA and prefetch efficiency.
Sources
10.10 Patterns and pitfalls
Most concurrent low-level code is some form of producer/consumer system. A NIC receive path produces packet descriptors; a user thread, kernel stack, or poll loop consumes them. A transmit path does the reverse. Logging paths, completion queues, interrupt moderation paths, and work queues have the same shape: one side makes work visible, another side claims it and eventually releases capacity. The hard part is not the queue operation by itself. The hard part is deciding what happens when the consumer cannot keep up.
Backpressure is the discipline of making overload explicit. If a bounded queue is full, the producer can wait, drop, overwrite, batch and retry, or signal upstream to slow down. In packet I/O, each choice has a different failure mode. Waiting in an interrupt context may be illegal or may destroy latency. Dropping may be correct for telemetry or best-effort receive, but wrong for storage or control-plane messages. Overwriting keeps the newest data, useful for tracing snapshots, but loses history. Retrying in a tight loop can burn a core and make the consumer slower. A good design names the policy at the boundary: try_enqueue can fail; enqueue_blocking may sleep; enqueue_overwrite destroys old entries by contract.
The queue should carry capacity information in the same direction as the data path. Hardware rings do this naturally: the driver posts receive buffers; the NIC consumes them and produces completions; the driver replenishes the ring before starvation. Software rings need the same accounting. Watermarks, credits, or explicit return codes let the caller act before the system is saturated.
Lock-free code is worth its complexity when blocking is more expensive than retrying and when progress under preemption matters. That often applies in NIC and driver work: interrupt handlers cannot take arbitrary sleeping locks, dataplane threads may be pinned to cores, and a single contended mutex can bounce a cache line through every queue participant.
But lock-free is not automatically faster. A mutex protects a larger critical section with one ownership transfer; a bad lock-free loop may perform many failed compare_exchange operations, each forcing exclusive ownership of the same cache line. Under contention, "lock-free" can mean "everyone is making the cache-coherence fabric busy while only one thread succeeds." If contention is low, the code may sleep anyway, or correctness depends on complex lifetime rules, a plain lock is often better.
Common mistakes usually come from confusing atomicity with a full protocol. An atomic increment does not make the pointed-to object alive. A successful CAS does not prove the value was never removed and reused. A release store on an index does not publish data if the data was written after the store. A relaxed load may be fine for a statistic, but not for deciding whether a descriptor payload is initialized.
Another common bug is optimizing away the backpressure path. Many ring examples are tested only when the queue is mostly empty. The full case is where correctness lives: off-by-one capacity errors, missed wakeups, producer livelock, and descriptor ownership bugs tend to appear only when the consumer is delayed. Also test wraparound: ring indices that are safe for a minute can fail after billions of packets if sequence numbers are too narrow.
Memory reclamation is separate from removal. Popping a node from a lock-free queue does not mean no other CPU still holds a pointer loaded just before the pop. Use a real reclamation scheme: RCU for read-mostly structures with grace periods, hazard pointers, epoch reclamation, reference counts, or fixed object pools. In driver datapaths, fixed pools and descriptor rings are common partly because they make lifetime visible and bounded.
Testing concurrent code means trying to break assumptions. Start with a simple reference model under a lock, then run the concurrent implementation against it with randomized operations and invariant checks. Force capacities such as 1, 2, and 3; these expose full/empty ambiguity and wraparound quickly. Add many producer and consumer counts, including asymmetric cases such as one slow consumer with many producers. Insert deliberate yields, sleeps, pauses, and CPU affinity changes around publication points. Build with sanitizers where available, especially ThreadSanitizer for ordinary data races, while remembering that custom atomics, inline assembly, MMIO, and kernel code may be limited.
For low-level networking code, measurement is part of correctness. A queue that is logically correct but collapses under burst traffic is still wrong for the job. Record drops, retries, maximum occupancy, latency, and cache-miss behavior. Test realistic bursts, not just average packet rates, because buffers fail at peaks. Also test shutdown: stop producers while consumers drain, and free queues only after all possible readers have passed through the reclamation scheme.
The pattern is simple but unforgiving: define ownership, publication, capacity, and reclamation, then test the cases where each definition is stressed. Lock-free programming is not the art of avoiding locks everywhere. It is the art of making progress and visibility rules precise enough that hardware, compiler, and scheduler cannot invent a different program.
Sources