In concurrent programming, “lock” is the word we use most, but a lock is not a primitive that exists on its own. Take any kernel lock apart and you find the same two foundations underneath: atomic operations, which make a read-modify-write impossible to interrupt, and memory barriers, which constrain the order in which other CPUs observe memory accesses. This chapter covers no particular lock. It focuses on these two foundations, because every lock that follows, from the spinlock in Chapter 2 to mutex, rwsem and ww_mutex, is a different combination of atomic operations + memory barriers + a waiting strategy. Without a solid foundation, there is no way to reason about the correctness of the locks built on top of it.

1.1 What a Lock Protects Against: Three Faces of a Data Race

When two CPUs run counter++ concurrently, the result can be smaller than expected. counter++ is not one instruction but three steps:

load  r, [counter];  read
add   r, 1        ;  modify
store [counter], r;  write

If both CPUs read the same old value at almost the same time, each adds one and writes the result back, and two increments leave only one behind. This is a lost update.

sequenceDiagram
    participant A as CPU A
    participant M as counter (initially 0)
    participant B as CPU B
    A->>M: load reads 0
    B->>M: load reads 0
    A->>A: 0 + 1 = 1
    B->>B: 0 + 1 = 1
    A->>M: store writes 1
    B->>M: store writes 1
    Note over M: Two increments leave 1: one update is lost

It is the most intuitive kind of data race, but not the only one. Concurrency bugs come in three forms:

  • Lost update: several read-modify-write sequences interleave and some updates are overwritten. The root cause is that the RMW is not atomic.
  • Torn access: a single read or write is split into several by the compiler or the hardware. On some paths a 64-bit variable may be written as two 32-bit halves, and another CPU can read a half-written value.
  • Reordering: even when every access is atomic on its own, different CPUs can observe the order of operations differently. Reordering happens at two levels: the compiler swaps independent reads and writes at compile time, and the CPU changes the global visibility order at run time through the store buffer and out-of-order execution.

The first two call for atomic operations; the third calls for memory barriers. These two tools run through the whole chapter.

1.2 Getting Past the Compiler First: READ_ONCE/WRITE_ONCE and the Compiler Barrier

The three races in the previous section all originate in multicore hardware. But before the trouble reaches the hardware, there is an earlier player: the compiler. To make code faster, it makes bold assumptions about every memory access we write. Those assumptions are perfectly valid in single-threaded code and cause bugs once several threads are involved. So the first tool in this chapter is neither an atomic instruction nor a hardware barrier, but the lightest and most often overlooked line of defense.

Start with a trap almost everyone has fallen into. One thread spins, waiting for another thread to set a flag:

while (!flag)
	;          /* wait until flag becomes non-zero */

From the compiler’s point of view, nothing in this loop modifies flag, so it loads flag from memory into a register once and from then on checks only the register, never memory. Even after another thread has set flag, the loop never sees it and spins forever. The compiler did nothing wrong; we never told it that the variable can change behind its back.

The C standard treats two threads reading and writing the same variable without synchronization as undefined behavior (a data race is undefined behavior). Once that happens, the compiler is entitled to any optimization: keep the value in a register, merge several reads into one, or even delete the loop altogether. To prevent this, we need a way to give the compiler a hard rule: this access must go to memory exactly once, no more and no less. The kernel’s answer is READ_ONCE/WRITE_ONCE, defined in include/asm-generic/rwonce.h:

#define __READ_ONCE(x)	(*(const volatile __unqual_scalar_typeof(x) *)&(x))

#define READ_ONCE(x)							\
({									\
	compiletime_assert_rwonce_type(x);				\
	__READ_ONCE(x);							\
})

#define __WRITE_ONCE(x, val)						\
do {									\
	*(volatile typeof(x) *)&(x) = (val);				\
} while (0)

Strip away the macro wrappers and the core is a single volatile cast. volatile tells the compiler that this location can be rewritten at any moment by something it cannot see, so it must not cache, merge or omit the access, and must go to memory every time. Changing the loop above to while (!READ_ONCE(flag)) makes the compiler reload flag on every iteration, and the loop exits as soon as the flag is set. It also prevents the tearing described in 1.1: volatile makes the access one complete read or write within the machine word size, never split in two. compiletime_assert_rwonce_type stands guard at compile time: use the macro on a type wider than the machine word, which cannot be accessed atomically in one go, and the build fails, catching the problem before it ships.

READ_ONCE/WRITE_ONCE cover a single access to a single variable, but not the order between statements. When the constraint is “finish writing A before writing B, and do not swap them”, we need a coarser tool, the compiler barrier:

#define barrier() asm volatile("" ::: "memory")

It is an empty piece of inline assembly that executes nothing; the trick is the trailing "memory" clobber. It tells the compiler that at this point anything in memory may have changed, so values loaded before this line must not be reused after it. As a result, the compiler will not move memory accesses across the barrier. Keep its limit in mind, though: it stops the compiler, not the CPU. The CPU can still reorder at run time; that is a separate problem, handled by the hardware barriers in 1.5. And precisely because x86 is strongly ordered, its smp_rmb/smp_wmb reduce to this barrier().

One point needs to be nailed down: both tools in this section act only at compile time, on the way from source to assembly, and generate no barrier instructions.

  • READ_ONCE/WRITE_ONCE use a volatile cast to constrain how the compiler emits memory accesses: it must actually emit a load or store, and may not keep the value in a register, merge accesses or delete them. They produce no extra CPU instructions (such as mfence or a lock prefix); the result is still an ordinary mov.
  • barrier() is the empty assembly asm volatile("" ::: "memory"). It generates no machine instructions; it only forbids the compiler from reordering the instructions it emits across that point.

The mechanisms that actually constrain run-time CPU reordering, and that emit a LOCK prefix or mfence/lfence/sfence, come later: atomic instructions in 1.3 and memory barriers in 1.5.

In one sentence: READ_ONCE/WRITE_ONCE ensure that this particular access to a variable really happens and is not torn, and barrier() ensures that the compiler does not move code across this point. Together they deal with problems the compiler causes; the visibility order between CPUs has to wait for the hardware barriers in 1.5.

Summary of this section: READ_ONCE/WRITE_ONCE and barrier() are the two lowest bricks of the entire atomic and locking machinery, and every layer above is built on them. This and later chapters will not explain them again, but will use them constantly. atomic_read/atomic_set (1.3) are thin wrappers around READ_ONCE/WRITE_ONCE. The acquire/release barriers smp_load_acquire/smp_store_release (1.6) are READ_ONCE/WRITE_ONCE plus a barrier(). And when spinlock, qspinlock and rwsem spin on the lock state, they read it with accesses such as READ_ONCE(lock->val), relying on exactly the guarantee from this section: every iteration really rereads memory and is never optimized into an endless loop. Keep this in mind and you will recognize these two foundations immediately in the source of any lock.

1.3 Atomic Types and Atomic Operations

atomic_t itself is surprisingly plain: an aligned int (include/linux/types.h):

typedef struct {
	int __aligned(sizeof(int)) counter;
} atomic_t;

The struct wrapper exists for type safety: it forces every access through the atomic_* API and rules out a bare v.counter++. Type safety is only the surface, though; the atomicity itself comes from the hardware. This section is the first place in the chapter where we cross the line between software and hardware. READ_ONCE and barrier() in 1.2 only constrain the compiler and generate no extra instructions. Starting with the atomic RMW in this section, we reach the level of CPU instructions: on x86, the LOCK prefix locks the cache line (modern implementations rely on the cache coherence protocol rather than locking the bus), and the hardware guarantees that the read-modify-write cannot be interrupted. See arch/x86/include/asm/atomic.h:

static __always_inline int arch_atomic_read(const atomic_t *v)
{
	return __READ_ONCE((v)->counter);      /* an aligned read is atomic by itself; no LOCK needed */
}

static __always_inline void arch_atomic_add(int i, atomic_t *v)
{
	asm_inline volatile(LOCK_PREFIX "addl %1, %0"
		     : "+m" (v->counter)
		     : "ir" (i) : "memory");   /* RMW: LOCK required */
}

static __always_inline int arch_atomic_add_return(int i, atomic_t *v)
{
	return i + xadd(&v->counter, i);       /* with a return value: xadd atomically fetches the old value */
}

Note that read and set do not need LOCK: on x86, aligned word-sized reads and writes are inherently atomic, so READ_ONCE/WRITE_ONCE (the compile-time control from 1.2) are enough to keep the compiler from interfering. LOCK is needed only for compound operations such as read-modify-write.

Look closely at LOCK_PREFIX in this code, because it marks the boundary between software and hardware. It is defined in arch/x86/include/asm/alternative.h. In an SMP kernel it expands to a real lock prefix (opcode 0xF0) placed in front of addl or cmpxchgl, and the CPU guarantees that the instruction is atomic. In a uniprocessor (UP) kernel it expands to an empty string and no prefix is emitted at all. In other words, LOCK_PREFIX is a genuine hardware instruction prefix, in sharp contrast to barrier() and volatile from 1.2, which generate no instructions. At this level, we are standing on the hardware.

Atomic operations therefore fall into three groups:

  • Plain reads and writes: atomic_read / atomic_set.
  • RMW without a return value: atomic_add / sub / inc / dec, which modify the value and do not report the result.
  • RMW with a return value or a condition: atomic_add_return (using xadd) and atomic_dec_and_test / inc_and_test (using GEN_UNARY_RMWcc, which reads the CPU flags directly to tell whether the result is zero). This third group does most of the work in reference counting and lock-free algorithms.

1.4 cmpxchg: The Common Foundation of Lock-Free Code and Lock Fast Paths

If the atomic operations above are parts, cmpxchg (compare-and-swap, CAS) is the universal connector that assembles them into any lock-free algorithm. Its semantics: if the current value in memory equals the expected old value, write the new value; in either case, return the original value. The x86 implementation is in arch/x86/include/asm/cmpxchg.h:

#define __raw_cmpxchg(ptr, old, new, size, lock)			\
({									\
	...								\
	case __X86_CASE_L:						\
	{								\
		volatile u32 *__ptr = (volatile u32 *)(ptr);		\
		asm_inline volatile(lock "cmpxchgl %2, %1"		\
			     : "=a" (__ret), "+m" (*__ptr)		\
			     : "r" (__new), "0" (__old)			\
			     : "memory");				\
		break;							\
	}								\
	...								\
})

#define arch_cmpxchg(ptr, old, new)					\
	__cmpxchg(ptr, old, new, sizeof(*(ptr)))   /* with LOCK_PREFIX */

The lock here is nothing new; it is the LOCK_PREFIX from 1.3. __raw_cmpxchg turns it into a macro parameter so that one assembly template serves two variants. arch_cmpxchg goes through __cmpxchg, which passes LOCK_PREFIX (a real lock prefix under SMP) and is atomic across CPUs. arch_cmpxchg_local goes through __cmpxchg_local, which passes an empty string; it only protects against interrupts on the local CPU and drops the prefix to run faster. So the atomicity of cmpxchg still rests on the hardware line drawn in 1.3.

With CAS, any update of the form “read the old value, compute a new value, swap it in atomically” can be written as a retry loop:

old = READ_ONCE(v);
do {
	new = f(old);
} while (!try_cmpxchg(&v, &old, new));   /* on failure, old is refreshed with the latest value; try again */

The importance of this pattern is hard to overstate: the fast path of every lock that follows is essentially one CAS. mutex uses CAS to change the owner from NULL to current, qspinlock uses it to grab the pending bit, and rwsem uses it to update the count. Understand this loop and you understand the skeleton of every lock fast path. (CAS has a classic pitfall, the ABA problem: a value changes from A to B and back to A, and CAS wrongly concludes that it never changed. It is discussed in the chapters on RCU and lock-free data structures.)

1.5 Memory Barriers: Four Basic Barriers and Their CPU Implementation

Atomic operations make a single operation indivisible, but they say nothing about the visibility order between operations. Consider the classic message-passing example:

CPU 0:  data = 42;          CPU 1:  while (!flag) ;
        flag = 1;                   r = data;

Even though the writes to data and flag are each atomic, CPU 1 may see flag == 1 and still read the old value of data: the two writes may drain from CPU 0’s store buffer out of order, or CPU 1 may execute its two reads out of order. Fixing this requires barriers. The kernel’s four basic barriers and their x86 implementation are in arch/x86/include/asm/barrier.h:

#define __mb()	asm volatile("mfence":::"memory")   /* full barrier: neither reads nor writes cross it */
#define __rmb()	asm volatile("lfence":::"memory")   /* read barrier */
#define __wmb()	asm volatile("sfence" ::: "memory") /* write barrier */

#define __smp_mb()	asm volatile("lock addl $0,-4(%%" _ASM_SP ")" ::: "memory", "cc")
#define __smp_rmb()	dma_rmb()
#define __smp_wmb()	barrier()

A few key points:

  • mb/rmb/wmb are for interaction with devices (MMIO and DMA) and map to mfence/lfence/sfence.
  • smp_mb/smp_rmb/smp_wmb order accesses between CPUs. x86 is strongly ordered: the CPU never reorders ordinary reads with other reads, or writes with other writes, so smp_rmb/smp_wmb reduce to compiler barriers. The only reordering x86 allows is a later read passing an earlier write, so smp_mb must be a real barrier. It uses lock addl $0, -4(%rsp) (a locked add of zero to the top of the stack) as a full barrier, which is faster than mfence.
  • On weakly ordered architectures (ARM64, PowerPC and others), smp_rmb/smp_wmb are real barrier instructions. This is why portable code must spell out its barriers instead of relying on x86’s strong ordering.

Following the software/hardware line drawn in 1.3, the barriers can also be sorted by whether they generate hardware instructions:

BarrierEmitted on x86Hardware instruction?
mb / rmb / wmbmfence / lfence / sfenceYes
smp_mblock addl $0, -4(%rsp)Yes (through the lock prefix)
smp_rmb / smp_wmbReduce to barrier()No, compile time only

The key point: whether the same barrier becomes a hardware instruction depends on how strongly ordered the target architecture is. smp_wmb() is an empty barrier() on x86 (the compile-time control from 1.2) but becomes a real dmb instruction on ARM64. This also explains the previous point: leaving out smp_wmb on x86 often happens to work, and breaks as soon as the code is ported to a weakly ordered architecture.

1.6 Acquire and Release: The Ordering Model Locks Actually Rely On

A full barrier gives strong guarantees but is expensive. What a lock actually needs is a cheaper, one-way ordering: accesses inside the critical section must not leak outside it. That is the acquire/release model:

  • acquire (used when taking a lock): no access after it may be reordered before it.
  • release (used when releasing a lock): no access before it may be reordered after it.

Placed on either side of the critical section, the pair keeps its reads and writes inside. The x86 implementation is in arch/x86/include/asm/barrier.h:

#define __smp_store_release(p, v)					\
do {									\
	compiletime_assert_atomic_type(*p);				\
	barrier();							\
	WRITE_ONCE(*p, v);						\
} while (0)

#define __smp_load_acquire(p)						\
({									\
	typeof(*p) ___p1 = READ_ONCE(*p);				\
	compiletime_assert_atomic_type(*p);				\
	barrier();							\
	___p1;								\
})

On strongly ordered x86, acquire and release need no real barrier instructions: a compiler barrier barrier() plus READ_ONCE/WRITE_ONCE is enough, because the hardware already guarantees every ordering except a read passing an earlier write. This is why unlocking can be so cheap on x86: a single ordinary write with release semantics. But this is an x86 bonus. On weakly ordered architectures such as ARM64, acquire and release use dedicated hardware instructions (such as ldar/stlr), and unlocking is no longer an ordinary write, just as smp_wmb in the table in 1.5 reduces to nothing on x86 but becomes a real instruction on weakly ordered machines. For the same reason, the barriers around atomic operations are empty on x86:

#define __smp_mb__before_atomic()	do { } while (0)
#define __smp_mb__after_atomic()	do { } while (0)

An atomic operation with a LOCK prefix is itself a full barrier, so nothing needs to be added. Thinking of lock as acquire and unlock as release is the ordering model that underlies every lock chapter that follows.

1.7 The Three Layers of the Kernel Atomic API

Reading the source, you will find several names for atomic_add: arch_atomic_add, raw_atomic_add and atomic_add. This is not duplication but a deliberate three-layer structure:

  1. arch_atomic_*: the architecture-specific implementation, such as the x86 LOCK_PREFIX "addl" above. An architecture only has to implement a minimal set.
  2. The fallback layer (include/linux/atomic/atomic-arch-fallback.h): scripts fill in every variant from the minimal set (for example, if an architecture does not implement add_return, it is synthesized from a cmpxchg loop).
  3. The instrumented atomic_* layer (include/linux/atomic/atomic-instrumented.h): the public API, wrapped with KASAN/KCSAN instrumentation for detecting concurrency bugs.

Almost all of these three layers are generated by the scripts under scripts/atomic/. The point of the layering: whoever ports the kernel to a new architecture writes only the minimal assembly, and the generic variants and debugging instrumentation come from the common layers, which saves work and keeps behavior consistent. Everyday driver code uses only the top-level atomic_* and never needs to care about the two layers below.

1.8 Assembling the Foundations into a Lock

Now let us use the parts from this chapter to write a minimal spinlock by hand, and check the formula “lock = acquire with CAS + release + waiting strategy”:

struct minimal_lock { atomic_t locked; };   /* 0 = free, 1 = held */

static void minimal_lock(struct minimal_lock *l)
{
	int expected;
	do {
		expected = 0;
		/* CAS to take the lock: swap 0 for 1; success means we hold it (acquire semantics) */
	} while (!atomic_try_cmpxchg_acquire(&l->locked, &expected, 1));
}

static void minimal_unlock(struct minimal_lock *l)
{
	/* write 0 with release semantics so every write in the critical section is visible to others */
	atomic_set_release(&l->locked, 0);
}

Item by item: atomic_try_cmpxchg_acquire is the CAS from 1.4 plus the acquire from 1.6; atomic_set_release is the release from 1.6; the empty spin in the do-while loop is the waiting strategy. This lock works, but its waiting strategy is too primitive: every contender spins writing the same locked variable, causing heavy cache-line bouncing. In Chapter 2, qspinlock replaces this bare spinning with an MCS queue in which each waiter spins on its own local node. That is the line between a lock that works and a lock that scales.

1.9 Misuse and Debugging

The most common pitfalls at this level:

  • Treating a bare v++ as atomic: updates are lost on multicore systems. Use atomic_inc or a cmpxchg loop.
  • Leaving out READ_ONCE/WRITE_ONCE: polling a shared flag with while (!flag) lets the compiler keep flag in a register and spin forever. Write while (!READ_ONCE(flag)).
  • Unpaired barriers: a writer using smp_store_release needs a reader using smp_load_acquire. A barrier on one side only gives no ordering guarantee; both ends of a message-passing pattern need one.
  • Trusting x86’s strong ordering: leaving out smp_rmb/smp_wmb on x86 often happens to work and breaks immediately on ARM64. Reason about portable code with a weakly ordered model.

Debugging tools: enable CONFIG_KCSAN for run-time data race detection; it catches most concurrent accesses that are missing READ_ONCE or atomic operations. For intricate ordering arguments, Documentation/memory-barriers.txt is the authoritative reference inside the kernel, and tools/memory-model/ contains a formal model (LKMM) you can check your reasoning against. Deadlock detection at the lock-ordering level (lockdep) is covered in the chapter on tools.


Summary

Every lock rests on two foundations. Atomic operations use the LOCK prefix and cmpxchg to make read-modify-write indivisible, preventing lost updates and tearing. Memory barriers constrain the visibility order between CPUs, and the one-way acquire/release pair is exactly the minimal model that keeps a critical section from leaking: lock is acquire, unlock is release. READ_ONCE/WRITE_ONCE keep a single access atomic and safe from optimization, and cmpxchg is the common connector of every lock fast path and lock-free algorithm. x86’s strong ordering reduces many barriers to nothing, but the right mental model is the weakly ordered one. With the formula “lock = atomics + barriers + waiting strategy” in hand, the next chapter takes apart the first real lock, from the simplest spinlock to qspinlock, which uses an MCS queue to eliminate contention.