Skip to contentSkip to conversation

sched_ext: Update core-sched task ordering for scheduler hierarchies

PATCH In review Tejun Heo 1 participant 6 messages Aug 16

Subsystems (3)
lore
Share & tools
lore

Tejun Heo

author reviewer
#0 lore raw

PATCH 1/1 sched_ext: Update core-sched task ordering for scheduler hierarchies

Hello,

Core-sched task ordering predates sub-schedulers. scx_prio_less() consults ops.core_sched_before() only when both tasks belong to the same scheduler, and the timestamp fallback maintains its own stamp, p->scx.core_sched_at, under two different stamping rules. This patchset updates core-sched task ordering for scheduler hierarchies:

- Fix ops.core_sched_before() being invoked with inverted polarity.

- Replace core_sched_at with p->scx.runnable_at which the stall watchdog already maintains, so that the fallback follows one wait-tracking rule. A running task orders after every waiting task.

- Order a pair of tasks spanning two schedulers by the nearest common ancestor which implements ops.core_sched_before().

- Drop a dead core-sched related test in the dequeue path.

This patchset contains the following four patches:

0001-sched_ext-Fix-inverted-ops.core_sched_before-invocat.patch 0002-sched_ext-Use-runnable_at-for-the-default-core-sched.patch 0003-sched_ext-Make-core-sched-task-ordering-hierarchy-aw.patch 0004-sched_ext-Drop-the-dead-SCX_DEQ_CORE_SCHED_EXEC-test.patch

and is on top of sched_ext/for-7.3 (3167bd3e0c22). The patches are also available in the following git branch:

git://git.kernel.org/pub/scm/linux/kernel/git/tj/sched_ext.git core-sched-hier

diffstat follows. Thanks.

 include/linux/sched/ext.h      |   3 -
 kernel/sched/ext/ext.c         | 147 +++++++++++++++++------------------------
 kernel/sched/ext/internal.h    |   5 ++
 tools/sched_ext/scx_qmap.bpf.c |  23 +++++--
 4 files changed, 81 insertions(+), 97 deletions(-)

--
tejun

author reviewer
#1 lore raw

PATCH 1/4 sched_ext: Fix inverted ops.core_sched_before() invocation

scx_prio_less() implements prio_less() semantics - %true means that @a is the lower priority and should run after @b. ops.core_sched_before() is documented to return %true when @a should run before @b. scx_prio_less() returns the op's value as-is, inverting the documented semantics at runtime.

Call the op with the arguments swapped.

scx_qmap followed the wiring instead of the documentation and returned %true for the younger task, so the two inversions canceled out and it behaved as intended. Flip its comparison to match. scx_qmap is likely the only current user in or out of the kernel tree. Any scheduler written the same way needs the same flip, while schedulers following the documentation are fixed by this change.

Fixes 7b0888b7cc19 ("sched_ext: Implement core-sched support")
Cc [email protected] # v6.12+
---
 kernel/sched/ext/ext.c         | 10 ++++++++--
 tools/sched_ext/scx_qmap.bpf.c |  2 +-
 2 files changed, 9 insertions(+), 3 deletions(-)
kernel/sched/ext/ext.c +8 -2
index cbbf3fa7462b..ddf448d526e4 100644
@@ -3528,6 +3528,8 @@ void ext_server_init(struct rq *rq)
  *
  * When ops.core_sched_before() is enabled, @p->scx.core_sched_at is used to
  * implement FIFO ordering within each local DSQ. See pick_task_scx().
+ *
+ * Return: %true if @a should run after @b.
  */
 bool scx_prio_less(const struct task_struct *a, const struct task_struct *b,
 		   bool in_fi)
@@ -3536,6 +3538,10 @@ bool scx_prio_less(const struct task_struct *a, const struct task_struct *b,
 	struct scx_sched *sch_b = scx_task_sched(b);
 
 	/*
+	 * scx_prio_less() returns whether @a should run after @b while
+	 * ops.core_sched_before() returns whether its first argument should run
+	 * before the second. Swap the arguments.
+	 *
 	 * The const qualifiers are dropped from task_struct pointers when
 	 * calling ops.core_sched_before(). Accesses are controlled by the
 	 * verifier.
@@ -3544,8 +3550,8 @@ bool scx_prio_less(const struct task_struct *a, const struct task_struct *b,
 	    !scx_bypassing(sch_a, task_cpu(a)))
 		return SCX_CALL_OP_2TASKS_RET(sch_a, core_sched_before,
 					      task_rq(a),
-					      (struct task_struct *)a,
-					      (struct task_struct *)b);
+					      (struct task_struct *)b,
+					      (struct task_struct *)a);
 	else
 		return time_after64(a->scx.core_sched_at, b->scx.core_sched_at);
 }
tools/sched_ext/scx_qmap.bpf.c +1 -1
index dd0434437835..723f45fe0cbc 100644
@@ -900,7 +900,7 @@ static s64 task_qdist(struct task_struct *p)
 bool BPF_STRUCT_OPS(qmap_core_sched_before,
 		    struct task_struct *a, struct task_struct *b)
 {
-	return task_qdist(a) > task_qdist(b);
+	return task_qdist(a) < task_qdist(b);
 }
 
 /*
Signature · 1 line
2.55.0
author reviewer
#2 lore raw

PATCH 2/4 sched_ext: Use runnable_at for the default core-sched task ordering

In reply to Tejun Heo

The default core-sched ordering runs the longest waiting task first by comparing p->scx.core_sched_at stamps. The stamp is maintained under two rules. touch_core_sched() stamps when a task starts waiting for a CPU and when its slice runs out. If the scheduler implements ops.core_sched_before(), touch_core_sched_dispatch() re-stamps on every dispatch.

A comparison can see one stamp taken under each rule, which isn't a meaningful ordering. The dispatch rule also buys little - it only aligns bypass-mode comparisons with the local DSQ order. Multiple schedulers make the mixed comparisons more common.

Wait time is what p->scx.runnable_at already tracks for the stall watchdog. Delete core_sched_at with both touch functions and compare runnable_at in the scx_prio_less() fallback.

runnable_at is refreshed only on enqueue and goes stale while a task keeps occupying its CPU. Instead of re-stamping, order a running task after every waiting task as it is the most recently serviced.

---
 include/linux/sched/ext.h |   3 --
 kernel/sched/ext/ext.c    | 105 +++++++++-----------------------------
 2 files changed, 25 insertions(+), 83 deletions(-)
include/linux/sched/ext.h +0 -3
index a3ec980e2925..582d7cd4a983 100644
@@ -212,9 +212,6 @@ struct sched_ext_entity {
 	struct list_head	runnable_node;	/* rq->scx.runnable_list */
 	unsigned long		runnable_at;
 
-#ifdef CONFIG_SCHED_CORE
-	u64			core_sched_at;	/* see scx_prio_less() */
-#endif
 #ifdef CONFIG_EXT_SUB_SCHED
 	unsigned long		rescue_at;	/* queued on a rescue DSQ at, jiffies */
 #endif
kernel/sched/ext/ext.c +25 -80

181 lines not on this page · raw message

Signature · 1 line
2.55.0
author reviewer
#3 lore raw

PATCH 3/4 sched_ext: Make core-sched task ordering hierarchy-aware

In reply to Tejun Heo

With sub-schedulers, tasks of different schedulers routinely share rqs and SMT siblings, but scx_prio_less() consults ops.core_sched_before() only when both tasks belong to the same scheduler. Every pair spanning two schedulers falls back to the default ordering, so no scheduler can express ordering across a scheduler boundary, including a root over its sub-schedulers' tasks.

Order a pair spanning schedulers by the nearest common ancestor that implements ops.core_sched_before(): both tasks are in its subtree, making this the one op where a scheduler is called on tasks it delegated to its sub-schedulers and may not be scheduling anymore. Same-scheduler pairs keep using the owning scheduler's op so a parent never orders inside a subtree it delegated. The op is skipped when the deciding scheduler is bypassing on either task's CPU.

Update scx_qmap to fall back to the kernel's default ordering when handed a delegated task it has no task_ctx for.

---
 kernel/sched/ext/ext.c         | 38 +++++++++++++++++++++++++++-------
 kernel/sched/ext/internal.h    |  5 +++++
 tools/sched_ext/scx_qmap.bpf.c | 23 +++++++++++++-------
 3 files changed, 51 insertions(+), 15 deletions(-)
kernel/sched/ext/ext.c +30 -8
index 3df2e084d580..f14e3fc69644 100644
@@ -3459,10 +3459,16 @@ void ext_server_init(struct rq *rq)
  * usual sched_class'es and needs to find out the expected task ordering. For
  * SCX, core-sched calls this function to interrogate the task ordering.
  *
- * Unless overridden by ops.core_sched_before(), the default task ordering runs
- * the task which has been waiting longer first. A running task counts as the
- * most recently serviced and orders after every waiting task. Waiting tasks are
- * compared by @p->scx.runnable_at.
+ * A pair of tasks owned by one scheduler is ordered by the owner's
+ * ops.core_sched_before(). A pair spanning two schedulers is ordered by their
+ * nearest common ancestor which implements the op - the one case where the op
+ * is called on tasks that the scheduler delegated to its sub-schedulers and may
+ * not be scheduling anymore.
+ *
+ * When neither applies, or the deciding scheduler is bypassing on either task's
+ * CPU, the default ordering runs the task which has been waiting longer first.
+ * A running task counts as the most recently serviced and orders after every
+ * waiting task. Waiting tasks are compared by @p->scx.runnable_at.
  *
  * Return: %true if @a should run after @b.
  */
@@ -3471,8 +3477,26 @@ bool scx_prio_less(const struct task_struct *a, const struct task_struct *b,
 {
 	struct scx_sched *sch_a = scx_task_sched(a);
 	struct scx_sched *sch_b = scx_task_sched(b);
+	struct scx_sched *sch = NULL;
 	bool a_running, b_running;
 
+	if (sch_a == sch_b) {
+		if (SCX_HAS_OP(sch_a, core_sched_before))
+			sch = sch_a;
+	} else {
+		s32 level;
+
+		for (level = min(sch_a->level, sch_b->level); level >= 0; level--) {
+			struct scx_sched *anc = sch_a->ancestors[level];
+
+			if (anc == sch_b->ancestors[level] &&
+			    SCX_HAS_OP(anc, core_sched_before)) {
+				sch = anc;
+				break;
+			}
+		}
+	}
+
 	/*
 	 * scx_prio_less() returns whether @a should run after @b while
 	 * ops.core_sched_before() returns whether its first argument should run
@@ -3482,10 +3506,8 @@ bool scx_prio_less(const struct task_struct *a, const struct task_struct *b,
 	 * calling ops.core_sched_before(). Accesses are controlled by the
 	 * verifier.
 	 */
-	if (sch_a == sch_b && SCX_HAS_OP(sch_a, core_sched_before) &&
-	    !scx_bypassing(sch_a, task_cpu(a)))
-		return SCX_CALL_OP_2TASKS_RET(sch_a, core_sched_before,
-					      task_rq(a),
+	if (sch && !scx_bypassing(sch, task_cpu(a)) && !scx_bypassing(sch, task_cpu(b)))
+		return SCX_CALL_OP_2TASKS_RET(sch, core_sched_before, task_rq(a),
 					      (struct task_struct *)b,
 					      (struct task_struct *)a);
 
kernel/sched/ext/internal.h +5 -0
index c91296c53225..fa20cac3ab61 100644
@@ -521,6 +521,11 @@ struct sched_ext_ops {
 	 * the BPF scheduler. Should return %true if @a should run before @b.
 	 * %false if there's no required ordering or @b should run before @a.
 	 *
+	 * In a scheduler hierarchy, a pair spanning two schedulers is ordered
+	 * by the nearest common ancestor implementing this op, so the op may be
+	 * called on tasks that the scheduler delegated to its sub-schedulers
+	 * and is not scheduling anymore. See scx_prio_less().
+	 *
 	 * If not specified, the default is ordering them according to when they
 	 * became runnable.
 	 */
tools/sched_ext/scx_qmap.bpf.c +16 -7
index 723f45fe0cbc..a5f666716d80 100644
@@ -866,16 +866,11 @@ void BPF_STRUCT_OPS(qmap_tick, struct task_struct *p)
  * The distance from the head of the queue scaled by the weight of the queue.
  * The lower the number, the older the task and the higher the priority.
  */
-static s64 task_qdist(struct task_struct *p)
+static s64 task_qdist(struct task_struct *p, task_ctx_t *taskc)
 {
 	int idx = weight_to_idx(p->scx.weight);
-	task_ctx_t *taskc;
 	s64 qdist;
 
-	taskc = lookup_task_ctx(p);
-	if (!taskc)
-		return 0;
-
 	qdist = taskc->core_sched_seq - qa.core_sched_head_seqs[idx];
 
 	/*
@@ -900,7 +895,21 @@ static s64 task_qdist(struct task_struct *p)
 bool BPF_STRUCT_OPS(qmap_core_sched_before,
 		    struct task_struct *a, struct task_struct *b)
 {
-	return task_qdist(a) < task_qdist(b);
+	task_ctx_t *taskc_a = lookup_task_ctx(a);
+	task_ctx_t *taskc_b = lookup_task_ctx(b);
+
+	/*
+	 * A task delegated to a sub-scheduler has no task_ctx here. Order such
+	 * pairs by the kernel's default ordering - a running task after every
+	 * waiting task, then by runnable_at.
+	 */
+	if (!taskc_a || !taskc_b) {
+		if (a->on_cpu != b->on_cpu)
+			return b->on_cpu;
+		return time_before(a->scx.runnable_at, b->scx.runnable_at);
+	}
+
+	return task_qdist(a, taskc_a) < task_qdist(b, taskc_b);
 }
 
 /*
Signature · 1 line
2.55.0
author reviewer
#4 lore raw

PATCH 4/4 sched_ext: Drop the dead SCX_DEQ_CORE_SCHED_EXEC test in dequeue_task_scx()

In reply to Tejun Heo

dequeue_task_scx() masks SCX_DEQ_CORE_SCHED_EXEC out of the SCX_DEQ_SCHED_CHANGE decision, but the test can never fire: the incoming flags are an int of generic DEQUEUE_* bits while the flag is bit 32, and the core-sched execute path never goes through class dequeue anyway - set_next_task_scx() calls ops_dequeue() with the flag directly. The test was live when the SCX_DEQ_SCHED_CHANGE computation sat in ops_dequeue() and became dead when 03f5304aad0f ("sched_ext: Pass full dequeue flags to ops.quiescent()") moved the computation here. Drop it.

---
 kernel/sched/ext/ext.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
kernel/sched/ext/ext.c +2 -2
index f14e3fc69644..395d8f5aaaa8 100644
@@ -2267,9 +2267,9 @@ static bool dequeue_task_scx(struct rq *rq, struct task_struct *p, int core_deq_
 
 	/*
 	 * Set %SCX_DEQ_SCHED_CHANGE when the dequeue is due to a property
-	 * change (not sleep or core-sched pick).
+	 * change (not sleep).
 	 */
-	if (!(deq_flags & (DEQUEUE_SLEEP | SCX_DEQ_CORE_SCHED_EXEC)))
+	if (!(deq_flags & DEQUEUE_SLEEP))
 		deq_flags |= SCX_DEQ_SCHED_CHANGE;
 
 	if (!(p->scx.flags & SCX_TASK_QUEUED)) {
Signature · 1 line
2.55.0
author reviewer
#5 lore raw
In reply to Tejun Heo
Quoted 5 lines

Tejun Heo (4):
sched_ext: Fix inverted ops.core_sched_before() invocation
sched_ext: Use runnable_at for the default core-sched task ordering
sched_ext: Make core-sched task ordering hierarchy-aware
sched_ext: Drop the dead SCX_DEQ_CORE_SCHED_EXEC test in dequeue_task_scx()

Applied 1-4 to sched_ext/for-7.3. The patches are going in really quickly. They are plugging obvious holes in sub-scheduler support and I'd like to make it more or less complete before the merge window opens. The blast radius is also pretty limited. If there are any review points, I'll address them with followup patches.

Thanks.

--
tejun