// SPDX-License-Identifier: GPL-2.0/* * Completely Fair Scheduling (CFS) Class (SCHED_NORMAL/SCHED_BATCH) * *  Copyright (C) 2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com> * *  Interactivity improvements by Mike Galbraith *  (C) 2007 Mike Galbraith <efault@gmx.de> * *  Various enhancements by Dmitry Adamushko. *  (C) 2007 Dmitry Adamushko <dmitry.adamushko@gmail.com> * *  Group scheduling enhancements by Srivatsa Vaddagiri *  Copyright IBM Corporation, 2007 *  Author: Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com> * *  Scaled math optimizations by Thomas Gleixner *  Copyright (C) 2007, Linutronix GmbH, Thomas Gleixner <tglx@kernel.org> * *  Adaptive scheduling granularity, math enhancements by Peter Zijlstra *  Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra */#include <linux/energy_model.h>#include <linux/mmap_lock.h>#include <linux/hugetlb_inline.h>#include <linux/jiffies.h>#include <linux/mm_api.h>#include <linux/highmem.h>#include <linux/hrtimer.h>#include <linux/hrtimer_bases.h>#include <linux/spinlock_api.h>#include <linux/cpumask_api.h>#include <linux/lockdep_api.h>#include <linux/softirq.h>#include <linux/refcount_api.h>#include <linux/topology.h>#include <linux/sched/clock.h>#include <linux/sched/cond_resched.h>#include <linux/sched/cputime.h>#include <linux/sched/isolation.h>#include <linux/sched/nohz.h>#include <linux/sched/prio.h>#include <linux/static_call.h> #include <linux/cpuidle.h>#include <linux/interrupt.h>#include <linux/memory-tiers.h>#include <linux/mempolicy.h>#include <linux/mutex_api.h>#include <linux/profile.h>#include <linux/psi.h>#include <linux/ratelimit.h>#include <linux/task_work.h>#include <linux/rbtree_augmented.h> #include <asm/switch_to.h> #include <uapi/linux/sched/types.h> #include "sched.h"#include "stats.h"#include "autogroup.h" /* * The initial- and re-scaling of tunables is configurable * * Options are: * *   SCHED_TUNABLESCALING_NONE - unscaled, always *1 *   SCHED_TUNABLESCALING_LOG - scaled logarithmically, *1+ilog(ncpus) *   SCHED_TUNABLESCALING_LINEAR - scaled linear, *ncpus * * (default SCHED_TUNABLESCALING_LOG = *(1+ilog(ncpus)) */unsigned int sysctl_sched_tunable_scaling = SCHED_TUNABLESCALING_LOG; /* * Default base time slice (request size r_i) for SCHED_NORMAL/SCHED_BATCH: * * Under EEVDF this is the request size used to compute the virtual * deadline; see update_deadline(). * * (default: 0.70 msec * (1 + ilog(ncpus)), units: nanoseconds) */unsigned int sysctl_sched_base_slice			= 700000ULL;static unsigned int normalized_sysctl_sched_base_slice	= 700000ULL; __read_mostly unsigned int sysctl_sched_migration_cost	= 500000UL; static int __init setup_sched_thermal_decay_shift(char *str){	pr_warn("Ignoring the deprecated sched_thermal_decay_shift= option\n");	return 1;}__setup("sched_thermal_decay_shift=", setup_sched_thermal_decay_shift); /* * For asym packing, by default the lower numbered CPU has higher priority. */int __weak arch_asym_cpu_priority(int cpu){	return -cpu;} /* * The margin used when comparing utilization with CPU capacity. * * (default: ~20%) */#define fits_capacity(cap, max)	((cap) * 1280 < (max) * 1024) /* * The margin used when comparing CPU capacities. * is 'cap1' noticeably greater than 'cap2' * * (default: ~5%) */#define capacity_greater(cap1, cap2) ((cap1) * 1024 > (cap2) * 1078) #ifdef CONFIG_CFS_BANDWIDTH/* * Amount of runtime to allocate from global (tg) to local (per-cfs_rq) pool * each time a cfs_rq requests quota. * * Note: in the case that the slice exceeds the runtime remaining (either due * to consumption or the quota being specified to be smaller than the slice) * we will always only issue the remaining available time. * * (default: 5 msec, units: microseconds) */static unsigned int sysctl_sched_cfs_bandwidth_slice		= 5000UL;#endif #ifdef CONFIG_NUMA_BALANCING/* Restrict the NUMA promotion throughput (MB/s) for each target node. */static unsigned int sysctl_numa_balancing_promote_rate_limit = 65536;#endif #ifdef CONFIG_SYSCTLstatic const struct ctl_table sched_fair_sysctls[] = {#ifdef CONFIG_CFS_BANDWIDTH	{		.procname       = "sched_cfs_bandwidth_slice_us",		.data           = &sysctl_sched_cfs_bandwidth_slice,		.maxlen         = sizeof(unsigned int),		.mode           = 0644,		.proc_handler   = proc_dointvec_minmax,		.extra1         = SYSCTL_ONE,	},#endif#ifdef CONFIG_NUMA_BALANCING	{		.procname	= "numa_balancing_promote_rate_limit_MBps",		.data		= &sysctl_numa_balancing_promote_rate_limit,		.maxlen		= sizeof(unsigned int),		.mode		= 0644,		.proc_handler	= proc_dointvec_minmax,		.extra1		= SYSCTL_ZERO,	},#endif /* CONFIG_NUMA_BALANCING */}; static int __init sched_fair_sysctl_init(void){	register_sysctl_init("kernel", sched_fair_sysctls);	return 0;}late_initcall(sched_fair_sysctl_init);#endif /* CONFIG_SYSCTL */ static inline void update_load_add(struct load_weight *lw, unsigned long inc){	lw->weight += inc;	lw->inv_weight = 0;} static inline void update_load_sub(struct load_weight *lw, unsigned long dec){	lw->weight -= dec;	lw->inv_weight = 0;} static inline void update_load_set(struct load_weight *lw, unsigned long w){	lw->weight = w;	lw->inv_weight = 0;} /* * Increase the granularity value when there are more CPUs, * because with more CPUs the 'effective latency' as visible * to users decreases. But the relationship is not linear, * so pick a second-best guess by going with the log2 of the * number of CPUs. * * This idea comes from the SD scheduler of Con Kolivas: */static unsigned int get_update_sysctl_factor(void){	unsigned int cpus = min_t(unsigned int, num_online_cpus(), 8);	unsigned int factor; 	switch (sysctl_sched_tunable_scaling) {	case SCHED_TUNABLESCALING_NONE:		factor = 1;		break;	case SCHED_TUNABLESCALING_LINEAR:		factor = cpus;		break;	case SCHED_TUNABLESCALING_LOG:	default:		factor = 1 + ilog2(cpus);		break;	} 	return factor;} static void update_sysctl(void){	unsigned int factor = get_update_sysctl_factor(); #define SET_SYSCTL(name) \	(sysctl_##name = (factor) * normalized_sysctl_##name)	SET_SYSCTL(sched_base_slice);#undef SET_SYSCTL} void __init sched_init_granularity(void){	update_sysctl();} #ifndef CONFIG_64BIT#define WMULT_CONST	(~0U)#define WMULT_SHIFT	32 static void __update_inv_weight(struct load_weight *lw){	unsigned long w; 	if (likely(lw->inv_weight))		return; 	w = scale_load_down(lw->weight); 	if (BITS_PER_LONG > 32 && unlikely(w >= WMULT_CONST))		lw->inv_weight = 1;	else if (unlikely(!w))		lw->inv_weight = WMULT_CONST;	else		lw->inv_weight = WMULT_CONST / w;} /* * delta_exec * weight / lw.weight *   OR * (delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT * * Either weight := NICE_0_LOAD and lw \e sched_prio_to_wmult[], in which case * we're guaranteed shift stays positive because inv_weight is guaranteed to * fit 32 bits, and NICE_0_LOAD gives another 10 bits; therefore shift >= 22. * * Or, weight =< lw.weight (because lw.weight is the runqueue weight), thus * weight/lw.weight <= 1, and therefore our shift will also be positive. */static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw){	u64 fact = scale_load_down(weight);	u32 fact_hi = (u32)(fact >> 32);	int shift = WMULT_SHIFT;	int fs; 	__update_inv_weight(lw); 	if (unlikely(fact_hi)) {		fs = fls(fact_hi);		shift -= fs;		fact >>= fs;	} 	fact = mul_u32_u32(fact, lw->inv_weight); 	fact_hi = (u32)(fact >> 32);	if (fact_hi) {		fs = fls(fact_hi);		shift -= fs;		fact >>= fs;	} 	return mul_u64_u32_shr(delta_exec, fact, shift);}#elsestatic u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw){	return (delta_exec * weight) / lw->weight;}#endif /* * delta /= w */static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se){	if (se->h_load.weight != NICE_0_LOAD)		delta = __calc_delta(delta, NICE_0_LOAD, &se->h_load); 	return delta;} const struct sched_class fair_sched_class; /************************************************************** * CFS operations on generic schedulable entities: */ #ifdef CONFIG_FAIR_GROUP_SCHED /* Walk up scheduling entities hierarchy */#define for_each_sched_entity(se) \		for (; se; se = se->parent) static inline bool list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq){	struct rq *rq = rq_of(cfs_rq);	int cpu = cpu_of(rq); 	if (cfs_rq->on_list)		return rq->tmp_alone_branch == &rq->leaf_cfs_rq_list; 	cfs_rq->on_list = 1; 	/*	 * Ensure we either appear before our parent (if already	 * enqueued) or force our parent to appear after us when it is	 * enqueued. The fact that we always enqueue bottom-up	 * reduces this to two cases and a special case for the root	 * cfs_rq. Furthermore, it also means that we will always reset	 * tmp_alone_branch either when the branch is connected	 * to a tree or when we reach the top of the tree	 */	if (cfs_rq->tg->parent &&	    tg_cfs_rq(cfs_rq->tg->parent, cpu)->on_list) {		/*		 * If parent is already on the list, we add the child		 * just before. Thanks to circular linked property of		 * the list, this means to put the child at the tail		 * of the list that starts by parent.		 */		list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,			&(tg_cfs_rq(cfs_rq->tg->parent, cpu)->leaf_cfs_rq_list));		/*		 * The branch is now connected to its tree so we can		 * reset tmp_alone_branch to the beginning of the		 * list.		 */		rq->tmp_alone_branch = &rq->leaf_cfs_rq_list;		return true;	} 	if (!cfs_rq->tg->parent) {		/*		 * cfs rq without parent should be put		 * at the tail of the list.		 */		list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,			&rq->leaf_cfs_rq_list);		/*		 * We have reach the top of a tree so we can reset		 * tmp_alone_branch to the beginning of the list.		 */		rq->tmp_alone_branch = &rq->leaf_cfs_rq_list;		return true;	} 	/*	 * The parent has not already been added so we want to	 * make sure that it will be put after us.	 * tmp_alone_branch points to the begin of the branch	 * where we will add parent.	 */	list_add_rcu(&cfs_rq->leaf_cfs_rq_list, rq->tmp_alone_branch);	/*	 * update tmp_alone_branch to points to the new begin	 * of the branch	 */	rq->tmp_alone_branch = &cfs_rq->leaf_cfs_rq_list;	return false;} static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq){	if (cfs_rq->on_list) {		struct rq *rq = rq_of(cfs_rq); 		/*		 * With cfs_rq being unthrottled/throttled during an enqueue,		 * it can happen the tmp_alone_branch points to the leaf that		 * we finally want to delete. In this case, tmp_alone_branch moves		 * to the prev element but it will point to rq->leaf_cfs_rq_list		 * at the end of the enqueue.		 */		if (rq->tmp_alone_branch == &cfs_rq->leaf_cfs_rq_list)			rq->tmp_alone_branch = cfs_rq->leaf_cfs_rq_list.prev; 		list_del_rcu(&cfs_rq->leaf_cfs_rq_list);		cfs_rq->on_list = 0;	}} static inline void assert_list_leaf_cfs_rq(struct rq *rq){	WARN_ON_ONCE(rq->tmp_alone_branch != &rq->leaf_cfs_rq_list);} /* Iterate through all leaf cfs_rq's on a runqueue */#define for_each_leaf_cfs_rq_safe(rq, cfs_rq, pos)			\	list_for_each_entry_safe(cfs_rq, pos, &rq->leaf_cfs_rq_list,	\				 leaf_cfs_rq_list) /* Do the two (enqueued) entities belong to the same group ? */static inline struct cfs_rq *is_same_group(struct sched_entity *se, struct sched_entity *pse){	if (se->cfs_rq == pse->cfs_rq)		return se->cfs_rq; 	return NULL;} static inline struct sched_entity *parent_entity(const struct sched_entity *se){	return se->parent;} static int tg_is_idle(struct task_group *tg){	return tg->idle > 0;} static int cfs_rq_is_idle(struct cfs_rq *cfs_rq){	return cfs_rq->idle > 0;} static int se_is_idle(struct sched_entity *se){	if (entity_is_task(se))		return task_has_idle_policy(task_of(se));	return cfs_rq_is_idle(group_cfs_rq(se));} #else /* !CONFIG_FAIR_GROUP_SCHED: */ #define for_each_sched_entity(se) \		for (; se; se = NULL) static inline bool list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq){	return true;} static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq){} static inline void assert_list_leaf_cfs_rq(struct rq *rq){} #define for_each_leaf_cfs_rq_safe(rq, cfs_rq, pos)	\		for (cfs_rq = &rq->cfs, pos = NULL; cfs_rq; cfs_rq = pos) static inline struct sched_entity *parent_entity(struct sched_entity *se){	return NULL;} static inline int tg_is_idle(struct task_group *tg){	return 0;} static int cfs_rq_is_idle(struct cfs_rq *cfs_rq){	return 0;} static int se_is_idle(struct sched_entity *se){	return task_has_idle_policy(task_of(se));} #endif /* !CONFIG_FAIR_GROUP_SCHED */ static __always_inlinebool account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec); /************************************************************** * Scheduling class tree data structure manipulation methods:

Lines 1–500 of 15682. Load more