/* 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/bitmap.h>#include <linux/btf_ids.h>#include <linux/rhashtable.h>#include <linux/sched/clock.h>#include <linux/sched/isolation.h>#include <linux/suspend.h>#include <linux/sysrq.h> #include "../pelt.h"#include "internal.h"#include "cid.h"#include "arena.h"#include "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_SCHEDstatic 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 /* see SCX_OPS_TID_TO_TASK */static const struct rhashtable_params scx_tid_hash_params = {	.key_len		= sizeof_field(struct sched_ext_entity, tid),	.key_offset		= offsetof(struct sched_ext_entity, tid),	.head_offset		= offsetof(struct sched_ext_entity, tid_hash_node),	.insecure_elasticity	= true,	/* inserted/removed under scx_tasks_lock */};static struct rhashtable scx_tid_hash; /* * 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 DEFINE_STATIC_KEY_FALSE(__scx_tid_to_task_enabled); /* * True once SCX_OPS_TID_TO_TASK has been negotiated with the root scheduler * and the tid->task table is live. Wraps the static key so callers don't * take the address, and hints "likely enabled" for the common case where * the feature is in use. */static inline bool scx_tid_to_task_enabled(void){	return static_branch_likely(&__scx_tid_to_task_enabled);} static atomic_long_t scx_nr_rejected = ATOMIC_LONG_INIT(0);static atomic_long_t scx_hotplug_seq = ATOMIC_LONG_INIT(0); /* Global cursor for the per-CPU tid allocator. Starts at 1; tid 0 is reserved. */static atomic64_t scx_tid_cursor = ATOMIC64_INIT(1); #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); /* * Per-CPU buffered allocator state for p->scx.tid. Each CPU pulls a chunk of * SCX_TID_CHUNK ids from scx_tid_cursor and hands them out locally without * further synchronization. See scx_alloc_tid(). */struct scx_tid_alloc {	u64	next;	u64	end;};static DEFINE_PER_CPU(struct scx_tid_alloc, scx_tid_alloc); /* * 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); __printf(5, 6) bool __scx_exit(struct scx_sched *sch,			       enum scx_exit_kind kind, s64 exit_code,			       s32 exit_cpu, const char *fmt, ...){	va_list args;	bool ret; 	va_start(args, fmt);	ret = scx_vexit(sch, kind, exit_code, exit_cpu, fmt, args);	va_end(args); 	return ret;} 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_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 inline struct scx_sched *scx_next_descendant_pre(struct scx_sched *pos, struct scx_sched *root) { return pos ? NULL : root; }static inline 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 void switch_rq_lock(struct rq *from, struct rq *to){	bool tracked = scx_locked_rq() == from; 	if (tracked)		update_locked_rq(NULL);	raw_spin_rq_unlock(from);	raw_spin_rq_lock(to);	if (tracked)		update_locked_rq(to);} /* * Flipped on enable per sch->is_cid_type. Declared in internal.h so * subsystem inlines can read it. */DEFINE_STATIC_KEY_FALSE(__scx_is_cid_type); /**

Lines 1–500 of 10833. Load more