[RFC PATCH v1 3/8] sched/proxy: Stop the chain walk when the blocked_on chain is a cycle

From: Mathieu Desnoyers

Date: Mon Nov 16 2026 - 14:26:56 EST


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@xxxxxxxxxxxx>
---
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