/* SPDX-License-Identifier: GPL-2.0 */

/*

* BPF extensible scheduler class: Documentation/scheduler/sched-ext.rst

*

* Copyright (c) 2022 Meta Platforms, Inc. and affiliates.

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

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

*/

#include <linux/btf_ids.h>

#include "ext_idle.h"

static DEFINE_RAW_SPINLOCK(scx_sched_lock);

/*

* NOTE: sched_ext is in the process of growing multiple scheduler support and

* scx_root usage is in a transitional state. Naked dereferences are safe if the

* caller is one of the tasks attached to SCX and explicit RCU dereference is

* necessary otherwise. Naked scx_root dereferences trigger sparse warnings but

* are used as temporary markers to indicate that the dereferences need to be

* updated to point to the associated scheduler instances rather than scx_root.

*/

struct scx_sched __rcu *scx_root;

/*

* All scheds, writers must hold both scx_enable_mutex and scx_sched_lock.

* Readers can hold either or rcu_read_lock().

*/

static LIST_HEAD(scx_sched_all);

#ifdef CONFIG_EXT_SUB_SCHED

static const struct rhashtable_params scx_sched_hash_params = {

.key_len = sizeof_field(struct scx_sched, ops.sub_cgroup_id),

.key_offset = offsetof(struct scx_sched, ops.sub_cgroup_id),

.head_offset = offsetof(struct scx_sched, hash_node),

.insecure_elasticity = true, /* inserted under scx_sched_lock */

};

static struct rhashtable scx_sched_hash;

#endif

/*

* During exit, a task may schedule after losing its PIDs. When disabling the

* BPF scheduler, we need to be able to iterate tasks in every state to

* guarantee system safety. Maintain a dedicated task list which contains every

* task between its fork and eventual free.

*/

static DEFINE_RAW_SPINLOCK(scx_tasks_lock);

static LIST_HEAD(scx_tasks);

/* ops enable/disable */

static DEFINE_MUTEX(scx_enable_mutex);

DEFINE_STATIC_KEY_FALSE(__scx_enabled);

DEFINE_STATIC_PERCPU_RWSEM(scx_fork_rwsem);

static atomic_t scx_enable_state_var = ATOMIC_INIT(SCX_DISABLED);

static DEFINE_RAW_SPINLOCK(scx_bypass_lock);

static bool scx_init_task_enabled;

static bool scx_switching_all;

DEFINE_STATIC_KEY_FALSE(__scx_switched_all);

static atomic_long_t scx_nr_rejected = ATOMIC_LONG_INIT(0);

static atomic_long_t scx_hotplug_seq = ATOMIC_LONG_INIT(0);

#ifdef CONFIG_EXT_SUB_SCHED

/*

* The sub sched being enabled. Used by scx_disable_and_exit_task() to exit

* tasks for the sub-sched being enabled. Use a global variable instead of a

* per-task field as all enables are serialized.

*/

static struct scx_sched *scx_enabling_sub_sched;

#else

#define scx_enabling_sub_sched (struct scx_sched *)NULL

#endif /* CONFIG_EXT_SUB_SCHED */

/*

* A monotonically increasing sequence number that is incremented every time a

* scheduler is enabled. This can be used to check if any custom sched_ext

* scheduler has ever been used in the system.

*/

static atomic_long_t scx_enable_seq = ATOMIC_LONG_INIT(0);

/*

* Watchdog interval. All scx_sched's share a single watchdog timer and the

* interval is half of the shortest sch->watchdog_timeout.

*/

static unsigned long scx_watchdog_interval;

/*

* The last time the delayed work was run. This delayed work relies on

* ksoftirqd being able to run to service timer interrupts, so it's possible

* that this work itself could get wedged. To account for this, we check that

* it's not stalled in the timer tick, and trigger an error if it is.

*/

static unsigned long scx_watchdog_timestamp = INITIAL_JIFFIES;

static struct delayed_work scx_watchdog_work;

/*

* For %SCX_KICK_WAIT: Each CPU has a pointer to an array of kick_sync sequence

* numbers. The arrays are allocated with kvzalloc() as size can exceed percpu

* allocator limits on large machines. O(nr_cpu_ids^2) allocation, allocated

* lazily when enabling and freed when disabling to avoid waste when sched_ext

* isn't active.

*/

struct scx_kick_syncs {

struct rcu_head rcu;

unsigned long syncs[];

};

static DEFINE_PER_CPU(struct scx_kick_syncs __rcu *, scx_kick_syncs);

/*

* Direct dispatch marker.

*

* Non-NULL values are used for direct dispatch from enqueue path. A valid

* pointer points to the task currently being enqueued. An ERR_PTR value is used

* to indicate that direct dispatch has already happened.

*/

static DEFINE_PER_CPU(struct task_struct *, direct_dispatch_task);

static const struct rhashtable_params dsq_hash_params = {

.key_len = sizeof_field(struct scx_dispatch_q, id),

.key_offset = offsetof(struct scx_dispatch_q, id),

.head_offset = offsetof(struct scx_dispatch_q, hash_node),

};

static LLIST_HEAD(dsqs_to_free);

/* string formatting from BPF */

struct scx_bstr_buf {

u64 data[MAX_BPRINTF_VARARGS];

char line[SCX_EXIT_MSG_LEN];

};

static DEFINE_RAW_SPINLOCK(scx_exit_bstr_buf_lock);

static struct scx_bstr_buf scx_exit_bstr_buf;

/* ops debug dump */

static DEFINE_RAW_SPINLOCK(scx_dump_lock);

struct scx_dump_data {

s32 cpu;

bool first;

s32 cursor;

struct seq_buf *s;

const char *prefix;

struct scx_bstr_buf buf;

};

static struct scx_dump_data scx_dump_data = {

.cpu = -1,

};

/* /sys/kernel/sched_ext interface */

static struct kset *scx_kset;

/*

* Parameters that can be adjusted through /sys/module/sched_ext/parameters.

* There usually is no reason to modify these as normal scheduler operation

* shouldn't be affected by them. The knobs are primarily for debugging.

*/

static unsigned int scx_slice_bypass_us = SCX_SLICE_BYPASS / NSEC_PER_USEC;

static unsigned int scx_bypass_lb_intv_us = SCX_BYPASS_LB_DFL_INTV_US;

static int set_slice_us(const char *val, const struct kernel_param *kp)

{

return param_set_uint_minmax(val, kp, 100, 100 * USEC_PER_MSEC);

}

static const struct kernel_param_ops slice_us_param_ops = {

.set = set_slice_us,

.get = param_get_uint,

};

static int set_bypass_lb_intv_us(const char *val, const struct kernel_param *kp)

{

return param_set_uint_minmax(val, kp, 0, 10 * USEC_PER_SEC);

}

static const struct kernel_param_ops bypass_lb_intv_us_param_ops = {

.set = set_bypass_lb_intv_us,

.get = param_get_uint,

};

#undef MODULE_PARAM_PREFIX

#define MODULE_PARAM_PREFIX "sched_ext."

module_param_cb(slice_bypass_us, &slice_us_param_ops, &scx_slice_bypass_us, 0600);

MODULE_PARM_DESC(slice_bypass_us, "bypass slice in microseconds, applied on [un]load (100us to 100ms)");

module_param_cb(bypass_lb_intv_us, &bypass_lb_intv_us_param_ops, &scx_bypass_lb_intv_us, 0600);

MODULE_PARM_DESC(bypass_lb_intv_us, "bypass load balance interval in microseconds (0 (disable) to 10s)");

#undef MODULE_PARAM_PREFIX

#define CREATE_TRACE_POINTS

#include <trace/events/sched_ext.h>

static void run_deferred(struct rq *rq);

static bool task_dead_and_done(struct task_struct *p);

static void scx_kick_cpu(struct scx_sched *sch, s32 cpu, u64 flags);

static void scx_disable(struct scx_sched *sch, enum scx_exit_kind kind);

static bool scx_vexit(struct scx_sched *sch, enum scx_exit_kind kind,

s64 exit_code, const char *fmt, va_list args);

static __printf(4, 5) bool scx_exit(struct scx_sched *sch,

enum scx_exit_kind kind, s64 exit_code,

const char *fmt, ...)

{

va_list args;

bool ret;

va_start(args, fmt);

ret = scx_vexit(sch, kind, exit_code, fmt, args);

va_end(args);

return ret;

}

#define scx_error(sch, fmt, args...) scx_exit((sch), SCX_EXIT_ERROR, 0, fmt, ##args)

#define scx_verror(sch, fmt, args) scx_vexit((sch), SCX_EXIT_ERROR, 0, fmt, args)

#define SCX_HAS_OP(sch, op) test_bit(SCX_OP_IDX(op), (sch)->has_op)

static long jiffies_delta_msecs(unsigned long at, unsigned long now)

{

if (time_after(at, now))

return jiffies_to_msecs(at - now);

else

return -(long)jiffies_to_msecs(now - at);

}

static bool u32_before(u32 a, u32 b)

{

return (s32)(a - b) < 0;

}

#ifdef CONFIG_EXT_SUB_SCHED

/**

* scx_parent - Find the parent sched

* @sch: sched to find the parent of

*

* Returns the parent scheduler or %NULL if @sch is root.

*/

static struct scx_sched *scx_parent(struct scx_sched *sch)

{

if (sch->level)

return sch->ancestors[sch->level - 1];

else

return NULL;

}

/**

* scx_next_descendant_pre - find the next descendant for pre-order walk

* @pos: the current position (%NULL to initiate traversal)

* @root: sched whose descendants to walk

*

* To be used by scx_for_each_descendant_pre(). Find the next descendant to

* visit for pre-order traversal of @root's descendants. @root is included in

* the iteration and the first node to be visited.

*/

static struct scx_sched *scx_next_descendant_pre(struct scx_sched *pos,

struct scx_sched *root)

{

struct scx_sched *next;

lockdep_assert(lockdep_is_held(&scx_enable_mutex) ||

lockdep_is_held(&scx_sched_lock));

/* if first iteration, visit @root */

if (!pos)

return root;

/* visit the first child if exists */

next = list_first_entry_or_null(&pos->children, struct scx_sched, sibling);

if (next)

return next;

/* no child, visit my or the closest ancestor's next sibling */

while (pos != root) {

if (!list_is_last(&pos->sibling, &scx_parent(pos)->children))

return list_next_entry(pos, sibling);

pos = scx_parent(pos);

}

return NULL;

}

static struct scx_sched *scx_find_sub_sched(u64 cgroup_id)

{

return rhashtable_lookup(&scx_sched_hash, &cgroup_id,

scx_sched_hash_params);

}

static void scx_set_task_sched(struct task_struct *p, struct scx_sched *sch)

{

rcu_assign_pointer(p->scx.sched, sch);

}

#else /* CONFIG_EXT_SUB_SCHED */

static struct scx_sched *scx_parent(struct scx_sched *sch) { return NULL; }

static struct scx_sched *scx_next_descendant_pre(struct scx_sched *pos, struct scx_sched *root) { return pos ? NULL : root; }

static struct scx_sched *scx_find_sub_sched(u64 cgroup_id) { return NULL; }

static void scx_set_task_sched(struct task_struct *p, struct scx_sched *sch) {}

#endif /* CONFIG_EXT_SUB_SCHED */

/**

* scx_is_descendant - Test whether sched is a descendant

* @sch: sched to test

* @ancestor: ancestor sched to test against

*

* Test whether @sch is a descendant of @ancestor.

*/

static bool scx_is_descendant(struct scx_sched *sch, struct scx_sched *ancestor)

{

if (sch->level < ancestor->level)

return false;

return sch->ancestors[ancestor->level] == ancestor;

}

/**

* scx_for_each_descendant_pre - pre-order walk of a sched's descendants

* @pos: iteration cursor

* @root: sched to walk the descendants of

*

* Walk @root's descendants. @root is included in the iteration and the first

* node to be visited. Must be called with either scx_enable_mutex or

* scx_sched_lock held.

*/

#define scx_for_each_descendant_pre(pos, root) \

for ((pos) = scx_next_descendant_pre(NULL, (root)); (pos); \

(pos) = scx_next_descendant_pre((pos), (root)))

static struct scx_dispatch_q *find_global_dsq(struct scx_sched *sch, s32 cpu)

{

return &sch->pnode[cpu_to_node(cpu)]->global_dsq;

}

static struct scx_dispatch_q *find_user_dsq(struct scx_sched *sch, u64 dsq_id)

{

return rhashtable_lookup(&sch->dsq_hash, &dsq_id, dsq_hash_params);

}

static const struct sched_class *scx_setscheduler_class(struct task_struct *p)

{

if (p->sched_class == &stop_sched_class)

return &stop_sched_class;

return __setscheduler_class(p->policy, p->prio);

}

static struct scx_dispatch_q *bypass_dsq(struct scx_sched *sch, s32 cpu)

{

return &per_cpu_ptr(sch->pcpu, cpu)->bypass_dsq;

}

static struct scx_dispatch_q *bypass_enq_target_dsq(struct scx_sched *sch, s32 cpu)

{

#ifdef CONFIG_EXT_SUB_SCHED

/*

* 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

* not-bypassing ancestor is responsible for scheduling all tasks from

* bypassing sub-trees. If all ancestors including root are bypassing,

* all tasks should go to the root's bypass DSQs.

*

* 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 bypass_dsq(sch, cpu);

}

/**

* bypass_dsp_enabled - Check if bypass dispatch path is enabled

* @sch: scheduler to check

*

* When a descendant scheduler enters bypass mode, bypassed tasks are scheduled

* by the nearest non-bypassing ancestor, or the root scheduler if all ancestors

* are bypassing. In the former case, the ancestor is not itself bypassing but

* its bypass DSQs will be populated with bypassed tasks from descendants. Thus,

* the ancestor's bypass dispatch path must be active even though its own

* bypass_depth remains zero.

*

* This function checks bypass_dsp_enable_depth which is managed separately from

* bypass_depth to enable this decoupling. See enable_bypass_dsp() and

* disable_bypass_dsp().

*/

static bool bypass_dsp_enabled(struct scx_sched *sch)

{

return unlikely(atomic_read(&sch->bypass_dsp_enable_depth));

}

/**

* rq_is_open - Is the rq available for immediate execution of an SCX task?

* @rq: rq to test

* @enq_flags: optional %SCX_ENQ_* of the task being enqueued

*

* Returns %true if @rq is currently open for executing an SCX task. After a

* %false return, @rq is guaranteed to invoke SCX dispatch path at least once

* before going to idle and not inserting a task into @rq's local DSQ after a

* %false return doesn't cause @rq to stall.

*/

static bool rq_is_open(struct rq *rq, u64 enq_flags)

{

lockdep_assert_rq_held(rq);

/*

* A higher-priority class task is either running or in the process of

* waking up on @rq.

*/

if (sched_class_above(rq->next_class, &ext_sched_class))

return false;

/*

* @rq is either in transition to or in idle and there is no

* higher-priority class task waking up on it.

*/

if (sched_class_above(&ext_sched_class, rq->next_class))

return true;

/*

* @rq is either picking, in transition to, or running an SCX task.

*/

/*

* If we're in the dispatch path holding rq lock, $curr may or may not

* be ready depending on whether the on-going dispatch decides to extend

* $curr's slice. We say yes here and resolve it at the end of dispatch.

* See balance_one().

*/

if (rq->scx.flags & SCX_RQ_IN_BALANCE)

return true;

/*

* %SCX_ENQ_PREEMPT clears $curr's slice if on SCX and kicks dispatch,

* so allow it to avoid spuriously triggering reenq on a combined

* PREEMPT|IMMED insertion.

*/

if (enq_flags & SCX_ENQ_PREEMPT)

return true;

/*

* @rq is either in transition to or running an SCX task and can't go

* idle without another SCX dispatch cycle.

*/

return false;

}

/*

* Track the rq currently locked.

*

* This allows kfuncs to safely operate on rq from any scx ops callback,

* knowing which rq is already locked.

*/

DEFINE_PER_CPU(struct rq *, scx_locked_rq_state);

static inline void update_locked_rq(struct rq *rq)

{

/*

* Check whether @rq is actually locked. This can help expose bugs

* or incorrect assumptions about the context in which a kfunc or

* callback is executed.

*/

if (rq)

lockdep_assert_rq_held(rq);

__this_cpu_write(scx_locked_rq_state, rq);

}

/*

* SCX ops can recurse via scx_bpf_sub_dispatch() - the inner call must not

* clobber the outer's scx_locked_rq_state. Save it on entry, restore on exit.

*/

#define SCX_CALL_OP(sch, op, locked_rq, args...) \

do { \

struct rq *__prev_locked_rq; \

\

if (locked_rq) { \

__prev_locked_rq = scx_locked_rq(); \

update_locked_rq(locked_rq); \

} \

(sch)->ops.op(args); \

if (locked_rq) \

update_locked_rq(__prev_locked_rq); \

} while (0)

#define SCX_CALL_OP_RET(sch, op, locked_rq, args...) \

({ \

struct rq *__prev_locked_rq; \

__typeof__((sch)->ops.op(args)) __ret; \

\

if (locked_rq) { \

__prev_locked_rq = scx_locked_rq(); \

update_locked_rq(locked_rq); \

} \

__ret = (sch)->ops.op(args); \

if (locked_rq) \

update_locked_rq(__prev_locked_rq); \

__ret; \

})

/*

* SCX_CALL_OP_TASK*() invokes an SCX op that takes one or two task arguments

* and records them in current->scx.kf_tasks[] for the duration of the call. A

* kfunc invoked from inside such an op can then use

* scx_kf_arg_task_ok() to verify that its task argument is one of

* those subject tasks.

*

* Every SCX_CALL_OP_TASK*() call site invokes its op with @p's rq lock held -

* either via the @locked_rq argument here, or (for ops.select_cpu()) via @p's

* pi_lock held by try_to_wake_up() with rq tracking via scx_rq.in_select_cpu.

* So if kf_tasks[] is set, @p's scheduler-protected fields are stable.

*

* kf_tasks[] can not stack, so task-based SCX ops must not nest. The

* WARN_ON_ONCE() in each macro catches a re-entry of any of the three variants

* while a previous one is still in progress.

*/

#define SCX_CALL_OP_TASK(sch, op, locked_rq, task, args...) \

do { \

WARN_ON_ONCE(current->scx.kf_tasks[0]); \

current->scx.kf_tasks[0] = task; \

SCX_CALL_OP((sch), op, locked_rq, task, ##args); \

current->scx.kf_tasks[0] = NULL; \

} while (0)

#define SCX_CALL_OP_TASK_RET(sch, op, locked_rq, task, args...) \

({ \

__typeof__((sch)->ops.op(task, ##args)) __ret; \

WARN_ON_ONCE(current->scx.kf_tasks[0]); \

current->scx.kf_tasks[0] = task; \

__ret = SCX_CALL_OP_RET((sch), op, locked_rq, task, ##args); \

current->scx.kf_tasks[0] = NULL; \

__ret; \

})

#define SCX_CALL_OP_2TASKS_RET(sch, op, locked_rq, task0, task1, args...) \

({ \

__typeof__((sch)->ops.op(task0, task1, ##args)) __ret; \

WARN_ON_ONCE(current->scx.kf_tasks[0]); \

current->scx.kf_tasks[0] = task0; \

current->scx.kf_tasks[1] = task1; \

__ret = SCX_CALL_OP_RET((sch), op, locked_rq, task0, task1, ##args); \

current->scx.kf_tasks[0] = NULL; \

current->scx.kf_tasks[1] = NULL; \

__ret; \

})

/* see SCX_CALL_OP_TASK() */

static __always_inline bool scx_kf_arg_task_ok(struct scx_sched *sch,

struct task_struct *p)

{

if (unlikely((p != current->scx.kf_tasks[0] &&

p != current->scx.kf_tasks[1]))) {

scx_error(sch, "called on a task not being operated on");

return false;

}

return true;

}

enum scx_dsq_iter_flags {

/* iterate in the reverse dispatch order */

SCX_DSQ_ITER_REV = 1U << 16,

__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_SLICE |

__SCX_DSQ_ITER_HAS_VTIME,

};

/**

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

* @dsq: non-local dsq being iterated

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

* @rev: walk backwards

*

* Returns %NULL when iteration is finished.

*/

static struct task_struct *nldsq_next_task(struct scx_dispatch_q *dsq,

struct task_struct *cur, bool rev)

{

struct list_head *list_node;

struct scx_dsq_list_node *dsq_lnode;

lockdep_assert_held(&dsq->lock);

if (cur)

list_node = &cur->scx.dsq_list.node;

else

list_node = &dsq->list;

/* find the next task, need to skip BPF iteration cursors */

do {

if (rev)

list_node = list_node->prev;

else

list_node = list_node->next;

if (list_node == &dsq->list)

return NULL;

dsq_lnode = container_of(list_node, struct scx_dsq_list_node,

node);

} while (dsq_lnode->flags & SCX_DSQ_LNODE_ITER_CURSOR);

return container_of(dsq_lnode, struct task_struct, scx.dsq_list);

}

#define nldsq_for_each_task(p, dsq) \

for ((p) = nldsq_next_task((dsq), NULL, false); (p); \

(p) = nldsq_next_task((dsq), (p), false))

/**

* nldsq_cursor_next_task - Iterate to the next task given a cursor in a non-local DSQ

* @cursor: scx_dsq_list_node initialized with INIT_DSQ_LIST_CURSOR()

* @dsq: non-local dsq being iterated

*

* Find the next task in a cursor based iteration. The caller must have

* initialized @cursor using INIT_DSQ_LIST_CURSOR() and can release the DSQ lock

* between the iteration steps.

*

* Only tasks which were queued before @cursor was initialized are visible. This

* bounds the iteration and guarantees that vtime never jumps in the other

* direction while iterating.

*/

static struct task_struct *nldsq_cursor_next_task(struct scx_dsq_list_node *cursor,

struct scx_dispatch_q *dsq)

{

bool rev = cursor->flags & SCX_DSQ_ITER_REV;

struct task_struct *p;

lockdep_assert_held(&dsq->lock);

BUG_ON(!(cursor->flags & SCX_DSQ_LNODE_ITER_CURSOR));

if (list_empty(&cursor->node))

p = NULL;

else

p = container_of(cursor, struct task_struct, scx.dsq_list);

/* skip cursors and tasks that were queued after @cursor init */

do {

p = nldsq_next_task(dsq, p, rev);

} while (p && unlikely(u32_before(cursor->priv, p->scx.dsq_seq)));

if (p) {

if (rev)

list_move_tail(&cursor->node, &p->scx.dsq_list.node);

else

list_move(&cursor->node, &p->scx.dsq_list.node);

} else {

list_del_init(&cursor->node);

}

return p;

}

/**

* nldsq_cursor_lost_task - Test whether someone else took the task since iteration

* @cursor: scx_dsq_list_node initialized with INIT_DSQ_LIST_CURSOR()

* @rq: rq @p was on

* @dsq: dsq @p was on

* @p: target task

*

* @p is a task returned by nldsq_cursor_next_task(). The locks may have been

* dropped and re-acquired inbetween. Verify that no one else took or is in the

* process of taking @p from @dsq.

*

* On %false return, the caller can assume full ownership of @p.

*/

static bool nldsq_cursor_lost_task(struct scx_dsq_list_node *cursor,

struct rq *rq, struct scx_dispatch_q *dsq,

struct task_struct *p)

{

lockdep_assert_rq_held(rq);

lockdep_assert_held(&dsq->lock);

/*

* @p could have already left $src_dsq, got re-enqueud, or be in the

* process of being consumed by someone else.

*/

if (unlikely(p->scx.dsq != dsq ||

u32_before(cursor->priv, p->scx.dsq_seq) ||

p->scx.holding_cpu >= 0))

return true;

/* if @p has stayed on @dsq, its rq couldn't have changed */

if (WARN_ON_ONCE(rq != task_rq(p)))

return true;

return false;

}

/*

* BPF DSQ iterator. Tasks in a non-local DSQ can be iterated in [reverse]

* dispatch order. BPF-visible iterator is opaque and larger to allow future

* changes without breaking backward compatibility. Can be used with

* bpf_for_each(). See bpf_iter_scx_dsq_*().

*/

struct bpf_iter_scx_dsq_kern {

struct scx_dsq_list_node cursor;

struct scx_dispatch_q *dsq;

u64 slice;

u64 vtime;

} __attribute__((aligned(8)));

struct bpf_iter_scx_dsq {

u64 __opaque[6];

} __attribute__((aligned(8)));

/*

* SCX task iterator.

*/

struct scx_task_iter {

struct sched_ext_entity cursor;

struct task_struct *locked_task;

struct rq *rq;

struct rq_flags rf;

u32 cnt;

bool list_locked;

#ifdef CONFIG_EXT_SUB_SCHED

struct cgroup *cgrp;

struct cgroup_subsys_state *css_pos;

struct css_task_iter css_iter;

#endif

};

/**

* scx_task_iter_start - Lock scx_tasks_lock and start a task iteration

* @iter: iterator to init

* @cgrp: Optional root of cgroup subhierarchy to iterate

*

* Initialize @iter. Once initialized, @iter must eventually be stopped with

* scx_task_iter_stop().

*

* If @cgrp is %NULL, scx_tasks is used for iteration and this function returns

* with scx_tasks_lock held and @iter->cursor inserted into scx_tasks.

*

* If @cgrp is not %NULL, @cgrp and its descendants' tasks are walked using

* @iter->css_iter. The caller must be holding cgroup_lock() to prevent cgroup

* task migrations.

*

* The two modes of iterations are largely independent and it's likely that

* scx_tasks can be removed in favor of always using cgroup iteration if

* CONFIG_SCHED_CLASS_EXT depends on CONFIG_CGROUPS.

*

* scx_tasks_lock and the rq lock may be released using scx_task_iter_unlock()

* between this and the first next() call or between any two next() calls. If

* the locks are released between two next() calls, the caller is responsible

* for ensuring that the task being iterated remains accessible either through

* RCU read lock or obtaining a reference count.

*

* All tasks which existed when the iteration started are guaranteed to be

* visited as long as they are not dead.

*/

static void scx_task_iter_start(struct scx_task_iter *iter, struct cgroup *cgrp)

{

memset(iter, 0, sizeof(*iter));

#ifdef CONFIG_EXT_SUB_SCHED

if (cgrp) {

lockdep_assert_held(&cgroup_mutex);

iter->cgrp = cgrp;

iter->css_pos = css_next_descendant_pre(NULL, &iter->cgrp->self);

css_task_iter_start(iter->css_pos, 0, &iter->css_iter);

return;

}

#endif

raw_spin_lock_irq(&scx_tasks_lock);

iter->cursor = (struct sched_ext_entity){ .flags = SCX_TASK_CURSOR };

list_add(&iter->cursor.tasks_node, &scx_tasks);

iter->list_locked = true;

}

static void __scx_task_iter_rq_unlock(struct scx_task_iter *iter)

{

if (iter->locked_task) {

__balance_callbacks(iter->rq, &iter->rf);

task_rq_unlock(iter->rq, iter->locked_task, &iter->rf);

iter->locked_task = NULL;

}

}

/**

* scx_task_iter_unlock - Unlock rq and scx_tasks_lock held by a task iterator

* @iter: iterator to unlock

*

* If @iter is in the middle of a locked iteration, it may be locking the rq of

* the task currently being visited in addition to scx_tasks_lock. Unlock both.

* This function can be safely called anytime during an iteration. The next

* iterator operation will automatically restore the necessary locking.

*/

static void scx_task_iter_unlock(struct scx_task_iter *iter)

{

__scx_task_iter_rq_unlock(iter);

if (iter->list_locked) {

iter->list_locked = false;

raw_spin_unlock_irq(&scx_tasks_lock);

}

}

static void __scx_task_iter_maybe_relock(struct scx_task_iter *iter)

{

if (!iter->list_locked) {

raw_spin_lock_irq(&scx_tasks_lock);

iter->list_locked = true;

}

}

/**

* scx_task_iter_stop - Stop a task iteration and unlock scx_tasks_lock

* @iter: iterator to exit

*

* Exit a previously initialized @iter. Must be called with scx_tasks_lock held

* which is released on return. If the iterator holds a task's rq lock, that rq

* lock is also released. See scx_task_iter_start() for details.

*/

static void scx_task_iter_stop(struct scx_task_iter *iter)

{

#ifdef CONFIG_EXT_SUB_SCHED

if (iter->cgrp) {

if (iter->css_pos)

css_task_iter_end(&iter->css_iter);

__scx_task_iter_rq_unlock(iter);

return;

}

#endif

__scx_task_iter_maybe_relock(iter);

list_del_init(&iter->cursor.tasks_node);

scx_task_iter_unlock(iter);

}

/**

* scx_task_iter_next - Next task

* @iter: iterator to walk

*

* Visit the next task. See scx_task_iter_start() for details. Locks are dropped

* and re-acquired every %SCX_TASK_ITER_BATCH iterations to avoid causing stalls

* by holding scx_tasks_lock for too long.

*/

static struct task_struct *scx_task_iter_next(struct scx_task_iter *iter)

{

struct list_head *cursor = &iter->cursor.tasks_node;

struct sched_ext_entity *pos;

if (!(++iter->cnt % SCX_TASK_ITER_BATCH)) {

scx_task_iter_unlock(iter);

cond_resched();

}

#ifdef CONFIG_EXT_SUB_SCHED

if (iter->cgrp) {

while (iter->css_pos) {

struct task_struct *p;

p = css_task_iter_next(&iter->css_iter);

if (p)

return p;

css_task_iter_end(&iter->css_iter);

iter->css_pos = css_next_descendant_pre(iter->css_pos,

&iter->cgrp->self);

if (iter->css_pos)

css_task_iter_start(iter->css_pos, 0, &iter->css_iter);

}

return NULL;

}

#endif

__scx_task_iter_maybe_relock(iter);

list_for_each_entry(pos, cursor, tasks_node) {

if (&pos->tasks_node == &scx_tasks)

return NULL;

if (!(pos->flags & SCX_TASK_CURSOR)) {

list_move(cursor, &pos->tasks_node);

return container_of(pos, struct task_struct, scx);

}

}

/* can't happen, should always terminate at scx_tasks above */

BUG();

}

/**

* 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()

* for details.

*/

static struct task_struct *scx_task_iter_next_locked(struct scx_task_iter *iter)

{

struct task_struct *p;

__scx_task_iter_rq_unlock(iter);

while ((p = scx_task_iter_next(iter))) {

/*

* scx_task_iter is used to prepare and move tasks into SCX

* while loading the BPF scheduler and vice-versa while

* unloading. The init_tasks ("swappers") should be excluded

* from the iteration because:

*

* - It's unsafe to use __setschduler_prio() on an init_task to

* determine the sched_class to use as it won't preserve its

* idle_sched_class.

*

* - ops.init/exit_task() can easily be confused if called with

* init_tasks as they, e.g., share PID 0.

*

* As init_tasks are never scheduled through SCX, they can be

* skipped safely. Note that is_idle_task() which tests %PF_IDLE

* doesn't work here:

*

* - %PF_IDLE may not be set for an init_task whose CPU hasn't

* yet been onlined.

*

* - %PF_IDLE can be set on tasks that are not init_tasks. See

* play_idle_precise() used by CONFIG_IDLE_INJECT.

*

* Test for idle_sched_class as only init_tasks are on it.

*/

if (p->sched_class != &idle_sched_class)

break;

}

if (!p)

return NULL;

iter->rq = task_rq_lock(p, &iter->rf);

iter->locked_task = p;

return p;

}

/**

* scx_add_event - Increase an event counter for 'name' by 'cnt'

* @sch: scx_sched to account events for

* @name: an event name defined in struct scx_event_stats

* @cnt: the number of the event occurred

*

* This can be used when preemption is not disabled.

*/

#define scx_add_event(sch, name, cnt) do { \

this_cpu_add((sch)->pcpu->event_stats.name, (cnt)); \

trace_sched_ext_event(#name, (cnt)); \

} while(0)

/**

* __scx_add_event - Increase an event counter for 'name' by 'cnt'

* @sch: scx_sched to account events for

* @name: an event name defined in struct scx_event_stats

* @cnt: the number of the event occurred

*

* This should be used only when preemption is disabled.

*/

#define __scx_add_event(sch, name, cnt) do { \

__this_cpu_add((sch)->pcpu->event_stats.name, (cnt)); \

trace_sched_ext_event(#name, cnt); \

} while(0)

/**

* scx_agg_event - Aggregate an event counter 'kind' from 'src_e' to 'dst_e'

* @dst_e: destination event stats

* @src_e: source event stats

* @kind: a kind of event to be aggregated

*/

#define scx_agg_event(dst_e, src_e, kind) do { \

(dst_e)->kind += READ_ONCE((src_e)->kind); \

} while(0)

/**

* scx_dump_event - Dump an event 'kind' in 'events' to 's'

* @s: output seq_buf

* @events: event stats

* @kind: a kind of event to dump

*/

#define scx_dump_event(s, events, kind) do { \

dump_line(&(s), "%40s: %16lld", #kind, (events)->kind); \

} while (0)

static void scx_read_events(struct scx_sched *sch,

struct scx_event_stats *events);

static enum scx_enable_state scx_enable_state(void)

{

return atomic_read(&scx_enable_state_var);

}

static enum scx_enable_state scx_set_enable_state(enum scx_enable_state to)

{

return atomic_xchg(&scx_enable_state_var, to);

}