What PREEMPT_RT Changes: Priority Inheritance (Part 2)

Part 1 of this series, Sleeping Spinlocks, ended at the substitution that makes PREEMPT_RT work: spinlock_t becomes an rtmutex, and a task that cannot acquire one sleeps instead of spinning. That creates a problem it must then solve. A sleeping lock holder can be preempted, and a low-priority task holding a lock a high-priority task needs will block it for as long as the scheduler leaves it descheduled. The mechanism that bounds this is priority inheritance, and it is why the rtmutex is a different data structure from a plain mutex rather than the same structure renamed.

This part takes the rtmutex itself: how priority inheritance is computed, where it is recorded, what happens when the boosted owner is also blocked, and why the same treatment cannot be given to every locking primitive. Everything below was read from kernel/locking/ in mainline this week.

Priority inheritance is an assignment, not an increment

The textbook description is that a lock holder is raised to the priority of the task waiting on it. Read that way it sounds like a sequence of adjustments: raise on contention, lower on release, keep the two balanced. If that were the implementation, every boost would need a matching unboost, and nested locks would need a stack of saved priorities to restore in order.

The kernel does not do this. The entire computation is here:

static __always_inline void rt_mutex_adjust_prio(struct rt_mutex_base *lock,
                                                 struct task_struct *p)
{
        struct task_struct *pi_task = NULL;

        lockdep_assert_held(&lock->wait_lock);
        lockdep_assert(rt_mutex_owner(lock) == p);
        lockdep_assert_held(&p->pi_lock);

        if (task_has_pi_waiters(p))
                pi_task = task_top_pi_waiter(p)->task;

        rt_mutex_setprio(p, pi_task);
}

There is no addition and no saved value. The owner either has waiters, in which case it is given the priority of the single highest-ranked one, or it has none, in which case pi_task is NULL and the task returns to its own priority. Every call recomputes the answer from the current state of the tree. That is why the boost cannot leak: there is no accumulated adjustment to lose track of. Releasing a lock removes a waiter, the recomputation runs again, and the result follows from what is left rather than from what was done earlier.

The boost is also not transitive by arithmetic. A task holding two contended locks is not boosted twice: both locks’ top waiters are entries in the same per-task tree, and the owner takes the highest.

A blocked task sits in two red-black trees

Priority inheritance needs to find the boost quickly, and the structure that makes that possible is struct rt_mutex_waiter, allocated on the stack of the task that blocks. Its first two members are the part worth studying:

struct rt_waiter_node {
        struct rb_node  entry;
        int             prio;
        u64             deadline;
};

struct rt_mutex_waiter {
        struct rt_waiter_node   tree;
        struct rt_waiter_node   pi_tree;
        struct task_struct      *task;
        struct rt_mutex_base    *lock;
        unsigned int            wake_state;
        struct ww_acquire_ctx   *ww_ctx;
};

Two nodes, two trees, one waiter. The header’s comment states what each is for and which lock protects it:

 * @tree:            node to enqueue into the mutex waiters tree
 * @pi_tree:         node to enqueue into the mutex owner waiters tree
 ...
 * @tree is ordered by @lock->wait_lock
 * @pi_tree is ordered by rt_mutex_owner(@lock)->pi_lock

The tree node goes into lock->waiters, the tasks queued on that one lock, and answers “who gets this lock next”. The pi_tree node goes into owner->pi_waiters, all tasks blocked on any lock this task holds, and answers “what priority must this task run at”. Separating the two is what makes the boost cheap: the owner’s priority is the leftmost node of one tree, not a walk over every lock it holds.

The nodes also carry their own copies of the sort keys. waiter_update_prio() sets tree.prio and tree.deadline from the task; waiter_clone_prio() copies them to pi_tree. Duplicating them looks wasteful until you notice the lock annotations: the trees are protected by different locks, so one shared copy could not be read safely from both paths.

What the ordering actually compares

Both trees use the same comparison, and it contains a detail that changes who benefits from priority inheritance:

static __always_inline int __waiter_prio(struct task_struct *task)
{
        int prio = task->prio;

        if (!rt_or_dl_prio(prio))
                return DEFAULT_PRIO;

        return prio;
}

A task that is neither real-time nor deadline-scheduled does not contribute its own priority at all; it is flattened to DEFAULT_PRIO. Every ordinary scheduler task therefore sorts equal in these trees whatever its nice value, so a nice -19 task gains nothing over a nice 0 task when queueing on an rtmutex, and boosts an owner no harder. This is a real-time mechanism, not a general fairness mechanism.

Above that, the comparison is priority first and then deadline:

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;

        /*
         * If both waiters have dl_prio(), we check the deadlines of the
         * associated tasks.
         ...
         */
        if (dl_prio(left->prio))
                return dl_time_before(left->deadline, right->deadline);

        return 0;
}

Lower prio wins, since the kernel’s internal numbering runs opposite to the SCHED_FIFO numbers you set from user space. For two SCHED_DEADLINE tasks at the same level the earlier absolute deadline wins, which keeps deadline semantics intact through a lock rather than degrading them to fixed-priority ordering.

The chain walk, when the boosted owner is itself blocked

The hard case is not one lock. It is a task blocking on a lock whose owner is itself blocked on a second lock. Boosting the first owner achieves nothing, because that owner is not runnable either, so the boost has to follow the chain to whichever task is actually holding things up.

The priority inheritance walk is rt_mutex_adjust_prio_chain(), whose comment block is the most valuable documentation in the file. The loop it describes:

 *      again:
 *        loop_sanity_check();
 *      retry:
 * [1]    lock(task->pi_lock);                  [R] acquire [P1]
 * [2]    waiter = task->pi_blocked_on;         [P1]
 * [3]    check_exit_conditions_1();            [P1]
 * [4]    lock = waiter->lock;                  [P1]
 * [5]    if (!try_lock(lock->wait_lock)) {     [P1] try to acquire [L]
 *          unlock(task->pi_lock);              release [P1]
 *          goto retry;
 *        }
 * [6]    check_exit_conditions_2();            [P1] + [L]
 * [7]    requeue_lock_waiter(lock, waiter);    [P1] + [L]
 * [8]    unlock(task->pi_lock);                release [P1]
 *        put_task_struct(task);                release [R]
 * [9]    check_exit_conditions_3();            [L]
 * [10]   task = owner(lock);                   [L]
 *        get_task_struct(task);                [L] acquire [R]
 *        lock(task->pi_lock);                  [L] acquire [P2]
 * [11]   requeue_pi_waiter(tsk, waiters(lock));[P2] + [L]
 * [12]   check_exit_conditions_4();            [P2] + [L]
 * [13]   unlock(task->pi_lock);                release [P2]
 *        unlock(lock->wait_lock);              release [L]
 *        goto again;

Read steps 7 and 11 together and the two-tree design pays off. Step 7 requeues the waiter in the lock’s own tree, because its priority changed; step 11 requeues it in the new owner’s PI tree, because that owner’s priority now depends on it. One waiter, two requeues, two different locks held at the two moments. A single-tree design would have to hold both locks for the whole operation.

Which brings up the constraint the author states explicitly just above the loop:

        /*
         * The (de)boosting is a step by step approach with a lot of
         * pitfalls. We want this to be preemptible and we want hold a
         * maximum of two locks per step. So we have to check
         * carefully whether things change under us.
         */

Two locks at a time, and preemptible. That requirement explains everything else. The chain is not walked under one big lock, so the walk re-checks its assumptions at each step — the four check_exit_conditions_* calls. It also explains step 5: the normal order is rtmutex->wait_lock then task->pi_lock, and the walk needs them the other way round, so it try-locks and restarts rather than risking a deadlock in the deadlock-avoidance code.

The practical consequence is that the operation is not a constant-time event: it is a bounded walk whose length depends on how deeply your locks nest, interruptible part-way through by something more urgent.

Where the chain stops

A priority inheritance walk cannot be unbounded, because a cycle in the lock graph would make it run forever. The limit is a plain integer with a sysctl behind it, declared in kernel/locking/rtmutex_api.c:

int max_lock_depth = 1024;

And the exit, at the top of the loop:

        if (++depth > max_lock_depth) {
                static int prev_max;

                /*
                 * Print this only once. If the admin changes the limit,
                 * print a new message when reaching the limit again.
                 */
                if (prev_max != max_lock_depth) {
                        prev_max = max_lock_depth;
                        printk(KERN_WARNING "Maximum lock depth %d reached "
                               "task: %s (%d)\n", max_lock_depth,
                               top_task->comm, task_pid_nr(top_task));
                }
                put_task_struct(task);

                return -EDEADLK;
        }

Two things are worth noting. The message prints once per limit value, not once per occurrence, so a system hitting this repeatedly produces one line and then goes quiet. And the return is -EDEADLK whether or not a real cycle exists, because 1024 steps of genuine nesting cannot be distinguished from a loop without more work than the limit was meant to avoid. The useful reading of Maximum lock depth 1024 reached is not “there is a deadlock” but “the chain from this task was too deep to resolve”.

Watching it happen on a running system

Two things are observable without patching anything. The depth limit is a sysctl, registered by init_rtmutex_sysctl() with mode 0644, so it is readable and writable at runtime:

raghu@techveda.org:~$ cat /proc/sys/kernel/max_lock_depth
1024

The boost has a tracepoint, sched_pi_setprio, fired from rt_mutex_setprio():

raghu@techveda.org:~$ sudo sh -c 'echo 1 > /sys/kernel/debug/tracing/events/sched/sched_pi_setprio/enable'
raghu@techveda.org:~$ sudo cat /sys/kernel/debug/tracing/trace_pipe

What makes this worth enabling is how the tracepoint computes the value it reports:

        __entry->oldprio        = tsk->prio;
        __entry->newprio        = pi_task ?
                        min(tsk->normal_prio, pi_task->prio) :
                        tsk->normal_prio;
        /* XXX SCHED_DEADLINE bits missing */

Each event reports the task’s comm and pid, the priority it had and the priority it is given. With no pi_task the new value is the task’s own normal_prio, which is the deboost; with one, it is the minimum of normal_prio and the donor’s priority — an assignment bounded by the task’s own priority, never an increase past it.

Note the comment on the last line: the tracepoint carries no deadline fields, so for SCHED_DEADLINE tasks it says a boost occurred but not which deadline won. No trace output is reproduced here because none was captured on hardware; the field list is from the definition in include/trace/events/sched.h.

Why a counting semaphore cannot have priority inheritance

The mechanism needs one thing above all others: a single, recorded owner to boost. Not a count of holders, not a list of waiters — an owner. The rtmutex has one, in lock->owner, which is why rt_mutex_adjust_prio() can assert rt_mutex_owner(lock) == p before doing anything.

Now look at what a counting semaphore is:

/* Please don't access any members of this structure directly */
struct semaphore {
        raw_spinlock_t          lock;
        unsigned int            count;
        struct semaphore_waiter *first_waiter;

#ifdef CONFIG_DETECT_HUNG_TASK_BLOCKER
        unsigned long           last_holder;
#endif
};

There is no owner field. A semaphore initialised with a count of five can have five holders at once, and the structure does not record who any of them are. Even if it did, the question would have no single answer: boosting all five would be wrong, because four may not be holding up the waiter and nothing says which one is. The problem is not that nobody implemented this for semaphores — the operation is not defined for an object with no owner.

The last_holder field is a deliberately limited exception. It exists only when CONFIG_DETECT_HUNG_TASK_BLOCKER is set, and records one holder for the hung-task detector to name in a diagnostic. Nothing in the locking code uses it to make decisions. That it had to be added separately, and only for diagnostics, is itself evidence of the point.

This is why down() and up() are left alone by PREEMPT_RT while spinlock_t and struct mutex are rebuilt on the rtmutex. A counting semaphore in a real-time path is a place where priority inversion is possible and nothing in the kernel will bound it for you.

The reader-writer case, which proves the rule

The clearest confirmation that ownership is the deciding factor is rw_semaphore, which under PREEMPT_RT is split along exactly that line:

#define READER_BIAS             (1U << 31)
#define WRITER_BIAS             (1U << 30)

struct rwbase_rt {
        atomic_t                readers;
        struct rt_mutex_base    rtmutex;
};

One structure, two treatments. The write side takes the embedded rt_mutex_base, so a writer is a recorded owner and is boosted like any other rtmutex holder. The read side is an atomic counter with no owner recorded anywhere. A high-priority writer blocked behind low-priority readers cannot boost them, because there is no “them” to boost. The rule is structural rather than historical: a primitive gets priority inheritance exactly when it records a single owner, and all three cases line up with that.

What this means for code you write

Keep the chains short: the cost of priority inheritance scales with nesting depth, and nested locks are a latency cost on RT in a way they are not on a mainline kernel, where a spinning holder is never descheduled at all. Choose the primitive by ownership rather than by habit — a counting semaphore used as a mutex loses the boost with no warning from the compiler or from lockdep, because the code is perfectly correct and simply has no inversion bound. And do not expect nice values to matter: ordinary tasks are flattened to DEFAULT_PRIO in the waiter trees.

Tracing a locking API down to the structure that records the decision is the habit this work rewards, and it is how the Linux kernel internals course approaches the kernel.

Limits, and what was not verified

Several things are deliberately out of scope. The futex side — PTHREAD_PRIO_INHERIT and the proxy-locking paths that serve it — uses the same rtmutex underneath but reaches it through a different interface, so nothing above describes the user-space behaviour. Priority ceiling is a different protocol, not implemented by the rtmutex at all. The ww_ctx member in struct rt_mutex_waiter belongs to wait-wound mutexes and was not examined.

On verification: all code above was read from mainline this week and quoted as it stands. The max_lock_depth value of 1024 is the compiled-in default and writable at runtime, so a system you are debugging may not be using it. No timing figures appear here because none were measured; the claim that deeper nesting costs more follows from the loop structure, not from a benchmark. The behaviour described is that of CONFIG_PREEMPT_RT builds for the sleeping-lock cases; the rtmutex is also used on non-RT kernels under CONFIG_RT_MUTEXES, where the same logic applies to explicit rtmutex users while spinlock_t remains a spinlock.

Key takeaways

• The rtmutex assigns the owner the priority of the top entry in its PI tree and recomputes it on every change. It is never an increment, so a boost cannot leak.
• Each blocked task is in two red-black trees: the lock’s waiter tree answers who gets the lock next, and the owner’s PI tree answers what priority the owner must run at.
• The two trees are protected by different locks, which is why struct rt_mutex_waiter carries two copies of the sort keys.
• Ordinary scheduler tasks are flattened to DEFAULT_PRIO in those trees, so nice values do not affect rtmutex ordering or boosting.
• The priority inheritance chain walk holds at most two locks per step and stays preemptible, which is why it re-checks its assumptions at each step.
• The walk returns -EDEADLK past max_lock_depth, default 1024, and logs Maximum lock depth once per limit value rather than once per occurrence.
• The sched_pi_setprio tracepoint reports the boost as min(normal_prio, pi_task->prio), making the assign-not-increment behaviour directly observable; max_lock_depth is readable at /proc/sys/kernel/max_lock_depth.
• A primitive can have priority inheritance only if it records a single owner. struct semaphore records none, and nor does the read side of an RT rw_semaphore.

Frequently asked questions

Does priority inheritance add the waiter’s priority to the owner’s?
No. rt_mutex_adjust_prio() assigns the owner the priority of the top entry in its PI waiters tree, or restores the owner’s own priority when that tree is empty. The value is recomputed from current state on every change, not adjusted incrementally.

Why does struct rt_mutex_waiter contain two rb_node members?
One enqueues the waiter in the lock’s own waiters tree, the other in the lock owner’s PI waiters tree. They answer different questions and are protected by different locks, lock->wait_lock and the owner’s pi_lock, which is also why the sort keys are duplicated.

What does “Maximum lock depth 1024 reached” in the kernel log mean?
The chain walk exceeded max_lock_depth and returned -EDEADLK. It does not prove a lock cycle exists; genuine nesting deeper than the limit produces the same result. The task named in the message is where to begin looking.

Why can a counting semaphore not have priority inheritance?
Because struct semaphore records no owner. A semaphore with a count above one can have several holders at once and the structure does not say who they are, so there is no task to boost. last_holder exists only under CONFIG_DETECT_HUNG_TASK_BLOCKER and is a diagnostic, not an ownership record.

Do nice values affect lock ordering on a PREEMPT_RT kernel?
No. __waiter_prio() returns DEFAULT_PRIO for any task that is not real-time or deadline-scheduled, so all ordinary tasks sort equal in the waiter trees. Only SCHED_FIFO, SCHED_RR and SCHED_DEADLINE tasks participate in the ordering.

Further reading

• kernel/locking/rtmutex.c — rt_mutex_adjust_prio(), rt_mutex_adjust_prio_chain() and its chain-walk comment, __waiter_prio() and rt_waiter_node_less().
• kernel/locking/rtmutex_common.h — struct rt_mutex_waiter, struct rt_waiter_node and the lock-protection comments.
• kernel/locking/rtmutex_api.c — the max_lock_depth default and its sysctl registration.
• RT-mutex implementation design — the kernel’s own description of the algorithm and its terminology.
• include/linux/semaphore.h — struct semaphore, showing the absence of an owner field.
• include/linux/rwbase_rt.h — struct rwbase_rt, the reader counter and the embedded rtmutex for writers.
• Lock types and their rules — which primitives change behaviour under CONFIG_PREEMPT_RT and which do not.