vault

Adaptive Mutex Spinning and Optimistic Spinning

20 min read

Adaptive Mutex Spinning and Optimistic Spinning

Optimistic spinning — the “midpath” of a Linux kernel sleeping lock — is the optimization that lets a contending task busy-wait instead of going to sleep, as long as the lock’s current owner is still running on another CPU. The bet is simple: if the owner is on a CPU right now, it is probably inside a short critical section and will release the lock within a few cycles, so spinning a moment is cheaper than the round-trip cost of a context switch out, a scheduler pass, and a wake-up later. The moment that bet looks bad — the owner blocks, gets descheduled, or the spinner itself is asked to reschedule — the spin aborts and the task falls through to the real sleep path. This is what makes a struct mutex behave as a hybrid lock: “spin if it’ll be quick, sleep if it’ll be long,” and it is the single reason Linux mutexes are nearly as fast as spinlocks under short contention (per Documentation/locking/mutex-design.rst, v6.12; the original mechanism was Zijlstra’s 2009 “mutex: implement adaptive spinning” patch). The same machinery is shared by writers of the [[Read-Write Semaphores|read/write semaphore (rw_semaphore)]]. This note describes the kernel as of 6.12 LTS.

The midpath is the middle of three acquisition attempts. See Kernel Mutexes for the fastpath (an uncontended cmpxchg) and the slowpath (enqueue on a wait list and sleep); this note is exclusively about what happens between them.

Mental Model

The right way to think about optimistic spinning is as a gamble on the owner’s near future, hedged by a single-file queue so the gamblers do not trample each other.

The gamble: sleeping is expensive. Putting a task to sleep means saving its register state, removing it from the run queue, picking another task, switching address spaces and stacks, and later doing the reverse on wake-up — plus the cache pollution of running an unrelated task in between. If the lock will be free in 200 nanoseconds, paying microseconds of scheduler overhead to sleep through those 200 ns is a terrible trade. So the kernel asks one question before sleeping: is the owner running right now? If yes, the critical section is in progress and almost certainly short (long-held mutexes block on I/O, and a blocked owner is not “running”), so spin. If the owner is not running — it went to sleep itself, or the scheduler descheduled it — then there is no telling how long the wait is, and spinning would burn a whole CPU for nothing. Sleep.

The hedge: if every waiter independently spun on the same owner field, you would get a stampede. Dozens of CPUs reading and racing on one cache line is exactly the cache-line bouncing that fair spinlocks were invented to avoid (Corbet, “Preventing overly-optimistic spinning,” LWN 2010). So the kernel funnels spinners through an MCS queue (the osq_lock): only the head of the queue actually competes for the mutex; everyone else spins quietly on their own per-CPU cache line, waiting to be promoted to head.

flowchart TD
  W["Waiter wants mutex<br/>(fastpath cmpxchg already failed)"] --> CAN{"mutex_can_spin_on_owner:<br/>need_resched?<br/>owner running on a CPU?"}
  CAN -->|"no — bail"| SLEEP["Slowpath:<br/>enqueue on wait list, sleep"]
  CAN -->|"yes"| OSQ["osq_lock: join MCS queue"]
  OSQ -->|"not head yet"| SPINNODE["Spin on OWN node->locked<br/>(per-CPU cache line)"]
  SPINNODE -->|"need_resched or<br/>vCPU preempted"| UNQ["Cancel: unqueue from MCS list"] --> SLEEP
  SPINNODE -->|"promoted to head"| HEAD
  OSQ -->|"became head"| HEAD["Queue head: only spinner<br/>competing for the mutex"]
  HEAD --> TRY{"__mutex_trylock_or_owner"}
  TRY -->|"got it (owner==NULL)"| WON["osq_unlock, return true<br/>(midpath WIN)"]
  TRY -->|"still owned"| SOO{"mutex_spin_on_owner:<br/>owner still == owner<br/>AND owner_on_cpu<br/>AND !need_resched"}
  SOO -->|"loop: cpu_relax()"| TRY
  SOO -->|"owner changed / slept /<br/>need_resched"| FAILU["osq_unlock, return false"] --> SLEEP

The decision flow of mutex_optimistic_spin() in v6.12. What it shows: two nested gates. The outer gate (mutex_can_spin_on_owner) decides whether spinning is even worth attempting; the MCS queue (osq_lock) serializes everyone so only the head reaches the inner loop; the inner loop (mutex_spin_on_owner) keeps spinning only while the same owner stays on a CPU. The insight to take: every path out of the spin leads either to a quick WIN (the owner released and the head grabbed it) or to a clean fall-through into the ordinary sleep slowpath. The spin is bounded — it never spins on a sleeping owner — which is what makes the gamble safe.

Mechanical Walk-through

The outer gate: should we spin at all?

When a task fails the fastpath and enters the mutex slowpath, the first thing the slowpath does (before touching the wait list) is call mutex_optimistic_spin(). For a fresh contender — one that has not yet been placed on the wait list (waiter == NULL) — the function first asks mutex_can_spin_on_owner() whether spinning makes sense. That helper reads the current owner out of the lock’s owner field and applies two tests. First, if the spinner itself has need_resched() set — meaning the scheduler wants this CPU for a higher-priority task — there is no point spinning; bail immediately. Second, if there is an owner, the helper returns whatever owner_on_cpu(owner) says: spin only if the owner is currently executing on some CPU. If there is no owner at the instant we look (the lock just became free), the helper returns true so the spin path can try to grab it directly.

A subtle correctness point lives here. The spinner dereferences another task’s task_struct (the owner) without holding a reference. Why is that safe? Because, as the v6.12 comment states, “We already disabled preemption which is equal to the RCU read-side critical section in optimistic spinning code. Thus the task_struct structure won’t go away during the spinning period” (per mutex.c, v6.12). Disabling preemption blocks the grace period that would free the owner’s task_struct, so the pointer stays valid for the duration of the spin — the same trick RCU readers rely on. This is why the whole optimistic-spin section runs with preemption disabled, asserted by lockdep_assert_preemption_disabled().

owner_on_cpu() — the heart of the bet

The single most important predicate is owner_on_cpu(). The task brief flagged that it is not in mutex.c; verification confirms it is a static inline in include/linux/sched.h, v6.12:

static inline bool owner_on_cpu(struct task_struct *owner)
{
	/*
	 * As lock holder preemption issue, we both skip spinning if
	 * task is not on cpu or its cpu is preempted
	 */
	return READ_ONCE(owner->on_cpu) && !vcpu_is_preempted(task_cpu(owner));
}

Two conditions, both must hold:

  • READ_ONCE(owner->on_cpu) — the on_cpu field of the owner’s task_struct is a flag (declared int on_cpu; inside the CONFIG_SMP block of task_struct) that the scheduler sets while the task is actually executing on a CPU and clears when it is switched out. READ_ONCE forces a single fresh load each time around the loop rather than letting the compiler hoist it. If on_cpu is zero, the owner is not running — it has slept or been descheduled — and the bet is off.
  • !vcpu_is_preempted(task_cpu(owner)) — in a virtualized guest, on_cpu being set only means the owner is running on a virtual CPU; the hypervisor may have descheduled that vCPU from any physical core. vcpu_is_preempted() reports exactly that. Spinning on an owner whose underlying physical CPU is not even scheduled is pointless — the owner is making no progress — so the predicate treats a preempted vCPU as “not on CPU.”

mutex_spin_on_owner() — the inner spin loop

Once the queue head decides to spin, it runs mutex_spin_on_owner():

static noinline
bool mutex_spin_on_owner(struct mutex *lock, struct task_struct *owner,
			 struct ww_acquire_ctx *ww_ctx, struct mutex_waiter *waiter)
{
	bool ret = true;
	lockdep_assert_preemption_disabled();
	while (__mutex_owner(lock) == owner) {
		barrier();
		/* Use vcpu_is_preempted to detect lock holder preemption issue. */
		if (!owner_on_cpu(owner) || need_resched()) {
			ret = false;
			break;
		}
		if (ww_ctx && !ww_mutex_spin_on_owner(lock, ww_ctx, waiter)) {
			ret = false;
			break;
		}
		cpu_relax();
	}
	return ret;
}

Line by line: the loop continues only while __mutex_owner(lock) == owner — that is, while the lock is still owned by the same task we started watching. If the owner field changes, the owner released (and possibly someone else grabbed it), so we stop and let the caller retry the trylock. The barrier() is a compiler barrier preventing the compiler from caching the loads across iterations. Inside the loop, the two abort conditions: !owner_on_cpu(owner) (owner stopped running) or need_resched() (our own CPU is wanted elsewhere) — either flips ret = false and breaks, signaling the caller to give up spinning. The ww_ctx branch handles Wound-Wait Mutexes (a spinner may need to back off to avoid a deadlock cycle); it is irrelevant to plain mutexes. Finally cpu_relax() — on x86 this emits the PAUSE instruction — hints to the CPU that this is a spin-wait, reducing power and easing memory-ordering pressure on the pipeline. A return of true means “the owner released while still running, go retry the trylock”; false means “give up spinning, go sleep.”

Putting it together: mutex_optimistic_spin()

static __always_inline bool
mutex_optimistic_spin(struct mutex *lock, struct ww_acquire_ctx *ww_ctx,
		      struct mutex_waiter *waiter)
{
	if (!waiter) {
		if (!mutex_can_spin_on_owner(lock))
			goto fail;
		if (!osq_lock(&lock->osq))
			goto fail;
	}
	for (;;) {
		struct task_struct *owner;
		owner = __mutex_trylock_or_owner(lock);
		if (!owner)
			break;
		if (!mutex_spin_on_owner(lock, owner, ww_ctx, waiter))
			goto fail_unlock;
		cpu_relax();
	}
	if (!waiter)
		osq_unlock(&lock->osq);
	return true;
fail_unlock:
	if (!waiter)
		osq_unlock(&lock->osq);
fail:
	if (need_resched()) {
		__set_current_state(TASK_RUNNING);
		schedule_preempt_disabled();
	}
	return false;
}

The !waiter branch is the entry gate for a fresh contender: check mutex_can_spin_on_owner(), then osq_lock(&lock->osq) to join the MCS queue. If either fails, goto fail. (A task already on the wait list passes waiter != NULL and skips the OSQ — it is allowed to spin without re-queuing, a refinement that lets a top-of-waitlist task also spin.) The infinite for loop is the acquire attempt: __mutex_trylock_or_owner() either grabs the lock and returns NULL (owner is now us → break, we won the midpath) or returns the current owner. If still owned, mutex_spin_on_owner() spins until the owner releases or the bet sours; a false return jumps to fail_unlock. On success, osq_unlock() releases our spot in the MCS queue and we return true. On failure, the fail: epilogue is important: if need_resched() is set, the function voluntarily reschedules right there (schedule_preempt_disabled()) before returning false, ensuring the higher-priority task that wanted this CPU gets it promptly rather than after we re-descend into the slowpath. The “we try to spin… if the lock owner is running, it is likely to release the lock soon. The mutex spinners are queued up using MCS lock so that only one spinner can compete for the mutex” comment (per mutex.c, v6.12) captures the whole design in two sentences.

The MCS Optimistic Spin Queue (osq_lock)

Why a naive owner-spin stampede is bad

If mutex_optimistic_spin() simply let every waiter loop on mutex_spin_on_owner() directly, then under contention dozens of CPUs would all be reading the same owner field and all racing to cmpxchg the same lock word the instant it freed. Only one wins; the rest just generated cache-coherence traffic, and the winner’s cmpxchg is delayed by all the losers’ atomics bouncing the cache line around. Corbet’s 2010 LWN write-up names the pathology precisely: “Once the mutex becomes available, only one of th[e] spinning threads will obtain it; the others will continue to spin, contending for the lock.” The fix is the same idea that makes qspinlock scale — serialize the waiters into a queue so they spin on private cache lines, not a shared one.

The structure

The optimistic spin queue is “An MCS like lock especially tailored for optimistic spinning for sleeping lock implementations (mutex, rwsem, etc). Using a single mcs node per CPU is safe because sleeping locks should not be called from interrupt context and we have preemption disabled while spinning” (per osq_lock.c, v6.12). The MCS algorithm is named for Mellor-Crummey and Scott; the kernel’s qspinlock is a more compact MCS variant, and this osq_lock is the MCS variant tailored for sleeping locks (see Alternatives below for the crisp contrast). Each CPU has one statically-allocated node:

struct optimistic_spin_node {
	struct optimistic_spin_node *next, *prev;
	int locked; /* 1 if lock acquired */
	int cpu; /* encoded CPU # + 1 value */
};
 
static DEFINE_PER_CPU_SHARED_ALIGNED(struct optimistic_spin_node, osq_node);

next/prev make a doubly-linked list (the doubly-linked part is what enables cancellation — see below). locked is the per-CPU flag each waiter spins on: when it flips to 1, this node has been promoted to queue head and may now compete for the mutex. cpu stores this node’s CPU number, encoded as CPU# + 1 so that the value 0 can mean “empty.” The DEFINE_PER_CPU_SHARED_ALIGNED puts one node per CPU on its own cache line. The queue itself is a single atomic word in the mutex (struct optimistic_spin_queue { atomic_t tail; }, with OSQ_UNLOCKED_VAL defined as 0), holding the encoded CPU number of the queue’s tail node, or 0 if empty.

Enqueue and spin: osq_lock()

bool osq_lock(struct optimistic_spin_queue *lock)
{
	struct optimistic_spin_node *node = this_cpu_ptr(&osq_node);
	struct optimistic_spin_node *prev, *next;
	int curr = encode_cpu(smp_processor_id());
	int old;
 
	node->locked = 0;
	node->next = NULL;
	node->cpu = curr;
 
	old = atomic_xchg(&lock->tail, curr);
	if (old == OSQ_UNLOCKED_VAL)
		return true;
 
	prev = decode_cpu(old);
	node->prev = prev;
 
	smp_wmb();
	WRITE_ONCE(prev->next, node);
 
	if (smp_cond_load_relaxed(&node->locked, VAL || need_resched() ||
				  vcpu_is_preempted(node_cpu(node->prev))))
		return true;
	/* ... cancellation path below ... */

The CPU initializes its own node (locked = 0, next = NULL, cpu = curr) and then does the central atomic step: old = atomic_xchg(&lock->tail, curr) — atomically install my node as the new tail and read back the previous tail. If old == OSQ_UNLOCKED_VAL, the queue was empty: I am now both head and tail, I own the OSQ, return true immediately. Otherwise prev = decode_cpu(old) finds my predecessor; I set node->prev = prev, issue an smp_wmb() (write barrier so my node is fully initialized before the predecessor can see it), and link myself in with WRITE_ONCE(prev->next, node). Now I spin: smp_cond_load_relaxed(&node->locked, ...) busy-waits reading my own node->locked until either it becomes nonzero (VAL is the loaded value — my predecessor promoted me to head), or need_resched() fires, or my predecessor’s vCPU is preempted. Crucially this spin touches only my per-CPU cache line plus a read of my predecessor’s CPU number — no shared-lock-word bouncing.

Cancellation: leaving the queue

The MCS variant for sleeping locks has a property a plain spinlock’s MCS does not: a waiter can abandon the queue when it needs to reschedule. As mutex-design.rst, v6.12 puts it, “An important feature of the customized MCS lock is that it has the extra property that spinners are able to exit the MCS spinlock queue when they need to reschedule.” This is why the node is doubly linked. When smp_cond_load_relaxed exits because of need_resched() or a preempted vCPU (not because locked was set), osq_lock enters its unqueue path: it must splice itself out by (A) detaching from its predecessor (cmpxchg(&prev->next, node, NULL), retrying if prev itself moved), (B) if it is the tail, using osq_wait_next() to atomic_cmpxchg_acquire(&lock->tail, curr, old_cpu) and restore the tail to its predecessor, and (C) otherwise relinking its successor to its predecessor (WRITE_ONCE(next->prev, prev); WRITE_ONCE(prev->next, next)). The function then returns false — “I left the queue, go sleep.” Without cancellation, a spinner that must yield the CPU to a higher-priority task would either hold up the whole queue or be unable to leave; the doubly-linked design makes a clean exit possible.

Handoff: osq_unlock()

void osq_unlock(struct optimistic_spin_queue *lock)
{
	struct optimistic_spin_node *node, *next;
	int curr = encode_cpu(smp_processor_id());
 
	if (likely(atomic_cmpxchg_release(&lock->tail, curr,
					  OSQ_UNLOCKED_VAL) == curr))
		return;
 
	node = this_cpu_ptr(&osq_node);
	next = xchg(&node->next, NULL);
	if (next) {
		WRITE_ONCE(next->locked, 1);
		return;
	}
 
	next = osq_wait_next(lock, node, OSQ_UNLOCKED_VAL);
	if (next)
		WRITE_ONCE(next->locked, 1);
}

The fast path: if I am still the tail (no one queued behind me), atomic_cmpxchg_release(&lock->tail, curr, OSQ_UNLOCKED_VAL) empties the queue and returns. Otherwise there is a successor: next = xchg(&node->next, NULL) grabs it and WRITE_ONCE(next->locked, 1) — this is the handoff: setting the successor’s locked flag is exactly what its smp_cond_load_relaxed is waiting on, so the next CPU’s spin completes and it becomes the new head. The osq_wait_next() fallback handles the race where node->next is momentarily NULL because a successor is mid-enqueue.

CONFIG_MUTEX_SPIN_ON_OWNER — the gate

The entire optimization is compiled in only when CONFIG_MUTEX_SPIN_ON_OWNER is set (it depends on SMP — there is nothing to spin on with one CPU). When the config is off, mutex_optimistic_spin() collapses to a stub that simply { return false; } (per mutex.c, v6.12); the slowpath then proceeds straight to enqueue-and-sleep, and the struct mutex carries no osq field. So a kernel built without this option still has correct mutexes — just without the hybrid speedup.

Uncertain

Verify: the precise default value of CONFIG_MUTEX_SPIN_ON_OWNER and its full Kconfig depends on clause in v6.12 (it is selected automatically rather than user-prompted, and the documentation describes it as effectively always-on for SMP). Reason: I confirmed the #else { return false; } stub from the verified mutex.c blob, but did not fetch kernel/Kconfig.locks to read the literal Kconfig stanza. To resolve: read kernel/Kconfig.locks at tag v6.12 for the MUTEX_SPIN_ON_OWNER entry. uncertain

Shared With rw_semaphore

The same osq_lock machinery drives writer-side optimistic spinning in [[Read-Write Semaphores|rw_semaphore]]. Verification of rwsem.c, v6.12 confirms it calls osq_lock(&sem->osq) / osq_unlock(&sem->osq) against an OSQ embedded in the rwsem, and has its own rwsem_can_spin_on_owner() / rwsem_spin_on_owner() mirroring the mutex helpers. There is one important difference owing to the reader/writer asymmetry: a rwsem can be owned by many readers at once, with no single “owner” task to watch. The rwsem comment makes the rule explicit — spinning stops when “1) the owning writer isn’t running; or 2) readers own the lock and spinning time has exceeded limit.” Spinning on a running writer is a good bet (one task, releasing soon); spinning while readers hold it is a worse bet (no single owner to track, indefinite hold), so it is time-bounded rather than owner-bounded. The shared osq_lock.c comment naming “mutex, rwsem, etc” confirms the queue was built to be reused.

Failure Modes and Common Misunderstandings

“Spinning is always faster than sleeping.” No — spinning is faster only when the wait is short, which is precisely the condition owner_on_cpu() checks. Spinning on a sleeping owner would burn a full CPU for the entire (possibly long) hold time; the whole point of the predicate is to never do that. The midpath converts mutexes to “spinlock-like” speed only for the short-critical-section case (Zijlstra, LWN 2009 reported a 345% VFS-scalability gain on his test box from adaptive spinning).

Spinning on a preempted vCPU. In a virtual machine, on_cpu set does not guarantee forward progress: the hypervisor may have suspended the owner’s vCPU. Without the vcpu_is_preempted() check, a guest could spin for an entire hypervisor time-slice waiting on an owner that is not even scheduled on a physical core — the classic “lock-holder preemption” problem. The owner_on_cpu() comment (“As lock holder preemption issue, we both skip spinning if task is not on cpu or its cpu is preempted”) exists precisely to abort the spin in that case.

The owner-changed stampede. If the owner field changes while you spin (rather than going to NULL), it means someone else won the race for the lock — a sign of heavy multi-CPU contention. mutex_spin_on_owner() stops looping the moment __mutex_owner(lock) != owner, and the broader design — only the OSQ head competes — prevents the cache-line storm that would otherwise result (Corbet, LWN 2010).

Forgetting that the spin is bounded. The wasted-CPU concern with any busy-wait is real, but here it is bounded by construction: the spin aborts the instant the owner stops running or the spinner is asked to reschedule. Worst case you spin for the remainder of a short critical section; you never spin through a sleep.

Assuming owner_on_cpu lives in mutex.c. It does not — it is a static inline in include/linux/sched.h so the scheduler-aware on_cpu/vcpu_is_preempted plumbing is reusable by mutex, rwsem, and rtmutex paths alike.

Alternatives and When to Choose Them

vs. a pure spinlock (Kernel Spinlocks / Queued Spinlocks and qspinlock). A spinlock always spins and may be taken in atomic/interrupt context; it has no concept of “owner is running” because the holder cannot sleep anyway. qspinlock is also MCS-based, but it is the always-spinning lock for code that cannot block, its node is not cancellable (a spinlock waiter cannot just leave to reschedule — it is in a non-preemptible region), and it is used from interrupt context. The osq_lock is the deliberately different MCS variant for sleeping locks: per-CPU node (safe because sleeping locks are never taken in interrupt context), preemption-disabled while spinning, and cancellable so a spinner can bail to the sleep path. That cancellability is the crisp distinction — osq_lock is “MCS you can quit,” qspinlock is “MCS you cannot.”

vs. always sleeping (no midpath). Building with CONFIG_MUTEX_SPIN_ON_OWNER off gives correct but slower mutexes; appropriate only where the spin’s wasted cycles are unacceptable (e.g. some single-CPU or power-constrained configs where there is no second CPU to spin against anyway).

vs. RT-mutex priority inheritance (Priority Inheritance and the RT-Mutex). Optimistic spinning is a throughput optimization; it does nothing for priority inversion. When a low-priority owner must be boosted so a high-priority waiter can proceed, that is the RT-mutex’s job. On PREEMPT_RT, most locks become PI-mutexes and the spinning story changes accordingly.

Production Notes

Adaptive spinning entered mainline in 2.6.30 via Peter Zijlstra’s January 2009 patch, itself a port of an idea from the -rt tree (Steven Rostedt, after Gregory Haskins). The crucial refinement — serializing spinners through an MCS queue so they stop trampling one another’s cache lines — followed from the overly-optimistic-spinning discussion in 2010 and the broader MCS-locks-and-qspinlocks work Corbet covered in 2014. The result is the structure that ships in 6.12: a clean three-tier mutex (fast cmpxchg → MCS-queued optimistic spin → wait-list sleep). The practical upshot, stated plainly in mutex-design.rst, v6.12, is that “While formally kernel mutexes are sleepable locks, it is path (ii) that makes them more practically a hybrid type,” and the documentation’s standing advice is to always prefer mutexes over hand-rolled locking unless their semantics genuinely conflict with your needs — precisely because the midpath has erased most of the performance reason one used to reach for a spinlock in process context.

Uncertain

Verify: the exact kernel release that first merged adaptive spinning (commonly cited as 2.6.30) and the attribution chain (Zijlstra ← Rostedt ← Haskins). Reason: these are historical facts drawn from LWN secondary reporting (LWN 314512), not from a primary git-log or changelog fetched during this task. To resolve: check the merge commit of the mutex: implement adaptive spinning patch in the kernel git history. The current v6.12 mechanism described above is verified against the v6.12 source blobs; only the historical merge-version detail is unverified. uncertain

See Also

Graph View

Backlinks