diff options
Diffstat (limited to 'kernel/sched/ext/ext.c')
| -rw-r--r-- | kernel/sched/ext/ext.c | 1323 |
1 files changed, 975 insertions, 348 deletions
diff --git a/kernel/sched/ext/ext.c b/kernel/sched/ext/ext.c index 050c27edee3f..ffaab9fafca8 100644 --- a/kernel/sched/ext/ext.c +++ b/kernel/sched/ext/ext.c @@ -24,6 +24,17 @@ DEFINE_RAW_SPINLOCK(scx_sched_lock); +/* + * Block a retained proxy donor, telling put_prev_task_scx() that the donor is + * about to be dequeued and must not be reenqueued. + */ +static void scx_block_proxy_donor(struct rq *rq, struct task_struct *p) +{ + rq->scx.flags |= SCX_RQ_PROXY_BLOCKING; + sched_proxy_block_task(rq, p); + rq->scx.flags &= ~SCX_RQ_PROXY_BLOCKING; +} + bool __scx_allow_proxy_exec(const struct task_struct *p) { struct scx_sched *sch; @@ -47,7 +58,7 @@ void scx_prepare_task_sched_change(struct task_struct *p) lockdep_assert_rq_held(task_rq(p)); update_rq_clock(task_rq(p)); - sched_proxy_block_task(task_rq(p), p); + scx_block_proxy_donor(task_rq(p), p); } /* @@ -377,9 +388,12 @@ static const struct sched_class *scx_setscheduler_class(struct task_struct *p) return __setscheduler_class(p->policy, p->prio); } -static struct scx_dispatch_q *bypass_enq_target_dsq(struct scx_sched *sch, s32 cpu) +static struct scx_dispatch_q *bypass_enq_target_dsq(struct scx_sched *sch, struct rq *rq, + struct task_struct *p, u64 *enq_flags) { -#ifdef CONFIG_EXT_SUB_SCHED + struct scx_sched *host = scx_exec_sched(sch, cpu_of(rq)); + struct scx_dispatch_q *dsq; + /* * If @sch is a sub-sched which is bypassing, its tasks should go into * the bypass DSQs of the nearest ancestor which is not bypassing. The @@ -390,12 +404,29 @@ static struct scx_dispatch_q *bypass_enq_target_dsq(struct scx_sched *sch, s32 c * Whenever a sched starts bypassing, all runnable tasks in its subtree * are re-enqueued after scx_bypassing() is turned on, guaranteeing that * all tasks are transferred to the right DSQs. - */ - while (scx_parent(sch) && scx_bypassing(sch, cpu)) - sch = scx_parent(sch); -#endif /* CONFIG_EXT_SUB_SCHED */ - - return scx_bypass_dsq(sch, cpu); + * + * A cpu's dispatch only descends into a host holding %SCX_CAP_BASE on + * it, so the bypass DSQ of a host without BASE here is never consumed. + * Send @p to rescue on this cpu instead, resolving against @host. + * scx_dispatch_enqueue() resolves a local DSQ again, against the + * bypassing @sch. %SCX_ENQ_IGNORE_CAPS makes that second resolution + * admit @p. + * + * A migration-disabled task can't leave this cpu, and a task with a + * migration pending must run here until the migration moves it. Either + * would wait on the unconsumed bypass DSQ until the host regains BASE. + * Resolve them too when rescue is disabled. The resolution admits both + * to the local DSQ, as it does any insert of such a task. + */ + if (unlikely(scx_missing_caps(host, cpu_of(rq), SCX_CAP_BASE)) && + (scx_rescue_enabled() || is_migration_disabled(p) || p->migration_pending)) { + *enq_flags |= SCX_ENQ_RESCUE; + dsq = scx_resolve_local_dsq(host, rq, p, enq_flags); + *enq_flags |= SCX_ENQ_IGNORE_CAPS; + } else { + dsq = scx_bypass_dsq(host, cpu_of(rq)); + } + return dsq; } /** @@ -431,6 +462,14 @@ static bool rq_is_open(struct rq *rq, u64 enq_flags) */ /* + * A local insertion can raise next_class to ext while the donor is + * still idle. Keep the rq open so that the local DSQ head is not + * unnecessarily reenqueued before the CPU can pick it. + */ + if (rq->donor == rq->idle) + return true; + + /* * If we're in the dispatch path holding rq lock, $donor may or may not * be ready depending on whether the on-going dispatch decides to extend * $donor's slice. We say yes here and resolve it at the end of dispatch. @@ -549,11 +588,13 @@ enum scx_dsq_iter_flags { /* iterate in the reverse dispatch order */ SCX_DSQ_ITER_REV = 1U << 16, + __SCX_DSQ_ITER_HAS_REENQ = 1U << 29, __SCX_DSQ_ITER_HAS_SLICE = 1U << 30, __SCX_DSQ_ITER_HAS_VTIME = 1U << 31, __SCX_DSQ_ITER_USER_FLAGS = SCX_DSQ_ITER_REV, __SCX_DSQ_ITER_ALL_FLAGS = __SCX_DSQ_ITER_USER_FLAGS | + __SCX_DSQ_ITER_HAS_REENQ | __SCX_DSQ_ITER_HAS_SLICE | __SCX_DSQ_ITER_HAS_VTIME, }; @@ -1121,9 +1162,10 @@ static void schedule_deferred_locked(struct rq *rq) return; /* - * If in dispatch, the balance callbacks will be called before rq lock - * is released. Schedule one. - * + * If in dispatch without proxy execution, the balance callbacks will + * be called before rq lock is released. Schedule one. With proxy + * execution, proxy resolution can zap the callbacks without another + * SCX dispatch to requeue them, so use irq_work instead. * * We can't directly insert the callback into the * rq's list: The call can drop its lock and make the pending balance @@ -1131,7 +1173,7 @@ static void schedule_deferred_locked(struct rq *rq) * * Just let dispatch_one() know that it must do it itself. */ - if (rq->scx.flags & SCX_RQ_IN_DISPATCH) { + if ((rq->scx.flags & SCX_RQ_IN_DISPATCH) && !sched_proxy_exec()) { rq->scx.flags |= SCX_RQ_BAL_CB_PENDING; return; } @@ -1144,6 +1186,36 @@ static void schedule_deferred_locked(struct rq *rq) schedule_deferred(rq); } +static void resched_irq_workfn(struct irq_work *irq_work) +{ + struct rq *rq = container_of(irq_work, struct rq, scx.resched_irq_work); + + guard(rq_lock)(rq); + /* a higher class task would only be picked again, see kick_one_cpu() */ + if (!sched_class_above(rq->donor->sched_class, &ext_sched_class)) + resched_curr(rq); + scx_rq_lock_drop(rq); +} + +/** + * scx_resched_curr_deferred - Reschedule @rq's cpu from hard irq work on it + * @rq: rq to reschedule + * + * A kick, like a direct resched, only guarantees that a scheduling event on the + * cpu completes after it, and that can be the one in progress. Work that a pick + * processes only at the start of its dispatch, such as the ecaps syncs, can be + * queued after that point and miss the pick. A pick on @rq's cpu runs with IRQs + * off, so the irq work runs after it, and the scheduling event its resched + * triggers starts after this call. A sibling's core scheduling pick for @rq + * isn't covered. A cpu running a task of a higher class isn't rescheduled, as + * its pick would return that task again. @rq's cpu must stay online until the + * irq work is queued. + */ +void scx_resched_curr_deferred(struct rq *rq) +{ + irq_work_queue_on(&rq->scx.resched_irq_work, cpu_of(rq)); +} + #ifdef CONFIG_NO_HZ_FULL static void scx_proxy_tick_bal_cb(struct rq *rq) { @@ -1189,6 +1261,14 @@ void scx_proxy_reenqueue_retry(struct rq *rq, struct task_struct *next) scx_proxy_update_tick(rq, next); #endif + /* + * A higher priority class may wake up while @rq is transiently idle + * for proxy resolution. wakeup_preempt_scx() isn't invoked in that + * case, so reenqueue IMMED donors parked on the local DSQ here. + */ + if (rq->scx.nr_immed && sched_class_above(rq->next_class, &ext_sched_class)) + scx_schedule_reenq_local(rq, 0); + if (rq->scx.flags & SCX_RQ_PROXY_RETRY) { rq->scx.flags &= ~SCX_RQ_PROXY_RETRY; schedule_deferred_locked(rq); @@ -1211,6 +1291,18 @@ void schedule_dsq_reenq(struct scx_sched *sch, struct scx_dispatch_q *dsq, rq = container_of(dsq, struct rq, scx.local_dsq); /* + * An inactive cpu's local DSQ holds only tasks that are bound + * to it or are being moved off, so a reenq of it is pointless. + * Once balance push is installed, queue_balance_callback() also + * drops the callback that would run a reenq requested from + * dispatch, and irq_work_queue_on() can't reach an offline cpu. + * The reenq's node would then stay on this rq's list after + * @sch's pcpu is freed. + */ + if (unlikely(!cpu_active(cpu_of(rq)))) + return; + + /* * A sub-sched lacking baseline access on the target cid has no * business triggering IPIs. The lockless test is fine: slipping * through right after a revoke is harmless and a wrong denial @@ -1266,7 +1358,9 @@ void schedule_dsq_reenq(struct scx_sched *sch, struct scx_dispatch_q *dsq, WRITE_ONCE(dru->flags, dru->flags | reenq_flags); } } else { - scx_error(sch, "DSQ 0x%llx not allowed for reenq", dsq->id); + /* destroyed since the caller resolved it, nothing to reenq */ + if (READ_ONCE(dsq->id) != SCX_DSQ_INVALID) + scx_error(sch, "DSQ 0x%llx not allowed for reenq", dsq->id); return; } @@ -1324,7 +1418,8 @@ enum scx_slice_oob_consts { * p->scx.slice_oob, applied under @p's rq lock at the next slice consideration. * * While %SCX_TASK_PROTECTED is set, every scheduler-reachable slice update is - * refused. See set_task_slice_keep_oob(). + * refused. See set_task_slice_keep_oob(). A kernel slice, see + * %SCX_TASK_KERNEL_SLICE, can be shortened but not extended. * * dsq_vtime orders the next PRIQ insertion and has no running-side consumer, so * scx_bpf_task_set_dsq_vtime() writes it directly. Fork-time init and direct @@ -1411,8 +1506,8 @@ bool scx_set_task_slice(struct task_struct *p, u64 slice) * @rq: rq @p is on * @p: task of interest * - * End what rides on the slice - the protection, and the rescue if @p is being - * rescued. + * End what rides on the slice - the protection, the kernel's ownership of the + * slice, and the rescue if @p is being rescued. * * A dequeue normally ends the slice too. The exception is a save/restore pair * on the running task. Attribute changes like renice cycle the task through @@ -1424,7 +1519,7 @@ void scx_task_slice_ended(struct rq *rq, struct task_struct *p) { lockdep_assert_rq_held(rq); - p->scx.flags &= ~SCX_TASK_PROTECTED; + p->scx.flags &= ~(SCX_TASK_PROTECTED | SCX_TASK_KERNEL_SLICE); if (unlikely(p == scx_rescuee(rq))) scx_rescue_end(rq); } @@ -1450,9 +1545,9 @@ static void set_task_slice_oob(struct scx_sched *sch, struct task_struct *p, u64 /* * Apply a pending out-of-band slice request under @rq's lock. A request whose * packed id no longer matches @p's current owner is dropped. An extension needs - * baseline cpu access on @p's cid, shortening is always allowed, and a - * protected slice refuses both. %SCX_EV_SLICE_DENIED counts the denials. See - * the write rules above. + * baseline cpu access on @p's cid and is refused on a kernel slice. Shortening + * is always allowed. A protected slice refuses both. %SCX_EV_SLICE_DENIED + * counts the denials. See the write rules above. */ static void apply_task_slice_oob(struct rq *rq, struct task_struct *p) { @@ -1476,7 +1571,8 @@ static void apply_task_slice_oob(struct rq *rq, struct task_struct *p) slice = dur == SCX_SLICE_OOB_DUR_MASK ? SCX_SLICE_INF : dur; if (slice > p->scx.slice && - unlikely(scx_missing_caps(scx_task_sched(p), cpu_of(rq), SCX_CAP_BASE))) { + unlikely(scx_task_has_kernel_slice(p) || + scx_missing_caps(scx_task_sched(p), cpu_of(rq), SCX_CAP_BASE))) { __scx_add_event(scx_task_sched(p), SCX_EV_SLICE_DENIED, 1); return; } @@ -1508,6 +1604,35 @@ static void apply_slice_vtime(struct task_struct *p, u64 slice, u64 vtime, u64 e p->scx.dsq_vtime = vtime; } +/* + * refill_task_slice_dfl() supplies a slice when the scheduler left none and + * expire_task_slice() takes it away to force the task off the cpu. Neither + * touches a kernel slice, see %SCX_TASK_KERNEL_SLICE. + */ +static void refill_task_slice_dfl(struct scx_sched *sch, struct task_struct *p) +{ + if (scx_task_has_kernel_slice(p)) + return; + + /* + * A default refill is not an explicit request, so it must not drop a + * pending out-of-band one, which is applied when @p next runs. + */ + set_task_slice_keep_oob(p, READ_ONCE(sch->slice_dfl)); + __scx_add_event(sch, SCX_EV_REFILL_SLICE_DFL, 1); +} + +static void expire_task_slice(struct task_struct *p) +{ + /* + * Unlike the refill above, an expiry supersedes a pending out-of-band + * request. A kept request would be applied at the next + * update_curr_scx() and undo the expiry. + */ + if (!scx_task_has_kernel_slice(p)) + scx_set_task_slice(p, 0); +} + static void update_curr_scx(struct rq *rq) { struct task_struct *donor; @@ -1601,16 +1726,6 @@ static void dsq_dec_nr(struct scx_dispatch_q *dsq, struct task_struct *p) } } -static void refill_task_slice_dfl(struct scx_sched *sch, struct task_struct *p) -{ - /* - * A default refill is not an explicit request, so it must not drop a - * pending out-of-band one, which is applied when @p next runs. - */ - set_task_slice_keep_oob(p, READ_ONCE(sch->slice_dfl)); - __scx_add_event(sch, SCX_EV_REFILL_SLICE_DFL, 1); -} - /* * Return true if @p is moving due to an internal SCX migration, false * otherwise. @@ -1892,6 +2007,7 @@ void scx_task_unlink_from_dsq(struct task_struct *p, struct scx_dispatch_q *dsq) RB_CLEAR_NODE(&p->scx.dsq_priq); p->scx.dsq_flags &= ~SCX_TASK_DSQ_ON_PRIQ; } + p->scx.dsq_flags &= ~SCX_TASK_DSQ_REENQ; list_del_init(&p->scx.dsq_list.node); dsq_dec_nr(dsq, p); @@ -2117,11 +2233,11 @@ static void direct_dispatch(struct scx_sched *sch, struct task_struct *p, bool scx_rq_online(struct rq *rq) { /* - * Test both cpu_active() and %SCX_RQ_ONLINE. %SCX_RQ_ONLINE indicates - * the online state as seen from the BPF scheduler. cpu_active() test - * guarantees that, if this function returns %true, %SCX_RQ_ONLINE will - * stay set until the current scheduling operation is complete even if - * we aren't locking @rq. + * Test both cpu_active() and %SCX_RQ_ONLINE. %SCX_RQ_ONLINE follows the + * core's rq online state. cpu_active() test guarantees that, if this + * function returns %true, %SCX_RQ_ONLINE will stay set until the + * current scheduling operation is complete even if we aren't locking + * @rq. */ return likely((rq->scx.flags & SCX_RQ_ONLINE) && cpu_active(cpu_of(rq))); } @@ -2155,10 +2271,30 @@ void scx_do_enqueue_task(struct rq *rq, struct task_struct *p, u64 enq_flags, p->scx.flags &= ~SCX_TASK_IMMED; /* + * If !scx_rq_online(), we already told the BPF scheduler that the CPU + * is offline and are just running the hotplug path. Don't bother the + * BPF scheduler. + */ + if (!scx_rq_online(rq)) + goto local; + + if (scx_bypassing(sch, cpu_of(rq))) { + __scx_add_event(sch, SCX_EV_BYPASS_DISPATCH, 1); + goto bypass; + } + + /* * A task reenqueued too many times without running means the scheduler * keeps re-deciding a placement it can't honor, e.g. re-inserting to a * cid it lacks caps on. Eject the owning scheduler and strand the task * to be picked up during sched exit. + * + * Bypass guarantees that every runnable task keeps running, and the + * disable relies on that to take sleeping locks. The kernel places the + * tasks of a bypassing scheduler and those on an offline rq, and + * counting their reenqueues could strand a task under bypass and + * deadlock the disable on a lock the task holds, so both tests stay + * above the count. */ if (enq_flags & SCX_ENQ_REENQ) { if (++p->scx.reenq_cnt > 1) @@ -2172,19 +2308,6 @@ void scx_do_enqueue_task(struct rq *rq, struct task_struct *p, u64 enq_flags, } } - /* - * If !scx_rq_online(), we already told the BPF scheduler that the CPU - * is offline and are just running the hotplug path. Don't bother the - * BPF scheduler. - */ - if (!scx_rq_online(rq)) - goto local; - - if (scx_bypassing(sch, cpu_of(rq))) { - __scx_add_event(sch, SCX_EV_BYPASS_DISPATCH, 1); - goto bypass; - } - if (p->scx.ddsp_dsq_id != SCX_DSQ_INVALID) goto direct; @@ -2263,7 +2386,7 @@ global: dsq = find_global_dsq(sch, task_cpu(p)); goto enqueue; bypass: - dsq = bypass_enq_target_dsq(sch, task_cpu(p)); + dsq = bypass_enq_target_dsq(sch, rq, p, &enq_flags); goto enqueue; enqueue: @@ -2393,7 +2516,13 @@ static void ops_dequeue(struct rq *rq, struct task_struct *p, u64 deq_flags) struct scx_sched *sch = scx_task_sched(p); unsigned long opss; - /* dequeue is always temporary, don't reset runnable_at */ + /* + * Don't reset runnable_at. If @p is waiting, the wait continues across + * temporary dequeues, e.g. for a migration or an attribute change. + * scx_reset_task_fields() ends it if @p leaves its sched's control. + * scx_bypass() restarts it when its requeue can change the sched + * running @p. + */ clr_task_runnable(p, false); retry: @@ -2596,11 +2725,14 @@ static void wakeup_preempt_scx(struct rq *rq, struct task_struct *p, int wake_fl void scx_move_local_task_to_local_dsq(struct scx_sched *sch, struct task_struct *p, u64 enq_flags, struct rq *dst_rq) { - struct scx_dispatch_q *dst_dsq = scx_resolve_local_dsq(sch, dst_rq, p, &enq_flags); + struct scx_dispatch_q *dst_dsq; lockdep_assert_rq_held(dst_rq); WARN_ON_ONCE(p->scx.holding_cpu >= 0); + scx_wait_dispatching(p); + + dst_dsq = scx_resolve_local_dsq(sch, dst_rq, p, &enq_flags); if (enq_flags & (SCX_ENQ_HEAD | SCX_ENQ_PREEMPT | SCX_ENQ_PREEMPT_LAZY)) dsq_insert_head(dst_dsq, p); @@ -2795,7 +2927,6 @@ static void scx_proxy_reject_task(struct scx_sched *sch, struct rq *rq, lockdep_assert_rq_held(rq); WARN_ON_ONCE(p->scx.flags & SCX_TASK_REENQ_REASON_MASK); - p->scx.holding_cpu = -1; p->scx.flags |= SCX_TASK_REENQ_PROXY; scx_divert_strip_flags(p, &enq_flags); @@ -2829,8 +2960,9 @@ static void scx_proxy_reject_task(struct scx_sched *sch, struct rq *rq, * tell whether we lost to dequeue by testing whether the holding_cpu still * points to this CPU. See scx_dispatch_dequeue() for the counterpart. * - * On return, @dsq is unlocked and @src_rq is locked. Returns %true if @p is - * still valid and detached from @dsq. %false if lost to dequeue. + * On return, @dsq is unlocked and @src_rq is locked. Return %true if @p is + * still valid and detached from @dsq, with holding_cpu cleared. Return %false + * if @p was lost to a dequeue. */ static bool unlink_dsq_and_switch_rq_lock(struct task_struct *p, struct scx_dispatch_q *dsq, @@ -2853,11 +2985,14 @@ static bool unlink_dsq_and_switch_rq_lock(struct task_struct *p, if (likely(p->scx.holding_cpu == cpu) && !WARN_ON_ONCE(src_rq != task_rq(p))) { /* * Keep ->dsq set until we own @src_rq so that a racing dequeue - * can find @dsq and clear holding_cpu. Once ownership is - * confirmed, clear it under @src_rq so that deactivate_task() - * takes the !dsq path instead of retaking @dsq->lock. + * can find @dsq and clear holding_cpu. Once we own @src_rq, the + * handshake is over. Clear ->dsq so that deactivate_task() + * takes the !dsq path instead of retaking @dsq->lock. Clear + * holding_cpu with it so that no caller has to. */ p->scx.dsq = NULL; + p->scx.holding_cpu = -1; + scx_wait_dispatching(p); return true; } @@ -2917,6 +3052,8 @@ static struct rq *move_task_between_dsqs(struct scx_sched *sch, lockdep_assert_held(&src_dsq->lock); lockdep_assert_rq_held(src_rq); + scx_wait_dispatching(p); + if (dst_dsq->id == SCX_DSQ_LOCAL) { dst_rq = container_of(dst_dsq, struct rq, scx.local_dsq); /* @@ -3090,20 +3227,21 @@ static void dispatch_to_local_dsq(struct scx_sched *sch, struct rq *rq, !WARN_ON_ONCE(src_rq != task_rq(p))) { bool fallback = false; + /* the handshake is over, see unlink_dsq_and_switch_rq_lock() */ + p->scx.holding_cpu = -1; + /* * If @p is staying on the same rq, there's no need to go * through the full deactivate/activate cycle. Optimize by * abbreviating move_remote_task_to_local_dsq(). */ if (src_rq == dst_rq) { - p->scx.holding_cpu = -1; scx_dispatch_enqueue(sch, dst_rq, &dst_rq->scx.local_dsq, p, slice, vtime, enq_flags | SCX_ENQ_APPLY_SLICE); } else if (unlikely(task_proxy_unsafe_to_move(p))) { fallback = true; scx_proxy_reject_task(sch, src_rq, p, enq_flags); } else if (unlikely(!task_can_run_on_remote_rq(sch, p, dst_rq, true))) { - p->scx.holding_cpu = -1; fallback = true; scx_dispatch_enqueue(sch, src_rq, find_global_dsq(sch, task_cpu(p)), p, slice, vtime, @@ -3273,17 +3411,32 @@ static enum scx_dsp_verdict dispatch_one(struct rq *rq, struct task_struct *prev update_curr_scx(rq); /* + * Under bypass, @prev's slice can't be trusted as a cpu-form + * scheduler can write it directly from BPF. Skipping the keep + * below is not enough as the post-dispatch test in + * scx_dispatch_sched() would keep @prev on the same slice. + * + * Expire it as the bypass tick would, so that neither test + * keeps @prev on it and @prev rotates through the bypass + * enqueue. A kernel slice is left alone and the keep below + * keeps @prev on it, see %SCX_TASK_KERNEL_SLICE. + * + * TODO: Once the cpu form is deprecated and the kfuncs refuse + * slice raises from a bypassing scheduler, slices can be + * trusted under bypass. This expiry, the bypass tick's zeroing + * and the related slice handling can then be cleaned up. + */ + if (scx_bypassing(scx_task_sched(prev), cpu)) + expire_task_slice(prev); + + /* * If @prev is runnable & has slice left, it has priority and * fetching more just increases latency for the fetched tasks. * Tell pick_task_scx() to keep running @prev. If the BPF * scheduler wants to handle this explicitly, it should * implement ->cpu_release(). - * - * See scx_disable_workfn() for the explanation on the bypassing - * test. */ - if ((prev->scx.flags & SCX_TASK_QUEUED) && prev->scx.slice && - !scx_bypassing(scx_task_sched(prev), cpu)) { + if ((prev->scx.flags & SCX_TASK_QUEUED) && prev->scx.slice) { verdict = SCX_DSP_PREV; goto has_tasks; } @@ -3314,6 +3467,34 @@ static enum scx_dsp_verdict dispatch_one(struct rq *rq, struct task_struct *prev verdict = SCX_DSP_PREV; goto has_tasks; } + + /* + * The scheduler preempts a rescuee like any other task by + * zeroing its slice. The grant survives the preemption. The + * rescuee gets the unserved remainder back and runs again + * behind whatever the scheduler wanted to run first. + * + * Two sites restore the remainder. When another task won the + * pick, put_prev_task_scx() restores it and queues the rescuee + * at the tail of the local DSQ. + * + * When nothing else is runnable, the cpu must not go idle with + * the rescuee queued. The keep above takes a rescuee whose + * scheduler holds %SCX_CAP_BASE here and doesn't take the last + * task through %SCX_OPS_ENQ_LAST. + * + * The pick then ends its zeroed slice, and the rescue with it, + * and refills a default slice. The task continues as an + * ordinary one, which is fine as its scheduler holds BASE here. + * + * For any other rescuee, a reinsert from put_prev_task_scx() + * would come after the pick settled on idle. Keep it running on + * the remainder here. + */ + if (unlikely(prev == scx_rescuee(rq)) && scx_rescue_keep(rq, prev)) { + verdict = SCX_DSP_PREV; + goto has_tasks; + } } rq->scx.flags &= ~SCX_RQ_IN_DISPATCH; return SCX_DSP_NONE; @@ -3328,8 +3509,12 @@ has_tasks: * * - A non-IMMED HEAD task can get queued in front of an IMMED task * between the IMMED queueing and the subsequent scheduling event. + * + * - When dispatch keeps @prev, even a lone IMMED task queued during the + * dispatch can't run right away. */ - if (unlikely(rq->scx.local_dsq.nr > 1 && rq->scx.nr_immed)) + if (unlikely((rq->scx.local_dsq.nr > 1 || verdict == SCX_DSP_PREV) && + rq->scx.nr_immed)) scx_schedule_reenq_local(rq, 0); rq->scx.flags &= ~SCX_RQ_IN_DISPATCH; @@ -3351,11 +3536,37 @@ static void scx_start_task_running(struct rq *rq, struct task_struct *p) p->scx.flags |= SCX_TASK_RUN_TRACKED; } +static void kick_sync_wait_bal_cb(struct rq *rq); + static void set_next_task_scx(struct rq *rq, struct task_struct *p, enum snt_e type) { bool first = type == SNT_PICK; bool can_stop_tick; + /* + * A blocked pick is provisional until proxy resolution completes, see + * put_prev_task_scx(). A retry can repick the same donor, so + * SNT_REPICK must set it again. + */ + rq->scx.flags &= ~SCX_RQ_PROXY_PENDING; + if (sched_proxy_exec() && p->is_blocked && + (type == SNT_PICK || type == SNT_REPICK)) + rq->scx.flags |= SCX_RQ_PROXY_PENDING; + + /* + * Defer the kick_sync wait to a balance callback which can drop rq lock + * and enable IRQs. Waiting directly in the pick path would deadlock + * against CPUs sending us IPIs (e.g., TLB flushes) while we wait for + * them. + * + * Queue it only once the pick is final, so that the rq lock can't be + * released with the callback queued (e.g., by another dispatch during + * a core-wide selection). If no SCX task gets picked, there's nothing + * to wait for and kick_sync_pending stays set for the next SCX pick. + */ + if (unlikely(rq->scx.kick_sync_pending) && (type == SNT_PICK || type == SNT_REPICK)) + queue_balance_callback(rq, &rq->scx.kick_sync_bal_cb, kick_sync_wait_bal_cb); + if (type == SNT_REPICK) return; @@ -3435,6 +3646,7 @@ void scx_proxy_donor_start(struct rq *rq) struct task_struct *donor = rq->donor; lockdep_assert_rq_held(rq); + rq->scx.flags &= ~SCX_RQ_PROXY_PENDING; if (donor->sched_class == &ext_sched_class && (donor->scx.flags & SCX_TASK_QUEUED)) scx_start_task_running(rq, donor); @@ -3495,7 +3707,14 @@ static void put_prev_task_scx(struct rq *rq, struct task_struct *p, struct task_struct *next) { struct scx_sched *sch = scx_task_sched(p); + bool proxy_put = p->is_blocked && next == rq->idle && + (rq->scx.flags & SCX_RQ_PROXY_PENDING); + bool proxy_block = rq->scx.flags & SCX_RQ_PROXY_BLOCKING; bool rescue_keep = false; + bool going_idle = !proxy_put && next && + sched_class_above(&ext_sched_class, next->sched_class); + + rq->scx.flags &= ~SCX_RQ_PROXY_PENDING; /* see kick_sync_wait_bal_cb() */ smp_store_release(&rq->scx.kick_sync, rq->scx.kick_sync + 1); @@ -3503,48 +3722,46 @@ static void put_prev_task_scx(struct rq *rq, struct task_struct *p, update_curr_scx(rq); /* - * If the slice is consumed, protection ends with it. A rescuee - * preempted beforehand keeps going, see scx_rescue_keep(). - */ - if (!p->scx.slice) { - if (unlikely(p == scx_rescuee(rq))) - rescue_keep = scx_rescue_keep(rq, p); - if (!rescue_keep) - scx_task_slice_ended(rq, p); - } - - /* * Preserve the running session when proxy execution refreshes the same * donor around an execution-context switch on this rq. */ if (next != p && (p->scx.flags & SCX_TASK_QUEUED) && (p->scx.flags & SCX_TASK_RUN_TRACKED)) { if (SCX_HAS_OP(sch, stopping)) - SCX_CALL_OP_TASK(sch, stopping, rq, p, true); + SCX_CALL_OP_TASK(sch, stopping, rq, p, !proxy_block); p->scx.flags &= ~SCX_TASK_RUN_TRACKED; } + /* + * If the slice is consumed, protection ends with it. + * + * A rescuee keeps going when a preemption or ops.stopping() zeroed its + * slice. Here another task won the pick. scx_rescue_keep() restores the + * unserved remainder and the reinsert below queues the rescuee at the + * tail of the local DSQ. When nothing else is runnable, dispatch_one() + * keeps the rescuee running on the remainder instead. + */ + if (!p->scx.slice) { + if (unlikely(p == scx_rescuee(rq))) + rescue_keep = scx_rescue_keep(rq, p); + if (!rescue_keep) + scx_task_slice_ended(rq, p); + } + if (p->scx.flags & SCX_TASK_QUEUED) { - set_task_runnable(rq, p); + if (proxy_block) + goto switch_class; - /* Delegate retained donor admission to its owning BPF scheduler. */ - if (p->is_blocked) { - /* - * If the donor is the same and only the mutex owner - * changes, avoid triggering another ops.enqueue(): the - * BPF scheduler has already admitted the donor, so it - * can continue running. - */ - if (next == p) - goto switch_class; + set_task_runnable(rq, p); - if (WARN_ON_ONCE(!sch)) - goto switch_class; - WARN_ON_ONCE(!(sch->ops.flags & SCX_OPS_ENQ_BLOCKED)); - scx_do_enqueue_task(rq, p, 0, -1); + /* + * If the donor is the same and only the mutex owner changes, + * avoid triggering another ops.enqueue(): the BPF scheduler has + * already admitted the donor, so it can continue running. + */ + if (p->is_blocked && next == p) goto switch_class; - } /* * If @p has slice left and is being put, @p is getting @@ -3553,28 +3770,40 @@ static void put_prev_task_scx(struct rq *rq, struct task_struct *p, * DSQ unless it was an IMMED task. IMMED tasks should not * linger on a busy CPU, reenqueue them to the BPF scheduler. * - * An open rescue must keep @p on the local DSQ even if the - * scheduler zeroed the slice in ops.stopping() above. + * The exception is an IMMED donor put by proxy_resched_idle(): + * the CPU isn't busy, proxy resolution is only retrying through + * idle, so keep the donor where it can be picked again. + * + * A task with a kernel slice stays on the local DSQ even while + * @sch bypasses. Under bypass, rescue runs @p when the host + * lacks %SCX_CAP_BASE, see bypass_enq_target_dsq(). */ - if ((p->scx.slice || unlikely(p == scx_rescuee(rq))) && - !scx_bypassing(sch, cpu_of(rq))) { - if (p->scx.flags & SCX_TASK_IMMED) { + if (p->scx.slice && (!scx_bypassing(sch, cpu_of(rq)) || + scx_task_has_kernel_slice(p))) { + if ((p->scx.flags & SCX_TASK_IMMED) && !proxy_put) { p->scx.flags |= SCX_TASK_REENQ_PREEMPTED; scx_do_enqueue_task(rq, p, SCX_ENQ_REENQ, -1); } else { u64 enq_flags = 0; /* - * Keep a preempted rescue going. If preempted - * by another SCX task, append to the local DSQ, - * see scx_rescue_keep(). + * The enqueue caps gate the scheduler's + * placement. The kernel placed a kernel-slice + * task here itself, so reinsert it without a + * cap check, at the head like any preempted + * task. When scx_rescue_keep() restored a slice + * the scheduler zeroed, the scheduler wanted + * something else to run first, so append. */ - if (unlikely(p == scx_rescuee(rq))) { + if (unlikely(scx_task_has_kernel_slice(p))) { enq_flags |= SCX_ENQ_IGNORE_CAPS; if (!rescue_keep) enq_flags |= SCX_ENQ_HEAD; } else { enq_flags |= SCX_ENQ_HEAD; + /* only require SCX_CAP_ENQ_IMMED, see scx_caps_for_enq() */ + if (proxy_put && (p->scx.flags & SCX_TASK_IMMED)) + enq_flags |= SCX_ENQ_IMMED; } scx_dispatch_enqueue(sch, rq, &rq->scx.local_dsq, p, 0, 0, @@ -3587,30 +3816,35 @@ static void put_prev_task_scx(struct rq *rq, struct task_struct *p, * If @p is runnable but we're about to enter a lower * sched_class, %SCX_OPS_ENQ_LAST must be set. Tell * ops.enqueue() that @p is the only one available for this cpu. - * This doesn't apply if the baseline access on the CPU is lost. + * This doesn't apply if the baseline access on the CPU is lost or + * proxy resolution temporarily switches to idle. * * Under core scheduling, a pick dispatches only when nothing is * locally runnable and can legitimately go idle with @p still * runnable (see do_pick_task_scx()). */ - if (next && sched_class_above(&ext_sched_class, next->sched_class) && - scx_task_can_stay_on_cpu(rq, p)) { + if (going_idle && scx_task_can_stay_on_cpu(rq, p)) { WARN_ON_ONCE(!sched_core_enabled(rq) && !(sch->ops.flags & SCX_OPS_ENQ_LAST)); scx_do_enqueue_task(rq, p, SCX_ENQ_LAST, -1); - - /* - * A task put on the local DSQ runs, as anywhere else. - * Here the insert can't reschedule on its own: the pick - * has settled on @next and @p is still curr, so - * resched_curr() would flag @p and __schedule() clears - * that right after the pick. Flag @next instead. - */ - if (p->scx.dsq == &rq->scx.local_dsq) - set_tsk_need_resched(next); } else { scx_do_enqueue_task(rq, p, 0, -1); } + + /* + * @p may be on the local DSQ now. With %SCX_ENQ_LAST the + * scheduler can put the last runnable task there. The plain + * insert runs when @p cannot stay on this cpu, and rescue can + * still admit it here. + * + * The cpu must not go idle with @p queued on its local DSQ. The + * usual resched doesn't work: the pick has settled on @next and + * @p is still curr, so resched_curr() would set need_resched on + * @p, which __schedule() clears right after the pick. Set it on + * @next instead. + */ + if (going_idle && p->scx.dsq == &rq->scx.local_dsq) + set_tsk_need_resched(next); } switch_class: @@ -3628,16 +3862,12 @@ static void kick_sync_wait_bal_cb(struct rq *rq) s32 cpu; /* - * This callback is queued and normally flushed within @rq's own - * scheduling pass. However, dispatch can drop the rq lock while it sits - * queued, and lock takers in that window (the sched class change paths, - * the scx task iterator) flush pending balance callbacks on release, - * running this one on a foreign CPU whose snapshots are unrelated. The - * kicked CPUs are already on their way to advance the kick_syncs being - * waited on. Don't get in the way. + * Clear only when the wait actually runs. The callback can be dropped + * without running (e.g., proxy exec zaps the balance callbacks and + * picks again when find_proxy_task() fails), in which case the next + * pick must queue it again. */ - if (unlikely(cpu_of(rq) != smp_processor_id())) - return; + rq->scx.kick_sync_pending = false; ks = __this_cpu_read(scx_kick_syncs); ksyncs = rcu_dereference_sched(ks)->syncs; @@ -3685,7 +3915,8 @@ static struct task_struct *first_local_task(struct rq *rq) } /* - * Run dispatch and queue the follow-up work for a pick. + * Run dispatch for a pick. The follow-up work is queued by do_pick_task_scx() + * once the pick is final. */ static enum scx_dsp_verdict dispatch_pick(struct rq *rq, struct rq_flags *rf, struct task_struct *prev) @@ -3695,18 +3926,6 @@ static enum scx_dsp_verdict dispatch_pick(struct rq *rq, struct rq_flags *rf, rq_unpin_lock(rq, rf); verdict = dispatch_one(rq, prev); rq_repin_lock(rq, rf); - maybe_queue_balance_callback(rq); - - /* - * Defer to a balance callback which can drop rq lock and enable IRQs. - * Waiting directly in the pick path would deadlock against CPUs sending - * us IPIs (e.g. TLB flushes) while we wait for them. - */ - if (unlikely(rq->scx.kick_sync_pending)) { - rq->scx.kick_sync_pending = false; - queue_balance_callback(rq, &rq->scx.kick_sync_bal_cb, - kick_sync_wait_bal_cb); - } return verdict; } @@ -3733,23 +3952,20 @@ static enum scx_dsp_verdict dispatch_core_pick(struct rq *rq, struct rq_flags *r verdict = dispatch_one(rq, prev); - if (cpu_of(rq) == smp_processor_id()) { - maybe_queue_balance_callback(rq); - - /* see dispatch_pick() */ - if (unlikely(rq->scx.kick_sync_pending)) { - rq->scx.kick_sync_pending = false; - queue_balance_callback(rq, &rq->scx.kick_sync_bal_cb, - kick_sync_wait_bal_cb); - } - } else if (unlikely(rq->scx.flags & SCX_RQ_BAL_CB_PENDING)) { - /* - * Balance callbacks must run in the context that queued them, - * so they can't be queued on another CPU's rq. Run the deferred - * work directly instead. - */ + /* + * A pick that returns a task isn't final under core scheduling: the + * selection goes on to pick the siblings, and their dispatch can + * release the rq lock, which can't happen with balance callbacks + * queued. Don't queue the deferred work as a balance callback, for this + * CPU or a sibling, and run it from irq_work instead. + * + * do_pick_task_scx() leaves %SCX_RQ_BAL_CB_PENDING alone under core + * scheduling, so that the early return above leaves it to the dispatch + * in flight, which handles it here. + */ + if (unlikely(rq->scx.flags & SCX_RQ_BAL_CB_PENDING)) { rq->scx.flags &= ~SCX_RQ_BAL_CB_PENDING; - run_deferred(rq); + schedule_deferred(rq); } rq_repin_lock(rq, rf); @@ -3772,21 +3988,32 @@ static struct task_struct * do_pick_task_scx(struct rq *rq, struct rq_flags *rf, bool force_scx) { struct task_struct *prev = rq->donor; + bool core_sched = sched_core_enabled(rq); enum scx_dsp_verdict verdict; struct task_struct *p; + /* A retry can abandon a provisional blocked-donor pick. */ + rq->scx.flags &= ~SCX_RQ_PROXY_PENDING; + /* see kick_sync_wait_bal_cb() */ smp_store_release(&rq->scx.kick_sync, rq->scx.kick_sync + 1); rq_modified_begin(rq, &ext_sched_class); - if (sched_core_enabled(rq)) + /* + * Core scheduling can get enabled while dispatch_pick() has the rq lock + * released. Stick to @core_sched, so that the follow-up work below + * matches the dispatch that ran. + */ + if (core_sched) verdict = dispatch_core_pick(rq, rf, prev); else verdict = dispatch_pick(rq, rf, prev); - if (verdict == SCX_DSP_RETRY) - return RETRY_TASK; + if (verdict == SCX_DSP_RETRY) { + p = RETRY_TASK; + goto out; + } /* * If any higher-priority sched class enqueued a runnable task on this @@ -3796,8 +4023,10 @@ do_pick_task_scx(struct rq *rq, struct rq_flags *rf, bool force_scx) * If @force_scx is true, always try to pick a SCHED_EXT task, * regardless of any higher-priority sched classes activity. */ - if (!force_scx && rq_modified_above(rq, &ext_sched_class)) - return RETRY_TASK; + if (!force_scx && rq_modified_above(rq, &ext_sched_class)) { + p = RETRY_TASK; + goto out; + } /* * If we're keeping @prev, replenish slice if necessary and keep running @@ -3813,7 +4042,7 @@ do_pick_task_scx(struct rq *rq, struct rq_flags *rf, bool force_scx) } else { p = first_local_task(rq); if (!p) - return NULL; + goto out; if (unlikely(!p->scx.slice) && scx_task_can_stay_on_cpu(rq, p)) { struct scx_sched *sch = scx_task_sched(p); @@ -3828,6 +4057,27 @@ do_pick_task_scx(struct rq *rq, struct rq_flags *rf, bool force_scx) } } +out: + if (cpu_of(rq) != smp_processor_id()) + return p; + + /* + * Balance callbacks must be consumed before the rq lock is released, so + * queue them only when the pick is final. On RETRY_TASK, or after a + * NULL pick from the dl_server, the core continues picking and can + * release the rq lock (e.g., prev_balance() or another dispatch). In + * that case, run the deferred work from irq_work, which doesn't depend + * on the current rq lock section. + */ + if (p != RETRY_TASK && (p || !force_scx)) { + /* under core scheduling, see dispatch_core_pick() */ + if (!core_sched) + maybe_queue_balance_callback(rq); + } else if (!core_sched && (rq->scx.flags & SCX_RQ_BAL_CB_PENDING)) { + rq->scx.flags &= ~SCX_RQ_BAL_CB_PENDING; + schedule_deferred(rq); + } + return p; } @@ -4052,6 +4302,7 @@ static void handle_hotplug(struct rq *rq, bool online) s32 cpu_or_cid = cpu; atomic_long_inc(&scx_hotplug_seq); + scx_update_frozen_cpus(cpu, online); /* * scx_root updates are protected by cpus_read_lock() and will stay @@ -4064,11 +4315,6 @@ static void handle_hotplug(struct rq *rq, bool online) if (scx_enabled()) scx_idle_update_selcpu_topology(&sch->ops); - if (online) - scx_online_ecaps(rq); - else - scx_offline_ecaps(rq); - /* * The tables can't be retired while this function is running as the * retirement is inside cpus_read_lock. However, scx_cpu_arg() is @@ -4097,6 +4343,14 @@ static void handle_hotplug(struct rq *rq, bool online) } } + /* + * ecaps are delivered for @cpu only after ops.cpu_online() and before + * ops.cpu_offline(). The ecaps ops may read online_cmask, so + * scx_offline_ecaps() and scx_online_ecaps() run after its update. + */ + if (!online) + scx_offline_ecaps(rq); + if (online && SCX_HAS_OP(sch, cpu_online)) SCX_CALL_OP(sch, cpu_online, NULL, cpu_or_cid); else if (!online && SCX_HAS_OP(sch, cpu_offline)) @@ -4106,6 +4360,9 @@ static void handle_hotplug(struct rq *rq, bool online) SCX_ECODE_ACT_RESTART | SCX_ECODE_RSN_HOTPLUG, "cpu %d going %s, exiting scheduler", cpu, online ? "online" : "offline"); + + if (online) + scx_online_ecaps(rq); } void scx_rq_activate(struct rq *rq) @@ -4160,24 +4417,17 @@ static bool check_rq_for_timeouts(struct rq *rq) goto out_unlock; list_for_each_entry(p, &rq->scx.runnable_list, scx.runnable_node) { - struct scx_sched *sch = scx_task_sched(p); + /* + * @p's owner schedules @p, or its host while the owner is + * bypassing. Test @p against that sched's timeout and blame it. + */ + struct scx_sched *sch = scx_exec_sched(scx_task_sched(p), cpu_of(rq)); unsigned long last_runnable = p->scx.runnable_at; if (unlikely(time_after(jiffies, last_runnable + READ_ONCE(sch->watchdog_timeout)))) { - struct scx_dispatch_q *dsq = READ_ONCE(p->scx.dsq); u32 dur_ms = jiffies_to_msecs(jiffies - last_runnable); - /* - * A task can be stuck on a DSQ that a sched other than - * its owner is responsible for draining, e.g. an - * ancestor's bypass DSQ while the owner is bypassing. - * Blame the drainer. The local DSQ is consumed by the - * cpu itself and keeps blame on the owner. - */ - if (dsq && dsq->sched && dsq->id != SCX_DSQ_LOCAL) - sch = dsq->sched; - __scx_exit(sch, SCX_EXIT_ERROR_STALL, 0, cpu_of(rq), "%s[%d] failed to run for %u.%03us", p->comm, p->pid, dur_ms / 1000, @@ -4246,7 +4496,7 @@ static void task_tick_scx(struct rq *rq, struct task_struct *donor, int queued) * management. */ if (scx_bypassing(sch, cpu_of(rq))) - scx_set_task_slice(donor, 0); + expire_task_slice(donor); else if (SCX_HAS_OP(sch, tick)) SCX_CALL_OP_TASK(sch, tick, rq, donor); @@ -4407,6 +4657,34 @@ void scx_enable_task(struct scx_sched *sch, struct task_struct *p) scx_set_task_state(p, SCX_TASK_ENABLED); } +/** + * scx_reset_task_fields - Reset what @p carries from its sched's control + * @rq: @p's rq, locked + * @p: task leaving its sched's control + * + * The vtime, the slice and what rides on it, the reenqueue count and the + * watchdog wait belong to the sched while it controls @p. The control ends when + * @p is taken off the sched or leaves the ext class while staying on the sched. + * Reset them so that @p starts clean wherever it goes. + */ +static void scx_reset_task_fields(struct rq *rq, struct task_struct *p) +{ + lockdep_assert_rq_held(rq); + + p->scx.dsq_vtime = 0; + scx_task_slice_ended(rq, p); + scx_set_task_slice(p, 0); + p->scx.reenq_cnt = 0; + + /* + * If @p is runnable but not running, its wait started at runnable_at, + * which ops_dequeue() didn't reset. Leaving the sched's control ends + * the wait. Reset runnable_at the next time @p is enqueued on SCX, so + * that the watchdog doesn't count the time @p spends elsewhere. + */ + p->scx.flags |= SCX_TASK_RESET_RUNNABLE_AT; +} + static void scx_disable_task(struct scx_sched *sch, struct task_struct *p) { struct rq *rq = task_rq(p); @@ -4421,15 +4699,6 @@ static void scx_disable_task(struct scx_sched *sch, struct task_struct *p) scx_set_task_state(p, SCX_TASK_READY); /* - * Reset the SCX-managed fields when @p leaves the BPF scheduler's - * control, after ops.disable() has observed their final values. - */ - p->scx.dsq_vtime = 0; - scx_task_slice_ended(rq, p); - scx_set_task_slice(p, 0); - p->scx.reenq_cnt = 0; - - /* * Verify the task is not in BPF scheduler's custody. If flag * transitions are consistent, the flag should always be clear * here. @@ -4448,6 +4717,11 @@ void __scx_disable_and_exit_task(struct scx_sched *sch, struct task_struct *p) switch (scx_get_task_state(p)) { case SCX_TASK_NONE: + /* + * No op to call, but @p may still carry @sch's state, e.g. a + * task punted by scx_fail_parent() and being rescued. + */ + scx_reset_task_fields(task_rq(p), p); return; case SCX_TASK_INIT: args.cancelled = true; @@ -4456,6 +4730,8 @@ void __scx_disable_and_exit_task(struct scx_sched *sch, struct task_struct *p) break; case SCX_TASK_ENABLED: scx_disable_task(sch, p); + /* after ops.disable() has seen the final values */ + scx_reset_task_fields(task_rq(p), p); break; default: WARN_ON_ONCE(true); @@ -4763,11 +5039,13 @@ static void switched_from_scx(struct rq *rq, struct task_struct *p) * parent's own teardown). There is nothing to disable; calling * scx_disable_task() would WARN on the non-%ENABLED state and trigger a * NONE -> READY validation failure. + * + * Either way, reset @p after ops.disable() has seen the final values. A + * %NONE @p can still be a rescuee under the parent. */ - if (scx_get_task_state(p) == SCX_TASK_NONE) - return; - - scx_disable_task(scx_task_sched(p), p); + if (scx_get_task_state(p) != SCX_TASK_NONE) + scx_disable_task(scx_task_sched(p), p); + scx_reset_task_fields(rq, p); } static void switched_to_scx(struct rq *rq, struct task_struct *p) {} @@ -4795,7 +5073,7 @@ void scx_prepare_setscheduler(struct task_struct *p, int policy) lockdep_assert_rq_held(task_rq(p)); if (scx_enabled() && p->policy != policy && policy == SCHED_EXT) - sched_proxy_block_task(task_rq(p), p); + scx_block_proxy_donor(task_rq(p), p); } static void process_ddsp_deferred_locals(struct rq *rq) @@ -4850,7 +5128,8 @@ static void process_ddsp_deferred_locals(struct rq *rq) * %SCX_TASK_REENQ_IMMED. If the BPF scheduler dispatches back to the same local * DSQ with %SCX_ENQ_IMMED while the CPU is still unavailable, this triggers * another reenq cycle. Repetitions are bounded by %SCX_REENQ_MAX_REPEAT in - * scx_do_enqueue_task(), which ejects the task's owning scheduler. + * scx_do_enqueue_task(), which ejects the task's owning scheduler. A bypassing + * scheduler's tasks are placed by the kernel instead and are not counted. */ static bool local_task_should_reenq(struct rq *rq, struct task_struct *p, u64 *reenq_flags, u32 *reason) @@ -4860,7 +5139,7 @@ static bool local_task_should_reenq(struct rq *rq, struct task_struct *p, first = !(*reenq_flags & SCX_REENQ_TSR_NOT_FIRST); *reenq_flags |= SCX_REENQ_TSR_NOT_FIRST; - if (unlikely((p->scx.flags & SCX_TASK_PROTECTED) || p == scx_rescuee(rq))) + if (unlikely((p->scx.flags & SCX_TASK_PROTECTED) || scx_task_has_kernel_slice(p))) return false; *reason = SCX_TASK_REENQ_KFUNC; @@ -4882,11 +5161,12 @@ static bool local_task_should_reenq(struct rq *rq, struct task_struct *p, } /* - * The dispatcher stores the final ops_state after dropping the DSQ lock, so @p - * can be found on a DSQ while still %SCX_OPSS_DISPATCHING. Reenqueueing @p - * before that store lands would have it clobber the new %SCX_OPSS_QUEUED. + * The dispatcher runs ops.dequeue() and stores the final ops_state after + * dropping the DSQ lock, so @p can be found on a DSQ while still + * %SCX_OPSS_DISPATCHING. Wait for the dispatch to finish before operating on + * @p. */ -void scx_reenq_wait_dispatching(struct task_struct *p) +void scx_wait_dispatching(struct task_struct *p) { if (unlikely(atomic_long_read_acquire(&p->scx.ops_state) == SCX_OPSS_DISPATCHING)) wait_ops_state(p, SCX_OPSS_DISPATCHING); @@ -4935,7 +5215,7 @@ static u32 reenq_local(struct scx_sched *sch, struct rq *rq, u64 reenq_flags) if (!local_task_should_reenq(rq, p, &reenq_flags, &reason)) continue; - scx_reenq_wait_dispatching(p); + scx_wait_dispatching(p); scx_dispatch_dequeue(rq, p); WARN_ON_ONCE(p->scx.flags & SCX_TASK_REENQ_REASON_MASK); @@ -4962,7 +5242,7 @@ static u32 reenq_local(struct scx_sched *sch, struct rq *rq, u64 reenq_flags) if ((reenq_flags & SCX_REENQ_CAP_REVOKE) && rq->donor->sched_class == &ext_sched_class && scx_task_reenq_on_cap_revoke(rq, rq->donor)) { - scx_set_task_slice(rq->donor, 0); + expire_task_slice(rq->donor); resched_curr(rq); } @@ -5011,7 +5291,9 @@ static void process_deferred_reenq_locals(struct rq *rq) static bool user_task_should_reenq(struct task_struct *p, u64 reenq_flags, u32 *reason) { *reason = SCX_TASK_REENQ_KFUNC; - return reenq_flags & SCX_REENQ_ANY; + if (reenq_flags & SCX_REENQ_ANY) + return true; + return (reenq_flags & SCX_REENQ_MARKED) && (p->scx.dsq_flags & SCX_TASK_DSQ_REENQ); } static void reenq_user(struct rq *rq, struct scx_dispatch_q *dsq, u64 reenq_flags) @@ -5020,7 +5302,7 @@ static void reenq_user(struct rq *rq, struct scx_dispatch_q *dsq, u64 reenq_flag struct scx_sched *sch = dsq->sched; struct scx_dsq_list_node cursor = INIT_DSQ_LIST_CURSOR(cursor, dsq, 0); struct task_struct *p; - s32 nr_enqueued = 0; + s32 nr_visited = 0; lockdep_assert_rq_held(rq); @@ -5030,6 +5312,21 @@ static void reenq_user(struct rq *rq, struct scx_dispatch_q *dsq, u64 reenq_flag struct rq *task_rq; u32 reason; + /* + * Count skipped tasks too so that a long walk doesn't hold the + * locks throughout. The cursor keeps the position. + */ + if (!(++nr_visited % SCX_TASK_ITER_BATCH)) { + raw_spin_unlock(&dsq->lock); + if (locked_rq) { + scx_rq_lock_drop(locked_rq); + raw_spin_rq_unlock(locked_rq); + locked_rq = NULL; + } + cpu_relax(); + raw_spin_lock(&dsq->lock); + } + p = nldsq_cursor_next_task(&cursor, dsq); if (!p) break; @@ -5057,7 +5354,7 @@ static void reenq_user(struct rq *rq, struct scx_dispatch_q *dsq, u64 reenq_flag } /* @p is on @dsq, its rq and @dsq are locked */ - scx_reenq_wait_dispatching(p); + scx_wait_dispatching(p); dispatch_dequeue_locked(p, dsq); raw_spin_unlock(&dsq->lock); @@ -5066,13 +5363,6 @@ static void reenq_user(struct rq *rq, struct scx_dispatch_q *dsq, u64 reenq_flag scx_do_enqueue_task(task_rq, p, SCX_ENQ_REENQ, -1); - if (!(++nr_enqueued % SCX_TASK_ITER_BATCH)) { - scx_rq_lock_drop(locked_rq); - raw_spin_rq_unlock(locked_rq); - locked_rq = NULL; - cpu_relax(); - } - raw_spin_lock(&dsq->lock); } @@ -5134,7 +5424,8 @@ static void process_deferred_reenq_users(struct rq *rq) * * A task can be re-rejected repeatedly. Reenqueues are bounded per task by * SCX_REENQ_MAX_REPEAT in scx_do_enqueue_task(), which ejects the owning - * scheduler. + * scheduler. A bypassing scheduler's tasks are placed by the kernel instead and + * are not counted. */ static void scx_reenq_reject(struct rq *rq) { @@ -5168,7 +5459,7 @@ static void scx_reenq_reject(struct rq *rq) WARN_ON_ONCE(p->migration_pending); } - scx_reenq_wait_dispatching(p); + scx_wait_dispatching(p); scx_dispatch_dequeue(rq, p); list_add_tail(&p->scx.dsq_list.node, &tasks); @@ -5929,10 +6220,6 @@ static void scx_sched_free_rcu_work(struct work_struct *work) struct scx_dispatch_q *dsq; int cpu, node; - irq_work_sync(&sch->propagate_exit_irq_work); - irq_work_sync(&sch->disable_irq_work); - kthread_destroy_worker(sch->helper); - timer_shutdown_sync(&sch->bypass_lb_timer); free_cpumask_var(sch->bypass_lb_donee_cpumask); free_cpumask_var(sch->bypass_lb_resched_cpumask); free_cpumask_var(sch->stall_cpus); @@ -5950,22 +6237,6 @@ static void scx_sched_free_rcu_work(struct work_struct *work) for_each_possible_cpu(cpu) { struct scx_sched_pcpu *pcpu = per_cpu_ptr(sch->pcpu, cpu); - /* - * $sch would have entered bypass mode before the RCU grace - * period. As that blocks new deferrals, all - * deferred_reenq_local_node's must be off-list by now. - */ - WARN_ON_ONCE(!list_empty(&pcpu->deferred_reenq_local.node)); - - /* remove the queued ecaps sync so the pcpu can be freed */ - scx_discard_ecaps_to_sync(cpu, pcpu); - - /* - * Bypass blocks new kicks. Flush the kick irq_work so this - * pcpu's to_kick_node is off the list before it is freed. - */ - irq_work_sync(&cpu_rq(cpu)->scx.kick_cpus_irq_work); - WARN_ON_ONCE(!list_empty(&pcpu->to_kick_node)); free_cpumask_var(pcpu->cpus_to_kick); free_cpumask_var(pcpu->cpus_to_kick_if_idle); free_cpumask_var(pcpu->cpus_to_preempt); @@ -6007,11 +6278,65 @@ static void scx_sched_free_rcu_work(struct work_struct *work) kfree(sch); } +/** + * scx_sched_quiesce_rcu_work - Quiesce a sched and queue its free + * @work: &scx_sched.rcu_work + * + * $sch is freed after two RCU grace periods because of its ecaps sync nodes. + * + * The first grace period runs between scx_kobj_release() and this function. It + * waits for the paths that found $sch before scx_unlink_sched(), such as the + * sub-cap kfuncs and the cpu hotplug hooks. Until they finish, they can queue + * $sch's syncs, and a cpu can take a queued node into a sync batch. The first + * grace period doesn't wait for a batch that started after it began. + * + * Nothing queues $sch's syncs now. Remove the nodes still on the cpus' lists. A + * batch that took a node can still write $sch's pcpu, and a delivery in the + * batch can drop the rq lock before that write. The batch keeps irqs off from + * taking the node to its last pcpu write, so the second grace period waits for + * it before scx_sched_free_rcu_work() frees $sch. + */ +static void scx_sched_quiesce_rcu_work(struct work_struct *work) +{ + struct rcu_work *rcu_work = to_rcu_work(work); + struct scx_sched *sch = container_of(rcu_work, struct scx_sched, rcu_work); + s32 cpu; + + irq_work_sync(&sch->propagate_exit_irq_work); + irq_work_sync(&sch->disable_irq_work); + kthread_destroy_worker(sch->helper); + timer_shutdown_sync(&sch->bypass_lb_timer); + + for_each_possible_cpu(cpu) { + struct scx_sched_pcpu *pcpu = per_cpu_ptr(sch->pcpu, cpu); + + /* + * $sch would have entered bypass mode before the first RCU + * grace period. As that blocks new deferrals, all + * deferred_reenq_local_node's must be off-list by now. + */ + WARN_ON_ONCE(!list_empty(&pcpu->deferred_reenq_local.node)); + + /* remove the queued ecaps sync so the pcpu can be freed */ + scx_discard_ecaps_to_sync(cpu, pcpu); + + /* + * Bypass blocks new kicks. Flush the kick irq_work so this + * pcpu's to_kick_node is off the list before it is freed. + */ + irq_work_sync(&cpu_rq(cpu)->scx.kick_cpus_irq_work); + WARN_ON_ONCE(!list_empty(&pcpu->to_kick_node)); + } + + INIT_RCU_WORK(&sch->rcu_work, scx_sched_free_rcu_work); + queue_rcu_work(system_dfl_wq, &sch->rcu_work); +} + static void scx_kobj_release(struct kobject *kobj) { struct scx_sched *sch = container_of(kobj, struct scx_sched, kobj); - INIT_RCU_WORK(&sch->rcu_work, scx_sched_free_rcu_work); + INIT_RCU_WORK(&sch->rcu_work, scx_sched_quiesce_rcu_work); queue_rcu_work(system_dfl_wq, &sch->rcu_work); } @@ -6315,6 +6640,110 @@ bool scx_hardlockup(int cpu) return true; } +/** + * bypass_lb_reenq_home - Reenqueue a task at its home from the balancer + * @rq: @p's home rq, locked + * @p: task off any DSQ, taken from the bypass DSQ of @dsq_cpu + * @dsq_cpu: cpu whose bypass DSQ gave up @p + * + * @p came off the bypass DSQ of @dsq_cpu with no donee able to take it. A drain + * sends a migration-disabled @p here unless the donee picked for it is its + * home, as every other cpu refuses it. The enqueue sends @p to rescue when the + * host lacks %SCX_CAP_BASE at home and rescue is enabled, and to the home's + * bypass DSQ otherwise. When @p must run at home, migration-disabled or with a + * migration pending, and the host lacks BASE there, it is admitted to the + * home's local DSQ in either case, see bypass_enq_target_dsq(). No DSQ lock may + * be held, as the enqueue takes one. + */ +static void bypass_lb_reenq_home(struct rq *rq, struct task_struct *p, s32 dsq_cpu) +{ + lockdep_assert_rq_held(rq); + + WARN_ON_ONCE(p->scx.flags & SCX_TASK_REENQ_REASON_MASK); + p->scx.flags |= SCX_TASK_REENQ_CAP; + p->scx.reenq_reason_caps = SCX_CAP_BASE; + p->scx.reenq_reason_cid = __scx_cpu_to_cid(dsq_cpu); + scx_do_enqueue_task(rq, p, SCX_ENQ_REENQ, -1); +} + +/** + * bypass_lb_can_move - Test whether @p can move to the bypass DSQ of @donee + * @sch: host sched whose bypass DSQs are balanced + * @p: task on a bypass DSQ of @sch, homed anywhere + * @donee: cpu whose bypass DSQ would receive @p, -1 for none + * + * @p's rq lock pins @p's affinity. Without it the answer is a hint. A task + * whose donee is its own cpu can always run there, and + * task_can_run_on_remote_rq() warns when asked about a task's own cpu. + */ +static bool bypass_lb_can_move(struct scx_sched *sch, struct task_struct *p, s32 donee) +{ + return donee >= 0 && (donee == task_cpu(p) || + task_can_run_on_remote_rq(sch, p, cpu_rq(donee), false)); +} + +/** + * bypass_lb_move - Move one task off a bypass DSQ for the balancer + * @sch: host sched whose bypass DSQs are balanced + * @donor_rq: rq of the cpu whose bypass DSQ gives up @p, locked + * @donor_dsq: @sch's bypass DSQ on @donor_rq's cpu, locked + * @p: task on @donor_dsq, homed anywhere + * @donee: cpu whose bypass DSQ receives @p, -1 for none + * + * Take @p off @donor_dsq and insert it into the bypass DSQ of @donee. The + * caller tests bypass_lb_can_move() without @p's rq lock for a task homed + * elsewhere, and not at all for a drain, so the test is repeated here under + * @p's rq lock. A task that fails it is not put back, as the host may no longer + * consume @donor_dsq. bypass_lb_reenq_home() reenqueues it at its home instead. + * + * The insert and the reenqueue run under @p's rq lock. A task homed on + * @donor_rq is dequeued in place. unlink_dsq_and_switch_rq_lock() takes one + * homed elsewhere off and switches the rq lock from @donor_rq to its own. The + * switch can lose to a dequeue, and @p then belongs to the dequeuer. + * + * @donor_rq and @donor_dsq are locked on entry and on return. @donor_dsq is + * unlocked in between, and @donor_rq too while the lock is switched, so the + * caller's walk must find its place in @donor_dsq again after the call. + * + * Return the cpu that received @p, or -1 if @p was lost to a dequeue. + */ +static s32 bypass_lb_move(struct scx_sched *sch, struct rq *donor_rq, + struct scx_dispatch_q *donor_dsq, struct task_struct *p, s32 donee) +{ + struct rq *rq = task_rq(p); + s32 ret; + + lockdep_assert_rq_held(donor_rq); + lockdep_assert_held(&donor_dsq->lock); + + if (rq == donor_rq) { + scx_wait_dispatching(p); + dispatch_dequeue_locked(p, donor_dsq); + raw_spin_unlock(&donor_dsq->lock); + } else if (!unlink_dsq_and_switch_rq_lock(p, donor_dsq, donor_rq, rq)) { + /* lost to a dequeue, @p is the dequeuer's now */ + ret = -1; + goto out; + } + + if (bypass_lb_can_move(sch, p, donee)) { + scx_dispatch_enqueue(sch, rq, scx_bypass_dsq(sch, donee), p, 0, 0, 0); + ret = donee; + } else { + /* + * No donee, or @p can't run on it. Reenqueue @p at home + * instead, see bypass_lb_reenq_home(). + */ + bypass_lb_reenq_home(rq, p, cpu_of(donor_rq)); + ret = cpu_of(rq); + } +out: + if (rq != donor_rq) + switch_rq_lock(rq, donor_rq); + raw_spin_lock(&donor_dsq->lock); + return ret; +} + static u32 bypass_lb_cpu(struct scx_sched *sch, s32 donor, struct cpumask *donee_mask, struct cpumask *resched_mask, u32 nr_donor_target, u32 nr_donee_target) @@ -6330,87 +6759,94 @@ static u32 bypass_lb_cpu(struct scx_sched *sch, s32 donor, * All we want to guarantee is reasonable forward progress. No reason to * fine tune. Assuming every task on @donor_dsq runs their full slice, * consider offloading iff the total queued duration is over the - * threshold. + * threshold. A zero target is a drain and empties the DSQ regardless. */ min_delta_us = READ_ONCE(scx_bypass_lb_intv_us) / SCX_BYPASS_LB_MIN_DELTA_DIV; - if (delta < DIV_ROUND_UP(min_delta_us, READ_ONCE(scx_slice_bypass_us))) + if (nr_donor_target && + delta < DIV_ROUND_UP(min_delta_us, READ_ONCE(scx_slice_bypass_us))) return 0; raw_spin_rq_lock_irq(donor_rq); raw_spin_lock(&donor_dsq->lock); + /* bound the walk to the tasks queued now, see the seq test below */ + cursor.priv = donor_dsq->seq; list_add(&cursor.node, &donor_dsq->list); resume: n = container_of(&cursor, struct task_struct, scx.dsq_list); n = nldsq_next_task(donor_dsq, n, false); while ((p = n)) { - struct scx_dispatch_q *donee_dsq; - int donee; + s32 donee, cpu; n = nldsq_next_task(donor_dsq, n, false); if (donor_dsq->nr <= nr_donor_target) break; - if (cpumask_empty(donee_mask)) - break; - /* - * If an earlier pass placed @p on @donor_dsq from a different - * CPU and the donee hasn't consumed it yet, @p is still on the - * previous CPU and task_rq(@p) != @donor_rq. @p can't be moved - * without its rq locked. Skip. + * Without a donee, a balancing donor has nothing to do. A drain + * still sends its tasks home. */ - if (task_rq(p) != donor_rq) - continue; - - donee = cpumask_any_and_distribute(donee_mask, p->cpus_ptr); - if (donee >= nr_cpu_ids) - continue; - - donee_dsq = scx_bypass_dsq(sch, donee); + if (cpumask_empty(donee_mask) && nr_donor_target) + break; /* - * $p's rq is not locked but $p's DSQ lock protects its - * scheduling properties making this test safe. + * A task queued after the walk began, including one the walk + * itself reenqueued, is left for the next pass. */ - if (!task_can_run_on_remote_rq(sch, p, cpu_rq(donee), false)) + if (u32_before(cursor.priv, p->scx.dsq_seq)) continue; /* - * Moving $p from one non-local DSQ to another. The source rq - * and DSQ are already locked. Do an abbreviated dequeue and - * then perform enqueue without unlocking $donor_dsq. - * - * We don't want to drop and reacquire the lock on each - * iteration as @donor_dsq can be very long and potentially - * highly contended. Donee DSQs are less likely to be contended. - * The nested locking is safe as only this LB moves tasks - * between bypass DSQs. + * A balancing donor leaves a task that can't move where it is. + * A home reenqueue would push one homed on the donor to the + * back of @donor_dsq on every pass. A drain sends it home. */ - dispatch_dequeue_locked(p, donor_dsq); - scx_dispatch_enqueue(sch, cpu_rq(donee), donee_dsq, p, 0, 0, SCX_ENQ_NESTED); + donee = cpumask_any_and_distribute(donee_mask, p->cpus_ptr); + if (donee >= nr_cpu_ids) + donee = -1; + if (nr_donor_target && !bypass_lb_can_move(sch, p, donee)) + continue; /* - * $donee might have been idle and need to be woken up. No need - * to be clever. Kick every CPU that receives tasks. + * The move drops @donor_dsq's lock, and the rq lock too when + * @p is homed elsewhere. The donor cpu's dispatch and its + * enqueuers can reach @donor_dsq then. Park the cursor behind + * @p and resume from it afterwards. The seq test above keeps a + * task enqueued meanwhile out of the pass. */ - cpumask_set_cpu(donee, resched_mask); + list_move(&cursor.node, &p->scx.dsq_list.node); + cpu = bypass_lb_move(sch, donor_rq, donor_dsq, p, donee); + if (cpu >= 0) { + /* + * @cpu might have been idle and need to be woken up. + * No need to be clever. Reschedule every cpu that + * receives tasks. + */ + cpumask_set_cpu(cpu, resched_mask); - if (READ_ONCE(donee_dsq->nr) >= nr_donee_target) - cpumask_clear_cpu(donee, donee_mask); + if (READ_ONCE(scx_bypass_dsq(sch, cpu)->nr) >= nr_donee_target) + cpumask_clear_cpu(cpu, donee_mask); - nr_balanced++; - if (!(nr_balanced % SCX_BYPASS_LB_BATCH) && n) { - list_move_tail(&cursor.node, &n->scx.dsq_list.node); - raw_spin_unlock(&donor_dsq->lock); - scx_rq_lock_drop(donor_rq); - raw_spin_rq_unlock_irq(donor_rq); - cpu_relax(); - raw_spin_rq_lock_irq(donor_rq); - raw_spin_lock(&donor_dsq->lock); - goto resume; + /* + * The rq lock is held across the walk, not cycled per + * move. @donor_dsq can be very long and contended, and + * the rq lock is what keeps its consumer and enqueuers + * away while the walk cycles the DSQ lock. The rare + * move of a task homed elsewhere does switch it away, + * see the cursor comment above. The walk can still take + * a while, so let the cpu breathe every so often. + */ + if (!(++nr_balanced % SCX_BYPASS_LB_BATCH)) { + raw_spin_unlock(&donor_dsq->lock); + scx_rq_lock_drop(donor_rq); + raw_spin_rq_unlock_irq(donor_rq); + cpu_relax(); + raw_spin_rq_lock_irq(donor_rq); + raw_spin_lock(&donor_dsq->lock); + } } + goto resume; } list_del_init(&cursor.node); @@ -6426,6 +6862,7 @@ static void bypass_lb_node(struct scx_sched *sch, int node) const struct cpumask *node_mask = cpumask_of_node(node); struct cpumask *donee_mask = sch->bypass_lb_donee_cpumask; struct cpumask *resched_mask = sch->bypass_lb_resched_cpumask; + u32 intv_us = READ_ONCE(scx_bypass_lb_intv_us); u32 nr_tasks = 0, nr_cpus = 0, nr_balanced = 0; u32 nr_target, nr_donor_target; u32 before_min = U32_MAX, before_max = 0; @@ -6437,13 +6874,15 @@ static void bypass_lb_node(struct scx_sched *sch, int node) u32 nr = READ_ONCE(scx_bypass_dsq(sch, cpu)->nr); nr_tasks += nr; - nr_cpus++; + /* only a cpu whose dispatch consumes its DSQ is capacity */ + if (!scx_missing_caps(sch, cpu, SCX_CAP_BASE)) + nr_cpus++; before_min = min(nr, before_min); before_max = max(nr, before_max); } - if (!nr_cpus) + if (!nr_tasks) return; /* @@ -6451,27 +6890,39 @@ static void bypass_lb_node(struct scx_sched *sch, int node) * balancing to fill donee CPUs up to $nr_target. Once targets are * calculated, find the donee CPUs. */ - nr_target = DIV_ROUND_UP(nr_tasks, nr_cpus); + nr_target = nr_cpus ? DIV_ROUND_UP(nr_tasks, nr_cpus) : 0; nr_donor_target = DIV_ROUND_UP(nr_target * SCX_BYPASS_LB_DONOR_PCT, 100); cpumask_clear(donee_mask); for_each_cpu_and(cpu, cpu_online_mask, node_mask) { - if (READ_ONCE(scx_bypass_dsq(sch, cpu)->nr) < nr_target) + /* a donee's DSQ is consumed only if @sch holds %SCX_CAP_BASE */ + if (READ_ONCE(scx_bypass_dsq(sch, cpu)->nr) < nr_target && + !scx_missing_caps(sch, cpu, SCX_CAP_BASE)) cpumask_set_cpu(cpu, donee_mask); } - /* iterate !donee CPUs and see if they should be offloaded */ + /* + * Offload the !donee cpus. A cpu where the host lost %SCX_CAP_BASE no + * longer consumes its DSQ. Drain it as a donor with a target of zero. A + * zero interval disables the balancing, not the drain. + */ cpumask_clear(resched_mask); for_each_cpu_and(cpu, cpu_online_mask, node_mask) { - if (cpumask_empty(donee_mask)) - break; - if (cpumask_test_cpu(cpu, donee_mask)) + u32 target = nr_donor_target; + + if (unlikely(scx_missing_caps(sch, cpu, SCX_CAP_BASE))) { + /* the mask may predate the loss, keep this cpu out */ + cpumask_clear_cpu(cpu, donee_mask); + target = 0; + } else if (!intv_us || cpumask_empty(donee_mask) || + cpumask_test_cpu(cpu, donee_mask)) { continue; - if (READ_ONCE(scx_bypass_dsq(sch, cpu)->nr) <= nr_donor_target) + } + if (READ_ONCE(scx_bypass_dsq(sch, cpu)->nr) <= target) continue; nr_balanced += bypass_lb_cpu(sch, cpu, donee_mask, resched_mask, - nr_donor_target, nr_target); + target, nr_target); } for_each_cpu(cpu, resched_mask) @@ -6510,9 +6961,28 @@ static void scx_bypass_lb_timerfn(struct timer_list *timer) for_each_node_with_cpus(node) bypass_lb_node(sch, node); + /* + * A kick during this run can leave the timer pending at now, see + * scx_bypass_lb_kick(). timer_reduce() only brings the expiry forward, + * so that kick is kept. + */ intv_us = READ_ONCE(scx_bypass_lb_intv_us); if (intv_us) - mod_timer(timer, jiffies + usecs_to_jiffies(intv_us)); + timer_reduce(timer, jiffies + usecs_to_jiffies(intv_us)); +} + +/** + * scx_bypass_lb_kick - Run the bypass load balancer now + * @sch: sched that lost %SCX_CAP_BASE on a cpu + * + * @sch no longer consumes its bypass DSQ on that cpu. Have the balancer drain + * it without waiting for the next interval, see bypass_lb_node(). A loss during + * a run leaves the timer pending at now, and the run that follows sees it. + */ +void scx_bypass_lb_kick(struct scx_sched *sch) +{ + if (scx_bypass_dsp_enabled(sch)) + mod_timer(&sch->bypass_lb_timer, jiffies); } static bool inc_bypass_depth(struct scx_sched *sch) @@ -6581,11 +7051,12 @@ static void enable_bypass_dsp(struct scx_sched *sch) /* * The LB timer will stop running if bypass dispatch is disabled. Start - * after enabling bypass dispatch. + * after enabling bypass dispatch. A kick from a BASE loss can have set + * the timer to expire now in the meantime, see scx_bypass_lb_kick(). + * timer_reduce() keeps that expiry. */ - if (intv_us && !timer_pending(&host->bypass_lb_timer)) - mod_timer(&host->bypass_lb_timer, - jiffies + usecs_to_jiffies(intv_us)); + if (intv_us) + timer_reduce(&host->bypass_lb_timer, jiffies + usecs_to_jiffies(intv_us)); } /* may be called without holding scx_bypass_lock */ @@ -6658,9 +7129,14 @@ static void unbypass_renotify_idle(struct rq *rq, struct scx_sched *pos, * * - ops.dispatch() is ignored. * - * - dispatch_one() does not report %SCX_DSP_PREV on non-zero slice as slice - * can't be trusted. Whenever a tick triggers, the running task is rotated to - * the tail of the queue. + * - ops.sub_ecaps_updated() and ops.sub_child_ecaps_updated() are still called. + * The bypassed tasks are on the bypass DSQs, under rescue or admitted to a + * local DSQ, out of their reach. + * + * - dispatch_one() expires prev's slice before its keep test as the slice can't + * be trusted. Each tick does the same and rotates the running task to the + * tail of the queue. A kernel slice is left alone, see + * %SCX_TASK_KERNEL_SLICE. * * - pick_next_task() suppresses zero slice warning. * @@ -6737,10 +7213,8 @@ void scx_bypass(struct scx_sched *sch, bool bypass) pcpu->flags |= SCX_SCHED_PCPU_BYPASSING; } else { pcpu->flags &= ~SCX_SCHED_PCPU_BYPASSING; - if (was_bypassing) { + if (was_bypassing) unbypass_renotify_idle(rq, pos, pcpu); - scx_unbypass_replay_ecaps(rq, pos); - } } } @@ -6758,6 +7232,24 @@ void scx_bypass(struct scx_sched *sch, bool bypass) } /* + * Bypass trumps protection. Cycling the queued tasks below + * clears theirs. The current donor isn't on the runnable list, + * so strip its protection here. + * + * When bypass lifts, the current donor keeps running on its + * slice without a cap check. Evict it if it can't stay on the + * cpu. + */ + p = rq->donor; + if (p->sched_class == &ext_sched_class && + scx_is_descendant(scx_task_sched(p), sch)) { + if (bypass) + scx_task_slice_ended(rq, p); + else if (!scx_task_can_stay_on_cpu(rq, p)) + expire_task_slice(p); + } + + /* * The use of list_for_each_entry_safe_reverse() is required * because each task is going to be removed from and added back * to the runnable_list during iteration. Because they're added @@ -6766,19 +7258,26 @@ void scx_bypass(struct scx_sched *sch, bool bypass) */ list_for_each_entry_safe_reverse(p, n, &rq->scx.runnable_list, scx.runnable_node) { - if (!scx_is_descendant(scx_task_sched(p), sch)) - continue; + struct scx_sched *owner = scx_task_sched(p); - /* - * Bypass trumps protection. Cycling clears for queued - * tasks but the current donor needs explicit stripping. - */ - if (bypass && task_current_donor(rq, p)) - scx_task_slice_ended(rq, p); + if (!scx_is_descendant(owner, sch)) + continue; /* cycling deq/enq is enough, see the function comment */ scoped_guard (sched_change, p, DEQUEUE_SAVE | DEQUEUE_MOVE) { - /* nothing */ ; + /* + * The requeue can change the sched running @p, + * and the watchdog counts @p's wait against + * that sched. Restart the wait unless @owner is + * the root, which runs its own tasks bypassing + * or not. + * + * A dispatch in flight writes p->scx.flags + * without @p's rq lock. The dequeue waits it + * out, so set the flag after it. + */ + if (scx_parent(owner)) + p->scx.flags |= SCX_TASK_RESET_RUNNABLE_AT; } } @@ -8193,6 +8692,8 @@ static void scx_root_enable_workfn(struct kthread_work *work) goto err_disable; } + scx_init_rq_ops_online(); + /* * Make the scheduler instance visible. Must be inside cpus_read_lock(). * See handle_hotplug(). @@ -9299,6 +9800,20 @@ static int scx_pm_handler(struct notifier_block *nb, unsigned long event, void * { struct scx_sched *sch; + /* track the PM cycle whether or not a root is loaded */ + switch (event) { + case PM_HIBERNATION_PREPARE: + case PM_SUSPEND_PREPARE: + case PM_RESTORE_PREPARE: + scx_sub_pm_begin(); + break; + case PM_POST_HIBERNATION: + case PM_POST_SUSPEND: + case PM_POST_RESTORE: + scx_sub_pm_end(); + break; + } + guard(rcu)(); sch = rcu_dereference(scx_root); @@ -9366,6 +9881,7 @@ void __init init_sched_ext_class(void) INIT_LIST_HEAD(&rq->scx.deferred_reenq_users); rq->scx.deferred_irq_work = IRQ_WORK_INIT_HARD(deferred_irq_workfn); rq->scx.kick_cpus_irq_work = IRQ_WORK_INIT_HARD(kick_cpus_irq_workfn); + rq->scx.resched_irq_work = IRQ_WORK_INIT_HARD(resched_irq_workfn); if (cpu_online(cpu)) cpu_rq(cpu)->scx.flags |= SCX_RQ_ONLINE; @@ -9650,6 +10166,40 @@ static const struct btf_kfunc_id_set scx_kfunc_set_enqueue_dispatch = { .filter = scx_kfunc_context_filter, }; +/* + * Lock @rq from a kfunc called either from ops.dispatch(), which holds the + * dispatched rq's lock, or from a context holding no rq lock. Under core + * scheduling, dispatch can run for a sibling rq, so the locked rq is not + * necessarily this CPU's. Return the rq locked on entry, NULL if none. + */ +static struct rq *kf_switch_rq_lock(struct rq *rq, unsigned long *flags) +{ + struct rq *entry_rq; + + local_irq_save(*flags); + + entry_rq = scx_locked_rq(); + if (entry_rq) { + if (entry_rq != rq) + switch_rq_lock(entry_rq, rq); + } else { + raw_spin_rq_lock(rq); + } + return entry_rq; +} + +/* undo kf_switch_rq_lock(), @rq is the rq locked now */ +static void kf_restore_rq_lock(struct rq *rq, struct rq *entry_rq, unsigned long flags) +{ + if (entry_rq) { + if (entry_rq != rq) + switch_rq_lock(rq, entry_rq); + } else { + scx_rq_lock_drop(rq); + raw_spin_rq_unlock_irqrestore(rq, flags); + } +} + static bool scx_dsq_move(struct bpf_iter_scx_dsq_kern *kit, struct task_struct *p, u64 dsq_id, u64 enq_flags, bool priq) @@ -9684,27 +10234,8 @@ static bool scx_dsq_move(struct bpf_iter_scx_dsq_kern *kit, if (unlikely(READ_ONCE(sch->aborting))) return false; - /* - * Can be called from either ops.dispatch() holding the dispatched rq's - * lock or any context where no rq lock is held. If latter, lock @p's - * task_rq which we'll likely need anyway. - */ src_rq = task_rq(p); - - local_irq_save(flags); - - /* - * Under core scheduling, dispatch can run for a sibling rq, so the - * locked rq is not necessarily this CPU's. - */ - locked_rq = scx_locked_rq(); - - if (locked_rq) { - if (locked_rq != src_rq) - switch_rq_lock(locked_rq, src_rq); - } else { - raw_spin_rq_lock(src_rq); - } + locked_rq = kf_switch_rq_lock(src_rq, &flags); p_rq = src_rq; raw_spin_lock(&src_dsq->lock); @@ -9743,13 +10274,7 @@ static bool scx_dsq_move(struct bpf_iter_scx_dsq_kern *kit, p_rq = move_task_between_dsqs(sch, p, enq_flags, src_dsq, dst_dsq); dispatched = true; out: - if (locked_rq) { - if (locked_rq != p_rq) - switch_rq_lock(p_rq, locked_rq); - } else { - scx_rq_lock_drop(p_rq); - raw_spin_rq_unlock_irqrestore(p_rq, flags); - } + kf_restore_rq_lock(p_rq, locked_rq, flags); kit->cursor.flags &= ~(__SCX_DSQ_ITER_HAS_SLICE | __SCX_DSQ_ITER_HAS_VTIME); @@ -9983,6 +10508,8 @@ BTF_ID_FLAGS(func, scx_bpf_dsq_move_set_slice, KF_RCU) BTF_ID_FLAGS(func, scx_bpf_dsq_move_set_vtime, KF_RCU) BTF_ID_FLAGS(func, scx_bpf_dsq_move, KF_RCU) BTF_ID_FLAGS(func, scx_bpf_dsq_move_vtime, KF_RCU) +/* also in scx_kfunc_ids_unlocked, same contexts as scx_bpf_dsq_move() */ +BTF_ID_FLAGS(func, scx_bpf_dsq_reenq_task, KF_RCU) #ifdef CONFIG_EXT_SUB_SCHED BTF_ID_FLAGS(func, scx_bpf_sub_dispatch, KF_IMPLICIT_ARGS) #endif @@ -10098,6 +10625,7 @@ BTF_ID_FLAGS(func, scx_bpf_dsq_move_set_slice, KF_RCU) BTF_ID_FLAGS(func, scx_bpf_dsq_move_set_vtime, KF_RCU) BTF_ID_FLAGS(func, scx_bpf_dsq_move, KF_RCU) BTF_ID_FLAGS(func, scx_bpf_dsq_move_vtime, KF_RCU) +BTF_ID_FLAGS(func, scx_bpf_dsq_reenq_task, KF_RCU) /* also in scx_kfunc_ids_select_cpu: also callable from ops.select_cpu()/ops.enqueue() */ BTF_ID_FLAGS(func, __scx_bpf_select_cpu_and, KF_IMPLICIT_ARGS | KF_RCU) BTF_ID_FLAGS(func, scx_bpf_select_cpu_and, KF_RCU) @@ -10123,10 +10651,12 @@ __bpf_kfunc_start_defs(); * rules above for the ownership model. * * Raising the slice is honored only while the scheduler holds %SCX_CAP_BASE on - * @p's cpu, otherwise it is counted in %SCX_EV_SLICE_DENIED. Shortening is - * always allowed. On the stashed path the slice is packed into an atomic64_t - * with the scheduler id and a flag bit, so a slice too large to fit is clamped - * and counted in %SCX_EV_SLICE_CLAMPED. %SCX_SLICE_INF is preserved. + * @p's cpu, and never on a kernel slice, see %SCX_TASK_KERNEL_SLICE. Shortening + * is honored unless @p is protected, see %SCX_TASK_PROTECTED, which refuses + * every write. A refused write is counted in %SCX_EV_SLICE_DENIED. On the + * stashed path the slice is packed into an atomic64_t with the scheduler id and + * a flag bit, so a slice too large to fit is clamped and counted in + * %SCX_EV_SLICE_CLAMPED. %SCX_SLICE_INF is preserved. * * Return %true on success, %false if @p is not on the calling scheduler. */ @@ -10164,9 +10694,13 @@ __bpf_kfunc bool scx_bpf_task_set_slice(struct task_struct *p, u64 slice, return true; } - /* under the rq lock: apply now, extensions gated on baseline access */ + /* + * @p's rq is locked, so apply now. An extension needs baseline access + * and is refused on a kernel slice. + */ if (slice > p->scx.slice && - unlikely(scx_missing_caps(sch, cpu_of(locked_rq), SCX_CAP_BASE))) { + unlikely(scx_task_has_kernel_slice(p) || + scx_missing_caps(sch, cpu_of(locked_rq), SCX_CAP_BASE))) { __scx_add_event(sch, SCX_EV_SLICE_DENIED, 1); return true; } @@ -10506,7 +11040,8 @@ __bpf_kfunc struct task_struct *bpf_iter_scx_dsq_next(struct bpf_iter_scx_dsq *i * bpf_iter_scx_dsq_destroy - Destroy a DSQ iterator * @it: iterator to destroy * - * Undo bpf_iter_scx_dsq_new(). + * Undo bpf_iter_scx_dsq_new(). If the iteration marked tasks with + * scx_bpf_dsq_reenq_task(), schedule their re-enqueue. */ __bpf_kfunc void bpf_iter_scx_dsq_destroy(struct bpf_iter_scx_dsq *it) { @@ -10522,6 +11057,13 @@ __bpf_kfunc void bpf_iter_scx_dsq_destroy(struct bpf_iter_scx_dsq *it) list_del_init(&kit->cursor.node); raw_spin_unlock_irqrestore(&kit->dsq->lock, flags); } + + if (kit->cursor.flags & __SCX_DSQ_ITER_HAS_REENQ) { + guard(preempt)(); + schedule_dsq_reenq(kit->dsq->sched, kit->dsq, SCX_REENQ_MARKED, + scx_locked_rq()); + } + kit->dsq = NULL; } @@ -10574,7 +11116,8 @@ __bpf_kfunc struct task_struct *scx_bpf_dsq_peek(u64 dsq_id, * - Local DSQs (%SCX_DSQ_LOCAL or %SCX_DSQ_LOCAL_ON | $cpu) * - User DSQs * - * Re-enqueues are performed asynchronously. Can be called from anywhere. + * Re-enqueues are performed asynchronously. Can be called from anywhere. A + * re-enqueue of an inactive cpu's local DSQ is ignored. * * %SCX_DSQ_LOCAL resolves to the local DSQ of the rq the current scheduler * operation is locked to - e.g. the rq being dispatched for in ops.dispatch() - @@ -10610,6 +11153,64 @@ __bpf_kfunc void scx_bpf_dsq_reenq(u64 dsq_id, u64 reenq_flags, } /** + * scx_bpf_dsq_reenq_task - Re-enqueue a task from a DSQ iteration + * @it__iter: DSQ iterator in progress + * @p: task to re-enqueue + * + * Mark @p, which is on the DSQ iterated by @it__iter and was queued before the + * iteration started, for re-enqueue. When the iteration ends, the DSQ's marked + * tasks go through ops.enqueue() with %SCX_ENQ_REENQ in DSQ order and the other + * tasks on the DSQ keep their positions. A marked task that leaves the DSQ in + * the meantime is not re-enqueued. The mark belongs to @p, so a re-enqueue + * scheduled by another iteration of the DSQ may re-enqueue @p before this + * iteration ends. @p must be on the DSQ's scheduler. + * + * Re-enqueues are performed asynchronously. Can be called from ops.dispatch() + * or any BPF context which doesn't hold a rq lock (e.g. BPF timers or SYSCALL + * programs). + * + * Return %true if @p was marked, %false if @p left the DSQ or was queued after + * the iteration started, @p is on another scheduler, or the iterator holds no + * DSQ. + */ +__bpf_kfunc bool scx_bpf_dsq_reenq_task(struct bpf_iter_scx_dsq *it__iter, + struct task_struct *p) +{ + struct bpf_iter_scx_dsq_kern *kit = (void *)it__iter; + struct scx_dispatch_q *dsq = kit->dsq; + struct rq *src_rq, *entry_rq; + unsigned long flags; + bool marked = false; + + /* NULL after a failed bpf_iter_scx_dsq_new(), see scx_dsq_move() */ + if (unlikely(!dsq)) + return false; + + /* the cursor check needs @p's rq locked */ + src_rq = task_rq(p); + entry_rq = kf_switch_rq_lock(src_rq, &flags); + + scoped_guard (raw_spinlock, &dsq->lock) { + if (nldsq_cursor_lost_task(&kit->cursor, src_rq, dsq, p)) + break; + + if (unlikely(!scx_task_on_sched(dsq->sched, p))) { + scx_error(dsq->sched, "scx_bpf_dsq_reenq_task() on %s[%d] but the task belongs to a different scheduler", + p->comm, p->pid); + break; + } + + p->scx.dsq_flags |= SCX_TASK_DSQ_REENQ; + /* the walk is scheduled once, by bpf_iter_scx_dsq_destroy() */ + kit->cursor.flags |= __SCX_DSQ_ITER_HAS_REENQ; + marked = true; + } + + kf_restore_rq_lock(src_rq, entry_rq, flags); + return marked; +} + +/** * scx_bpf_reenqueue_local___v2 - Re-enqueue tasks on a local DSQ * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs * @@ -11524,6 +12125,31 @@ static const struct btf_kfunc_id_set scx_kfunc_set_any = { }; /* + * Kfuncs that tracing programs can't call. A tracing program can run in any + * kernel context, including with an rq lock held. scx_locked_rq() only tracks + * rq locks held across SCX callbacks and returns NULL there. + * + * scx_bpf_cpuperf_set() and scx_bpf_cidperf_set() take the target cpu's rq lock + * when scx_locked_rq() returns NULL. Taking it while the context already holds + * an rq lock, the same one or another cpu's, can deadlock. + * + * Before returning, scx_bpf_sub_grant() and scx_bpf_sub_revoke() invoke + * ops.sub_caps_updated() of the sub-schedulers whose caps changed, so those ops + * run in the tracing program's context. No SCX op expects to run from an + * arbitrary tracing context. One that calls scx_bpf_cidperf_set() hits the + * deadlock above. + * + * Members must also stay in scx_kfunc_ids_any so that struct_ops and syscall + * programs keep their access. + */ +BTF_KFUNCS_START(scx_kfunc_ids_no_tracing) +BTF_ID_FLAGS(func, scx_bpf_cpuperf_set, KF_IMPLICIT_ARGS) +BTF_ID_FLAGS(func, scx_bpf_cidperf_set, KF_IMPLICIT_ARGS) +BTF_ID_FLAGS(func, scx_bpf_sub_grant, KF_IMPLICIT_ARGS) +BTF_ID_FLAGS(func, scx_bpf_sub_revoke, KF_IMPLICIT_ARGS) +BTF_KFUNCS_END(scx_kfunc_ids_no_tracing) + +/* * cpu-form kfuncs that are forbidden from cid-form schedulers * (bpf_sched_ext_ops_cid). Programs targeting the cid struct_ops type must * use the cid-form alternative (cid/cmask kfuncs). @@ -11631,6 +12257,7 @@ int scx_kfunc_context_filter(const struct bpf_prog *prog, u32 kfunc_id) bool in_any = btf_id_set8_contains(&scx_kfunc_ids_any, kfunc_id); bool in_cpu_only = btf_id_set8_contains(&scx_kfunc_ids_cpu_only, kfunc_id); bool in_cid = btf_id_set8_contains(&scx_kfunc_ids_cid, kfunc_id); + bool in_no_tracing = btf_id_set8_contains(&scx_kfunc_ids_no_tracing, kfunc_id); u32 moff, flags; /* Not an SCX kfunc - allow. */ @@ -11643,7 +12270,7 @@ int scx_kfunc_context_filter(const struct bpf_prog *prog, u32 kfunc_id) return (in_unlocked || in_select_cpu || in_idle || in_any || in_cid) ? 0 : -EACCES; if (prog->type != BPF_PROG_TYPE_STRUCT_OPS) - return (in_any || in_idle || in_cid) ? 0 : -EACCES; + return (!in_no_tracing && (in_any || in_idle || in_cid)) ? 0 : -EACCES; /* * add_subprog_and_kfunc() collects all kfunc calls, including dead code |