Skip to contentSkip to conversation

sched/proxy_exec: Limit find_proxy_task() chain depth to prevent CPU hang

PATCH In review [email protected] 4 participants 18 messages Apr 14 – Sep 14

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 sched/proxy_exec: Limit find_proxy_task() chain depth to prevent CPU hang

From: zhidao su <[email protected]>

find_proxy_task() follows the blocked_on chain with:

for (p = donor; task_is_blocked(p); p = owner)

The existing WARN_ON(owner == p) only detects immediate self-loops (a task waiting on a mutex it already owns). It does not detect multi-task cycles: if tasks A and B form a cycle where A waits on B's mutex and B waits on A's mutex, the chain traversal loops forever between A and B, hanging the CPU indefinitely while holding rq->lock.

The scenario is real under PE: mutex-blocked tasks are kept on the runqueue (try_to_block_task() with should_block=false), so both A and B remain selectable by pick_next_task(). When A is selected as donor, find_proxy_task() follows A->mutex_B->owner=B->mutex_A->owner=A->... with no termination condition for cycles.

rt-mutex handles this identically with max_lock_depth (default 1024), printing a warning and returning -EDEADLK when the chain is too deep.

Add a chain_depth counter with MAX_PROXY_CHAIN_DEPTH=64. When exceeded, emit WARN_ONCE and call proxy_resched_idle() to schedule idle briefly, consistent with how other unresolvable states are handled in the function (e.g., owner migrating, curr_in_chain bailouts). This keeps the kernel healthy without spinning; the deadlock resolution is the caller's problem.

Tested with a built-in boot-param test (pe_cycle_test) that creates two kthreads on CPU 0 each holding one kernel mutex while trying to acquire the other, forming an A->B->A deadlock cycle.

With this fix:

  [  111.758150] sched/pe: proxy chain depth exceeded 64, possible deadlock cycle involving pid 120
  [  111.758150] WARNING: CPU: 0 PID: 119 at kernel/sched/core.c:7339 __schedule+0x1e6e/0x1e80
  ...
  [  112.694277] pe_cycle_test: still alive after 1s (CPU not hung)

Without this fix, an NMI watchdog (nmi_watchdog=1, watchdog_thresh=15) fires a hard LOCKUP on CPU 0 with RIP in do_raw_spin_lock, called from __schedule, confirming the CPU spins inside find_proxy_task() holding rq->lock with no forward progress:

  [  109.951781] watchdog: CPU0: Watchdog detected hard LOCKUP on cpu 0
  [  109.951781] RIP: 0010:do_raw_spin_lock+0x3e/0xb0
  [  109.951781] Call Trace:
  [  109.951781]  __schedule+0x11e7/0x1e10
  [  109.951781]  schedule_preempt_disabled+0x18/0x30
  [  109.951781]  __mutex_lock+0x6f0/0xac0
  [  109.951781]  pe_test_thread_a+0x9c/0xe0
Fixes 7de9d4f94638 ("sched: Start blocked_on chain processing in find_proxy_task()")
---
 kernel/sched/core.c | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)
kernel/sched/core.c +17 -0
index 3f3425c6b2f2..bafb59432f7f 100644
@@ -7310,6 +7310,17 @@ DEFINE_LOCK_GUARD_1(blocked_on_lock, struct blocked_on_lock,
  * Returns the task that is going to be used as execution context (the one
  * that is actually going to be run on cpu_of(rq)).
  */
+/*
+ * Limit proxy chain traversal depth to avoid infinite loops in pathological
+ * cases (e.g., A waits for B's mutex while B waits for A's mutex). The
+ * existing WARN_ON(owner == p) only catches immediate self-loops; multi-task
+ * cycles like A->B->A are not detected without a depth counter.
+ *
+ * rt-mutex uses a similar guard (max_lock_depth = 1024). We use a smaller
+ * limit since proxy chains are expected to be short in practice.
+ */
+#define MAX_PROXY_CHAIN_DEPTH	64
+
 static struct task_struct *
 find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 	__must_hold(__rq_lockp(rq))
@@ -7318,11 +7329,17 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 	struct task_struct *owner = NULL;
 	bool curr_in_chain = false;
 	int this_cpu = cpu_of(rq);
+	int chain_depth = 0;
 	struct task_struct *p;
 	int owner_cpu;
 
 	/* Follow blocked_on chain. */
 	for (p = donor; task_is_blocked(p); p = owner) {
+		if (++chain_depth > MAX_PROXY_CHAIN_DEPTH) {
+			WARN_ONCE(1, "sched/pe: proxy chain depth exceeded %d, possible deadlock cycle involving pid %d\n",
+				  MAX_PROXY_CHAIN_DEPTH, p->pid);
+			return proxy_resched_idle(rq);
+		}
 		/* copy the entire blocked_on structure */
 		raw_spin_lock(&p->blocked_lock);
 		bo = p->blocked_on;
Signature · 1 line
2.43.0
#1 lore raw
Quoted 22 lines · On Mon, Apr 13, 2026 at 10:36 PM <[email protected]> wrote:

From: zhidao su <[email protected]>

find_proxy_task() follows the blocked_on chain with:

for (p = donor; task_is_blocked(p); p = owner)

The existing WARN_ON(owner == p) only detects immediate self-loops (a task waiting on a mutex it already owns). It does not detect multi-task cycles: if tasks A and B form a cycle where A waits on B's mutex and B waits on A's mutex, the chain traversal loops forever between A and B, hanging the CPU indefinitely while holding rq->lock.

The scenario is real under PE: mutex-blocked tasks are kept on the runqueue (try_to_block_task() with should_block=false), so both A and B remain selectable by pick_next_task(). When A is selected as donor, find_proxy_task() follows A->mutex_B->owner=B->mutex_A->owner=A->... with no termination condition for cycles.

rt-mutex handles this identically with max_lock_depth (default 1024), printing a warning and returning -EDEADLK when the chain is too deep.

Quoted 6 lines

Add a chain_depth counter with MAX_PROXY_CHAIN_DEPTH=64. When exceeded, emit WARN_ONCE and call proxy_resched_idle() to schedule idle briefly, consistent with how other unresolvable states are handled in the function (e.g., owner migrating, curr_in_chain bailouts). This keeps the kernel healthy without spinning; the deadlock resolution is the caller's problem.

Nice. I used a very similar change myself when debugging proxy-exec issues in the early days of getting ww_mutexes working properly. :)

Quoted 16 lines

Tested with a built-in boot-param test (pe_cycle_test) that creates two kthreads on CPU 0 each holding one kernel mutex while trying to acquire the other, forming an A->B->A deadlock cycle.

With this fix:

  [  111.758150] sched/pe: proxy chain depth exceeded 64, possible deadlock cycle involving pid 120
  [  111.758150] WARNING: CPU: 0 PID: 119 at kernel/sched/core.c:7339 __schedule+0x1e6e/0x1e80
  ...
  [  112.694277] pe_cycle_test: still alive after 1s (CPU not hung)

Without this fix, an NMI watchdog (nmi_watchdog=1, watchdog_thresh=15) fires a hard LOCKUP on CPU 0 with RIP in do_raw_spin_lock, called from __schedule, confirming the CPU spins inside find_proxy_task() holding rq->lock with no forward progress:

Quoted 7 lines
  [  109.951781] watchdog: CPU0: Watchdog detected hard LOCKUP on cpu 0
  [  109.951781] RIP: 0010:do_raw_spin_lock+0x3e/0xb0
  [  109.951781] Call Trace:
  [  109.951781]  __schedule+0x11e7/0x1e10
  [  109.951781]  schedule_preempt_disabled+0x18/0x30
  [  109.951781]  __mutex_lock+0x6f0/0xac0
  [  109.951781]  pe_test_thread_a+0x9c/0xe0

So, I guess I'd be curious what happens without proxy-exec.

My sense if if you have a mutex lock cycle today without proxy execution you'll just deadlock and get a similar hard LOCKUP warning. I assume you'd get a LOCKDEP splat as well if that was enabled in either case, no?

So I'm not sure if I see a whole lot of benefit to rescheduling idle over and over to keep the system sort of alive when that cpu is not going to make any progress.

A few more thoughts below...

Quoted 14 lines
Fixes 7de9d4f94638 ("sched: Start blocked_on chain processing in find_proxy_task()")
---
 kernel/sched/core.c | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)
kernel/sched/core.c +0 -0
index 3f3425c6b2f2..bafb59432f7f 100644
@@ -7310,6 +7310,17 @@ DEFINE_LOCK_GUARD_1(blocked_on_lock, struct blocked_on_lock,
  * Returns the task that is going to be used as execution context (the one
  * that is actually going to be run on cpu_of(rq)).
  */

kernel/sched/core.c DEFINE_LOCK_GUARD_1(blocked_on_lock, struct blocked_on_lock, · line 7322

Quoted 10 lines
kernel/sched/core.c +10 -0
+/*
+ * Limit proxy chain traversal depth to avoid infinite loops in pathological
+ * cases (e.g., A waits for B's mutex while B waits for A's mutex). The
+ * existing WARN_ON(owner == p) only catches immediate self-loops; multi-task
+ * cycles like A->B->A are not detected without a depth counter.
+ *
+ * rt-mutex uses a similar guard (max_lock_depth = 1024). We use a smaller
+ * limit since proxy chains are expected to be short in practice.
+ */
+#define MAX_PROXY_CHAIN_DEPTH  64

So while we'd hope proxy chains are short in most cases, there's no guarantee they would be different from rt-mutexes.
In fact, with rwsem support, the chains could interleave across lock types, so I'd probably at least match the rt-mutex value.

Quoted 7 lines
kernel/sched/core.c +0 -0
 static struct task_struct *
 find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
        __must_hold(__rq_lockp(rq))
@@ -7318,11 +7329,17 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
        struct task_struct *owner = NULL;
        bool curr_in_chain = false;
        int this_cpu = cpu_of(rq);

kernel/sched/core.c find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf) · line 7341

Quoted 10 lines
kernel/sched/core.c +5 -0
+       int chain_depth = 0;
        struct task_struct *p;
        int owner_cpu;
 
        /* Follow blocked_on chain. */
        for (p = donor; task_is_blocked(p); p = owner) {
+               if (++chain_depth > MAX_PROXY_CHAIN_DEPTH) {
+                       WARN_ONCE(1, "sched/pe: proxy chain depth exceeded %d, possible deadlock cycle involving pid %d\n",
+                                 MAX_PROXY_CHAIN_DEPTH, p->pid);
+                       return proxy_resched_idle(rq);

So at this point the cpu is going to be stuck, as as soon as it switches to idle, it will call back into __schedule(), select the same donor task and and traverse the same chain, and then reschedule idle and start again.

So it seems to me like BUG() would be more appropriate here as the cpu is effectively deadlocked.

I guess one could deactivate the selected blocked donor task, which would let the cpu continue to run other tasks, but the entire lock chain would eventually get deactivated and would never be woken up, so it would likely trip hung task warnings. So I of would lean towards BUG() since lock cycles are a big no no (for non-ww_mutexes) and I'd fret if you don't stop the system folks will just ignore warnings and not really understand why things aren't working properly.

But that's just my instinct.

Anyway, thanks for the submission here! I'm excited to see more folks working and testing with proxy-exec!

thanks
-john

#2 lore raw

Hello John, Zhidao,

Quoted 21 lines · John Stultz
Quoted 12 lines

With this fix:

  [  111.758150] sched/pe: proxy chain depth exceeded 64, possible deadlock cycle involving pid 120
  [  111.758150] WARNING: CPU: 0 PID: 119 at kernel/sched/core.c:7339 __schedule+0x1e6e/0x1e80
  ...
  [  112.694277] pe_cycle_test: still alive after 1s (CPU not hung)

Without this fix, an NMI watchdog (nmi_watchdog=1, watchdog_thresh=15) fires a hard LOCKUP on CPU 0 with RIP in do_raw_spin_lock, called from __schedule, confirming the CPU spins inside find_proxy_task() holding rq->lock with no forward progress:

Quoted 7 lines
  [  109.951781] watchdog: CPU0: Watchdog detected hard LOCKUP on cpu 0
  [  109.951781] RIP: 0010:do_raw_spin_lock+0x3e/0xb0
  [  109.951781] Call Trace:
  [  109.951781]  __schedule+0x11e7/0x1e10
  [  109.951781]  schedule_preempt_disabled+0x18/0x30
  [  109.951781]  __mutex_lock+0x6f0/0xac0
  [  109.951781]  pe_test_thread_a+0x9c/0xe0
Quoted 1 line

So, I guess I'd be curious what happens without proxy-exec.

I think you hit the hung task detector in that case since the interruptible sleep has lingered for too long.

Quoted 76 lines

My sense if if you have a mutex lock cycle today without proxy execution you'll just deadlock and get a similar hard LOCKUP warning. I assume you'd get a LOCKDEP splat as well if that was enabled in either case, no?

So I'm not sure if I see a whole lot of benefit to rescheduling idle over and over to keep the system sort of alive when that cpu is not going to make any progress.

A few more thoughts below...

Quoted 14 lines
Fixes 7de9d4f94638 ("sched: Start blocked_on chain processing in find_proxy_task()")
---
 kernel/sched/core.c | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)
kernel/sched/core.c +0 -0
index 3f3425c6b2f2..bafb59432f7f 100644
@@ -7310,6 +7310,17 @@ DEFINE_LOCK_GUARD_1(blocked_on_lock, struct blocked_on_lock,
  * Returns the task that is going to be used as execution context (the one
  * that is actually going to be run on cpu_of(rq)).
  */

kernel/sched/core.c DEFINE_LOCK_GUARD_1(blocked_on_lock, struct blocked_on_lock, · line 7322

Quoted 10 lines
kernel/sched/core.c +10 -0
+/*
+ * Limit proxy chain traversal depth to avoid infinite loops in pathological
+ * cases (e.g., A waits for B's mutex while B waits for A's mutex). The
+ * existing WARN_ON(owner == p) only catches immediate self-loops; multi-task
+ * cycles like A->B->A are not detected without a depth counter.
+ *
+ * rt-mutex uses a similar guard (max_lock_depth = 1024). We use a smaller
+ * limit since proxy chains are expected to be short in practice.
+ */
+#define MAX_PROXY_CHAIN_DEPTH  64

So while we'd hope proxy chains are short in most cases, there's no guarantee they would be different from rt-mutexes.
In fact, with rwsem support, the chains could interleave across lock types, so I'd probably at least match the rt-mutex value.

Quoted 7 lines
kernel/sched/core.c +0 -0
 static struct task_struct *
 find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
        __must_hold(__rq_lockp(rq))
@@ -7318,11 +7329,17 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
        struct task_struct *owner = NULL;
        bool curr_in_chain = false;
        int this_cpu = cpu_of(rq);

kernel/sched/core.c find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf) · line 7341

Quoted 10 lines
kernel/sched/core.c +5 -0
+       int chain_depth = 0;
        struct task_struct *p;
        int owner_cpu;
 
        /* Follow blocked_on chain. */
        for (p = donor; task_is_blocked(p); p = owner) {
+               if (++chain_depth > MAX_PROXY_CHAIN_DEPTH) {
+                       WARN_ONCE(1, "sched/pe: proxy chain depth exceeded %d, possible deadlock cycle involving pid %d\n",
+                                 MAX_PROXY_CHAIN_DEPTH, p->pid);
+                       return proxy_resched_idle(rq);

So at this point the cpu is going to be stuck, as as soon as it switches to idle, it will call back into __schedule(), select the same donor task and and traverse the same chain, and then reschedule idle and start again.

So it seems to me like BUG() would be more appropriate here as the cpu is effectively deadlocked.

I guess one could deactivate the selected blocked donor task, which would let the cpu continue to run other tasks, but the entire lock chain would eventually get deactivated and would never be woken up, so it would likely trip hung task warnings. So I of would lean towards BUG() since lock cycles are a big no no (for non-ww_mutexes) and I'd fret if you don't stop the system folks will just ignore warnings and not really understand why things aren't working properly.

Quoted 1 line

But that's just my instinct.

I would second that but I can see someone having a "creative" mutex_lock_interruptible() pattern that relies on the hung task splat to then trigger something from userspace to selectively kill tasks. (Insane? Yes! Possible? Also yes!)

As an alternate approach, when traversing blocked_on links, can we start deactivating the chain if we encounter rq->donor again as owner in find_proxy_task() loop?

That way we go back to triggering the hung task detector and if someone has a stack that depends on it, it'll continue to work fine while also avoiding this lockup.

Thoughts?

Quoted 3 lines

Anyway, thanks for the submission here! I'm excited to see more folks working and testing with proxy-exec!

+1. With the next batch of changes, when we hopefully drop the EXPERT dependency, we'll probably see even wider usage and development ;-)

Signature · 2 lines
Thanks and Regards,
Prateek
author
#3 lore raw

Hello John, Prateek,

Quoted 7 lines · K Prateek Nayak

As an alternate approach, when traversing blocked_on links, can we start deactivating the chain if we encounter rq->donor again as owner in find_proxy_task() loop?

That way we go back to triggering the hung task detector and if someone has a stack that depends on it, it'll continue to work fine while also avoiding this lockup.

Thanks for the suggestion. I've implemented and tested this approach.

On John's point about BUG(): I agree lock cycles are a serious bug, but deactivating the donor preserves mutex_lock_interruptible() recovery paths and avoids a hard system stop for what could be an application-level bug. The WARN_ONCE + hung-task splat provides sufficient visibility.

Changes from v1:
- Replace proxy_resched_idle() with proxy_deactivate() on both the depth-exceeded path and the new cycle-detected path. proxy_resched_idle() returns rq->idle, causing __schedule() to immediately re-select the same donor and re-enter find_proxy_task(), creating a soft loop with no forward progress. (John Stultz)
- Add owner == donor cycle detection immediately after resolving owner from blocked_on. This catches A->B->...->A at the first chain closure; no visited set needed. (Prateek Sood)
- Raise MAX_PROXY_CHAIN_DEPTH from 64 to 1024 to match rt-mutex's max_lock_depth. (John Stultz)

Tested with pe_cycle_kmod (two kthreads pinned to CPU 0, each holding one mutex and trying to acquire the other, virtme-ng, CONFIG_LOCKDEP=n):

  [  109.057659] sched/pe: deadlock cycle detected, pid 154
  [  109.057687] WARNING: CPU: 0 PID: 155 at kernel/sched/core.c:7392
                 find_proxy_task+0x.../...
  ...
  [  246.820220] INFO: task pe_cycle_A:154 blocked for more than 122 seconds.
  [  246.820238] "echo 0 > /proc/sys/kernel/hung_task_timeout_secs" disables this message.
  [  246.820358] INFO: task pe_cycle_A:154 is blocked on a mutex likely owned by task pe_cycle_B:155.
  [  246.820360] INFO: task pe_cycle_B:155 blocked for more than 122 seconds.
  [  246.820433] INFO: task pe_cycle_B:155 is blocked on a mutex likely owned by task pe_cycle_A:154.
  EXEC_DONE  (VM continued normally throughout)

cycle detection fires immediately (~1ms after deadlock forms), donor is deactivated, hung-task detector fires after 122s as expected.

Will send v2 once this direction is confirmed.

Thanks,
zhidao su

author
#4 lore raw
In reply to K Prateek Nayak

Hello John, Prateek,

Quoted 7 lines · K Prateek Nayak

As an alternate approach, when traversing blocked_on links, can we start deactivating the chain if we encounter rq->donor again as owner in find_proxy_task() loop?

That way we go back to triggering the hung task detector and if someone has a stack that depends on it, it'll continue to work fine while also avoiding this lockup.

Thanks for the suggestion. I've implemented and tested this approach.

On John's point about BUG(): I agree lock cycles are a serious bug, but deactivating the donor preserves mutex_lock_interruptible() recovery paths and avoids a hard system stop for what could be an application-level bug. The WARN_ONCE + hung-task splat provides sufficient visibility.

Changes from v1:
- Replace proxy_resched_idle() with proxy_deactivate() on both the depth-exceeded path and the new cycle-detected path. proxy_resched_idle() returns rq->idle, causing __schedule() to immediately re-select the same donor and re-enter find_proxy_task(), creating a soft loop with no forward progress. (John Stultz)
- Add owner == donor cycle detection immediately after resolving owner from blocked_on. This catches A->B->...->A at the first chain closure; no visited set needed. (K Prateek Nayak)
- Raise MAX_PROXY_CHAIN_DEPTH from 64 to 1024 to match rt-mutex's max_lock_depth. (John Stultz)

Tested with pe_cycle_kmod (two kthreads pinned to CPU 0, each holding one mutex and trying to acquire the other, virtme-ng, CONFIG_LOCKDEP=n):

  [  109.057659] sched/pe: deadlock cycle detected, pid 154
  [  109.057687] WARNING: CPU: 0 PID: 155 at kernel/sched/core.c:7392
                 find_proxy_task+0x.../...
  ...
  [  246.820220] INFO: task pe_cycle_A:154 blocked for more than 122 seconds.
  [  246.820238] "echo 0 > /proc/sys/kernel/hung_task_timeout_secs" disables this message.
  [  246.820358] INFO: task pe_cycle_A:154 is blocked on a mutex likely owned by task pe_cycle_B:155.
  [  246.820360] INFO: task pe_cycle_B:155 blocked for more than 122 seconds.
  [  246.820433] INFO: task pe_cycle_B:155 is blocked on a mutex likely owned by task pe_cycle_A:154.
  EXEC_DONE  (VM continued normally throughout)

cycle detection fires immediately (~1ms after deadlock forms), donor is deactivated, hung-task detector fires after 122s as expected.

Will send v2 once this direction is confirmed.

Thanks,
zhidao su

#5 lore raw

PATCH v2 1/1 sched/proxy_exec: Break cyclic proxy chains by deactivating blocked tasks

In reply to K Prateek Nayak

From: "zhidao su (Xiaomi)" <[email protected]>

find_proxy_task() follows the blocked_on/owner chain for a blocked donor. If the chain forms a cycle, __schedule() can keep walking the same chain while holding rq->lock.

A PE cycle reproducer creates two tasks blocked on each other's mutexes. Without a guard, the guest does not complete within a 90s vng timeout. With this change, loading the reproducer reports:

sched/pe: deadlock cycle detected, pid 128

and a heartbeat kthread pinned to the same CPU continues to run:

pe_cycle_kmod: heartbeat 3 pid 129

Rescheduling idle is not enough here: the same blocked_on relation remains, so the next scheduling pass can select the same donor and re-enter the same cycle.

When the walk reaches the original donor again, clear the current blocked_on relation and deactivate that blocked task. Do the same for excessive chain depth after revalidating blocked_on under p->blocked_lock. This removes the task from the proxy-exec runnable-chain selection path and lets the scheduler make progress.

Use 1024 as the depth limit to match rtmutex's default max_lock_depth.

---

Changes from v1:
- Deactivate the blocked task instead of rescheduling idle.
- Add direct owner == donor cycle detection.
- Raise MAX_PROXY_CHAIN_DEPTH from 64 to 1024.

 kernel/sched/core.c | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)
kernel/sched/core.c +17 -0
index 2e7cde033a319..cff1a3b58660b 100644
@@ -6724,6 +6724,8 @@ static bool try_to_block_task(struct rq *rq, struct task_struct *p,
 }
 
 #ifdef CONFIG_SCHED_PROXY_EXEC
+#define MAX_PROXY_CHAIN_DEPTH	1024
+
 static inline void proxy_set_task_cpu(struct task_struct *p, int cpu)
 {
 	unsigned int wake_cpu;
@@ -6873,6 +6875,7 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 	int this_cpu = cpu_of(rq);
 	struct task_struct *p;
 	int owner_cpu;
+	int chain_depth = 0;
 
 	/* Follow blocked_on chain. */
 	for (p = donor; p->is_blocked; p = owner) {
@@ -6905,6 +6908,13 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			return NULL;
 		}
 
+		if (++chain_depth > MAX_PROXY_CHAIN_DEPTH) {
+			WARN_ONCE(1, "sched/pe: proxy chain depth exceeded %d, pid %d\n",
+				  MAX_PROXY_CHAIN_DEPTH, p->pid);
+			__clear_task_blocked_on(p, NULL);
+			goto deactivate;
+		}
+
 		if (task_current(rq, p))
 			curr_in_chain = true;
 
@@ -6923,6 +6933,13 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			goto deactivate;
 		}
 
+		if (owner == donor) {
+			WARN_ONCE(1, "sched/pe: deadlock cycle detected, pid %d\n",
+				  p->pid);
+			__clear_task_blocked_on(p, NULL);
+			goto deactivate;
+		}
+
 		if (!READ_ONCE(owner->on_rq) || owner->se.sched_delayed) {
 			/* XXX Don't handle blocked owners/delayed dequeue yet */
 			if (curr_in_chain)
Signature · 1 line
2.43.0
#6 lore raw

Re: [PATCH v2] sched/proxy_exec: Break cyclic proxy chains by deactivating blocked tasks

Hello Zhidao,

kernel/sched/core.c static bool try_to_block_task(struct rq *rq, struct task_struct *p, · line 6727

Quoted 9 lines · On 7/14/2026 8:51 PM, [email protected] wrote:
kernel/sched/core.c +1 -0
index 2e7cde033a319..cff1a3b58660b 100644
@@ -6724,6 +6724,8 @@ static bool try_to_block_task(struct rq *rq, struct task_struct *p,
 }
 
 #ifdef CONFIG_SCHED_PROXY_EXEC
+#define MAX_PROXY_CHAIN_DEPTH	1024

I'm not really a fan of the arbitrary MAX_PROXY_CHAIN_DEPTH.

Quoted 27 lines
kernel/sched/core.c +9 -0
+
 static inline void proxy_set_task_cpu(struct task_struct *p, int cpu)
 {
 	unsigned int wake_cpu;
@@ -6873,6 +6875,7 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 	int this_cpu = cpu_of(rq);
 	struct task_struct *p;
 	int owner_cpu;
+	int chain_depth = 0;
 
 	/* Follow blocked_on chain. */
 	for (p = donor; p->is_blocked; p = owner) {
@@ -6905,6 +6908,13 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			return NULL;
 		}
 
+		if (++chain_depth > MAX_PROXY_CHAIN_DEPTH) {
+			WARN_ONCE(1, "sched/pe: proxy chain depth exceeded %d, pid %d\n",
+				  MAX_PROXY_CHAIN_DEPTH, p->pid);
+			__clear_task_blocked_on(p, NULL);
+			goto deactivate;
+		}
+
 		if (task_current(rq, p))
 			curr_in_chain = true;
 

kernel/sched/core.c find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf) · line 6936

Quoted 4 lines
kernel/sched/core.c +1 -0
@@ -6923,6 +6933,13 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			goto deactivate;
 		}
 
+		if (owner == donor) {

So let us take a step back. Say you have a genuine case of:

A -> B -> C -> D

       ^         |
       |         |
       +---------+

donor = A
Cycle is somewhere in-between the chain

Now, we have a "p->blocked_donor" back link that we can probably leverage to detect this cycle except we don't clear a p->blocked_donor link when find_proxy_task() returns idle or NULL so we can have stale p->blocked_donor links for queued tasks but they are so far harmless.

Me goes and thinks ...

Since p->blocked_donor isn't used for chain migration yet, does something like below help your deadlock case?

(Prepared on top of tip:sched/core; Lightly tested)

kernel/sched/core.c +22 -0
index 2e7cde033a31..fa1d9443f744 100644
@@ -6874,6 +6874,9 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 	struct task_struct *p;
 	int owner_cpu;
 
+	/* Increment proxy_pick_seq such that last 4 bits are always set. */
+	rq->proxy_pick_seq += 0x10;
+
 	/* Follow blocked_on chain. */
 	for (p = donor; p->is_blocked; p = owner) {
 		/* if its PROXY_WAKING, do return migration or run if current */
@@ -6990,12 +6993,28 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			 */
 			return proxy_resched_idle(rq);
 		}
+
+		/* Cyclic deadlock detection. */
+		if (((u64)owner->blocked_donor) & 0xF) {
+			u64 pick_seq = (u64)owner->blocked_donor;
+
+			/*
+			 * Owner was already seen during this find_proxy_task() loop.
+			 * Deactivate the task since there is a loop in proxy-chain.
+			 */
+			if (rq->proxy_pick_seq == pick_seq) {
+				__clear_task_blocked_on(p, NULL);
+				goto deactivate;
+			}
+		}
+
 		/*
 		 * OK, now we're absolutely sure @owner is on this
 		 * rq, therefore holding @rq->lock is sufficient to
 		 * guarantee its existence, as per ttwu_remote().
 		 */
 		owner->blocked_donor = p;
+		p->blocked_donor = (void *)rq->proxy_pick_seq;
 	}
 	WARN_ON_ONCE(owner && !owner->on_rq);
 	return owner;
@@ -9057,6 +9076,9 @@ void __init sched_init(void)
 		raw_spin_lock_init(&rq->cpu_epoch_lock);
 		rq->cpu_epoch_next = jiffies;
 #endif
+#ifdef CONFIG_SCHED_PROXY_EXEC
+		rq->proxy_pick_seq = 0xf;
+#endif
 
 		zalloc_cpumask_var_node(&rq->scratch_mask, GFP_KERNEL, cpu_to_node(i));
 	}
kernel/sched/sched.h +1 -0
index 26ae13c86b69..452cbcd3a8c5 100644
@@ -1154,6 +1154,7 @@ struct rq {
 #ifdef CONFIG_SCHED_PROXY_EXEC
 	struct task_struct __rcu	*donor;  /* Scheduling context */
 	struct task_struct __rcu	*curr;   /* Execution context */
+	u64			proxy_pick_seq;  /* find_proxy_task() seq */
 #else
 	union {
 		struct task_struct __rcu *donor; /* Scheduler context */

---
base-commit: 04998aa54848f15332202d0bea008d2ca1ed1713

This assumes task_struct pointers are 4-bytes aligned.

Only rq->curr->blocked_donor matters currently so it should be okay to clobber the rest of the chain. If this is okay, perhaps we can just stash the pick_seq copy in task_struct.

Thoughts?

Quoted 9 lines
kernel/sched/core.c +6 -0
+			WARN_ONCE(1, "sched/pe: deadlock cycle detected, pid %d\n",
+				  p->pid);
+			__clear_task_blocked_on(p, NULL);
+			goto deactivate;
+		}
+
 		if (!READ_ONCE(owner->on_rq) || owner->se.sched_delayed) {
 			/* XXX Don't handle blocked owners/delayed dequeue yet */
 			if (curr_in_chain)
Signature · 2 lines
Thanks and Regards,
Prateek
#7 lore raw

Re: [PATCH v2] sched/proxy_exec: Break cyclic proxy chains by deactivating blocked tasks

In reply to [email protected]

Thanks Prateek.

Quoted 1 line

I'm not really a fan of the arbitrary MAX_PROXY_CHAIN_DEPTH.

Agreed. It was only a guard rail, not a real fix. I'll drop it in v3 and switch to a proper cycle check.

Quoted 1 line

This only catches cycles that come back to the original donor.

Right. The owner == donor check only catches cycles that include the original donor, so it misses loops in the middle of the chain, like your A -> B -> C -> D -> B example.

Quoted 1 line

Maybe we can use the blocked_donor backlink as a visited marker?

The basic idea makes sense, but I'd rather not overload blocked_donor. That field is already the donor-stack backlink, and keeping it as a plain task pointer seems easier to reason about as the proxy-exec model grows to more primitives.

So for v3 I'll likely use an explicit per-pick seq marker instead.

Quoted 1 line

We should probably think about other lock types too.

Yes, agreed. That's another reason to keep this at the proxy wait-for-chain level rather than make it mutex-specific. The current tree still only has mutex-backed blocked_on, but the design is meant to cover other blocking primitives as well.

Thanks for the review. I'll rework v3 accordingly.

#8 lore raw

Re: [PATCH v2] sched/proxy_exec: Break cyclic proxy chains by deactivating blocked tasks

Hello Zhidao,

Quoted 13 lines · On 7/15/2026 8:07 AM, [email protected] wrote:

Thanks Prateek.

Quoted 1 line

I'm not really a fan of the arbitrary MAX_PROXY_CHAIN_DEPTH.

Agreed. It was only a guard rail, not a real fix. I'll drop it in v3 and switch to a proper cycle check.

Quoted 1 line

This only catches cycles that come back to the original donor.

Right. The owner == donor check only catches cycles that include the original donor, so it misses loops in the middle of the chain, like your A -> B -> C -> D -> B example.

Quoted 8 lines
Quoted 1 line

Maybe we can use the blocked_donor backlink as a visited marker?

The basic idea makes sense, but I'd rather not overload blocked_donor. That field is already the donor-stack backlink, and keeping it as a plain task pointer seems easier to reason about as the proxy-exec model grows to more primitives.

So for v3 I'll likely use an explicit per-pick seq marker instead.

Ack! Sample code was just a PoC to see if it is good enough to solve the hard lockup problem :-)

Btw, I realized you'll need to reset this marker on migration, else there is a rare chance of a stale p->blocked_donor pick_seq from an old pick CPU colliding with the pick_seq after migration.

For my PoC, this was a good enough solution:

kernel/sched/sched.h +1 -0
index 452cbcd3a8c5..f5180913c038 100644
@@ -2400,6 +2400,7 @@ static inline void __set_task_cpu(struct task_struct *p, unsigned int cpu)
 	smp_wmb();
 	WRITE_ONCE(task_thread_info(p)->cpu, cpu);
 	p->wake_cpu = cpu;
+	p->blocked_donor = NULL;
 	rseq_sched_set_ids_changed(p);
 #endif /* CONFIG_SMP */
 }

---

You can make this fit as per your v3 scheme.

Quoted 6 lines
Quoted 1 line

We should probably think about other lock types too.

Yes, agreed. That's another reason to keep this at the proxy wait-for-chain level rather than make it mutex-specific. The current tree still only has mutex-backed blocked_on, but the design is meant to cover other blocking primitives as well.

Ack! I think eventually, blocked_on becomes a struct with a lock_type enum + void* pointer which allows for interpreting the pointer based on the lock_type.

I agree p->blocked_donor has other uses with the extended series so it is best to use a separate variable to track the seq_count if we go down that route.

I'll let John comment if it is a good idea or not.

Quoted 2 lines

Thanks for the review. I'll rework v3 accordingly.

Thanks a ton.

Signature · 2 lines
Thanks and Regards,
Prateek
#9 lore raw

Re: [PATCH v2] sched/proxy_exec: Break cyclic proxy chains by deactivating blocked tasks

Quoted 3 lines

Btw, I realized you'll need to reset this marker on migration, else there is a rare chance of a stale p->blocked_donor pick_seq from an old pick CPU colliding with the pick_seq after migration.

Good catch. I think v3 should clear the marker when we migrate the task, so the pick state is only meaningful for a single walk on a single CPU. That avoids stale state from an old CPU colliding with a later walk.

Quoted 1 line

You can make this fit as per your v3 scheme.

I’m leaning toward keeping this proxy-local instead of putting it in a generic CPU switch helper.

Quoted 3 lines

Ack! I think eventually, blocked_on becomes a struct with a lock_type enum + void* pointer which allows for interpreting the pointer based on the lock_type.

Makes sense, and that’s another reason I’d keep the walk marker separate from the blocked_on / blocked_donor representation itself.

Quoted 3 lines

I agree p->blocked_donor has other uses with the extended series so it is best to use a separate variable to track the seq_count if we go down that route.

Right, that was my thinking as well.

#10 lore raw

PATCH v3 1/1 sched/proxy_exec: Detect cycles in proxy walks

In reply to [email protected]

find_proxy_task() can keep walking the same blocked_on chain if the chain contains a cycle. This happens with a simple A->B->A mutex deadlock under proxy execution, and can leave the CPU spinning in __schedule() with the rq lock held.

Mark each task visited during one proxy walk with the rq's pick sequence. If the walk sees the same task again in the same pick, break the cycle by clearing the blocked_on state at the detection point and deactivating that task.

Clear the marker when proxy execution migrates a blocked task, so a later walk on another CPU cannot match stale state.

Tested with a PE cycle reproducer in virtme-ng:

buggy kernel: vng timed out without returning fixed kernel: WARN_ONCE "sched/pe: deadlock cycle detected"

---
Changes since v2:
- Drop the proxy-chain depth limit.
- Detect cycles anywhere in the proxy walk, not only cycles back to the original donor.
- Use a separate per-pick marker instead of overloading blocked_donor.
- Clear the marker on proxy-exec blocked-task migration.

 include/linux/sched.h |  4 ++++
 kernel/fork.c         |  4 ++++
 kernel/sched/core.c   | 34 ++++++++++++++++++++++++++++++++--
 kernel/sched/sched.h  |  1 +
 4 files changed, 41 insertions(+), 2 deletions(-)
include/linux/sched.h +4 -0
index 968b18a7f4702..b83a4e775d736 100644
@@ -1256,6 +1256,10 @@ struct task_struct {
 	 * under preempt_disable().
 	 */
 	struct task_struct		*blocked_donor;
+#ifdef CONFIG_SCHED_PROXY_EXEC
+	int				proxy_pick_cpu;
+	u64				proxy_pick_seq; /* find_proxy_task() seq */
+#endif
 
 #ifdef CONFIG_DETECT_HUNG_TASK_BLOCKER
 	/*
kernel/fork.c +4 -0
index 13e38e89a1f30..2219cce602c62 100644
@@ -2242,6 +2242,10 @@ __latent_entropy struct task_struct *copy_process(
 
 	p->blocked_on = NULL; /* not blocked yet */
 	p->blocked_donor = NULL; /* nobody is boosting p yet */
+#ifdef CONFIG_SCHED_PROXY_EXEC
+	p->proxy_pick_cpu = -1;
+	p->proxy_pick_seq = 0;
+#endif
 
 #ifdef CONFIG_BCACHE
 	p->sequential_io	= 0;
kernel/sched/core.c +32 -2
index 2e7cde033a319..3db4e6c2b786a 100644
@@ -6724,6 +6724,7 @@ static bool try_to_block_task(struct rq *rq, struct task_struct *p,
 }
 
 #ifdef CONFIG_SCHED_PROXY_EXEC
+
 static inline void proxy_set_task_cpu(struct task_struct *p, int cpu)
 {
 	unsigned int wake_cpu;
@@ -6830,6 +6831,10 @@ static void proxy_migrate_task(struct rq *rq, struct rq_flags *rf,
 
 	deactivate_task(rq, p, DEQUEUE_NOCLOCK);
 	proxy_set_task_cpu(p, target_cpu);
+#ifdef CONFIG_SCHED_PROXY_EXEC
+	WRITE_ONCE(p->proxy_pick_cpu, -1);
+	WRITE_ONCE(p->proxy_pick_seq, 0);
+#endif
 
 	proxy_release_rq_lock(rq, rf);
 
@@ -6839,14 +6844,14 @@ static void proxy_migrate_task(struct rq *rq, struct rq_flags *rf,
 }
 
 /*
- * Find runnable lock owner to proxy for mutex blocked donor
+ * Find runnable lock owner to proxy for a blocked donor
  *
  * Follow the blocked-on relation:
  *
  *                ,-> task
  *                |     | blocked-on
  *                |     v
- *  blocked_donor |   mutex
+ *  blocked_donor | blocking primitive
  *                |     | owner
  *                |     v
  *                `-- task
@@ -6874,6 +6879,10 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 	struct task_struct *p;
 	int owner_cpu;
 
+	rq->proxy_pick_seq++;
+	if (unlikely(!rq->proxy_pick_seq))
+		rq->proxy_pick_seq++;
+
 	/* Follow blocked_on chain. */
 	for (p = donor; p->is_blocked; p = owner) {
 		/* if its PROXY_WAKING, do return migration or run if current */
@@ -6905,6 +6914,16 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			return NULL;
 		}
 
+		if (READ_ONCE(p->proxy_pick_cpu) == this_cpu &&
+		    READ_ONCE(p->proxy_pick_seq) == rq->proxy_pick_seq) {
+			WARN_ONCE(1, "sched/pe: deadlock cycle detected, pid %d\n",
+				  p->pid);
+			__clear_task_blocked_on(p, NULL);
+			goto deactivate;
+		}
+		WRITE_ONCE(p->proxy_pick_cpu, this_cpu);
+		WRITE_ONCE(p->proxy_pick_seq, rq->proxy_pick_seq);
+
 		if (task_current(rq, p))
 			curr_in_chain = true;
 
@@ -6990,6 +7009,14 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			 */
 			return proxy_resched_idle(rq);
 		}
+
+		if (READ_ONCE(owner->proxy_pick_cpu) == this_cpu &&
+		    READ_ONCE(owner->proxy_pick_seq) == rq->proxy_pick_seq) {
+			WARN_ONCE(1, "sched/pe: deadlock cycle detected, pid %d\n",
+				  p->pid);
+			__clear_task_blocked_on(p, NULL);
+			goto deactivate;
+		}
 		/*
 		 * OK, now we're absolutely sure @owner is on this
 		 * rq, therefore holding @rq->lock is sufficient to
@@ -9057,6 +9084,9 @@ void __init sched_init(void)
 		raw_spin_lock_init(&rq->cpu_epoch_lock);
 		rq->cpu_epoch_next = jiffies;
 #endif
+#ifdef CONFIG_SCHED_PROXY_EXEC
+		rq->proxy_pick_seq = 0;
+#endif
 
 		zalloc_cpumask_var_node(&rq->scratch_mask, GFP_KERNEL, cpu_to_node(i));
 	}
kernel/sched/sched.h +1 -0
index 26ae13c86b699..f63c024d160e8 100644
@@ -1154,6 +1154,7 @@ struct rq {
 #ifdef CONFIG_SCHED_PROXY_EXEC
 	struct task_struct __rcu	*donor;  /* Scheduling context */
 	struct task_struct __rcu	*curr;   /* Execution context */
+	u64				proxy_pick_seq;  /* find_proxy_task() seq */
 #else
 	union {
 		struct task_struct __rcu *donor; /* Scheduler context */

base-commit: 04998aa54848f15332202d0bea008d2ca1ed1713

Signature · 1 line
2.43.0
#11 lore raw

Re: [PATCH v3] sched/proxy_exec: Detect cycles in proxy walks

Hello Zhidao,

Quoted 38 lines · zhidao su (Xiaomi)

find_proxy_task() can keep walking the same blocked_on chain if the chain contains a cycle. This happens with a simple A->B->A mutex deadlock under proxy execution, and can leave the CPU spinning in __schedule() with the rq lock held.

Mark each task visited during one proxy walk with the rq's pick sequence. If the walk sees the same task again in the same pick, break the cycle by clearing the blocked_on state at the detection point and deactivating that task.

Clear the marker when proxy execution migrates a blocked task, so a later walk on another CPU cannot match stale state.

Tested with a PE cycle reproducer in virtme-ng:

buggy kernel: vng timed out without returning fixed kernel: WARN_ONCE "sched/pe: deadlock cycle detected"

---
Changes since v2:
- Drop the proxy-chain depth limit.
- Detect cycles anywhere in the proxy walk, not only cycles back to the original donor.
- Use a separate per-pick marker instead of overloading blocked_donor.
- Clear the marker on proxy-exec blocked-task migration.

 include/linux/sched.h |  4 ++++
 kernel/fork.c         |  4 ++++
 kernel/sched/core.c   | 34 ++++++++++++++++++++++++++++++++--
 kernel/sched/sched.h  |  1 +
 4 files changed, 41 insertions(+), 2 deletions(-)
include/linux/sched.h +0 -0
index 968b18a7f4702..b83a4e775d736 100644

include/linux/sched.h struct task_struct { · line 1260

Quoted 5 lines
include/linux/sched.h +2 -0
@@ -1256,6 +1256,10 @@ struct task_struct {
 	 * under preempt_disable().
 	 */
 	struct task_struct		*blocked_donor;
+#ifdef CONFIG_SCHED_PROXY_EXEC
+	int				proxy_pick_cpu;

This adds 8-bytes to task_struct for not much benefit.

I think resetting proxy_pick_seq on migration / enqueue is much simpler than tracking 2 things. Not to mention you need to write to "proxy_pick_cpu" at every iteration and compare it too.

Quoted 10 lines
include/linux/sched.h +2 -0
+	u64				proxy_pick_seq; /* find_proxy_task() seq */
+#endif
 
 #ifdef CONFIG_DETECT_HUNG_TASK_BLOCKER
 	/*
kernel/fork.c +0 -0
index 13e38e89a1f30..2219cce602c62 100644

kernel/fork.c __latent_entropy struct task_struct *copy_process( · line 2247

Quoted 6 lines
kernel/fork.c +3 -0
@@ -2242,6 +2242,10 @@ __latent_entropy struct task_struct *copy_process(
 
 	p->blocked_on = NULL; /* not blocked yet */
 	p->blocked_donor = NULL; /* nobody is boosting p yet */
+#ifdef CONFIG_SCHED_PROXY_EXEC
+	p->proxy_pick_cpu = -1;
+	p->proxy_pick_seq = 0;

It should be okay to inherit these values from parent. The task still needs to be placed after the fork which grabs the rq_lock and next pick would increment the seq number anyways.

Quoted 45 lines
kernel/fork.c +1 -0
+#endif
 
 #ifdef CONFIG_BCACHE
 	p->sequential_io	= 0;
kernel/sched/core.c +7 -2
index 2e7cde033a319..3db4e6c2b786a 100644
@@ -6724,6 +6724,7 @@ static bool try_to_block_task(struct rq *rq, struct task_struct *p,
 }
 
 #ifdef CONFIG_SCHED_PROXY_EXEC
+
 static inline void proxy_set_task_cpu(struct task_struct *p, int cpu)
 {
 	unsigned int wake_cpu;
@@ -6830,6 +6831,10 @@ static void proxy_migrate_task(struct rq *rq, struct rq_flags *rf,
 
 	deactivate_task(rq, p, DEQUEUE_NOCLOCK);
 	proxy_set_task_cpu(p, target_cpu);
+#ifdef CONFIG_SCHED_PROXY_EXEC
+	WRITE_ONCE(p->proxy_pick_cpu, -1);
+	WRITE_ONCE(p->proxy_pick_seq, 0);
+#endif
 
 	proxy_release_rq_lock(rq, rf);
 
@@ -6839,14 +6844,14 @@ static void proxy_migrate_task(struct rq *rq, struct rq_flags *rf,
 }
 
 /*
- * Find runnable lock owner to proxy for mutex blocked donor
+ * Find runnable lock owner to proxy for a blocked donor
  *
  * Follow the blocked-on relation:
  *
  *                ,-> task
  *                |     | blocked-on
  *                |     v
- *  blocked_donor |   mutex
+ *  blocked_donor | blocking primitive
  *                |     | owner
  *                |     v
  *                `-- task

kernel/sched/core.c find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf) · line 6884

Quoted 6 lines
kernel/sched/core.c +3 -0
@@ -6874,6 +6879,10 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 	struct task_struct *p;
 	int owner_cpu;
 
+	rq->proxy_pick_seq++;
+	if (unlikely(!rq->proxy_pick_seq))
+		rq->proxy_pick_seq++;

Can't we simply initialize "rq->proxy_pick_seq" to 1 in sched_init()? I don't think we need to worry about a u64 wraparound.

Quoted 8 lines
kernel/sched/core.c +1 -0
+
 	/* Follow blocked_on chain. */
 	for (p = donor; p->is_blocked; p = owner) {
 		/* if its PROXY_WAKING, do return migration or run if current */
@@ -6905,6 +6914,16 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			return NULL;
 		}
 

kernel/sched/core.c find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf) · line 6926

Quoted 10 lines
kernel/sched/core.c +10 -0
+		if (READ_ONCE(p->proxy_pick_cpu) == this_cpu &&
+		    READ_ONCE(p->proxy_pick_seq) == rq->proxy_pick_seq) {
+			WARN_ONCE(1, "sched/pe: deadlock cycle detected, pid %d\n",
+				  p->pid);
+			__clear_task_blocked_on(p, NULL);
+			goto deactivate;
+		}
+		WRITE_ONCE(p->proxy_pick_cpu, this_cpu);
+		WRITE_ONCE(p->proxy_pick_seq, rq->proxy_pick_seq);
+

Why do we need READ_ONCE() / WRITE_ONCE()?

All the checks happen on the same CPU under rq_lock. There is no chance of a concurrent update here. Any time we drop the lock, we do a re-pick and that should be sufficient to prevent any collision.

Quoted 42 lines
kernel/sched/core.c +11 -0
 		if (task_current(rq, p))
 			curr_in_chain = true;
 
@@ -6990,6 +7009,14 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			 */
 			return proxy_resched_idle(rq);
 		}
+
+		if (READ_ONCE(owner->proxy_pick_cpu) == this_cpu &&
+		    READ_ONCE(owner->proxy_pick_seq) == rq->proxy_pick_seq) {
+			WARN_ONCE(1, "sched/pe: deadlock cycle detected, pid %d\n",
+				  p->pid);
+			__clear_task_blocked_on(p, NULL);
+			goto deactivate;
+		}
 		/*
 		 * OK, now we're absolutely sure @owner is on this
 		 * rq, therefore holding @rq->lock is sufficient to
@@ -9057,6 +9084,9 @@ void __init sched_init(void)
 		raw_spin_lock_init(&rq->cpu_epoch_lock);
 		rq->cpu_epoch_next = jiffies;
 #endif
+#ifdef CONFIG_SCHED_PROXY_EXEC
+		rq->proxy_pick_seq = 0;
+#endif
 
 		zalloc_cpumask_var_node(&rq->scratch_mask, GFP_KERNEL, cpu_to_node(i));
 	}
kernel/sched/sched.h +1 -0
index 26ae13c86b699..f63c024d160e8 100644
@@ -1154,6 +1154,7 @@ struct rq {
 #ifdef CONFIG_SCHED_PROXY_EXEC
 	struct task_struct __rcu	*donor;  /* Scheduling context */
 	struct task_struct __rcu	*curr;   /* Execution context */
+	u64				proxy_pick_seq;  /* find_proxy_task() seq */
 #else
 	union {
 		struct task_struct __rcu *donor; /* Scheduler context */

base-commit: 04998aa54848f15332202d0bea008d2ca1ed1713

Signature · 2 lines
Thanks and Regards,
Prateek
#12 lore raw

PATCH v4 1/1 sched/proxy_exec: Detect cycles in proxy walks

find_proxy_task() can keep walking the same blocked_on chain if the chain contains a cycle. This happens with a simple A->B->A mutex deadlock under proxy execution, and can leave the CPU spinning in __schedule() with the rq lock held.

Use the rq pick sequence as a per-walk marker. Mark each task visited by the current proxy walk. If the walk sees the same marker again, break the cycle by clearing the blocked_on state at the detection point and deactivating that task.

The marker is only consumed while holding the rq lock. Clear it when a task is activated, so stale state from an earlier pick or another rq is not carried into the next queued lifetime.

Tested with a PE cycle reproducer in virtme-ng:

buggy kernel: vng timed out without returning fixed kernel: WARN_ONCE "sched/pe: deadlock cycle detected"

---
Changes since v3:
- Use a single per-task proxy_pick_seq marker instead of storing both CPU and sequence.
- Clear stale proxy-walk state from activate_task() rather than from the proxy migration path only.
- Drop fork-time marker initialization.
- Drop READ_ONCE()/WRITE_ONCE() around marker accesses; the walk is under rq lock.
- Drop the u64 wraparound guard.

 include/linux/sched.h |  3 +++
 kernel/sched/core.c   | 28 ++++++++++++++++++++++++++--
 kernel/sched/sched.h  |  1 +
 3 files changed, 30 insertions(+), 2 deletions(-)
include/linux/sched.h +3 -0
index 968b18a7f4702..b1c46e21bc268 100644
@@ -1256,6 +1256,9 @@ struct task_struct {
 	 * under preempt_disable().
 	 */
 	struct task_struct		*blocked_donor;
+#ifdef CONFIG_SCHED_PROXY_EXEC
+	u64				proxy_pick_seq;
+#endif
 
 #ifdef CONFIG_DETECT_HUNG_TASK_BLOCKER
 	/*
kernel/sched/core.c +26 -2
index 2e7cde033a319..1a9d3decd66e0 100644
@@ -2221,6 +2221,9 @@ void activate_task(struct rq *rq, struct task_struct *p, int flags)
 	if (task_on_rq_migrating(p))
 		flags |= ENQUEUE_MIGRATED;
 
+#ifdef CONFIG_SCHED_PROXY_EXEC
+	p->proxy_pick_seq = 0;
+#endif
 	enqueue_task(rq, p, flags);
 
 	WRITE_ONCE(p->on_rq, TASK_ON_RQ_QUEUED);
@@ -6724,6 +6727,7 @@ static bool try_to_block_task(struct rq *rq, struct task_struct *p,
 }
 
 #ifdef CONFIG_SCHED_PROXY_EXEC
+
 static inline void proxy_set_task_cpu(struct task_struct *p, int cpu)
 {
 	unsigned int wake_cpu;
@@ -6839,14 +6843,14 @@ static void proxy_migrate_task(struct rq *rq, struct rq_flags *rf,
 }
 
 /*
- * Find runnable lock owner to proxy for mutex blocked donor
+ * Find runnable lock owner to proxy for a blocked donor
  *
  * Follow the blocked-on relation:
  *
  *                ,-> task
  *                |     | blocked-on
  *                |     v
- *  blocked_donor |   mutex
+ *  blocked_donor | blocking primitive
  *                |     | owner
  *                |     v
  *                `-- task
@@ -6874,6 +6878,8 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 	struct task_struct *p;
 	int owner_cpu;
 
+	rq->proxy_pick_seq++;
+
 	/* Follow blocked_on chain. */
 	for (p = donor; p->is_blocked; p = owner) {
 		/* if its PROXY_WAKING, do return migration or run if current */
@@ -6905,6 +6911,14 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			return NULL;
 		}
 
+		if (p->proxy_pick_seq == rq->proxy_pick_seq) {
+			WARN_ONCE(1, "sched/pe: deadlock cycle detected, pid %d\n",
+				  p->pid);
+			__clear_task_blocked_on(p, NULL);
+			goto deactivate;
+		}
+		p->proxy_pick_seq = rq->proxy_pick_seq;
+
 		if (task_current(rq, p))
 			curr_in_chain = true;
 
@@ -6990,6 +7004,13 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			 */
 			return proxy_resched_idle(rq);
 		}
+
+		if (owner->proxy_pick_seq == rq->proxy_pick_seq) {
+			WARN_ONCE(1, "sched/pe: deadlock cycle detected, pid %d\n",
+				  p->pid);
+			__clear_task_blocked_on(p, NULL);
+			goto deactivate;
+		}
 		/*
 		 * OK, now we're absolutely sure @owner is on this
 		 * rq, therefore holding @rq->lock is sufficient to
@@ -9057,6 +9078,9 @@ void __init sched_init(void)
 		raw_spin_lock_init(&rq->cpu_epoch_lock);
 		rq->cpu_epoch_next = jiffies;
 #endif
+#ifdef CONFIG_SCHED_PROXY_EXEC
+		rq->proxy_pick_seq = 1;
+#endif
 
 		zalloc_cpumask_var_node(&rq->scratch_mask, GFP_KERNEL, cpu_to_node(i));
 	}
kernel/sched/sched.h +1 -0
index 26ae13c86b699..26d8d2788e0cd 100644
@@ -1154,6 +1154,7 @@ struct rq {
 #ifdef CONFIG_SCHED_PROXY_EXEC
 	struct task_struct __rcu	*donor;  /* Scheduling context */
 	struct task_struct __rcu	*curr;   /* Execution context */
+	u64				proxy_pick_seq;
 #else
 	union {
 		struct task_struct __rcu *donor; /* Scheduler context */

base-commit: 04998aa54848f15332202d0bea008d2ca1ed1713

Signature · 1 line
2.43.0
reviewer Reviewed-by on v4 1/1
#13 lore raw

Re: [PATCH v4] sched/proxy_exec: Detect cycles in proxy walks

Hello Zhidao,

kernel/sched/core.c void activate_task(struct rq *rq, struct task_struct *p, int flags) · line 2226

Quoted 11 lines · zhidao su (Xiaomi)
kernel/sched/core.c +3 -0
index 2e7cde033a319..1a9d3decd66e0 100644
@@ -2221,6 +2221,9 @@ void activate_task(struct rq *rq, struct task_struct *p, int flags)
 	if (task_on_rq_migrating(p))
 		flags |= ENQUEUE_MIGRATED;
 
+#ifdef CONFIG_SCHED_PROXY_EXEC
+	p->proxy_pick_seq = 0;
+#endif

nit.

I think it would be better if we have a sched_proxy_enqueue_task() wrapper around this to avoid sprinkling #ifdef in otherwise what is a clean function.

Also you can bail out early for !sched_proxy_exec() to avoid this write for users who disable proxy execution at runtime.

Quoted 38 lines
kernel/sched/core.c +5 -2
 	enqueue_task(rq, p, flags);
 
 	WRITE_ONCE(p->on_rq, TASK_ON_RQ_QUEUED);
@@ -6724,6 +6727,7 @@ static bool try_to_block_task(struct rq *rq, struct task_struct *p,
 }
 
 #ifdef CONFIG_SCHED_PROXY_EXEC
+
 static inline void proxy_set_task_cpu(struct task_struct *p, int cpu)
 {
 	unsigned int wake_cpu;
@@ -6839,14 +6843,14 @@ static void proxy_migrate_task(struct rq *rq, struct rq_flags *rf,
 }
 
 /*
- * Find runnable lock owner to proxy for mutex blocked donor
+ * Find runnable lock owner to proxy for a blocked donor
  *
  * Follow the blocked-on relation:
  *
  *                ,-> task
  *                |     | blocked-on
  *                |     v
- *  blocked_donor |   mutex
+ *  blocked_donor | blocking primitive
  *                |     | owner
  *                |     v
  *                `-- task
@@ -6874,6 +6878,8 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 	struct task_struct *p;
 	int owner_cpu;
 
+	rq->proxy_pick_seq++;
+
 	/* Follow blocked_on chain. */
 	for (p = donor; p->is_blocked; p = owner) {
 		/* if its PROXY_WAKING, do return migration or run if current */

kernel/sched/core.c find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf) · line 6915

Quoted 5 lines
kernel/sched/core.c +2 -0
@@ -6905,6 +6911,14 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			return NULL;
 		}
 
+		if (p->proxy_pick_seq == rq->proxy_pick_seq) {
+			WARN_ONCE(1, "sched/pe: deadlock cycle detected, pid %d\n",

You can use pr_warn_once().

kernel/sched/core.c find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf) · line 6921

Quoted 6 lines
kernel/sched/core.c +6 -0
+				  p->pid);
+			__clear_task_blocked_on(p, NULL);
+			goto deactivate;
+		}
+		p->proxy_pick_seq = rq->proxy_pick_seq;
+

Do we need to do this here too? ...

Quoted 4 lines
kernel/sched/core.c +0 -0
 		if (task_current(rq, p))
 			curr_in_chain = true;
 

kernel/sched/core.c find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf) · line 7013

Quoted 10 lines
kernel/sched/core.c +7 -0
@@ -6990,6 +7004,13 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			 */
 			return proxy_resched_idle(rq);
 		}
+
+		if (owner->proxy_pick_seq == rq->proxy_pick_seq) {
+			WARN_ONCE(1, "sched/pe: deadlock cycle detected, pid %d\n",
+				  p->pid);
+			__clear_task_blocked_on(p, NULL);
+			goto deactivate;
+		}

... This should be sufficient right? You can just set

   owner->proxy_pick_seq = rq->proxy_pick_seq;

below once owner is finalized instead of setting "p->proxy_pick_seq" very early above.

kernel/sched/core.c find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf) · line 7016

Quoted 3 lines
kernel/sched/core.c +0 -0
 		/*
 		 * OK, now we're absolutely sure @owner is on this
 		 * rq, therefore holding @rq->lock is sufficient to

Apart from those, the patch looks good. With the comments addressed, feel free to include:

Signature · 2 lines
Thanks and Regards,
Prateek
#14 lore raw

PATCH v5 1/1 sched/proxy_exec: Detect cycles in proxy walks

find_proxy_task() can keep walking the same blocked_on chain if the chain contains a cycle. A simple A->B->A deadlock can leave the CPU spinning in __schedule() with rq->lock held.

Use the rq pick sequence as a per-walk marker. Mark each task visited by the current walk. If the walk sees the same marker again, break the cycle by clearing blocked_on at the detection point and deactivating that task.

The marker is only consumed while holding rq->lock. Clear it when a task is activated, so stale state from an earlier pick or another rq is not carried into the next queued lifetime.

Tested with a PE cycle reproducer in virtme-ng:

buggy kernel: vng timed out without returning fixed kernel: WARN_ONCE "sched/pe: deadlock cycle detected"

---
Changes since v4:
- Use sched_proxy_enqueue_task() to clear stale proxy-walk state when a task is activated.
- Stop marking the donor early; only mark the finalized owner.
- Use pr_warn_once() for the cycle warning.

 include/linux/sched.h |  3 +++
 kernel/sched/core.c   | 19 +++++++++++++++++--
 kernel/sched/sched.h  | 11 +++++++++++
 3 files changed, 31 insertions(+), 2 deletions(-)
include/linux/sched.h +3 -0
index 968b18a7f4702..b1c46e21bc268 100644
@@ -1256,6 +1256,9 @@ struct task_struct {
 	 * under preempt_disable().
 	 */
 	struct task_struct		*blocked_donor;
+#ifdef CONFIG_SCHED_PROXY_EXEC
+	u64				proxy_pick_seq;
+#endif
 
 #ifdef CONFIG_DETECT_HUNG_TASK_BLOCKER
 	/*
kernel/sched/core.c +17 -2
index 2e7cde033a319..c1bb4f98dd64a 100644
@@ -2221,6 +2221,7 @@ void activate_task(struct rq *rq, struct task_struct *p, int flags)
 	if (task_on_rq_migrating(p))
 		flags |= ENQUEUE_MIGRATED;
 
+	sched_proxy_enqueue_task(p);
 	enqueue_task(rq, p, flags);
 
 	WRITE_ONCE(p->on_rq, TASK_ON_RQ_QUEUED);
@@ -6724,6 +6725,7 @@ static bool try_to_block_task(struct rq *rq, struct task_struct *p,
 }
 
 #ifdef CONFIG_SCHED_PROXY_EXEC
+
 static inline void proxy_set_task_cpu(struct task_struct *p, int cpu)
 {
 	unsigned int wake_cpu;
@@ -6839,14 +6841,14 @@ static void proxy_migrate_task(struct rq *rq, struct rq_flags *rf,
 }
 
 /*
- * Find runnable lock owner to proxy for mutex blocked donor
+ * Find runnable lock owner to proxy for a blocked donor
  *
  * Follow the blocked-on relation:
  *
  *                ,-> task
  *                |     | blocked-on
  *                |     v
- *  blocked_donor |   mutex
+ *  blocked_donor | blocking primitive
  *                |     | owner
  *                |     v
  *                `-- task
@@ -6874,6 +6876,8 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 	struct task_struct *p;
 	int owner_cpu;
 
+	rq->proxy_pick_seq++;
+
 	/* Follow blocked_on chain. */
 	for (p = donor; p->is_blocked; p = owner) {
 		/* if its PROXY_WAKING, do return migration or run if current */
@@ -6990,6 +6994,14 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			 */
 			return proxy_resched_idle(rq);
 		}
+
+		if (owner->proxy_pick_seq == rq->proxy_pick_seq) {
+			pr_warn_once("sched/pe: deadlock cycle detected, pid %d\n",
+				     p->pid);
+			__clear_task_blocked_on(p, NULL);
+			goto deactivate;
+		}
+		owner->proxy_pick_seq = rq->proxy_pick_seq;
 		/*
 		 * OK, now we're absolutely sure @owner is on this
 		 * rq, therefore holding @rq->lock is sufficient to
@@ -9057,6 +9069,9 @@ void __init sched_init(void)
 		raw_spin_lock_init(&rq->cpu_epoch_lock);
 		rq->cpu_epoch_next = jiffies;
 #endif
+#ifdef CONFIG_SCHED_PROXY_EXEC
+		rq->proxy_pick_seq = 1;
+#endif
 
 		zalloc_cpumask_var_node(&rq->scratch_mask, GFP_KERNEL, cpu_to_node(i));
 	}
kernel/sched/sched.h +11 -0
index 26ae13c86b699..d5d9de509dfdb 100644
@@ -1154,6 +1154,7 @@ struct rq {
 #ifdef CONFIG_SCHED_PROXY_EXEC
 	struct task_struct __rcu	*donor;  /* Scheduling context */
 	struct task_struct __rcu	*curr;   /* Execution context */
+	u64				proxy_pick_seq;
 #else
 	union {
 		struct task_struct __rcu *donor; /* Scheduler context */
@@ -3092,6 +3093,16 @@ static inline void __block_task(struct rq *rq, struct task_struct *p)
 extern void activate_task(struct rq *rq, struct task_struct *p, int flags);
 extern void deactivate_task(struct rq *rq, struct task_struct *p, int flags);
 
+static inline void sched_proxy_enqueue_task(struct task_struct *p)
+{
+#ifdef CONFIG_SCHED_PROXY_EXEC
+	if (!sched_proxy_exec())
+		return;
+
+	p->proxy_pick_seq = 0;
+#endif
+}
+
 extern void wakeup_preempt(struct rq *rq, struct task_struct *p, int flags);
 
 /*

base-commit: 04998aa54848f15332202d0bea008d2ca1ed1713

Signature · 1 line
2.43.0
#15 lore raw

Re: [PATCH v5] sched/proxy_exec: Detect cycles in proxy walks

Quoted 13 lines · zhidao su (Xiaomi)

find_proxy_task() can keep walking the same blocked_on chain if the chain contains a cycle. A simple A->B->A deadlock can leave the CPU spinning in __schedule() with rq->lock held.

Use the rq pick sequence as a per-walk marker. Mark each task visited by the current walk. If the walk sees the same marker again, break the cycle by clearing blocked_on at the detection point and deactivating that task.

The marker is only consumed while holding rq->lock. Clear it when a task is activated, so stale state from an earlier pick or another rq is not carried into the next queued lifetime.

Quoted 7 lines

Tested with a PE cycle reproducer in virtme-ng:

buggy kernel: vng timed out without returning fixed kernel: WARN_ONCE "sched/pe: deadlock cycle detected"

Hey! Zhidao,
Sorry for not having responded on this for awhile. In part its
because I'm still maybe partial to the simplicity of the MAX_PROXY_CHAIN_DEPTH appraoch (no structure additions to task or rq needed!).

But I also trust K Prateek's taste more then my own, so I've sort of backed off to see what takes shape here.

I've not seen the cycle detection as super urgent, as mutex lock cycles are not currently allowable in-kernel, and while the behavior in this problematic case does shift with proxy (system hang vs task stalls), it didn't seem like this was an actual problem except for
problematic out of tree drivers. That said, now that Suleiman has a
first draft for proxy-enabled futexes, this definitely raises the urgency, as userland would be controlling the locking, so cycle detection would be critical.

So I'm definitely eager to see this move forward. Though I still think a simple (++count > MAX_PROXY_CHAIN_DEPTH) check would be simpler and just as effective.

One small thought below..

kernel/sched/core.c find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf) · line 7003

Quoted 11 lines
kernel/sched/core.c +7 -0
@@ -6990,6 +6994,14 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
                         */
                        return proxy_resched_idle(rq);
                }
+
+               if (owner->proxy_pick_seq == rq->proxy_pick_seq) {
+                       pr_warn_once("sched/pe: deadlock cycle detected, pid %d\n",
+                                    p->pid);
+                       __clear_task_blocked_on(p, NULL);
+                       goto deactivate;
+               }

So, the only thought I have here is that the deactivate here will deactivate p, not the donor. This will cause the next cycle to follow the same chain path, until it hits the deactivated task and then it will call proxy_enqueue_on_owner() and pick_again. The downside is since you're always acting effectively on a leaf (sort of an inacturate term in the loop case), you have to basically deactivate/enqueue_on_owner the whole chain before we migth pick something runnable.

If instead the donor was first to be deactivated (working root to leaf), the next pick_again cycle could potentially pick a task out of the chain and run it.

This is maybe a little moot, since once you detect and deactivate a task *in-the-loop*, the proxy_enqueue_on_owner() code will have to work leaf->root. But if the loop is at the end of a chain it might help allow non-chain tasks to be picked a little faster.

Bit of a tangent, but this does make me wonder if we should eventually try to do the proxy_enqueue_on_owner() back down the entire chain following the blocked_donor (similar to what we do for proxy_migrate_task) to try to reduce the amount of pick_again work we do.

thanks
-john

#16 lore raw

Re: [PATCH v5] sched/proxy_exec: Detect cycles in proxy walks

Hey John,

Thanks for the reply, and agreed that the proxy futex work makes this urgent rather than a theoretical edge case.

I tested the "deactivate the donor" idea on v31 (7.2-rc4, with the sleeping_owner / blocked_on_lock rework), using a kernel-mutex reproducer with a tail+cycle: D -> A -> B -> C -> A, where D waits on A but is not in the cycle.

  deactivate p (v5):      1 detection, stable
  deactivate owner:       1 detection, stable
  deactivate donor:       unstable - 4 runs gave 1 / hang / 1 / 2

When the picked donor is D (outside the cycle), deactivating it leaves the A->B->C->A cycle intact, so the next pick_again re-walks it and can hang again. At detection time p and owner are always cycle members (the check only fires once owner is already marked); the donor is only guaranteed to be blocked.

So I'd rather keep deactivating the detection point, or switch to owner if that reads better, but not the donor.

You're right that after one node is deactivated, the remaining blocked tasks still get enqueued one at a time (N-1 for an N-node cycle). If futex makes long cycles common, doing the whole blocked_donor chain in one pass like proxy_migrate_task() would be the real win - I can prototype that as a follow-up.

-zhidao

#17 lore raw

Re: [PATCH v5] sched/proxy_exec: Detect cycles in proxy walks

In reply to zhidao su (Xiaomi)
Quoted 7 lines

Use the rq pick sequence as a per-walk marker. Mark each task visited by the current walk. If the walk sees the same marker again, break the cycle by clearing blocked_on at the detection point and deactivating that task.

The marker is only consumed while holding rq->lock. Clear it when a task is activated, so stale state from an earlier pick or another rq is not carried into the next queued lifetime.

I have been experimenting with a different trade-off for the same cycle detection problem. I sent it as a separate RFC so it can be reviewed independently from the sequence-marker approach:

https://lore.kernel.org/lkml/[email protected]/

The Online Brent version keeps the cycle-detection state local to the real owner walk. It does not add state to task_struct or struct rq, and it does not require activation-time marker reset. The cycle detector reuses the owner resolution performed by the real walk instead of adding a separate preflight traversal.

The trade-off is that Brent may detect a cycle only after the walk has temporarily closed the blocked_donor cycle. In the tested natural recovery path, the selected cycle member reached mutex_unlock() with blocked_donor already cleared. A validation-only forced-stale test also confirmed that the existing blocked_on revalidation rejects a stale handoff. I do not claim that these tests cover every possible scheduling interleaving.

The RFC includes a comparison against this v5 implementation on the same base, configuration, KVM setup, and staged testcase. The normal acyclic find_proxy_task() timings were comparable in the tested depths; the main design question is whether avoiding persistent task/rq visitation state and its activation lifecycle is worth accepting the transient backlink window.

Thanks for the v5 implementation and the detailed discussion.