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

[Hui Su]

> 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