sched_ext: Fix ops.dequeue() semantics
Subsystems (4)
Andrea Righi
reviewerPATCH v6 1/1 sched_ext: Fix ops.dequeue() semantics
The callback ops.dequeue() is provided to let BPF schedulers observe when a task leaves the scheduler, either because it is dispatched or due to a task property change. However, this callback is currently unreliable and not invoked systematically, which can result in missed ops.dequeue() events.
In particular, once a task is removed from the scheduler (whether for dispatch or due to a property change) the BPF scheduler loses visibility of the task and the sched_ext core may not always trigger ops.dequeue().
This breaks accurate accounting (i.e., per-DSQ queued runtime sums) and prevents reliable tracking of task lifecycle transitions.
This patch set fixes the semantics of ops.dequeue(), by guaranteeing that each task entering the BPF scheduler's custody triggers exactly one ops.dequeue() call when it leaves that custody, whether the exit is due to a dispatch (regular or via a core scheduling pick) or to a scheduling property change (e.g. sched_setaffinity(), sched_setscheduler(), set_user_nice(), NUMA balancing, etc.).
To identify property change dequeues a new ops.dequeue() flag is
introduced: %SCX_DEQ_SCHED_CHANGE.
Together, these changes allow BPF schedulers to reliably track task ownership and maintain accurate accounting.
Changes in v6:
- Rename SCX_TASK_OPS_ENQUEUED -> SCX_TASK_NEED_DSQ
- Use SCX_DSQ_FLAG_BUILTIN in is_terminal_dsq() to check for all builtin DSQs (local, global, bypass)
- centralize ops.dequeue() logic in dispatch_enqueue()
- Remove "Property Change Notifications for Running Tasks" section from the documentation
- The kselftest now validates the right behavior both from ops.enqueue() and ops.select_cpu()
- Link to v5: https://lore.kernel.org/all/[email protected]
Changes in v5:
- Introduce the concept of "terminal DSQ" (when a task is dispatched to a terminal DSQ, the task leaves the BPF scheduler's custody)
- Consider SCX_DSQ_GLOBAL as a terminal DSQ
- Link to v4: https://lore.kernel.org/all/[email protected]
Changes in v4:
- Introduce the concept of "BPF scheduler custody"
- Do not trigger ops.dequeue() for direct dispatches to local DSQs
- Trigger ops.dequeue() only once; after the task leaves BPF scheduler custody, further dequeue events are not reported.
- Link to v3: https://lore.kernel.org/all/[email protected]
Changes in v3:
- Rename SCX_DEQ_ASYNC to SCX_DEQ_SCHED_CHANGE
- Handle core-sched dequeues (Kuba)
- Link to v2: https://lore.kernel.org/all/[email protected]
Changes in v2:
- Distinguish between "dispatch" dequeues and "property change" dequeues (flag SCX_DEQ_ASYNC)
- Link to v1: https://lore.kernel.org/all/[email protected]
Andrea Righi (2):
sched_ext: Fix ops.dequeue() semantics selftests/sched_ext: Add test to validate ops.dequeue() semantics
Documentation/scheduler/sched-ext.rst | 53 ++++ include/linux/sched/ext.h | 1 + kernel/sched/ext.c | 130 ++++++++- kernel/sched/ext_internal.h | 7 + tools/sched_ext/include/scx/enum_defs.autogen.h | 1 + tools/sched_ext/include/scx/enums.autogen.bpf.h | 2 + tools/sched_ext/include/scx/enums.autogen.h | 1 + tools/testing/selftests/sched_ext/Makefile | 1 + tools/testing/selftests/sched_ext/dequeue.bpf.c | 334 ++++++++++++++++++++++++ tools/testing/selftests/sched_ext/dequeue.c | 222 ++++++++++++++++ 10 files changed, 739 insertions(+), 13 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 events. In addition, ops.dequeue() callbacks are completely skipped when tasks are dispatched to non-local DSQs from ops.select_cpu(). As a result, BPF schedulers cannot reliably track task state.
Fix this by guaranteeing that each task entering the BPF scheduler's custody triggers exactly one ops.dequeue() call when it leaves that custody, whether the exit is due to a dispatch (regular or via a core scheduling pick) or to a scheduling property change (e.g. sched_setaffinity(), sched_setscheduler(), set_user_nice(), NUMA balancing, etc.).
BPF scheduler custody concept: a task is considered to be in "BPF scheduler's custody" when it has been queued in user-created DSQs and the BPF scheduler is responsible for its lifecycle. Custody ends when the task is dispatched to a terminal DSQ (local DSQ or SCX_DSQ_GLOBAL), selected by core scheduling, or removed due to a property change.
Tasks directly dispatched to terminal DSQs bypass the BPF scheduler entirely and are not in its custody. Terminal DSQs include:
- Local DSQs (%SCX_DSQ_LOCAL or %SCX_DSQ_LOCAL_ON): per-CPU queues where tasks go directly to execution.
- Global DSQ (%SCX_DSQ_GLOBAL): the built-in fallback queue where the BPF scheduler is considered "done" with the task.
As a result, ops.dequeue() is not invoked for tasks dispatched to terminal DSQs, as the BPF scheduler no longer retains custody of them.
To identify dequeues triggered by scheduling property changes, introduce the new ops.dequeue() flag %SCX_DEQ_SCHED_CHANGE: when this flag is set, the dequeue was caused by a scheduling property change.
New ops.dequeue() semantics:
- ops.dequeue() is invoked exactly once when the task leaves the BPF scheduler's custody, in one of the following cases:
a) regular dispatch: a task dispatched to a user DSQ is moved to a terminal DSQ (ops.dequeue() called without any special flags set),
b) core scheduling dispatch: core-sched picks task before dispatch, ops.dequeue() called with %SCX_DEQ_CORE_SCHED_EXEC flag set,
c) property change: task properties modified before dispatch, ops.dequeue() called with %SCX_DEQ_SCHED_CHANGE flag set.
This allows BPF schedulers to:
- reliably track task ownership and lifecycle,
- maintain accurate accounting of managed tasks,
- update internal state when tasks change properties.
--- Documentation/scheduler/sched-ext.rst | 53 +++++++ include/linux/sched/ext.h | 1 + kernel/sched/ext.c | 130 ++++++++++++++++-- kernel/sched/ext_internal.h | 7 + .../sched_ext/include/scx/enum_defs.autogen.h | 1 + .../sched_ext/include/scx/enums.autogen.bpf.h | 2 + tools/sched_ext/include/scx/enums.autogen.h | 1 + 7 files changed, 182 insertions(+), 13 deletions(-)
Documentation/scheduler/sched-ext.rst +53 -0
@@ -252,6 +252,57 @@ The following briefly shows how a waking task is scheduled and executed. * Queue the task on the BPF side. + **Task State Tracking and ops.dequeue() Semantics** + + Once ``ops.select_cpu()`` or ``ops.enqueue()`` is called, the task may + enter the "BPF scheduler's custody" depending on where it's dispatched: + + * **Direct dispatch to terminal DSQs** (``SCX_DSQ_LOCAL``, + ``SCX_DSQ_LOCAL_ON | cpu``, or ``SCX_DSQ_GLOBAL``): The BPF scheduler + is done with the task - it either goes straight to a CPU's local run + queue or to the global DSQ as a fallback. The task never enters (or + exits) BPF custody, and ``ops.dequeue()`` will not be called. + + * **Dispatch to user-created DSQs** (custom DSQs): the task enters the + BPF scheduler's custody. When the task later leaves BPF custody + (dispatched to a terminal DSQ, picked by core-sched, or dequeued for + sleep/property changes), ``ops.dequeue()`` will be called exactly once. + + * **Queued on BPF side**: The task is in BPF data structures and in BPF + custody, ``ops.dequeue()`` will be called when it leaves. + + The key principle: **ops.dequeue() is called when a task leaves the BPF + scheduler's custody**. + + This works also with the ``ops.select_cpu()`` direct dispatch + optimization: even though it skips ``ops.enqueue()`` invocation, if the + task is dispatched to a user-created DSQ, it enters BPF custody and will + get ``ops.dequeue()`` when it leaves. If dispatched to a terminal DSQ, + the BPF scheduler is done with it immediately. This provides the + performance benefit of avoiding the ``ops.enqueue()`` roundtrip while + maintaining correct state tracking. + + The dequeue can happen for different reasons, distinguished by flags: + + 1. **Regular dispatch workflow**: when the task is dispatched from a + user-created DSQ to a terminal DSQ (leaving BPF custody for execution), + ``ops.dequeue()`` is triggered without any special flags. + + 2. **Core scheduling pick**: when ``CONFIG_SCHED_CORE`` is enabled and + core scheduling picks a task for execution while it's still in BPF + custody, ``ops.dequeue()`` is called with the + ``SCX_DEQ_CORE_SCHED_EXEC`` flag. + + 3. **Scheduling property change**: when a task property changes (via + operations like ``sched_setaffinity()``, ``sched_setscheduler()``, + priority changes, CPU migrations, etc.) while the task is still in + BPF custody, ``ops.dequeue()`` is called with the + ``SCX_DEQ_SCHED_CHANGE`` flag set in ``deq_flags``. + + **Important**: Once a task has left BPF custody (dispatched to a + terminal DSQ), property changes will not trigger ``ops.dequeue()``, + since the task is no longer being managed by the BPF scheduler. + 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 +370,8 @@ by a sched_ext scheduler: /* Any usable CPU becomes available */ ops.dispatch(); /* Task is moved to a local DSQ */ + + ops.dequeue(); /* Exiting BPF scheduler */ } ops.running(); /* Task starts running on its assigned CPU */ while (task->scx.slice > 0 && task is runnable)
include/linux/sched/ext.h +1 -0
@@ -84,6 +84,7 @@ struct scx_dispatch_q {/* scx_entity.flags */ enum scx_ent_flags {SCX_TASK_QUEUED =1 <<0 ,/* on ext runqueue */ +SCX_TASK_NEED_DEQ =1 <<1 ,/* task needs ops.dequeue() */ SCX_TASK_RESET_RUNNABLE_AT =1 <<2 ,/* runnable_at should be reset */ SCX_TASK_DEQD_FOR_SLEEP =1 <<3 ,/* last dequeue was for SLEEP */
kernel/sched/ext.c +117 -13
251 lines not on this page · raw message
kernel/sched/ext_internal.h +7 -0
@@ -982,6 +982,13 @@ enum scx_deq_flags {* it hasn't been dispatched yet. Dequeue from the BPF side. */ SCX_DEQ_CORE_SCHED_EXEC =1LLU <<32 , + +/* +* The task is being dequeued due to a property change (e.g., +* sched_setaffinity(), sched_setscheduler(), set_user_nice(), +* etc.). +*/ + SCX_DEQ_SCHED_CHANGE = 1LLU << 33, }; enum scx_pick_idle_cpu_flags {
tools/sched_ext/include/scx/enum_defs.autogen.h +1 -0
@@ -21,6 +21,7 @@#define HAVE_SCX_CPU_PREEMPT_UNKNOWN #define HAVE_SCX_DEQ_SLEEP #define HAVE_SCX_DEQ_CORE_SCHED_EXEC +#define HAVE_SCX_DEQ_SCHED_CHANGE #define HAVE_SCX_DSQ_FLAG_BUILTIN #define HAVE_SCX_DSQ_FLAG_LOCAL_ON #define HAVE_SCX_DSQ_INVALID
tools/sched_ext/include/scx/enums.autogen.bpf.h +2 -0
@@ -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
@@ -46,4 +46,5 @@SCX_ENUM_SET (skel, scx_enq_flags,SCX_ENQ_LAST ); \SCX_ENUM_SET (skel, scx_enq_flags,SCX_ENQ_CLEAR_OPSS ); \SCX_ENUM_SET (skel, scx_enq_flags,SCX_ENQ_DSQ_PRIQ ); \ +SCX_ENUM_SET (skel, scx_deq_flags,SCX_DEQ_SCHED_CHANGE ); \ }while (0 )
Signature · 1 line
2.53.0
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 events. In addition,ops.dequeue()callbacks are completely skipped when tasks are dispatched to non-local DSQs fromops.select_cpu(). As a result, BPF schedulers cannot reliably track task state.Fix this by guaranteeing that each task entering the BPF scheduler's custody triggers exactly one
ops.dequeue()call when it leaves that custody, whether the exit is due to a dispatch (regular or via a core scheduling pick) or to a scheduling property change (e.g.sched_setaffinity(),sched_setscheduler(),set_user_nice(), NUMA balancing, etc.).
Quoted 5 lines
BPF scheduler custody concept: a task is considered to be in "BPF scheduler's custody" when it has been queued in user-created DSQs and the BPF scheduler is responsible for its lifecycle. Custody ends when the task is dispatched to a terminal DSQ (local DSQ or
SCX_DSQ_GLOBAL), selected by core scheduling, or removed due to a property change.
Strictly speaking, a task in BPF scheduler custody doesn't have to be queued in a user-created DSQ. It could just reside on some custom data structure.
Quoted 10 lines
Tasks directly dispatched to terminal DSQs bypass the BPF scheduler entirely and are not in its custody. Terminal DSQs include:
- Local DSQs (%SCX_DSQ_LOCAL or %SCX_DSQ_LOCAL_ON): per-CPU queues where tasks go directly to execution.
- Global DSQ (%SCX_DSQ_GLOBAL): the built-in fallback queue where the BPF scheduler is considered "done" with the task.As a result,
ops.dequeue()is not invoked for tasks dispatched to terminal DSQs, as the BPF scheduler no longer retains custody of them.
Shouldn't it be "directly dispatched to terminal DSQs"?
Quoted 10 lines
To identify dequeues triggered by scheduling property changes, introduce the new
ops.dequeue()flag %SCX_DEQ_SCHED_CHANGE: when this flag is set, the dequeue was caused by a scheduling property change.New
ops.dequeue()semantics:
-ops.dequeue()is invoked exactly once when the task leaves the BPF scheduler's custody, in one of the following cases:
a) regular dispatch: a task dispatched to a user DSQ is moved to a terminal DSQ (ops.dequeue()called without any special flags set),
I don't think the task has to be on a user DSQ. How about just "a task in BPF scheduler's custody is dispatched to a terminal DSQ from ops.dispatch()"?
Quoted 10 lines
b) core scheduling dispatch: core-sched picks task before dispatch,
ops.dequeue()called with %SCX_DEQ_CORE_SCHED_EXEC flag set,
c) property change: task properties modified before dispatch,ops.dequeue()called with %SCX_DEQ_SCHED_CHANGE flag set.This allows BPF schedulers to:
- reliably track task ownership and lifecycle,
- maintain accurate accounting of managed tasks,
- update internal state when tasks change properties.
...
Quoted 33 lines
Documentation/scheduler/sched-ext.rst +25
-0@@ -252,6 +252,57 @@ The following briefly shows how a waking task is scheduled and executed. * Queue the task on the BPF side. + **Task State Tracking and ops.dequeue() Semantics** + + Once ``ops.select_cpu()`` or ``ops.enqueue()`` is called, the task may + enter the "BPF scheduler's custody" depending on where it's dispatched: + + * **Direct dispatch to terminal DSQs** (``SCX_DSQ_LOCAL``, + ``SCX_DSQ_LOCAL_ON | cpu``, or ``SCX_DSQ_GLOBAL``): The BPF scheduler + is done with the task - it either goes straight to a CPU's local run + queue or to the global DSQ as a fallback. The task never enters (or + exits) BPF custody, and ``ops.dequeue()`` will not be called. + + * **Dispatch to user-created DSQs** (custom DSQs): the task enters the + BPF scheduler's custody. When the task later leaves BPF custody + (dispatched to a terminal DSQ, picked by core-sched, or dequeued for + sleep/property changes), ``ops.dequeue()`` will be called exactly once. + + * **Queued on BPF side**: The task is in BPF data structures and in BPF + custody, ``ops.dequeue()`` will be called when it leaves. + + The key principle: **ops.dequeue() is called when a task leaves the BPF + scheduler's custody**. + + This works also with the ``ops.select_cpu()`` direct dispatch + optimization: even though it skips ``ops.enqueue()`` invocation, if the + task is dispatched to a user-created DSQ, it enters BPF custody and will
Documentation/scheduler/sched-ext.rst The following briefly shows how a waking task is scheduled and executed. · line 289
Quoted 10 lines
Documentation/scheduler/sched-ext.rst +10
-0+ get ``ops.dequeue()`` when it leaves. If dispatched to a terminal DSQ, + the BPF scheduler is done with it immediately. This provides the + performance benefit of avoiding the ``ops.enqueue()`` roundtrip while + maintaining correct state tracking. + + The dequeue can happen for different reasons, distinguished by flags: + + 1. **Regular dispatch workflow**: when the task is dispatched from a + user-created DSQ to a terminal DSQ (leaving BPF custody for execution), + ``ops.dequeue()`` is triggered without any special flags.
There's no requirement for the task do be on a user-created DSQ.
Quoted 19 lines
Documentation/scheduler/sched-ext.rst +16
-0+ + 2. **Core scheduling pick**: when ``CONFIG_SCHED_CORE`` is enabled and + core scheduling picks a task for execution while it's still in BPF + custody, ``ops.dequeue()`` is called with the + ``SCX_DEQ_CORE_SCHED_EXEC`` flag. + + 3. **Scheduling property change**: when a task property changes (via + operations like ``sched_setaffinity()``, ``sched_setscheduler()``, + priority changes, CPU migrations, etc.) while the task is still in + BPF custody, ``ops.dequeue()`` is called with the + ``SCX_DEQ_SCHED_CHANGE`` flag set in ``deq_flags``. + + **Important**: Once a task has left BPF custody (dispatched to a + terminal DSQ), property changes will not trigger ``ops.dequeue()``, + since the task is no longer being managed by the BPF scheduler. + 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
...
include/linux/sched/ext.h struct scx_dispatch_q { · line 87
Quoted 9 lines
include/linux/sched/ext.h +1
-0@@ -84,6 +84,7 @@ struct scx_dispatch_q {/* scx_entity.flags */ enum scx_ent_flags {SCX_TASK_QUEUED =1 <<0 ,/* on ext runqueue */ +SCX_TASK_NEED_DEQ =1 <<1 ,/* task needs ops.dequeue() */
I think this could use a comment that connects this flag to the concept of BPF custody, so how about something like "task is in BPF custody, needs ops.dequeue() when leaving it"?
Quoted 7 lines
include/linux/sched/ext.h +0
-0SCX_TASK_RESET_RUNNABLE_AT =1 <<2 ,/* runnable_at should be reset */ SCX_TASK_DEQD_FOR_SLEEP = 1 << 3, /* last dequeue was for SLEEP */kernel/sched/ext.c +0
-0
...
Quoted 15 lines
kernel/sched/ext.c +11
-0@@ -1103,6 +1125,27 @@ static void dispatch_enqueue(struct scx_sched *sch, struct scx_dispatch_q *dsq,dsq_mod_nr (dsq,1 ); p->scx.dsq = dsq; +/* +* Handle ops.dequeue() and custody tracking. +* +* Builtin DSQs (local, global, bypass) are terminal: the BPF +* scheduler is done with the task. If it was in BPF custody, call +* ops.dequeue() and clear the flag. +* +* User DSQs: Task is in BPF scheduler's custody. Set the flag so +* ops.dequeue() will be called when it leaves. +*/ +if (SCX_HAS_OP (sch, dequeue)) {
kernel/sched/ext.c static void dispatch_enqueue(struct scx_sched *sch, struct scx_dispatch_q *dsq, · line 1148
Quoted 10 lines
kernel/sched/ext.c +10
-0+if (is_terminal_dsq (dsq->id)) { +if (p->scx.flags &SCX_TASK_NEED_DEQ ) +SCX_CALL_OP_TASK (sch,SCX_KF_REST , dequeue, + rq, p,0 ); + p->scx.flags &= ~SCX_TASK_NEED_DEQ ; + }else { + p->scx.flags |=SCX_TASK_NEED_DEQ ; + } + } +
This is the only place where I see SCX_TASK_NEED_DEQ being set, which means it won't be set if the enqueued task is queued on the BPF scheduler's internal data structures rather than dispatched to a user-created DSQ. I don't think that's the behavior we're aiming for.
Quoted 26 lines
kernel/sched/ext.c +18
-0@@ -1524,6 +1579,24 @@ static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags)switch (opss &SCX_OPSS_STATE_MASK ) {case SCX_OPSS_NONE : +/* +* Task is not in BPF data structures (either dispatched to +* a DSQ or running). Only call ops.dequeue() if the task +* is still in BPF scheduler's custody (%SCX_TASK_NEED_DEQ +* is set). +* +* If the task has already been dispatched to a terminal +* DSQ (local DSQ or %SCX_DSQ_GLOBAL), it has left the BPF +* scheduler's custody and the flag will be clear, so we +* skip ops.dequeue(). +* +* If this is a property change (not sleep/core-sched) and +* the task is still in BPF custody, set the +* %SCX_DEQ_SCHED_CHANGE flag. +*/ +if (SCX_HAS_OP (sch, dequeue) && + (p->scx.flags &SCX_TASK_NEED_DEQ )) +call_task_dequeue (sch, rq, p, deq_flags);break ;case SCX_OPSS_QUEUEING :/*
kernel/sched/ext.c static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags) · line 1613
Quoted 9 lines
kernel/sched/ext.c +6
-0@@ -1532,9 +1605,14 @@ static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags)*/ BUG ();case SCX_OPSS_QUEUED : +/* +* Task is still on the BPF scheduler (not dispatched yet). +* Call ops.dequeue() to notify. Add %SCX_DEQ_SCHED_CHANGE +* only for property changes, not for core-sched picks or +* sleep. +*/
The part of the comment about SCX_DEQ_SCHED_CHANGE looks like it belongs in call_task_dequeue(), not here.
kernel/sched/ext.c static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags) · line 1615
Quoted 4 lines
kernel/sched/ext.c +1
-2if (SCX_HAS_OP (sch, dequeue)) -SCX_CALL_OP_TASK (sch,SCX_KF_REST , dequeue, rq, - p, deq_flags); +call_task_dequeue (sch, rq, p, deq_flags);
How about adding WARN_ON_ONCE(!(p->scx.flags & SCX_TASK_NEED_DEQ)) here or in call_task_dequeue()?
Thanks,
Kuba
Andrea Righi
reviewerHi Kuba,
Quoted 17 lines · Kuba Piecuch
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 events. In addition,ops.dequeue()callbacks are completely skipped when tasks are dispatched to non-local DSQs fromops.select_cpu(). As a result, BPF schedulers cannot reliably track task state.Fix this by guaranteeing that each task entering the BPF scheduler's custody triggers exactly one
ops.dequeue()call when it leaves that custody, whether the exit is due to a dispatch (regular or via a core scheduling pick) or to a scheduling property change (e.g.sched_setaffinity(),sched_setscheduler(),set_user_nice(), NUMA balancing, etc.).
Quoted 8 lines
Quoted 5 lines
BPF scheduler custody concept: a task is considered to be in "BPF scheduler's custody" when it has been queued in user-created DSQs and the BPF scheduler is responsible for its lifecycle. Custody ends when the task is dispatched to a terminal DSQ (local DSQ or
SCX_DSQ_GLOBAL), selected by core scheduling, or removed due to a property change.Strictly speaking, a task in BPF scheduler custody doesn't have to be queued in a user-created DSQ. It could just reside on some custom data structure.
Yeah... we definitely need to consider internal BPF queues.
Quoted 9 lines
Quoted 9 lines
Tasks directly dispatched to terminal DSQs bypass the BPF scheduler entirely and are not in its custody. Terminal DSQs include:
- Local DSQs (%SCX_DSQ_LOCAL or %SCX_DSQ_LOCAL_ON): per-CPU queues where tasks go directly to execution.
- Global DSQ (%SCX_DSQ_GLOBAL): the built-in fallback queue where the BPF scheduler is considered "done" with the task.
Quoted 4 lines
Quoted 2 lines
As a result,
ops.dequeue()is not invoked for tasks dispatched to terminal DSQs, as the BPF scheduler no longer retains custody of them.Shouldn't it be "directly dispatched to terminal DSQs"?
Ack.
Quoted 6 lines
Quoted 6 lines
To identify dequeues triggered by scheduling property changes, introduce the new
ops.dequeue()flag %SCX_DEQ_SCHED_CHANGE: when this flag is set, the dequeue was caused by a scheduling property change.
Quoted 8 lines
Quoted 5 lines
New
ops.dequeue()semantics:
-ops.dequeue()is invoked exactly once when the task leaves the BPF scheduler's custody, in one of the following cases:
a) regular dispatch: a task dispatched to a user DSQ is moved to a terminal DSQ (ops.dequeue()called without any special flags set),I don't think the task has to be on a user DSQ. How about just "a task in BPF scheduler's custody is dispatched to a terminal DSQ from
ops.dispatch()"?
Right.
Quoted 49 lines
Quoted 11 lines
b) core scheduling dispatch: core-sched picks task before dispatch,
ops.dequeue()called with %SCX_DEQ_CORE_SCHED_EXEC flag set,
c) property change: task properties modified before dispatch,ops.dequeue()called with %SCX_DEQ_SCHED_CHANGE flag set.This allows BPF schedulers to:
- reliably track task ownership and lifecycle,
- maintain accurate accounting of managed tasks,
- update internal state when tasks change properties....
Quoted 37 lines
Documentation/scheduler/sched-ext.rst +29
-0@@ -252,6 +252,57 @@ The following briefly shows how a waking task is scheduled and executed. * Queue the task on the BPF side. + **Task State Tracking and ops.dequeue() Semantics** + + Once ``ops.select_cpu()`` or ``ops.enqueue()`` is called, the task may + enter the "BPF scheduler's custody" depending on where it's dispatched: + + * **Direct dispatch to terminal DSQs** (``SCX_DSQ_LOCAL``, + ``SCX_DSQ_LOCAL_ON | cpu``, or ``SCX_DSQ_GLOBAL``): The BPF scheduler + is done with the task - it either goes straight to a CPU's local run + queue or to the global DSQ as a fallback. The task never enters (or + exits) BPF custody, and ``ops.dequeue()`` will not be called. + + * **Dispatch to user-created DSQs** (custom DSQs): the task enters the + BPF scheduler's custody. When the task later leaves BPF custody + (dispatched to a terminal DSQ, picked by core-sched, or dequeued for + sleep/property changes), ``ops.dequeue()`` will be called exactly once. + + * **Queued on BPF side**: The task is in BPF data structures and in BPF + custody, ``ops.dequeue()`` will be called when it leaves. + + The key principle: **ops.dequeue() is called when a task leaves the BPF + scheduler's custody**. + + This works also with the ``ops.select_cpu()`` direct dispatch + optimization: even though it skips ``ops.enqueue()`` invocation, if the + task is dispatched to a user-created DSQ, it enters BPF custody and will + get ``ops.dequeue()`` when it leaves. If dispatched to a terminal DSQ, + the BPF scheduler is done with it immediately. This provides the + performance benefit of avoiding the ``ops.enqueue()`` roundtrip while + maintaining correct state tracking.
Quoted 8 lines
Documentation/scheduler/sched-ext.rst The following briefly shows how a waking task is scheduled and executed. · line 289
Quoted 6 lines
Documentation/scheduler/sched-ext.rst +6
-0+ + The dequeue can happen for different reasons, distinguished by flags: + + 1. **Regular dispatch workflow**: when the task is dispatched from a + user-created DSQ to a terminal DSQ (leaving BPF custody for execution), + ``ops.dequeue()`` is triggered without any special flags.There's no requirement for the task do be on a user-created DSQ.
Ditto.
Quoted 21 lines
Quoted 20 lines
Documentation/scheduler/sched-ext.rst +16
-0+ + 2. **Core scheduling pick**: when ``CONFIG_SCHED_CORE`` is enabled and + core scheduling picks a task for execution while it's still in BPF + custody, ``ops.dequeue()`` is called with the + ``SCX_DEQ_CORE_SCHED_EXEC`` flag. + + 3. **Scheduling property change**: when a task property changes (via + operations like ``sched_setaffinity()``, ``sched_setscheduler()``, + priority changes, CPU migrations, etc.) while the task is still in + BPF custody, ``ops.dequeue()`` is called with the + ``SCX_DEQ_SCHED_CHANGE`` flag set in ``deq_flags``. + + **Important**: Once a task has left BPF custody (dispatched to a + terminal DSQ), property changes will not trigger ``ops.dequeue()``, + since the task is no longer being managed by the BPF scheduler. + 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...
Quoted 13 lines
include/linux/sched/ext.h struct scx_dispatch_q { · line 87
Quoted 9 lines
include/linux/sched/ext.h +1
-0@@ -84,6 +84,7 @@ struct scx_dispatch_q {/* scx_entity.flags */ enum scx_ent_flags {SCX_TASK_QUEUED =1 <<0 ,/* on ext runqueue */ +SCX_TASK_NEED_DEQ =1 <<1 ,/* task needs ops.dequeue() */ I think this could use a comment that connects this flag to the concept of BPF custody, so how about something like "task is in BPF custody, needs
ops.dequeue()when leaving it"?
Ack.
Quoted 31 lines
Quoted 8 lines
include/linux/sched/ext.h +0
-0SCX_TASK_RESET_RUNNABLE_AT =1 <<2 ,/* runnable_at should be reset */ SCX_TASK_DEQD_FOR_SLEEP = 1 << 3, /* last dequeue was for SLEEP */kernel/sched/ext.c +0
-0...
Quoted 22 lines
kernel/sched/ext.c +18
-0@@ -1103,6 +1125,27 @@ static void dispatch_enqueue(struct scx_sched *sch, struct scx_dispatch_q *dsq,dsq_mod_nr (dsq,1 ); p->scx.dsq = dsq; +/* +* Handle ops.dequeue() and custody tracking. +* +* Builtin DSQs (local, global, bypass) are terminal: the BPF +* scheduler is done with the task. If it was in BPF custody, call +* ops.dequeue() and clear the flag. +* +* User DSQs: Task is in BPF scheduler's custody. Set the flag so +* ops.dequeue() will be called when it leaves. +*/ +if (SCX_HAS_OP (sch, dequeue)) { +if (is_terminal_dsq (dsq->id)) { +if (p->scx.flags &SCX_TASK_NEED_DEQ ) +SCX_CALL_OP_TASK (sch,SCX_KF_REST , dequeue, + rq, p,0 ); + p->scx.flags &= ~SCX_TASK_NEED_DEQ ; + }else { + p->scx.flags |=SCX_TASK_NEED_DEQ ;
Quoted 8 lines
kernel/sched/ext.c static void dispatch_enqueue(struct scx_sched *sch, struct scx_dispatch_q *dsq, · line 1148
Quoted 3 lines
kernel/sched/ext.c +3
-0+ } + } +This is the only place where I see
SCX_TASK_NEED_DEQbeing set, which means it won't be set if the enqueued task is queued on the BPF scheduler's internal data structures rather than dispatched to a user-created DSQ. I don't think that's the behavior we're aiming for.
Right, I'll implement the right behavior (calling ops.dequeue()) for tasks stored in internal BPF queues.
Quoted 31 lines
Quoted 31 lines
kernel/sched/ext.c +19
-0@@ -1524,6 +1579,24 @@ static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags)switch (opss &SCX_OPSS_STATE_MASK ) {case SCX_OPSS_NONE : +/* +* Task is not in BPF data structures (either dispatched to +* a DSQ or running). Only call ops.dequeue() if the task +* is still in BPF scheduler's custody (%SCX_TASK_NEED_DEQ +* is set). +* +* If the task has already been dispatched to a terminal +* DSQ (local DSQ or %SCX_DSQ_GLOBAL), it has left the BPF +* scheduler's custody and the flag will be clear, so we +* skip ops.dequeue(). +* +* If this is a property change (not sleep/core-sched) and +* the task is still in BPF custody, set the +* %SCX_DEQ_SCHED_CHANGE flag. +*/ +if (SCX_HAS_OP (sch, dequeue) && + (p->scx.flags &SCX_TASK_NEED_DEQ )) +call_task_dequeue (sch, rq, p, deq_flags);break ;case SCX_OPSS_QUEUEING :/* @@ -1532,9 +1605,14 @@ static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags)*/ BUG ();case SCX_OPSS_QUEUED : +/*
Quoted 8 lines
kernel/sched/ext.c static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags) · line 1613
Quoted 5 lines
kernel/sched/ext.c +5
-0+* Task is still on the BPF scheduler (not dispatched yet). +* Call ops.dequeue() to notify. Add %SCX_DEQ_SCHED_CHANGE +* only for property changes, not for core-sched picks or +* sleep. +*/ The part of the comment about
SCX_DEQ_SCHED_CHANGElooks like it belongs incall_task_dequeue(), not here.
Ack.
Quoted 8 lines
kernel/sched/ext.c static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags) · line 1615
Quoted 5 lines
kernel/sched/ext.c +1
-2if (SCX_HAS_OP (sch, dequeue)) -SCX_CALL_OP_TASK (sch,SCX_KF_REST , dequeue, rq, - p, deq_flags); +call_task_dequeue (sch, rq, p, deq_flags);How about adding
WARN_ON_ONCE(!(p->scx.flags & SCX_TASK_NEED_DEQ))here or incall_task_dequeue()?
Ack.
Thanks for the review!
-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 the new ops.dequeue() semantics work correctly for all task lifecycle scenarios, including the distinction between terminal DSQs (where BPF scheduler is done with the task) and user DSQs (where BPF scheduler manages the task lifecycle), regardless of which callback performs the dispatch.
The test validates 6 scenarios:
- from ops.enqueue():
- scenario 0 (local DSQ): tasks dispatched to local DSQs bypass BPF scheduler entirely, they never enter BPF custody, so no ops.dequeue() should be called,
- scenario 1 (global DSQ): tasks dispatched to SCX_DSQ_GLOBAL also bypass BPF scheduler, like local DSQs, no ops.dequeue() should be called,
- scenario 2 (user DSQ): tasks enter BPF scheduler custody with full enqueue/dequeue lifecycle tracking and state machine validation (expects 1:1 enqueue/dequeue pairing).
- from ops.select_cpu():
- scenario 3 (local DSQ): identical behavior to scenario 0,
- scenario 4 (global DSQ): identical behavior to scenario 1,
- scenario 5 (user DSQ): identical behavior to scenario 2.
This verifies that:
- terminal DSQ dispatch (local, global) don't trigger ops.dequeue(),
- user DSQ dispatch has exact 1:1 ops.enqueue()/dequeue() pairing,
- dispatch dequeues have no flags (normal workflow),
- property change dequeues have the %SCX_DEQ_SCHED_CHANGE flag set,
- no duplicate enqueues or invalid state transitions are happening,
- ops.enqueue() and ops.select_cpu() dispatch paths behave identically.
--- tools/testing/selftests/sched_ext/Makefile | 1 + .../testing/selftests/sched_ext/dequeue.bpf.c | 334 ++++++++++++++++++ tools/testing/selftests/sched_ext/dequeue.c | 222 ++++++++++++ 3 files changed, 557 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 +334 -0
334 lines not on this page · raw message
tools/testing/selftests/sched_ext/dequeue.c new file +222 -0
222 lines not on this page · raw message
Signature · 1 line
2.53.0