/* * 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 <pzijlstr@redhat.com> */ #include <linux/latencytop.h>#include <linux/sched.h>#include <linux/cpumask.h> /* * Targeted preemption latency for CPU-bound tasks: * (default: 6ms * (1 + ilog(ncpus)), units: nanoseconds) * * 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) */unsigned int sysctl_sched_latency = 6000000ULL;unsigned int normalized_sysctl_sched_latency = 6000000ULL; /* * The initial- and re-scaling of tunables is configurable * (default SCHED_TUNABLESCALING_LOG = *(1+ilog(ncpus)) * * Options are: * SCHED_TUNABLESCALING_NONE - unscaled, always *1 * SCHED_TUNABLESCALING_LOG - scaled logarithmical, *1+ilog(ncpus) * SCHED_TUNABLESCALING_LINEAR - scaled linear, *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; /* * 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. * (default: 1 msec * (1 + ilog(ncpus)), units: nanoseconds) * * This option delays the preemption effects of decoupled workloads * and reduces their over-scheduling. Synchronous workloads will still * have immediate wakeup/sleep latencies. */unsigned int sysctl_sched_wakeup_granularity = 1000000UL;unsigned int normalized_sysctl_sched_wakeup_granularity = 1000000UL; const_debug unsigned int sysctl_sched_migration_cost = 500000UL; /* * The exponential sliding  window over which load is averaged for shares * distribution. * (default: 10msec) */unsigned int __read_mostly sysctl_sched_shares_window = 10000000UL; #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 static 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){#ifdef CONFIG_SCHED_DEBUG	WARN_ON_ONCE(!entity_is_task(se));#endif	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) {		/*		 * 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.		 */		if (cfs_rq->tg->parent &&		    cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->on_list) {			list_add_rcu(&cfs_rq->leaf_cfs_rq_list,				&rq_of(cfs_rq)->leaf_cfs_rq_list);		} else {			list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,				&rq_of(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(rq, cfs_rq) \	list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list) /* Do the two (enqueued) entities belong to the same group ? */static inline intis_same_group(struct sched_entity *se, struct sched_entity *pse){	if (se->cfs_rq == pse->cfs_rq)		return 1; 	return 0;} static inline struct sched_entity *parent_entity(struct sched_entity *se){	return se->parent;} /* return depth at which a sched entity is present in the hierarchy */static inline int depth_se(struct sched_entity *se){	int depth = 0; 	for_each_sched_entity(se)		depth++; 	return depth;} 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 = depth_se(*se);	pse_depth = depth_se(*pse); 	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(rq, cfs_rq) \		for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL) static inline intis_same_group(struct sched_entity *se, struct sched_entity *pse){	return 1;} 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 void account_cfs_rq_runtime(struct cfs_rq *cfs_rq,				   unsigned long delta_exec); /************************************************************** * Scheduling class tree data structure manipulation methods: */ static inline u64 max_vruntime(u64 min_vruntime, u64 vruntime){	s64 delta = (s64)(vruntime - min_vruntime);	if (delta > 0)		min_vruntime = vruntime; 	return min_vruntime;} static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime){	s64 delta = (s64)(vruntime - min_vruntime);	if (delta < 0)		min_vruntime = vruntime; 	return min_vruntime;} static inline int entity_before(struct sched_entity *a,				struct sched_entity *b){	return (s64)(a->vruntime - b->vruntime) < 0;} static void update_min_vruntime(struct cfs_rq *cfs_rq){	u64 vruntime = cfs_rq->min_vruntime; 	if (cfs_rq->curr)		vruntime = cfs_rq->curr->vruntime; 	if (cfs_rq->rb_leftmost) {		struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,						   struct sched_entity,						   run_node); 		if (!cfs_rq->curr)			vruntime = se->vruntime;		else			vruntime = min_vruntime(vruntime, se->vruntime);	} 	cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);#ifndef CONFIG_64BIT	smp_wmb();	cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;#endif} /* * Enqueue an entity into the rb-tree: */static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se){	struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;	struct rb_node *parent = NULL;	struct sched_entity *entry;	int leftmost = 1; 	/*	 * Find the right place in the rbtree:	 */	while (*link) {		parent = *link;		entry = rb_entry(parent, struct sched_entity, run_node);		/*		 * We dont care about collisions. Nodes with		 * the same key stay together.		 */		if (entity_before(se, entry)) {			link = &parent->rb_left;		} else {			link = &parent->rb_right;			leftmost = 0;		}	} 	/*	 * Maintain a cache of leftmost tree entries (it is frequently	 * used):	 */	if (leftmost)		cfs_rq->rb_leftmost = &se->run_node; 	rb_link_node(&se->run_node, parent, link);	rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);} static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se){	if (cfs_rq->rb_leftmost == &se->run_node) {		struct rb_node *next_node; 		next_node = rb_next(&se->run_node);		cfs_rq->rb_leftmost = next_node;	} 	rb_erase(&se->run_node, &cfs_rq->tasks_timeline);} static struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq){	struct rb_node *left = cfs_rq->rb_leftmost; 	if (!left)		return NULL; 	return rb_entry(left, struct sched_entity, run_node);} static struct sched_entity *__pick_next_entity(struct sched_entity *se){	struct rb_node *next = rb_next(&se->run_node); 	if (!next)		return NULL; 	return rb_entry(next, struct sched_entity, run_node);} #ifdef CONFIG_SCHED_DEBUGstatic struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq){	struct rb_node *last = rb_last(&cfs_rq->tasks_timeline); 	if (!last)		return NULL; 	return rb_entry(last, struct sched_entity, run_node);} /************************************************************** * Scheduling class statistics methods: */ int sched_proc_update_handler(struct ctl_table *table, int write,		void __user *buffer, size_t *lenp,		loff_t *ppos){	int ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);	int factor = get_update_sysctl_factor(); 	if (ret || !write)		return ret; 	sched_nr_latency = DIV_ROUND_UP(sysctl_sched_latency,					sysctl_sched_min_granularity); #define WRT_SYSCTL(name) \	(normalized_sysctl_##name = sysctl_##name / (factor))	WRT_SYSCTL(sched_min_granularity);	WRT_SYSCTL(sched_latency);	WRT_SYSCTL(sched_wakeup_granularity);#undef WRT_SYSCTL 	return 0;}#endif /* * delta /= w */static inline unsigned longcalc_delta_fair(unsigned long delta, struct sched_entity *se){	if (unlikely(se->load.weight != NICE_0_LOAD))		delta = calc_delta_mine(delta, NICE_0_LOAD, &se->load); 	return delta;} /* * The idea is to set a period in which each task runs once. * * When there are too many tasks (sysctl_sched_nr_latency) we have to stretch * this period because otherwise the slices get too small. * * p = (nr <= nl) ? l : l*nr/nl */static u64 __sched_period(unsigned long nr_running){	u64 period = sysctl_sched_latency;	unsigned long nr_latency = sched_nr_latency; 	if (unlikely(nr_running > nr_latency)) {

Lines 1–500 of 5090. Load more