/* 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"#include "sub.h"#include "inlines.h" 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(). */LIST_HEAD(scx_sched_all); #ifdef CONFIG_EXT_SUB_SCHEDconst 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 */}; 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 */DEFINE_MUTEX(scx_enable_mutex);DEFINE_STATIC_KEY_FALSE(__scx_enabled);DEFINE_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); /* * Gates cgroup ops delivery. Set at the end of the cgroup init phase of root * enable and cleared before root disable starts tearing down tasks, both under * scx_cgroup_lock(). Holding cgroup_lock() and seeing %true guarantees no race * against root tearing down tasks. */bool scx_cgroup_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); /* is @dsq synchronized by the containing rq lock instead of dsq->lock? */static bool dsq_is_rq_owned(struct scx_dispatch_q *dsq){	switch (dsq->id) {	case SCX_DSQ_LOCAL:	case SCX_DSQ_REJECT:	case SCX_DSQ_RESCUE:		return true;	default:		return false;	}} /* Cursor for unique scx_sched instance ids. id 0 is reserved. */static atomic64_t scx_sched_id_cursor = ATOMIC64_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. */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); /* 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_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;} /** * 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. */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;} 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_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 scx_bypass_dsq(sch, cpu);} /** * 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 dispatch_one().	 */	if (rq->scx.flags & SCX_RQ_IN_DISPATCH)		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) {		struct task_struct *curr = rq->curr; 		/*		 * A protected slice refuses the preemption and the cpu stays		 * occupied. See rq_owned_post_enq().		 */		return curr->sched_class != &ext_sched_class ||			likely(!(curr->scx.flags & SCX_TASK_PROTECTED));	} 	/*	 * @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); /* * Under core scheduling, a pick that releases the rq lock invalidates the * core-wide selection it is part of. Count the releases so that the core-sched * pick can tell whether one happened across dispatch. */static void scx_rq_lock_drop(struct rq *rq){	lockdep_assert_rq_held(rq);#ifdef CONFIG_SCHED_CORE	if (sched_core_enabled(rq))		rq->scx.lock_drop_seq++;#endif} static void switch_rq_lock(struct rq *from, struct rq *to){	bool tracked = scx_locked_rq() == from; 	if (tracked)		update_locked_rq(NULL);	scx_rq_lock_drop(from);	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); /** * scx_call_op_set_cpumask - invoke ops.set_cpumask / ops_cid.set_cmask for @task * @sch: scx_sched being invoked * @rq: rq to update as the currently-locked rq, or NULL * @task: task whose affinity is changing * @cpumask: new cpumask * * For cid-form schedulers, translate @cpumask to a cmask via the per-cpu * scratch in cid.c and dispatch through the ops_cid union view. Caller * must hold @rq's rq lock so this_cpu_ptr is stable across the call. */static inline void scx_call_op_set_cpumask(struct scx_sched *sch, struct rq *rq,					   struct task_struct *task,					   const struct cpumask *cpumask){	if (scx_is_cid_type()) {		struct scx_cmask *kern_va = *this_cpu_ptr(sch->set_cmask_scratch);		struct scx_cmask_ref ref; 		/*		 * Build the per-cpu arena cmask from kernel geometry via @ref,		 * never reading its BPF-writable header. set_cmask()'s __arena		 * argument takes the kernel address and the struct_ops		 * trampoline rebases it into BPF's arena pointer form. The rq		 * lock makes this cpu the sole kernel writer.		 */		scx_cmask_ref_init_kern(sch, kern_va, 0, num_possible_cpus(), &ref);		scx_cmask_ref_from_cpumask(&ref, cpumask);		SCX_CALL_CID_OP_TASK(sch, set_cmask, rq, task, kern_va);	} else {		SCX_CALL_OP_TASK(sch, set_cpumask, rq, task, cpumask);	}} 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

Lines 1–500 of 11064. Load more