[PATCHSET sched_ext/for-7.3-fixes] sched_ext: Fix keep-last for sub-scheduler tasks and two scx_qmap placement loops

[PATCHSET sched_ext/for-7.3-fixes] sched_ext: Fix keep-last for sub-scheduler tasks and two scx_qmap placement loops

[Tejun Heo]

Hello,

Running scx_qmap as a sub-scheduler under scx_nitosis exposed a kernel bug
and two scx_qmap bugs:

- dispatch_one() decides whether to keep running @prev by testing the root
  scheduler's SCX_OPS_ENQ_LAST and bypass state. Those are properties of
  @prev's own scheduler, and put_prev_task_scx() acts on that scheduler.
  When the root sets the flag and @prev belongs to a sub-scheduler that
  doesn't, the task is not kept and is enqueued with SCX_ENQ_LAST to a
  scheduler that never opted in. This trips the WARN_ON_ONCE in
  put_prev_task_scx(), and the task is queued without a follow-up scheduling
  event, which can stall it. Patches 1-2 fix this.

- scx_qmap added SCX_ENQ_IMMED to its rescue inserts, which turns a rescue
  request into a regular placement on a time-shared cid and loops with the
  kernel's REENQ bounce until the reenqueue limit ejects the scheduler.
  Patch 3 fixes this.

- scx_qmap placed tasks from the delegation split alone, ahead of the caps
  in effect on the cpus, so highpri moves to a freshly granted cid were
  denied and bounced. Patch 4 fixes this.

This patchset contains the following four patches:

 0001 sched_ext: Rename sch to root_sch in dispatch_one()
 0002 sched_ext: Use @prev's scheduler for the keep decisions in dispatch_one()
 0003 sched_ext: scx_qmap: Do not add IMMED to rescue inserts
 0004 sched_ext: scx_qmap: Place only on cids whose caps are in effect

0001-0002 fix the kernel side. 0003-0004 fix scx_qmap.

The patchset is based on sched_ext/for-7.3-fixes (0a85182723b6) and is also
available in the following git branch:

 git://git.kernel.org/pub/scm/linux/kernel/git/tj/sched_ext.git sub-keep-last-rescue

diffstat follows. Thanks.

 kernel/sched/ext/ext.c         |  33 ++++++++------
 tools/sched_ext/scx_qmap.bpf.c | 101 ++++++++++++++++++++++++++++++-----------
 tools/sched_ext/scx_qmap.h     |   3 ++
 3 files changed, 97 insertions(+), 40 deletions(-)

--
tejun

[PATCH sched_ext/for-7.3-fixes 1/4] sched_ext: Rename sch to root_sch in dispatch_one()

[Tejun Heo]

dispatch_one() uses the root scheduler for everything it does, including the
two decisions to keep running @prev, which are wrong when @prev belongs to a
sub-scheduler. The function has to deal with @prev's scheduler too. Rename
the root's local from sch to root_sch for clarity and to make room for it.
No functional change.

Signed-off-by: Tejun Heo <tj@kernel.org>
---
 kernel/sched/ext/ext.c | 16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)

diff --git a/kernel/sched/ext/ext.c b/kernel/sched/ext/ext.c
index 7e414a7c53fc..120540cdda74 100644
--- a/kernel/sched/ext/ext.c
+++ b/kernel/sched/ext/ext.c
@@ -2919,7 +2919,7 @@ static inline void maybe_queue_balance_callback(struct rq *rq)
 
 static enum scx_dsp_verdict dispatch_one(struct rq *rq, struct task_struct *prev)
 {
-	struct scx_sched *sch = scx_root_protected_live();
+	struct scx_sched *root_sch = scx_root_protected_live();
 	enum scx_dsp_verdict verdict;
 	s32 cpu = cpu_of(rq);
 
@@ -2928,7 +2928,7 @@ static enum scx_dsp_verdict dispatch_one(struct rq *rq, struct task_struct *prev
 
 	scx_process_sync_ecaps(rq, prev);
 
-	if ((sch->ops.flags & SCX_OPS_HAS_CPU_PREEMPT) &&
+	if ((root_sch->ops.flags & SCX_OPS_HAS_CPU_PREEMPT) &&
 	    unlikely(rq->scx.cpu_released)) {
 		/*
 		 * If the previous sched_class for the current CPU was not SCX,
@@ -2936,8 +2936,8 @@ static enum scx_dsp_verdict dispatch_one(struct rq *rq, struct task_struct *prev
 		 * core. This callback complements ->cpu_release(), which is
 		 * emitted in switch_class().
 		 */
-		if (sch->ops.cpu_acquire)
-			SCX_CALL_OP(sch, cpu_acquire, rq, cpu, NULL);
+		if (root_sch->ops.cpu_acquire)
+			SCX_CALL_OP(root_sch, cpu_acquire, rq, cpu, NULL);
 		rq->scx.cpu_released = false;
 	}
 
@@ -2955,7 +2955,7 @@ static enum scx_dsp_verdict dispatch_one(struct rq *rq, struct task_struct *prev
 		 * test.
 		 */
 		if ((prev->scx.flags & SCX_TASK_QUEUED) && prev->scx.slice &&
-		    !scx_bypassing(sch, cpu)) {
+		    !scx_bypassing(root_sch, cpu)) {
 			verdict = SCX_DSP_PREV;
 			goto has_tasks;
 		}
@@ -2967,7 +2967,7 @@ static enum scx_dsp_verdict dispatch_one(struct rq *rq, struct task_struct *prev
 		goto has_tasks;
 	}
 
-	verdict = scx_dispatch_sched(sch, rq, prev, false);
+	verdict = scx_dispatch_sched(root_sch, rq, prev, false);
 	if (verdict != SCX_DSP_NONE)
 		goto has_tasks;
 
@@ -2976,9 +2976,9 @@ static enum scx_dsp_verdict dispatch_one(struct rq *rq, struct task_struct *prev
 	 * %SCX_OPS_ENQ_LAST is in effect.
 	 */
 	if ((prev->scx.flags & SCX_TASK_QUEUED) &&
-	    (!(sch->ops.flags & SCX_OPS_ENQ_LAST) || scx_bypassing(sch, cpu)) &&
+	    (!(root_sch->ops.flags & SCX_OPS_ENQ_LAST) || scx_bypassing(root_sch, cpu)) &&
 	    scx_task_can_stay_on_cpu(rq, prev)) {
-		__scx_add_event(sch, SCX_EV_DISPATCH_KEEP_LAST, 1);
+		__scx_add_event(root_sch, SCX_EV_DISPATCH_KEEP_LAST, 1);
 		verdict = SCX_DSP_PREV;
 		goto has_tasks;
 	}
-- 
2.55.0

[PATCH sched_ext/for-7.3-fixes 2/4] sched_ext: Use @prev's scheduler for the keep decisions in dispatch_one()

[Tejun Heo]

dispatch_one() tests ops flags and bypass state against the root scheduler
in both places where it decides to keep running @prev: the early keep of a
@prev with slice left tests the root's bypass state, and the keep-last at
the end tests the root's SCX_OPS_ENQ_LAST and bypass state. Both are
properties of the scheduler @prev belongs to, and put_prev_task_scx(), which
acts on the outcome, reads them from that scheduler. When @prev belongs to a
sub-scheduler the two sides disagree.

The keep-last case is visible. The root set SCX_OPS_ENQ_LAST, so a lone
@prev of a sub-scheduler is not kept and is enqueued with SCX_ENQ_LAST to a
sub-scheduler that never opted in. This trips the WARN_ON_ONCE in
put_prev_task_scx() for the missing flag, and the sub-scheduler queues the
task like any other and triggers no follow-up scheduling event, which can
lead to stalls.

Test SCX_OPS_ENQ_LAST and bypass state on @prev's sched in both places and
charge SCX_EV_DISPATCH_KEEP_LAST to it. Read the sched at each decision, as
the dispatch in between can drop the rq lock.

Fixes: 88234b075c3f ("sched_ext: Introduce scx_task_sched[_rcu]()")
Signed-off-by: Tejun Heo <tj@kernel.org>
---
 kernel/sched/ext/ext.c | 23 ++++++++++++++---------
 1 file changed, 14 insertions(+), 9 deletions(-)

diff --git a/kernel/sched/ext/ext.c b/kernel/sched/ext/ext.c
index 120540cdda74..adf5993fa597 100644
--- a/kernel/sched/ext/ext.c
+++ b/kernel/sched/ext/ext.c
@@ -2955,7 +2955,7 @@ static enum scx_dsp_verdict dispatch_one(struct rq *rq, struct task_struct *prev
 		 * test.
 		 */
 		if ((prev->scx.flags & SCX_TASK_QUEUED) && prev->scx.slice &&
-		    !scx_bypassing(root_sch, cpu)) {
+		    !scx_bypassing(scx_task_sched(prev), cpu)) {
 			verdict = SCX_DSP_PREV;
 			goto has_tasks;
 		}
@@ -2972,15 +2972,20 @@ static enum scx_dsp_verdict dispatch_one(struct rq *rq, struct task_struct *prev
 		goto has_tasks;
 
 	/*
-	 * Didn't find another task to run. Keep running @prev unless
-	 * %SCX_OPS_ENQ_LAST is in effect.
+	 * Didn't find another task to run. Keep running @prev unless its own
+	 * scheduler set %SCX_OPS_ENQ_LAST and takes the enqueue instead, see
+	 * put_prev_task_scx(). Read the scheduler here as the dispatch above
+	 * may have dropped the rq lock while @prev changed class or scheduler.
 	 */
-	if ((prev->scx.flags & SCX_TASK_QUEUED) &&
-	    (!(root_sch->ops.flags & SCX_OPS_ENQ_LAST) || scx_bypassing(root_sch, cpu)) &&
-	    scx_task_can_stay_on_cpu(rq, prev)) {
-		__scx_add_event(root_sch, SCX_EV_DISPATCH_KEEP_LAST, 1);
-		verdict = SCX_DSP_PREV;
-		goto has_tasks;
+	if (prev->scx.flags & SCX_TASK_QUEUED) {
+		struct scx_sched *prev_sch = scx_task_sched(prev);
+
+		if ((!(prev_sch->ops.flags & SCX_OPS_ENQ_LAST) ||
+		     scx_bypassing(prev_sch, cpu)) && scx_task_can_stay_on_cpu(rq, prev)) {
+			__scx_add_event(prev_sch, SCX_EV_DISPATCH_KEEP_LAST, 1);
+			verdict = SCX_DSP_PREV;
+			goto has_tasks;
+		}
 	}
 	rq->scx.flags &= ~SCX_RQ_IN_DISPATCH;
 	return SCX_DSP_NONE;
-- 
2.55.0

[PATCH sched_ext/for-7.3-fixes 3/4] sched_ext: scx_qmap: Do not add IMMED to rescue inserts

[Tejun Heo]

qmap's stranded fallback forces a task that can run on none of its self cids
onto its first allowed cid with SCX_ENQ_RESCUE, and adds SCX_ENQ_IMMED when
that cid is a time-share it holds. On such a cid the insert stops being a
rescue request:

1. A task is enqueued while none of its allowed cids is in self_cids. At
   attach self_cids is still empty.
2. qmap inserts it into cid 0's local DSQ with SCX_ENQ_RESCUE |
   SCX_ENQ_IMMED.
3. The kernel finds ENQ_IMMED held on cid 0, admits the insert and skips the
   rescue diversion.
4. cid 0's cpu is busy, so the IMMED task is bounced back to qmap with
   SCX_ENQ_REENQ.
5. qmap's enqueue sees the same inputs and repeats step 2. Nothing runs in
   between.
6. The reenqueue limit ejects qmap with SCX_EXIT_ERROR_REENQ.

The caps granted during the parent's ops.sub_attach() are delivered after
the sub already holds its tasks, while the per-cid effective caps that mark
the time-shares are delivered from the first dispatch after bypass lifts, so
every attach that receives a time-share on a task's first allowed cid starts
the loop. Drop IMMED from the rescue inserts so that step 3 diverts to the
rescue path.

Signed-off-by: Tejun Heo <tj@kernel.org>
---
 tools/sched_ext/scx_qmap.bpf.c | 18 ++++++++++--------
 1 file changed, 10 insertions(+), 8 deletions(-)

diff --git a/tools/sched_ext/scx_qmap.bpf.c b/tools/sched_ext/scx_qmap.bpf.c
index 9f6e61d7ca07..e4e51303bd29 100644
--- a/tools/sched_ext/scx_qmap.bpf.c
+++ b/tools/sched_ext/scx_qmap.bpf.c
@@ -358,8 +358,8 @@ s32 BPF_STRUCT_OPS(qmap_select_cid, struct task_struct *p,
 }
 
 /*
- * A received time-shared cid is held ENQ_IMMED-only, so inserts must set
- * SCX_ENQ_IMMED.
+ * A received time-shared cid is held ENQ_IMMED-only, so inserts meant to run
+ * there must set SCX_ENQ_IMMED.
  */
 static u64 needs_immed(s32 cid)
 {
@@ -444,9 +444,11 @@ void BPF_STRUCT_OPS(qmap_enqueue, struct task_struct *p, u64 enq_flags)
 	 * didn't grant them or we delegated them to children - would starve in
 	 * SHARED/FIFO since we only pull from those on self cids.
 	 *
-	 * Force it onto its first allowed cid's local DSQ. If we hold that cid
-	 * it runs. Otherwise the insert carries SCX_ENQ_RESCUE and the kernel
-	 * diverts the task to its rescue path.
+	 * Force it onto its first allowed cid's local DSQ with SCX_ENQ_RESCUE.
+	 * If we hold ENQ on that cid it runs. Otherwise the kernel diverts the
+	 * task to its rescue path. IMMED would turn the insert into a legal
+	 * placement on a time-shared cid and the kernel would bounce it back
+	 * here instead of rescuing it.
 	 */
 	if (!cmask_intersects(&taskc->cpus_allowed, &qa.self_cids.mask)) {
 		s32 c = cmask_next_set_wrap(&taskc->cpus_allowed, 0);
@@ -455,7 +457,7 @@ void BPF_STRUCT_OPS(qmap_enqueue, struct task_struct *p, u64 enq_flags)
 			taskc->force_local = false;
 			__sync_fetch_and_add(&qa.nr_rescue_dsp, 1);
 			scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL_ON | c, slice_ns,
-					   enq_flags | needs_immed(c) | SCX_ENQ_RESCUE);
+					   enq_flags | SCX_ENQ_RESCUE);
 			return;
 		}
 	}
@@ -618,7 +620,7 @@ static bool scan_shared_dsq(bool from_timer)
 			if (c >= 0 && c < scx_bpf_nr_cids()) {
 				__sync_fetch_and_add(&qa.nr_rescue_dsp, 1);
 				scx_bpf_dsq_move(BPF_FOR_EACH_ITER, p, SCX_DSQ_LOCAL_ON | c,
-						 needs_immed(c) | SCX_ENQ_RESCUE);
+						 SCX_ENQ_RESCUE);
 			}
 			continue;
 		}
@@ -659,7 +661,7 @@ static bool scan_shared_dsq(bool from_timer)
 			if (c >= 0 && c < nr_cids) {
 				__sync_fetch_and_add(&qa.nr_rescue_dsp, 1);
 				scx_bpf_dsq_move(BPF_FOR_EACH_ITER, p, SCX_DSQ_LOCAL_ON | c,
-						 needs_immed(c) | SCX_ENQ_RESCUE);
+						 SCX_ENQ_RESCUE);
 			}
 			continue;
 		}
-- 
2.55.0

[PATCH sched_ext/for-7.3-fixes 4/4] sched_ext: scx_qmap: Place only on cids whose caps are in effect

[Tejun Heo]

qmap decides placements from self_cids, which redistribute() derives from
the caps view at ops.sub_caps_updated() time. That view runs ahead of the
cpus: a granted cid can be in self_cids before its cpu has reported the caps
in effect through ops.sub_ecaps_updated(). ops.update_idle() only comes once
BASE is in effect, so the idle-gated placements reach such a cid only
through an idle bit left over from an earlier hold. The highpri scan has no
gate at all:

  parent                    cpu Y, qmap               cpu X
  grants ENQ on X to qmap
                            sub_caps_updated() adds X
                            to self_cids
                            highpri scan moves a task
                            to X with PREEMPT
                                                      caps not in effect,
                                                      move denied, task
                                                      bounced with REENQ_CAP
                                                      reject drain, enqueue
                            the scan moves it to X
                            again
                                                      denied again
                                                      dispatch syncs ecaps,
                                                      sub_ecaps_updated(X)

Every highpri move to X in that window is denied and bounced. The two
callbacks are meant to split the roles: ops.sub_caps_updated() tracks what
the node holds and drives what it delegates to its children, while
ops.sub_ecaps_updated() says whether a task can run on a cpu now. qmap used
the first for both. Track the caps in effect from ops.sub_ecaps_updated() as
avail_cids and place only on self_cids & avail_cids, so that self_cids stays
the delegation split and avail_cids gates the placement.

The stranded tests keep self_cids, as they ask whether the split gives the
task anywhere at all. A highpri task whose self_cids lack caps in effect
waits for them instead of being moved and bounced.

Signed-off-by: Tejun Heo <tj@kernel.org>
---
 tools/sched_ext/scx_qmap.bpf.c | 83 ++++++++++++++++++++++++++--------
 tools/sched_ext/scx_qmap.h     |  3 ++
 2 files changed, 68 insertions(+), 18 deletions(-)

diff --git a/tools/sched_ext/scx_qmap.bpf.c b/tools/sched_ext/scx_qmap.bpf.c
index e4e51303bd29..062bb22ee65c 100644
--- a/tools/sched_ext/scx_qmap.bpf.c
+++ b/tools/sched_ext/scx_qmap.bpf.c
@@ -24,6 +24,9 @@
  *            time-share that stays self-local.
  *   self   - The excl cpus the node kept for itself, plus all of held_shared.
  *   owner  - Who holds a cid - a child slot, CID_SELF, or CID_NONE.
+ *   avail  - Cpus whose caps are in effect, per ops.sub_ecaps_updated().
+ *   usable - self AND avail. Placement decisions use this: self is the
+ *            delegation split and can run ahead of what the cpus honor.
  *
  * The scheduler splits its held-excl cpus among self and the children in
  * proportion to each node's cpu.weight, handing each the floor of its share as
@@ -208,8 +211,8 @@ static int qmap_spin_lock(struct bpf_res_spin_lock *lock)
 }
 
 /*
- * Try prev_cid, then scan cpus_allowed AND idle_cids AND self_cids round-robin
- * from prev_cid + 1. Atomic claim retries on race; bounded by
+ * Try prev_cid, then scan cpus_allowed AND idle_cids AND usable_cids
+ * round-robin from prev_cid + 1. Atomic claim retries on race; bounded by
  * IDLE_PICK_RETRIES to keep the verifier's insn budget in check.
  */
 #define IDLE_PICK_RETRIES	16
@@ -221,7 +224,7 @@ static s32 pick_direct_dispatch_cid(struct task_struct *p, s32 prev_cid,
 	s32 cid;
 	u32 i;
 
-	if (cmask_test(prev_cid, &qa.self_cids.mask) &&
+	if (cmask_test(prev_cid, &qa.usable_cids.mask) &&
 	    cmask_test_and_clear(prev_cid, &qa.idle_cids.mask))
 		return prev_cid;
 
@@ -229,7 +232,7 @@ static s32 pick_direct_dispatch_cid(struct task_struct *p, s32 prev_cid,
 	bpf_for(i, 0, IDLE_PICK_RETRIES) {
 		cid = cmask_next_and2_set_wrap(&taskc->cpus_allowed,
 					       &qa.idle_cids.mask,
-					       &qa.self_cids.mask, cid + 1);
+					       &qa.usable_cids.mask, cid + 1);
 		barrier_var(cid);
 		if (cid >= nr_cids)
 			return -1;
@@ -542,7 +545,7 @@ void BPF_STRUCT_OPS(qmap_enqueue, struct task_struct *p, u64 enq_flags)
 		scx_bpf_dsq_insert(p, SHARED_DSQ, 0, enq_flags);
 		cid = cmask_next_and2_set_wrap(&taskc->cpus_allowed,
 					       &qa.idle_cids.mask,
-					       &qa.self_cids.mask, 0);
+					       &qa.usable_cids.mask, 0);
 		if (cid < scx_bpf_nr_cids())
 			scx_bpf_kick_cid(cid, SCX_KICK_IDLE);
 		return;
@@ -646,18 +649,23 @@ static bool scan_shared_dsq(bool from_timer)
 		if (!(taskc = lookup_task_ctx(p)))
 			return false;
 
-		/* only run highpri tasks on cids this node holds, not delegated ones */
+		/* only run highpri tasks on cids this node can use right now */
 		if (cmask_test(this_cid, &taskc->cpus_allowed) &&
-		    cmask_test(this_cid, &qa.self_cids.mask))
+		    cmask_test(this_cid, &qa.usable_cids.mask))
 			cid = this_cid;
 		else
 			cid = cmask_next_and_set_wrap(&taskc->cpus_allowed,
-						      &qa.self_cids.mask,
+						      &qa.usable_cids.mask,
 						      this_cid + 1);
 		if (cid >= nr_cids) {
-			/* stranded after the cull - rescue it from here */
-			s32 c = cmask_next_set_wrap(&taskc->cpus_allowed, 0);
+			s32 c;
+
+			/* self cids lack caps in effect yet, leave it queued */
+			if (cmask_intersects(&taskc->cpus_allowed, &qa.self_cids.mask))
+				continue;
 
+			/* stranded after the cull - rescue it from here */
+			c = cmask_next_set_wrap(&taskc->cpus_allowed, 0);
 			if (c >= 0 && c < nr_cids) {
 				__sync_fetch_and_add(&qa.nr_rescue_dsp, 1);
 				scx_bpf_dsq_move(BPF_FOR_EACH_ITER, p, SCX_DSQ_LOCAL_ON | c,
@@ -1115,7 +1123,7 @@ void BPF_STRUCT_OPS(qmap_update_idle, s32 cid, bool idle)
 	/*
 	 * The kernel delivers update_idle() for every cid this node holds
 	 * SCX_CAP_BASE on. Track every cid's idle state regardless of
-	 * delegation: the direct-dispatch pick masks idle_cids with self_cids
+	 * delegation: the direct-dispatch pick masks idle_cids with usable_cids
 	 * at selection, so a cid already idle when it returns to self needs no
 	 * reseed here.
 	 */
@@ -1539,6 +1547,19 @@ static __noinline void account_alloc(void)
 	}
 }
 
+/*
+ * usable_cids = self_cids & avail_cids. The inputs have separate writers,
+ * apply_partition() and qmap_sub_ecaps_updated(), so the result is rebuilt in
+ * full under the partition guard, in scratch first so that readers never see
+ * self_cids alone.
+ */
+static void refresh_usable(void)
+{
+	cmask_copy(&qa.usable_scratch.mask, &qa.self_cids.mask);
+	cmask_and(&qa.usable_scratch.mask, &qa.avail_cids.mask);
+	cmask_copy(&qa.usable_cids.mask, &qa.usable_scratch.mask);
+}
+
 /*
  * apply_partition - execute the plan compute_partition() built
  *
@@ -1561,6 +1582,7 @@ __noinline void apply_partition(void)
 	/* no excl cpu: run own tasks on the held shares, evict children */
 	if (!qa.part.nr_excl) {
 		cmask_copy(&qa.self_cids.mask, &qa.held_shared.mask);
+		refresh_usable();
 		bpf_for(i, 0, MAX_SUB_SCHEDS)
 			if (qa.sub_sched_ctxs[i].cgroup_id)
 				scx_bpf_sub_kill(qa.sub_sched_ctxs[i].cgroup_id,
@@ -1598,6 +1620,7 @@ __noinline void apply_partition(void)
 		else if (o == CID_SELF)
 			cmask_set(cid, &qa.self_cids.mask);
 	}
+	refresh_usable();
 
 	/*
 	 * Apply each child's exclusive cids as a delta against its previous
@@ -1839,8 +1862,11 @@ s32 BPF_STRUCT_OPS_SLEEPABLE(qmap_init)
 	cmask_init(&qa.rr_cids.mask, 0, nr_cids);
 	cmask_init(&qa.prev_rr_cids.mask, 0, nr_cids);
 	cmask_init(&qa.self_cids.mask, 0, nr_cids);
+	cmask_init(&qa.avail_cids.mask, 0, nr_cids);
+	cmask_init(&qa.usable_cids.mask, 0, nr_cids);
 	cmask_init(&qa.to_revoke_cids.mask, 0, nr_cids);
 	cmask_init(&qa.to_grant_cids.mask, 0, nr_cids);
+	cmask_init(&qa.usable_scratch.mask, 0, nr_cids);
 	cmask_init(&qa.held_excl.mask, 0, nr_cids);
 	cmask_init(&qa.held_shared.mask, 0, nr_cids);
 
@@ -1854,14 +1880,16 @@ s32 BPF_STRUCT_OPS_SLEEPABLE(qmap_init)
 	}
 
 	/*
-	 * The root starts holding every cid. qmap_sub_ecaps_updated() maintains
-	 * per-cid shared state as effective caps settle, and redistribute()
-	 * rebuilds owner and self from held caps. A non-root node starts with
-	 * nothing.
+	 * The root starts holding every cid and gets no ecaps notifications, so
+	 * its avail set is fixed here. qmap_sub_ecaps_updated() maintains the
+	 * per-cid state as effective caps settle, and redistribute() rebuilds
+	 * owner and self from held caps. A non-root node starts with nothing.
 	 */
 	bpf_for(i, 0, nr_cids) {
 		if (!sub_cgroup_id) {
 			cmask_set(i, &qa.self_cids.mask);
+			cmask_set(i, &qa.avail_cids.mask);
+			cmask_set(i, &qa.usable_cids.mask);
 			qa.part.cid_owner[i] = CID_SELF;
 		} else {
 			qa.part.cid_owner[i] = CID_NONE;
@@ -2002,12 +2030,31 @@ void BPF_STRUCT_OPS(qmap_sub_ecaps_updated, s32 cid, u64 before, u64 after)
 {
 	/*
 	 * Effective caps updated. Track which cids hold shared caps so a self
-	 * task placed there enqueues IMMED.
+	 * task placed there enqueues IMMED, and which cids have ENQ_IMMED in
+	 * effect at all (avail, see the header comment).
 	 */
-	if (after & SCX_CAP_ENQ_IMMED)
+	if (after & SCX_CAP_ENQ_IMMED) {
 		qa.cid_shared[cid] = (after & SCX_CAP_ENQ) ? 0 : 1;
-	else
+		cmask_set(cid, &qa.avail_cids.mask);
+	} else {
 		qa.cid_shared[cid] = 0;
+		cmask_clear(cid, &qa.avail_cids.mask);
+	}
+
+	/*
+	 * When another runner holds the partition guard, set part_pending:
+	 * redistribute() drains it before releasing and rr_advance() checks it
+	 * after, so the deferred refresh lands by the next rr tick. A
+	 * repartition that lost the guard to us runs here.
+	 */
+	if (part_try_start()) {
+		refresh_usable();
+		part_end();
+		if (__sync_fetch_and_or(&part_pending, 0))
+			redistribute();
+	} else {
+		__sync_fetch_and_or(&part_pending, 1);
+	}
 }
 
 SCX_OPS_CID_DEFINE(qmap_ops,
diff --git a/tools/sched_ext/scx_qmap.h b/tools/sched_ext/scx_qmap.h
index c78d61806b39..e95fffcf7b23 100644
--- a/tools/sched_ext/scx_qmap.h
+++ b/tools/sched_ext/scx_qmap.h
@@ -165,12 +165,15 @@ struct qmap_arena {
 
 	/* bpf-internal cmasks (embedded, see struct qmap_cmask) */
 	struct qmap_cmask self_cids;	/* cids this node runs its own tasks on */
+	struct qmap_cmask avail_cids;	/* cids with caps in effect on the cpu */
+	struct qmap_cmask usable_cids;	/* self_cids & avail_cids, placeable right now */
 	struct qmap_cmask idle_cids;	/* idle state of all cids regardless of delegation */
 	struct qmap_cmask rr_cids;	/* the shared pool, as a mask for grant/revoke */
 
 	/* scratch cmasks */
 	struct qmap_cmask to_revoke_cids; /* delta cids to revoke */
 	struct qmap_cmask to_grant_cids; /* delta cids to grant */
+	struct qmap_cmask usable_scratch; /* refresh_usable() build area */
 	struct qmap_cmask prev_rr_cids; /* previous shared pool, to clear stale grants */
 	struct qmap_cmask held_excl;	/* cids held excl (ENQ): delegatable */
 	struct qmap_cmask held_shared;	/* cids held shared (ENQ_IMMED only): self-local */
-- 
2.55.0

Re: [PATCH sched_ext/for-7.3-fixes 4/4] sched_ext: scx_qmap: Place only on cids whose caps are in effect

[Tejun Heo]

Hello,

> This is a pre-existing issue, but can lockless readers observe a transiently
> zeroed qa.self_cids.mask here and incorrectly fall through to the rescue block?

Yes, but scx_qmap is an example scheduler and the result is a spurious rescue
insert, which isn't critical. The race is acceptable.

Thanks.

--
tejun

Re: [PATCH sched_ext/for-7.3-fixes 4/4] sched_ext: scx_qmap: Place only on cids whose caps are in effect

[Andrea Righi]

On Sat, Sep 05, 2026 at 06:40:32AM -1000, Tejun Heo wrote:
> Hello,
> 
> > This is a pre-existing issue, but can lockless readers observe a transiently
> > zeroed qa.self_cids.mask here and incorrectly fall through to the rescue block?
> 
> Yes, but scx_qmap is an example scheduler and the result is a spurious rescue
> insert, which isn't critical. The race is acceptable.

BTW, while looking at this I noticed another potential different race in
qmap_sub_ecaps_updated() busy/pending handoff.

    CPU0                                  CPU1
    holds part_busy
    refresh_usable() using old avail
                                          update avail_cids
                                          part_try_start() fails
    sees part_pending == 0
    part_end()
    returns
                                          sets part_pending = 1

IIUC, there's no owner left to consume part_pending immediately at this point,
so usable_cids can remain stale until the next rr_advance() or redistribute()
pass. It should self-correct, but a task may remain queued until another
dispatch event.

This is likely not a big problem either, just wanted to point it out as a
separate one from the transient self_cids issue reported by Sashiko.

Thanks,
-Andrea

Re: [PATCHSET sched_ext/for-7.3-fixes] sched_ext: Fix keep-last for sub-scheduler tasks and two scx_qmap placement loops

[Andrea Righi]

Hi Tejun,

On Sat, Sep 05, 2026 at 06:09:54AM -1000, Tejun Heo wrote:
> Hello,
> 
> Running scx_qmap as a sub-scheduler under scx_nitosis exposed a kernel bug
> and two scx_qmap bugs:
> 
> - dispatch_one() decides whether to keep running @prev by testing the root
>   scheduler's SCX_OPS_ENQ_LAST and bypass state. Those are properties of
>   @prev's own scheduler, and put_prev_task_scx() acts on that scheduler.
>   When the root sets the flag and @prev belongs to a sub-scheduler that
>   doesn't, the task is not kept and is enqueued with SCX_ENQ_LAST to a
>   scheduler that never opted in. This trips the WARN_ON_ONCE in
>   put_prev_task_scx(), and the task is queued without a follow-up scheduling
>   event, which can stall it. Patches 1-2 fix this.
> 
> - scx_qmap added SCX_ENQ_IMMED to its rescue inserts, which turns a rescue
>   request into a regular placement on a time-shared cid and loops with the
>   kernel's REENQ bounce until the reenqueue limit ejects the scheduler.
>   Patch 3 fixes this.
> 
> - scx_qmap placed tasks from the delegation split alone, ahead of the caps
>   in effect on the cpus, so highpri moves to a freshly granted cid were
>   denied and bounced. Patch 4 fixes this.

Apart from the comment about PATCH 4 (which I don't think it's a blocker)
everything else looks good to me.

For the series:

Reviewed-by: Andrea Righi <arighi@nvidia.com>

Thanks,
-Andrea

> 
> This patchset contains the following four patches:
> 
>  0001 sched_ext: Rename sch to root_sch in dispatch_one()
>  0002 sched_ext: Use @prev's scheduler for the keep decisions in dispatch_one()
>  0003 sched_ext: scx_qmap: Do not add IMMED to rescue inserts
>  0004 sched_ext: scx_qmap: Place only on cids whose caps are in effect
> 
> 0001-0002 fix the kernel side. 0003-0004 fix scx_qmap.
> 
> The patchset is based on sched_ext/for-7.3-fixes (0a85182723b6) and is also
> available in the following git branch:
> 
>  git://git.kernel.org/pub/scm/linux/kernel/git/tj/sched_ext.git sub-keep-last-rescue
> 
> diffstat follows. Thanks.
> 
>  kernel/sched/ext/ext.c         |  33 ++++++++------
>  tools/sched_ext/scx_qmap.bpf.c | 101 ++++++++++++++++++++++++++++++-----------
>  tools/sched_ext/scx_qmap.h     |   3 ++
>  3 files changed, 97 insertions(+), 40 deletions(-)
> 
> --
> tejun