sched/proxy_exec: Limit find_proxy_task() chain depth to prevent CPU hang
Subsystems (3)
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
--- kernel/sched/core.c | 17 +++++++++++++++++ 1 file changed, 17 insertions(+)
kernel/sched/core.c +17 -0
@@ -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
Quoted 22 lines · On Mon, Apr 13, 2026 at 10:36 PM <[email protected]> wrote:
From: zhidao su <[email protected]>
find_proxy_task()follows theblocked_onchain 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 holdingrq->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 bypick_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-EDEADLKwhen the chain is too deep.
Quoted 6 lines
Add a
chain_depthcounter with MAX_PROXY_CHAIN_DEPTH=64. When exceeded, emitWARN_ONCEand callproxy_resched_idle()to schedule idle briefly, consistent with how other unresolvable states are handled in the function (e.g., owner migrating,curr_in_chainbailouts). 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 anA->B->Adeadlock 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 insidefind_proxy_task()holdingrq->lockwith 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()")Signed-off-by zhidao su <[email protected]>--- kernel/sched/core.c | 17 +++++++++++++++++ 1 file changed, 17 insertions(+)kernel/sched/core.c +0
-0@@ -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
-0static 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
K Prateek Nayak
reviewerHello 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 insidefind_proxy_task()holdingrq->lockwith 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()")Signed-off-by zhidao su <[email protected]>--- kernel/sched/core.c | 17 +++++++++++++++++ 1 file changed, 17 insertions(+)kernel/sched/core.c +0
-0@@ -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 64So 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
-0static 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
Hello John, Prateek,
Quoted 7 lines · K Prateek Nayak
As an alternate approach, when traversing
blocked_onlinks, can we start deactivating the chain if we encounterrq->donoragain as owner infind_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
Hello John, Prateek,
Quoted 7 lines · K Prateek Nayak
As an alternate approach, when traversing
blocked_onlinks, can we start deactivating the chain if we encounterrq->donoragain as owner infind_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
PATCH v2 1/1 sched/proxy_exec: Break cyclic proxy chains by deactivating blocked tasks
In reply to K Prateek NayakFrom: "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
@@ -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
K Prateek Nayak
reviewerRe: [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@@ -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
@@ -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
@@ -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
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_donorbacklink 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.
K Prateek Nayak
reviewerRe: [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_donorbacklink 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
@@ -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
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_donorpick_seqfrom an old pick CPU colliding with thepick_seqafter 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_onbecomes a struct with alock_typeenum + void* pointer which allows for interpreting the pointer based on thelock_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_donorhas other uses with the extended series so it is best to use a separate variable to track theseq_countif we go down that route.
Right, that was my thinking as well.
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
@@ -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
@@ -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
@@ -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
@@ -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
K Prateek Nayak
reviewerRe: [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 sameblocked_onchain if the chain contains a cycle. This happens with a simpleA->B->Amutex 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_onstate 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"Signed-off-by zhidao su (Xiaomi) <[email protected]>---
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 overloadingblocked_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
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
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@@ -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
-0if (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@@ -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
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
@@ -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
@@ -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
@@ -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
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@@ -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
-2enqueue_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
-0if (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
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
@@ -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
@@ -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
@@ -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
Re: [PATCH v5] sched/proxy_exec: Detect cycles in proxy walks
Quoted 13 lines · zhidao su (Xiaomi)
find_proxy_task()can keep walking the sameblocked_onchain if the chain contains a cycle. A simpleA->B->Adeadlock can leave the CPU spinning in__schedule()withrq->lockheld.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_onat 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"Reviewed-by K Prateek Nayak <[email protected]>Signed-off-by zhidao su (Xiaomi) <[email protected]>
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
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
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_onat 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.