vault

Queued Spinlocks and qspinlock

16 min read

Queued Spinlocks and qspinlock

The queued spinlock (qspinlock) is the implementation that actually backs a kernel spinlock_t on every contemporary SMP architecture — it is what arch_spin_lock() resolves to. It is built on the MCS lock (named for its inventors John Mellor-Crummey and Michael Scott), whose key property is that each waiting CPU spins on its own private memory location rather than on the shared lock word. This eliminates the cache-line storm that plagues a naive test-and-set or ticket spinlock: when the holder of a contended ticket lock releases, every waiting CPU’s cached copy of the lock word is invalidated and they all re-read it across the interconnect, so contention cost grows with the number of waiters. With MCS, a release touches only the next waiter’s cache line — exactly one invalidation. qspinlock is the kernel’s clever compression of the MCS idea into the single 32-bit word that a spinlock_t must remain, by encoding a locked byte, a pending bit, and a tail pointer into one atomic_t (qspinlock.c, v6.12). It became the default x86 spinlock in Linux 4.2 (2015), replacing the ticket lock (Kernel Newbies, Linux 4.2).

This note explains why the queued design beats the ticket lock under contention, walks the 32-bit word layout, and traces the three acquisition paths — uncontended, one-waiter (pending), and queued (≥2 waiters) — plus the paravirtualized variant for virtual machines. The contract and API of spinlock_t itself (the no-sleep rule, preemption disabling) live in the sibling note Kernel Spinlocks.

Uncertain

Verify: “default x86 spinlock since Linux 4.2 (2015).” Reason: confirmed by the Linux 4.2 release notes (“Queued spinlocks become the default spinlock implementation”) and Phoronix, which are reliable secondary sources, and consistent with the qspinlock_types.h copyright “(C) Copyright 2013-2015”; not cross-checked against the merge commit or git log directly. To resolve: confirm against the merging commit a33fda35e3a7 and the 4.2 merge window pull. uncertain

Mental Model: Why Spinning on a Shared Word Is Pathological

To see what qspinlock fixes, picture the lock it replaced. A ticket spinlock is like a deli counter: the lock word holds two 16-bit counters, head and tail. To acquire, you atomically increment tail and remember your ticket number; you then spin reading head until it equals your number. To release, you increment head. This is fair (FIFO) and simple, but it has a fatal scaling flaw: every waiter spins reading the same shared head field. On a cache-coherent multiprocessor, when the holder writes head on release, the hardware coherence protocol (MESI) must invalidate that cache line in every CPU that had it cached for reading — and all N waiters had it cached. All N then take a coherence miss and re-fetch the line across the interconnect, but only one of them (the next ticket) actually gets to proceed; the other N−1 re-cache the line only to keep spinning. Each release thus generates O(N) cross-CPU cache traffic. On a multi-socket NUMA box this is catastrophic — the LWN write-ups on the topic measured the ticket lock collapsing under heavy contention (LWN, “MCS locks and qspinlocks”).

The MCS lock breaks the storm by giving each waiter its own node to spin on. Waiters form an explicit linked list (a queue). Each CPU enqueues a small per-CPU mcs_spinlock node and then spins on node->locked — a field that only its predecessor will ever write. When the holder releases, it writes 1 into only the next node’s locked field, invalidating exactly one cache line on exactly one CPU. Release cost is now O(1) regardless of how many CPUs are queued.

flowchart LR
  subgraph TICKET["Ticket lock release (the storm)"]
    H["holder writes head"] --> I1["invalidate CPU1 line"]
    H --> I2["invalidate CPU2 line"]
    H --> I3["invalidate CPU3 line"]
    H --> IN["invalidate CPU-N line"]
    I1 --> R["all re-read shared word<br/>O(N) coherence traffic"]
    I2 --> R
    I3 --> R
    IN --> R
  end
  subgraph MCS["MCS / qspinlock release (quiet)"]
    HM["holder sets next->locked=1"] --> ONE["invalidate ONE line<br/>on the NEXT waiter only"]
    ONE --> PROC["next waiter proceeds<br/>O(1) traffic"]
  end

Why queued beats ticket under contention. What it shows: a ticket-lock release writes the single shared head word, which the coherence protocol must invalidate in every waiter’s cache, forcing all N waiters to re-fetch it — O(N) interconnect traffic per handoff. An MCS/qspinlock release instead writes only the next queued node’s private locked flag, touching exactly one remote cache line. The insight to take: the win is not about spinning being cheaper per se — both spin — it is that the cost of a lock handoff stops scaling with the number of waiters. This is what lets qspinlock hold up on 4-socket-plus NUMA machines where the ticket lock fell over.

The Compression Problem and the 32-bit Word Layout

A textbook MCS lock needs a tail pointer (8 bytes on 64-bit) in the lock itself, plus each node carries a next pointer (another 8 bytes). That is far too big: a spinlock_t must stay 4 bytes to preserve every existing struct layout and the lock API. The qspinlock insight, spelled out in the header comment of qspinlock.c, is to compress {tail, locked} into a single 32-bit word and add a one-waiter fast path so the MCS queue is only used when ≥2 CPUs contend (qspinlock.c, v6.12).

The single atomic_t val is partitioned as follows, from qspinlock_types.h (v6.12):

 When NR_CPUS < 16K (the common case):
  bits  0- 7:  locked byte   (1 = some CPU owns the lock)
  bit      8:  pending       (one CPU is the designated next owner)
  bits  9-15:  unused
  bits 16-17:  tail index    (which of the 4 per-CPU nodes: task/softirq/hardirq/nmi)
  bits 18-31:  tail cpu (+1)  (CPU number of the queue tail, +1 so that 0 = "no tail")

Three design choices in this layout are worth unpacking:

  • The lock is a full byte, not a single bit. Only one bit is logically needed, but a whole byte (_Q_LOCKED_BITS == 8) is used “to achieve better performance for architectures that support atomic byte write” — release can be a single-byte store (smp_store_release(&lock->locked, 0)) instead of a read-modify-write on the whole word. The type even exposes a u8 locked and u8 pending via an endian-aware union so these can be written byte-wise.
  • The tail encodes a CPU plus a node index, not a pointer. Because a spinlock is non-recursive within a single context but a CPU can hold spinlocks at up to four nesting levels (task, softirq, hardirq, NMI), the tail records which CPU is at the tail and which of that CPU’s four per-CPU MCS nodes (MAX_NODES == 4) it is using. The CPU number is stored +1 so that an all-zero tail unambiguously means “queue is empty” rather than “CPU 0” — encode_tail() does (cpu + 1) << _Q_TAIL_CPU_OFFSET, and decode_tail() subtracts 1 and uses per_cpu_ptr(&qnodes[idx].mcs, cpu) to recover the real node (qspinlock.c).
  • The next pointer lives in the per-CPU node, not the lock. The lock word only holds the tail. Each queued node’s next field (in struct mcs_spinlock) chains forward to the node behind it. The head spinner spins on the lock byte; every other waiter spins on its own node’s locked field. This is the trick that keeps the lock 4 bytes while preserving MCS’s per-CPU-spin property.

The mcs_spinlock node itself is tiny (mcs_spinlock.h, v6.12):

struct mcs_spinlock {
    struct mcs_spinlock *next;  /* who is queued behind me */
    int locked;                 /* 1 once my predecessor hands me the lock */
    int count;                  /* nesting level (task/softirq/hardirq/nmi) */
};

Four of these are allocated per CPU as qnodes[MAX_NODES], sized so that on a 64-bit machine all four fit in one 64-byte cache line.

Walk-through: The Three Acquisition Paths

queued_spin_lock() itself is the fast path and is trivially short (asm-generic/qspinlock.h):

static __always_inline void queued_spin_lock(struct qspinlock *lock)
{
    int val = 0;
    if (likely(atomic_try_cmpxchg_acquire(&lock->val, &val, _Q_LOCKED_VAL)))
        return;                               /* (0,0,0) -> (0,0,1): uncontended win */
    queued_spin_lock_slowpath(lock, val);     /* anything else: go handle contention */
}

The notation (tail, pending, locked) is used throughout the source comments. The fast path is one atomic compare-and-swap: if the whole word is zero ((0,0,0), fully free) swap in _Q_LOCKED_VAL (set the locked byte → (0,0,1)) with acquire ordering and return. See Compare-and-Swap and cmpxchg in the Kernel for the semantics of atomic_try_cmpxchg_acquire. If the word was non-zero, control falls into queued_spin_lock_slowpath(), which has two sub-paths.

The pending path — exactly one waiter. This is the cleverest optimization and the reason the common “two CPUs briefly collide” case never touches the MCS queue at all. When the slow path sees the lock held but no queue yet, it sets the pending bit via queued_fetch_set_pending_acquire() (an atomic_fetch_or_acquire of _Q_PENDING_VAL). The pending bit means “I am the designated next owner.” The CPU then spins with smp_cond_load_acquire(&lock->locked, !VAL) — waiting for just the locked byte to clear, spinning on the lock word but as the sole pending waiter. When the holder releases (clears the locked byte), this CPU does clear_pending_set_locked(): it atomically clears pending and sets locked in one go ((0,1,0) -> (0,0,1)), taking ownership. So with one holder and one waiter, no per-CPU node is ever allocated and no queue is built — the handoff is a couple of atomics on the word. This is the case the kernel optimizes hardest because brief two-way contention is by far the most common.

The queued path — two or more waiters. If a CPU arrives and finds the lock held and pending already set (or a tail already present), it must join the MCS queue. The sequence in queued_spin_lock_slowpath() is:

  1. Grab this CPU’s MCS node: node = this_cpu_ptr(&qnodes[0].mcs), then index by nesting level idx = node->count++ and node = grab_mcs_node(node, idx). (If idx >= MAX_NODES — more than 4 nested contexts, essentially never — it falls back to a plain trylock spin loop.)
  2. Initialize the node: node->locked = 0; node->next = NULL;. A barrier() ensures the count++ lands before the node init so an interrupt can’t corrupt it.
  3. Encode this node into a tail code word and publish it atomically: old = xchg_tail(lock, tail). The xchg returns the previous tail. An smp_wmb() before this guarantees the node is fully initialized before it becomes reachable.
  4. If old held a previous tail (old & _Q_TAIL_MASK), this CPU is not the head of the queue: decode the predecessor node, link into it with WRITE_ONCE(prev->next, node), and then spin on its own node: arch_mcs_spin_lock_contended(&node->locked), which is smp_cond_load_acquire(l, VAL) — wait until the predecessor sets node->locked to 1. This is the cache-friendly spin: the CPU reads only its own private node, untouched by anyone but its single predecessor.
  5. Once at the head of the queue (predecessor handed off, or there was no predecessor), spin on the lock word waiting for both locked and pending to clear: val = atomic_cond_read_acquire(&lock->val, !(VAL & _Q_LOCKED_PENDING_MASK)). The head waiter is the one CPU that legitimately spins on the shared word — there is only ever one of it.
  6. Claim the lock. If this node is also the tail (no one queued behind), try atomic_try_cmpxchg_relaxed(&lock->val, &val, _Q_LOCKED_VAL) to atomically swap the whole word to just-locked, clearing the tail. If someone is queued behind, just set_locked(lock) and then hand off to the successor: arch_mcs_spin_unlock_contended(&next->locked) writes 1 into the next node’s locked, releasing exactly that one CPU.

The release side is unchanged from the fast case — queued_spin_unlock() is smp_store_release(&lock->locked, 0), a single byte store with release ordering. The MCS hand-off (step 6) is what actually passes ownership down the queue; the lock-byte store is what lets the head spinner notice the lock is free. The smp_wmb(), the acquire/release pairings, and smp_cond_load_acquire() are not optional decorations — qspinlock’s header explicitly notes it “relies on atomic_release()/atomic_acquire() to be RCsc” and on mixed-size atomics (it needs a working xchg16), which is why some weakly-ordered architectures cannot use it. See Memory Barriers in the Linux Kernel and Acquire Release and Fence Semantics.

Paravirt qspinlock — Surviving Lock-Holder Preemption

qspinlock has one assumption that a bare-metal kernel can take for granted but a virtual machine guest cannot: that the CPU holding the lock keeps running. In a VM, the hypervisor can deschedule a virtual CPU (vCPU) at any instant. If it deschedules the lock holder, every other vCPU spinning for that lock burns its entire time slice waiting for a holder that is not even on a physical CPU — the lock-holder preemption (LHP) problem. Worse, with the strictly-FIFO MCS queue, if the hypervisor preempts a vCPU in the middle of the queue, every vCPU behind it is blocked even though the actual holder may have long since released — the lock-waiter preemption problem. A plain queued lock can collapse virtualized throughput.

The fix is paravirtualized qspinlock (pv_qspinlock), enabled by CONFIG_PARAVIRT_SPINLOCKS and used when the kernel detects it is a guest under a cooperating hypervisor (KVM, Xen). It is generated from the same qspinlock.c source compiled a second time with _GEN_PV_LOCK_SLOWPATH defined, which swaps the no-op PV hooks for real ones (qspinlock.c, qspinlock_paravirt.h, v6.12). The core idea, stated in the PV header: “halt the vcpus instead [of spinning]” using two hypercalls — pv_wait(ptr, val) suspends the calling vCPU while *ptr == val, and pv_kick(cpu) wakes a suspended vCPU. The mechanism:

  • A queued vCPU spins for a bounded SPIN_THRESHOLD. If it still has not been handed the lock, instead of spinning forever it sets its node state to vcpu_halted and calls pv_wait() — yielding the physical CPU back to the hypervisor rather than wasting it.
  • Because the predecessor must be able to find and wake a halted successor, and the lock word has no room for a pointer, the PV code maintains a global hash table (pv_hash) keyed by lock address that maps a lock to the pv_node of its halted head waiter. On release, __pv_queued_spin_unlock() checks whether the lock byte is the special _Q_SLOW_VAL (3) — the marker that a waiter went to sleep — and if so, looks up the waiter in the hash and issues pv_kick() to wake it.
  • pv_kick_node() and pv_wait_head_or_lock() advance waiter states so a vCPU isn’t woken only to immediately re-sleep, and they allow a small amount of lock stealing (a running vCPU can grab a lock ahead of a sleeping queue head) to mitigate waiter preemption — which is why the PV path tolerates n,0,1 -> 0,0,1 transitions the native path never sees.

The trade-off: PV qspinlock spends extra memory (the per-CPU pv_node doubles the node storage, padding qnode with long reserved[2]) and adds hypercall overhead, but it converts a potential throughput collapse under LHP into graceful degradation. It can be disabled with the nopvspin kernel boot parameter. See Linux Virtualization MOC for the broader paravirt picture.

Configuration and How to Confirm It’s Active

qspinlock is selected, not chosen at runtime: an architecture opts in via select ARCH_USE_QUEUED_SPINLOCKS in its Kconfig (x86 does, at arch/x86/Kconfig, v6.12), which makes CONFIG_QUEUED_SPINLOCKS def_bool y for SMP builds (kernel/Kconfig.locks, v6.12). When set, <asm/qspinlock.h> remaps arch_spin_lock() and friends onto the queued_spin_* functions, so every spinlock_t in the kernel transparently uses it. On a running x86-64 system you can confirm with zgrep CONFIG_QUEUED_SPINLOCKS /proc/config.gz (expect =y) and grep -c '' /proc/config.gz | ... for the paravirt option CONFIG_PARAVIRT_SPINLOCKS. There is no per-lock opt-out: a uniprocessor (CONFIG_SMP=n) build compiles spinlocks away to bare preemption toggles, and PREEMPT_RT replaces spinlock_t with an rt-mutex entirely (see Raw Spinlocks and PREEMPT_RT).

Failure Modes and Common Misunderstandings

“qspinlock is fair like the ticket lock.” Mostly, but not in the PV path. The native MCS queue is strictly FIFO, so it is fair. But the pending fast path lets a brand-new arrival grab the lock ahead of CPUs that would otherwise queue, and the PV path deliberately permits limited lock stealing to dodge waiter preemption. So qspinlock is “fair under sustained contention, opportunistic under light contention.”

“The waiter spins on the lock word.” Only the head waiter does. A frequent misreading. The head of the MCS queue spins on the shared lock byte (there is exactly one such CPU). Every other queued CPU spins on its own private node->locked. Conflating the two loses the entire scalability argument.

Stalls from a non-running holder, on bare metal. If qspinlock (native, not PV) is used inside a VM by accident — or if a holder is stuck (e.g. an NMI storm) — waiters spin uselessly. On bare metal this manifests as a watchdog: BUG: soft lockup if a holder loops too long. The virt_spin_lock() hook exists so a guest without full PV support can fall back to a simple test-and-set that at least doesn’t enforce FIFO ordering against a preempted holder.

More than 4 nesting levels. The 4-node-per-CPU assumption (task/softirq/hardirq/NMI) is violated only by nested NMIs taking spinlocks — pathological. The code handles it by falling back to a plain while (!queued_spin_trylock(lock)) cpu_relax(); loop with no MCS node, accepting unfairness for that vanishingly rare case.

Alternatives and When They Apply

qspinlock is not a choice you make in code — it is the implementation of spin_lock(), so “when to use it” is really “when to use a spinlock,” answered in Kernel Spinlocks. The historically relevant alternative is the ticket spinlock it replaced: still available as asm-generic/ticket-spinlock.h and used by architectures that lack the cheap mixed-size atomics (xchg16) qspinlock requires, or whose contention profile (few CPUs, single socket) never triggered the storm. The qspinlock.h header is explicit that an architecture “looking for a ‘generic’ spinlock, please first consider ticket-lock.h and only come looking here when you’ve considered all the constraints below and can show your hardware does actually perform better with qspinlock.” For read-mostly workloads, the right move is to avoid the spinlock entirely with seqlocks or RCU; for the reader/writer-asymmetric case there is the queued rwlock.

Production Notes

qspinlock is the workhorse under essentially every hot spinlock_t in the kernel — scheduler run-queues, the slab allocator, network packet queues, filesystem inode locks. Its merge in 4.2 was driven by measured ticket-lock collapse on large NUMA servers; Hewlett-Packard’s Waiman Long (the primary author, per the file copyrights) reported double-digit-percent throughput gains on I/O- and interrupt-heavy multi-socket workloads (Phoronix). The PV variant matters most in cloud fleets: KVM and Xen guests rely on it so that an oversubscribed host (more vCPUs than physical CPUs) does not turn every contended lock into a time-slice-burning spin. When tuning, the two knobs that surface are the nopvspin boot parameter (force native spinning, useful when measuring) and the lock-event counters exposed under debugfs (lock_pending, lock_slowpath, lock_no_node, built when CONFIG_LOCK_EVENT_COUNTS is on) that let you see how often locks take the fast, pending, and queued paths in practice.

See Also

Graph View

Backlinks