Skip to contentSkip to conversation

sched_ext: Fix ops.dequeue() semantics

PATCH Superseded Andrea Righi 3 participants 7 messages Jan 21 – Jan 23

Subsystems (4)

v2 of 10 Superseded Latest is v10 →

lore
Share & tools
lore

Andrea Righi

author reviewer
#0 lore raw

PATCH v2 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 BPF scheduler, either due to dispatch or a property change, visibility of the task is lost and the sched_ext core may not invoke 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 dispatch dequeue and a property change dequeue, introduce a new dequeue flag: SCX_DEQ_ASYNC (I'm open to suggestions to find a better name for this flag). BPF schedulers can use this flag to distinguish between regular dispatch dequeues (SCX_DSQ_ASYNC unset) and property change dequeues (SCX_DEQ_ASYNC set).

In addition, a kselftest is provided to validate the behavior of ops.dequeue() in all the different cases.

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

Changes in v2:
- Distinguish between "dispatch" dequeues and "property change" dequeues (flag SCX_DSQ_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                              |  63 ++++++-
 kernel/sched/ext_internal.h                     |   6 +
 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, 508 insertions(+), 2 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_ASYNC flag to distinguish dequeues triggered by scheduling property changes from those occurring in the normal dispatch 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, because it is dispatched to a DSQ (regular workflow)
3. ops.dequeue(SCX_DEQ_ASYNC) is called when the task leaves the BPF scheduler, because a task property is changed (sched_change)

The SCX_DEQ_ASYNC flag allows BPF schedulers to distinguish between a regular dispatch workflow and a task property changes (e.g., sched_setaffinity(), sched_setscheduler(), set_user_nice(), NUMA balancing, CPU migrations, etc.).

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

Cc Tejun Heo <[email protected]>
Cc Emil Tsalapatis <[email protected]>
---
 Documentation/scheduler/sched-ext.rst         | 33 ++++++++++
 include/linux/sched/ext.h                     | 11 ++++
 kernel/sched/ext.c                            | 63 ++++++++++++++++++-
 kernel/sched/ext_internal.h                   |  6 ++
 .../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, 116 insertions(+), 2 deletions(-)
Documentation/scheduler/sched-ext.rst +33 -0
index 404fe6126a769..960125c1439ab 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 two 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. **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_ASYNC`` 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()``.
+
+   The ``SCX_DEQ_ASYNC`` flag allows BPF schedulers to distinguish between:
+   - normal dispatch workflow (task successfully dispatched to a DSQ),
+   - asynchronous dequeues (``SCX_DEQ_ASYNC``): task property changes that
+     require the scheduler to update its internal state.
+
+   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..f3094b4a72a56 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 async dequeues (property changes)
+	 * and to 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 +61 -2

94 lines not on this page · raw message

kernel/sched/ext_internal.h +6 -0
index 386c677e4c9a0..068c7c2892a16 100644
@@ -982,6 +982,12 @@ 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 an asynchronous event (e.g.,
+	 * property change via sched_setaffinity(), priority change, etc.).
+	 */
+	SCX_DEQ_ASYNC		= 1LLU << 33,
 };
 
 enum scx_pick_idle_cpu_flags {
tools/sched_ext/include/scx/enum_defs.autogen.h +2 -0
index c2c33df9292c2..17d8f4324b856 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_ASYNC
 #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..b3ecd6783d1e5 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_ASYNC __weak;
+#define SCX_DEQ_ASYNC __SCX_DEQ_ASYNC
tools/sched_ext/include/scx/enums.autogen.h +1 -0
index fedec938584be..89359ab65cd3c 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_ASYNC); \
 } while (0)
Signature · 1 line
2.52.0
#2 lore raw
Quoted 26 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_ASYNC flag to distinguish dequeues triggered by scheduling property changes from those occurring in the normal dispatch 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, because it is dispatched to a DSQ (regular workflow)
3. ops.dequeue(SCX_DEQ_ASYNC) is called when the task leaves the BPF scheduler, because a task property is changed (sched_change)

The SCX_DEQ_ASYNC flag allows BPF schedulers to distinguish between a regular dispatch workflow and a task property changes (e.g., sched_setaffinity(), sched_setscheduler(), set_user_nice(), NUMA balancing, CPU migrations, etc.).

Quoted 5 lines

This allows BPF schedulers to:
- reliably track task ownership and lifecycle,
- maintain accurate accounting of enqueue/dequeue pairs,
- update internal state when tasks change properties. [snip]

Cool, so with this patch I should be able to fix my scx_storm BPF scheduler doing local inserts, as long as I track all the task's status that are not in a DSQ?
https://github.com/cloehle/scx/commit/25ea91d8f7fea1f31cf426561b432180fb9cf76a
mentioned in
https://github.com/sched-ext/scx/issues/2825

Let me give that a go and report back!

author reviewer
#3 lore raw

On Wed, Jan 21, 2026 at 12:54:42PM +0000, Christian Loehle wrote:
...

Quoted 6 lines
Quoted 5 lines

This allows BPF schedulers to:
- reliably track task ownership and lifecycle,
- maintain accurate accounting of enqueue/dequeue pairs,
- update internal state when tasks change properties. [snip]

Quoted 6 lines

Cool, so with this patch I should be able to fix my scx_storm BPF scheduler doing local inserts, as long as I track all the task's status that are not in a DSQ?
https://github.com/cloehle/scx/commit/25ea91d8f7fea1f31cf426561b432180fb9cf76a
mentioned in
https://github.com/sched-ext/scx/issues/2825

In theory, yes...

Quoted 2 lines

Let me give that a go and report back!

Let me know how it goes.

Thanks,
-Andrea

#4 lore raw
In reply to Andrea Righi

[Resending with reply-all, messed up the first time, apologies.]

Hi Andrea,

Quoted 14 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_ASYNC flag to distinguish dequeues triggered by scheduling property changes from those occurring in the normal dispatch workflow.

Quoted 6 lines

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, because it is dispatched to a DSQ (regular workflow)
3. ops.dequeue(SCX_DEQ_ASYNC) is called when the task leaves the BPF scheduler, because a task property is changed (sched_change)

What about the case where ops.dequeue() is called due to core-sched picking the task through sched_core_find()? If I understand core-sched correctly, it can happen without prior dispatch, so it doesn't fit case 2, and we're not changing task properties, so it doesn't fit case 3 either.

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

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

I see this flag being set and cleared in several places, but I don't see it actually being read, is that intentional?

Quoted 26 lines
kernel/sched/ext.c +14 -1
@@ -1529,6 +1553,17 @@ 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) {
+                     bool is_async_dequeue =
+                             !(deq_flags & (DEQUEUE_SLEEP | SCX_DEQ_CORE_SCHED_EXEC));
+
+                     if (is_async_dequeue)
+                             SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq,
+                                              p, deq_flags | SCX_DEQ_ASYNC);
+                     p->scx.flags &= ~(SCX_TASK_OPS_ENQUEUED |
+                                       SCX_TASK_DISPATCH_DEQUEUED);
+             }
              break;
      case SCX_OPSS_QUEUEING:
              /*
@@ -1537,9 +1572,17 @@ 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))
+             /*
+              * Task is in the enqueued state. This is a property change
+              * dequeue before dispatch completes. Notify the BPF scheduler

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

Quoted 10 lines
kernel/sched/ext.c +7 -1
+              * with SCX_DEQ_ASYNC flag.
+              */
+             if (SCX_HAS_OP(sch, dequeue)) {
                      SCX_CALL_OP_TASK(sch, SCX_KF_REST, dequeue, rq,
-                                      p, deq_flags);
+                                      p, deq_flags | SCX_DEQ_ASYNC);
+                     p->scx.flags &= ~(SCX_TASK_OPS_ENQUEUED |
+                                       SCX_TASK_DISPATCH_DEQUEUED);
+             }
 

A core-sched pick of a task queued on the BPF scheduler will result in entering the SCX_OPSS_QUEUED case, which in turn will call ops.dequeue(SCX_DEQ_ASYNC). This seems to conflict with the is_async_dequeue check above, which treats SCX_DEQ_CORE_SCHED_EXEC as a synchronous dequeue.

Thanks,
Kuba

author reviewer
#5 lore raw
Quoted 1 line · Kuba Piecuch

[Resending with reply-all, messed up the first time, apologies.]

Re-sendind my reply as well, just for the records. :)

Quoted 25 lines

Hi Andrea,

Quoted 14 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_ASYNC flag to distinguish dequeues triggered by scheduling property changes from those occurring in the normal dispatch workflow.

Quoted 6 lines

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, because it is dispatched to a DSQ (regular workflow)
3. ops.dequeue(SCX_DEQ_ASYNC) is called when the task leaves the BPF scheduler, because a task property is changed (sched_change)

Quoted 4 lines

What about the case where ops.dequeue() is called due to core-sched picking the task through sched_core_find()? If I understand core-sched correctly, it can happen without prior dispatch, so it doesn't fit case 2, and we're not changing task properties, so it doesn't fit case 3 either.

You're absolutely right, core-sched picks are inconsistently handled. They're treated as property change dequeues in the SCX_OPSS_QUEUED case and as dispatch dequeues in SCX_OPSS_NONE.

Core-sched picks should be treated consistently as regular dequeues since they're not property changes. I'll fix this in the next version (adding SCX_DEQ_CORE_SCHED_EXEC check in the SCX_OPSS_QUEUED should make the core-sched case consistent).

Quoted 10 lines

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

Quoted 7 lines
include/linux/sched/ext.h +6 -0
+     /*
+      * Set when ops.dequeue() is called after successful dispatch; used to
+      * distinguish dispatch dequeues from async dequeues (property changes)
+      * and to prevent duplicate dequeue calls.
+      */
+     SCX_TASK_DISPATCH_DEQUEUED = 1 << 4,

I see this flag being set and cleared in several places, but I don't see it actually being read, is that intentional?

And you're right here as well. At some point this was used to distinguish dispatch dequeues vs async dequeues, but isn't actually used anymore. I'll clean this up in the next version.

Thanks,
-Andrea

author reviewer
#6 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,
- async dequeues (SCX_DEQ_ASYNC) 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]>
---
 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 2c601a7eaff5f..2815a875bde2f 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