* Copyright (c) 2022 Tejun Heo <tj@kernel.org>

* Copyright (c) 2022 David Vernet <dvernet@meta.com>

*/

#define SCX_OP_IDX(op) (offsetof(struct sched_ext_ops, op) / sizeof(void (*)(void)))

enum scx_consts {

/*

* Keep built-in idle tracking even if ops.update_idle() is implemented.

*/

/*

* By default, if there are no other task to run on the CPU, ext core

* flag is specified, such tasks are passed to ops.enqueue() with

* %SCX_ENQ_LAST. See the comment above %SCX_ENQ_LAST for more info.

*/

/*

* An exiting task may schedule after PF_EXITING is set. In such cases,

* depend on pid lookups and wants to handle these tasks directly, the

* following flag can be used.

*/

/*

* If set, only tasks with policy set to SCHED_EXT are attached to

* sched_ext. If clear, SCHED_NORMAL tasks are also included.

*/

/*

* CPU cgroup support flags

SCX_OPS_ALL_FLAGS = SCX_OPS_KEEP_BUILTIN_IDLE |

SCX_OPS_ENQ_LAST |

SCX_OPS_ENQ_EXITING |

SCX_OPS_SWITCH_PARTIAL |

SCX_OPS_HAS_CGROUP_WEIGHT,

};

*/

struct sched_ext_ops {

/**

* @p: task being woken up

* @prev_cpu: the cpu @p was on before sleeping

* @wake_flags: SCX_WAKE_*

s32 (*select_cpu)(struct task_struct *p, s32 prev_cpu, u64 wake_flags);

/**

* @p: task being enqueued

* @enq_flags: %SCX_ENQ_*

*

void (*enqueue)(struct task_struct *p, u64 enq_flags);

/**

* @p: task being dequeued

* @deq_flags: %SCX_DEQ_*

*

void (*dequeue)(struct task_struct *p, u64 deq_flags);

/**

* @cpu: CPU to dispatch tasks for

* @prev: previous task being switched out

*

void (*dispatch)(s32 cpu, struct task_struct *prev);

/**

* @p: task running currently

*

* This operation is called every 1/HZ seconds on CPUs which are

void (*tick)(struct task_struct *p);

/**

* @p: task becoming runnable

* @enq_flags: %SCX_ENQ_*

*

void (*runnable)(struct task_struct *p, u64 enq_flags);

/**

* @p: task starting to run

*

* See ->runnable() for explanation on the task state notifiers.

void (*running)(struct task_struct *p);

/**

* @p: task stopping to run

* @runnable: is task @p still runnable?

*

void (*stopping)(struct task_struct *p, bool runnable);

/**

* @p: task becoming not runnable

* @deq_flags: %SCX_DEQ_*

*

void (*quiescent)(struct task_struct *p, u64 deq_flags);

/**

* @from: yielding task

* @to: optional yield target task

*

bool (*yield)(struct task_struct *from, struct task_struct *to);

/**

* @a: task A

* @b: task B

*

bool (*core_sched_before)(struct task_struct *a, struct task_struct *b);

/**

* @p: task to set weight for

* @weight: new weight [1..10000]

*

void (*set_weight)(struct task_struct *p, u32 weight);

/**

* @p: task to set CPU affinity for

* @cpumask: cpumask of cpus that @p can run on

*

const struct cpumask *cpumask);

/**

* @idle: whether entering or exiting the idle state

*

* This operation is called when @rq's CPU goes or leaves the idle

void (*update_idle)(s32 cpu, bool idle);

/**

* @cpu: The CPU being acquired by the BPF scheduler.

* @args: Acquire arguments, see the struct definition.

*

void (*cpu_acquire)(s32 cpu, struct scx_cpu_acquire_args *args);

/**

* @cpu: The CPU being released by the BPF scheduler.

* @args: Release arguments, see the struct definition.

*

void (*cpu_release)(s32 cpu, struct scx_cpu_release_args *args);

/**

* @p: task to initialize for BPF scheduling

* @args: init arguments, see the struct definition

*

s32 (*init_task)(struct task_struct *p, struct scx_init_task_args *args);

/**

* @p: task to exit

*

* @p is exiting or the BPF scheduler is being unloaded. Perform any

* necessary cleanup for @p.

void (*exit_task)(struct task_struct *p, struct scx_exit_task_args *args);

/**

* @p: task to enable BPF scheduling for

*

* Enable @p for BPF scheduling. enable() is called on @p any time it

void (*enable)(struct task_struct *p);

/**

* @p: task to disable BPF scheduling for

*

* @p is exiting, leaving SCX or the BPF scheduler is being unloaded.

void (*disable)(struct task_struct *p);

/**

* @ctx: debug dump context

*

* Use scx_bpf_dump() to generate BPF scheduler specific debug dump.

void (*dump)(struct scx_dump_ctx *ctx);

/**

* @ctx: debug dump context

* @cpu: CPU to generate debug dump for

* @idle: @cpu is currently idle without any runnable tasks

void (*dump_cpu)(struct scx_dump_ctx *ctx, s32 cpu, bool idle);

/**

* @ctx: debug dump context

* @p: runnable task to generate debug dump for

*

#ifdef CONFIG_EXT_GROUP_SCHED

/**

* @cgrp: cgroup being initialized

* @args: init arguments, see the struct definition

*

struct scx_cgroup_init_args *args);

/**

* @cgrp: cgroup being exited

*

* Either the BPF scheduler is being unloaded or @cgrp destroyed, exit

void (*cgroup_exit)(struct cgroup *cgrp);

/**

* @p: task being moved

* @from: cgroup @p is being moved from

* @to: cgroup @p is being moved to

struct cgroup *from, struct cgroup *to);

/**

* @p: task being moved

* @from: cgroup @p is being moved from

* @to: cgroup @p is being moved to

struct cgroup *from, struct cgroup *to);

/**

* @p: task whose cgroup move is being canceled

* @from: cgroup @p was being moved from

* @to: cgroup @p was being moved to

struct cgroup *from, struct cgroup *to);

/**

* @cgrp: cgroup whose weight is being updated

* @weight: new weight [1..10000]

*

*/

/**

* @cpu: CPU which just came up

*

* @cpu just came online. @cpu will not call ops.enqueue() or

void (*cpu_online)(s32 cpu);

/**

* @cpu: CPU which is going offline

*

* @cpu is going offline. @cpu will not call ops.enqueue() or

*/

/**

*/

s32 (*init)(void);

/**

* @info: Exit info

*

* ops.exit() is also called on ops.init() failure, which is a bit

void (*exit)(struct scx_exit_info *info);

/**

*/

u32 dispatch_max_batch;

/**

*/

u64 flags;

/**

* runnable task should be able to wait before being scheduled. The

* maximum timeout may not exceed the default timeout of 30 seconds.

*

u32 timeout_ms;

/**

* value of 32768 is used.

*/

u32 exit_dump_len;

/**

* detect when a hotplug event has occurred during the loading process.

* If 0, no detection occurs. Otherwise, the scheduler will fail to

* load if the sequence number does not match @scx_hotplug_seq on the

u64 hotplug_seq;

/**

*

* Must be a non-zero valid BPF object name including only isalnum(),

* '_' and '.' chars. Shows up in kernel.sched_ext_ops sysctl while the

enum scx_pick_idle_cpu_flags {

SCX_PICK_IDLE_CORE = 1LLU << 0, /* pick a CPU whose SMT siblings are also idle */

};

enum scx_kick_flags {

static struct sched_ext_ops scx_ops;

static bool scx_warned_zero_slice;

static DEFINE_STATIC_KEY_FALSE(scx_ops_enq_last);

static DEFINE_STATIC_KEY_FALSE(scx_ops_enq_exiting);

static DEFINE_STATIC_KEY_FALSE(scx_ops_cpu_preempt);

static struct static_key_false scx_has_op[SCX_OPI_END] =

{ [0 ... SCX_OPI_END-1] = STATIC_KEY_FALSE_INIT };

static struct delayed_work scx_watchdog_work;

/* for %SCX_KICK_WAIT */

static unsigned long __percpu *scx_kick_cpus_pnt_seqs;

static struct scx_dispatch_q **global_dsqs;

static const struct rhashtable_params dsq_hash_params = {

.key_offset = offsetof(struct scx_dispatch_q, id),

.head_offset = offsetof(struct scx_dispatch_q, hash_node),

};

/**

* nldsq_next_task - Iterate to the next task in a non-local DSQ

* @cur: current position, %NULL to start iteration

* @rev: walk backwards

*

/**

* scx_task_iter_next_locked - Next non-idle task with its rq locked

* @iter: iterator to walk

*

* Visit the non-idle task with its rq lock held. Allows callers to specify

* whether they would like to filter out dead tasks. See scx_task_iter_start()

return p;

}

static enum scx_ops_enable_state scx_ops_enable_state(void)

{

return atomic_read(&scx_ops_enable_state_var);

if (!scx_rq_online(rq))

goto local;

goto global;

if (p->scx.ddsp_dsq_id != SCX_DSQ_INVALID)

goto direct;

/* see %SCX_OPS_ENQ_EXITING */

if (!static_branch_unlikely(&scx_ops_enq_exiting) &&

goto local;

if (!SCX_HAS_OP(enqueue))

goto global;

*/

touch_core_sched(rq, p);

p->scx.slice = SCX_SLICE_DFL;

local_norefill:

dispatch_enqueue(&rq->scx.local_dsq, p, enq_flags);

return;

global:

touch_core_sched(rq, p); /* see the comment in local: */

p->scx.slice = SCX_SLICE_DFL;

dispatch_enqueue(find_global_dsq(p), p, enq_flags);

}

/*

* list_add_tail() must be used. scx_ops_bypass() depends on tasks being

*/

list_add_tail(&p->scx.runnable_node, &rq->scx.runnable_list);

}

do_enqueue_task(rq, p, enq_flags, sticky_cpu);

out:

rq->scx.flags &= ~SCX_RQ_IN_WAKEUP;

}

static void ops_dequeue(struct task_struct *p, u64 deq_flags)

*

* - The BPF scheduler is bypassed while the rq is offline and we can always say

* no to the BPF scheduler initiated migrations while offline.

*/

static bool task_can_run_on_remote_rq(struct task_struct *p, struct rq *rq,

{

int cpu = cpu_of(rq);

/*

* We don't require the BPF scheduler to avoid dispatching to offline

* CPUs mostly for convenience but also because CPUs can go offline

* picked CPU is outside the allowed mask.

*/

if (!task_allowed_on_cpu(p, cpu)) {

return false;

}

return false;

return true;

}

}

#else /* CONFIG_SMP */

static inline void move_remote_task_to_local_dsq(struct task_struct *p, u64 enq_flags, struct rq *src_rq, struct rq *dst_rq) { WARN_ON_ONCE(1); }

static inline bool consume_remote_task(struct rq *this_rq, struct task_struct *p, struct scx_dispatch_q *dsq, struct rq *task_rq) { return false; }

#endif /* CONFIG_SMP */

if (dst_dsq->id == SCX_DSQ_LOCAL) {

dst_rq = container_of(dst_dsq, struct rq, scx.local_dsq);

dst_dsq = find_global_dsq(p);

dst_rq = src_rq;

}

/*

* A poorly behaving BPF scheduler can live-lock the system by e.g. incessantly

* banging on the same DSQ on a large NUMA system to the point where switching

* bypass mode is switching to guarantee timely completion.

*/

static void scx_ops_breather(struct rq *rq)

{

struct rq *src_rq = task_rq(p);

struct rq *dst_rq = container_of(dst_dsq, struct rq, scx.local_dsq);

/*

* We're synchronized against dequeue through DISPATCHING. As @p can't

}

#ifdef CONFIG_SMP

dispatch_enqueue(find_global_dsq(p), p,

enq_flags | SCX_ENQ_CLEAR_OPSS);

return;

atomic_long_set_release(&p->scx.ops_state, SCX_OPSS_NONE);

/* switch to @src_rq lock */

raw_spin_rq_lock(src_rq);

}

} else {

move_remote_task_to_local_dsq(p, enq_flags,

src_rq, dst_rq);

}

/* if the destination CPU is idle, wake it up */

}

/* switch back to @rq lock */

raw_spin_rq_lock(rq);

}

#else /* CONFIG_SMP */

if (prev_on_rq && (!static_branch_unlikely(&scx_ops_enq_last) ||

scx_rq_bypassing(rq))) {

rq->scx.flags |= SCX_RQ_BAL_KEEP;

goto has_tasks;

}

rq->scx.flags &= ~SCX_RQ_IN_BALANCE;

{

struct task_struct *prev = rq->curr;

struct task_struct *p;

bool keep_prev = rq->scx.flags & SCX_RQ_BAL_KEEP;

bool kick_idle = false;

* if pick_task_scx() is called without preceding balance_scx().

*/

if (unlikely(rq->scx.flags & SCX_RQ_BAL_PENDING)) {

keep_prev = true;

} else {

keep_prev = false;

kick_idle = true;

}

WARN_ON_ONCE(scx_ops_enable_state() == SCX_OPS_ENABLED);

keep_prev = false;

}

*/

if (keep_prev) {

p = prev;

p->scx.slice = SCX_SLICE_DFL;

} else {

p = first_local_task(rq);

if (!p) {

scx_warned_zero_slice = true;

}

p->scx.slice = SCX_SLICE_DFL;

}

}

* scx_prio_less - Task ordering for core-sched

* @a: task A

* @b: task B

*

* Core-sched is implemented as an additional scheduling layer on top of the

* usual sched_class'es and needs to find out the expected task ordering. For

*

* Unless overridden by ops.core_sched_before(), @p->scx.core_sched_at is used

* to implement the default task ordering. The older the timestamp, the higher

* behavior.

*

* When ops.core_sched_before() is enabled, @p->scx.core_sched_at is used to

#ifdef CONFIG_SMP

static int select_task_rq_scx(struct task_struct *p, int prev_cpu, int wake_flags)

{

/*

* sched_exec() calls with %WF_EXEC when @p is about to exec(2) as it

* can be a good migration opportunity with low cache and memory

if (unlikely(wake_flags & WF_EXEC))

return prev_cpu;

s32 cpu;

struct task_struct **ddsp_taskp;

cpu = SCX_CALL_OP_TASK_RET(SCX_KF_ENQUEUE | SCX_KF_SELECT_CPU,

select_cpu, p, prev_cpu, wake_flags);

*ddsp_taskp = NULL;

if (ops_cpu_valid(cpu, "from ops.select_cpu()"))

return cpu;

else

return prev_cpu;

} else {

s32 cpu;

p->scx.slice = SCX_SLICE_DFL;

p->scx.ddsp_dsq_id = SCX_DSQ_LOCAL;

}

return cpu;

}

}

(struct cpumask *)p->cpus_ptr);

}

static void handle_hotplug(struct rq *rq, bool online)

{

int cpu = cpu_of(rq);

atomic_long_inc(&scx_hotplug_seq);

if (scx_enabled())

if (online && SCX_HAS_OP(cpu_online))

SCX_CALL_OP(SCX_KF_UNLOCKED, cpu_online, cpu);

rq->scx.flags &= ~SCX_RQ_ONLINE;

}

#endif /* CONFIG_SMP */

static bool check_rq_for_timeouts(struct rq *rq)

curr->scx.slice = 0;

touch_core_sched(rq, curr);

} else if (SCX_HAS_OP(tick)) {

}

if (!curr->scx.slice)

WARN_ON_ONCE(scx_get_task_state(p) != SCX_TASK_ENABLED);

if (SCX_HAS_OP(disable))

scx_set_task_state(p, SCX_TASK_READY);

}

}

if (SCX_HAS_OP(exit_task))

scx_set_task_state(p, SCX_TASK_NONE);

}

return ops_sanitize_err("cgroup_prep_move", ret);

}

{

if (!scx_cgroup_enabled)

return;

/*

* @p must have ops.cgroup_prep_move() called on it and thus

* cgrp_moving_from set.

*/

cgroup_warned_missing_idle = false;

/*

* cgroups and init, all online cgroups are initialized.

*/

rcu_read_lock();

}

SCX_ATTR(ops);

static struct attribute *scx_sched_attrs[] = {

&scx_attr_ops.attr,

NULL,

};

ATTRIBUTE_GROUPS(scx_sched);

/**

* scx_softlockup - sched_ext softlockup handler

*

* On some multi-socket setups (e.g. 2x Intel 8480c), the BPF scheduler can

* live-lock the system by making many CPUs target the same DSQ to the point

/**

* scx_ops_bypass - [Un]bypass scx_ops and guarantee forward progress

*

* Bypassing guarantees that all runnable tasks make forward progress without

* trusting the BPF scheduler. We can't grab any mutexes or rwsems as they might

static void scx_ops_bypass(bool bypass)

{

static DEFINE_RAW_SPINLOCK(bypass_lock);

int cpu;

unsigned long flags;

WARN_ON_ONCE(scx_ops_bypass_depth <= 0);

if (scx_ops_bypass_depth != 1)

goto unlock;

} else {

scx_ops_bypass_depth--;

WARN_ON_ONCE(scx_ops_bypass_depth < 0);

if (scx_ops_bypass_depth != 0)

goto unlock;

}

atomic_inc(&scx_ops_breather_depth);

struct task_struct *p;

struct rhashtable_iter rht_iter;

struct scx_dispatch_q *dsq;

kind = atomic_read(&scx_exit_kind);

while (true) {

scx_task_iter_stop(&sti);

percpu_up_write(&scx_fork_rwsem);

/* no task is on scx, turn off all the switches and flush in-progress calls */

static_branch_disable(&__scx_ops_enabled);

for (i = SCX_OPI_BEGIN; i < SCX_OPI_END; i++)

static_branch_disable(&scx_has_op[i]);

static_branch_disable(&scx_ops_enq_last);

static_branch_disable(&scx_ops_enq_exiting);

static_branch_disable(&scx_ops_cpu_preempt);

synchronize_rcu();

if (ei->kind >= SCX_EXIT_ERROR) {

scx_get_task_state(p), p->scx.flags & ~SCX_TASK_STATE_MASK,

p->scx.dsq_flags, ops_state & SCX_OPSS_STATE_MASK,

ops_state >> SCX_OPSS_QSEQ_SHIFT);

dump_line(s, " cpus=%*pb", cpumask_pr_args(p->cpus_ptr));

if (SCX_HAS_OP(dump_task)) {

.at_jiffies = jiffies,

};

struct seq_buf s;

unsigned long flags;

char *buf;

int cpu;

rq_unlock(rq, &rf);

}

if (seq_buf_has_overflowed(&s) && dump_len >= sizeof(trunc_marker))

memcpy(ei->dump + dump_len - sizeof(trunc_marker),

trunc_marker, sizeof(trunc_marker));

{

struct kthread_worker *helper;

if (helper)

sched_set_fifo(helper->task);

return helper;

return -EINVAL;

}

return 0;

}

mutex_lock(&scx_ops_enable_mutex);

if (!scx_ops_helper) {

WRITE_ONCE(scx_ops_helper,

scx_create_rt_helper("sched_ext_ops_helper"));

static_branch_enable_cpuslocked(&scx_has_op[i]);

check_hotplug_seq(ops);

cpus_read_unlock();

ret = validate_ops(ops);

if (((void (**)(void))ops)[i])

static_branch_enable(&scx_has_op[i]);

if (ops->flags & SCX_OPS_ENQ_LAST)

static_branch_enable(&scx_ops_enq_last);

if (ops->flags & SCX_OPS_ENQ_EXITING)

static_branch_enable(&scx_ops_enq_exiting);

if (scx_ops.cpu_acquire || scx_ops.cpu_release)

static_branch_enable(&scx_ops_cpu_preempt);

/*

* Lock out forks, cgroup on/offlining and moves before opening the

SCX_TG_ONLINE);

BUG_ON(rhashtable_init(&dsq_hash, &dsq_hash_params));

scx_kick_cpus_pnt_seqs =

__alloc_percpu(sizeof(scx_kick_cpus_pnt_seqs[0]) * nr_cpu_ids,

__alignof__(scx_kick_cpus_pnt_seqs[0]));

for_each_possible_cpu(cpu) {

struct rq *rq = cpu_rq(cpu);

init_dsq(&rq->scx.local_dsq, SCX_DSQ_LOCAL);

INIT_LIST_HEAD(&rq->scx.runnable_list);

INIT_LIST_HEAD(&rq->scx.ddsp_deferred_locals);

init_irq_work(&rq->scx.deferred_irq_work, deferred_irq_workfn);

init_irq_work(&rq->scx.kick_cpus_irq_work, kick_cpus_irq_workfn);

/********************************************************************************

* Helpers that can be called from the BPF scheduler.

*/

static bool scx_dsq_insert_preamble(struct task_struct *p, u64 enq_flags)

{

if (!scx_kf_allowed(SCX_KF_ENQUEUE | SCX_KF_DISPATCH))

* ops.select_cpu(), and ops.dispatch().

*

* When called from ops.select_cpu() or ops.enqueue(), it's for direct dispatch

*

* When called from ops.select_cpu(), @enq_flags and @dsp_id are stored, and @p

* will be directly inserted into the corresponding dispatch queue after

* CPUs disagree, they use %ENQUEUE_RESTORE which is bypassed to

* the current local DSQ for running tasks and thus are not

* visible to the BPF scheduler.

*/

continue;

dispatch_dequeue(rq, p);

}

/**

* @fmt: format string

* @data: format string parameters packaged using ___bpf_fill() macro

* @data__sz: @data len, must end in '__sz' for the verifier

* scx_bpf_cpuperf_set - Set the relative performance target of a CPU

* @cpu: CPU of interest

* @perf: target performance level [0, %SCX_CPUPERF_ONE]

*

* Set the target performance level of @cpu to @perf. @perf is in linear

* relative scale between 0 and %SCX_CPUPERF_ONE. This determines how the

}

/**

* scx_bpf_nr_cpu_ids - Return the number of possible CPU IDs

*

* All valid CPU IDs in the system are smaller than the returned value.

}

/**

* scx_bpf_task_running - Is task currently running?

* @p: task of interest

*/

}

#endif

__bpf_kfunc_end_defs();

BTF_KFUNCS_START(scx_kfunc_ids_any)

BTF_ID_FLAGS(func, scx_bpf_cpuperf_cap)

BTF_ID_FLAGS(func, scx_bpf_cpuperf_cur)

BTF_ID_FLAGS(func, scx_bpf_cpuperf_set)

BTF_ID_FLAGS(func, scx_bpf_nr_cpu_ids)

BTF_ID_FLAGS(func, scx_bpf_get_possible_cpumask, KF_ACQUIRE)

BTF_ID_FLAGS(func, scx_bpf_get_online_cpumask, KF_ACQUIRE)

#ifdef CONFIG_CGROUP_SCHED

BTF_ID_FLAGS(func, scx_bpf_task_cgroup, KF_RCU | KF_ACQUIRE)

#endif

BTF_KFUNCS_END(scx_kfunc_ids_any)

static const struct btf_kfunc_id_set scx_kfunc_set_any = {

* check using scx_kf_allowed().

*/

if ((ret = register_btf_kfunc_id_set(BPF_PROG_TYPE_STRUCT_OPS,

&scx_kfunc_set_enqueue_dispatch)) ||

(ret = register_btf_kfunc_id_set(BPF_PROG_TYPE_STRUCT_OPS,

&scx_kfunc_set_dispatch)) ||

return ret;

}

ret = register_bpf_struct_ops(&bpf_sched_ext_ops, sched_ext_ops);

if (ret) {

pr_err("sched_ext: Failed to register struct_ops (%d)\n", ret);