vault

Priority Inheritance and the RT-Mutex

17 min read

Priority Inheritance and the RT-Mutex

The rt_mutex is a blocking mutual-exclusion lock that implements the priority-inheritance (PI) protocol — the standard cure for unbounded priority inversion, the failure where a high-priority task is blocked indefinitely on a lock held by a low-priority task that itself cannot run because some medium-priority task keeps preempting it. The fix is direct: while a low-priority owner holds a lock that a higher-priority task is waiting on, the owner temporarily inherits the waiter’s priority (or, for deadline tasks, its earlier deadline), so the medium task can no longer preempt it; the boost evaporates the instant the lock is released (rt-mutex.rst, v6.12). When a boosted owner is itself blocked on another lock, the boost must propagate down the chain of blocked-on owners — the PI chain walk, implemented by rt_mutex_adjust_prio_chain. The rt_mutex underlies the kernel-side PI-futex (FUTEX_LOCK_PI, exposing PTHREAD_PRIO_INHERIT to userspace), and on a PREEMPT_RT kernel it is the engine behind almost every converted spinlock and mutex.

This note is pinned to Linux 6.12 LTS (released 2024-11-17). The rt_mutex and its PI design originated in the out-of-tree -rt patch set and were merged to mainline incrementally; as of v6.12, PREEMPT_RT itself is a mainline-selectable config (depends on EXPERT && ARCH_SUPPORTS_RT) (Kconfig.preempt, v6.12).

Mental Model — Borrowing Urgency, Not Lending It

The core intuition: a lock holder is, while it holds the lock, a bottleneck for everyone waiting behind it. If the most urgent waiter is far more urgent than the holder, then the holder’s own (low) priority is a lie about how urgent its work currently is — finishing its critical section quickly is exactly as urgent as the most urgent waiter, because that waiter cannot proceed until it does. Priority inheritance makes the scheduler tell the truth: it temporarily raises the holder’s effective priority to match its most urgent waiter, so the holder gets scheduled aggressively, finishes the critical section, and releases the lock. The urgency is borrowed downward (from waiter to holder) for exactly as long as the dependency exists.

flowchart TB
  subgraph without["WITHOUT priority inheritance — unbounded inversion"]
    A1["A (high prio)<br/>blocked on L1"] --> C1["C (low prio)<br/>holds L1, wants to run"]
    B1["B (medium prio)<br/>runnable"] -->|"preempts C forever"| C1
    C1 -.->|"never runs,<br/>never releases L1"| A1
  end
  subgraph with["WITH priority inheritance"]
    A2["A (high prio)<br/>blocked on L1"] -->|"C inherits A's prio"| C2["C (now HIGH prio)<br/>holds L1"]
    B2["B (medium prio)<br/>runnable"] -.->|"can NOT preempt<br/>boosted C"| C2
    C2 -->|"runs, releases L1,<br/>loses boost"| A2
  end

What it shows: the three-task inversion scenario, with and without PI. A is highest priority, C lowest, B in between. A blocks on a lock C holds; B, being higher than C, preempts C and starves it — so A waits on B indirectly and unboundedly (left). With PI (right), C inherits A’s high priority the moment A blocks, so B can no longer preempt C; C runs, releases the lock, and immediately drops back to its own priority. The insight: PI converts an unbounded inversion (limited only by how long B chooses to run) into a bounded one (limited to the length of C’s critical section).

Unbounded Priority Inversion — The Disease

Priority inversion per se is unavoidable and usually harmless: any time a high-priority task needs a resource a lower-priority task currently holds, the high task must wait — that is inversion, and it lasts only as long as the critical section (rt-mutex-design.rst, v6.12). The pathological form is unbounded inversion. Take three tasks: A (highest priority), B (medium), C (lowest). C acquires lock L1. A wakes, tries to take L1, and blocks — correctly letting C run to release it. But now B becomes runnable; being higher priority than C, B preempts C. C cannot run, so it cannot release L1, so A stays blocked — and there is no bound on how long B runs. If B is a CPU hog, A may wait forever. The kernel doc renders it in ASCII:

     grab lock L1 (owned by C)
       |
  A ---+
          C preempted by B
            |
  C    +----+
  B         +-------->
                  B now keeps A from running.

The most famous real-world instance is the 1997 Mars Pathfinder mission, whose flight computer suffered repeated watchdog resets because a high-priority bus-management task was blocked on a mutex held by a low-priority meteorological task, which a medium-priority communications task kept preempting — textbook unbounded inversion. The fix uplinked to Mars was to enable priority inheritance on that mutex. (This anecdote is widely retold; the kernel docs do not cite it, so treat the details as historical color, not a kernel-sourced claim.)

Uncertain

Verify: the Mars Pathfinder priority-inversion narrative (which exact tasks, that PI was the deployed fix). Reason: a famous and widely-retold story, but recounted here from general engineering lore, not from a primary source consulted for this note. To resolve: Glenn Reeves’ (JPL) original account / Mike Jones’ write-up of it. uncertain

The PI Mechanism — Inherit the Top Waiter’s Priority

The rt_mutex’s solution is a strict protocol enforced by two red-black trees and two locks per task (rt-mutex-design.rst).

Per-mutex waiters tree. Every rt_mutex has a red-black tree (lock->waiters) of all tasks blocked on it, ordered by priority (FIFO within equal priority). The highest-priority blocked task is the top waiter.

Per-task pi_waiters tree. Every task has a red-black tree (task->pi_waiters) holding the top waiter of each mutex it owns — not all waiters, just the top one per owned lock. The top of this tree is therefore the single most urgent task waiting on anything this owner holds — the top pi waiter. It is protected by the per-task pi_lock, which may be taken in interrupt context (so it is always acquired with interrupts disabled).

The adjustment rule. A task’s effective priority is the better of its own normal priority and its top pi waiter’s priority. From v6.12 rtmutex.c:

static __always_inline void rt_mutex_adjust_prio(struct rt_mutex_base *lock,
						 struct task_struct *p)
{
	struct task_struct *pi_task = NULL;
 
	if (task_has_pi_waiters(p))
		pi_task = task_top_pi_waiter(p)->task;   /* most urgent waiter */
 
	rt_mutex_setprio(p, pi_task);                    /* boost or de-boost p */
}

rt_mutex_setprio (defined in kernel/sched/core.c) does the actual scheduler-visible change. Crucially, this function both boosts and de-boosts: because pi_waiters always contains the current most-urgent waiter, recomputing from it handles the waiter leaving (timeout, signal) just as naturally as a waiter arriving — the owner’s priority is simply re-derived. A reminder on the convention: in task_struct->prio, lower number = higher priority (prio 5 outranks prio 10).

The waiter sort key, rt_waiter_node_less, ranks by prio first and, when two tasks are both deadline (DL) tasks (dl_prio), by their absolute deadline — earlier deadline wins:

static __always_inline int rt_waiter_node_less(struct rt_waiter_node *left,
					       struct rt_waiter_node *right)
{
	if (left->prio < right->prio)
		return 1;                                  /* numerically lower = higher prio */
	if (dl_prio(left->prio))
		return dl_time_before(left->deadline, right->deadline);  /* earlier deadline wins */
	return 0;
}

This is deadline inheritance: an owner blocking a deadline task inherits not a static priority level but the waiter’s earlier deadline, so the Earliest-Deadline-First (EDF) scheduler runs it ahead of the deadline task it is blocking — see Deadline Scheduling and SCHED_DEADLINE for how EDF and the Constant Bandwidth Server interact with this. Only real-time (SCHED_FIFO/SCHED_RR) and deadline tasks participate in boosting; a normal SCHED_OTHER task’s prio maps to DEFAULT_PRIO for waiter-sorting purposes (__waiter_prio).

The Lock State Machine — Owner Field and the Waiters Bit

The rt_mutex tracks its whole state in one word: lock->owner, a task_struct * whose bit 0 is stolen as the “has waiters” flag (legal because task_struct is at least 2-byte aligned on every architecture) (rt-mutex.rst):

ownerbit 0meaning
NULL0free — fast cmpxchg acquire possible
NULL1free, has waiters; top waiter is about to take it
taskptr0held — fast cmpxchg release possible
taskptr1held and has waiters

The fast paths exploit this. Uncontended acquire: a single cmpxchg swaps NULL→current into owner (only legal when bit 0 is 0). Uncontended release: a single cmpxchg swaps current→NULL. There is zero internal locking overhead when locking a free mutex or unlocking one with no waiters — the design is “optimized for fastpath operations” (rt-mutex.rst). The “has waiters” bit is the trip-wire: once set, an unlocking owner is forced into the slow path (it must take wait_lock and hand the lock to a waiter) rather than the bare cmpxchg, which is how a releasing owner is made to synchronize with the slow-path enqueue/wakeup machinery. (Architectures lacking cmpxchg always take the slow path via an internal spinlock.)

Mechanical Walk-through — Blocking and the Chain Walk

When try_to_take_rt_mutex fails on a contended lock, the slow path calls task_blocks_on_rt_mutex (rtmutex.c, v6.12). With wait_lock held, it builds the waiter struct on the blocking task’s stack, records its priority, and enqueues it:

waiter->task = task;
waiter->lock = lock;
waiter_update_prio(waiter, task);          /* snapshot prio + deadline into the node */
...
rt_mutex_enqueue(lock, waiter);            /* into lock->waiters, sorted by prio */
task->pi_blocked_on = waiter;              /* this task is now blocked-on this waiter */

Then, if this new waiter became the lock’s top waiter, the owner’s pi_waiters tree changes and the owner’s priority must be reconsidered:

if (waiter == rt_mutex_top_waiter(lock)) {
	rt_mutex_dequeue_pi(owner, top_waiter);   /* remove old top from owner's pi tree */
	rt_mutex_enqueue_pi(owner, waiter);       /* insert new top */
	rt_mutex_adjust_prio(lock, owner);        /* boost the owner if needed */
	if (owner->pi_blocked_on)
		chain_walk = 1;                   /* owner itself is blocked -> propagate */
}

That last condition is the trigger for the PI chain walk. If the owner we just boosted is itself blocked on another rt_mutex, the boost must ripple down to that lock’s owner too, and so on. The walk is rt_mutex_adjust_prio_chain.

flowchart LR
  E["E (top, urgent)<br/>blocked on"] --> L4["L4"]
  L4 --> D["D<br/>blocked on"]
  D --> L3["L3"]
  L3 --> C["C<br/>blocked on"]
  C --> L2["L2"]
  L2 --> B["B<br/>blocked on"]
  B --> L1["L1"]
  L1 --> A["A (root owner)"]

What it shows: a PI chain E->L4->D->L3->C->L2->B->L1->A — each task is blocked on a lock owned by the next, ending at A who is blocked on nothing. The insight: when E (most urgent) joins the chain, its urgency must propagate all the way to A, because A is the task that actually has to run to start unwinding the whole stack. Chains can merge (two tasks blocked on the same lock) but never diverge (a task is blocked on at most one lock at a time), so following pi_blocked_on links always reaches a single root.

The chain walk’s careful lock dance

rt_mutex_adjust_prio_chain is the subtle heart of the subsystem. Its design constraint: stay preemptible while walking a potentially long chain, holding at most two locks at any instant (rtmutex.c, “Chain walk basics” comment, v6.12). It cannot grab every pi_lock and wait_lock in the chain at once — that would disable preemption for the whole walk and could itself deadlock. So it “hand-over-hands” up the chain, one step per iteration:

  1. lock(task->pi_lock) and read waiter = task->pi_blocked_on — the lock this task is blocked on.
  2. Check exit conditions: if waiter is NULL the chain ended; if the lock graph changed under us (the task moved to a different lock than next_lock recorded), bail.
  3. Try-lock the mutex’s wait_lock; if it fails, drop pi_lock and retry (cpu_relax()) — never block while holding pi_lock.
  4. Deadlock check: if this lock is the original lock, or owned by the task that started the walk, we have a cycle → -EDEADLK.
  5. Requeue the waiter in the mutex’s waiters tree at its new priority; requeue it in the owner’s pi_waiters tree; recompute the owner’s priority.
  6. Drop pi_lock, step task = owner(lock), take the new owner’s pi_lock, and goto again.

The walk is also length-limited: max_lock_depth = 1024 (defined in rtmutex_api.c); exceeding it returns -EDEADLK and logs a warning, defending against a malicious userspace nesting an enormous chain of PI-futexes to make the kernel spin holding locks (rtmutex.c, v6.12). The maximum chain depth is bounded by mutex nesting depth, but is hard to compute statically because nesting is created dynamically across functions — hence a runtime cap.

The deadlock-detection step is where rt_mutex and ww_mutex interact. A ww_mutex on PREEMPT_RT is built on an rt_mutex, and the wound/die backoff protocol can create spurious cycles in the lock graph that are not true deadlocks. The chain walk explicitly recognizes this and, when the cycle involves a ww context, suppresses the -EDEADLK and lets the die logic decide which contender backs off instead:

if (lock == orig_lock || rt_mutex_owner(lock) == top_task) {
	ret = -EDEADLK;
	/* When the deadlock is due to ww_mutex ... let the ww_mutex
	 * wound/die logic pick which contending thread gets -EDEADLK. */
	if (IS_ENABLED(CONFIG_PREEMPT_RT) && orig_waiter && orig_waiter->ww_ctx)
		ret = 0;
	...
}

Unlock — Handing Off and Dropping the Boost

When an owner releases a contended rt_mutex, the slow unlock path takes wait_lock, finds the lock’s top waiter, removes it from both the mutex’s waiters tree and the owner’s pi_waiters tree, and marks the owner field so a lower-priority task cannot steal the lock from the designated next owner (the “pending owner” — the woken top waiter) (rt-mutex-design.rst, Unlocking). Because the released waiter leaves the owner’s pi_waiters tree, the next rt_mutex_adjust_prio recomputes the owner’s priority from whatever (if anything) remains — that is where the boost is immediately removed. The rt-mutex.rst is emphatic: “The priority boosting is immediately removed once the rt_mutex has been unlocked.” An owner never carries a stale boost past the release of the lock that caused it.

The woken top waiter (no longer literally called a “pending owner” in the code, though the concept persists) retries try_to_take_rt_mutex; if it succeeds it becomes the owner and pulls the new top waiter into its own pi_waiters tree. If another task stole the lock in the race window, it goes back to sleep.

The PI-Futex — Priority Inheritance for Userspace Mutexes

The rt_mutex exists in mainline (outside PREEMPT_RT) primarily to back PI-futexes. A userspace pthread_mutex_t created with the PTHREAD_PRIO_INHERIT protocol maps, in the contended case, onto the FUTEX_LOCK_PI / FUTEX_UNLOCK_PI futex operations, which the kernel implements using a per-futex rt_mutex so that the userspace lock gets the same PI guarantee as a kernel rt_mutex (rt-mutex.rst, v6.12). The futex word in userspace stores the owner’s thread ID (TID); when a higher-priority thread blocks, the kernel boosts the owning thread until it issues FUTEX_UNLOCK_PI. This lets a real-time application keep its critical sections inside high-priority threads without sacrificing determinism — the whole point of pthread_mutex PI support. The deeper futex mechanics, including the robust-futex and requeue-PI variants, live in Futex and OS Synchronization Primitives and the kernel-side The Kernel Futex Interface.

Uncertain

Verify: the precise mapping that glibc’s PTHREAD_PRIO_INHERIT contended path issues FUTEX_LOCK_PI/FUTEX_UNLOCK_PI. Reason: stated in rt-mutex.rst that “RT-mutexes … support PI-futexes, which enable pthread_mutex_t priority inheritance attributes (PTHREAD_PRIO_INHERIT),” but the exact futex opcode sequence is from pi-futex.rst / glibc, not re-verified here against those sources. To resolve: read Documentation/locking/pi-futex.rst and glibc’s nptl mutex implementation.

On PREEMPT_RT — Almost Every Lock Becomes a PI Mutex

The largest consumer of the rt_mutex is the PREEMPT_RT configuration. Its very Kconfig help text describes what it does: it “turns the kernel into a real-time kernel by replacing various locking primitives (spinlocks, rwlocks, etc.) with preemptible priority-inheritance aware variants, enforcing interrupt threading and introducing mechanisms to break up long non-preemptible sections” (Kconfig.preempt, v6.12). On PREEMPT_RT, a spinlock_t no longer disables preemption and busy-waits — it becomes a sleeping lock built on the rt_mutex core (the RT_MUTEX_BUILD_SPINLOCKS build variant), so a task blocked on what looks like a spinlock can be preempted, and the holder is PI-boosted. Only the genuine raw_spinlock_t stays a true non-preemptible spin lock — see Raw Spinlocks and PREEMPT_RT and The PREEMPT_RT Real-Time Kernel for the full conversion story. This is why determinism on RT depends utterly on the rt_mutex being correct and its chain walk bounded: every contended lock acquisition in the kernel may now trigger a PI boost.

A subtlety visible in the code: under RT_MUTEX_BUILD_SPINLOCKS, RT tasks are excluded from same-priority (“lateral”) lock stealing (rt_mutex_steal), specifically to prevent unbounded latency — a same-priority steal could let a long chain of equal-priority tasks indefinitely defer one of them.

Failure Modes and Common Misunderstandings

  • PI is not a deadlock fix. It bounds inversion (waiting time), not deadlock (cyclic waiting). An AB-BA lock-ordering bug still deadlocks an rt_mutex; the chain walk’s -EDEADLK is a detector of self-deadlock during the boost walk, not a general avoider. For multi-lock acquisition without a fixed order, you need ww_mutex, not PI.
  • PI is not a license for sloppy design. The kernel doc is blunt: “Priority inheritance is not a magic bullet for poorly designed applications.” It rescues well-designed code from inversion; it cannot fix a critical section that is simply too long.
  • Boost is transitive but bounded by max_lock_depth = 1024. A pathologically deep PI-futex chain returns -EDEADLK rather than letting the walk run unbounded.
  • pi_lock is IRQ-sensitive. Because a task’s pi_lock can be taken from interrupt context, all PI bookkeeping disables interrupts; getting this wrong is a classic lockdep splat.
  • De-boost timing. Some assume a boosted task keeps the boost until it sleeps; in fact the boost is recomputed every time a waiter joins or leaves, and is dropped the instant the causing lock is unlocked.

Alternatives — Other Cures for Priority Inversion

PI is one of several classical remedies; the kernel chose it for futexes and RT for specific reasons:

  • Priority ceiling protocol (PCP). Each lock is statically assigned a ceiling = the highest priority of any task that may take it; an acquiring task is immediately raised to the ceiling. It bounds inversion and also prevents deadlock and chained blocking, but requires knowing all users of a lock at design time — impractical for a general-purpose kernel and for userspace pthread mutexes. Linux exposes PTHREAD_PRIO_PROTECT for this at the pthread level, but the kernel rt_mutex implements inheritance, not ceiling.
  • Disabling preemption / interrupts around the critical section (what a non-RT spinlock_t effectively does). Trivially prevents inversion for that section but is unusable when the holder may sleep, and destroys RT latency if the section is long.
  • Non-blocking / lockless algorithms (RCU, lock-free structures) sidestep inversion by not holding locks at all — the preferred answer where applicable, but not always feasible.

PI wins for the kernel/futex case precisely because it needs no static knowledge of a lock’s users: it reacts dynamically to whoever actually blocks.

Production Notes

The rt_mutex’s correctness is load-bearing for the entire real-time Linux ecosystem (industrial control, audio, telecom, robotics) now that PREEMPT_RT is mainline. Its fast paths mean the common uncontended case costs a single cmpxchg, identical to a plain mutex; the PI machinery only activates under real contention with priority disparity. The chain-walk code is famously delicate — its “Chain walk basics and protection scope” comment by Thomas Gleixner enumerates the exact lock-acquisition steps [1]–[13] and which lock protects each, because the preemptible, two-locks-at-a-time invariant is easy to violate. The interaction with ww_mutex (spurious cycles deferred to wound/die) and with SCHED_DEADLINE (deadline inheritance via dl_time_before) are the two places the subsystem reaches beyond plain priority numbers, and both are recent enough additions that they warrant care when reading older treatments of rt_mutex that predate them.

See Also

Graph View

Backlinks