sched_ext: Implement proper ops.dequeue() semantics
Subsystems (4)
Andrea Righi
reviewercover sched_ext: Implement proper ops.dequeue() semantics
Currently, ops.dequeue() is only invoked when tasks are still owned by the BPF scheduler (i.e., not yet dispatched to any DSQ). However, BPF schedulers may need to track task ownership transitions reliably.
The issue is that once a task is dispatched, the BPF scheduler loses visibility of when the task leaves its ownership. This makes it impossible to maintain accurate accounting (e.g., per-DSQ queued runtime sums) or properly track task lifecycle events.
This fixes the semantics of ops.dequeue() to ensure that every ops.enqueue() is properly balanced by a corresponding ops.dequeue() call.
With this, a task is considered "enqueued" from the moment ops.enqueue() is called until it either:
1. Gets dispatched (moved to a local DSQ for execution) or,
2. Is removed from the scheduler (e.g., blocks, or properties like CPU affinity or priority are changed)
When either happens, ops.dequeue() is invoked, ensuring reliable 1:1 pairing between enqueue and dequeue operations.
This allows BPF schedulers to reliably track task ownership and maintain accurate accounting.
Andrea Righi (2):
sched_ext: Fix ops.dequeue() semantics selftests/sched_ext: Add test to validate ops.dequeue()
Documentation/scheduler/sched-ext.rst | 22 +++ include/linux/sched/ext.h | 1 + kernel/sched/ext.c | 27 +++- tools/testing/selftests/sched_ext/Makefile | 1 + tools/testing/selftests/sched_ext/dequeue.bpf.c | 139 +++++++++++++++++++ tools/testing/selftests/sched_ext/dequeue.c | 172 ++++++++++++++++++++++++ 6 files changed, 361 insertions(+), 1 deletion(-) 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
Properly implement ops.dequeue() to ensure every ops.enqueue() is balanced by a corresponding ops.dequeue() call, regardless of whether the task is on a BPF data structure or already dispatched to a DSQ.
A task is considered enqueued when it is owned by the BPF scheduler. This ownership persists until the task is either dispatched (moved to a local DSQ for execution) or removed from the BPF scheduler, such as when it blocks waiting for an event or when its properties (for example, CPU affinity or priority) are updated.
When the task enters the BPF scheduler ops.enqueue() is invoked, when it leaves BPF scheduler ownership, ops.dequeue() is invoked.
This allows BPF schedulers to reliably track task ownership and maintain accurate accounting.
--- Documentation/scheduler/sched-ext.rst | 22 ++++++++++++++++++++++ include/linux/sched/ext.h | 1 + kernel/sched/ext.c | 27 ++++++++++++++++++++++++++- 3 files changed, 49 insertions(+), 1 deletion(-)
Documentation/scheduler/sched-ext.rst +22 -0
@@ -252,6 +252,26 @@ 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 is considered "enqueued" and + is owned by the BPF scheduler. Ownership is retained until the task is + either dispatched (moved to a local DSQ for execution) or dequeued + (removed from the scheduler due to a blocking event, or to modify a + property, like CPU affinity, priority, etc.). When the task leaves the + BPF scheduler ``ops.dequeue()`` is invoked. + + **Important**: ``ops.dequeue()`` is called for *any* enqueued task, + regardless of whether the task is still on a BPF data structure, or it + is already dispatched to a DSQ (global, local, or user DSQ) + + This guarantees that every ``ops.enqueue()`` will eventually be followed + by a ``ops.dequeue()``. This makes it reliable for BPF schedulers to + track task ownership and maintain accurate accounting, such as per-DSQ + queued runtime sums. + + 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 +339,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_OPS_ENQUEUED =1 <<1 ,/* ops.enqueue() was called */ 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 +26 -1
@@ -1390,6 +1390,9 @@ 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 */ + p->scx.flags |=SCX_TASK_OPS_ENQUEUED ; + ddsp_taskp =this_cpu_ptr (&direct_dispatch_task);WARN_ON_ONCE (*ddsp_taskp); *ddsp_taskp = p;
@@ -1522,6 +1525,21 @@ 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 currently being enqueued or queued on the BPF +* scheduler. Check if ops.enqueue() was called for this task. +*/ +if ((p->scx.flags &SCX_TASK_OPS_ENQUEUED ) && +SCX_HAS_OP (sch, dequeue)) { +/* +* ops.enqueue() was called and the task was dispatched. +* Call ops.dequeue() to notify the BPF scheduler that +* the task is leaving. +*/ +SCX_CALL_OP_TASK (sch,SCX_KF_REST , dequeue, rq, + p, deq_flags); + p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED ; + }break ;case SCX_OPSS_QUEUEING :/*
@@ -1530,9 +1548,16 @@ 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 owned by the BPF scheduler. Call ops.dequeue() +* to notify the BPF scheduler that the task is being +* removed. +*/ +if (SCX_HAS_OP (sch, dequeue)) {SCX_CALL_OP_TASK (sch,SCX_KF_REST , dequeue, rq, p, deq_flags); + p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED ; + }if (atomic_long_try_cmpxchg (&p->scx.ops_state, &opss,SCX_OPSS_NONE ))
Signature · 1 line
2.52.0
Re: [PATCH 1/2] sched_ext: Fix ops.dequeue() semantics
Quoted 13 lines · Andrea Righi
Properly implement
ops.dequeue()to ensure everyops.enqueue()is balanced by a correspondingops.dequeue()call, regardless of whether the task is on a BPF data structure or already dispatched to a DSQ.A task is considered enqueued when it is owned by the BPF scheduler. This ownership persists until the task is either dispatched (moved to a local DSQ for execution) or removed from the BPF scheduler, such as when it blocks waiting for an event or when its properties (for example, CPU affinity or priority) are updated.
When the task enters the BPF scheduler
ops.enqueue()is invoked, when it leaves BPF scheduler ownership,ops.dequeue()is invoked.
Quoted 6 lines
This allows BPF schedulers to reliably track task ownership and maintain accurate accounting.
Cc Emil Tsalapatis <[email protected]>Signed-off-by Andrea Righi <[email protected]>---
Hi Andrea,
This change looks reasonable to me. Some comments inline:
Quoted 10 lines
Documentation/scheduler/sched-ext.rst | 22 ++++++++++++++++++++++ include/linux/sched/ext.h | 1 + kernel/sched/ext.c | 27 ++++++++++++++++++++++++++- 3 files changed, 49 insertions(+), 1 deletion(-)Documentation/scheduler/sched-ext.rst +0
-0
Documentation/scheduler/sched-ext.rst The following briefly shows how a waking task is scheduled and executed. · line 261
Quoted 10 lines
Documentation/scheduler/sched-ext.rst +7
-0@@ -252,6 +252,26 @@ 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 is considered "enqueued" and + is owned by the BPF scheduler. Ownership is retained until the task is + either dispatched (moved to a local DSQ for execution) or dequeued + (removed from the scheduler due to a blocking event, or to modify a + property, like CPU affinity, priority, etc.). When the task leaves the + BPF scheduler ``ops.dequeue()`` is invoked. +
Can we say "leaves the scx class" instead? On direct dispatch we technically never insert the task into the BPF scheduler.
Quoted 30 lines
Documentation/scheduler/sched-ext.rst +15
-0+ **Important**: ``ops.dequeue()`` is called for *any* enqueued task, + regardless of whether the task is still on a BPF data structure, or it + is already dispatched to a DSQ (global, local, or user DSQ) + + This guarantees that every ``ops.enqueue()`` will eventually be followed + by a ``ops.dequeue()``. This makes it reliable for BPF schedulers to + track task ownership and maintain accurate accounting, such as per-DSQ + queued runtime sums. + + 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 +339,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 +0
-0
include/linux/sched/ext.h struct scx_dispatch_q { · line 87
Quoted 4 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_OPS_ENQUEUED =1 <<1 ,/* ops.enqueue() was called */
Can we rename this flag? For direct dispatch we never got enqueued. Something like "DEQ_ON_DISPATCH" would show the purpose of the flag more clearly.
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
kernel/sched/ext.c static void do_enqueue_task(struct rq *rq, struct task_struct *p, u64 enq_flags, · line 1395
Quoted 6 lines
kernel/sched/ext.c +3
-0@@ -1390,6 +1390,9 @@ 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 */ + p->scx.flags |=SCX_TASK_OPS_ENQUEUED ; +
Can we avoid setting this flag when we have no .dequeue() method? Otherwise it stays set forever AFAICT, even after the task has been sent to the runqueues.
Quoted 26 lines
kernel/sched/ext.c +15
-0ddsp_taskp =this_cpu_ptr (&direct_dispatch_task);WARN_ON_ONCE (*ddsp_taskp); *ddsp_taskp = p;@@ -1522,6 +1525,21 @@ 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 currently being enqueued or queued on the BPF +* scheduler. Check if ops.enqueue() was called for this task. +*/ +if ((p->scx.flags &SCX_TASK_OPS_ENQUEUED ) && +SCX_HAS_OP (sch, dequeue)) { +/* +* ops.enqueue() was called and the task was dispatched. +* Call ops.dequeue() to notify the BPF scheduler that +* the task is leaving. +*/ +SCX_CALL_OP_TASK (sch,SCX_KF_REST , dequeue, rq, + p, deq_flags); + p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED ; + }break ;case SCX_OPSS_QUEUEING :/*
kernel/sched/ext.c static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags) · line 1556
Quoted 10 lines
kernel/sched/ext.c +6
-1@@ -1530,9 +1548,16 @@ 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 owned by the BPF scheduler. Call ops.dequeue() +* to notify the BPF scheduler that the task is being +* removed. +*/ +if (SCX_HAS_OP (sch, dequeue)) {
Edge case, but if we have a .dequeue() method but not an .enqueue() we still make this call. Can we add flags & SCX_TASK_OPS_ENQUEUED as an extra condition to be consistent with the SCX_OPSS_NONE case above?
Quoted 7 lines
kernel/sched/ext.c +2
-0SCX_CALL_OP_TASK (sch,SCX_KF_REST , dequeue, rq, p, deq_flags); + p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED ; + }if (atomic_long_try_cmpxchg (&p->scx.ops_state, &opss,SCX_OPSS_NONE ))
Andrea Righi
reviewerRe: [PATCH 1/2] sched_ext: Fix ops.dequeue() semantics
Hi Emil,
Quoted 39 lines · Emil Tsalapatis
Quoted 13 lines · Andrea Righi
Properly implement
ops.dequeue()to ensure everyops.enqueue()is balanced by a correspondingops.dequeue()call, regardless of whether the task is on a BPF data structure or already dispatched to a DSQ.A task is considered enqueued when it is owned by the BPF scheduler. This ownership persists until the task is either dispatched (moved to a local DSQ for execution) or removed from the BPF scheduler, such as when it blocks waiting for an event or when its properties (for example, CPU affinity or priority) are updated.
When the task enters the BPF scheduler
ops.enqueue()is invoked, when it leaves BPF scheduler ownership,ops.dequeue()is invoked.Quoted 6 lines
This allows BPF schedulers to reliably track task ownership and maintain accurate accounting.
Cc Emil Tsalapatis <[email protected]>Signed-off-by Andrea Righi <[email protected]>---
Hi Andrea,
This change looks reasonable to me. Some comments inline:
Quoted 13 lines
Documentation/scheduler/sched-ext.rst | 22 ++++++++++++++++++++++ include/linux/sched/ext.h | 1 + kernel/sched/ext.c | 27 ++++++++++++++++++++++++++- 3 files changed, 49 insertions(+), 1 deletion(-)Documentation/scheduler/sched-ext.rst +0
-0@@ -252,6 +252,26 @@ The following briefly shows how a waking task is scheduled and executed. * Queue the task on the BPF side.
Quoted 10 lines
Documentation/scheduler/sched-ext.rst The following briefly shows how a waking task is scheduled and executed. · line 261
Quoted 7 lines
Documentation/scheduler/sched-ext.rst +7
-0+ Once ``ops.enqueue()`` is called, the task is considered "enqueued" and + is owned by the BPF scheduler. Ownership is retained until the task is + either dispatched (moved to a local DSQ for execution) or dequeued + (removed from the scheduler due to a blocking event, or to modify a + property, like CPU affinity, priority, etc.). When the task leaves the + BPF scheduler ``ops.dequeue()`` is invoked. +Can we say "leaves the scx class" instead? On direct dispatch we technically never insert the task into the BPF scheduler.
Hm.. I agree that'd be more accurate, but it might also be slightly misleading, as it could be interpreted as the task being moved to a different scheduling class. How about saying "leaves the enqueued state" instead, where enqueued means ops.enqueue() being called... I can't find a better name for this state, like "ops_enqueued", but that's be even more confusing. :)
Quoted 31 lines
Quoted 31 lines
Documentation/scheduler/sched-ext.rst +15
-0+ **Important**: ``ops.dequeue()`` is called for *any* enqueued task, + regardless of whether the task is still on a BPF data structure, or it + is already dispatched to a DSQ (global, local, or user DSQ) + + This guarantees that every ``ops.enqueue()`` will eventually be followed + by a ``ops.dequeue()``. This makes it reliable for BPF schedulers to + track task ownership and maintain accurate accounting, such as per-DSQ + queued runtime sums. + + 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 +339,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 +0
-0@@ -84,6 +84,7 @@ struct scx_dispatch_q {
Quoted 8 lines
include/linux/sched/ext.h struct scx_dispatch_q { · line 87
Quoted 4 lines
include/linux/sched/ext.h +1
-0/* scx_entity.flags */ enum scx_ent_flags {SCX_TASK_QUEUED =1 <<0 ,/* on ext runqueue */ +SCX_TASK_OPS_ENQUEUED =1 <<1 ,/* ops.enqueue() was called */ Can we rename this flag? For direct dispatch we never got enqueued. Something like "
DEQ_ON_DISPATCH" would show the purpose of the flag more clearly.
Good point. However, ops.dequeue() isn't only called on dispatch, it can also be triggered when a task property is changed.
So the flag should represent the "enqueued state" in the sense that ops.enqueue() has been called and a corresponding ops.dequeue() is expected. This is a lifecycle state, not an indication that the task is in any queue.
Would a more descriptive comment clarify this? Something like:
SCX_TASK_OPS_ENQUEUED = 1 << 1, /* Task in enqueued state: ops.enqueue()
called, ops.dequeue() will be called when task leaves this state. */
Quoted 12 lines
Quoted 12 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@@ -1390,6 +1390,9 @@ 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);
Quoted 7 lines
kernel/sched/ext.c static void do_enqueue_task(struct rq *rq, struct task_struct *p, u64 enq_flags, · line 1395
Quoted 3 lines
kernel/sched/ext.c +3
-0+/* Mark that ops.enqueue() is being called for this task */ + p->scx.flags |=SCX_TASK_OPS_ENQUEUED ; +Can we avoid setting this flag when we have no .dequeue() method? Otherwise it stays set forever AFAICT, even after the task has been sent to the runqueues.
Good catch! Definitely we don't need to set this for schedulers that don't implement ops.dequeue().
Quoted 33 lines
Quoted 33 lines
kernel/sched/ext.c +17
-1ddsp_taskp =this_cpu_ptr (&direct_dispatch_task);WARN_ON_ONCE (*ddsp_taskp); *ddsp_taskp = p;@@ -1522,6 +1525,21 @@ 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 currently being enqueued or queued on the BPF +* scheduler. Check if ops.enqueue() was called for this task. +*/ +if ((p->scx.flags &SCX_TASK_OPS_ENQUEUED ) && +SCX_HAS_OP (sch, dequeue)) { +/* +* ops.enqueue() was called and the task was dispatched. +* Call ops.dequeue() to notify the BPF scheduler that +* the task is leaving. +*/ +SCX_CALL_OP_TASK (sch,SCX_KF_REST , dequeue, rq, + p, deq_flags); + p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED ; + }break ;case SCX_OPSS_QUEUEING :/* @@ -1530,9 +1548,16 @@ 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 owned by the BPF scheduler. Call ops.dequeue()
Quoted 8 lines
kernel/sched/ext.c static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags) · line 1556
Quoted 4 lines
kernel/sched/ext.c +4
-0+* to notify the BPF scheduler that the task is being +* removed. +*/ +if (SCX_HAS_OP (sch, dequeue)) {Edge case, but if we have a .dequeue() method but not an .enqueue() we still make this call. Can we add flags &
SCX_TASK_OPS_ENQUEUEDas an extra condition to be consistent with theSCX_OPSS_NONEcase above?
Also good catch. Will add that.
Quoted 9 lines
kernel/sched/ext.c static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags) · line 1563
Quoted 8 lines
kernel/sched/ext.c +2
-0SCX_CALL_OP_TASK (sch,SCX_KF_REST , dequeue, rq, p, deq_flags); + p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED ; + }if (atomic_long_try_cmpxchg (&p->scx.ops_state, &opss,SCX_OPSS_NONE ))
Thanks,
-Andrea
Re: [PATCH 1/2] sched_ext: Fix ops.dequeue() semantics
Quoted 53 lines · Andrea Righi
Hi Emil,
Quoted 39 lines · Emil Tsalapatis
Quoted 13 lines · Andrea Righi
Properly implement
ops.dequeue()to ensure everyops.enqueue()is balanced by a correspondingops.dequeue()call, regardless of whether the task is on a BPF data structure or already dispatched to a DSQ.A task is considered enqueued when it is owned by the BPF scheduler. This ownership persists until the task is either dispatched (moved to a local DSQ for execution) or removed from the BPF scheduler, such as when it blocks waiting for an event or when its properties (for example, CPU affinity or priority) are updated.
When the task enters the BPF scheduler
ops.enqueue()is invoked, when it leaves BPF scheduler ownership,ops.dequeue()is invoked.Quoted 6 lines
This allows BPF schedulers to reliably track task ownership and maintain accurate accounting.
Cc Emil Tsalapatis <[email protected]>Signed-off-by Andrea Righi <[email protected]>---
Hi Andrea,
This change looks reasonable to me. Some comments inline:
Quoted 13 lines
Documentation/scheduler/sched-ext.rst | 22 ++++++++++++++++++++++ include/linux/sched/ext.h | 1 + kernel/sched/ext.c | 27 ++++++++++++++++++++++++++- 3 files changed, 49 insertions(+), 1 deletion(-)Documentation/scheduler/sched-ext.rst +0
-0@@ -252,6 +252,26 @@ The following briefly shows how a waking task is scheduled and executed. * Queue the task on the BPF side.Quoted 10 lines
Documentation/scheduler/sched-ext.rst The following briefly shows how a waking task is scheduled and executed. · line 261
Quoted 7 lines
Documentation/scheduler/sched-ext.rst +7
-0+ Once ``ops.enqueue()`` is called, the task is considered "enqueued" and + is owned by the BPF scheduler. Ownership is retained until the task is + either dispatched (moved to a local DSQ for execution) or dequeued + (removed from the scheduler due to a blocking event, or to modify a + property, like CPU affinity, priority, etc.). When the task leaves the + BPF scheduler ``ops.dequeue()`` is invoked. +Can we say "leaves the scx class" instead? On direct dispatch we technically never insert the task into the BPF scheduler.
Quoted 7 lines
Hm.. I agree that'd be more accurate, but it might also be slightly misleading, as it could be interpreted as the task being moved to a different scheduling class. How about saying "leaves the enqueued state" instead, where enqueued means
ops.enqueue()being called... I can't find a better name for this state, like "ops_enqueued", but that's be even more confusing. :)
I like "leaves the enqueued state", it implies that the task has no state in the scx scheduler.
Quoted 48 lines
Quoted 31 lines
Quoted 31 lines
Documentation/scheduler/sched-ext.rst +15
-0+ **Important**: ``ops.dequeue()`` is called for *any* enqueued task, + regardless of whether the task is still on a BPF data structure, or it + is already dispatched to a DSQ (global, local, or user DSQ) + + This guarantees that every ``ops.enqueue()`` will eventually be followed + by a ``ops.dequeue()``. This makes it reliable for BPF schedulers to + track task ownership and maintain accurate accounting, such as per-DSQ + queued runtime sums. + + 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 +339,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 +0
-0@@ -84,6 +84,7 @@ struct scx_dispatch_q {Quoted 8 lines
include/linux/sched/ext.h struct scx_dispatch_q { · line 87
Quoted 4 lines
include/linux/sched/ext.h +1
-0/* scx_entity.flags */ enum scx_ent_flags {SCX_TASK_QUEUED =1 <<0 ,/* on ext runqueue */ +SCX_TASK_OPS_ENQUEUED =1 <<1 ,/* ops.enqueue() was called */ Can we rename this flag? For direct dispatch we never got enqueued. Something like "
DEQ_ON_DISPATCH" would show the purpose of the flag more clearly.Good point. However,
ops.dequeue()isn't only called on dispatch, it can also be triggered when a task property is changed.So the flag should represent the "enqueued state" in the sense that
ops.enqueue()has been called and a correspondingops.dequeue()is expected. This is a lifecycle state, not an indication that the task is in any queue.
Quoted 6 lines
Would a more descriptive comment clarify this? Something like:
SCX_TASK_OPS_ENQUEUED= 1 << 1, /* Task in enqueued state:ops.enqueue()
called,ops.dequeue()will be called when task leaves this state. */
That makes sense, my reasoning was that we actually use the flag for is not whether the task is enqueued, but rather whether whether we need to call the dequeue callback when dequeueing from the SCX_OPSS_NONE state. Can the comment maybe more concretely explain this?
As an aside, I think this change makes it so we can remove the _OPSS_ state machine with some more refactoring.
Quoted 79 lines
Quoted 12 lines
Quoted 12 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@@ -1390,6 +1390,9 @@ 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);Quoted 7 lines
kernel/sched/ext.c static void do_enqueue_task(struct rq *rq, struct task_struct *p, u64 enq_flags, · line 1395
Quoted 3 lines
kernel/sched/ext.c +3
-0+/* Mark that ops.enqueue() is being called for this task */ + p->scx.flags |=SCX_TASK_OPS_ENQUEUED ; +Can we avoid setting this flag when we have no .dequeue() method? Otherwise it stays set forever AFAICT, even after the task has been sent to the runqueues.
Good catch! Definitely we don't need to set this for schedulers that don't implement
ops.dequeue().Quoted 33 lines
Quoted 33 lines
kernel/sched/ext.c +17
-1ddsp_taskp =this_cpu_ptr (&direct_dispatch_task);WARN_ON_ONCE (*ddsp_taskp); *ddsp_taskp = p;@@ -1522,6 +1525,21 @@ 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 currently being enqueued or queued on the BPF +* scheduler. Check if ops.enqueue() was called for this task. +*/ +if ((p->scx.flags &SCX_TASK_OPS_ENQUEUED ) && +SCX_HAS_OP (sch, dequeue)) { +/* +* ops.enqueue() was called and the task was dispatched. +* Call ops.dequeue() to notify the BPF scheduler that +* the task is leaving. +*/ +SCX_CALL_OP_TASK (sch,SCX_KF_REST , dequeue, rq, + p, deq_flags); + p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED ; + }break ;case SCX_OPSS_QUEUEING :/* @@ -1530,9 +1548,16 @@ 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 owned by the BPF scheduler. Call ops.dequeue() Quoted 8 lines
kernel/sched/ext.c static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags) · line 1556
Quoted 4 lines
kernel/sched/ext.c +4
-0+* to notify the BPF scheduler that the task is being +* removed. +*/ +if (SCX_HAS_OP (sch, dequeue)) {Edge case, but if we have a .dequeue() method but not an .enqueue() we still make this call. Can we add flags &
SCX_TASK_OPS_ENQUEUEDas an extra condition to be consistent with theSCX_OPSS_NONEcase above?Also good catch. Will add that.
Quoted 9 lines
kernel/sched/ext.c static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags) · line 1563
Quoted 8 lines
kernel/sched/ext.c +2
-0SCX_CALL_OP_TASK (sch,SCX_KF_REST , dequeue, rq, p, deq_flags); + p->scx.flags &= ~SCX_TASK_OPS_ENQUEUED ; + }if (atomic_long_try_cmpxchg (&p->scx.ops_state, &opss,SCX_OPSS_NONE ))Thanks,
-Andrea
Tejun Heo
reviewerRe: [PATCH 1/2] sched_ext: Fix ops.dequeue() semantics
In reply to Andrea RighiHello, Andrea.
On Fri, Dec 19, 2025 at 11:43:14PM +0100, Andrea Righi wrote:
...
Quoted 5 lines
Documentation/scheduler/sched-ext.rst +5
-0+ Once ``ops.enqueue()`` is called, the task is considered "enqueued" and + is owned by the BPF scheduler. Ownership is retained until the task is + either dispatched (moved to a local DSQ for execution) or dequeued + (removed from the scheduler due to a blocking event, or to modify a + property, like CPU affinity, priority, etc.). When the task leaves the
Documentation/scheduler/sched-ext.rst The following briefly shows how a waking task is scheduled and executed. · line 269
Quoted 10 lines
Documentation/scheduler/sched-ext.rst +10
-0+ BPF scheduler ``ops.dequeue()`` is invoked. + + **Important**: ``ops.dequeue()`` is called for *any* enqueued task, + regardless of whether the task is still on a BPF data structure, or it + is already dispatched to a DSQ (global, local, or user DSQ) + + This guarantees that every ``ops.enqueue()`` will eventually be followed + by a ``ops.dequeue()``. This makes it reliable for BPF schedulers to + track task ownership and maintain accurate accounting, such as per-DSQ + queued runtime sums.
While this works, from the BPF sched's POV, there's no way to tell whether an ops.dequeue() call is from the task being actually dequeued or the follow-up to the dispatch operation it just did. This won't make much difference if ops.dequeue() is just used for accounting purposes, but, a scheduler which uses an arena data structure for queueing would likely need to perform extra tests to tell whether the task needs to be dequeued from the arena side. I *think* hot path (ops.dequeue() following the task's dispatch) can be a simple lockless test, so this may be okay, but from API POV, it can probably be better.
The counter interlocking point is scx_bpf_dsq_insert(). If we can synchronize scx_bpf_dsq_insert() and dequeue so that ops.dequeue() is not called for a successfully inserted task, I think the semantics would be neater - an enqueued task is either dispatched or dequeued. Due to the async dispatch operation, this likely is difficult to do without adding extra sync operations in scx_bpf_dsq_insert(). However, I *think* we may be able to get rid of dspc and async inserting if we call ops.dispatch() w/ rq lock dropped. That may make the whole dispatch path simpler and the behavior neater too. What do you think?
Thanks.
Signature · 1 line
tejun
Tejun Heo
reviewerRe: [PATCH 1/2] sched_ext: Fix ops.dequeue() semantics
Hello,
Quoted 10 lines · Tejun Heo
While this works, from the BPF sched's POV, there's no way to tell whether an
ops.dequeue()call is from the task being actually dequeued or the follow-up to the dispatch operation it just did. This won't make much difference ifops.dequeue()is just used for accounting purposes, but, a scheduler which uses an arena data structure for queueing would likely need to perform extra tests to tell whether the task needs to be dequeued from the arena side. I *think* hot path (ops.dequeue()following the task's dispatch) can be a simple lockless test, so this may be okay, but from API POV, it can probably be better.
Quoted 9 lines
The counter interlocking point is
scx_bpf_dsq_insert(). If we can synchronizescx_bpf_dsq_insert()and dequeue so thatops.dequeue()is not called for a successfully inserted task, I think the semantics would be neater - an enqueued task is either dispatched or dequeued. Due to the async dispatch operation, this likely is difficult to do without adding extra sync operations inscx_bpf_dsq_insert(). However, I *think* we may be able to get rid of dspc and async inserting if we callops.dispatch()w/ rq lock dropped. That may make the whole dispatch path simpler and the behavior neater too. What do you think?
I sat down and went through the code to see whether I was actually making sense, and I wasn't:
The async dispatch buffering is necessary to avoid lock inversion between rq lock and whatever locks the BPF scheduler might be using internally. This is necessary because enqueue path runs with rq lock held. Thus, any lock that BPF sched uses in tne enqueue path has to nest inside rq lock.
In dispatch, scx_bpf_dsq_insert() is likely to be called with the same BPF sched side lock held. If we try to do rq lock dancing synchronously, we can end up trying to grab rq lock while holding BPF side lock leading to deadlock.
Kernel side has no control over BPF side locking, so the asynchronous operation is there to side-step the issue. I don't see a good way to make this synchronous.
So, please ignore that part. That's non-sense. I still wonder whether we can create some interlocking between scx_bpf_dsq_insert() and ops.dequeue() without making hot path slower. I'll think more about it.
Thanks.
Signature · 1 line
tejun
Tejun Heo
reviewerRe: [PATCH 1/2] sched_ext: Fix ops.dequeue() semantics
Hello again, again.
On Sun, Dec 28, 2025 at 01:28:04PM -1000, Tejun Heo wrote:
...
Quoted 3 lines
So, please ignore that part. That's non-sense. I still wonder whether we can create some interlocking between
scx_bpf_dsq_insert()andops.dequeue()without making hot path slower. I'll think more about it.
And we can't create an interlocking between scx_bpf_dsq_insert() and ops.dequeue() without adding extra atomic operations in hot paths. The only thing shared is task rq lock and dispatch path can't do that synchronously. So, yeah, it looks like the best we can do is always letting the BPF sched know and let it figure out locking and whether the task needs to be dequeued from BPF side.
Thanks.
Signature · 1 line
tejun
Andrea Righi
reviewerRe: [PATCH 1/2] sched_ext: Fix ops.dequeue() semantics
Hi Tejun,
Quoted 8 lines · Tejun Heo
Hello again, again.
On Sun, Dec 28, 2025 at 01:28:04PM -1000, Tejun Heo wrote:
...Quoted 3 lines
So, please ignore that part. That's non-sense. I still wonder whether we can create some interlocking between
scx_bpf_dsq_insert()andops.dequeue()without making hot path slower. I'll think more about it.
Quoted 6 lines
And we can't create an interlocking between
scx_bpf_dsq_insert()andops.dequeue()without adding extra atomic operations in hot paths. The only thing shared is task rq lock and dispatch path can't do that synchronously. So, yeah, it looks like the best we can do is always letting the BPF sched know and let it figure out locking and whether the task needs to be dequeued from BPF side.
How about setting a flag in deq_flags to distinguish between a "dispatch" dequeue vs a real dequeue (due to property changes or other reasons)?
We should be able to pass this information in a reliable way without any additional synchronization in the hot paths. This would let schedulers that use arena data structures check the flag instead of doing their own internal lookups.
And it would also allow us to provide both semantics:
1) Catch real dequeues that need special BPF-side actions (check the flag)
2) Track all ops.enqueue()/ops.dequeue() pairs for accounting purposes (ignore the flag)
Thanks,
-Andrea
Re: [PATCH 1/2] sched_ext: Fix ops.dequeue() semantics
Quoted 26 lines · Andrea Righi
Hi Tejun,
Quoted 8 lines · Tejun Heo
Hello again, again.
On Sun, Dec 28, 2025 at 01:28:04PM -1000, Tejun Heo wrote:
...Quoted 3 lines
So, please ignore that part. That's non-sense. I still wonder whether we can create some interlocking between
scx_bpf_dsq_insert()andops.dequeue()without making hot path slower. I'll think more about it.Quoted 6 lines
And we can't create an interlocking between
scx_bpf_dsq_insert()andops.dequeue()without adding extra atomic operations in hot paths. The only thing shared is task rq lock and dispatch path can't do that synchronously. So, yeah, it looks like the best we can do is always letting the BPF sched know and let it figure out locking and whether the task needs to be dequeued from BPF side.How about setting a flag in
deq_flagsto distinguish between a "dispatch" dequeue vs a real dequeue (due to property changes or other reasons)?We should be able to pass this information in a reliable way without any additional synchronization in the hot paths. This would let schedulers that use arena data structures check the flag instead of doing their own internal lookups.
Quoted 5 lines
And it would also allow us to provide both semantics:
1) Catch real dequeues that need special BPF-side actions (check the flag)
2) Track all ops.enqueue()/ops.dequeue() pairs for accounting purposes (ignore the flag)
IMO the extra flag suffices for arena-based queueing, the arena data structures already have to track the state of the task already:
Even without the flag it should be possible to infer the task is in in from inside the BPF code. For example, calling .dequeue() while the task is in an arena queue means the task got dequeued _after_ being dispatched, while calling .dequeue() on a queued task means we are removing it because of a true dequeue event (e.g. sched_setaffinity() was called). The only edge case in the logic is if a true dequeue event happens between .dispatch() and .dequeue(), but a new flag would take care of that.
Quoted 2 lines
Thanks,
-Andrea
Tejun Heo
reviewerRe: [PATCH 1/2] sched_ext: Fix ops.dequeue() semantics
In reply to Andrea RighiHello,
Documentation/scheduler/sched-ext.rst The following briefly shows how a waking task is scheduled and executed. · line 256
Quoted 2 lines · Andrea Righi
Documentation/scheduler/sched-ext.rst +2
-0+ Once ``ops.enqueue()`` is called, the task is considered "enqueued" and + is owned by the BPF scheduler. Ownership is retained until the task is
Can we avoid using "ownership" for this? From user's POV, this is fine but kernel side internally uses the word for different purposes - e.g. we say the BPF side owns the task if the task's SCX_OPSS_QUEUED is set (ie. it's on BPF data structure, not on a DSQ). Here, the ownership encompasses both kernel-side and BPF-side queueing, so the term becomes rather confusing. Maybe we can stick with "queued" or "enqueued"?
Thanks.
Signature · 1 line
tejun
Andrea Righi
reviewerRe: [PATCH 1/2] sched_ext: Fix ops.dequeue() semantics
Hi,
Quoted 6 lines · Tejun Heo
Hello,
Documentation/scheduler/sched-ext.rst The following briefly shows how a waking task is scheduled and executed. · line 256
Quoted 2 lines · Andrea Righi
Documentation/scheduler/sched-ext.rst +2
-0+ Once ``ops.enqueue()`` is called, the task is considered "enqueued" and + is owned by the BPF scheduler. Ownership is retained until the task is
Quoted 6 lines
Can we avoid using "ownership" for this? From user's POV, this is fine but kernel side internally uses the word for different purposes - e.g. we say the BPF side owns the task if the task's
SCX_OPSS_QUEUEDis set (ie. it's on BPF data structure, not on a DSQ). Here, the ownership encompasses both kernel-side and BPF-side queueing, so the term becomes rather confusing. Maybe we can stick with "queued" or "enqueued"?
Agreed. I can't find a better term to describe this phase of the lifecycle, where ops.enqueue() has been called and the task remains in that state until the corresponding ops.dequeue() occurs (either due to a "dispatch" dequeue or "real" dequeue).
So maybe we should stick with "enqueued" and clarify exactly what this state means.
Thanks,
-Andrea
Tejun Heo
reviewerRe: [PATCH 1/2] sched_ext: Fix ops.dequeue() semantics
In reply to Andrea RighiSorry about the million replies. Pretty squirrel brained right now.
kernel/sched/ext.c static void do_enqueue_task(struct rq *rq, struct task_struct *p, u64 enq_flags, · line 1394
Quoted 6 lines · Andrea Righi
kernel/sched/ext.c +2
-0@@ -1390,6 +1390,9 @@ 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 */ + p->scx.flags |=SCX_TASK_OPS_ENQUEUED ;
Is this guaranteed to be cleared after dispatch? ops_dequeue() is called from dequeue_task_scx() and set_next_task_scx(). It looks like the call from set_next_task_scx() may end up calling ops.dequeue() when the task starts running, this seems mostly accidental.
- The BPF sched probably expects ops.dequeue() call immediately after dispatch rather than on the running transition. e.g. imagine a scenario where a BPF sched dispatches multiple tasks to a local DSQ. Wouldn't the expectation be that ops.dequeue() is called as soon as a task is dispatched into a local DSQ?
- If this depends on the ops_dequeue() call from set_next_task_scx(), it'd also be using the wrong DEQ flag - SCX_DEQ_CORE_SCHED_EXEC - for regular ops.dequeue() following a dispatch. That call there is that way only because ops_dequeue() didn't do anything when OPSS_NONE.
Thanks.
Signature · 1 line
tejun
Andrea Righi
reviewerRe: [PATCH 1/2] sched_ext: Fix ops.dequeue() semantics
Quoted 21 lines · Tejun Heo
Sorry about the million replies. Pretty squirrel brained right now.
kernel/sched/ext.c static void do_enqueue_task(struct rq *rq, struct task_struct *p, u64 enq_flags, · line 1394
Quoted 6 lines · Andrea Righi
kernel/sched/ext.c +2
-0@@ -1390,6 +1390,9 @@ 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 */ + p->scx.flags |=SCX_TASK_OPS_ENQUEUED ;Is this guaranteed to be cleared after dispatch?
ops_dequeue()is called fromdequeue_task_scx()andset_next_task_scx(). It looks like the call fromset_next_task_scx()may end up callingops.dequeue()when the task starts running, this seems mostly accidental.- The BPF sched probably expects
ops.dequeue()call immediately after dispatch rather than on the running transition. e.g. imagine a scenario where a BPF sched dispatches multiple tasks to a local DSQ. Wouldn't the expectation be thatops.dequeue()is called as soon as a task is dispatched into a local DSQ?
Quoted 4 lines
- If this depends on the
ops_dequeue()call fromset_next_task_scx(), it'd also be using the wrong DEQ flag -SCX_DEQ_CORE_SCHED_EXEC- for regularops.dequeue()following a dispatch. That call there is that way only becauseops_dequeue()didn't do anything whenOPSS_NONE.
You're right, the flag should be cleared and ops.dequeue() should be called immediately when the async dispatch completes and the task is inserted into the DSQ. I'll add an explicit ops.dequeue() call in the dispatch completion path.
Thanks,
-Andrea
Andrea Righi
reviewerPATCH 2/2 selftests/sched_ext: Add test to validate ops.dequeue()
In reply to Andrea RighiAdd a kselftest to validate ops.dequeue() semantics with direct dispatch, user DSQ dispatch, affinity changes and verify that any ops.enqueue() is balanced by a corresponding ops.dequeue().
--- tools/testing/selftests/sched_ext/Makefile | 1 + .../testing/selftests/sched_ext/dequeue.bpf.c | 139 ++++++++++++++ tools/testing/selftests/sched_ext/dequeue.c | 172 ++++++++++++++++++ 3 files changed, 312 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 +139 -0
139 lines not on this page · raw message
tools/testing/selftests/sched_ext/dequeue.c new file +172 -0
172 lines not on this page · raw message
Signature · 1 line
2.52.0
Re: [PATCH 2/2] selftests/sched_ext: Add test to validate ops.dequeue()
Quoted 7 lines · Andrea Righi
Add a kselftest to validate
ops.dequeue()semantics with direct dispatch, user DSQ dispatch, affinity changes and verify that anyops.enqueue()is balanced by a correspondingops.dequeue().Cc Emil Tsalapatis <[email protected]>Signed-off-by Andrea Righi <[email protected]>---
Hi Andrea,
Quoted 50 lines
tools/testing/selftests/sched_ext/Makefile | 1 + .../testing/selftests/sched_ext/dequeue.bpf.c | 139 ++++++++++++++ tools/testing/selftests/sched_ext/dequeue.c | 172 ++++++++++++++++++ 3 files changed, 312 insertions(+) create mode 100644 tools/testing/selftests/sched_ext/dequeue.bpf.c create mode 100644 tools/testing/selftests/sched_ext/dequeue.ctools/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 +25
-0@@ -0,0 +1,139 @@ +// 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 +*/ +u64 enqueue_cnt, dequeue_cnt; +
tools/testing/selftests/sched_ext/dequeue.bpf.c line 35
Quoted 10 lines
tools/testing/selftests/sched_ext/dequeue.bpf.c new file +10
-0+/* +* Test scenarios: +* - 0: Dispatch to local DSQ +* - 1: Dispatch to shared DSQ +*/ +u32 test_scenario; + +/* Per-task state */ +struct task_ctx { +u64 enqueued;/* was this task enqueued? */
Do we use this for anything? If not, can we remove it? We can also just do an extra sanity check with it during enqueues/dequeues to ensure we have no double operations.
Quoted 282 lines
tools/testing/selftests/sched_ext/dequeue.bpf.c new file +104
-0+}; + +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 ; + + tctx->enqueued =1 ; + +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 ; + + tctx->enqueued =0 ; +} + +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 +172
-0@@ -0,0 +1,172 @@ +// 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; +u64 enq_delta, 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; + + 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; + +printf ("%s:\n" , scenario_name); +printf (" enqueues: %lu\n" , (unsigned long )enq_delta); +printf (" dequeues: %lu\n" , (unsigned long )deq_delta); + +/* Validate that we got enqueue and dequeue events */ +SCX_GT (enq_delta,0 ); +SCX_GT (deq_delta,0 ); + +if (enq_delta > deq_delta) +SCX_FAIL ("Too many enqueues without dequeues: %lu enqueues, %lu dequeues" , + (unsigned long )enq_delta, (unsigned long )deq_delta); +else if (deq_delta > enq_delta) +SCX_FAIL ("More dequeues than enqueues: %lu enqueues, %lu dequeues" , + (unsigned long )enq_delta, (unsigned long )deq_delta); + +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 ("\nAll scenarios passed\n" ); +printf ("-> Validated: ops.dequeue() is called for tasks on local DSQ\n" ); +printf ("-> Validated: ops.dequeue() is called for tasks on user DSQ\n" ); +printf ("-> Validated: Every enqueue is balanced with dequeue or execution\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)
Andrea Righi
reviewerRe: [PATCH 2/2] selftests/sched_ext: Add test to validate ops.dequeue()
Hi Emil,
Quoted 69 lines · Emil Tsalapatis
Quoted 7 lines · Andrea Righi
Add a kselftest to validate
ops.dequeue()semantics with direct dispatch, user DSQ dispatch, affinity changes and verify that anyops.enqueue()is balanced by a correspondingops.dequeue().Cc Emil Tsalapatis <[email protected]>Signed-off-by Andrea Righi <[email protected]>---
Reviewed-by Emil Tsalapatis <[email protected]>Hi Andrea,
Quoted 56 lines
tools/testing/selftests/sched_ext/Makefile | 1 + .../testing/selftests/sched_ext/dequeue.bpf.c | 139 ++++++++++++++ tools/testing/selftests/sched_ext/dequeue.c | 172 ++++++++++++++++++ 3 files changed, 312 insertions(+) create mode 100644 tools/testing/selftests/sched_ext/dequeue.bpf.c create mode 100644 tools/testing/selftests/sched_ext/dequeue.ctools/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 +31
-0@@ -0,0 +1,139 @@ +// 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 +*/ +u64 enqueue_cnt, dequeue_cnt; + +/* +* Test scenarios: +* - 0: Dispatch to local DSQ +* - 1: Dispatch to shared DSQ +*/ +u32 test_scenario;
Quoted 8 lines
tools/testing/selftests/sched_ext/dequeue.bpf.c line 35
Quoted 4 lines
tools/testing/selftests/sched_ext/dequeue.bpf.c new file +4
-0+ +/* Per-task state */ +struct task_ctx { +u64 enqueued;/* was this task enqueued? */ Do we use this for anything? If not, can we remove it? We can also just do an extra sanity check with it during enqueues/dequeues to ensure we have no double operations.
Oh yes, the intention was to use this to detect duplicate ops.enqueue() calls, but I forgot to add the actual check in ops.enqueue(). I'll add that in the next version.
Thanks!
-Andrea