From: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
To: jstultz@google.com, peterz@infradead.org, mingo@redhat.com,
juri.lelli@redhat.com, vincent.guittot@linaro.org
Cc: linux-kernel@vger.kernel.org,
Mathieu Desnoyers <mathieu.desnoyers@efficios.com>,
dietmar.eggemann@arm.com, rostedt@goodmis.org,
bsegall@google.com, mgorman@suse.de, vschneid@redhat.com,
kprateek.nayak@amd.com, connoro@google.com, arighi@nvidia.com,
akpm@linux-foundation.org, shuah@kernel.org,
linux-kselftest@vger.kernel.org
Subject: [RFC PATCH v1 3/8] sched/proxy: Stop the chain walk when the blocked_on chain is a cycle
Date: Mon, 16 Nov 2026 14:26:33 -0500 [thread overview]
Message-ID: <20261116192638.233125-4-mathieu.desnoyers@efficios.com> (raw)
In-Reply-To: <20261116192638.233125-1-mathieu.desnoyers@efficios.com>
find_proxy_task() follows the blocked_on chain from the donor to a task
that can run. It holds the rq lock, with interrupts off. It has no bound
on the number of steps.
The walk relies on the chain having an end. The ww_mutex die and wound
paths clear blocked_on for that reason. Their comments say that circular
blocked_on relationships would not resolve otherwise. But two tasks that
take two plain mutexes in opposite orders deadlock for good. Once both
are on one runqueue, the walk goes around the cycle forever.
Without proxy execution, such a deadlock leaves two tasks asleep, and
the hung task detector can report them. With it, the CPU locks up with
its rq lock held. Other CPUs would then block on that lock. In a test
with two CPUs, the guest stopped without a message.
Fix this by detecting the cycle. The walk remembers the task it met at
its last step that is a power of two. When it meets that task again, it
stops the donation and deactivates the donor. The donor then sleeps on
its mutex, as without proxy execution.
Fixes: 7de9d4f94638 ("sched: Start blocked_on chain processing in find_proxy_task()")
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
kernel/sched/core.c | 26 +++++++++++++++++++++++++-
1 file changed, 25 insertions(+), 1 deletion(-)
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index cededdcfd5a3..24105eeeb3c7 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -7135,7 +7135,8 @@ static struct task_struct *
find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
__must_hold(__rq_lockp(rq))
{
- struct task_struct *owner = NULL;
+ struct task_struct *owner = NULL, *mark = NULL;
+ unsigned int steps = 0, mark_at = 1;
bool curr_in_chain = false;
int this_cpu = cpu_of(rq);
struct task_struct *p;
@@ -7145,6 +7146,29 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
for (p = donor; p->is_blocked; p = owner) {
/* if its PROXY_WAKING, do return migration or run if current */
struct mutex *mutex = p->blocked_on;
+
+ /*
+ * The walk came back to a task it already met: the chain is
+ * a cycle. Either the tasks deadlock, or a ww_mutex cycle is
+ * about to be broken. Do not walk it forever with the rq lock
+ * held. Stop the donation: the donor then sleeps on its
+ * mutex, as it does without proxy execution.
+ *
+ * @mark is the task met at the last step that is a power of
+ * two. Once the walk is in a cycle, @mark is soon a task of
+ * that cycle, and the walk meets it again.
+ */
+ if (p == mark) {
+ if (curr_in_chain)
+ goto resched_idle;
+ p = donor;
+ clear_task_blocked_on(p, NULL);
+ goto deactivate;
+ }
+ if (++steps == mark_at) {
+ mark = p;
+ mark_at <<= 1;
+ }
if (!mutex) {
clear_task_blocked_on(p, mutex);
if (task_current(rq, p)) {
--
2.47.3
next prev parent reply other threads:[~2026-11-16 19:26 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-11-16 19:26 [RFC PATCH v1 0/8] sched/proxy: fixes for proxy execution, with selftests Mathieu Desnoyers
2026-11-16 19:26 ` [RFC PATCH v1 1/8] sched/proxy: Reschedule when a blocked task is woken under a proxy Mathieu Desnoyers
2026-11-16 21:12 ` John Stultz
2026-11-16 19:26 ` [RFC PATCH v1 2/8] sched/proxy: Wake blocked RT and deadline tasks through the full path Mathieu Desnoyers
2026-11-16 21:35 ` John Stultz
2026-11-16 19:26 ` Mathieu Desnoyers [this message]
2026-11-16 20:36 ` [RFC PATCH v1 3/8] sched/proxy: Stop the chain walk when the blocked_on chain is a cycle John Stultz
2026-11-16 19:26 ` [RFC PATCH v1 4/8] sched/proxy: Tell the class about a proxy migration Mathieu Desnoyers
2026-11-16 20:42 ` John Stultz
2026-11-16 19:26 ` [RFC PATCH v1 5/8] sched/proxy: Clear blocked_donor when the donor stops donating Mathieu Desnoyers
2026-11-16 19:26 ` [RFC PATCH v1 6/8] sched/deadline: Use the root domain a proxy-migrated task runs in Mathieu Desnoyers
2026-11-16 19:26 ` [RFC PATCH v1 7/8] lib: Add test_proxy_exec, kernel mutexes that user space can hold Mathieu Desnoyers
2026-11-16 19:26 ` [RFC PATCH v1 8/8] selftests/sched: Add tests of proxy execution Mathieu Desnoyers
2026-11-16 20:27 ` [RFC PATCH v1 0/8] sched/proxy: fixes for proxy execution, with selftests John Stultz
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=20261116192638.233125-4-mathieu.desnoyers@efficios.com \
--to=mathieu.desnoyers@efficios.com \
--cc=akpm@linux-foundation.org \
--cc=arighi@nvidia.com \
--cc=bsegall@google.com \
--cc=connoro@google.com \
--cc=dietmar.eggemann@arm.com \
--cc=jstultz@google.com \
--cc=juri.lelli@redhat.com \
--cc=kprateek.nayak@amd.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-kselftest@vger.kernel.org \
--cc=mgorman@suse.de \
--cc=mingo@redhat.com \
--cc=peterz@infradead.org \
--cc=rostedt@goodmis.org \
--cc=shuah@kernel.org \
--cc=vincent.guittot@linaro.org \
--cc=vschneid@redhat.com \
/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®