Skip to contentSkip to conversation

sched_ext: Fix ops.dequeue() semantics

PATCH Superseded Andrea Righi 2 participants 5 messages Feb 4 – Feb 5

Subsystems (4)

v5 of 10 Superseded Latest is v10 →

lore
Share & tools
lore

Andrea Righi

author reviewer
#0 lore raw

PATCH v5 1/1 sched_ext: Fix ops.dequeue() semantics

The callback ops.dequeue() is provided to let BPF schedulers observe when a task leaves the scheduler, either because it is dispatched or due to a task property change. However, this callback is currently unreliable and not invoked systematically, which can result in missed ops.dequeue() events.

In particular, once a task is removed from the scheduler (whether for dispatch or due to a property change) the BPF scheduler loses visibility of the task and the sched_ext core may not always trigger ops.dequeue().

This breaks accurate accounting (i.e., per-DSQ queued runtime sums) and prevents reliable tracking of task lifecycle transitions.

This patch set fixes the semantics of ops.dequeue(), by guaranteeing that each task entering the BPF scheduler's custody triggers exactly one ops.dequeue() call when it leaves that custody, whether the exit is due to a dispatch (regular or via a core scheduling pick) or to a scheduling property change (e.g. sched_setaffinity(), sched_setscheduler(), set_user_nice(), NUMA balancing, etc.).

To identify property change dequeues a new ops.dequeue() flag is
introduced: %SCX_DEQ_SCHED_CHANGE.

Together, these changes allow BPF schedulers to reliably track task ownership and maintain accurate accounting.

Changes in v5:
- Introduce the concept of "terminal DSQ" (when a task is dispatched to a terminal DSQ, the task leaves the BPF scheduler's custody)
- Consider SCX_DSQ_GLOBAL as a terminal DSQ
- Link to v4: https://lore.kernel.org/all/[email protected]

Changes in v4:
- Introduce the concept of "BPF scheduler custody"
- Do not trigger ops.dequeue() for direct dispatches to local DSQs
- Trigger ops.dequeue() only once; after the task leaves BPF scheduler custody, further dequeue events are not reported.
- Link to v3: https://lore.kernel.org/all/[email protected]

Changes in v3:
- Rename SCX_DEQ_ASYNC to SCX_DEQ_SCHED_CHANGE
- Handle core-sched dequeues (Kuba)
- Link to v2: https://lore.kernel.org/all/[email protected]

Changes in v2:
- Distinguish between "dispatch" dequeues and "property change" dequeues (flag SCX_DEQ_ASYNC)
- Link to v1: https://lore.kernel.org/all/[email protected]

Andrea Righi (2):
sched_ext: Fix ops.dequeue() semantics selftests/sched_ext: Add test to validate ops.dequeue() semantics

 Documentation/scheduler/sched-ext.rst           |  74 +++++++
 include/linux/sched/ext.h                       |   1 +
 kernel/sched/ext.c                              | 186 +++++++++++++++-
 kernel/sched/ext_internal.h                     |   7 +
 tools/sched_ext/include/scx/enum_defs.autogen.h |   1 +
 tools/sched_ext/include/scx/enums.autogen.bpf.h |   2 +
 tools/sched_ext/include/scx/enums.autogen.h     |   1 +
 tools/testing/selftests/sched_ext/Makefile      |   1 +
 tools/testing/selftests/sched_ext/dequeue.bpf.c | 269 ++++++++++++++++++++++++
 tools/testing/selftests/sched_ext/dequeue.c     | 207 ++++++++++++++++++
 10 files changed, 746 insertions(+), 3 deletions(-)
 create mode 100644 tools/testing/selftests/sched_ext/dequeue.bpf.c
 create mode 100644 tools/testing/selftests/sched_ext/dequeue.c
author reviewer
#1 lore raw

PATCH 1/2 sched_ext: Fix ops.dequeue() semantics

Currently, ops.dequeue() is only invoked when the sched_ext core knows that a task resides in BPF-managed data structures, which causes it to miss scheduling property change events. In addition, ops.dequeue() callbacks are completely skipped when tasks are dispatched to non-local DSQs from ops.select_cpu(). As a result, BPF schedulers cannot reliably track task state.

Fix this by guaranteeing that each task entering the BPF scheduler's custody triggers exactly one ops.dequeue() call when it leaves that custody, whether the exit is due to a dispatch (regular or via a core scheduling pick) or to a scheduling property change (e.g. sched_setaffinity(), sched_setscheduler(), set_user_nice(), NUMA balancing, etc.).

BPF scheduler custody concept: a task is considered to be in "BPF scheduler's custody" when it has been queued in user-created DSQs and the BPF scheduler is responsible for its lifecycle. Custody ends when the task is dispatched to a terminal DSQ (local DSQ or SCX_DSQ_GLOBAL), selected by core scheduling, or removed due to a property change.

Tasks directly dispatched to terminal DSQs bypass the BPF scheduler entirely and are not in its custody. Terminal DSQs include:
- Local DSQs (%SCX_DSQ_LOCAL or %SCX_DSQ_LOCAL_ON): per-CPU queues where tasks go directly to execution.
- Global DSQ (%SCX_DSQ_GLOBAL): the built-in fallback queue where the BPF scheduler is considered "done" with the task.

As a result, ops.dequeue() is not invoked for tasks dispatched to terminal DSQs, as the BPF scheduler no longer retains custody of them.

To identify dequeues triggered by scheduling property changes, introduce the new ops.dequeue() flag %SCX_DEQ_SCHED_CHANGE: when this flag is set, the dequeue was caused by a scheduling property change.

New ops.dequeue() semantics:
- ops.dequeue() is invoked exactly once when the task leaves the BPF scheduler's custody, in one of the following cases:
a) regular dispatch: a task dispatched to a user DSQ is moved to a terminal DSQ (ops.dequeue() called without any special flags set),
b) core scheduling dispatch: core-sched picks task before dispatch, ops.dequeue() called with %SCX_DEQ_CORE_SCHED_EXEC flag set,
c) property change: task properties modified before dispatch, ops.dequeue() called with %SCX_DEQ_SCHED_CHANGE flag set.

This allows BPF schedulers to:
- reliably track task ownership and lifecycle,
- maintain accurate accounting of managed tasks,
- update internal state when tasks change properties.

Cc Tejun Heo <[email protected]>
Cc Emil Tsalapatis <[email protected]>
Cc Kuba Piecuch <[email protected]>
---
 Documentation/scheduler/sched-ext.rst         |  74 +++++++
 include/linux/sched/ext.h                     |   1 +
 kernel/sched/ext.c                            | 186 +++++++++++++++++-
 kernel/sched/ext_internal.h                   |   7 +
 .../sched_ext/include/scx/enum_defs.autogen.h |   1 +
 .../sched_ext/include/scx/enums.autogen.bpf.h |   2 +
 tools/sched_ext/include/scx/enums.autogen.h   |   1 +
 7 files changed, 269 insertions(+), 3 deletions(-)
Documentation/scheduler/sched-ext.rst +74 -0
index 404fe6126a769..1457f2aefa93e 100644
@@ -252,6 +252,78 @@ The following briefly shows how a waking task is scheduled and executed.
 
    * Queue the task on the BPF side.
 
+   **Task State Tracking and ops.dequeue() Semantics**
+
+   Once ``ops.select_cpu()`` or ``ops.enqueue()`` is called, the task may
+   enter the "BPF scheduler's custody" depending on where it's dispatched:
+
+   * **Direct dispatch to terminal DSQs** (``SCX_DSQ_LOCAL``,
+     ``SCX_DSQ_LOCAL_ON | cpu``, or ``SCX_DSQ_GLOBAL``): The BPF scheduler
+     is done with the task - it either goes straight to a CPU's local run
+     queue or to the global DSQ as a fallback. The task never enters (or
+     exits) BPF custody, and ``ops.dequeue()`` will not be called.
+
+   * **Dispatch to user-created DSQs** (custom DSQs): the task enters the
+     BPF scheduler's custody. When the task later leaves BPF custody
+     (dispatched to a terminal DSQ, picked by core-sched, or dequeued for
+     sleep/property changes), ``ops.dequeue()`` will be called exactly once.
+
+   * **Queued on BPF side**: The task is in BPF data structures and in BPF
+     custody, ``ops.dequeue()`` will be called when it leaves.
+
+   The key principle: **ops.dequeue() is called when a task leaves the BPF
+   scheduler's custody**.
+
+   This works also with the ``ops.select_cpu()`` direct dispatch
+   optimization: even though it skips ``ops.enqueue()`` invocation, if the
+   task is dispatched to a user-created DSQ, it enters BPF custody and will
+   get ``ops.dequeue()`` when it leaves. If dispatched to a terminal DSQ,
+   the BPF scheduler is done with it immediately. This provides the
+   performance benefit of avoiding the ``ops.enqueue()`` roundtrip while
+   maintaining correct state tracking.
+
+   The dequeue can happen for different reasons, distinguished by flags:
+
+   1. **Regular dispatch workflow**: when the task is dispatched from a
+      user-created DSQ to a terminal DSQ (leaving BPF custody for execution),
+      ``ops.dequeue()`` is triggered without any special flags.
+
+   2. **Core scheduling pick**: when ``CONFIG_SCHED_CORE`` is enabled and
+      core scheduling picks a task for execution while it's still in BPF
+      custody, ``ops.dequeue()`` is called with the
+      ``SCX_DEQ_CORE_SCHED_EXEC`` flag.
+
+   3. **Scheduling property change**: when a task property changes (via
+      operations like ``sched_setaffinity()``, ``sched_setscheduler()``,
+      priority changes, CPU migrations, etc.) while the task is still in
+      BPF custody, ``ops.dequeue()`` is called with the
+      ``SCX_DEQ_SCHED_CHANGE`` flag set in ``deq_flags``.
+
+   **Important**: Once a task has left BPF custody (dispatched to a
+   terminal DSQ), property changes will not trigger ``ops.dequeue()``,
+   since the task is no longer being managed by the BPF scheduler.
+
+   **Property Change Notifications for Running Tasks**:
+
+   For tasks that have left BPF custody (running or on terminal DSQs),
+   property changes can be intercepted through the dedicated callbacks:
+
+   * ``ops.set_cpumask()``: Called when a task's CPU affinity changes
+     (e.g., via ``sched_setaffinity()``). This callback is invoked for
+     all tasks regardless of their state or BPF custody.
+
+   * ``ops.set_weight()``: Called when a task's scheduling weight/priority
+     changes (e.g., via ``sched_setscheduler()`` or ``set_user_nice()``).
+     This callback is also invoked for all tasks.
+
+   These callbacks provide complete coverage for property changes,
+   complementing ``ops.dequeue()`` which only applies to tasks in BPF
+   custody.
+
+   BPF schedulers can choose not to implement ``ops.dequeue()`` if they
+   don't need to track these transitions. The sched_ext core will safely
+   handle all dequeue operations regardless.
+
 3. When a CPU is ready to schedule, it first looks at its local DSQ. If
    empty, it then looks at the global DSQ. If there still isn't a task to
    run, ``ops.dispatch()`` is invoked which can use the following two
@@ -319,6 +391,8 @@ by a sched_ext scheduler:
                 /* Any usable CPU becomes available */
 
                 ops.dispatch(); /* Task is moved to a local DSQ */
+
+                ops.dequeue(); /* Exiting BPF scheduler */
             }
             ops.running();      /* Task starts running on its assigned CPU */
             while (task->scx.slice > 0 && task is runnable)
include/linux/sched/ext.h +1 -0
index bcb962d5ee7d8..8d7c13e75efec 100644
@@ -84,6 +84,7 @@ struct scx_dispatch_q {
 /* scx_entity.flags */
 enum scx_ent_flags {
 	SCX_TASK_QUEUED		= 1 << 0, /* on ext runqueue */
+	SCX_TASK_OPS_ENQUEUED	= 1 << 1, /* in BPF scheduler's custody */
 	SCX_TASK_RESET_RUNNABLE_AT = 1 << 2, /* runnable_at should be reset */
 	SCX_TASK_DEQD_FOR_SLEEP	= 1 << 3, /* last dequeue was for SLEEP */
 
kernel/sched/ext.c +183 -3

252 lines not on this page · raw message

kernel/sched/ext_internal.h +7 -0
index 386c677e4c9a0..befa9a5d6e53f 100644
@@ -982,6 +982,13 @@ enum scx_deq_flags {
 	 * it hasn't been dispatched yet. Dequeue from the BPF side.
 	 */
 	SCX_DEQ_CORE_SCHED_EXEC	= 1LLU << 32,
+
+	/*
+	 * The task is being dequeued due to a property change (e.g.,
+	 * sched_setaffinity(), sched_setscheduler(), set_user_nice(),
+	 * etc.).
+	 */
+	SCX_DEQ_SCHED_CHANGE	= 1LLU << 33,
 };
 
 enum scx_pick_idle_cpu_flags {
tools/sched_ext/include/scx/enum_defs.autogen.h +1 -0
index c2c33df9292c2..dcc945304760f 100644
@@ -21,6 +21,7 @@
 #define HAVE_SCX_CPU_PREEMPT_UNKNOWN
 #define HAVE_SCX_DEQ_SLEEP
 #define HAVE_SCX_DEQ_CORE_SCHED_EXEC
+#define HAVE_SCX_DEQ_SCHED_CHANGE
 #define HAVE_SCX_DSQ_FLAG_BUILTIN
 #define HAVE_SCX_DSQ_FLAG_LOCAL_ON
 #define HAVE_SCX_DSQ_INVALID
tools/sched_ext/include/scx/enums.autogen.bpf.h +2 -0
index 2f8002bcc19ad..5da50f9376844 100644
@@ -127,3 +127,5 @@ const volatile u64 __SCX_ENQ_CLEAR_OPSS __weak;
 const volatile u64 __SCX_ENQ_DSQ_PRIQ __weak;
 #define SCX_ENQ_DSQ_PRIQ __SCX_ENQ_DSQ_PRIQ
 
+const volatile u64 __SCX_DEQ_SCHED_CHANGE __weak;
+#define SCX_DEQ_SCHED_CHANGE __SCX_DEQ_SCHED_CHANGE
tools/sched_ext/include/scx/enums.autogen.h +1 -0
index fedec938584be..fc9a7a4d9dea5 100644
@@ -46,4 +46,5 @@
 	SCX_ENUM_SET(skel, scx_enq_flags, SCX_ENQ_LAST); \
 	SCX_ENUM_SET(skel, scx_enq_flags, SCX_ENQ_CLEAR_OPSS); \
 	SCX_ENUM_SET(skel, scx_enq_flags, SCX_ENQ_DSQ_PRIQ); \
+	SCX_ENUM_SET(skel, scx_deq_flags, SCX_DEQ_SCHED_CHANGE); \
 } while (0)
Signature · 1 line
2.53.0
reviewer
#2 lore raw

Hello,

Quoted 34 lines · Andrea Righi

Currently, ops.dequeue() is only invoked when the sched_ext core knows that a task resides in BPF-managed data structures, which causes it to miss scheduling property change events. In addition, ops.dequeue() callbacks are completely skipped when tasks are dispatched to non-local DSQs from ops.select_cpu(). As a result, BPF schedulers cannot reliably track task state.

Fix this by guaranteeing that each task entering the BPF scheduler's custody triggers exactly one ops.dequeue() call when it leaves that custody, whether the exit is due to a dispatch (regular or via a core scheduling pick) or to a scheduling property change (e.g. sched_setaffinity(), sched_setscheduler(), set_user_nice(), NUMA balancing, etc.).

BPF scheduler custody concept: a task is considered to be in "BPF scheduler's custody" when it has been queued in user-created DSQs and the BPF scheduler is responsible for its lifecycle. Custody ends when the task is dispatched to a terminal DSQ (local DSQ or SCX_DSQ_GLOBAL), selected by core scheduling, or removed due to a property change.

Tasks directly dispatched to terminal DSQs bypass the BPF scheduler entirely and are not in its custody. Terminal DSQs include:
- Local DSQs (%SCX_DSQ_LOCAL or %SCX_DSQ_LOCAL_ON): per-CPU queues where tasks go directly to execution.
- Global DSQ (%SCX_DSQ_GLOBAL): the built-in fallback queue where the BPF scheduler is considered "done" with the task.

As a result, ops.dequeue() is not invoked for tasks dispatched to terminal DSQs, as the BPF scheduler no longer retains custody of them.

To identify dequeues triggered by scheduling property changes, introduce the new ops.dequeue() flag %SCX_DEQ_SCHED_CHANGE: when this flag is set, the dequeue was caused by a scheduling property change.

...

Documentation/scheduler/sched-ext.rst The following briefly shows how a waking task is scheduled and executed. · line 309

Quoted 4 lines
Documentation/scheduler/sched-ext.rst +4 -0
+   **Property Change Notifications for Running Tasks**:
+
+   For tasks that have left BPF custody (running or on terminal DSQs),
+   property changes can be intercepted through the dedicated callbacks:

I'm not sure this section is necessary. The way it's phrased makes it sound like schedulers would use DEQ_SCHED_CHANGE to process property changes but that's not the case. Relevant property changes will be notified in whatever ways they're notified and a task being dequeued for SCHED_CHANGE doesn't necessarily mean there will be an associated property change event either. e.g. We don't do anything re. on sched_setnuma().

Quoted 5 lines
kernel/sched/ext.c +1 -0
@@ -1102,6 +1122,18 @@ static void dispatch_enqueue(struct scx_sched *sch, struct scx_dispatch_q *dsq,
 	dsq_mod_nr(dsq, 1);
 	p->scx.dsq = dsq;
 
+	/*

kernel/sched/ext.c static void dispatch_enqueue(struct scx_sched *sch, struct scx_dispatch_q *dsq, · line 1135

Quoted 10 lines
kernel/sched/ext.c +10 -0
+	 * Mark task as in BPF scheduler's custody if being queued to a
+	 * non-builtin (user) DSQ. Builtin DSQs (local, global, bypass) are
+	 * terminal: tasks on them have left BPF custody.
+	 *
+	 * Don't touch the flag if already set (e.g., by
+	 * mark_direct_dispatch() or direct_dispatch()/finish_dispatch()
+	 * for user DSQs).
+	 */
+	if (SCX_HAS_OP(sch, dequeue) && !(dsq->id & SCX_DSQ_FLAG_BUILTIN))
+		p->scx.flags |= SCX_TASK_OPS_ENQUEUED;

given that this is tied to dequeue, maybe a more direct name would be less confusing? e.g. something like SCX_TASK_NEED_DEQ?

Quoted 12 lines
kernel/sched/ext.c +8 -0
@@ -1274,6 +1306,24 @@ static void mark_direct_dispatch(struct scx_sched *sch,
 
 	p->scx.ddsp_dsq_id = dsq_id;
 	p->scx.ddsp_enq_flags = enq_flags;
+
+	/*
+	 * Mark the task as entering BPF scheduler's custody if it's being
+	 * dispatched to a non-terminal DSQ (i.e., custom user DSQs). This
+	 * handles the case where ops.select_cpu() directly dispatches - even
+	 * though ops.enqueue() won't be called, the task enters BPF custody
+	 * if dispatched to a user DSQ and should get ops.dequeue() when it
+	 * leaves.

kernel/sched/ext.c static void mark_direct_dispatch(struct scx_sched *sch, · line 1326

Quoted 10 lines
kernel/sched/ext.c +10 -0
+	 *
+	 * For terminal DSQs (local DSQs and SCX_DSQ_GLOBAL), ensure the flag
+	 * is clear since the BPF scheduler is done with the task.
+	 */
+	if (SCX_HAS_OP(sch, dequeue)) {
+		if (!is_terminal_dsq(dsq_id))
+			p->scx.flags |= SCX_TASK_OPS_ENQUEUED;
+		else
+			p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED;
+	}

Hmm... I'm a bit confused on why this needs to be in mark_direct_dispatch() AND dispatch_enqueue(). The flag should be clear when off SCX. The only places where it could be set is from the enqueue path - when a task is direct dispatched to a non-terminal DSQ or BPF. Both cases can be reliably captured in do_enqueue_task(), no?

Quoted 2 lines
kernel/sched/ext.c +0 -0
 static void direct_dispatch(struct scx_sched *sch, struct task_struct *p,
@@ -1287,6 +1337,41 @@ static void direct_dispatch(struct scx_sched *sch, struct task_struct *p,

...

kernel/sched/ext.c static void direct_dispatch(struct scx_sched *sch, struct task_struct *p, · line 1373

Quoted 9 lines
kernel/sched/ext.c +9 -0
+	if (SCX_HAS_OP(sch, dequeue)) {
+		if (!is_terminal_dsq(dsq->id)) {
+			p->scx.flags |= SCX_TASK_OPS_ENQUEUED;
+		} else {
+			if (p->scx.flags & SCX_TASK_OPS_ENQUEUED)
+				SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq, p, 0);
+			p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED;
+		}
+	}

And when would direct_dispatch() need to call ops.dequeue()? direct_dispatch() is only used from do_enqueue_task() and there can only be one direct dispatch attempt on any given enqueue event. A task being enqueued shouldn't have the OPS_ENQUEUED set and would get dispatched once to either a terminal or non-terminal DSQ. If terminal, there's nothing to do. If non-terminal, the flag would need to be set. Am I missing something?

Quoted 1 line
(quoted diff) +0 -0
@@ -1523,6 +1608,31 @@ static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags)

...

kernel/sched/ext.c static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags) · line 1627

Quoted 2 lines
kernel/sched/ext.c +2 -0
+		if (SCX_HAS_OP(sch, dequeue) &&
+		    p->scx.flags & SCX_TASK_OPS_ENQUEUED) {

nit: () around & expression.

Quoted 25 lines
kernel/sched/ext.c +15 -3
+			u64 flags = deq_flags;
+
+			if (!(deq_flags & (DEQUEUE_SLEEP | SCX_DEQ_CORE_SCHED_EXEC)))
+				flags |= SCX_DEQ_SCHED_CHANGE;
+
+			SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq, p, flags);
+			p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED;
+		}
 		break;
 	case SCX_OPSS_QUEUEING:
 		/*
@@ -1531,9 +1641,24 @@ static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags)
 		 */
 		BUG();
 	case SCX_OPSS_QUEUED:
-		if (SCX_HAS_OP(sch, dequeue))
-			SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq,
-					 p, deq_flags);
+		/*
+		 * Task is still on the BPF scheduler (not dispatched yet).
+		 * Call ops.dequeue() to notify. Add %SCX_DEQ_SCHED_CHANGE
+		 * only for property changes, not for core-sched picks or
+		 * sleep.
+		 *
+		 * Clear the flag after calling ops.dequeue(): the task is

kernel/sched/ext.c static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags) · line 1660

Quoted 10 lines
kernel/sched/ext.c +10 -0
+		 * leaving BPF scheduler's custody.
+		 */
+		if (SCX_HAS_OP(sch, dequeue)) {
+			u64 flags = deq_flags;
+
+			if (!(deq_flags & (DEQUEUE_SLEEP | SCX_DEQ_CORE_SCHED_EXEC)))
+				flags |= SCX_DEQ_SCHED_CHANGE;
+
+			SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq, p, flags);
+			p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED;

I wonder whether this and the above block can be factored somehow.

Quoted 32 lines
kernel/sched/ext.c +14 -0
@@ -1630,6 +1755,7 @@ static void move_local_task_to_local_dsq(struct task_struct *p, u64 enq_flags,
 					 struct scx_dispatch_q *src_dsq,
 					 struct rq *dst_rq)
 {
+	struct scx_sched *sch = scx_root;
 	struct scx_dispatch_q *dst_dsq = &dst_rq->scx.local_dsq;
 
 	/* @dsq is locked and @p is on @dst_rq */
@@ -1638,6 +1764,15 @@ static void move_local_task_to_local_dsq(struct task_struct *p, u64 enq_flags,
 
 	WARN_ON_ONCE(p->scx.holding_cpu >= 0);
 
+	/*
+	 * Task is moving from a non-local DSQ to a local DSQ. Call
+	 * ops.dequeue() if the task was in BPF custody.
+	 */
+	if (SCX_HAS_OP(sch, dequeue) && (p->scx.flags & SCX_TASK_OPS_ENQUEUED)) {
+		SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, dst_rq, p, 0);
+		p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED;
+	}
+
 	if (enq_flags & (SCX_ENQ_HEAD | SCX_ENQ_PREEMPT))
 		list_add(&p->scx.dsq_list.node, &dst_dsq->list);
 	else
@@ -2107,6 +2242,36 @@ static void finish_dispatch(struct scx_sched *sch, struct rq *rq,
 
 	BUG_ON(!(p->scx.flags & SCX_TASK_QUEUED));
 
+	/*
+	 * Handle ops.dequeue() based on destination DSQ.
+	 *
+	 * Dispatch to terminal DSQs (local DSQs and SCX_DSQ_GLOBAL): the BPF

kernel/sched/ext.c static void finish_dispatch(struct scx_sched *sch, struct rq *rq, · line 2258

Quoted 10 lines
kernel/sched/ext.c +10 -0
+	 * scheduler is done with the task. Call ops.dequeue() if it was in
+	 * BPF custody, then clear the %SCX_TASK_OPS_ENQUEUED flag.
+	 *
+	 * Dispatch to user DSQs: task is in BPF scheduler's custody.
+	 * Mark it so ops.dequeue() will be called when it leaves.
+	 */
+	if (SCX_HAS_OP(sch, dequeue)) {
+		if (!is_terminal_dsq(dsq_id)) {
+			p->scx.flags |= SCX_TASK_OPS_ENQUEUED;
+		} else {

Let's do "if (COND) { A } else { B }" instead of "if (!COND) { B } else { A }". Continuing from earlier, I don't understand why we'd need to set OPS_ENQUEUED here. Given that a transition to a terminal DSQ is terminal, I can't think of conditions where we'd need to set OPS_ENQUEUED from ops.dispatch().

Quoted 5 lines
kernel/sched/ext.c +5 -0
+			/*
+			 * Locking: we're holding the @rq lock (the
+			 * dispatch CPU's rq), but not necessarily
+			 * task_rq(p), since @p may be from a remote CPU.
+			 *

kernel/sched/ext.c static void finish_dispatch(struct scx_sched *sch, struct rq *rq, · line 2273

Quoted 10 lines
kernel/sched/ext.c +10 -0
+			 * This is safe because SCX_OPSS_DISPATCHING state
+			 * prevents racing dequeues, any concurrent
+			 * ops_dequeue() will wait for this state to clear.
+			 */
+			if (p->scx.flags & SCX_TASK_OPS_ENQUEUED)
+				SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq, p, 0);
+
+			p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED;
+		}
+	}

I'm not sure finish_dispatch() is the right place to do this. e.g. scx_bpf_dsq_move() can also move tasks from a user DSQ to a terminal DSQ and the above wouldn't cover it. Wouldn't it make more sense to do this in dispatch_enqueue()?

Quoted 16 lines
kernel/sched/ext.c +8 -0
@@ -2894,6 +3059,14 @@ static void scx_enable_task(struct task_struct *p)
 
 	lockdep_assert_rq_held(rq);
 
+	/*
+	 * Clear enqueue/dequeue tracking flags when enabling the task.
+	 * This ensures a clean state when the task enters SCX. Only needed
+	 * if ops.dequeue() is implemented.
+	 */
+	if (SCX_HAS_OP(sch, dequeue))
+		p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED;
+
 	/*
 	 * Set the weight before calling ops.enable() so that the scheduler
 	 * doesn't see a stale value if they inspect the task struct.

kernel/sched/ext.c static void scx_disable_task(struct task_struct *p) · line 3107

Quoted 10 lines
kernel/sched/ext.c +7 -0
@@ -2925,6 +3098,13 @@ static void scx_disable_task(struct task_struct *p)
 	if (SCX_HAS_OP(sch, disable))
 		SCX_CALL_OP_TASK(sch, SCX_KF_REST, disable, rq, p);
 	scx_set_task_state(p, SCX_TASK_READY);
+
+	/*
+	 * Clear enqueue/dequeue tracking flags when disabling the task.
+	 * Only needed if ops.dequeue() is implemented.
+	 */
+	if (SCX_HAS_OP(sch, dequeue))
+		p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED;

If we make the flag transitions consistent, we shouldn't need these, right? We can add WARN_ON_ONCE() at the head of enqueue maybe.

Thanks.

Signature · 1 line
tejun
author reviewer
#3 lore raw

Hi Tejun,

Quoted 43 lines · Tejun Heo

Hello,

Quoted 34 lines · Andrea Righi

Currently, ops.dequeue() is only invoked when the sched_ext core knows that a task resides in BPF-managed data structures, which causes it to miss scheduling property change events. In addition, ops.dequeue() callbacks are completely skipped when tasks are dispatched to non-local DSQs from ops.select_cpu(). As a result, BPF schedulers cannot reliably track task state.

Fix this by guaranteeing that each task entering the BPF scheduler's custody triggers exactly one ops.dequeue() call when it leaves that custody, whether the exit is due to a dispatch (regular or via a core scheduling pick) or to a scheduling property change (e.g. sched_setaffinity(), sched_setscheduler(), set_user_nice(), NUMA balancing, etc.).

BPF scheduler custody concept: a task is considered to be in "BPF scheduler's custody" when it has been queued in user-created DSQs and the BPF scheduler is responsible for its lifecycle. Custody ends when the task is dispatched to a terminal DSQ (local DSQ or SCX_DSQ_GLOBAL), selected by core scheduling, or removed due to a property change.

Tasks directly dispatched to terminal DSQs bypass the BPF scheduler entirely and are not in its custody. Terminal DSQs include:
- Local DSQs (%SCX_DSQ_LOCAL or %SCX_DSQ_LOCAL_ON): per-CPU queues where tasks go directly to execution.
- Global DSQ (%SCX_DSQ_GLOBAL): the built-in fallback queue where the BPF scheduler is considered "done" with the task.

As a result, ops.dequeue() is not invoked for tasks dispatched to terminal DSQs, as the BPF scheduler no longer retains custody of them.

To identify dequeues triggered by scheduling property changes, introduce the new ops.dequeue() flag %SCX_DEQ_SCHED_CHANGE: when this flag is set, the dequeue was caused by a scheduling property change.

...

Documentation/scheduler/sched-ext.rst The following briefly shows how a waking task is scheduled and executed. · line 309

Quoted 4 lines
Documentation/scheduler/sched-ext.rst +4 -0
+   **Property Change Notifications for Running Tasks**:
+
+   For tasks that have left BPF custody (running or on terminal DSQs),
+   property changes can be intercepted through the dedicated callbacks:
Quoted 6 lines

I'm not sure this section is necessary. The way it's phrased makes it sound like schedulers would use DEQ_SCHED_CHANGE to process property changes but that's not the case. Relevant property changes will be notified in whatever ways they're notified and a task being dequeued for SCHED_CHANGE doesn't necessarily mean there will be an associated property change event either. e.g. We don't do anything re. on sched_setnuma().

Agreed, this section is a bit misleading, DEQ_SCHED_CHANGE is an informational flag indicating the ops.dequeue() wasn't due to dispatch, schedulers shouldn't use it to process property changes. I'll remove it.

Quoted 5 lines
Quoted 5 lines
kernel/sched/ext.c +0 -0
@@ -1102,6 +1122,18 @@ static void dispatch_enqueue(struct scx_sched *sch, struct scx_dispatch_q *dsq,
 	dsq_mod_nr(dsq, 1);
 	p->scx.dsq = dsq;
 
Quoted 14 lines

kernel/sched/ext.c static void dispatch_enqueue(struct scx_sched *sch, struct scx_dispatch_q *dsq, · line 1135

Quoted 11 lines
kernel/sched/ext.c +11 -0
+	/*
+	 * Mark task as in BPF scheduler's custody if being queued to a
+	 * non-builtin (user) DSQ. Builtin DSQs (local, global, bypass) are
+	 * terminal: tasks on them have left BPF custody.
+	 *
+	 * Don't touch the flag if already set (e.g., by
+	 * mark_direct_dispatch() or direct_dispatch()/finish_dispatch()
+	 * for user DSQs).
+	 */
+	if (SCX_HAS_OP(sch, dequeue) && !(dsq->id & SCX_DSQ_FLAG_BUILTIN))
+		p->scx.flags |= SCX_TASK_OPS_ENQUEUED;

given that this is tied to dequeue, maybe a more direct name would be less confusing? e.g. something like SCX_TASK_NEED_DEQ?

Ack.

Quoted 21 lines
Quoted 21 lines
kernel/sched/ext.c +16 -0
@@ -1274,6 +1306,24 @@ static void mark_direct_dispatch(struct scx_sched *sch,
 
 	p->scx.ddsp_dsq_id = dsq_id;
 	p->scx.ddsp_enq_flags = enq_flags;
+
+	/*
+	 * Mark the task as entering BPF scheduler's custody if it's being
+	 * dispatched to a non-terminal DSQ (i.e., custom user DSQs). This
+	 * handles the case where ops.select_cpu() directly dispatches - even
+	 * though ops.enqueue() won't be called, the task enters BPF custody
+	 * if dispatched to a user DSQ and should get ops.dequeue() when it
+	 * leaves.
+	 *
+	 * For terminal DSQs (local DSQs and SCX_DSQ_GLOBAL), ensure the flag
+	 * is clear since the BPF scheduler is done with the task.
+	 */
+	if (SCX_HAS_OP(sch, dequeue)) {
+		if (!is_terminal_dsq(dsq_id))
+			p->scx.flags |= SCX_TASK_OPS_ENQUEUED;
+		else
Quoted 8 lines

Review static void mark_direct_dispatch(struct scx_sched *sch, · line 1326

Quoted 2 lines
(quoted diff) +2 -0
+			p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED;
+	}

Hmm... I'm a bit confused on why this needs to be in mark_direct_dispatch() AND dispatch_enqueue(). The flag should be clear when off SCX. The only places where it could be set is from the enqueue path - when a task is direct dispatched to a non-terminal DSQ or BPF. Both cases can be reliably captured in do_enqueue_task(), no?

You're right. I was incorrectly assuming we needed this in mark_direct_dispatch() to catch direct dispatches to user DSQs from ops.select_cpu(), but that's not true. All paths go through do_enqueue_task() which funnels to dispatch_enqueue(), so we can handle it all in one place.

Quoted 4 lines
Quoted 3 lines
kernel/sched/ext.c +0 -0
 static void direct_dispatch(struct scx_sched *sch, struct task_struct *p,
@@ -1287,6 +1337,41 @@ static void direct_dispatch(struct scx_sched *sch, struct task_struct *p,

...

Quoted 16 lines

kernel/sched/ext.c static void direct_dispatch(struct scx_sched *sch, struct task_struct *p, · line 1373

Quoted 9 lines
kernel/sched/ext.c +9 -0
+	if (SCX_HAS_OP(sch, dequeue)) {
+		if (!is_terminal_dsq(dsq->id)) {
+			p->scx.flags |= SCX_TASK_OPS_ENQUEUED;
+		} else {
+			if (p->scx.flags & SCX_TASK_OPS_ENQUEUED)
+				SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq, p, 0);
+			p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED;
+		}
+	}

And when would direct_dispatch() need to call ops.dequeue()? direct_dispatch() is only used from do_enqueue_task() and there can only be one direct dispatch attempt on any given enqueue event. A task being enqueued shouldn't have the OPS_ENQUEUED set and would get dispatched once to either a terminal or non-terminal DSQ. If terminal, there's nothing to do. If non-terminal, the flag would need to be set. Am I missing something?

Nah, you're right, direct_dispatch() doesn't need to call ops.dequeue() or manage the flag. I'll remove all the flag management from direct_dispatch() and centralize it in dispatch_enqueue().

Quoted 37 lines
Quoted 2 lines
(quoted diff) +0 -0
@@ -1523,6 +1608,31 @@ static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags)

...

kernel/sched/ext.c static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags) · line 1627

Quoted 2 lines
kernel/sched/ext.c +2 -0
+		if (SCX_HAS_OP(sch, dequeue) &&
+		    p->scx.flags & SCX_TASK_OPS_ENQUEUED) {

nit: () around & expression.

Quoted 29 lines
kernel/sched/ext.c +19 -3
+			u64 flags = deq_flags;
+
+			if (!(deq_flags & (DEQUEUE_SLEEP | SCX_DEQ_CORE_SCHED_EXEC)))
+				flags |= SCX_DEQ_SCHED_CHANGE;
+
+			SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq, p, flags);
+			p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED;
+		}
 		break;
 	case SCX_OPSS_QUEUEING:
 		/*
@@ -1531,9 +1641,24 @@ static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags)
 		 */
 		BUG();
 	case SCX_OPSS_QUEUED:
-		if (SCX_HAS_OP(sch, dequeue))
-			SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq,
-					 p, deq_flags);
+		/*
+		 * Task is still on the BPF scheduler (not dispatched yet).
+		 * Call ops.dequeue() to notify. Add %SCX_DEQ_SCHED_CHANGE
+		 * only for property changes, not for core-sched picks or
+		 * sleep.
+		 *
+		 * Clear the flag after calling ops.dequeue(): the task is
+		 * leaving BPF scheduler's custody.
+		 */
+		if (SCX_HAS_OP(sch, dequeue)) {
+			u64 flags = deq_flags;
Quoted 8 lines

kernel/sched/ext.c static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags) · line 1634

Quoted 6 lines
kernel/sched/ext.c +6 -0
+
+			if (!(deq_flags & (DEQUEUE_SLEEP | SCX_DEQ_CORE_SCHED_EXEC)))
+				flags |= SCX_DEQ_SCHED_CHANGE;
+
+			SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq, p, flags);
+			p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED;

I wonder whether this and the above block can be factored somehow.

Ack, we can add a helper for this.

Quoted 41 lines
Quoted 41 lines
kernel/sched/ext.c +22 -0
@@ -1630,6 +1755,7 @@ static void move_local_task_to_local_dsq(struct task_struct *p, u64 enq_flags,
 					 struct scx_dispatch_q *src_dsq,
 					 struct rq *dst_rq)
 {
+	struct scx_sched *sch = scx_root;
 	struct scx_dispatch_q *dst_dsq = &dst_rq->scx.local_dsq;
 
 	/* @dsq is locked and @p is on @dst_rq */
@@ -1638,6 +1764,15 @@ static void move_local_task_to_local_dsq(struct task_struct *p, u64 enq_flags,
 
 	WARN_ON_ONCE(p->scx.holding_cpu >= 0);
 
+	/*
+	 * Task is moving from a non-local DSQ to a local DSQ. Call
+	 * ops.dequeue() if the task was in BPF custody.
+	 */
+	if (SCX_HAS_OP(sch, dequeue) && (p->scx.flags & SCX_TASK_OPS_ENQUEUED)) {
+		SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, dst_rq, p, 0);
+		p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED;
+	}
+
 	if (enq_flags & (SCX_ENQ_HEAD | SCX_ENQ_PREEMPT))
 		list_add(&p->scx.dsq_list.node, &dst_dsq->list);
 	else
@@ -2107,6 +2242,36 @@ static void finish_dispatch(struct scx_sched *sch, struct rq *rq,
 
 	BUG_ON(!(p->scx.flags & SCX_TASK_QUEUED));
 
+	/*
+	 * Handle ops.dequeue() based on destination DSQ.
+	 *
+	 * Dispatch to terminal DSQs (local DSQs and SCX_DSQ_GLOBAL): the BPF
+	 * scheduler is done with the task. Call ops.dequeue() if it was in
+	 * BPF custody, then clear the %SCX_TASK_OPS_ENQUEUED flag.
+	 *
+	 * Dispatch to user DSQs: task is in BPF scheduler's custody.
+	 * Mark it so ops.dequeue() will be called when it leaves.
+	 */
+	if (SCX_HAS_OP(sch, dequeue)) {
+		if (!is_terminal_dsq(dsq_id)) {
Quoted 8 lines

Review static void finish_dispatch(struct scx_sched *sch, struct rq *rq, · line 2258

Quoted 2 lines
(quoted diff) +2 -0
+			p->scx.flags |= SCX_TASK_OPS_ENQUEUED;
+		} else {

Let's do "if (COND) { A } else { B }" instead of "if (!COND) { B } else { A }". Continuing from earlier, I don't understand why we'd need to set OPS_ENQUEUED here. Given that a transition to a terminal DSQ is terminal, I can't think of conditions where we'd need to set OPS_ENQUEUED from ops.dispatch().

Right, a task that reaches ops.dispatch() is already in QUEUED state, if it's in a user DSQ the flag is already set from when it was enqueued, so there's no need to set the flag in finish_dispatch().

Quoted 13 lines
Quoted 13 lines
kernel/sched/ext.c +12 -0
+			/*
+			 * Locking: we're holding the @rq lock (the
+			 * dispatch CPU's rq), but not necessarily
+			 * task_rq(p), since @p may be from a remote CPU.
+			 *
+			 * This is safe because SCX_OPSS_DISPATCHING state
+			 * prevents racing dequeues, any concurrent
+			 * ops_dequeue() will wait for this state to clear.
+			 */
+			if (p->scx.flags & SCX_TASK_OPS_ENQUEUED)
+				SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq, p, 0);
+
Quoted 8 lines

kernel/sched/ext.c static void direct_dispatch(struct scx_sched *sch, struct task_struct *p, · line 1373

Quoted 3 lines
kernel/sched/ext.c +3 -0
+			p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED;
+		}
+	}

I'm not sure finish_dispatch() is the right place to do this. e.g. scx_bpf_dsq_move() can also move tasks from a user DSQ to a terminal DSQ and the above wouldn't cover it. Wouldn't it make more sense to do this in dispatch_enqueue()?

Agreed.

Quoted 22 lines
Quoted 22 lines
kernel/sched/ext.c +10 -0
@@ -2894,6 +3059,14 @@ static void scx_enable_task(struct task_struct *p)
 
 	lockdep_assert_rq_held(rq);
 
+	/*
+	 * Clear enqueue/dequeue tracking flags when enabling the task.
+	 * This ensures a clean state when the task enters SCX. Only needed
+	 * if ops.dequeue() is implemented.
+	 */
+	if (SCX_HAS_OP(sch, dequeue))
+		p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED;
+
 	/*
 	 * Set the weight before calling ops.enable() so that the scheduler
 	 * doesn't see a stale value if they inspect the task struct.
@@ -2925,6 +3098,13 @@ static void scx_disable_task(struct task_struct *p)
 	if (SCX_HAS_OP(sch, disable))
 		SCX_CALL_OP_TASK(sch, SCX_KF_REST, disable, rq, p);
 	scx_set_task_state(p, SCX_TASK_READY);
+
+	/*
Quoted 8 lines

kernel/sched/ext.c static void scx_disable_task(struct task_struct *p) · line 3107

Quoted 5 lines
kernel/sched/ext.c +5 -0
+	 * Clear enqueue/dequeue tracking flags when disabling the task.
+	 * Only needed if ops.dequeue() is implemented.
+	 */
+	if (SCX_HAS_OP(sch, dequeue))
+		p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED;

If we make the flag transitions consistent, we shouldn't need these, right? We can add WARN_ON_ONCE() at the head of enqueue maybe.

Correct.

Thanks for the review! I'll post a new version.

-Andrea

author reviewer
#4 lore raw

PATCH 2/2 selftests/sched_ext: Add test to validate ops.dequeue() semantics

In reply to Andrea Righi

Add a new kselftest to validate the following scenarios:
- scenario 0 (Local DSQ): tasks dispatched to local DSQs bypass BPF scheduler entirely, they never enter BPF custody, so no ops.dequeue() should be called,
- scenario 1 (Global DSQ): tasks dispatched to SCX_DSQ_GLOBAL also bypass BPF scheduler, like local DSQs, no ops.dequeue() should be called,
- scenario 2 (User DSQ): tasks enter BPF scheduler custody with full enqueue/dequeue lifecycle tracking and state machine validation (expects 1:1 enqueue/dequeue pairing).

The test validates that:
- terminal DSQ dispatch (local, global) don't trigger ops.dequeue(),
- user DSQ dispatch has exact 1:1 ops.enqueue()/dequeue() pairing,
- dispatch dequeues have no flags (normal workflow),
- property change dequeues have the %SCX_DEQ_SCHED_CHANGE flag set,
- no duplicate enqueues or invalid state transitions are happening.

This validates that the new ops.dequeue() semantics work correctly for all task lifecycle scenarios, including the distinction between terminal DSQs (where BPF scheduler is done with the task) and user DSQs (where BPF scheduler manages the task lifecycle).

Cc Tejun Heo <[email protected]>
Cc Emil Tsalapatis <[email protected]>
Cc Kuba Piecuch <[email protected]>
---
 tools/testing/selftests/sched_ext/Makefile    |   1 +
 .../testing/selftests/sched_ext/dequeue.bpf.c | 269 ++++++++++++++++++
 tools/testing/selftests/sched_ext/dequeue.c   | 207 ++++++++++++++
 3 files changed, 477 insertions(+)
 create mode 100644 tools/testing/selftests/sched_ext/dequeue.bpf.c
 create mode 100644 tools/testing/selftests/sched_ext/dequeue.c
tools/testing/selftests/sched_ext/Makefile +1 -0
index 5fe45f9c5f8fd..764e91edabf93 100644
@@ -161,6 +161,7 @@ all_test_bpfprogs := $(foreach prog,$(wildcard *.bpf.c),$(INCLUDE_DIR)/$(patsubs
 
 auto-test-targets :=			\
 	create_dsq			\
+	dequeue				\
 	enq_last_no_enq_fails		\
 	ddsp_bogus_dsq_fail		\
 	ddsp_vtimelocal_fail		\
tools/testing/selftests/sched_ext/dequeue.bpf.c new file +269 -0

269 lines not on this page · raw message

tools/testing/selftests/sched_ext/dequeue.c new file +207 -0

207 lines not on this page · raw message

Signature · 1 line
2.53.0