[RFC PATCH 0/1] sched/proxy_exec: detect cycles without persistent walk state

[RFC PATCH 0/1] sched/proxy_exec: detect cycles without persistent walk state

[Hui Su]

Proxy execution follows blocked_on relationships to find a runnable lock
owner. If that relationship contains a cycle, find_proxy_task() can loop
indefinitely while holding rq->lock.

Zhidao Su's v5 detects repetition with sequence state in task_struct and
struct rq, and resets the task marker on activation. This RFC explores a
different trade-off: keep cycle-detection state local to the real owner walk
without adding persistent task or runqueue state.

The patch applies Brent's checkpoint algorithm directly to the existing owner
walk. Cycle detection reuses the owner resolution already performed by the
real walk and does not add a separate preflight traversal. The existing
owner == p wakeup-race handling remains ahead of cycle detection because that
state does not by itself prove a deadlock cycle.

The Online Brent walk can temporarily install a blocked_donor cycle before
the delayed checkpoint detection point.

I also tested the lifetime of this transient state. In the natural recovery
path, a cycle member selected to run reached its subsequent mutex_unlock()
with blocked_donor already cleared. As a defense-in-depth check, a
validation-only forced-stale test restored a stale blocked_donor immediately
before mutex_unlock(); the existing blocked_on revalidation rejected that
handoff.

This does not prove every possible scheduling interleaving, but no
blocked_donor chain reader was found in the tested tree, and the tested
recovery path did not expose the transient backlink to normal mutex handoff.
Whether allowing that transient state while rq->lock is held is preferable
to persistent visitation state is the main design question for this RFC.

For comparison, Zhidao Su's v5 patch is available at:

https://lore.kernel.org/r/20260722120346.93000-1-soolaugust@gmail.com/

Both implementations were tested as one commit above the same base
revision, with the same x86_64 configuration, compiler, staged testcase
module, SSH initramfs, KVM setup, 2048 MiB guest memory, four vCPUs, and host
CPU affinity 8-11. The timing hook surrounds only find_proxy_task(),
accumulates per-CPU counters, and dumps once after each testcase. No
per-edge printk or atomic counter is used.

The following are medians from five fresh acyclic runs. ns/call is calculated
per run before selecting the median:

        depth   v5 ns/call   Online Brent ns/call   Online/v5
        -----   ----------   --------------------   ----------
        16      500          442                    0.884
        32      584          612                    1.048
        64      1314         988                    0.752
        128     2276         1942                   0.853
        256     4561         4815                   1.056
        512     9338         8396                   0.899
        1024    26551        25507                  0.961

The 16-64 entries are included for completeness; fixed per-call and guest
scheduling noise is more visible at those depths. Across these deeper
acyclic walks, Online Brent and the sequence-marker implementation show
comparable find_proxy_task() cost. These measurements are not intended to
claim a performance improvement for Online Brent; they show that keeping
Brent state in the real owner walk does not add a second owner traversal.

Cycle testing covered 33 topologies per implementation, including A -> B ->
A, A -> B -> C -> A, D -> A -> B -> C -> A, D0 -> D1 -> A -> B -> C -> A,
root cycle lengths through 513 with power-of-two boundaries, and tail lengths
1 and 5 with selected cycle lengths. Each topology was run in a fresh guest.
All 66 cases returned successfully and emitted exactly one cycle warning.
Saved dmesg logs include blocked_donor dumps. This build did not include a
per-edge cycle counter, so these results establish detection and progress,
not an exact first-closing-edge count.

Additional validation included Brent power-of-two boundaries, acyclic chains
through depth 1024, repeated task/mutex reuse, and a KCSAN + lockdep build.
The synthetic mutexes used to construct deliberate dependency cycles were
assigned no-validate lockdep classes so that those test dependencies did not
disable lockdep before the scheduler paths were exercised. No
Online-Brent-specific KCSAN report or scheduler lock-order failure was
observed.

The Online Brent patch changes one file with 19 implementation lines. Unlike
v5, it adds no task_struct or rq fields and needs no activation-time marker
reset.

A hard bound on proxy-walk length is intentionally left separate from this
cycle detector. In particular, should we also add an independent bound of
1024 owner transitions, matching the rt-mutex maximum lock depth, for
pathological acyclic or late-detected proxy-futex dependency graphs? Depth
exhaustion does not itself prove a cycle, so the recovery policy for such a
bound is orthogonal to cycle detection and is left for discussion.

The implementation diff in this message-only reroll is identical to the
Online Brent implementation used for the measurements; only commit-message
and cover-letter text changed after testing.

The open design question is whether avoiding persistent task/rq state and its
activation lifecycle is worth accepting the temporary blocked_donor cycle
window in the single-pass Online Brent walk.

Hui Su (1):
  sched/proxy_exec: detect cycles in proxy walks

 kernel/sched/core.c | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)


base-commit: 2f0c1cf72f4682178506f513bbf015e591b1aa4a
-- 
2.55.0

[RFC PATCH 1/1] sched/proxy_exec: detect cycles in proxy walks

[Hui Su]

Proxy execution follows blocked_on relationships to find a runnable lock
owner. A cycle in that chain can make find_proxy_task() loop indefinitely
while holding rq->lock.

Use Brent checkpoint state directly in the real owner walk. Cycle detection
reuses the owner resolution already performed by that walk and requires no
separate preflight traversal. The checkpoint, power, and span state are all
invocation-local.

Keep the existing owner == p wakeup-race handling ahead of cycle detection.
Unlike a sequence-marker approach, this adds no task_struct or runqueue
state and requires no activation-time reset.

The online walk can temporarily install a blocked_donor cycle before the
delayed Brent detection point. In the tested recovery path, the selected
task's blocked_donor was cleared before it resumed. A forced-stale control
also confirmed that mutex handoff revalidates the donor's blocked_on
relationship before consuming a backlink. Validation of this trade-off and
comparative measurements against the sequence-marker approach are included
in the cover letter.

Signed-off-by: Hui Su <sh_def@163.com>
---
 kernel/sched/core.c | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index b998ef6b87af..debf313ed9fd 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -6914,6 +6914,9 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 	__must_hold(__rq_lockp(rq))
 {
 	struct task_struct *owner = NULL;
+	struct task_struct *cycle_checkpoint = donor;
+	unsigned int cycle_power = 1;
+	unsigned int cycle_span = 0;
 	bool curr_in_chain = false;
 	int this_cpu = cpu_of(rq);
 	struct task_struct *p;
@@ -6921,6 +6924,13 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 
 	/* Follow blocked_on chain. */
 	for (p = donor; p->is_blocked; p = owner) {
+		/* Keep Brent's checkpoint state local to this owner walk. */
+		if (cycle_span == cycle_power) {
+			cycle_checkpoint = p;
+			cycle_power <<= 1;
+			cycle_span = 0;
+		}
+
 		/* if its PROXY_WAKING, do return migration or run if current */
 		struct mutex *mutex = p->blocked_on;
 		if (!mutex) {
@@ -7035,6 +7045,15 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			 */
 			return proxy_resched_idle(rq);
 		}
+
+		cycle_span++;
+		if (owner == cycle_checkpoint) {
+			pr_warn_once("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
-- 
2.55.0