Part VI — Parallel Programming & Synchronization

Overview

Correct concurrent programming starts at the hardware level. A CPU does not execute instructions in the order you wrote them — it reorders stores and loads for performance. Multiple CPUs sharing memory introduce cache coherence traffic that can make a naive counter slower than a single-threaded one. Every kernel synchronization primitive — from a spinlock to RCU — exists to manage these hardware-level effects. This part builds the foundation: hardware behavior (§6.1), the MESI protocol that keeps caches consistent (§6.2), and the memory barriers that enforce ordering across CPUs (§6.3).

1. §6.1 — Hardware Foundations for Parallelism

CPU Pipeline: Store Buffer & Invalidation Queue

A modern CPU core does not write to the cache immediately. When a store instruction executes, the value goes into the store buffer — a small, private FIFO inside the core. The cache line is only updated when the store buffer drains, which can be many nanoseconds later. Meanwhile, other CPUs cannot see the write yet.

Similarly, when a cache line is invalidated by another CPU's write, the invalidation message is first dropped into the invalidation queuerather than applied immediately. This batching improves throughput but means a CPU might read a stale value from its L1 cache even after the message arrived.

Memory Hierarchy & Latency

Cache misses are the dominant cost in concurrent code. A lock acquisition that transfers a cache line from a remote CPU costs ~100–300 ns — as slow as a DRAM access. Designing concurrent code means designing to minimize cache-line transfers.

False Sharing — The Hidden Performance Killer

2. §6.2 — Cache Coherence: MESI Protocol

Every cache line in every L1/L2 cache is tagged with one of four MESI states. The protocol guarantees a globally consistent view of memory across all cores — but at the cost of bus traffic on every state transition.

Key Transitions to Memorize

Cache-Line Bouncing: atomic_inc() Under Contention

MOESI Extension

AMD CPUs add an Owned (O) state — a line that is dirty but shared. The owner responds to snoops directly (CPU-to-CPU transfer) without writing back to DRAM first. This reduces memory bus traffic in read-heavy workloads. Intel uses a similar Forward state in some implementations.

3. §6.3 — Memory Barriers & Ordering

Two Levels of Reordering

Linux Kernel Barrier API

x86 TSO (Total Store Order)

x86 guarantees that stores are observed by other CPUs in program order (no store-store reordering visible to observers). It does allow one reordering: a CPU may observe its own earlier stores before other CPUs do. In practice this means smp_wmb() and smp_rmb() compile to nothing on x86 (the compiler barrier is still needed). Only smp_mb() compiles to mfence.

On ARM and POWER the memory model is much weaker — any reordering is possible. Correct code must use explicit barriers on every platform, not just x86.

Pairing Rules — the Golden Rule

Minimal C Demo — Memory Barrier Simulation

Minimal C Demo — READ_ONCE / WRITE_ONCE

Minimal C Demo — C11 memory_order: release/acquire

4. §6.4 — Atomic Operations

Memory barriers tell the CPU and compiler about ordering. But they do not make an increment atomic — two CPUs can still read the same value, both add 1, and write back the same result (lost update). Atomic operations solve this by combining the read-modify-write into a single indivisible bus transaction. On x86 this uses the LOCK prefix; on ARM it uses ldxr/stxr (load-linked / store-conditional).

atomic_t, atomic64_t, refcount_t

Core Mechanism: Compare-and-Swap (CAS) Loop

Minimal C Demo — CAS Lock-Free Counter

kref / refcount_t — Reference Counting

kref wraps a single atomic_t with a lifecycle discipline: every caller that uses an object takes a reference (kref_get), and releases it when done (kref_put). When the count reaches zero, kref_put calls the release function to free the object. refcount_t (since kernel 4.11) adds saturation — an overflow wraps to 1 rather than 0, preventing use-after-free bugs from counter wraparound.

Minimal C Demo — kref / refcount_t Lifecycle

5. §6.5 — Counting at Scale

A single atomic_inc() call on a shared counter causes a cache-line round trip on every call (§6.2). At scale — 16 CPUs each doing millions of increments per second — that single cache line becomes the bottleneck for the entire machine. The kernel solves this with per-CPU counters.

percpu_counter vs local_t vs atomic_t

Minimal C Demo — Per-CPU Counter

6. §6.6 — Locking Patterns

Choosing the wrong synchronization primitive is one of the most common performance mistakes in kernel and systems code. The decision tree below encodes the key questions — each primitive has a specific niche, and using a heavier one than necessary wastes CPU cycles on every call.

Deadlock Prevention: Lock Ordering

Minimal C Demo — Lock Ordering

trylock + Release-on-Fail Pattern

When a code path must acquire two locks but cannot enforce a global order (e.g., the locks belong to different subsystems with incompatible hierarchies), use trylock: attempt to take the second lock; on failure, release the first and restart. Add a short backoff (cpu_relax() or cond_resched()) to avoid livelock.

Priority Inversion & PI Mutexes

A high-priority task blocks on a mutex held by a low-priority task. A medium-priority task preempts the low-priority holder, delaying the high-priority task indefinitely. The kernel's rt_mutex uses priority inheritance: while a task holds an rt_mutex, it temporarily runs at the highest priority of any waiter. This prevents medium priority tasks from causing unbounded delays. POSIX threads support this via PTHREAD_PRIO_INHERIT.

7. §6.7 — Spinlock Internals & Variants

A spinlock is the lowest-level mutual exclusion primitive in the kernel — it busy-waits instead of sleeping, making it safe in interrupt context where sleeping is forbidden. Three generations exist in the kernel, each fixing the previous one's scalability problem.

Generation 1: Test-and-Set — Simple but Unfair & Slow

Every waiting CPU repeatedly executes an atomic write (test-and-set) to the shared lock variable. Even when the lock is held and the attempt will fail, it still writes — generating a MESI invalidation that forces every other waiter to refetch the cache line before its next spin. With N waiters, each spin triggers N−1 invalidation round trips.

Generation 2: Ticket Spinlock — Fair but Still Bounces

A ticket spinlock assigns each caller a number (like a deli counter). The lock holds next (next ticket to issue) and owner (currently serving). Waiters spin on read-only copies of owner — no write per spin. Fair: CPUs are served FIFO. But unlock() increments owner, invalidating all spinners at once.

Generation 3: MCS Lock — Fully Local Spinning

qspinlock — Linux Default (kernel ≥ 4.2)

qspinlock combines all three ideas into a single 32-bit word. Uncontended acquires cost one CAS. A second waiter sets the pending bit and spins on the owner bit (no node allocation). The third and beyond join an MCS queue. This makes the common case (no contention) extremely cheap while scaling gracefully under high contention.

Spinlock Variants — When to Use Which

Minimal C Demo — Test-and-Set Spinlock

Minimal C Demo — MCS Lock Acquire / Release

8. §6.8 — Sleeping Locks: Mutex & Semaphore

When a critical section may hold a lock for milliseconds (e.g., disk I/O, copying from user space), busy-spinning wastes an entire CPU. A mutexsleeps the waiter and wakes it on unlock. The kernel's struct mutex adds adaptive (optimistic) spinning: if the lock owner is currently running on another CPU, a short spin can avoid the costly context switch.

struct mutex Key Fields

rw_semaphore — Reader-Writer Sleeping Lock

struct rw_semaphore allows multiple concurrent readers but exclusive writers. Key policy: once a writer is waiting, new readers are blocked (writer-preferring) to prevent writer starvation. percpu_rw_semaphore goes further — readers take a per-CPU lock (fast path), writers do a stop-machine-like barrier (slow path). Used for mm->mmap_lock, task_list_lock, and kernel module loading.

Minimal C Demo — Mutex Adaptive Spinning

9. §6.9 — Sequence Locks

A seqlock gives readers a lock-free fast path at the cost of possible retries. Writers hold an internal spinlock and increment a sequence counter (even → odd → even). Readers snapshot the counter before and after reading — if it changed, a writer was active and they retry. Used pervasively for time-keeping: jiffies, xtime, and the VDSO clock_gettime() fast path.

seqlock vs RCU vs rwlock

Minimal C Demo — seqlock Reader & Writer

10. §6.10 — RCU: Read-Copy-Update

RCU is the most important synchronization primitive introduced in the Linux kernel (2.5.43, 2002). The core insight: allow reads without any synchronization at all, and defer the cost of synchronization to the write side. Readers pay only a preemption disable (no cache line transfer, no atomic). Writers publish a new version atomically and wait for a grace period before freeing the old one.

RCU API — at a Glance

Core Mechanism: Publish-Subscribe + Grace Period

Grace Period: How Does the Kernel Know Readers Are Done?

A quiescent stateis a point at which a CPU cannot be inside an RCU read-side critical section: a context switch, entry to userspace, or the idle loop. The kernel's RCU subsystem watches for each CPU to pass through at least one quiescent state after the writer called synchronize_rcu(). Once every CPU has done so, the grace period is complete and the old object can be freed.

RCU-Protected Linked Lists

The kernel provides a full set of RCU-safe list operations in include/linux/rculist.h. list_del_rcu() unlinks the node but does not free it — a concurrent reader might still hold a pointer to it. Only after the grace period is it safe to free.

SRCU — Sleepable RCU

Standard RCU forbids sleeping in read-side critical sections. When sleeping is needed (e.g., waiting for user-space to respond), srcu_struct provides a per-domain sleepable variant. Each domain has its own grace-period tracking, so a slow reader only delays reclamation in its own domain. Used in KVM, eBPF, and file system notifications.

Practical Uses in the Linux Kernel

Minimal C Demo — RCU Reader & Writer

Minimal C Demo — RCU-Protected Linked List

11. §6.11 — Lock-Free Data Structures

Lock-free data structures use Compare-and-Swap (CAS) loops instead of locks. If a CAS fails (another CPU changed the value), the thread retries — no thread can be blocked forever by the scheduler. The Linux kernel uses lock-free structures in hot paths: rte_ring (DPDK), RCU-protected lists, and the per-CPU run-queue arrays.

Treiber Stack — Lock-Free Push & Pop

The simplest lock-free structure. A single pointer topis updated atomically. Both push and pop are CAS loops: read the current top, compute the new value, CAS — retry if another CPU changed top first.

The ABA Problem

CAS checks value equality, not identity. If a pointer value is reused (address A is freed then reallocated back to A), a stale CAS will succeed even though the structure changed underneath. The standard fix is to embed a version counter in the same word as the pointer (double-word CAS, or tagged pointers using low bits). The kernel's kfree_rcu sidesteps ABA entirely by deferring frees until all readers finish.

Minimal C Demo — Treiber Stack

Minimal C Demo — ABA Problem

Michael-Scott Queue (MPMC Lock-Free)

A lock-free FIFO queue with a head (consumer side) and tail(producer side), each independently CAS-ed. Enqueue: CAS tail to point to new node, then CAS tail forward. Dequeue: CAS head forward. Used in DPDK's rte_ringand Java's ConcurrentLinkedQueue.

12. §6.12 — Per-CPU Data

Per-CPU variables give each CPU its own private copy of a variable. Accesses require no synchronization at all — no lock, no atomic, no cache-line bounce. The kernel uses them for run-queues, statistics counters, softirq work queues, and slab allocator magazines.

API at a Glance

Why Per-CPU Beats atomic_t at Scale

Every atomic_inc() generates a bus-locked LOCK XADD on x86. With 64 CPUs all hitting the same counter, the cache line bounces between them — throughput degrades as O(N). With per-CPU: each CPU writes its own cache line, zero coherence traffic — throughput scales as O(1). The read cost is O(NR_CPUS) (summing all slots), but reads are rare for statistics counters.

Minimal C Demo — Per-CPU Counter Simulation

13. §6.13 — Synchronization Design Patterns

Choosing the wrong primitive costs performance or correctness. The decision tree below encodes the kernel community's conventional wisdom: start with per-CPU data, escalate to RCU for read-heavy, and only reach for a sleeping lock when the critical section is long or blocking.

Producer-Consumer: Ring Buffer Pattern

The most common real-world pattern in network drivers and audio subsystems.

SPSC Ring — Barrier-Only Synchronization

Hazard Pointers — Pointer-Safe Memory Reclamation

An alternative to RCU for lock-free structures. Each thread announces the pointer it is currently accessing in a public hazard pointer slot. The reclamer scans all hazard pointer slots before freeing — if any slot holds the address, it defers the free. Advantages over RCU: no grace period concept, works without preemption semantics. Disadvantages: O(N) scan per free, hazard pointers must be carefully ordered with the access (store-load barrier).

Common Anti-Patterns to Avoid

14. §6.14 — Debugging Concurrency Issues

Concurrency bugs (data races, deadlocks, priority inversion, false sharing) are the hardest class of kernel bugs to reproduce. The kernel ships with four major dynamic analysis tools — enable them during development, not production.

Tool Overview

lockdep — Lock Dependency Graph

lockdep builds a directed graph of lock acquisitions at runtime. An edge A → B means "lock A was held when lock B was acquired." If a cycle is ever detected (A → B and B → A from different code paths), lockdep fires WARN_ON with a full stack trace before the deadlock actually occurs — it detects the potential for deadlock, not just when it happens.

KCSAN — Kernel Concurrency Sanitizer

KCSAN instruments every load and store at compile time. At runtime it records concurrent accesses to the same address and reports a data race if at least one is a write. It uses a watchpoint-based approach — each CPU can hold a small number of watchpoints at a time, providing statistical coverage without full shadow memory.

perf c2c — False Sharing Detection

perf c2c record -- ./workload captures cache-to-cache transfer events (HITM — Hit In Modified state from another core). The report shows which cache lines are hot and which source lines produced the conflicting accesses. Typical fix: pad the hot variables to separate cache lines with __cacheline_aligned_in_smp or restructure structs so writer and reader fields do not share a line.

Minimal C Demo — lockdep Cycle Detection

Debugging Workflow

15. Kernel Source Pointers

16. Interview Prep