sched_ext: Fix ops.dequeue() semantics
Subsystems (4)
Andrea Righi
reviewerPATCH 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
Andrea Righi
reviewerPATCH 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.
--- 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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
Quoted 26 lines · Andrea Righi
Currently,
ops.dequeue()is only invoked when thesched_extcore 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), soops.enqueue()calls are not always paired with a correspondingops.dequeue(), potentially breaking accounting logic.Fix this by guaranteeing that every
ops.enqueue()is matched with a correspondingops.dequeue(), and introduce theSCX_DEQ_ASYNCflag 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_ASYNCflag 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!
Andrea Righi
reviewerOn 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_stormBPF 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
[Resending with reply-all, messed up the first time, apologies.]
Hi Andrea,
Quoted 14 lines · Andrea Righi
Currently,
ops.dequeue()is only invoked when thesched_extcore 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), soops.enqueue()calls are not always paired with a correspondingops.dequeue(), potentially breaking accounting logic.Fix this by guaranteeing that every
ops.enqueue()is matched with a correspondingops.dequeue(), and introduce theSCX_DEQ_ASYNCflag 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
Andrea Righi
reviewerQuoted 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 thesched_extcore 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), soops.enqueue()calls are not always paired with a correspondingops.dequeue(), potentially breaking accounting logic.Fix this by guaranteeing that every
ops.enqueue()is matched with a correspondingops.dequeue(), and introduce theSCX_DEQ_ASYNCflag 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 throughsched_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
Andrea Righi
reviewerPATCH 2/2 selftests/sched_ext: Add test to validate ops.dequeue() semantics
In reply to Andrea RighiAdd 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.
--- 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
@@ -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