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

> 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.

I did some follow-up validation of the unchanged Online Brent patch on
tip/sched/core at e81ee0630837.

One relevant change since the base used for the original measurements is:

	772d9ffbfd26 ("sched: Migrate whole chain in proxy_migrate_task()")

proxy_migrate_task() now walks p->blocked_donor directly, so this seemed
like the most important current consumer against which to test the temporary
backlink cycle mentioned in the RFC.

I added validation-only, read-only instrumentation at
proxy_migrate_task() entry.  It inspected the already-built backlink prefix
but did not repair, truncate, or otherwise change the production migration
path.

The validation on that tip revision included cross-CPU/multi-hop cycle cases, long
acyclic chains, repeated reuse of the same task/mutex objects, and KCSAN
runs.  Some representative results were:

  - an acyclic depth-1024 case completed 2921/2921 observed whole-chain
    migrations, reaching a maximum backlink prefix of 1016 tasks;

  - curr_in_chain/current-task protection was exercised 959 times in that
    run, with no current task entering the migration prefix;

  - the same task/mutex objects were reused for 100 rounds while affinity
    changes forced remote-owner placement; 226/226 observed proxy migrations
    completed;

  - across the observed migration entries I saw no backlink cycle, duplicate
    task, wrong-rq task, or off-rq task;

  - the clean RFC kernel, without the observer, also completed the
    representative cycle cases, and a clean KCSAN build completed a
    tail-plus-cycle case and 100 repeated cycle/recovery rounds without a KCSAN
    report or fatal scheduler diagnostic.

This does not prove every possible owner-change interleaving, but in the
tested paths I did not observe the temporary backlink cycle caused by delayed
Brent detection escaping into the current whole-chain blocked_donor
consumer.

The control-flow argument also looks consistent with those results: before a
remote-owner migration, find_proxy_task() has not installed the backlink for
that owner edge, so proxy_migrate_task() sees the finite prefix already
constructed from the current donor.  Once a local backlink cycle can close,
those owners have already passed the same-rq validation while rq->lock is
held.

There is also a state-lifetime property of this approach that I think is
worth considering as PE evolves.

The Brent state:

	checkpoint / power / span

belongs entirely to one find_proxy_task() invocation.  In other words, the
lifetime of the cycle-detection state matches the lifetime of the owner walk
that consumes it.  Task activation, migration, or later reactivation
therefore do not have to carry or reset detector state.

I have not tested this RFC on top of the sleeping-owner, rwsem, or futex
series; the point here is about the ownership and lifetime of the
cycle-detection state rather than a compatibility claim for those patches.

The same separation applies at the owner-resolution boundary.  As long as a
blocking primitive exposes or resolves one dependency step to at most one
task owner, e.g.

	mutex -----------\
	rwsem writer -----+--> task owner
	futex ------------/

the detector still only sees a task-to-task walk and does not need to know
which primitive supplied the edge.

So the useful property here is that lock-specific owner resolution,
task/rq lifecycle, and cycle-detection state remain separate.

There is also a clear limit to this abstraction: Brent assumes one successor
per step.  If PE eventually models and traverses multiple rwsem readers as
dependency owners, the walk becomes a branching graph and cycle detection
would need to be reconsidered together with that traversal model.

The cost remains the one described in the RFC: detection can occur later
than the first repeated owner, and the walk can temporarily close a
blocked_donor cycle.  The current-tip testing above was intended to exercise
that cost against the whole-chain blocked_donor consumer now present in
proxy_migrate_task().

The RFC implementation itself did not need any changes after this
validation, so I do not plan to respin it just for the additional test
results.

At this point, the main question I would appreciate feedback on is whether
this trade-off -- invocation-local detector state in exchange for delayed
detection and the transient backlink window -- is reasonable for this path.

Thanks,
Hui