Wound-Wait Mutexes

A wound/wait mutex (ww_mutex) is a blocking mutual-exclusion lock augmented with a deadlock-avoidance protocol borrowed from database transaction theory, designed for the one situation a plain mutex cannot handle safely: acquiring a set of locks whose order is not known in advance. When two threads each grab a subset of the same locks in opposite orders, a classic AB-BA deadlock is unavoidable with ordinary mutexes. The ww_mutex machinery sidesteps this by stamping each “acquire context” with a globally increasing ticket and, on contention, deterministically choosing one contender (always the younger one — larger stamp) to back off: it drops every lock it holds and retries from scratch, signalled by a return of -EDEADLK from ww_mutex_lock. Because the oldest transaction never backs off, the protocol guarantees forward progress and is provably deadlock-free (ww-mutex-design.rst, v6.12). Its flagship user is the graphics stack: GPU command submission must reserve many buffer objects whose order is dictated by userspace, via the dma_resv reservation lock.

This note is pinned to Linux 6.12 LTS (released 2024-11-17). The ww_mutex design has been stable since its 2013 introduction; the choice-of-algorithm (Wound-Wait vs Wait-Die) split dates from 2018.

Uncertain

Verify: the claim that ww_mutex was introduced in 2013 and the Wound-Wait/Wait-Die algorithm split landed in 2018. Reason: dated from copyright headers in include/linux/ww_mutex.h (“Wait/Die implementation: Copyright (C) 2013 Canonical Ltd.” and “Choice of algorithm: Copyright (C) 2018 WMWare Inc.”), not from the actual merge commits. To resolve: git log --follow on the relevant files to find the introducing commit dates.

Mental Model — Tickets and the Right to Not Back Off

Think of every batch of lock acquisitions as a transaction that, the moment it begins, takes a numbered ticket from a single global dispenser. Lower number means older; older means more senior. The entire protocol reduces to one rule with two readings:

An older transaction (lower ticket) must never be made to abort because of a younger one. Seniority is permanent priority.
Therefore, when two transactions collide over a lock, the younger one yields — it releases everything and starts over, getting in line behind the senior.

That single asymmetry is what kills deadlock. A deadlock is a cycle of “A waits for B waits for … waits for A.” But a cycle requires that somewhere along it an older transaction waits on a younger one. The ww protocol forbids exactly that: an older transaction never waits behind a younger holder — instead the younger holder is forced out of the way. With no edge from old→young permitted to persist, no cycle can close, so the wait-for graph stays acyclic and progress is guaranteed.

flowchart TB
  subgraph T1["Transaction T1 (ticket 7 — OLDER)"]
    A1["holds lock A"]
  end
  subgraph T2["Transaction T2 (ticket 19 — YOUNGER)"]
    B1["holds lock B"]
  end
  A1 -->|"T1 now wants B<br/>(held by younger T2)"| W["Wound-Wait:<br/>T1 WOUNDS T2"]
  B1 -->|"T2 now wants A<br/>(held by older T1)"| D["T2 sees it is wounded,<br/>returns -EDEADLK,<br/>drops A and B, retries"]
  W -.->|"sets T2.wounded = 1"| D
  D -->|"after T1 finishes"| R["T2 re-acquires<br/>via ww_mutex_lock_slow"]

What it shows: the canonical AB-BA collision and how Wound-Wait resolves it. T1 (older, ticket 7) holds A and reaches for B; T2 (younger, ticket 19) holds B and reaches for A — a textbook deadlock with plain mutexes. The insight: the protocol breaks the cycle preemptively — the older T1 marks the younger T2 as “wounded,” and T2 discovers this the next time it contends for a lock, then voluntarily aborts (-EDEADLK), releases A and B, and retries once T1 is done. The older transaction is never the one to suffer.

The Two Algorithms — Wound-Wait and Wait-Die

The kernel implements the deadlock-avoidance idea two different ways, both drawn from relational-database (RDBMS) concurrency control. Both are fair — every transaction eventually succeeds — but they differ in who aborts and when (ww-mutex-design.rst).

Wait-Die is the conservative, requester-side rule. When a transaction tries to take a lock that is already held:

If the holder is younger, the requester waits.
If the holder is older, the requester dies — it aborts immediately and returns -EDEADLK. (Hence “Wait-Die”: you either wait or you die, decided by your own seniority relative to the holder.)

Wound-Wait is the aggressive, holder-side rule. When a transaction tries to take a held lock:

If the holder is younger, the requester wounds it — it marks the younger holder for death, requesting it abort.
If the holder is older, the requester waits.

The crucial difference: in Wait-Die the requester is the one that may abort (it kills itself); in Wound-Wait an older requester reaches across and forces a younger holder to abort. Wound-Wait is therefore preemptive — a running transaction can be told from outside to give up. The documentation is careful to note that this “preemption” is not CPU preemption: a wounded transaction is considered preempted only when it actually dies (returns -EDEADLK) in response to the wound.

The practical trade-off: Wound-Wait typically generates fewer rollbacks than Wait-Die (a senior transaction in Wait-Die may repeatedly die against many younger holders), but Wound-Wait does more work per backoff because it must reliably detect the wounded condition and unwind a transaction that was already making progress. The kernel’s rough rule of thumb: choose Wound-Wait when the number of simultaneously competing transactions is small and you want to minimize rollbacks.

The algorithm is selected at class definition time, not per-lock:

static DEFINE_WW_CLASS(my_class);   /* Wound-Wait */
static DEFINE_WD_CLASS(my_class);   /* Wait-Die   */

DEFINE_WW_CLASS sets is_wait_die = 0; DEFINE_WD_CLASS sets is_wait_die = 1 (ww_mutex.h). A single ww_class must never mix the two — the wait-list ordering invariants assume one algorithm throughout.

Uncertain

Verify: the relative-rollback and per-backoff-cost comparison (“Wound-Wait generates fewer backoffs but does more recovery work than Wait-Die”). Reason: stated in the kernel design doc as a general RDBMS result (“typically stated to generate fewer backoffs”) rather than measured for the kernel implementation. To resolve: the underlying claim traces to RDBMS literature (Rosenkrantz, Stearns, Lewis 1978); the doc itself hedges with “typically stated.”

The Two Extra Objects — `ww_class` and `ww_acquire_ctx`

A plain struct mutex needs nothing beyond itself. A ww_mutex adds two concepts to the interface (ww-mutex-design.rst).

The ww class (struct ww_class) holds the single global stamp dispenser — an atomic_long_t stamp — plus the algorithm selector (is_wait_die) and lockdep keys. Unlike a normal mutex, the class is explicit for a ww_mutex because the acquire context needs it. From the v6.12 header:

struct ww_class {
	atomic_long_t stamp;                 /* the global ticket counter */
	struct lock_class_key acquire_key;   /* lockdep: keys the acquire ctx */
	struct lock_class_key mutex_key;     /* lockdep: keys the mutexes     */
	const char *acquire_name;
	const char *mutex_name;
	unsigned int is_wait_die;            /* 1 = Wait-Die, 0 = Wound-Wait  */
};

The acquire context (struct ww_acquire_ctx) represents one transaction. It is allocated on the caller’s stack (the doc recommends this explicitly) and lives for the duration of the multi-lock acquisition:

struct ww_acquire_ctx {
	struct task_struct *task;       /* who owns this transaction         */
	unsigned long stamp;            /* this transaction's ticket         */
	unsigned int acquired;          /* how many locks held so far        */
	unsigned short wounded;         /* set by an older transaction       */
	unsigned short is_wait_die;     /* copied from the class             */
	/* ... debug/lockdep fields when CONFIG_DEBUG_* ... */
};

The stamp is assigned in ww_acquire_init:

ctx->task    = current;
ctx->stamp   = atomic_long_inc_return_relaxed(&ww_class->stamp);  /* take a ticket */
ctx->acquired = 0;
ctx->wounded  = false;
ctx->is_wait_die = ww_class->is_wait_die;

atomic_long_inc_return_relaxed atomically increments the class’s global counter and returns the new value — that value is this transaction’s ticket. The decisive property the design doc stresses: a backing-off transaction keeps the same stamp on retry; it does not call ww_acquire_init again and grab a new (larger, younger) ticket. If it did, a perpetually-unlucky transaction could be starved forever, always being the youngest. Keeping the original stamp means every retry makes the transaction relatively older as newer transactions arrive, so it eventually becomes the oldest and is guaranteed to win.

The ww_mutex itself simply wraps a base mutex plus a back-pointer to whoever currently owns it under a context:

struct ww_mutex {
	struct WW_MUTEX_BASE base;       /* a 'struct mutex', or 'struct rt_mutex' on PREEMPT_RT */
	struct ww_acquire_ctx *ctx;      /* the context that acquired it, or NULL */
};

The design note observes that ww_mutex “encapsulates a struct mutex, this means no extra overhead for normal mutex locks” — the deadlock-avoidance logic only runs on the contended slow path, so uncontended ww_mutex_lock is as cheap as a normal mutex. On PREEMPT_RT the base becomes an rt_mutex instead, so ww locks gain priority inheritance — see Priority Inheritance and the RT-Mutex.

Mechanical Walk-through — How the Wound Actually Lands

The deadlock-avoidance logic lives in kernel/locking/ww_mutex.h and runs only when a ww_mutex_lock cannot take the lock immediately and must enqueue on the wait-list. Three pieces matter (kernel/locking/ww_mutex.h, v6.12).

Comparing seniority — __ww_ctx_less. “Who is older” reduces to comparing stamps with wraparound-safe arithmetic:

/* FIFO order tie break -- bigger is younger */
return (signed long)(a->stamp - b->stamp) > 0;

Casting the subtraction to signed long makes the comparison correct even when the unsigned long counter wraps around (the same trick used for jiffies time comparisons). If a’s stamp is larger, a is the younger (a < b in seniority is false — a is “less” senior). On PREEMPT_RT this function first checks real-time/deadline task priority before falling back to the stamp, because there the base lock is PI-aware.

The wait-list is kept sorted by stamp. __ww_mutex_add_waiter inserts a new waiter before the first waiter with a higher (younger) stamp, so contexts queue oldest-first; waiters with no context are interspersed in FIFO order to avoid starving them. As it walks the list to find the insertion point, it does the algorithm-specific work inline.

Wait-Die backoff at enqueue time. When a Wait-Die transaction is about to queue and finds an older context already waiting ahead of it, there is no point queueing — the moment that older context acquires the lock this one would have to die. So it dies now:

if (__ww_ctx_less(ww_ctx, cur->ww_ctx)) {     /* we are older than cur? */
	if (is_wait_die) {
		int ret = __ww_mutex_kill(lock, ww_ctx);
		if (ret) return ret;                  /* returns -EDEADLK */
	}
	break;
}

Wounding — __ww_mutex_wound. For Wound-Wait, after adding itself to the wait-list, the requester checks whether the current lock holder is younger and, if so, wounds it:

static bool __ww_mutex_wound(struct MUTEX *lock,
			     struct ww_acquire_ctx *ww_ctx,
			     struct ww_acquire_ctx *hold_ctx)
{
	struct task_struct *owner = __ww_mutex_owner(lock);
	...
	if (ww_ctx->acquired > 0 && __ww_ctx_less(hold_ctx, ww_ctx)) {
		hold_ctx->wounded = 1;          /* mark the younger holder for death */
		if (owner != current)
			wake_up_process(owner);  /* nudge it so it notices */
		return true;
	}
	return false;
}

Two subtleties here are worth dwelling on. First, the guard ww_ctx->acquired > 0: a transaction only wounds when it already holds at least one lock itself. A transaction that holds nothing has nothing to deadlock with, so there is no need to disturb the holder. Second, wounding sets a flag and sends a wakeup — it does not abort the victim synchronously. This is the lazy-preemption scheme the design doc describes: the wounded status is checked only later, when the victim next contends for a lock and a true deadlock is actually possible.

Discovering the wound — __ww_mutex_check_kill. The wounded transaction finds out at its next ww_mutex_lock slow path:

if (!ctx->is_wait_die) {            /* Wound-Wait path */
	if (ctx->wounded)
		return __ww_mutex_kill(lock, ctx);   /* -> -EDEADLK */
	return 0;
}

And __ww_mutex_kill only returns -EDEADLK if the transaction actually holds locks (acquired > 0); otherwise there is no deadlock to break and the call proceeds normally:

static __always_inline int __ww_mutex_kill(...) {
	if (ww_ctx->acquired > 0) {
		/* record the contending lock for the slow-path retry */
		return -EDEADLK;
	}
	return 0;
}

The benefit of lazy checking, the doc explains, is precise: when the wounded transaction does back off, it can identify which contended lock it should wait on before restarting — blindly restarting would likely just deadlock again on the same lock.

sequenceDiagram
  participant Y as Younger txn (holds B, wants A)
  participant O as Older txn (holds A, wants B)
  participant LB as lock B wait-list
  O->>LB: ww_mutex_lock(B) — B held by younger Y
  Note over LB: __ww_mutex_add_waiter:<br/>O is older than holder Y
  LB->>Y: __ww_mutex_wound: set Y.wounded = 1,<br/>wake_up_process(Y)
  Y->>Y: next ww_mutex_lock(A) hits slow path
  Note over Y: __ww_mutex_check_kill:<br/>wounded && acquired>0
  Y-->>Y: ww_mutex_lock returns -EDEADLK
  Y->>Y: drop B (and all held locks)
  O->>O: now acquires B uncontended, finishes
  Y->>Y: ww_mutex_lock_slow(A) — blocks until free,<br/>then re-acquires the rest

What it shows: the full lifecycle of a wound under Wound-Wait, from the older transaction’s contended ww_mutex_lock through the lazy detection and the younger transaction’s abort-and-retry. The insight: wounding is asynchronous — the wound is recorded as a flag and a wakeup, but the actual abort happens cooperatively at the victim’s next lock attempt, which is also the only place a genuine deadlock could form.

The `-EDEADLK` Retry Idiom and `ww_mutex_lock_slow`

The caller’s responsibility, after ww_mutex_lock returns -EDEADLK, is fixed: release every lock currently held under this context, then re-acquire the contended lock first using ww_mutex_lock_slow, then resume normal acquisition. Here is the canonical reorderable-list pattern (Method 2 from the design doc), annotated:

int lock_objs(struct list_head *list, struct ww_acquire_ctx *ctx)
{
	struct obj_entry *entry, *entry2;
 
	ww_acquire_init(ctx, &ww_class);              /* take a ticket */
 
	list_for_each_entry(entry, list, head) {
		ret = ww_mutex_lock(&entry->obj->lock, ctx);
		if (ret < 0) {
			entry2 = entry;
			/* unwind: release everything we already grabbed,
			 * in REVERSE order of acquisition                */
			list_for_each_entry_continue_reverse(entry2, list, head)
				ww_mutex_unlock(&entry2->obj->lock);
 
			if (ret != -EDEADLK) {        /* e.g. -EINTR: a real error */
				ww_acquire_fini(ctx);
				return ret;
			}
 
			/* we lost the seqno race: block on the contended lock,
			 * then restart the whole acquisition.               */
			ww_mutex_lock_slow(&entry->obj->lock, ctx);
 
			/* move the contended buffer to the head so the for-loop
			 * restarts from the first not-yet-locked entry.        */
			list_del(&entry->head);
			list_add(&entry->head, list);
		}
	}
 
	ww_acquire_done(ctx);                          /* optional: end acquire phase */
	return 0;
}

Why ww_mutex_lock_slow rather than a plain ww_mutex_lock? Semantically they are identical after a full unwind — once you hold no other ww locks there is no deadlock potential, so a normal ww_mutex_lock on the contended lock would simply block and never spuriously return -EDEADLK. The _slow variant exists purely for interface safety (ww-mutex-design.rst):

ww_mutex_lock has a __must_check int return; ww_mutex_lock_slow returns void. After a full unwind the call cannot fail, so the void return documents that and avoids a spurious “ignored return value” compiler warning.
With CONFIG_DEBUG_WW_MUTEX_SLOWPATH/full debugging, ww_mutex_lock_slow verifies that all other ww locks were released first, and that you are blocking on the actual contended lock — catching the two most common abuses: forgetting to unwind, and spinning through the -EDEADLK path repeatedly.

The _slow wrapper is literally ww_mutex_lock with the return discarded, plus a debug assertion:

static inline void ww_mutex_lock_slow(struct ww_mutex *lock, struct ww_acquire_ctx *ctx) {
	int ret;
#ifdef DEBUG_WW_MUTEXES
	DEBUG_LOCKS_WARN_ON(!ctx->contending_lock);   /* must follow an -EDEADLK */
#endif
	ret = ww_mutex_lock(lock, ctx);
	(void)ret;
}

There is also a third return code worth knowing: -EALREADY, returned when the same context tries to lock the same mutex twice. For list-based acquisition built from userspace input (e.g. a GPU command-buffer ioctl that forbids duplicate buffer handles), this lets the helper detect duplicates cheaply. Note that the ad-hoc “graph walk” pattern (Method 3) cannot propagate -EALREADY because the object list is rebuilt on each retry.

The Canonical User — `dma_resv` and GPU Buffer Reservation

The motivating use case, and still the dominant one, is the graphics subsystem. A single GPU command submission (execbuf) references many buffer objects — vertex buffers, textures, render targets — and the order they appear is chosen by userspace (the sequence of OpenGL/Vulkan calls an application makes). Two processes can therefore reference the same buffers in opposite orders, and there is no static lock ordering the kernel can impose. Worse, the kernel may need to migrate buffers into video RAM (VRAM), possibly evicting others, before the GPU runs — so the lock set is large and dynamic (ww-mutex-design.rst, Motivation).

The kernel exposes this through struct dma_resv (the DMA reservation object), whose core is exactly a ww_mutex:

struct dma_resv {
	struct ww_mutex lock;     /* the reservation lock */
	...
};
extern struct ww_class reservation_ww_class;   /* the shared class */

dma_resv_lock(obj, ctx) is a thin wrapper over ww_mutex_lock(&obj->lock, ctx), dma_resv_lock_slow over ww_mutex_lock_slow, and so on (dma-resv.h, v6.12). The Direct Rendering Manager (DRM) Translation Table Maps (TTM) memory manager pioneered this scheme — the design doc credits TTM with inventing the ticket algorithm — and it is now shared across DRM drivers and dmabuf, even across devices via PRIME/dmabuf buffer sharing.

A subtle and frequently-misreported fact: despite the name reservation_ww_class, the reservation lock is defined with DEFINE_WD_CLASS — it uses Wait-Die, not Wound-Wait (dma-resv.c line 57, v6.12):

DEFINE_WD_CLASS(reservation_ww_class);
EXPORT_SYMBOL(reservation_ww_class);

So the headline algorithm in the literature (“Wound-Wait”) and the one the marquee user actually runs (Wait-Die) differ. Both deliver the same deadlock-freedom guarantee; the choice is a tuning decision. The name ww_mutex (“wound/wait”) is the family name covering both algorithms, not a commitment to the Wound-Wait variant specifically.

Uncertain

Verify: that reservation_ww_class remains DEFINE_WD_CLASS (Wait-Die) in current/later kernels, and why DRM chose Wait-Die. Reason: confirmed for v6.12 from the source line, but the rationale (the doc says use Wound-Wait when competing transactions are few — DRM evidently judged otherwise) is inferred, not documented at the definition site. To resolve: read the commit that switched/introduced the class choice and any DRM mailing-list discussion. uncertain

Failure Modes and Interface Abuse

ww_mutex has more ways to be misused than a plain mutex, so it ships extensive debug checking under CONFIG_DEBUG_MUTEXES and especially CONFIG_PROVE_LOCKING (ww-mutex-design.rst, Lockdep). The classic mistakes:

Forgetting to unwind before ww_mutex_lock_slow. Calling _slow (or re-acquiring) on the contended lock while still holding other ww locks reintroduces the deadlock the protocol was meant to avoid. Full debugging asserts acquired == 0 at this point.
Re-grabbing a new ticket on retry. Calling ww_acquire_init again after -EDEADLK resets the stamp to a fresh (younger) value, destroying the starvation-freedom guarantee. The retry must reuse the same context.
Locking the wrong mutex after -EDEADLK. The context records the contending_lock; locking anything else first is flagged. So is locking the right mutex but before releasing everything else.
Calling ww_mutex_lock_slow without a preceding -EDEADLK (contending_lock is NULL) — the _slow debug assertion catches this.
Mixing a contexted acquisition with single-lock (ctx == NULL) acquisition of the same class, or mixing two different contexts — both can produce undetected deadlocks and are forbidden; lockdep catches them.
Forgetting ww_acquire_fini, or acquiring more locks after ww_acquire_done.

There is also CONFIG_DEBUG_WW_MUTEX_SLOWPATH, which deliberately injects fake -EDEADLK returns (using a per-context countdown seeded from the low bits of the stamp) to exercise the backoff path even when no real contention occurs — a fuzzing aid for the retry idiom, since the very first lock of a transaction can otherwise never legitimately fail.

The single-lock escape hatch deserves emphasis: if you only ever take one lock of a class, you cannot deadlock within that class, so deadlock avoidance is pure overhead. Pass a NULL context to ww_mutex_lock and it behaves exactly like an ordinary mutex — no ticket, no wait-list sorting.

Alternatives and When to Choose Them

A ww_mutex is the right tool only when you must hold multiple locks of the same class simultaneously and their order is data-dependent. The alternatives:

Plain Kernel Mutexes with a fixed lock ordering. If a global acquisition order exists (lock by ascending address, by ID, by tree position), enforce it and use ordinary mutexes — simpler, cheaper, and lockdep-verifiable. Only when no such order can be imposed (because userspace dictates it) does ww_mutex earn its complexity.
A single coarse lock over the whole set. Trivially deadlock-free, but serializes everything — unacceptable when the sets are large and mostly disjoint, which is the GPU case.
try-lock with backoff (lock-by-address, on failure release-all-and-retry). This is essentially a hand-rolled, un-prioritized version of ww — it works but offers no fairness guarantee and can livelock under contention. ww_mutex formalizes it with stamps to guarantee progress.
Lock Ordering and Deadlock Avoidance via lockdep is detection, not avoidance — it tells you after the fact that an ordering is dangerous. ww_mutex is for the case where you provably cannot establish an ordering at all.

Within ww_mutex, the Wound-Wait vs Wait-Die choice is the sub-decision: Wound-Wait for few competing transactions and minimal rollbacks; Wait-Die (as DRM chose) otherwise.

Production Notes

The ww_mutex is not a niche curiosity — it is on the hot path of every modern Linux GPU workload through dma_resv. Each drm_exec / ttm_eu_reserve_buffers cycle, every atomic KMS commit that pins framebuffers, and every dmabuf import crosses it. Because the uncontended path is a bare mutex acquire, the cost is invisible in the common case; the backoff machinery only fires under genuine cross-context contention, which the design doc explicitly notes is expected to be rare (“not much contention is expected … optimization focus should therefore be directed towards the uncontended cases”).

On a PREEMPT_RT kernel the base lock switches from struct mutex to struct rt_mutex, so ww locks transparently gain priority inheritance — and the stamp comparison in __ww_ctx_less additionally honors real-time and deadline task priority before the FIFO stamp tiebreak. This interaction is delicate: the rt_mutex chain walk (rt_mutex_adjust_prio_chain) explicitly tolerates the “spurious” cycles that ww_mutexes can create in the lock graph, deferring the -EDEADLK decision to the wound/die logic rather than reporting a false deadlock (rtmutex.c, v6.12). See Priority Inheritance and the RT-Mutex for that mechanism.

vault

Explorer

Wound-Wait Mutexes

Wound-Wait Mutexes

Mental Model — Tickets and the Right to Not Back Off

The Two Algorithms — Wound-Wait and Wait-Die

The Two Extra Objects — `ww_class` and `ww_acquire_ctx`

Mechanical Walk-through — How the Wound Actually Lands

The `-EDEADLK` Retry Idiom and `ww_mutex_lock_slow`

The Canonical User — `dma_resv` and GPU Buffer Reservation

Failure Modes and Interface Abuse

Alternatives and When to Choose Them

Production Notes

See Also

Graph View

Table of Contents

vault

Explorer

Wound-Wait Mutexes

Wound-Wait Mutexes

Mental Model — Tickets and the Right to Not Back Off

The Two Algorithms — Wound-Wait and Wait-Die

The Two Extra Objects — ww_class and ww_acquire_ctx

Mechanical Walk-through — How the Wound Actually Lands

The -EDEADLK Retry Idiom and ww_mutex_lock_slow

The Canonical User — dma_resv and GPU Buffer Reservation

Failure Modes and Interface Abuse

Alternatives and When to Choose Them

Production Notes

See Also

Graph View

Table of Contents

The Two Extra Objects — `ww_class` and `ww_acquire_ctx`

The `-EDEADLK` Retry Idiom and `ww_mutex_lock_slow`

The Canonical User — `dma_resv` and GPU Buffer Reservation