From: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
To: juri.lelli@redhat.com, peterz@infradead.org, mingo@redhat.com,
vincent.guittot@linaro.org
Cc: linux-kernel@vger.kernel.org,
Mathieu Desnoyers <mathieu.desnoyers@efficios.com>,
tglx@kernel.org, will@kernel.org, boqun@kernel.org,
dietmar.eggemann@arm.com, rostedt@goodmis.org,
bsegall@google.com, mgorman@suse.de, vschneid@redhat.com,
kprateek.nayak@amd.com, luca.abeni@santannapisa.it,
mathieu.poirier@linaro.org, longman@redhat.com,
ridong.chen@linux.dev, tj@kernel.org, hannes@cmpxchg.org,
mkoutny@suse.com, shuah@kernel.org, bigeasy@linutronix.de,
clrkwllms@kernel.org, parri.andrea@gmail.com,
m.szyprowski@samsung.com, kayracizmeci@gmail.com,
weihengqiuu@gmail.com, cgroups@vger.kernel.org,
linux-kselftest@vger.kernel.org, linux-rt-devel@lists.linux.dev,
stable@vger.kernel.org
Subject: [PATCH v7 09/40] rtmutex: Continue the chain walk when a waiter's deadline donor changes
Date: Tue, 17 Nov 2026 09:10:30 -0500 [thread overview]
Message-ID: <c8b228501d8981454f63843b394019fefd4002f3.1794922146.git.mathieu.desnoyers@efficios.com> (raw)
In-Reply-To: <cover.1794922146.git.mathieu.desnoyers@efficios.com>
A task boosted by a SCHED_DEADLINE waiter runs on the parameters of a
donor, dl.pi_se. Commit 2279f540ea7d ("sched/deadline: Fix priority
inheritance with multiple scheduling classes") made the donor follow the
chain. rt_mutex_setprio() copies the donor of the top waiter to the
owner. So the owner at the end of a chain points at the deadline task at
its head. That task waits on no lock the owner holds.
The chain walk stops at a task whose waiter has the same sort keys as
the task: the priority and the deadline. Then "there is no further
priority adjustment necessary". Before 2279f540ea7d, this was enough.
The refill read the parameters of the owner's own top waiter, which is
blocked and so alive.
But a boost can change the donor of a blocked task and leave its keys
as they were. The task keeps a deadline priority. It sleeps, so no
refill moves its deadline. The walk then stops one lock too early.
M and O are SCHED_OTHER tasks. W and Z are SCHED_DEADLINE tasks. Z has
the earlier deadline. L1, L1' and L2 are rt_mutexes:
O M W Z
locks L2 locks L1 and L1'
blocks on L1'
rt_mutex_setprio(M, W)
M->dl.pi_se = &W->dl
blocks on L2
rt_mutex_setprio(O, M)
O->dl.pi_se = &W->dl
blocks on L1
rt_mutex_setprio(M, Z)
M->dl.pi_se = &Z->dl
chain walk at M:
keys equal, stops
times out on L1'
exits
O runs on W's parameters, with a later deadline than Z's, while Z waits
for it. After W exits, O's next refill would read W's freed task_struct.
A deboost has the same effect. Take a deadline task that a waiter with
an earlier deadline boosts, and that blocks on a second lock. It keeps
its own deadline. When that waiter leaves, rt_mutex_setprio() makes the
task its own donor again. Its keys stay equal. A policy change in
__setscheduler_dl_pi() can also change the donor of a blocked task with
no change of keys. rt_mutex_adjust_pi() then skips the walk.
Setting up the deadline tasks needs CAP_SYS_NICE. The timeout of a
FUTEX_LOCK_PI needs no privilege. The Sashiko AI review of the sixth
posting of this series found the deboost case.
Fix this by recording the donor in the waiter with the sort keys, in
waiter_update_prio(). rt_waiter_up_to_date() compares both. The walk and
rt_mutex_adjust_pi() use it. A new donor then takes the walk on to the
next owner, and rt_mutex_setprio() gives that owner the new donor. The
waiter's copy is only compared, never dereferenced. A task without a
deadline priority is always its own donor, so its walks do not change.
A known limit remains. Two walks can overlap on a chain of three locks
or more. The owners further down then keep the old donor until the
first walk reaches them.
The case pi_chain_donor_leaves of deadline_bw_test, added later in this
series, tests the missed boost. W leaves SCHED_DEADLINE there, in place
of exiting. Without this patch, another deadline task gets no CPU time.
On v7.4-rc2 the case passes. There, a blocked task that leaves
SCHED_DEADLINE keeps its parameters, so O runs on W's.
Fixes: 2279f540ea7d ("sched/deadline: Fix priority inheritance with multiple scheduling classes")
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: stable@vger.kernel.org # v5.15+
---
kernel/locking/rtmutex.c | 22 ++++++++++++++++++++--
kernel/locking/rtmutex_api.c | 2 +-
kernel/locking/rtmutex_common.h | 3 +++
3 files changed, 24 insertions(+), 3 deletions(-)
diff --git a/kernel/locking/rtmutex.c b/kernel/locking/rtmutex.c
index 5a9534c715b8..c78dfe9c93fc 100644
--- a/kernel/locking/rtmutex.c
+++ b/kernel/locking/rtmutex.c
@@ -369,10 +369,12 @@ static __always_inline void
waiter_update_prio(struct rt_mutex_waiter *waiter, struct task_struct *task)
{
lockdep_assert_held(&waiter->lock->wait_lock);
+ lockdep_assert_held(&task->pi_lock);
lockdep_assert(RB_EMPTY_NODE(&waiter->tree.entry));
waiter->tree.prio = __waiter_prio(task);
waiter->tree.deadline = task->dl.deadline;
+ waiter->pi_se = task->dl.pi_se;
}
/*
@@ -433,6 +435,21 @@ static __always_inline int rt_waiter_node_equal(struct rt_waiter_node *left,
return 1;
}
+/*
+ * Return true if @waiter is up to date with its task @task. Compare the
+ * sort keys and the deadline donor, which rt_mutex_setprio() copies from
+ * @task to the lock owner. A boost or a deboost of @task can change its
+ * donor and leave its keys as they were. The owner must then get the new
+ * donor: the old one can exit. The caller holds @task->pi_lock, which
+ * protects @task->dl.pi_se. @waiter->pi_se is never dereferenced.
+ */
+static __always_inline bool
+rt_waiter_up_to_date(struct rt_mutex_waiter *waiter, struct task_struct *task)
+{
+ return rt_waiter_node_equal(&waiter->tree, task_to_waiter_node(task)) &&
+ waiter->pi_se == task->dl.pi_se;
+}
+
static inline bool rt_mutex_steal(struct rt_mutex_waiter *waiter,
struct rt_mutex_waiter *top_waiter)
{
@@ -824,12 +841,13 @@ static int __sched rt_mutex_adjust_prio_chain(struct task_struct *task,
/*
* If the waiter priority is the same as the task priority
- * then there is no further priority adjustment necessary. If
+ * then there is no further priority adjustment necessary. The
+ * task must also pass on the same deadline donor. If
* deadlock detection is off, we stop the chain walk. If its
* enabled we continue, but stop the requeueing in the chain
* walk.
*/
- if (rt_waiter_node_equal(&waiter->tree, task_to_waiter_node(task))) {
+ if (rt_waiter_up_to_date(waiter, task)) {
if (!detect_deadlock)
goto out_unlock_pi;
else
diff --git a/kernel/locking/rtmutex_api.c b/kernel/locking/rtmutex_api.c
index eb18b094473c..6bdbd36bac94 100644
--- a/kernel/locking/rtmutex_api.c
+++ b/kernel/locking/rtmutex_api.c
@@ -510,7 +510,7 @@ void __sched rt_mutex_adjust_pi(struct task_struct *task)
raw_spin_lock_irqsave(&task->pi_lock, flags);
waiter = task->pi_blocked_on;
- if (!waiter || rt_waiter_node_equal(&waiter->tree, task_to_waiter_node(task))) {
+ if (!waiter || rt_waiter_up_to_date(waiter, task)) {
raw_spin_unlock_irqrestore(&task->pi_lock, flags);
return;
}
diff --git a/kernel/locking/rtmutex_common.h b/kernel/locking/rtmutex_common.h
index c38b7bdea7b3..c0f391c352e3 100644
--- a/kernel/locking/rtmutex_common.h
+++ b/kernel/locking/rtmutex_common.h
@@ -43,6 +43,8 @@ struct rt_waiter_node {
* @pi_tree: node to enqueue into the mutex owner waiters tree
* @task: task reference to the blocked task
* @lock: Pointer to the rt_mutex on which the waiter blocks
+ * @pi_se: The deadline donor of @task when @tree was last updated.
+ * Only compared, never dereferenced.
* @wake_state: Wakeup state to use (TASK_NORMAL or TASK_RTLOCK_WAIT)
* @ww_ctx: WW context pointer
*
@@ -54,6 +56,7 @@ struct rt_mutex_waiter {
struct rt_waiter_node pi_tree;
struct task_struct *task;
struct rt_mutex_base *lock;
+ struct sched_dl_entity *pi_se;
unsigned int wake_state;
struct ww_acquire_ctx *ww_ctx;
};
--
2.47.3
next prev parent reply other threads:[~2026-11-17 14:11 UTC|newest]
Thread overview: 55+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-11-17 14:10 [PATCH v7 00/40] sched/deadline: bandwidth accounting fixes and selftests Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 01/40] sched: Refuse SCHED_FLAG_KEEP_PARAMS that would change the policy or the class Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 02/40] sched/deadline: Do not admit bandwidth for parameters that are kept Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 03/40] sched: Let a task boosted by a deadline waiter change its policy Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 04/40] sched/deadline: Do not divide by zero active CPUs of a root domain Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 05/40] sched/deadline: Refuse dl_server debugfs writes while the rq is offline Mathieu Desnoyers
2026-11-17 14:38 ` sashiko-bot
2026-11-17 14:10 ` [PATCH v7 06/40] sched: Take cpuset_mutex for a deadline policy change only with pi Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 07/40] sched/deadline: Do not lose a throttled task switched out and back Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 08/40] sched/deadline: Do not replenish a boost from cleared parameters Mathieu Desnoyers
2026-11-17 14:10 ` Mathieu Desnoyers [this message]
2026-11-17 14:50 ` [PATCH v7 09/40] rtmutex: Continue the chain walk when a waiter's deadline donor changes sashiko-bot
2026-11-17 14:10 ` [PATCH v7 10/40] sched/deadline: Reset the deadline and the runtime with the parameters Mathieu Desnoyers
2026-11-17 14:55 ` sashiko-bot
2026-11-17 14:10 ` [PATCH v7 11/40] sched/deadline: Reset the donor's runtime at a deboost in the class Mathieu Desnoyers
2026-11-17 14:55 ` sashiko-bot
2026-11-17 14:10 ` [PATCH v7 12/40] sched/deadline: Replenish a throttled task boosted while asleep Mathieu Desnoyers
2026-11-17 14:55 ` sashiko-bot
2026-11-17 14:10 ` [PATCH v7 13/40] sched/deadline: Release the bandwidth of a task that leaves the class asleep Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 14/40] sched/deadline: Reject SCHED_DEADLINE on exited tasks Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 15/40] sched/deadline: Keep departing bandwidth across a root domain rebuild Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 16/40] sched/deadline: Fix this_bw when a task is changed during a remote wakeup Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 17/40] sched/deadline: Rebuild the root domains' accounting from the task list Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 18/40] sched/deadline: Record the root domain holding a task's bandwidth Mathieu Desnoyers
2026-11-17 15:14 ` sashiko-bot
2026-11-17 14:10 ` [PATCH v7 19/40] sched/deadline: Leave a dying task out of a rebuild of the accounting Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 20/40] sched/deadline: Check SCHED_DEADLINE affinity under the rq lock Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 21/40] sched/deadline: Move a task's bandwidth only where room was made Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 22/40] cgroup/cpuset: Wait for an attach before rebuilding the sched domains Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 23/40] sched: Make deadline policy and affinity changes wait for a cpuset attach Mathieu Desnoyers
2026-11-17 15:18 ` sashiko-bot
2026-11-17 14:10 ` [PATCH v7 24/40] cgroup/cpuset: Give back the bandwidth an attach did not move Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 25/40] cgroup/cpuset: Reserve the bandwidth in the root domain a task moves to Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 26/40] sched/deadline: Make a rebuild count a task in the root domain it runs in Mathieu Desnoyers
2026-11-17 15:31 ` sashiko-bot
2026-11-17 14:10 ` [PATCH v7 27/40] sched/deadline: Move a task's bandwidth to " Mathieu Desnoyers
2026-11-17 15:29 ` sashiko-bot
2026-11-17 14:10 ` [PATCH v7 28/40] sched/deadline: Keep a task in the root domain that counts its bandwidth Mathieu Desnoyers
2026-11-17 15:32 ` sashiko-bot
2026-11-17 14:10 ` [PATCH v7 29/40] sched/deadline: Keep the last CPU a task has in its root domain Mathieu Desnoyers
2026-11-17 15:41 ` sashiko-bot
2026-11-17 14:10 ` [PATCH v7 30/40] cgroup/cpuset: Refuse to take a deadline task out of " Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 31/40] sched/deadline: Cancel the replenishment timer with the parameters Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 32/40] sched/deadline: Count the bandwidth a boosted task is given Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 33/40] sched/deadline: Start a period for a task that enters the class blocked Mathieu Desnoyers
2026-11-17 15:46 ` sashiko-bot
2026-11-17 14:10 ` [PATCH v7 34/40] sched/deadline: Cap the runtime left of a constrained task at dl_runtime Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 35/40] sched/deadline: Check the runtime of a task that comes back runnable Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 36/40] sched/deadline: Check the runtime of a task whose parameters change Mathieu Desnoyers
2026-11-17 15:45 ` sashiko-bot
2026-11-17 14:10 ` [PATCH v7 37/40] sched/debug: Show the deadline bandwidth of each runqueue Mathieu Desnoyers
2026-11-17 14:10 ` [PATCH v7 38/40] selftests/sched: Add a test of SCHED_DEADLINE policy round trips Mathieu Desnoyers
2026-11-17 15:23 ` sashiko-bot
2026-11-17 14:11 ` [PATCH v7 39/40] selftests/sched: Test SCHED_DEADLINE bandwidth across a root domain rebuild Mathieu Desnoyers
2026-11-17 14:11 ` [PATCH v7 40/40] selftests/sched: Add a test of SCHED_DEADLINE bandwidth accounting Mathieu Desnoyers
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=c8b228501d8981454f63843b394019fefd4002f3.1794922146.git.mathieu.desnoyers@efficios.com \
--to=mathieu.desnoyers@efficios.com \
--cc=bigeasy@linutronix.de \
--cc=boqun@kernel.org \
--cc=bsegall@google.com \
--cc=cgroups@vger.kernel.org \
--cc=clrkwllms@kernel.org \
--cc=dietmar.eggemann@arm.com \
--cc=hannes@cmpxchg.org \
--cc=juri.lelli@redhat.com \
--cc=kayracizmeci@gmail.com \
--cc=kprateek.nayak@amd.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-kselftest@vger.kernel.org \
--cc=linux-rt-devel@lists.linux.dev \
--cc=longman@redhat.com \
--cc=luca.abeni@santannapisa.it \
--cc=m.szyprowski@samsung.com \
--cc=mathieu.poirier@linaro.org \
--cc=mgorman@suse.de \
--cc=mingo@redhat.com \
--cc=mkoutny@suse.com \
--cc=parri.andrea@gmail.com \
--cc=peterz@infradead.org \
--cc=ridong.chen@linux.dev \
--cc=rostedt@goodmis.org \
--cc=shuah@kernel.org \
--cc=stable@vger.kernel.org \
--cc=tglx@kernel.org \
--cc=tj@kernel.org \
--cc=vincent.guittot@linaro.org \
--cc=vschneid@redhat.com \
--cc=weihengqiuu@gmail.com \
--cc=will@kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®