/* * 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, Thomas Gleixner <tglx@linutronix.de> * *  Adaptive scheduling granularity, math enhancements by Peter Zijlstra *  Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra */ #include <linux/sched/mm.h>#include <linux/sched/topology.h> #include <linux/latencytop.h>#include <linux/cpumask.h>#include <linux/cpuidle.h>#include <linux/slab.h>#include <linux/profile.h>#include <linux/interrupt.h>#include <linux/mempolicy.h>#include <linux/migrate.h>#include <linux/task_work.h> #include <trace/events/sched.h> #include "sched.h" /* * Targeted preemption latency for CPU-bound tasks: * * NOTE: this latency value is not the same as the concept of * 'timeslice length' - timeslices in CFS are of variable length * and have no persistent notion like in traditional, time-slice * based scheduling concepts. * * (to see the precise effective timeslice length of your workload, *  run vmstat and monitor the context-switches (cs) field) * * (default: 6ms * (1 + ilog(ncpus)), units: nanoseconds) */unsigned int sysctl_sched_latency			= 6000000ULL;unsigned int normalized_sysctl_sched_latency		= 6000000ULL; /* * The initial- and re-scaling of tunables is configurable * * Options are: * *   SCHED_TUNABLESCALING_NONE - unscaled, always *1 *   SCHED_TUNABLESCALING_LOG - scaled logarithmical, *1+ilog(ncpus) *   SCHED_TUNABLESCALING_LINEAR - scaled linear, *ncpus * * (default SCHED_TUNABLESCALING_LOG = *(1+ilog(ncpus)) */enum sched_tunable_scaling sysctl_sched_tunable_scaling = SCHED_TUNABLESCALING_LOG; /* * Minimal preemption granularity for CPU-bound tasks: * * (default: 0.75 msec * (1 + ilog(ncpus)), units: nanoseconds) */unsigned int sysctl_sched_min_granularity		= 750000ULL;unsigned int normalized_sysctl_sched_min_granularity	= 750000ULL; /* * This value is kept at sysctl_sched_latency/sysctl_sched_min_granularity */static unsigned int sched_nr_latency = 8; /* * After fork, child runs first. If set to 0 (default) then * parent will (try to) run first. */unsigned int sysctl_sched_child_runs_first __read_mostly; /* * SCHED_OTHER wake-up granularity. * * This option delays the preemption effects of decoupled workloads * and reduces their over-scheduling. Synchronous workloads will still * have immediate wakeup/sleep latencies. * * (default: 1 msec * (1 + ilog(ncpus)), units: nanoseconds) */unsigned int sysctl_sched_wakeup_granularity		= 1000000UL;unsigned int normalized_sysctl_sched_wakeup_granularity	= 1000000UL; const_debug unsigned int sysctl_sched_migration_cost	= 500000UL; #ifdef CONFIG_SMP/* * For asym packing, by default the lower numbered cpu has higher priority. */int __weak arch_asym_cpu_priority(int cpu){	return -cpu;}#endif #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) */unsigned int sysctl_sched_cfs_bandwidth_slice		= 5000UL;#endif /* * The margin used when comparing utilization with CPU capacity: * util * margin < capacity * 1024 * * (default: ~20%) */unsigned int capacity_margin				= 1280; 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_min_granularity);	SET_SYSCTL(sched_latency);	SET_SYSCTL(sched_wakeup_granularity);#undef SET_SYSCTL} void sched_init_granularity(void){	update_sysctl();} #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);	int shift = WMULT_SHIFT; 	__update_inv_weight(lw); 	if (unlikely(fact >> 32)) {		while (fact >> 32) {			fact >>= 1;			shift--;		}	} 	/* hint to use a 32x32->64 mul */	fact = (u64)(u32)fact * lw->inv_weight; 	while (fact >> 32) {		fact >>= 1;		shift--;	} 	return mul_u64_u32_shr(delta_exec, fact, shift);}  const struct sched_class fair_sched_class; /************************************************************** * CFS operations on generic schedulable entities: */ #ifdef CONFIG_FAIR_GROUP_SCHED /* cpu runqueue to which this cfs_rq is attached */static inline struct rq *rq_of(struct cfs_rq *cfs_rq){	return cfs_rq->rq;} /* An entity is a task if it doesn't "own" a runqueue */#define entity_is_task(se)	(!se->my_q) static inline struct task_struct *task_of(struct sched_entity *se){	SCHED_WARN_ON(!entity_is_task(se));	return container_of(se, struct task_struct, se);} /* Walk up scheduling entities hierarchy */#define for_each_sched_entity(se) \		for (; se; se = se->parent) static inline struct cfs_rq *task_cfs_rq(struct task_struct *p){	return p->se.cfs_rq;} /* runqueue on which this entity is (to be) queued */static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se){	return se->cfs_rq;} /* runqueue "owned" by this group */static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp){	return grp->my_q;} static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq){	if (!cfs_rq->on_list) {		struct rq *rq = rq_of(cfs_rq);		int cpu = cpu_of(rq);		/*		 * 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 beg of the tree		 */		if (cfs_rq->tg->parent &&		    cfs_rq->tg->parent->cfs_rq[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,				&(cfs_rq->tg->parent->cfs_rq[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;		} else 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 beg 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;		} else {			/*			 * 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 beg 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 beg			 * of the branch			 */			rq->tmp_alone_branch = &cfs_rq->leaf_cfs_rq_list;		} 		cfs_rq->on_list = 1;	}} static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq){	if (cfs_rq->on_list) {		list_del_rcu(&cfs_rq->leaf_cfs_rq_list);		cfs_rq->on_list = 0;	}} /* Iterate thr' 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(struct sched_entity *se){	return se->parent;} static voidfind_matching_se(struct sched_entity **se, struct sched_entity **pse){	int se_depth, pse_depth; 	/*	 * preemption test can be made between sibling entities who are in the	 * same cfs_rq i.e who have a common parent. Walk up the hierarchy of	 * both tasks until we find their ancestors who are siblings of common	 * parent.	 */ 	/* First walk up until both entities are at same depth */	se_depth = (*se)->depth;	pse_depth = (*pse)->depth; 	while (se_depth > pse_depth) {		se_depth--;		*se = parent_entity(*se);	} 	while (pse_depth > se_depth) {		pse_depth--;		*pse = parent_entity(*pse);	} 	while (!is_same_group(*se, *pse)) {		*se = parent_entity(*se);		*pse = parent_entity(*pse);	}} #else	/* !CONFIG_FAIR_GROUP_SCHED */ static inline struct task_struct *task_of(struct sched_entity *se){	return container_of(se, struct task_struct, se);} static inline struct rq *rq_of(struct cfs_rq *cfs_rq){	return container_of(cfs_rq, struct rq, cfs);} #define entity_is_task(se)	1 #define for_each_sched_entity(se) \		for (; se; se = NULL) static inline struct cfs_rq *task_cfs_rq(struct task_struct *p){	return &task_rq(p)->cfs;} static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se){	struct task_struct *p = task_of(se);	struct rq *rq = task_rq(p); 	return &rq->cfs;} /* runqueue "owned" by this group */static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp){	return NULL;} static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq){} static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_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 voidfind_matching_se(struct sched_entity **se, struct sched_entity **pse){} #endif	/* CONFIG_FAIR_GROUP_SCHED */ static __always_inlinevoid account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec); /************************************************************** * Scheduling class tree data structure manipulation methods: */ static inline u64 max_vruntime(u64 max_vruntime, u64 vruntime){	s64 delta = (s64)(vruntime - max_vruntime);	if (delta > 0)		max_vruntime = vruntime; 	return max_vruntime;} static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime){	s64 delta = (s64)(vruntime - min_vruntime);

Lines 1–500 of 9509. Load more