Skip to contentSkip to conversation

sched_ext: Fix ops.dequeue() semantics

PATCH Superseded Andrea Righi 4 participants 21 messages Jan 26 – Feb 2

Subsystems (4)

v3 of 10 Superseded Latest is v10 →

lore
Share & tools
lore

Andrea Righi

author reviewer
#0 lore raw

PATCH v3 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(), ensuring that every ops.enqueue() is balanced by a corresponding ops.dequeue() invocation. In addition, ops.dequeue() is now properly invoked when tasks are removed from the sched_ext class, such as on task property changes.

To distinguish between a "regular" dequeue and a property change dequeue a new dequeue flag is introduced: %SCX_DEQ_SCHED_CHANGE. BPF schedulers can use this flag to distinguish between regular dispatch dequeues (%SCX_DEQ_SCHED_CHANGE unset) and property change dequeues (%SCX_DEQ_SCHED_CHANGE set).

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

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           |  33 ++++
 include/linux/sched/ext.h                       |  11 ++
 kernel/sched/ext.c                              |  89 +++++++++-
 kernel/sched/ext_internal.h                     |   7 +
 tools/sched_ext/include/scx/enum_defs.autogen.h |   2 +
 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 | 209 ++++++++++++++++++++++++
 tools/testing/selftests/sched_ext/dequeue.c     | 182 +++++++++++++++++++++
 10 files changed, 534 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 scenarios. As a result, BPF schedulers cannot reliably track task state.

In addition, some ops.dequeue() callbacks can be skipped (e.g., during direct dispatch), so ops.enqueue() calls are not always paired with a corresponding ops.dequeue(), potentially breaking accounting logic.

Fix this by guaranteeing that every ops.enqueue() is matched with a corresponding ops.dequeue(), and introduce the %SCX_DEQ_SCHED_CHANGE flag to distinguish dequeues triggered by scheduling property changes from those occurring in the normal dispatch/execution workflow.

New semantics:
1. ops.enqueue() is called when a task enters the BPF scheduler
2. ops.dequeue() is called when the task leaves the BPF scheduler in the following cases:
a) regular dispatch workflow: task dispatched to a DSQ,
b) core scheduling pick: core-sched picks task before dispatch,
c) property change: task properties modified.

A new %SCX_DEQ_SCHED_CHANGE flag is also introduced, allowing BPF schedulers to distinguish between:
- normal dispatch/execution workflow (dispatch, core-sched pick),
- property changes that require state updates (e.g., sched_setaffinity(), sched_setscheduler(), set_user_nice(), NUMA balancing, CPU migrations, etc.).

With this, BPF schedulers can:
- reliably track task ownership and lifecycle,
- maintain accurate accounting of enqueue/dequeue pairs,
- distinguish between execution events and property changes,
- update internal state appropriately for each dequeue type.

Cc Tejun Heo <[email protected]>
Cc Emil Tsalapatis <[email protected]>
Cc Kuba Piecuch <[email protected]>
---
 Documentation/scheduler/sched-ext.rst         | 33 +++++++
 include/linux/sched/ext.h                     | 11 +++
 kernel/sched/ext.c                            | 89 ++++++++++++++++++-
 kernel/sched/ext_internal.h                   |  7 ++
 .../sched_ext/include/scx/enum_defs.autogen.h |  2 +
 .../sched_ext/include/scx/enums.autogen.bpf.h |  2 +
 tools/sched_ext/include/scx/enums.autogen.h   |  1 +
 7 files changed, 142 insertions(+), 3 deletions(-)
Documentation/scheduler/sched-ext.rst +33 -0
index 404fe6126a769..ed6bf7d9e6e8c 100644
@@ -252,6 +252,37 @@ The following briefly shows how a waking task is scheduled and executed.
 
    * Queue the task on the BPF side.
 
+   Once ``ops.enqueue()`` is called, the task enters the "enqueued state".
+   The task remains in this state until ``ops.dequeue()`` is called, which
+   happens in the following cases:
+
+   1. **Regular dispatch workflow**: when the task is successfully
+      dispatched to a DSQ (local, global, or user DSQ), ``ops.dequeue()``
+      is triggered immediately to notify the BPF scheduler.
+
+   2. **Core scheduling pick**: when ``CONFIG_SCHED_CORE`` is enabled and
+      core scheduling picks a task for execution before it has been
+      dispatched, ``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.), ``ops.dequeue()`` is called
+      with the ``SCX_DEQ_SCHED_CHANGE`` flag set in ``deq_flags``.
+
+   **Important**: ``ops.dequeue()`` is called for *any* enqueued task,
+   regardless of whether the task is still on a BPF data structure, or it
+   has already been dispatched to a DSQ. This guarantees that every
+   ``ops.enqueue()`` will eventually be followed by a corresponding
+   ``ops.dequeue()``.
+
+   This makes it reliable for BPF schedulers to track the enqueued state
+   and maintain accurate accounting.
+
+   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 +350,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 +11 -0
index bcb962d5ee7d8..59446cd0373fa 100644
@@ -84,8 +84,19 @@ struct scx_dispatch_q {
 /* scx_entity.flags */
 enum scx_ent_flags {
 	SCX_TASK_QUEUED		= 1 << 0, /* on ext runqueue */
+	/*
+	 * Set when ops.enqueue() is called; used to determine if ops.dequeue()
+	 * should be invoked when transitioning out of SCX_OPSS_NONE state.
+	 */
+	SCX_TASK_OPS_ENQUEUED	= 1 << 1,
 	SCX_TASK_RESET_RUNNABLE_AT = 1 << 2, /* runnable_at should be reset */
 	SCX_TASK_DEQD_FOR_SLEEP	= 1 << 3, /* last dequeue was for SLEEP */
+	/*
+	 * Set when ops.dequeue() is called after successful dispatch; used to
+	 * distinguish dispatch dequeues from property change dequeues and
+	 * prevent duplicate dequeue calls.
+	 */
+	SCX_TASK_DISPATCH_DEQUEUED = 1 << 4,
 
 	SCX_TASK_STATE_SHIFT	= 8,	  /* bit 8 and 9 are used to carry scx_task_state */
 	SCX_TASK_STATE_BITS	= 2,
kernel/sched/ext.c +86 -3

119 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 +2 -0
index c2c33df9292c2..8284f717ff05e 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
@@ -48,6 +49,7 @@
 #define HAVE_SCX_TASK_QUEUED
 #define HAVE_SCX_TASK_RESET_RUNNABLE_AT
 #define HAVE_SCX_TASK_DEQD_FOR_SLEEP
+#define HAVE_SCX_TASK_DISPATCH_DEQUEUED
 #define HAVE_SCX_TASK_STATE_SHIFT
 #define HAVE_SCX_TASK_STATE_BITS
 #define HAVE_SCX_TASK_STATE_MASK
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.52.0
Reviewed-by on v1 1/2
#2 lore raw
Quoted 35 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 scenarios. As a result, BPF schedulers cannot reliably track task state.

In addition, some ops.dequeue() callbacks can be skipped (e.g., during direct dispatch), so ops.enqueue() calls are not always paired with a corresponding ops.dequeue(), potentially breaking accounting logic.

Fix this by guaranteeing that every ops.enqueue() is matched with a corresponding ops.dequeue(), and introduce the %SCX_DEQ_SCHED_CHANGE flag to distinguish dequeues triggered by scheduling property changes from those occurring in the normal dispatch/execution workflow.

New semantics:
1. ops.enqueue() is called when a task enters the BPF scheduler
2. ops.dequeue() is called when the task leaves the BPF scheduler in the following cases:
a) regular dispatch workflow: task dispatched to a DSQ,
b) core scheduling pick: core-sched picks task before dispatch,
c) property change: task properties modified.

A new %SCX_DEQ_SCHED_CHANGE flag is also introduced, allowing BPF schedulers to distinguish between:
- normal dispatch/execution workflow (dispatch, core-sched pick),
- property changes that require state updates (e.g., sched_setaffinity(), sched_setscheduler(), set_user_nice(), NUMA balancing, CPU migrations, etc.).

With this, BPF schedulers can:
- reliably track task ownership and lifecycle,
- maintain accurate accounting of enqueue/dequeue pairs,
- distinguish between execution events and property changes,
- update internal state appropriately for each dequeue type.

Quoted 4 lines
Cc Tejun Heo <[email protected]>
Cc Emil Tsalapatis <[email protected]>
Cc Kuba Piecuch <[email protected]>

Looks great overall. Following up on our off-list chat about whether SCX_TASK_DISPATCH_DEQUEUED is necessary: We need it for the new DEQ_STATE change flag so no need to consider removing it imo.

Quoted 271 lines
---
 Documentation/scheduler/sched-ext.rst         | 33 +++++++
 include/linux/sched/ext.h                     | 11 +++
 kernel/sched/ext.c                            | 89 ++++++++++++++++++-
 kernel/sched/ext_internal.h                   |  7 ++
 .../sched_ext/include/scx/enum_defs.autogen.h |  2 +
 .../sched_ext/include/scx/enums.autogen.bpf.h |  2 +
 tools/sched_ext/include/scx/enums.autogen.h   |  1 +
 7 files changed, 142 insertions(+), 3 deletions(-)
Documentation/scheduler/sched-ext.rst +33 -0
index 404fe6126a769..ed6bf7d9e6e8c 100644
@@ -252,6 +252,37 @@ The following briefly shows how a waking task is scheduled and executed.
 
    * Queue the task on the BPF side.
 
+   Once ``ops.enqueue()`` is called, the task enters the "enqueued state".
+   The task remains in this state until ``ops.dequeue()`` is called, which
+   happens in the following cases:
+
+   1. **Regular dispatch workflow**: when the task is successfully
+      dispatched to a DSQ (local, global, or user DSQ), ``ops.dequeue()``
+      is triggered immediately to notify the BPF scheduler.
+
+   2. **Core scheduling pick**: when ``CONFIG_SCHED_CORE`` is enabled and
+      core scheduling picks a task for execution before it has been
+      dispatched, ``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.), ``ops.dequeue()`` is called
+      with the ``SCX_DEQ_SCHED_CHANGE`` flag set in ``deq_flags``.
+
+   **Important**: ``ops.dequeue()`` is called for *any* enqueued task,
+   regardless of whether the task is still on a BPF data structure, or it
+   has already been dispatched to a DSQ. This guarantees that every
+   ``ops.enqueue()`` will eventually be followed by a corresponding
+   ``ops.dequeue()``.
+
+   This makes it reliable for BPF schedulers to track the enqueued state
+   and maintain accurate accounting.
+
+   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 +350,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 +11 -0
index bcb962d5ee7d8..59446cd0373fa 100644
@@ -84,8 +84,19 @@ struct scx_dispatch_q {
 /* scx_entity.flags */
 enum scx_ent_flags {
 	SCX_TASK_QUEUED		= 1 << 0, /* on ext runqueue */
+	/*
+	 * Set when ops.enqueue() is called; used to determine if ops.dequeue()
+	 * should be invoked when transitioning out of SCX_OPSS_NONE state.
+	 */
+	SCX_TASK_OPS_ENQUEUED	= 1 << 1,
 	SCX_TASK_RESET_RUNNABLE_AT = 1 << 2, /* runnable_at should be reset */
 	SCX_TASK_DEQD_FOR_SLEEP	= 1 << 3, /* last dequeue was for SLEEP */
+	/*
+	 * Set when ops.dequeue() is called after successful dispatch; used to
+	 * distinguish dispatch dequeues from property change dequeues and
+	 * prevent duplicate dequeue calls.
+	 */
+	SCX_TASK_DISPATCH_DEQUEUED = 1 << 4,
 
 	SCX_TASK_STATE_SHIFT	= 8,	  /* bit 8 and 9 are used to carry scx_task_state */
 	SCX_TASK_STATE_BITS	= 2,
kernel/sched/ext.c +86 -3
index afe28c04d5aa7..18bca2b83f5c5 100644
@@ -1287,6 +1287,20 @@ static void direct_dispatch(struct scx_sched *sch, struct task_struct *p,
 
 	p->scx.ddsp_enq_flags |= enq_flags;
 
+	/*
+	 * The task is about to be dispatched. If ops.enqueue() was called,
+	 * notify the BPF scheduler by calling ops.dequeue().
+	 *
+	 * Keep %SCX_TASK_OPS_ENQUEUED set so that subsequent property
+	 * changes can trigger ops.dequeue() with %SCX_DEQ_SCHED_CHANGE.
+	 * Mark that the dispatch dequeue has been called to distinguish
+	 * from property change dequeues.
+	 */
+	if (SCX_HAS_OP(sch, dequeue) && (p->scx.flags & SCX_TASK_OPS_ENQUEUED)) {
+		SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq, p, 0);
+		p->scx.flags |= SCX_TASK_DISPATCH_DEQUEUED;
+	}
+
 	/*
 	 * We are in the enqueue path with @rq locked and pinned, and thus can't
 	 * double lock a remote rq and enqueue to its local DSQ. For
@@ -1391,6 +1405,16 @@ static void do_enqueue_task(struct rq *rq, struct task_struct *p, u64 enq_flags,
 	WARN_ON_ONCE(atomic_long_read(&p->scx.ops_state) != SCX_OPSS_NONE);
 	atomic_long_set(&p->scx.ops_state, SCX_OPSS_QUEUEING | qseq);
 
+	/*
+	 * Mark that ops.enqueue() is being called for this task.
+	 * Clear the dispatch dequeue flag for the new enqueue cycle.
+	 * Only track these flags if ops.dequeue() is implemented.
+	 */
+	if (SCX_HAS_OP(sch, dequeue)) {
+		p->scx.flags |= SCX_TASK_OPS_ENQUEUED;
+		p->scx.flags &= ~SCX_TASK_DISPATCH_DEQUEUED;
+	}
+
 	ddsp_taskp = this_cpu_ptr(&direct_dispatch_task);
 	WARN_ON_ONCE(*ddsp_taskp);
 	*ddsp_taskp = p;
@@ -1523,6 +1547,34 @@ static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags)
 
 	switch (opss & SCX_OPSS_STATE_MASK) {
 	case SCX_OPSS_NONE:
+		if (SCX_HAS_OP(sch, dequeue) &&
+		    p->scx.flags & SCX_TASK_OPS_ENQUEUED) {
+			/*
+			 * Task was already dispatched. Only call ops.dequeue()
+			 * if it hasn't been called yet (check DISPATCH_DEQUEUED).
+			 * This can happen when:
+			 * 1. Core-sched picks a task that was dispatched
+			 * 2. Property changes occur after dispatch
+			 */
+			if (!(p->scx.flags & SCX_TASK_DISPATCH_DEQUEUED)) {
+				/*
+				 * ops.dequeue() wasn't called during dispatch.
+				 * This shouldn't normally happen, but call it now.
+				 */
+				SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq,
+						 p, deq_flags);
+			} else if (!(deq_flags & (DEQUEUE_SLEEP | SCX_DEQ_CORE_SCHED_EXEC))) {
+				/*
+				 * This is a property change after
+				 * dispatch. Call ops.dequeue() again with
+				 * %SCX_DEQ_SCHED_CHANGE.
+				 */
+				SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq,
+						 p, deq_flags | SCX_DEQ_SCHED_CHANGE);
+			}
+			p->scx.flags &= ~(SCX_TASK_OPS_ENQUEUED |
+					  SCX_TASK_DISPATCH_DEQUEUED);
+		}
 		break;
 	case SCX_OPSS_QUEUEING:
 		/*
@@ -1531,9 +1583,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.
+		 */
+		if (SCX_HAS_OP(sch, dequeue)) {
+			u64 flags = deq_flags;
+			/*
+			 * Add %SCX_DEQ_SCHED_CHANGE for property changes,
+			 * but not for core-sched picks or sleep.
+			 */
+			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 |
+					  SCX_TASK_DISPATCH_DEQUEUED);
+		}
 
 		if (atomic_long_try_cmpxchg(&p->scx.ops_state, &opss,
 					    SCX_OPSS_NONE))
@@ -2107,6 +2174,22 @@ static void finish_dispatch(struct scx_sched *sch, struct rq *rq,
 
 	BUG_ON(!(p->scx.flags & SCX_TASK_QUEUED));
 
+	/*
+	 * The task is about to be dispatched. If ops.enqueue() was called,
+	 * notify the BPF scheduler by calling ops.dequeue().
+	 *
+	 * Keep %SCX_TASK_OPS_ENQUEUED set so that subsequent property
+	 * changes can trigger ops.dequeue() with %SCX_DEQ_SCHED_CHANGE.
+	 * Mark that the dispatch dequeue has been called to distinguish
+	 * from property change dequeues.
+	 */
+	if (SCX_HAS_OP(sch, dequeue) && (p->scx.flags & SCX_TASK_OPS_ENQUEUED)) {
+		struct rq *task_rq = task_rq(p);
+
+		SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, task_rq, p, 0);
+		p->scx.flags |= SCX_TASK_DISPATCH_DEQUEUED;
+	}
+
 	dsq = find_dsq_for_dispatch(sch, this_rq(), dsq_id, p);
 
 	if (dsq->id == SCX_DSQ_LOCAL)
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 +2 -0
index c2c33df9292c2..8284f717ff05e 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
@@ -48,6 +49,7 @@
 #define HAVE_SCX_TASK_QUEUED
 #define HAVE_SCX_TASK_RESET_RUNNABLE_AT
 #define HAVE_SCX_TASK_DEQD_FOR_SLEEP
+#define HAVE_SCX_TASK_DISPATCH_DEQUEUED
 #define HAVE_SCX_TASK_STATE_SHIFT
 #define HAVE_SCX_TASK_STATE_BITS
 #define HAVE_SCX_TASK_STATE_MASK
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)
#3 lore raw
In reply to Andrea Righi

Hi Andrea,

Quoted 70 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 scenarios. As a result, BPF schedulers cannot reliably track task state.

In addition, some ops.dequeue() callbacks can be skipped (e.g., during direct dispatch), so ops.enqueue() calls are not always paired with a corresponding ops.dequeue(), potentially breaking accounting logic.

Fix this by guaranteeing that every ops.enqueue() is matched with a corresponding ops.dequeue(), and introduce the %SCX_DEQ_SCHED_CHANGE flag to distinguish dequeues triggered by scheduling property changes from those occurring in the normal dispatch/execution workflow.

New semantics:
1. ops.enqueue() is called when a task enters the BPF scheduler
2. ops.dequeue() is called when the task leaves the BPF scheduler in the following cases:
a) regular dispatch workflow: task dispatched to a DSQ,
b) core scheduling pick: core-sched picks task before dispatch,
c) property change: task properties modified.

A new %SCX_DEQ_SCHED_CHANGE flag is also introduced, allowing BPF schedulers to distinguish between:
- normal dispatch/execution workflow (dispatch, core-sched pick),
- property changes that require state updates (e.g., sched_setaffinity(), sched_setscheduler(), set_user_nice(), NUMA balancing, CPU migrations, etc.).

With this, BPF schedulers can:
- reliably track task ownership and lifecycle,
- maintain accurate accounting of enqueue/dequeue pairs,
- distinguish between execution events and property changes,
- update internal state appropriately for each dequeue type.

Cc Tejun Heo <[email protected]>
Cc Emil Tsalapatis <[email protected]>
Cc Kuba Piecuch <[email protected]>
---
 Documentation/scheduler/sched-ext.rst         | 33 +++++++
 include/linux/sched/ext.h                     | 11 +++
 kernel/sched/ext.c                            | 89 ++++++++++++++++++-
 kernel/sched/ext_internal.h                   |  7 ++
 .../sched_ext/include/scx/enum_defs.autogen.h |  2 +
 .../sched_ext/include/scx/enums.autogen.bpf.h |  2 +
 tools/sched_ext/include/scx/enums.autogen.h   |  1 +
 7 files changed, 142 insertions(+), 3 deletions(-)
Documentation/scheduler/sched-ext.rst +13 -0
index 404fe6126a769..ed6bf7d9e6e8c 100644
@@ -252,6 +252,37 @@ The following briefly shows how a waking task is scheduled and executed.
 
    * Queue the task on the BPF side.
 
+   Once ``ops.enqueue()`` is called, the task enters the "enqueued state".
+   The task remains in this state until ``ops.dequeue()`` is called, which
+   happens in the following cases:
+
+   1. **Regular dispatch workflow**: when the task is successfully
+      dispatched to a DSQ (local, global, or user DSQ), ``ops.dequeue()``
+      is triggered immediately to notify the BPF scheduler.
+
+   2. **Core scheduling pick**: when ``CONFIG_SCHED_CORE`` is enabled and
+      core scheduling picks a task for execution before it has been
+      dispatched, ``ops.dequeue()`` is called with the
+      ``SCX_DEQ_CORE_SCHED_EXEC`` flag.
+

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

Quoted 10 lines
Documentation/scheduler/sched-ext.rst +10 -0
+   3. **Scheduling property change**: when a task property changes (via
+      operations like ``sched_setaffinity()``, ``sched_setscheduler()``,
+      priority changes, CPU migrations, etc.), ``ops.dequeue()`` is called
+      with the ``SCX_DEQ_SCHED_CHANGE`` flag set in ``deq_flags``.
+
+   **Important**: ``ops.dequeue()`` is called for *any* enqueued task,
+   regardless of whether the task is still on a BPF data structure, or it
+   has already been dispatched to a DSQ. This guarantees that every
+   ``ops.enqueue()`` will eventually be followed by a corresponding
+   ``ops.dequeue()``.

Not sure I follow this paragraph, specifically the first sentence (starting with ``ops.dequeue()`` is called ...).
It seems to imply that a task that has already been dispatched to a DSQ still counts as enqueued, but the preceding text contradicts that by saying that a task is in an "enqueued state" from the time ops.enqueue() is called until (among other things) it's successfully dispatched to a DSQ.

This would make sense if this paragraph used "enqueued" in the SCX_TASK_QUEUED sense, while the first paragraph used the SCX_OPSS_QUEUED sense, but if that's the case, it's quite confusing and should be clarified IMO.

Quoted 30 lines
Documentation/scheduler/sched-ext.rst +10 -0
+
+   This makes it reliable for BPF schedulers to track the enqueued state
+   and maintain accurate accounting.
+
+   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 +350,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 +2 -0
index bcb962d5ee7d8..59446cd0373fa 100644
@@ -84,8 +84,19 @@ struct scx_dispatch_q {
 /* scx_entity.flags */
 enum scx_ent_flags {
 	SCX_TASK_QUEUED		= 1 << 0, /* on ext runqueue */
+	/*
+	 * Set when ops.enqueue() is called; used to determine if ops.dequeue()

include/linux/sched/ext.h struct scx_dispatch_q { · line 98

Quoted 10 lines
include/linux/sched/ext.h +8 -0
+	 * should be invoked when transitioning out of SCX_OPSS_NONE state.
+	 */
+	SCX_TASK_OPS_ENQUEUED	= 1 << 1,
 	SCX_TASK_RESET_RUNNABLE_AT = 1 << 2, /* runnable_at should be reset */
 	SCX_TASK_DEQD_FOR_SLEEP	= 1 << 3, /* last dequeue was for SLEEP */
+	/*
+	 * Set when ops.dequeue() is called after successful dispatch; used to
+	 * distinguish dispatch dequeues from property change dequeues and
+	 * prevent duplicate dequeue calls.
+	 */

What counts as a duplicate dequeue call? Looking at the code, we can clearly have ops.dequeue(SCHED_CHANGE) called after ops.dequeue(0) without an intervening call to ops.enqueue().

Quoted 54 lines
include/linux/sched/ext.h +1 -0
+	SCX_TASK_DISPATCH_DEQUEUED = 1 << 4,
 
 	SCX_TASK_STATE_SHIFT	= 8,	  /* bit 8 and 9 are used to carry scx_task_state */
 	SCX_TASK_STATE_BITS	= 2,
kernel/sched/ext.c +28 -0
index afe28c04d5aa7..18bca2b83f5c5 100644
@@ -1287,6 +1287,20 @@ static void direct_dispatch(struct scx_sched *sch, struct task_struct *p,
 
 	p->scx.ddsp_enq_flags |= enq_flags;
 
+	/*
+	 * The task is about to be dispatched. If ops.enqueue() was called,
+	 * notify the BPF scheduler by calling ops.dequeue().
+	 *
+	 * Keep %SCX_TASK_OPS_ENQUEUED set so that subsequent property
+	 * changes can trigger ops.dequeue() with %SCX_DEQ_SCHED_CHANGE.
+	 * Mark that the dispatch dequeue has been called to distinguish
+	 * from property change dequeues.
+	 */
+	if (SCX_HAS_OP(sch, dequeue) && (p->scx.flags & SCX_TASK_OPS_ENQUEUED)) {
+		SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq, p, 0);
+		p->scx.flags |= SCX_TASK_DISPATCH_DEQUEUED;
+	}
+
 	/*
 	 * We are in the enqueue path with @rq locked and pinned, and thus can't
 	 * double lock a remote rq and enqueue to its local DSQ. For
@@ -1391,6 +1405,16 @@ static void do_enqueue_task(struct rq *rq, struct task_struct *p, u64 enq_flags,
 	WARN_ON_ONCE(atomic_long_read(&p->scx.ops_state) != SCX_OPSS_NONE);
 	atomic_long_set(&p->scx.ops_state, SCX_OPSS_QUEUEING | qseq);
 
+	/*
+	 * Mark that ops.enqueue() is being called for this task.
+	 * Clear the dispatch dequeue flag for the new enqueue cycle.
+	 * Only track these flags if ops.dequeue() is implemented.
+	 */
+	if (SCX_HAS_OP(sch, dequeue)) {
+		p->scx.flags |= SCX_TASK_OPS_ENQUEUED;
+		p->scx.flags &= ~SCX_TASK_DISPATCH_DEQUEUED;
+	}
+
 	ddsp_taskp = this_cpu_ptr(&direct_dispatch_task);
 	WARN_ON_ONCE(*ddsp_taskp);
 	*ddsp_taskp = p;
@@ -1523,6 +1547,34 @@ static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags)
 
 	switch (opss & SCX_OPSS_STATE_MASK) {
 	case SCX_OPSS_NONE:
+		if (SCX_HAS_OP(sch, dequeue) &&
+		    p->scx.flags & SCX_TASK_OPS_ENQUEUED) {
+			/*
+			 * Task was already dispatched. Only call ops.dequeue()

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

Quoted 10 lines
kernel/sched/ext.c +10 -0
+			 * if it hasn't been called yet (check DISPATCH_DEQUEUED).
+			 * This can happen when:
+			 * 1. Core-sched picks a task that was dispatched
+			 * 2. Property changes occur after dispatch
+			 */
+			if (!(p->scx.flags & SCX_TASK_DISPATCH_DEQUEUED)) {
+				/*
+				 * ops.dequeue() wasn't called during dispatch.
+				 * This shouldn't normally happen, but call it now.
+				 */

Should we add a warning here?

Quoted 4 lines
kernel/sched/ext.c +4 -0
+				SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq,
+						 p, deq_flags);
+			} else if (!(deq_flags & (DEQUEUE_SLEEP | SCX_DEQ_CORE_SCHED_EXEC))) {
+				/*

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

Quoted 10 lines
kernel/sched/ext.c +10 -0
+				 * This is a property change after
+				 * dispatch. Call ops.dequeue() again with
+				 * %SCX_DEQ_SCHED_CHANGE.
+				 */
+				SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq,
+						 p, deq_flags | SCX_DEQ_SCHED_CHANGE);
+			}
+			p->scx.flags &= ~(SCX_TASK_OPS_ENQUEUED |
+					  SCX_TASK_DISPATCH_DEQUEUED);
+		}

If I understand the logic correctly, ops.dequeue(SCHED_CHANGE) will be called for a task at most once between it being dispatched and taken off the CPU, even if its properties are changed multiple times while it's on CPU. Is that intentional? I don't see it documented.

To illustrate, assume we have a task p that has been enqueued, dispatched, and is currently running on the CPU, so we have both SCX_TASK_OPS_ENQUEUE and SCX_TASK_DISPATCH_DEQUEUED set in p->scx.flags.

When a property of p is changed while it runs on the CPU, the sequence of calls is:
dequeue_task_scx(p, DEQUEUE_SAVE) => put_prev_task_scx(p) => (change property) => enqueue_task_scx(p, ENQUEUE_RESTORE) => set_next_task_scx(p).

dequeue_task_scx(p, DEQUEUE_SAVE) calls ops_dequeue() which calls ops.dequeue(p, ... | SCHED_CHANGE) and clears SCX_TASK_{OPS_ENQUEUED,DISPATCH_DEQUEUED} from p->scx.flags.

put_prev_task_scx(p) doesn't do much because SCX_TASK_QUEUED was cleared by dequeue_task_scx().

enqueue_task_scx(p, ENQUEUE_RESTORE) sets sticky_cpu because the task is currently running and ENQUEUE_RESTORE is set. This causes do_enqueue_task() to jump straight to local_norefill, skipping the call to ops.enqueue(), leaving SCX_TASK_OPS_ENQUEUED unset, and then enqueueing the task on the local DSQ.

set_next_task_scx(p) calls ops_dequeue(p, SCX_DEQ_CORE_SCHED_EXEC) even though this is not a core-sched pick, but it won't do much because the ops_state is SCX_OPSS_NONE and SCX_TASK_OPS_ENQUEUED is unset. It also calls dispatch_dequeue(p) which the removes the task from the local DSQ it was just inserted into.

So, we end up in a state where any subsequent property change while the task is still on CPU will not result in ops.dequeue(p, ... | SCHED_CHANGE) being called, because both SCX_TASK_OPS_ENQUEUED and SCX_TASK_DISPATCH_DEQUEUED are unset in p->scx.flags.

I really hope I didn't mess anything up when tracing the code, but of course I'm happy to be corrected.

Quoted 107 lines
kernel/sched/ext.c +34 -3
 		break;
 	case SCX_OPSS_QUEUEING:
 		/*
@@ -1531,9 +1583,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.
+		 */
+		if (SCX_HAS_OP(sch, dequeue)) {
+			u64 flags = deq_flags;
+			/*
+			 * Add %SCX_DEQ_SCHED_CHANGE for property changes,
+			 * but not for core-sched picks or sleep.
+			 */
+			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 |
+					  SCX_TASK_DISPATCH_DEQUEUED);
+		}
 
 		if (atomic_long_try_cmpxchg(&p->scx.ops_state, &opss,
 					    SCX_OPSS_NONE))
@@ -2107,6 +2174,22 @@ static void finish_dispatch(struct scx_sched *sch, struct rq *rq,
 
 	BUG_ON(!(p->scx.flags & SCX_TASK_QUEUED));
 
+	/*
+	 * The task is about to be dispatched. If ops.enqueue() was called,
+	 * notify the BPF scheduler by calling ops.dequeue().
+	 *
+	 * Keep %SCX_TASK_OPS_ENQUEUED set so that subsequent property
+	 * changes can trigger ops.dequeue() with %SCX_DEQ_SCHED_CHANGE.
+	 * Mark that the dispatch dequeue has been called to distinguish
+	 * from property change dequeues.
+	 */
+	if (SCX_HAS_OP(sch, dequeue) && (p->scx.flags & SCX_TASK_OPS_ENQUEUED)) {
+		struct rq *task_rq = task_rq(p);
+
+		SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, task_rq, p, 0);
+		p->scx.flags |= SCX_TASK_DISPATCH_DEQUEUED;
+	}
+
 	dsq = find_dsq_for_dispatch(sch, this_rq(), dsq_id, p);
 
 	if (dsq->id == SCX_DSQ_LOCAL)
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 +2 -0
index c2c33df9292c2..8284f717ff05e 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
@@ -48,6 +49,7 @@
 #define HAVE_SCX_TASK_QUEUED
 #define HAVE_SCX_TASK_RESET_RUNNABLE_AT
 #define HAVE_SCX_TASK_DEQD_FOR_SLEEP
+#define HAVE_SCX_TASK_DISPATCH_DEQUEUED
 #define HAVE_SCX_TASK_STATE_SHIFT
 #define HAVE_SCX_TASK_STATE_BITS
 #define HAVE_SCX_TASK_STATE_MASK
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 +0 -0
index fedec938584be..fc9a7a4d9dea5 100644

tools/sched_ext/include/scx/enums.autogen.h line 50

Quoted 5 lines
tools/sched_ext/include/scx/enums.autogen.h +1 -0
@@ -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)

Thanks,
Kuba

author reviewer
#4 lore raw

Hi Kuba,

On Tue, Jan 27, 2026 at 04:41:43PM +0000, Kuba Piecuch wrote:
...

Quoted 39 lines
Quoted 21 lines
Documentation/scheduler/sched-ext.rst +13 -0
index 404fe6126a769..ed6bf7d9e6e8c 100644
@@ -252,6 +252,37 @@ The following briefly shows how a waking task is scheduled and executed.
 
    * Queue the task on the BPF side.
 
+   Once ``ops.enqueue()`` is called, the task enters the "enqueued state".
+   The task remains in this state until ``ops.dequeue()`` is called, which
+   happens in the following cases:
+
+   1. **Regular dispatch workflow**: when the task is successfully
+      dispatched to a DSQ (local, global, or user DSQ), ``ops.dequeue()``
+      is triggered immediately to notify the BPF scheduler.
+
+   2. **Core scheduling pick**: when ``CONFIG_SCHED_CORE`` is enabled and
+      core scheduling picks a task for execution before it has been
+      dispatched, ``ops.dequeue()`` is called with the
+      ``SCX_DEQ_CORE_SCHED_EXEC`` flag.
+

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

Quoted 10 lines
Documentation/scheduler/sched-ext.rst +10 -0
+   3. **Scheduling property change**: when a task property changes (via
+      operations like ``sched_setaffinity()``, ``sched_setscheduler()``,
+      priority changes, CPU migrations, etc.), ``ops.dequeue()`` is called
+      with the ``SCX_DEQ_SCHED_CHANGE`` flag set in ``deq_flags``.
+
+   **Important**: ``ops.dequeue()`` is called for *any* enqueued task,
+   regardless of whether the task is still on a BPF data structure, or it
+   has already been dispatched to a DSQ. This guarantees that every
+   ``ops.enqueue()`` will eventually be followed by a corresponding
+   ``ops.dequeue()``.

Not sure I follow this paragraph, specifically the first sentence (starting with ``ops.dequeue()`` is called ...).
It seems to imply that a task that has already been dispatched to a DSQ still counts as enqueued, but the preceding text contradicts that by saying that a task is in an "enqueued state" from the time ops.enqueue() is called until (among other things) it's successfully dispatched to a DSQ.

Quoted 3 lines

This would make sense if this paragraph used "enqueued" in the SCX_TASK_QUEUED sense, while the first paragraph used the SCX_OPSS_QUEUED sense, but if that's the case, it's quite confusing and should be clarified IMO.

Good point, the confusion is on my side, the documentation overloads the term "enqueued" and doesn't clearly distinguish the different contexts.

In that paragraph, "enqueued" refers to the ops lifecycle (i.e., a task for which ops.enqueue() has been called and whose scheduler-visible state is being tracked), not to the task being queued on a DSQ or having SCX_TASK_QUEUED set.

The intent is to treat ops.enqueue() and ops.dequeue() as the boundaries of a scheduler-visible lifecycle, regardless of whether the task is eventually queued on a DSQ or dispatched directly.

And as noted by Tejun in his last email, skipping ops.dequeue() for direct dispatches also makes sense, since in that case no new ops lifecycle is established (direct dispatch in ops.select_cpu() or ops.enqueue() can be seen as a shortcut to bypass the scheduler).

I'll update the patch and documentation accordingly to make this distinction more explicit.

Quoted 37 lines
Quoted 37 lines
Documentation/scheduler/sched-ext.rst +10 -0
+
+   This makes it reliable for BPF schedulers to track the enqueued state
+   and maintain accurate accounting.
+
+   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 +350,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 +6 -0
index bcb962d5ee7d8..59446cd0373fa 100644
@@ -84,8 +84,19 @@ struct scx_dispatch_q {
 /* scx_entity.flags */
 enum scx_ent_flags {
 	SCX_TASK_QUEUED		= 1 << 0, /* on ext runqueue */
+	/*
+	 * Set when ops.enqueue() is called; used to determine if ops.dequeue()
+	 * should be invoked when transitioning out of SCX_OPSS_NONE state.
+	 */
+	SCX_TASK_OPS_ENQUEUED	= 1 << 1,
 	SCX_TASK_RESET_RUNNABLE_AT = 1 << 2, /* runnable_at should be reset */
 	SCX_TASK_DEQD_FOR_SLEEP	= 1 << 3, /* last dequeue was for SLEEP */
+	/*
Quoted 8 lines

include/linux/sched/ext.h struct scx_dispatch_q { · line 98

Quoted 4 lines
include/linux/sched/ext.h +4 -0
+	 * Set when ops.dequeue() is called after successful dispatch; used to
+	 * distinguish dispatch dequeues from property change dequeues and
+	 * prevent duplicate dequeue calls.
+	 */

What counts as a duplicate dequeue call? Looking at the code, we can clearly have ops.dequeue(SCHED_CHANGE) called after ops.dequeue(0) without an intervening call to ops.enqueue().

Yeah SCHED_CHANGE dequeues are the exception, and it's acceptable to have ops.dequeue(0) + ops.dequeue(SCHED_CHANGE). The idea is to catch potential duplicate dispatch dequeues. I'll clarify this.

Quoted 59 lines
Quoted 59 lines
include/linux/sched/ext.h +1 -0
+	SCX_TASK_DISPATCH_DEQUEUED = 1 << 4,
 
 	SCX_TASK_STATE_SHIFT	= 8,	  /* bit 8 and 9 are used to carry scx_task_state */
 	SCX_TASK_STATE_BITS	= 2,
kernel/sched/ext.c +32 -0
index afe28c04d5aa7..18bca2b83f5c5 100644
@@ -1287,6 +1287,20 @@ static void direct_dispatch(struct scx_sched *sch, struct task_struct *p,
 
 	p->scx.ddsp_enq_flags |= enq_flags;
 
+	/*
+	 * The task is about to be dispatched. If ops.enqueue() was called,
+	 * notify the BPF scheduler by calling ops.dequeue().
+	 *
+	 * Keep %SCX_TASK_OPS_ENQUEUED set so that subsequent property
+	 * changes can trigger ops.dequeue() with %SCX_DEQ_SCHED_CHANGE.
+	 * Mark that the dispatch dequeue has been called to distinguish
+	 * from property change dequeues.
+	 */
+	if (SCX_HAS_OP(sch, dequeue) && (p->scx.flags & SCX_TASK_OPS_ENQUEUED)) {
+		SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq, p, 0);
+		p->scx.flags |= SCX_TASK_DISPATCH_DEQUEUED;
+	}
+
 	/*
 	 * We are in the enqueue path with @rq locked and pinned, and thus can't
 	 * double lock a remote rq and enqueue to its local DSQ. For
@@ -1391,6 +1405,16 @@ static void do_enqueue_task(struct rq *rq, struct task_struct *p, u64 enq_flags,
 	WARN_ON_ONCE(atomic_long_read(&p->scx.ops_state) != SCX_OPSS_NONE);
 	atomic_long_set(&p->scx.ops_state, SCX_OPSS_QUEUEING | qseq);
 
+	/*
+	 * Mark that ops.enqueue() is being called for this task.
+	 * Clear the dispatch dequeue flag for the new enqueue cycle.
+	 * Only track these flags if ops.dequeue() is implemented.
+	 */
+	if (SCX_HAS_OP(sch, dequeue)) {
+		p->scx.flags |= SCX_TASK_OPS_ENQUEUED;
+		p->scx.flags &= ~SCX_TASK_DISPATCH_DEQUEUED;
+	}
+
 	ddsp_taskp = this_cpu_ptr(&direct_dispatch_task);
 	WARN_ON_ONCE(*ddsp_taskp);
 	*ddsp_taskp = p;
@@ -1523,6 +1547,34 @@ static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags)
 
 	switch (opss & SCX_OPSS_STATE_MASK) {
 	case SCX_OPSS_NONE:
+		if (SCX_HAS_OP(sch, dequeue) &&
+		    p->scx.flags & SCX_TASK_OPS_ENQUEUED) {
+			/*
+			 * Task was already dispatched. Only call ops.dequeue()
+			 * if it hasn't been called yet (check DISPATCH_DEQUEUED).
+			 * This can happen when:
+			 * 1. Core-sched picks a task that was dispatched
+			 * 2. Property changes occur after dispatch
Quoted 8 lines

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

Quoted 6 lines
kernel/sched/ext.c +6 -0
+			 */
+			if (!(p->scx.flags & SCX_TASK_DISPATCH_DEQUEUED)) {
+				/*
+				 * ops.dequeue() wasn't called during dispatch.
+				 * This shouldn't normally happen, but call it now.
+				 */

Should we add a warning here?

Good idea, I'll add a WARN_ON_ONCE().

Quoted 50 lines
Quoted 5 lines
kernel/sched/ext.c +4 -0
+				SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq,
+						 p, deq_flags);
+			} else if (!(deq_flags & (DEQUEUE_SLEEP | SCX_DEQ_CORE_SCHED_EXEC))) {
+				/*

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

Quoted 10 lines
kernel/sched/ext.c +10 -0
+				 * This is a property change after
+				 * dispatch. Call ops.dequeue() again with
+				 * %SCX_DEQ_SCHED_CHANGE.
+				 */
+				SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq,
+						 p, deq_flags | SCX_DEQ_SCHED_CHANGE);
+			}
+			p->scx.flags &= ~(SCX_TASK_OPS_ENQUEUED |
+					  SCX_TASK_DISPATCH_DEQUEUED);
+		}

If I understand the logic correctly, ops.dequeue(SCHED_CHANGE) will be called for a task at most once between it being dispatched and taken off the CPU, even if its properties are changed multiple times while it's on CPU. Is that intentional? I don't see it documented.

To illustrate, assume we have a task p that has been enqueued, dispatched, and is currently running on the CPU, so we have both SCX_TASK_OPS_ENQUEUE and SCX_TASK_DISPATCH_DEQUEUED set in p->scx.flags.

When a property of p is changed while it runs on the CPU, the sequence of calls is:
dequeue_task_scx(p, DEQUEUE_SAVE) => put_prev_task_scx(p) => (change property) => enqueue_task_scx(p, ENQUEUE_RESTORE) => set_next_task_scx(p).

dequeue_task_scx(p, DEQUEUE_SAVE) calls ops_dequeue() which calls ops.dequeue(p, ... | SCHED_CHANGE) and clears SCX_TASK_{OPS_ENQUEUED,DISPATCH_DEQUEUED} from p->scx.flags.

put_prev_task_scx(p) doesn't do much because SCX_TASK_QUEUED was cleared by dequeue_task_scx().

enqueue_task_scx(p, ENQUEUE_RESTORE) sets sticky_cpu because the task is currently running and ENQUEUE_RESTORE is set. This causes do_enqueue_task() to jump straight to local_norefill, skipping the call to ops.enqueue(), leaving SCX_TASK_OPS_ENQUEUED unset, and then enqueueing the task on the local DSQ.

set_next_task_scx(p) calls ops_dequeue(p, SCX_DEQ_CORE_SCHED_EXEC) even though this is not a core-sched pick, but it won't do much because the ops_state is SCX_OPSS_NONE and SCX_TASK_OPS_ENQUEUED is unset. It also calls dispatch_dequeue(p) which the removes the task from the local DSQ it was just inserted into.

Quoted 7 lines

So, we end up in a state where any subsequent property change while the task is still on CPU will not result in ops.dequeue(p, ... | SCHED_CHANGE) being called, because both SCX_TASK_OPS_ENQUEUED and SCX_TASK_DISPATCH_DEQUEUED are unset in p->scx.flags.

I really hope I didn't mess anything up when tracing the code, but of course I'm happy to be corrected.

Correct. And the enqueue/dequeue balancing is preserved here. In the scenario you describe, subsequent property changes while the task remains running go through ENQUEUE_RESTORE, which intentionally skips ops.enqueue(). Since no new enqueue cycle is started, there is no corresponding ops.dequeue() to deliver either.

In other words, SCX_DEQ_SCHED_CHANGE is associated with invalidating the scheduler state established by the last ops.enqueue(), not with every individual property change. Multiple property changes while the task stays on CPU are coalesced and the enqueue/dequeue pairing remains balanced.

I agree this distinction isn't obvious from the current documentation, I'll clarify that SCX_DEQ_SCHED_CHANGE is edge-triggered per enqueue/run cycle, not per property change.

Do you see any practical use case where it'd be beneficial to tie individual ops.dequeue() calls to every property change, as opposed to the current coalesced behavior??

Thanks,
-Andrea

#5 lore raw

Hi Andrea,

On Fri Jan 30, 2026 at 7:34 AM UTC, Andrea Righi wrote:
...

Quoted 8 lines

Good point, the confusion is on my side, the documentation overloads the term "enqueued" and doesn't clearly distinguish the different contexts.

In that paragraph, "enqueued" refers to the ops lifecycle (i.e., a task for which ops.enqueue() has been called and whose scheduler-visible state is being tracked), not to the task being queued on a DSQ or having SCX_TASK_QUEUED set.

Quoted 8 lines

The intent is to treat ops.enqueue() and ops.dequeue() as the boundaries of a scheduler-visible lifecycle, regardless of whether the task is eventually queued on a DSQ or dispatched directly.

And as noted by Tejun in his last email, skipping ops.dequeue() for direct dispatches also makes sense, since in that case no new ops lifecycle is established (direct dispatch in ops.select_cpu() or ops.enqueue() can be seen as a shortcut to bypass the scheduler).

Right, skipping ops.dequeue() for direct dispatches makes sense, provided the task is being dispatched to a local/global DSQ. Or at least that's my takeaway after reading Tejun's email.

...

Quoted 49 lines
Quoted 35 lines

If I understand the logic correctly, ops.dequeue(SCHED_CHANGE) will be called for a task at most once between it being dispatched and taken off the CPU, even if its properties are changed multiple times while it's on CPU. Is that intentional? I don't see it documented.

To illustrate, assume we have a task p that has been enqueued, dispatched, and is currently running on the CPU, so we have both SCX_TASK_OPS_ENQUEUE and SCX_TASK_DISPATCH_DEQUEUED set in p->scx.flags.

When a property of p is changed while it runs on the CPU, the sequence of calls is:
dequeue_task_scx(p, DEQUEUE_SAVE) => put_prev_task_scx(p) => (change property) => enqueue_task_scx(p, ENQUEUE_RESTORE) => set_next_task_scx(p).

dequeue_task_scx(p, DEQUEUE_SAVE) calls ops_dequeue() which calls ops.dequeue(p, ... | SCHED_CHANGE) and clears SCX_TASK_{OPS_ENQUEUED,DISPATCH_DEQUEUED} from p->scx.flags.

put_prev_task_scx(p) doesn't do much because SCX_TASK_QUEUED was cleared by dequeue_task_scx().

enqueue_task_scx(p, ENQUEUE_RESTORE) sets sticky_cpu because the task is currently running and ENQUEUE_RESTORE is set. This causes do_enqueue_task() to jump straight to local_norefill, skipping the call to ops.enqueue(), leaving SCX_TASK_OPS_ENQUEUED unset, and then enqueueing the task on the local DSQ.

set_next_task_scx(p) calls ops_dequeue(p, SCX_DEQ_CORE_SCHED_EXEC) even though this is not a core-sched pick, but it won't do much because the ops_state is SCX_OPSS_NONE and SCX_TASK_OPS_ENQUEUED is unset. It also calls dispatch_dequeue(p) which the removes the task from the local DSQ it was just inserted into.

Quoted 7 lines

So, we end up in a state where any subsequent property change while the task is still on CPU will not result in ops.dequeue(p, ... | SCHED_CHANGE) being called, because both SCX_TASK_OPS_ENQUEUED and SCX_TASK_DISPATCH_DEQUEUED are unset in p->scx.flags.

I really hope I didn't mess anything up when tracing the code, but of course I'm happy to be corrected.

Correct. And the enqueue/dequeue balancing is preserved here. In the scenario you describe, subsequent property changes while the task remains running go through ENQUEUE_RESTORE, which intentionally skips ops.enqueue(). Since no new enqueue cycle is started, there is no corresponding ops.dequeue() to deliver either.

Quoted 4 lines

In other words, SCX_DEQ_SCHED_CHANGE is associated with invalidating the scheduler state established by the last ops.enqueue(), not with every individual property change. Multiple property changes while the task stays on CPU are coalesced and the enqueue/dequeue pairing remains balanced.

Ok, I think I understand the logic behind this, here's how I understand it:

The BPF scheduler is naturally going to have some internal per-task state. That state may be expensive to compute from scratch, so we don't want to completely discard it when the BPF scheduler loses ownership of the task.

ops.dequeue(SCHED_CHANGE) serves as a notification to the BPF scheduler:
"Hey, some scheduling properties of the task are about to change, so you probably should invalidate whatever state you have for that task which depends on these properties."

That way, the BPF scheduler will know to recompute the invalidated state on the next ops.enqueue(). If there was no call to ops.dequeue(SCHED_CHANGE), the BPF scheduler knows that none of the task's fundamental scheduling properties (priority, cpu, cpumask, etc.) changed, so it can potentially skip recomputing the state. Of course, the potential for savings depends on the particular scheduler's policy.

This also explains why we only get one call to ops.dequeue(SCHED_CHANGE) while a task is running: for subsequent calls, the BPF scheduler had already been notified to invalidate its state, so there's no use in notifying it again.

However, I feel like there's a hidden assumption here that the BPF scheduler doesn't recompute its state for the task before the next ops.enqueue(). What if the scheduler wanted to immediately react to the priority of a task being decreased by preempting it? You might say "hook into ops.set_weight()", but then doesn't that obviate the need for ops.dequeue(SCHED_CHANGE)?

I guess it could be argued that ops.dequeue(SCHED_CHANGE) covers property changes that happen under ``scoped_guard (sched_change, ...)`` which don't have a dedicated ops callback, but I wasn't able to find any such properties which would be relevant to SCX.

Another thought on the design: currently, the exact meaning of ops.dequeue(SCHED_CHANGE) depends on whether the task is owned by the BPF scheduler:

* When it's owned, it combines two notifications: BPF scheduler losing ownership AND that it should invalidate task state.
* When it's not owned, it only serves as an "invalidate" notification, the ownership status doesn't change.

Wouldn't it be more elegant to have another callback, say ops.property_change(), which would only serve as the "invalidate" notification, and leave ops.dequeue() only for tracking ownership?
That would mean calling ops.dequeue() followed by ops.property_change() when changing properties of a task owned by the BPF scheduler, as opposed to a single call to ops.dequeue(SCHED_CHANGE).

But honestly, when I put it like this, it gets harder to justify having this callback over just using ops.set_weight() etc.

Quoted 8 lines

I agree this distinction isn't obvious from the current documentation, I'll clarify that SCX_DEQ_SCHED_CHANGE is edge-triggered per enqueue/run cycle, not per property change.

Do you see any practical use case where it'd be beneficial to tie individual ops.dequeue() calls to every property change, as opposed to the current coalesced behavior??

I don't know how practical it is, but in my comment above I mention a BPF scheduler wanting to immediately preempt a running task on priority decrease, but in that case we need to hook into ops.set_weight() anyway to find out whether the priority was decreased.

Thanks,
Kuba

author reviewer
#6 lore raw

Hi Kuba,

On Fri, Jan 30, 2026 at 01:14:23PM +0000, Kuba Piecuch wrote:
...

Quoted 55 lines
Quoted 48 lines
Quoted 34 lines

If I understand the logic correctly, ops.dequeue(SCHED_CHANGE) will be called for a task at most once between it being dispatched and taken off the CPU, even if its properties are changed multiple times while it's on CPU. Is that intentional? I don't see it documented.

To illustrate, assume we have a task p that has been enqueued, dispatched, and is currently running on the CPU, so we have both SCX_TASK_OPS_ENQUEUE and SCX_TASK_DISPATCH_DEQUEUED set in p->scx.flags.

When a property of p is changed while it runs on the CPU, the sequence of calls is:
dequeue_task_scx(p, DEQUEUE_SAVE) => put_prev_task_scx(p) => (change property) => enqueue_task_scx(p, ENQUEUE_RESTORE) => set_next_task_scx(p).

dequeue_task_scx(p, DEQUEUE_SAVE) calls ops_dequeue() which calls ops.dequeue(p, ... | SCHED_CHANGE) and clears SCX_TASK_{OPS_ENQUEUED,DISPATCH_DEQUEUED} from p->scx.flags.

put_prev_task_scx(p) doesn't do much because SCX_TASK_QUEUED was cleared by dequeue_task_scx().

enqueue_task_scx(p, ENQUEUE_RESTORE) sets sticky_cpu because the task is currently running and ENQUEUE_RESTORE is set. This causes do_enqueue_task() to jump straight to local_norefill, skipping the call to ops.enqueue(), leaving SCX_TASK_OPS_ENQUEUED unset, and then enqueueing the task on the local DSQ.

set_next_task_scx(p) calls ops_dequeue(p, SCX_DEQ_CORE_SCHED_EXEC) even though this is not a core-sched pick, but it won't do much because the ops_state is SCX_OPSS_NONE and SCX_TASK_OPS_ENQUEUED is unset. It also calls dispatch_dequeue(p) which the removes the task from the local DSQ it was just inserted into.

Quoted 7 lines

So, we end up in a state where any subsequent property change while the task is still on CPU will not result in ops.dequeue(p, ... | SCHED_CHANGE) being called, because both SCX_TASK_OPS_ENQUEUED and SCX_TASK_DISPATCH_DEQUEUED are unset in p->scx.flags.

I really hope I didn't mess anything up when tracing the code, but of course I'm happy to be corrected.

Correct. And the enqueue/dequeue balancing is preserved here. In the scenario you describe, subsequent property changes while the task remains running go through ENQUEUE_RESTORE, which intentionally skips ops.enqueue(). Since no new enqueue cycle is started, there is no corresponding ops.dequeue() to deliver either.

Quoted 4 lines

In other words, SCX_DEQ_SCHED_CHANGE is associated with invalidating the scheduler state established by the last ops.enqueue(), not with every individual property change. Multiple property changes while the task stays on CPU are coalesced and the enqueue/dequeue pairing remains balanced.

Ok, I think I understand the logic behind this, here's how I understand it:

Quoted 8 lines

The BPF scheduler is naturally going to have some internal per-task state. That state may be expensive to compute from scratch, so we don't want to completely discard it when the BPF scheduler loses ownership of the task.

ops.dequeue(SCHED_CHANGE) serves as a notification to the BPF scheduler:
"Hey, some scheduling properties of the task are about to change, so you probably should invalidate whatever state you have for that task which depends on these properties."

Correct. And it's also a way to notify that the task has left the BPF scheduler, so if the task is stored in any internal queue it can/should be removed.

Quoted 11 lines

That way, the BPF scheduler will know to recompute the invalidated state on the next ops.enqueue(). If there was no call to ops.dequeue(SCHED_CHANGE), the BPF scheduler knows that none of the task's fundamental scheduling properties (priority, cpu, cpumask, etc.) changed, so it can potentially skip recomputing the state. Of course, the potential for savings depends on the particular scheduler's policy.

This also explains why we only get one call to ops.dequeue(SCHED_CHANGE) while a task is running: for subsequent calls, the BPF scheduler had already been notified to invalidate its state, so there's no use in notifying it again.

Actually I think the proper behavior would be to trigger ops.dequeue(SCHED_CHANGE) only when the task is "owned" by the BPF scheduler. While running, tasks are outside the BPF scheduler ownership, so ops.dequeue() shouldn't be triggered at all.

Quoted 3 lines

However, I feel like there's a hidden assumption here that the BPF scheduler doesn't recompute its state for the task before the next ops.enqueue().

And that should be the proper behavior. BPF scheduler should recompute a task state only when the task is re-enqueued after a property change.

Quoted 4 lines

What if the scheduler wanted to immediately react to the priority of a task being decreased by preempting it? You might say "hook into ops.set_weight()", but then doesn't that obviate the need for ops.dequeue(SCHED_CHANGE)?

If a scheduler wants to implement preemption on property change, it can do so in ops.enqueue(): after a property change, the task is re-enqueued, triggering ops.enqueue(), at which point the BPF scheduler can decide whether and how to preempt currently running tasks.

If a property change does not result in an ops.enqueue() call, it means the task is not runnable yet (or does not intend to run), so attempting to trigger a preemption at that point would be pointless.

Quoted 6 lines

I guess it could be argued that ops.dequeue(SCHED_CHANGE) covers property changes that happen under ``scoped_guard (sched_change, ...)`` which don't have a dedicated ops callback, but I wasn't able to find any such properties which would be relevant to SCX.

Quoted 8 lines

Another thought on the design: currently, the exact meaning of ops.dequeue(SCHED_CHANGE) depends on whether the task is owned by the BPF scheduler:

* When it's owned, it combines two notifications: BPF scheduler losing ownership AND that it should invalidate task state.
* When it's not owned, it only serves as an "invalidate" notification, the ownership status doesn't change.

When it's not owned I think ops.dequeue() shouldn't be triggered at all.

Quoted 7 lines

Wouldn't it be more elegant to have another callback, say ops.property_change(), which would only serve as the "invalidate" notification, and leave ops.dequeue() only for tracking ownership?
That would mean calling ops.dequeue() followed by ops.property_change() when changing properties of a task owned by the BPF scheduler, as opposed to a single call to ops.dequeue(SCHED_CHANGE).

We could provide an ops.property_change(), but honestly I don't see any practical usage of this callback.

Thanks,
-Andrea

#7 lore raw

Hi Andrea,

Quoted 59 lines · Andrea Righi
Quoted 59 lines
Quoted 48 lines
Quoted 34 lines

If I understand the logic correctly, ops.dequeue(SCHED_CHANGE) will be called for a task at most once between it being dispatched and taken off the CPU, even if its properties are changed multiple times while it's on CPU. Is that intentional? I don't see it documented.

To illustrate, assume we have a task p that has been enqueued, dispatched, and is currently running on the CPU, so we have both SCX_TASK_OPS_ENQUEUE and SCX_TASK_DISPATCH_DEQUEUED set in p->scx.flags.

When a property of p is changed while it runs on the CPU, the sequence of calls is:
dequeue_task_scx(p, DEQUEUE_SAVE) => put_prev_task_scx(p) => (change property) => enqueue_task_scx(p, ENQUEUE_RESTORE) => set_next_task_scx(p).

dequeue_task_scx(p, DEQUEUE_SAVE) calls ops_dequeue() which calls ops.dequeue(p, ... | SCHED_CHANGE) and clears SCX_TASK_{OPS_ENQUEUED,DISPATCH_DEQUEUED} from p->scx.flags.

put_prev_task_scx(p) doesn't do much because SCX_TASK_QUEUED was cleared by dequeue_task_scx().

enqueue_task_scx(p, ENQUEUE_RESTORE) sets sticky_cpu because the task is currently running and ENQUEUE_RESTORE is set. This causes do_enqueue_task() to jump straight to local_norefill, skipping the call to ops.enqueue(), leaving SCX_TASK_OPS_ENQUEUED unset, and then enqueueing the task on the local DSQ.

set_next_task_scx(p) calls ops_dequeue(p, SCX_DEQ_CORE_SCHED_EXEC) even though this is not a core-sched pick, but it won't do much because the ops_state is SCX_OPSS_NONE and SCX_TASK_OPS_ENQUEUED is unset. It also calls dispatch_dequeue(p) which the removes the task from the local DSQ it was just inserted into.

Quoted 7 lines

So, we end up in a state where any subsequent property change while the task is still on CPU will not result in ops.dequeue(p, ... | SCHED_CHANGE) being called, because both SCX_TASK_OPS_ENQUEUED and SCX_TASK_DISPATCH_DEQUEUED are unset in p->scx.flags.

I really hope I didn't mess anything up when tracing the code, but of course I'm happy to be corrected.

Correct. And the enqueue/dequeue balancing is preserved here. In the scenario you describe, subsequent property changes while the task remains running go through ENQUEUE_RESTORE, which intentionally skips ops.enqueue(). Since no new enqueue cycle is started, there is no corresponding ops.dequeue() to deliver either.

Quoted 4 lines

In other words, SCX_DEQ_SCHED_CHANGE is associated with invalidating the scheduler state established by the last ops.enqueue(), not with every individual property change. Multiple property changes while the task stays on CPU are coalesced and the enqueue/dequeue pairing remains balanced.

Ok, I think I understand the logic behind this, here's how I understand it:

The BPF scheduler is naturally going to have some internal per-task state. That state may be expensive to compute from scratch, so we don't want to completely discard it when the BPF scheduler loses ownership of the task.

Quoted 8 lines
Quoted 4 lines

ops.dequeue(SCHED_CHANGE) serves as a notification to the BPF scheduler:
"Hey, some scheduling properties of the task are about to change, so you probably should invalidate whatever state you have for that task which depends on these properties."

Correct. And it's also a way to notify that the task has left the BPF scheduler, so if the task is stored in any internal queue it can/should be removed.

Right, unless the task has already been dispatched, in which case it's just an invalidation notification.

Quoted 9 lines
Quoted 9 lines

That way, the BPF scheduler will know to recompute the invalidated state on the next ops.enqueue(). If there was no call to ops.dequeue(SCHED_CHANGE), the BPF scheduler knows that none of the task's fundamental scheduling properties (priority, cpu, cpumask, etc.) changed, so it can potentially skip recomputing the state. Of course, the potential for savings depends on the particular scheduler's policy.

Quoted 9 lines
Quoted 3 lines

This also explains why we only get one call to ops.dequeue(SCHED_CHANGE) while a task is running: for subsequent calls, the BPF scheduler had already been notified to invalidate its state, so there's no use in notifying it again.

Actually I think the proper behavior would be to trigger ops.dequeue(SCHED_CHANGE) only when the task is "owned" by the BPF scheduler. While running, tasks are outside the BPF scheduler ownership, so ops.dequeue() shouldn't be triggered at all.

I don't think this is what the current implementation does, right?

Quoted 7 lines
Quoted 3 lines

However, I feel like there's a hidden assumption here that the BPF scheduler doesn't recompute its state for the task before the next ops.enqueue().

And that should be the proper behavior. BPF scheduler should recompute a task state only when the task is re-enqueued after a property change.

That would make sense if ops.enqueue() was called immediately after a property change when a task is running, but I believe that's currently not the case, see my attempt at tracing the enqueue-dequeue cycle on property change in my first reply.

Quoted 5 lines
Quoted 4 lines

What if the scheduler wanted to immediately react to the priority of a task being decreased by preempting it? You might say "hook into ops.set_weight()", but then doesn't that obviate the need for ops.dequeue(SCHED_CHANGE)?

Quoted 9 lines

If a scheduler wants to implement preemption on property change, it can do so in ops.enqueue(): after a property change, the task is re-enqueued, triggering ops.enqueue(), at which point the BPF scheduler can decide whether and how to preempt currently running tasks.

If a property change does not result in an ops.enqueue() call, it means the task is not runnable yet (or does not intend to run), so attempting to trigger a preemption at that point would be pointless.

IIUC a dequeue-enqueue cycle on a running task during property change doesn't result in a call to ops.enqueue(), so if the BPF scheduler recomputed its state only in ops.enqueue(), then it wouldn't be able to react immediately.

Quoted 25 lines
Quoted 6 lines

I guess it could be argued that ops.dequeue(SCHED_CHANGE) covers property changes that happen under ``scoped_guard (sched_change, ...)`` which don't have a dedicated ops callback, but I wasn't able to find any such properties which would be relevant to SCX.

Quoted 8 lines

Another thought on the design: currently, the exact meaning of ops.dequeue(SCHED_CHANGE) depends on whether the task is owned by the BPF scheduler:

* When it's owned, it combines two notifications: BPF scheduler losing ownership AND that it should invalidate task state.
* When it's not owned, it only serves as an "invalidate" notification, the ownership status doesn't change.

When it's not owned I think ops.dequeue() shouldn't be triggered at all.

Quoted 7 lines

Wouldn't it be more elegant to have another callback, say ops.property_change(), which would only serve as the "invalidate" notification, and leave ops.dequeue() only for tracking ownership?
That would mean calling ops.dequeue() followed by ops.property_change() when changing properties of a task owned by the BPF scheduler, as opposed to a single call to ops.dequeue(SCHED_CHANGE).

Quoted 3 lines

We could provide an ops.property_change(), but honestly I don't see any practical usage of this callback.

Neither do I, I just made it up for the sake of argument :-)

Thanks,
Kuba

author reviewer
#8 lore raw

Hi Kuba,

On Sat, Jan 31, 2026 at 04:45:59PM +0000, Kuba Piecuch wrote:
...

Quoted 9 lines
Quoted 9 lines
Quoted 8 lines

The BPF scheduler is naturally going to have some internal per-task state. That state may be expensive to compute from scratch, so we don't want to completely discard it when the BPF scheduler loses ownership of the task.

ops.dequeue(SCHED_CHANGE) serves as a notification to the BPF scheduler:
"Hey, some scheduling properties of the task are about to change, so you probably should invalidate whatever state you have for that task which depends on these properties."

Quoted 6 lines
Quoted 3 lines

Correct. And it's also a way to notify that the task has left the BPF scheduler, so if the task is stored in any internal queue it can/should be removed.

Right, unless the task has already been dispatched, in which case it's just an invalidation notification.

Right, but if the task has already been dispatched I don't think we should trigger ops.dequeue(SCHED_CHANGE), because it's not anymore under the BPF scheduler's custody (not the way it's implemented right now, I'm just trying to define the proper semantics based on the latest disussions).

Quoted 11 lines
Quoted 11 lines
Quoted 10 lines

That way, the BPF scheduler will know to recompute the invalidated state on the next ops.enqueue(). If there was no call to ops.dequeue(SCHED_CHANGE), the BPF scheduler knows that none of the task's fundamental scheduling properties (priority, cpu, cpumask, etc.) changed, so it can potentially skip recomputing the state. Of course, the potential for savings depends on the particular scheduler's policy.

This also explains why we only get one call to ops.dequeue(SCHED_CHANGE) while a task is running: for subsequent calls, the BPF scheduler had already been notified to invalidate its state, so there's no use in notifying it again.

Quoted 7 lines
Quoted 5 lines

Actually I think the proper behavior would be to trigger ops.dequeue(SCHED_CHANGE) only when the task is "owned" by the BPF scheduler. While running, tasks are outside the BPF scheduler ownership, so ops.dequeue() shouldn't be triggered at all.

I don't think this is what the current implementation does, right?

Right, sorry, I wasn't clear. I'm just trying to define the behavior that makes more sense (see below).

Quoted 11 lines
Quoted 6 lines
Quoted 2 lines

However, I feel like there's a hidden assumption here that the BPF scheduler doesn't recompute its state for the task before the next ops.enqueue().

And that should be the proper behavior. BPF scheduler should recompute a task state only when the task is re-enqueued after a property change.

That would make sense if ops.enqueue() was called immediately after a property change when a task is running, but I believe that's currently not the case, see my attempt at tracing the enqueue-dequeue cycle on property change in my first reply.

Yeah, that's right.

I have a new patch set where I've implemented the following semantics (that should match also Tejun's requirements).

With the new semantics:
- for running tasks: property changes do NOT trigger ops.dequeue(SCHED_CHANGE)
- once a task leaves BPF custody (dispatched to local DSQ), the BPF scheduler no longer manages it
- property changes on running tasks don't affect the BPF scheduler

Key principle: ops.dequeue() is only called when a task leaves BPF scheduler's custody. A running task has already left BPF custody, so property changes don't trigger ops.dequeue().

Therefore, ops.dequeue(SCHED_CHANGE) gets called only when:
- task is in BPF data structures (QUEUED state), or
- task is on a non-local DSQ (still in BPF custody)

In this case (BPF scheduler custody), if a property change happens, ops.dequeue(SCHED_CHANGE) is called to notify the BPF scheduler.

Then if you want to react immediately on priority changes for running tasks we have:
- ops.set_cpumask(): CPU affinity changes
- ops.set_weight(): priority/nice changes
- ops.cgroup_*(): cgroup changes

In conclusion, we don't need ops.dequeue(SCHED_CHANGE) for running tasks, the dedicated callbacks (ops.set_cpumask(), ops.set_weight(), ...) already provide comprehensive coverage for property changes on all tasks, regardless of whether they're running or in BPF custody. And the new ops.dequeue(SCHED_CHANGE) semantics only notifies for property changes when tasks are actively managed by the BPF scheduler (in QUEUED state or on non-local DSQs).

Do you think it's reasonable enough / do you see any flaws?

Thanks,
-Andrea

reviewer
#9 lore raw
In reply to Andrea Righi

Hello,

Quoted 7 lines · Andrea Righi
kernel/sched/ext.c +3 -0
@@ -1287,6 +1287,20 @@ static void direct_dispatch(struct scx_sched *sch, struct task_struct *p,
 
 	p->scx.ddsp_enq_flags |= enq_flags;
 
+	/*
+	 * The task is about to be dispatched. If ops.enqueue() was called,
+	 * notify the BPF scheduler by calling ops.dequeue().

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

Quoted 10 lines
kernel/sched/ext.c +10 -0
+	 *
+	 * Keep %SCX_TASK_OPS_ENQUEUED set so that subsequent property
+	 * changes can trigger ops.dequeue() with %SCX_DEQ_SCHED_CHANGE.
+	 * Mark that the dispatch dequeue has been called to distinguish
+	 * from property change dequeues.
+	 */
+	if (SCX_HAS_OP(sch, dequeue) && (p->scx.flags & SCX_TASK_OPS_ENQUEUED)) {
+		SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq, p, 0);
+		p->scx.flags |= SCX_TASK_DISPATCH_DEQUEUED;
+	}

1. When to call ops.dequeue()?

I'm not sure whether deciding whether to call ops.dequeue() solely onwhether ops.enqueue() was called. Direct dispatch has been expanded to include other DSQs but was originally added as a way to shortcut the dispatch path and "dispatch directly" for execution from ops.select_cpu/enqueue() paths. ie. When a task is dispatched directly to a local DSQ, the BPF scheduler is done with that task - the task is now in the same state with tasks that get dispatched to a local DSQ from ops.dispatch().

ie. What effectively decides whether a task left the BPF scheduler is whether the task reached a local DSQ or not, and direct dispatching into a local DSQ shouldn't trigger ops.dequeue() - the task never really "queues" on the BPF scheduler.

This creates another discrepancy - From ops.enqueue(), direct dispatching into a non-local DSQ clearly makes the task enter the BPF scheduler and thus its departure should trigger ops.dequeue(). What about a task which is direct dispatched to a non-local DSQ from ops.select_cpu()? Superficially, the right thing to do seems to skip ops.dequeue(). After all, the task has never been ops.enqueue()'d. However, I think this is another case where what's obvious doesn't agree with what's happening underneath.

ops.select_cpu() cannot actually queue anything. It's too early. Direct dispatch from ops.select_cpu() is a shortcut to schedule direct dispatch once the enqueue path is invoked so that the BPF scheudler can avoid invocation of ops.enqueue() when the decision has already been made. While this shortcut was added for convenience (so that e.g. the BPF scheduler doesn't have to pass a note from ops.select_cpu() to ops.enqueue()), it has real performance implications as it does save a roundtrip through ops.enqueue() and we know that such overheads do matter for some use cases (e.g. maximizing FPS on certain games).

So, while more subtle on the surface, I think the right thing to do is basing the decision to call ops.dequeue() on the task's actual state - ops.dequeue() should be called if the task is "on" the BPF scheduler - ie. if the task ran ops.select_cpu/enqueue() paths and ended up in a non-local DSQ or on the BPF side.

The subtlety would need clear documentation and we probably want to allow ops.dequeue() to distinguish different cases. If you boil it down to the actual task state, I don't think it's that subtle - if a task is in the custody of the BPF scheduler, ops.dequeue() will be called. Otherwise, not. Note that, this way, whether ops.dequeue() needs to be called agrees with whether the task needs to be dispatched to run.

2. Why keep %SCX_TASK_OPS_ENQUEUED for %SCX_DEQ_SCHED_CHANGE?

Wouldn't that lead to calling ops.dequeue() more than once for the same enqueue event? If the BPF scheduler is told that the task has left it already, why does it matter whether the task gets dequeued for sched change afterwards? e.g. from the BPF sched's POV, it shouldn't matter whether the task is still on the local DSQ or already running, in which case the sched class's dequeue() wouldn't be called in the first place, no?

Thanks.

Signature · 1 line
tejun
#10 lore raw

Hi Tejun,

On Wed Jan 28, 2026 at 9:21 PM UTC, Tejun Heo wrote:
...

Quoted 10 lines

1. When to call ops.dequeue()?

I'm not sure whether deciding whether to call ops.dequeue() solely onwhether ops.enqueue() was called. Direct dispatch has been expanded to include other DSQs but was originally added as a way to shortcut the dispatch path and "dispatch directly" for execution from ops.select_cpu/enqueue() paths. ie. When a task is dispatched directly to a local DSQ, the BPF scheduler is done with that task - the task is now in the same state with tasks that get dispatched to a local DSQ from ops.dispatch().

Quoted 4 lines

ie. What effectively decides whether a task left the BPF scheduler is whether the task reached a local DSQ or not, and direct dispatching into a local DSQ shouldn't trigger ops.dequeue() - the task never really "queues" on the BPF scheduler.

Is "local" short for "local or global", i.e. not user-created? Direct dispatching into the global DSQ also shouldn't trigger ops.dequeue(), since dispatch isn't necessary for the task to run. This follows from the last paragraph:

Note that, this way, whether ops.dequeue() needs to be called agrees with whether the task needs to be dispatched to run.

I agree with your points, just wanted to clarify this one thing.

Quoted 25 lines

This creates another discrepancy - From ops.enqueue(), direct dispatching into a non-local DSQ clearly makes the task enter the BPF scheduler and thus its departure should trigger ops.dequeue(). What about a task which is direct dispatched to a non-local DSQ from ops.select_cpu()? Superficially, the right thing to do seems to skip ops.dequeue(). After all, the task has never been ops.enqueue()'d. However, I think this is another case where what's obvious doesn't agree with what's happening underneath.

ops.select_cpu() cannot actually queue anything. It's too early. Direct dispatch from ops.select_cpu() is a shortcut to schedule direct dispatch once the enqueue path is invoked so that the BPF scheudler can avoid invocation of ops.enqueue() when the decision has already been made. While this shortcut was added for convenience (so that e.g. the BPF scheduler doesn't have to pass a note from ops.select_cpu() to ops.enqueue()), it has real performance implications as it does save a roundtrip through ops.enqueue() and we know that such overheads do matter for some use cases (e.g. maximizing FPS on certain games).

So, while more subtle on the surface, I think the right thing to do is basing the decision to call ops.dequeue() on the task's actual state - ops.dequeue() should be called if the task is "on" the BPF scheduler - ie. if the task ran ops.select_cpu/enqueue() paths and ended up in a non-local DSQ or on the BPF side.

Quoted 6 lines

The subtlety would need clear documentation and we probably want to allow ops.dequeue() to distinguish different cases. If you boil it down to the actual task state, I don't think it's that subtle - if a task is in the custody of the BPF scheduler, ops.dequeue() will be called. Otherwise, not. Note that, this way, whether ops.dequeue() needs to be called agrees with whether the task needs to be dispatched to run.

Here's my attempt at documenting this behavior:

After ops.enqueue() is called on a task, the task is owned by the BPF scheduler, provided the task wasn't direct-dispatched to a local/global DSQ. When a task is owned by the BPF scheduler, the scheduler needs to dispatch the task to a local/global DSQ in order for it to run.
When the BPF scheduler loses ownership of the task, either due to dispatching it to a local/global DSQ or due to external events (core-sched pick, CPU migration, scheduling property changes), the BPF scheduler is notified through ops.dequeue() with appropriate flags (TBD).

Thanks,
Kuba

author reviewer
#11 lore raw
Quoted 24 lines · Kuba Piecuch

Hi Tejun,

On Wed Jan 28, 2026 at 9:21 PM UTC, Tejun Heo wrote:
...

Quoted 10 lines

1. When to call ops.dequeue()?

I'm not sure whether deciding whether to call ops.dequeue() solely onwhether ops.enqueue() was called. Direct dispatch has been expanded to include other DSQs but was originally added as a way to shortcut the dispatch path and "dispatch directly" for execution from ops.select_cpu/enqueue() paths. ie. When a task is dispatched directly to a local DSQ, the BPF scheduler is done with that task - the task is now in the same state with tasks that get dispatched to a local DSQ from ops.dispatch().

Quoted 4 lines

ie. What effectively decides whether a task left the BPF scheduler is whether the task reached a local DSQ or not, and direct dispatching into a local DSQ shouldn't trigger ops.dequeue() - the task never really "queues" on the BPF scheduler.

Is "local" short for "local or global", i.e. not user-created? Direct dispatching into the global DSQ also shouldn't trigger ops.dequeue(), since dispatch isn't necessary for the task to run. This follows from the last paragraph:

Quoted 4 lines

Note that, this way, whether ops.dequeue() needs to be called agrees with whether the task needs to be dispatched to run.

I agree with your points, just wanted to clarify this one thing.

I think this should be interpreted as local DSQs only (SCX_DSQ_LOCAL / SCX_DSQ_LOCAL_ON), not any built-in DSQ. SCX_DSQ_GLOBAL is essentially a built-in user DSQ, provided for convenience, it's not really a "direct dispatch" DSQ.

Quoted 35 lines
Quoted 26 lines

This creates another discrepancy - From ops.enqueue(), direct dispatching into a non-local DSQ clearly makes the task enter the BPF scheduler and thus its departure should trigger ops.dequeue(). What about a task which is direct dispatched to a non-local DSQ from ops.select_cpu()? Superficially, the right thing to do seems to skip ops.dequeue(). After all, the task has never been ops.enqueue()'d. However, I think this is another case where what's obvious doesn't agree with what's happening underneath.

ops.select_cpu() cannot actually queue anything. It's too early. Direct dispatch from ops.select_cpu() is a shortcut to schedule direct dispatch once the enqueue path is invoked so that the BPF scheudler can avoid invocation of ops.enqueue() when the decision has already been made. While this shortcut was added for convenience (so that e.g. the BPF scheduler doesn't have to pass a note from ops.select_cpu() to ops.enqueue()), it has real performance implications as it does save a roundtrip through ops.enqueue() and we know that such overheads do matter for some use cases (e.g. maximizing FPS on certain games).

So, while more subtle on the surface, I think the right thing to do is basing the decision to call ops.dequeue() on the task's actual state - ops.dequeue() should be called if the task is "on" the BPF scheduler - ie. if the task ran ops.select_cpu/enqueue() paths and ended up in a non-local DSQ or on the BPF side.

Quoted 6 lines

The subtlety would need clear documentation and we probably want to allow ops.dequeue() to distinguish different cases. If you boil it down to the actual task state, I don't think it's that subtle - if a task is in the custody of the BPF scheduler, ops.dequeue() will be called. Otherwise, not. Note that, this way, whether ops.dequeue() needs to be called agrees with whether the task needs to be dispatched to run.

Here's my attempt at documenting this behavior:

Quoted 8 lines

After ops.enqueue() is called on a task, the task is owned by the BPF scheduler, provided the task wasn't direct-dispatched to a local/global DSQ. When a task is owned by the BPF scheduler, the scheduler needs to dispatch the task to a local/global DSQ in order for it to run.
When the BPF scheduler loses ownership of the task, either due to dispatching it to a local/global DSQ or due to external events (core-sched pick, CPU migration, scheduling property changes), the BPF scheduler is notified through ops.dequeue() with appropriate flags (TBD).

This looks good overall, except for the global DSQ part. Also, it might be better to avoid the term “owned”, internally the kernel already uses the concept of "task ownership" with a different meaning (see
https://lore.kernel.org/all/[email protected]), and reusing it here could be misleading.

With that in mind, I'd probably rephrase your documentation along these lines:

After ops.enqueue() is called, the task is considered *enqueued* by the BPF scheduler, unless it is directly dispatched to a local DSQ (via SCX_DSQ_LOCAL or SCX_DSQ_LOCAL_ON).

While a task is enqueued, the BPF scheduler must explicitly dispatch it to a DSQ in order for it to run.

When a task leaves the enqueued state (either because it is dispatched to a non-local DSQ, or due to external events such as a core-sched pick, CPU migration, or scheduling property changes), ops.dequeue() is invoked to notify the BPF scheduler, with flags indicating the reason for the dequeue:
regular dispatch dequeues have no flags set, whereas dequeues triggered by scheduling property changes are reported with SCX_DEQ_SCHED_CHANGE.

What do you think?

Thanks,
-Andrea

#12 lore raw
Quoted 9 lines · Andrea Righi
Quoted 8 lines · Kuba Piecuch

Is "local" short for "local or global", i.e. not user-created? Direct dispatching into the global DSQ also shouldn't trigger ops.dequeue(), since dispatch isn't necessary for the task to run. This follows from the last paragraph:

Note that, this way, whether ops.dequeue() needs to be called agrees with whether the task needs to be dispatched to run.

Quoted 6 lines
Quoted 1 line

I agree with your points, just wanted to clarify this one thing.

I think this should be interpreted as local DSQs only (SCX_DSQ_LOCAL / SCX_DSQ_LOCAL_ON), not any built-in DSQ. SCX_DSQ_GLOBAL is essentially a built-in user DSQ, provided for convenience, it's not really a "direct dispatch" DSQ.

SCX_DSQ_GLOBAL is significantly different from user DSQs, because balance_one() can pull tasks directly from SCX_DSQ_GLOBAL, while it cannot pull tasks from user-created DSQs.

If a BPF scheduler puts a task onto SCX_DSQ_GLOBAL, then it _must_ be ok with balance_one() coming along and pulling that task without the BPF scheduler's intervention, so in that way I believe SCX_DSQ_GLOBAL is semantically quite similar to local DSQs.

Quoted 24 lines
Quoted 10 lines

Here's my attempt at documenting this behavior:

After ops.enqueue() is called on a task, the task is owned by the BPF scheduler, provided the task wasn't direct-dispatched to a local/global DSQ. When a task is owned by the BPF scheduler, the scheduler needs to dispatch the task to a local/global DSQ in order for it to run.
When the BPF scheduler loses ownership of the task, either due to dispatching it to a local/global DSQ or due to external events (core-sched pick, CPU migration, scheduling property changes), the BPF scheduler is notified through ops.dequeue() with appropriate flags (TBD).

This looks good overall, except for the global DSQ part. Also, it might be better to avoid the term “owned”, internally the kernel already uses the concept of "task ownership" with a different meaning (see
https://lore.kernel.org/all/[email protected]), and reusing it here could be misleading.

With that in mind, I'd probably rephrase your documentation along these lines:

After ops.enqueue() is called, the task is considered *enqueued* by the BPF scheduler, unless it is directly dispatched to a local DSQ (via SCX_DSQ_LOCAL or SCX_DSQ_LOCAL_ON).

Quoted 5 lines

While a task is enqueued, the BPF scheduler must explicitly dispatch it to a DSQ in order for it to run.

When a task leaves the enqueued state (either because it is dispatched to a non-local DSQ, or due to external events such as a core-sched pick, CPU

Shouldn't it be "dispatched to a local DSQ"?

Quoted 4 lines

migration, or scheduling property changes), ops.dequeue() is invoked to notify the BPF scheduler, with flags indicating the reason for the dequeue:
regular dispatch dequeues have no flags set, whereas dequeues triggered by scheduling property changes are reported with SCX_DEQ_SCHED_CHANGE.

Core-sched dequeues also have a dedicated flag, it should probably be included here.

Quoted 2 lines

What do you think?

I think using the term "enqueued" isn't very good either since it results in two ways in which a task can be considered enqueued:

1. Between ops.enqueue() and ops.dequeue()
2. Between enqueue_task_scx() and dequeue_task_scx()

The two are not equivalent, since a task that's running is not enqueued according to 1. but is enqueued according to 2.

I would be ok with it if we change it to something unambiguous, e.g. "BPF-enqueued", although that poses a risk of people getting lazy and using "enqueued" anyway.

Some potential alternative terms: "resident"/"BPF-resident", "managed"/"BPF-managed", "dispatchable", "pending dispatch", or simply "pending".

Thanks,
Kuba

author reviewer
#13 lore raw
Quoted 17 lines · Kuba Piecuch
Quoted 9 lines · Andrea Righi
Quoted 8 lines · Kuba Piecuch

Is "local" short for "local or global", i.e. not user-created? Direct dispatching into the global DSQ also shouldn't trigger ops.dequeue(), since dispatch isn't necessary for the task to run. This follows from the last paragraph:

Note that, this way, whether ops.dequeue() needs to be called agrees with whether the task needs to be dispatched to run.

Quoted 6 lines
Quoted 1 line

I agree with your points, just wanted to clarify this one thing.

I think this should be interpreted as local DSQs only (SCX_DSQ_LOCAL / SCX_DSQ_LOCAL_ON), not any built-in DSQ. SCX_DSQ_GLOBAL is essentially a built-in user DSQ, provided for convenience, it's not really a "direct dispatch" DSQ.

Quoted 8 lines

SCX_DSQ_GLOBAL is significantly different from user DSQs, because balance_one() can pull tasks directly from SCX_DSQ_GLOBAL, while it cannot pull tasks from user-created DSQs.

If a BPF scheduler puts a task onto SCX_DSQ_GLOBAL, then it _must_ be ok with balance_one() coming along and pulling that task without the BPF scheduler's intervention, so in that way I believe SCX_DSQ_GLOBAL is semantically quite similar to local DSQs.

I agree that SCX_DSQ_GLOBAL behaves differently from user-created DSQs at the implementation level, but I think that difference shouldn't leak into the logical model.

From a semantic point of view, dispatching a task to SCX_DSQ_GLOBAL does not mean that the task leaves the "enqueued by BPF" state. The task is still under the BPF scheduler's custody, not directly dispatched to a specific CPU, and remains sched_ext-managed. The scheduler has queued the task and it hasn't relinquished control over it.

That said, I don't have a strong opinion here. If we prefer to treat SCX_DSQ_GLOBAL as a "direct dispatch" DSQ for the purposes of ops.dequeue() semantics, then I'm fine with adjusting the logic accordingly (with proper documentation).

Tejun, thoughts?

Quoted 25 lines
Quoted 25 lines
Quoted 11 lines

Here's my attempt at documenting this behavior:

After ops.enqueue() is called on a task, the task is owned by the BPF scheduler, provided the task wasn't direct-dispatched to a local/global DSQ. When a task is owned by the BPF scheduler, the scheduler needs to dispatch the task to a local/global DSQ in order for it to run.
When the BPF scheduler loses ownership of the task, either due to dispatching it to a local/global DSQ or due to external events (core-sched pick, CPU migration, scheduling property changes), the BPF scheduler is notified through ops.dequeue() with appropriate flags (TBD).

This looks good overall, except for the global DSQ part. Also, it might be better to avoid the term “owned”, internally the kernel already uses the concept of "task ownership" with a different meaning (see
https://lore.kernel.org/all/[email protected]), and reusing it here could be misleading.

With that in mind, I'd probably rephrase your documentation along these lines:

After ops.enqueue() is called, the task is considered *enqueued* by the BPF scheduler, unless it is directly dispatched to a local DSQ (via SCX_DSQ_LOCAL or SCX_DSQ_LOCAL_ON).

Quoted 7 lines
Quoted 5 lines

While a task is enqueued, the BPF scheduler must explicitly dispatch it to a DSQ in order for it to run.

When a task leaves the enqueued state (either because it is dispatched to a non-local DSQ, or due to external events such as a core-sched pick, CPU

Shouldn't it be "dispatched to a local DSQ"?

Oh yes, sorry, it should be "dispatched to a local DSQ, ...".

Quoted 8 lines
Quoted 5 lines

migration, or scheduling property changes), ops.dequeue() is invoked to notify the BPF scheduler, with flags indicating the reason for the dequeue:
regular dispatch dequeues have no flags set, whereas dequeues triggered by scheduling property changes are reported with SCX_DEQ_SCHED_CHANGE.

Core-sched dequeues also have a dedicated flag, it should probably be included here.

Right, core-sched dequeues should be mentioned as well.

Quoted 13 lines
Quoted 3 lines

What do you think?

I think using the term "enqueued" isn't very good either since it results in two ways in which a task can be considered enqueued:

1. Between ops.enqueue() and ops.dequeue()
2. Between enqueue_task_scx() and dequeue_task_scx()

The two are not equivalent, since a task that's running is not enqueued according to 1. but is enqueued according to 2.

Quoted 7 lines

I would be ok with it if we change it to something unambiguous, e.g. "BPF-enqueued", although that poses a risk of people getting lazy and using "enqueued" anyway.

Some potential alternative terms: "resident"/"BPF-resident", "managed"/"BPF-managed", "dispatchable", "pending dispatch", or simply "pending".

I agree that enqueued is a very ambiguous term and we probably need something more BPF-specific. How about a task "under BPF custody"?

Thanks,
-Andrea

reviewer
#14 lore raw

Hello,

Quoted 10 lines · Andrea Righi

I agree that SCX_DSQ_GLOBAL behaves differently from user-created DSQs at the implementation level, but I think that difference shouldn't leak into the logical model.

From a semantic point of view, dispatching a task to SCX_DSQ_GLOBAL does not mean that the task leaves the "enqueued by BPF" state. The task is still under the BPF scheduler's custody, not directly dispatched to a specific CPU, and remains sched_ext-managed. The scheduler has queued the task and it hasn't relinquished control over it.

Quoted 6 lines

That said, I don't have a strong opinion here. If we prefer to treat SCX_DSQ_GLOBAL as a "direct dispatch" DSQ for the purposes of ops.dequeue() semantics, then I'm fine with adjusting the logic accordingly (with proper documentation).

Tejun, thoughts?

I think putting a task into GLOBAL means that the BPF scheduler is done with it. Another data point in this direction is that when insertion into a local DSQ can't be done, the task falls back to the global DSQ although all the current ones also trigger error.

Thanks.

Signature · 1 line
tejun
author reviewer
#15 lore raw
Quoted 18 lines · Tejun Heo

Hello,

Quoted 15 lines · Andrea Righi

I agree that SCX_DSQ_GLOBAL behaves differently from user-created DSQs at the implementation level, but I think that difference shouldn't leak into the logical model.

From a semantic point of view, dispatching a task to SCX_DSQ_GLOBAL does not mean that the task leaves the "enqueued by BPF" state. The task is still under the BPF scheduler's custody, not directly dispatched to a specific CPU, and remains sched_ext-managed. The scheduler has queued the task and it hasn't relinquished control over it.

That said, I don't have a strong opinion here. If we prefer to treat SCX_DSQ_GLOBAL as a "direct dispatch" DSQ for the purposes of ops.dequeue() semantics, then I'm fine with adjusting the logic accordingly (with proper documentation).

Quoted 6 lines
Quoted 1 line

Tejun, thoughts?

I think putting a task into GLOBAL means that the BPF scheduler is done with it. Another data point in this direction is that when insertion into a local DSQ can't be done, the task falls back to the global DSQ although all the current ones also trigger error.

Alright, it seems that the general consensus, based on your feedback and Kuba's, is to treat SCX_DSQ_GLOBAL as a "terminal" DSQ for the purpose of triggering ops.dequeue().

I'll update the logic to do the following:
- When a task is dispatched to SCX_DSQ_GLOBAL, the BPF scheduler is considered done with it (similar to local DSQ dispatches).
- ops.dequeue() will not be called for SCX_DSQ_GLOBAL dispatches.
- This aligns with the fallback behavior where tasks that fail local DSQ insertion end up in the global DSQ as a terminal destination.

Thanks,
-Andrea

reviewer
#16 lore raw
In reply to Kuba Piecuch

Hello,

Sorry about tardiness.

Quoted 1 line · Kuba Piecuch

Is "local" short for "local or global", i.e. not user-created?

Yes, maybe it'd be useful to come up with a terminology for them. e.g. terminal - once a task reaches a terminal DSQ, the only way that the BPF scheduler can affect the task is by triggering re-enqueue (although we don't yet support reenqueueing global DSQs).

Thanks.

Signature · 1 line
tejun
author reviewer
#17 lore raw
Quoted 11 lines · Tejun Heo

Hello,

Sorry about tardiness.

Quoted 1 line · Kuba Piecuch

Is "local" short for "local or global", i.e. not user-created?

Yes, maybe it'd be useful to come up with a terminology for them. e.g. terminal - once a task reaches a terminal DSQ, the only way that the BPF scheduler can affect the task is by triggering re-enqueue (although we don't yet support reenqueueing global DSQs).

I like "terminal DSQ", if there's no objection I'll update the documentation using this terminology.

Thanks,
-Andrea

#18 lore raw
Quoted 11 lines · Andrea Righi
Quoted 7 lines · Tejun Heo
Quoted 1 line · Kuba Piecuch

Is "local" short for "local or global", i.e. not user-created?

Yes, maybe it'd be useful to come up with a terminology for them. e.g. terminal - once a task reaches a terminal DSQ, the only way that the BPF scheduler can affect the task is by triggering re-enqueue (although we don't yet support reenqueueing global DSQs).

I like "terminal DSQ", if there's no objection I'll update the documentation using this terminology.

"Built-in" would also work and avoids introducing new terminology, but it doesn't provide any insight into why these DSQs are special, whereas "terminal" suggests there's some finality to inserting a task there.

I'm slightly leaning towards "terminal".

Thanks,
Kuba

author reviewer
#19 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 that:
- every enqueue is followed by proper dequeue,
- dispatch dequeues happen exactly once per enqueue,
- property change dequeues (%SCX_DEQ_SCHED_CHANGE) only happen for property changes,
- no duplicate enqueues without proper dequeue.

Test scenarios:
- direct dispatch to local DSQ (%SCX_DSQ_LOCAL),
- dispatch to user DSQ,
- explicit property changes via sched_setaffinity().

This validates that the new ops.dequeue() semantics work correctly for all task lifecycle scenarios.

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 | 209 ++++++++++++++++++
 tools/testing/selftests/sched_ext/dequeue.c   | 182 +++++++++++++++
 3 files changed, 392 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 +209 -0

209 lines not on this page · raw message

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

182 lines not on this page · raw message

Signature · 1 line
2.52.0
Reviewed-by on v1 2/2
#20 lore raw

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

Quoted 12 lines · Andrea Righi

Add a new kselftest to validate that:
- every enqueue is followed by proper dequeue,
- dispatch dequeues happen exactly once per enqueue,
- property change dequeues (%SCX_DEQ_SCHED_CHANGE) only happen for property changes,
- no duplicate enqueues without proper dequeue.

Test scenarios:
- direct dispatch to local DSQ (%SCX_DSQ_LOCAL),
- dispatch to user DSQ,
- explicit property changes via sched_setaffinity().

Quoted 7 lines

This validates that the new ops.dequeue() semantics work correctly for all task lifecycle scenarios.

Cc Tejun Heo <[email protected]>
Cc Emil Tsalapatis <[email protected]>
Cc Kuba Piecuch <[email protected]>
Quoted 423 lines
---
 tools/testing/selftests/sched_ext/Makefile    |   1 +
 .../testing/selftests/sched_ext/dequeue.bpf.c | 209 ++++++++++++++++++
 tools/testing/selftests/sched_ext/dequeue.c   | 182 +++++++++++++++
 3 files changed, 392 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 +209 -0
new file mode 100644
index 0000000000000..8b2f792cf7d8b
@@ -0,0 +1,209 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * A scheduler that validates ops.dequeue() is called correctly:
+ * - For tasks on BPF data structures (not yet dispatched)
+ * - For tasks already on DSQs (local or shared)
+ * - That every ops.enqueue() is followed by ops.dequeue()
+ *
+ * Copyright (c) 2025 NVIDIA Corporation.
+ */
+
+#include <scx/common.bpf.h>
+
+#define SHARED_DSQ	0
+
+char _license[] SEC("license") = "GPL";
+
+UEI_DEFINE(uei);
+
+/*
+ * Counters to track the lifecycle of tasks:
+ * - enqueue_cnt: Number of times ops.enqueue() was called
+ * - dequeue_cnt: Number of times ops.dequeue() was called (any type)
+ * - dispatch_dequeue_cnt: Number of regular dispatch dequeues (no flag)
+ * - change_dequeue_cnt: Number of property change dequeues (%SCX_DEQ_SCHED_CHANGE)
+ */
+u64 enqueue_cnt, dequeue_cnt, dispatch_dequeue_cnt, change_dequeue_cnt;
+
+/*
+ * Test scenarios:
+ * - 0: Dispatch to local DSQ
+ * - 1: Dispatch to shared DSQ
+ */
+u32 test_scenario;
+
+/*
+ * Per-task state to track lifecycle and validate workflow semantics.
+ * State transitions:
+ *   NONE -> ENQUEUED (on enqueue)
+ *   ENQUEUED -> DISPATCHED (on dispatch dequeue)
+ *   DISPATCHED -> NONE (on property change dequeue or re-enqueue)
+ *   ENQUEUED -> NONE (on property change dequeue before dispatch)
+ */
+enum task_state {
+	TASK_NONE = 0,      /* Task is outside scheduler control */
+	TASK_ENQUEUED,      /* ops.enqueue() called, waiting for dequeue */
+	TASK_DISPATCHED,    /* Dispatch dequeue received, can get property change or re-enqueue */
+};
+
+struct task_ctx {
+	enum task_state state; /* Current state in the workflow */
+	u64 enqueue_seq;       /* Sequence number for debugging */
+};
+
+struct {
+	__uint(type, BPF_MAP_TYPE_TASK_STORAGE);
+	__uint(map_flags, BPF_F_NO_PREALLOC);
+	__type(key, int);
+	__type(value, struct task_ctx);
+} task_ctx_stor SEC(".maps");
+
+static struct task_ctx *try_lookup_task_ctx(struct task_struct *p)
+{
+	return bpf_task_storage_get(&task_ctx_stor, p, 0, 0);
+}
+
+s32 BPF_STRUCT_OPS(dequeue_select_cpu, struct task_struct *p,
+		   s32 prev_cpu, u64 wake_flags)
+{
+	/* Always bounce to ops.enqueue() */
+	return prev_cpu;
+}
+
+void BPF_STRUCT_OPS(dequeue_enqueue, struct task_struct *p, u64 enq_flags)
+{
+	struct task_ctx *tctx;
+
+	__sync_fetch_and_add(&enqueue_cnt, 1);
+
+	tctx = try_lookup_task_ctx(p);
+	if (!tctx)
+		return;
+
+	/*
+	 * Validate state transition: enqueue is only valid from NONE or
+	 * DISPATCHED states. Getting enqueue while in ENQUEUED state
+	 * indicates a missing dequeue.
+	 */
+	if (tctx->state == TASK_ENQUEUED)
+		scx_bpf_error("%d (%s): enqueue while in ENQUEUED state (seq %llu)",
+			      p->pid, p->comm, tctx->enqueue_seq);
+
+	/* Transition to ENQUEUED state */
+	tctx->state = TASK_ENQUEUED;
+	tctx->enqueue_seq++;
+
+	switch (test_scenario) {
+	case 0:
+		/* Scenario 0: Direct dispatch to the local DSQ */
+		scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL, SCX_SLICE_DFL, enq_flags);
+		break;
+
+	case 1:
+		/* Scenario 1: Dispatch to shared DSQ */
+		scx_bpf_dsq_insert(p, SHARED_DSQ, SCX_SLICE_DFL, enq_flags);
+		break;
+	}
+}
+
+void BPF_STRUCT_OPS(dequeue_dequeue, struct task_struct *p, u64 deq_flags)
+{
+	struct task_ctx *tctx;
+
+	__sync_fetch_and_add(&dequeue_cnt, 1);
+
+	tctx = try_lookup_task_ctx(p);
+	if (!tctx)
+		return;
+
+	/*
+	 * Validate state: dequeue should only happen from ENQUEUED or
+	 * DISPATCHED states. Getting dequeue from NONE indicates a bug.
+	 */
+	if (tctx->state == TASK_NONE)
+		scx_bpf_error("%d (%s): dequeue from NONE state (seq %llu)",
+			      p->pid, p->comm, tctx->enqueue_seq);
+
+	if (deq_flags & SCX_DEQ_SCHED_CHANGE) {
+		/*
+		 * Async dequeue: property change interrupting the workflow.
+		 * Valid from both ENQUEUED and DISPATCHED states.
+		 * Transitions task back to NONE state.
+		 */
+		__sync_fetch_and_add(&change_dequeue_cnt, 1);
+
+		/* Validate state transition */
+		if (tctx->state != TASK_ENQUEUED && tctx->state != TASK_DISPATCHED)
+			scx_bpf_error("%d (%s): property change dequeue from invalid state %d (seq %llu)",
+				      p->pid, p->comm, tctx->state, tctx->enqueue_seq);
+
+		/* Transition back to NONE - task outside scheduler control */
+		tctx->state = TASK_NONE;
+	} else {
+		/*
+		 * Regular dispatch dequeue: normal workflow step.
+		 * Valid only from ENQUEUED state (after enqueue, before dispatch dequeue).
+		 * Transitions to DISPATCHED state.
+		 */
+		__sync_fetch_and_add(&dispatch_dequeue_cnt, 1);
+
+		/* Validate: dispatch dequeue should NOT have %SCX_DEQ_SCHED_CHANGE flag */
+		if (deq_flags & SCX_DEQ_SCHED_CHANGE)
+			scx_bpf_error("%d (%s): SCX_DEQ_SCHED_CHANGE in dispatch dequeue (seq %llu)",
+				      p->pid, p->comm, tctx->enqueue_seq);
+
+		/* Must be in ENQUEUED state */
+		if (tctx->state != TASK_ENQUEUED)
+			scx_bpf_error("%d (%s): dispatch dequeue from state %d (seq %llu)",
+				      p->pid, p->comm, tctx->state, tctx->enqueue_seq);
+
+		/* Transition to DISPATCHED - normal cycle completed dispatch */
+		tctx->state = TASK_DISPATCHED;
+	}
+}
+
+void BPF_STRUCT_OPS(dequeue_dispatch, s32 cpu, struct task_struct *prev)
+{
+	scx_bpf_dsq_move_to_local(SHARED_DSQ);
+}
+
+s32 BPF_STRUCT_OPS(dequeue_init_task, struct task_struct *p,
+		   struct scx_init_task_args *args)
+{
+	struct task_ctx *tctx;
+
+	tctx = bpf_task_storage_get(&task_ctx_stor, p, 0,
+				   BPF_LOCAL_STORAGE_GET_F_CREATE);
+	if (!tctx)
+		return -ENOMEM;
+
+	return 0;
+}
+
+s32 BPF_STRUCT_OPS_SLEEPABLE(dequeue_init)
+{
+	s32 ret;
+
+	ret = scx_bpf_create_dsq(SHARED_DSQ, -1);
+	if (ret)
+		return ret;
+
+	return 0;
+}
+
+void BPF_STRUCT_OPS(dequeue_exit, struct scx_exit_info *ei)
+{
+	UEI_RECORD(uei, ei);
+}
+
+SEC(".struct_ops.link")
+struct sched_ext_ops dequeue_ops = {
+	.select_cpu		= (void *)dequeue_select_cpu,
+	.enqueue		= (void *)dequeue_enqueue,
+	.dequeue		= (void *)dequeue_dequeue,
+	.dispatch		= (void *)dequeue_dispatch,
+	.init_task		= (void *)dequeue_init_task,
+	.init			= (void *)dequeue_init,
+	.exit			= (void *)dequeue_exit,
+	.name			= "dequeue_test",
+};
tools/testing/selftests/sched_ext/dequeue.c new file +182 -0
new file mode 100644
index 0000000000000..6861257d79b47
@@ -0,0 +1,182 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Copyright (c) 2025 NVIDIA Corporation.
+ */
+#define _GNU_SOURCE
+#include <stdio.h>
+#include <unistd.h>
+#include <signal.h>
+#include <bpf/bpf.h>
+#include <scx/common.h>
+#include <sys/wait.h>
+#include <sched.h>
+#include <pthread.h>
+#include "scx_test.h"
+#include "dequeue.bpf.skel.h"
+
+#define NUM_WORKERS 8
+
+/*
+ * Worker function that creates enqueue/dequeue events. It alternates
+ * between CPU work, sleeping, and affinity changes to trigger dequeues.
+ */
+static void worker_fn(int id)
+{
+	cpu_set_t cpuset;
+	int i;
+	volatile int sum = 0;
+
+	for (i = 0; i < 1000; i++) {
+		int j;
+
+		/* Do some work to trigger scheduling events */
+		for (j = 0; j < 10000; j++)
+			sum += j;
+
+		/* Change affinity to trigger dequeue */
+		if (i % 10 == 0) {
+			CPU_ZERO(&cpuset);
+			/* Rotate through the first 4 CPUs */
+			CPU_SET(i % 4, &cpuset);
+			sched_setaffinity(0, sizeof(cpuset), &cpuset);
+		}
+
+		/* Do additional work */
+		for (j = 0; j < 10000; j++)
+			sum += j;
+
+		/* Sleep to trigger dequeue */
+		usleep(1000 + (id * 100));
+	}
+
+	exit(0);
+}
+
+static enum scx_test_status run_scenario(struct dequeue *skel, u32 scenario,
+					 const char *scenario_name)
+{
+	struct bpf_link *link;
+	pid_t pids[NUM_WORKERS];
+	int i, status;
+	u64 enq_start, deq_start, dispatch_deq_start, change_deq_start;
+	u64 enq_delta, deq_delta, dispatch_deq_delta, change_deq_delta;
+
+	/* Set the test scenario */
+	skel->bss->test_scenario = scenario;
+
+	/* Record starting counts */
+	enq_start = skel->bss->enqueue_cnt;
+	deq_start = skel->bss->dequeue_cnt;
+	dispatch_deq_start = skel->bss->dispatch_dequeue_cnt;
+	change_deq_start = skel->bss->change_dequeue_cnt;
+
+	link = bpf_map__attach_struct_ops(skel->maps.dequeue_ops);
+	SCX_FAIL_IF(!link, "Failed to attach struct_ops for scenario %s", scenario_name);
+
+	/* Fork worker processes to generate enqueue/dequeue events */
+	for (i = 0; i < NUM_WORKERS; i++) {
+		pids[i] = fork();
+		SCX_FAIL_IF(pids[i] < 0, "Failed to fork worker %d", i);
+
+		if (pids[i] == 0) {
+			worker_fn(i);
+			/* Should not reach here */
+			exit(1);
+		}
+	}
+
+	/* Wait for all workers to complete */
+	for (i = 0; i < NUM_WORKERS; i++) {
+		SCX_FAIL_IF(waitpid(pids[i], &status, 0) != pids[i],
+			    "Failed to wait for worker %d", i);
+		SCX_FAIL_IF(status != 0, "Worker %d exited with status %d", i, status);
+	}
+
+	bpf_link__destroy(link);
+
+	SCX_EQ(skel->data->uei.kind, EXIT_KIND(SCX_EXIT_UNREG));
+
+	/* Calculate deltas */
+	enq_delta = skel->bss->enqueue_cnt - enq_start;
+	deq_delta = skel->bss->dequeue_cnt - deq_start;
+	dispatch_deq_delta = skel->bss->dispatch_dequeue_cnt - dispatch_deq_start;
+	change_deq_delta = skel->bss->change_dequeue_cnt - change_deq_start;
+
+	printf("%s:\n", scenario_name);
+	printf("  enqueues: %lu\n", (unsigned long)enq_delta);
+	printf("  dequeues: %lu (dispatch: %lu, property_change: %lu)\n",
+	       (unsigned long)deq_delta,
+	       (unsigned long)dispatch_deq_delta,
+	       (unsigned long)change_deq_delta);
+
+	/*
+	 * Validate that we got enqueue and dequeue events.
+	 * The BPF code does strict state machine validation with scx_bpf_error()
+	 * to ensure the workflow semantics are correct. If we reach here without
+	 * errors, the semantics are validated correctly.
+	 */
+	SCX_GT(enq_delta, 0);
+	SCX_GT(deq_delta, 0);
+
+	return SCX_TEST_PASS;
+}
+
+static enum scx_test_status setup(void **ctx)
+{
+	struct dequeue *skel;
+
+	skel = dequeue__open();
+	SCX_FAIL_IF(!skel, "Failed to open skel");
+	SCX_ENUM_INIT(skel);
+	SCX_FAIL_IF(dequeue__load(skel), "Failed to load skel");
+
+	*ctx = skel;
+
+	return SCX_TEST_PASS;
+}
+
+static enum scx_test_status run(void *ctx)
+{
+	struct dequeue *skel = ctx;
+	enum scx_test_status status;
+
+	status = run_scenario(skel, 0, "Local DSQ");
+	if (status != SCX_TEST_PASS)
+		return status;
+
+	status = run_scenario(skel, 1, "User DSQ");
+	if (status != SCX_TEST_PASS)
+		return status;
+
+	printf("\n=== Summary ===\n");
+	printf("Total enqueues: %lu\n", (unsigned long)skel->bss->enqueue_cnt);
+	printf("Total dequeues: %lu\n", (unsigned long)skel->bss->dequeue_cnt);
+	printf("  Dispatch dequeues: %lu (no flag, normal workflow)\n",
+	       (unsigned long)skel->bss->dispatch_dequeue_cnt);
+	printf("  Property change dequeues: %lu (SCX_DEQ_SCHED_CHANGE flag)\n",
+	       (unsigned long)skel->bss->change_dequeue_cnt);
+	printf("\nAll scenarios passed - no state machine violations detected\n");
+	printf("-> Validated: Correct state transitions (NONE -> ENQUEUED -> DISPATCHED)\n");
+	printf("-> Validated: Dispatch dequeues have no flags (normal workflow)\n");
+	printf("-> Validated: Async dequeues have SCX_DEQ_SCHED_CHANGE flag (interruptions)\n");
+	printf("-> Validated: No duplicate enqueues or invalid state transitions\n");
+
+	return SCX_TEST_PASS;
+}
+
+static void cleanup(void *ctx)
+{
+	struct dequeue *skel = ctx;
+
+	dequeue__destroy(skel);
+}
+
+struct scx_test dequeue_test = {
+	.name = "dequeue",
+	.description = "Verify that ops.enqueue() is balanced with ops.dequeue()",
+	.setup = setup,
+	.run = run,
+	.cleanup = cleanup,
+};
+
+REGISTER_SCX_TEST(&dequeue_test)