/* *  kernel/sched.c * *  Kernel scheduler and related syscalls * *  Copyright (C) 1991-2002  Linus Torvalds * *  1996-12-23  Modified by Dave Grothe to fix bugs in semaphores and *		make semaphores SMP safe *  1998-11-19	Implemented schedule_timeout() and related stuff *		by Andrea Arcangeli *  2002-01-04	New ultra-scalable O(1) scheduler by Ingo Molnar: *		hybrid priority-list and round-robin design with *		an array-switch method of distributing timeslices *		and per-CPU runqueues.  Cleanups and useful suggestions *		by Davide Libenzi, preemptible kernel bits by Robert Love. *  2003-09-03	Interactivity tuning by Con Kolivas. *  2004-04-02	Scheduler domains code by Nick Piggin *  2007-04-15  Work begun on replacing all interactivity tuning with a *              fair scheduling design by Con Kolivas. *  2007-05-05  Load balancing (smp-nice) and other improvements *              by Peter Williams *  2007-05-06  Interactivity improvements to CFS by Mike Galbraith *  2007-07-01  Group scheduling enhancements by Srivatsa Vaddagiri */ #include <linux/mm.h>#include <linux/module.h>#include <linux/nmi.h>#include <linux/init.h>#include <linux/uaccess.h>#include <linux/highmem.h>#include <linux/smp_lock.h>#include <asm/mmu_context.h>#include <linux/interrupt.h>#include <linux/capability.h>#include <linux/completion.h>#include <linux/kernel_stat.h>#include <linux/debug_locks.h>#include <linux/security.h>#include <linux/notifier.h>#include <linux/profile.h>#include <linux/freezer.h>#include <linux/vmalloc.h>#include <linux/blkdev.h>#include <linux/delay.h>#include <linux/smp.h>#include <linux/threads.h>#include <linux/timer.h>#include <linux/rcupdate.h>#include <linux/cpu.h>#include <linux/cpuset.h>#include <linux/percpu.h>#include <linux/kthread.h>#include <linux/seq_file.h>#include <linux/sysctl.h>#include <linux/syscalls.h>#include <linux/times.h>#include <linux/tsacct_kern.h>#include <linux/kprobes.h>#include <linux/delayacct.h>#include <linux/reciprocal_div.h>#include <linux/unistd.h> #include <asm/tlb.h> /* * Scheduler clock - returns current time in nanosec units. * This is default implementation. * Architectures and sub-architectures can override this. */unsigned long long __attribute__((weak)) sched_clock(void){	return (unsigned long long)jiffies * (1000000000 / HZ);} /* * Convert user-nice values [ -20 ... 0 ... 19 ] * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ], * and back. */#define NICE_TO_PRIO(nice)	(MAX_RT_PRIO + (nice) + 20)#define PRIO_TO_NICE(prio)	((prio) - MAX_RT_PRIO - 20)#define TASK_NICE(p)		PRIO_TO_NICE((p)->static_prio) /* * 'User priority' is the nice value converted to something we * can work with better when scaling various scheduler parameters, * it's a [ 0 ... 39 ] range. */#define USER_PRIO(p)		((p)-MAX_RT_PRIO)#define TASK_USER_PRIO(p)	USER_PRIO((p)->static_prio)#define MAX_USER_PRIO		(USER_PRIO(MAX_PRIO)) /* * Some helpers for converting nanosecond timing to jiffy resolution */#define NS_TO_JIFFIES(TIME)	((TIME) / (1000000000 / HZ))#define JIFFIES_TO_NS(TIME)	((TIME) * (1000000000 / HZ)) #define NICE_0_LOAD		SCHED_LOAD_SCALE#define NICE_0_SHIFT		SCHED_LOAD_SHIFT /* * These are the 'tuning knobs' of the scheduler: * * Minimum timeslice is 5 msecs (or 1 jiffy, whichever is larger), * default timeslice is 100 msecs, maximum timeslice is 800 msecs. * Timeslices get refilled after they expire. */#define MIN_TIMESLICE		max(5 * HZ / 1000, 1)#define DEF_TIMESLICE		(100 * HZ / 1000) #ifdef CONFIG_SMP/* * Divide a load by a sched group cpu_power : (load / sg->__cpu_power) * Since cpu_power is a 'constant', we can use a reciprocal divide. */static inline u32 sg_div_cpu_power(const struct sched_group *sg, u32 load){	return reciprocal_divide(load, sg->reciprocal_cpu_power);} /* * Each time a sched group cpu_power is changed, * we must compute its reciprocal value */static inline void sg_inc_cpu_power(struct sched_group *sg, u32 val){	sg->__cpu_power += val;	sg->reciprocal_cpu_power = reciprocal_value(sg->__cpu_power);}#endif #define SCALE_PRIO(x, prio) \	max(x * (MAX_PRIO - prio) / (MAX_USER_PRIO / 2), MIN_TIMESLICE) /* * static_prio_timeslice() scales user-nice values [ -20 ... 0 ... 19 ] * to time slice values: [800ms ... 100ms ... 5ms] */static unsigned int static_prio_timeslice(int static_prio){	if (static_prio == NICE_TO_PRIO(19))		return 1; 	if (static_prio < NICE_TO_PRIO(0))		return SCALE_PRIO(DEF_TIMESLICE * 4, static_prio);	else		return SCALE_PRIO(DEF_TIMESLICE, static_prio);} static inline int rt_policy(int policy){	if (unlikely(policy == SCHED_FIFO) || unlikely(policy == SCHED_RR))		return 1;	return 0;} static inline int task_has_rt_policy(struct task_struct *p){	return rt_policy(p->policy);} /* * This is the priority-queue data structure of the RT scheduling class: */struct rt_prio_array {	DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */	struct list_head queue[MAX_RT_PRIO];}; struct load_stat {	struct load_weight load;	u64 load_update_start, load_update_last;	unsigned long delta_fair, delta_exec, delta_stat;}; /* CFS-related fields in a runqueue */struct cfs_rq {	struct load_weight load;	unsigned long nr_running; 	s64 fair_clock;	u64 exec_clock;	s64 wait_runtime;	u64 sleeper_bonus;	unsigned long wait_runtime_overruns, wait_runtime_underruns; 	struct rb_root tasks_timeline;	struct rb_node *rb_leftmost;	struct rb_node *rb_load_balance_curr;#ifdef CONFIG_FAIR_GROUP_SCHED	/* 'curr' points to currently running entity on this cfs_rq.	 * It is set to NULL otherwise (i.e when none are currently running).	 */	struct sched_entity *curr;	struct rq *rq;	/* cpu runqueue to which this cfs_rq is attached */ 	/* leaf cfs_rqs are those that hold tasks (lowest schedulable entity in	 * a hierarchy). Non-leaf lrqs hold other higher schedulable entities	 * (like users, containers etc.)	 *	 * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This	 * list is used during load balance.	 */	struct list_head leaf_cfs_rq_list; /* Better name : task_cfs_rq_list? */#endif}; /* Real-Time classes' related field in a runqueue: */struct rt_rq {	struct rt_prio_array active;	int rt_load_balance_idx;	struct list_head *rt_load_balance_head, *rt_load_balance_curr;}; /* * This is the main, per-CPU runqueue data structure. * * Locking rule: those places that want to lock multiple runqueues * (such as the load balancing or the thread migration code), lock * acquire operations must be ordered by ascending &runqueue. */struct rq {	spinlock_t lock;	/* runqueue lock */ 	/*	 * nr_running and cpu_load should be in the same cacheline because	 * remote CPUs use both these fields when doing load calculation.	 */	unsigned long nr_running;	#define CPU_LOAD_IDX_MAX 5	unsigned long cpu_load[CPU_LOAD_IDX_MAX];	unsigned char idle_at_tick;#ifdef CONFIG_NO_HZ	unsigned char in_nohz_recently;#endif	struct load_stat ls;	/* capture load from *all* tasks on this cpu */	unsigned long nr_load_updates;	u64 nr_switches; 	struct cfs_rq cfs;#ifdef CONFIG_FAIR_GROUP_SCHED	struct list_head leaf_cfs_rq_list; /* list of leaf cfs_rq on this cpu */#endif	struct rt_rq  rt; 	/*	 * This is part of a global counter where only the total sum	 * over all CPUs matters. A task can increase this counter on	 * one CPU and if it got migrated afterwards it may decrease	 * it on another CPU. Always updated under the runqueue lock:	 */	unsigned long nr_uninterruptible; 	struct task_struct *curr, *idle;	unsigned long next_balance;	struct mm_struct *prev_mm; 	u64 clock, prev_clock_raw;	s64 clock_max_delta; 	unsigned int clock_warps, clock_overflows;	u64 idle_clock;	unsigned int clock_deep_idle_events;	u64 tick_timestamp; 	atomic_t nr_iowait; #ifdef CONFIG_SMP	struct sched_domain *sd; 	/* For active balancing */	int active_balance;	int push_cpu;	int cpu;		/* cpu of this runqueue */ 	struct task_struct *migration_thread;	struct list_head migration_queue;#endif #ifdef CONFIG_SCHEDSTATS	/* latency stats */	struct sched_info rq_sched_info; 	/* sys_sched_yield() stats */	unsigned long yld_exp_empty;	unsigned long yld_act_empty;	unsigned long yld_both_empty;	unsigned long yld_cnt; 	/* schedule() stats */	unsigned long sched_switch;	unsigned long sched_cnt;	unsigned long sched_goidle; 	/* try_to_wake_up() stats */	unsigned long ttwu_cnt;	unsigned long ttwu_local;#endif	struct lock_class_key rq_lock_key;}; static DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);static DEFINE_MUTEX(sched_hotcpu_mutex); static inline void check_preempt_curr(struct rq *rq, struct task_struct *p){	rq->curr->sched_class->check_preempt_curr(rq, p);} static inline int cpu_of(struct rq *rq){#ifdef CONFIG_SMP	return rq->cpu;#else	return 0;#endif} /* * Update the per-runqueue clock, as finegrained as the platform can give * us, but without assuming monotonicity, etc.: */static void __update_rq_clock(struct rq *rq){	u64 prev_raw = rq->prev_clock_raw;	u64 now = sched_clock();	s64 delta = now - prev_raw;	u64 clock = rq->clock; #ifdef CONFIG_SCHED_DEBUG	WARN_ON_ONCE(cpu_of(rq) != smp_processor_id());#endif	/*	 * Protect against sched_clock() occasionally going backwards:	 */	if (unlikely(delta < 0)) {		clock++;		rq->clock_warps++;	} else {		/*		 * Catch too large forward jumps too:		 */		if (unlikely(clock + delta > rq->tick_timestamp + TICK_NSEC)) {			if (clock < rq->tick_timestamp + TICK_NSEC)				clock = rq->tick_timestamp + TICK_NSEC;			else				clock++;			rq->clock_overflows++;		} else {			if (unlikely(delta > rq->clock_max_delta))				rq->clock_max_delta = delta;			clock += delta;		}	} 	rq->prev_clock_raw = now;	rq->clock = clock;} static void update_rq_clock(struct rq *rq){	if (likely(smp_processor_id() == cpu_of(rq)))		__update_rq_clock(rq);} /* * The domain tree (rq->sd) is protected by RCU's quiescent state transition. * See detach_destroy_domains: synchronize_sched for details. * * The domain tree of any CPU may only be accessed from within * preempt-disabled sections. */#define for_each_domain(cpu, __sd) \	for (__sd = rcu_dereference(cpu_rq(cpu)->sd); __sd; __sd = __sd->parent) #define cpu_rq(cpu)		(&per_cpu(runqueues, (cpu)))#define this_rq()		(&__get_cpu_var(runqueues))#define task_rq(p)		cpu_rq(task_cpu(p))#define cpu_curr(cpu)		(cpu_rq(cpu)->curr) /* * For kernel-internal use: high-speed (but slightly incorrect) per-cpu * clock constructed from sched_clock(): */unsigned long long cpu_clock(int cpu){	unsigned long long now;	unsigned long flags;	struct rq *rq; 	local_irq_save(flags);	rq = cpu_rq(cpu);	update_rq_clock(rq);	now = rq->clock;	local_irq_restore(flags); 	return now;} #ifdef CONFIG_FAIR_GROUP_SCHED/* Change a task's ->cfs_rq if it moves across CPUs */static inline void set_task_cfs_rq(struct task_struct *p){	p->se.cfs_rq = &task_rq(p)->cfs;}#elsestatic inline void set_task_cfs_rq(struct task_struct *p){}#endif #ifndef prepare_arch_switch# define prepare_arch_switch(next)	do { } while (0)#endif#ifndef finish_arch_switch# define finish_arch_switch(prev)	do { } while (0)#endif #ifndef __ARCH_WANT_UNLOCKED_CTXSWstatic inline int task_running(struct rq *rq, struct task_struct *p){	return rq->curr == p;} static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next){} static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev){#ifdef CONFIG_DEBUG_SPINLOCK	/* this is a valid case when another task releases the spinlock */	rq->lock.owner = current;#endif	/*	 * If we are tracking spinlock dependencies then we have to	 * fix up the runqueue lock - which gets 'carried over' from	 * prev into current:	 */	spin_acquire(&rq->lock.dep_map, 0, 0, _THIS_IP_); 	spin_unlock_irq(&rq->lock);} #else /* __ARCH_WANT_UNLOCKED_CTXSW */static inline int task_running(struct rq *rq, struct task_struct *p){#ifdef CONFIG_SMP	return p->oncpu;#else	return rq->curr == p;#endif} static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next){#ifdef CONFIG_SMP	/*	 * We can optimise this out completely for !SMP, because the	 * SMP rebalancing from interrupt is the only thing that cares	 * here.	 */	next->oncpu = 1;#endif#ifdef __ARCH_WANT_INTERRUPTS_ON_CTXSW	spin_unlock_irq(&rq->lock);#else	spin_unlock(&rq->lock);#endif} static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev){#ifdef CONFIG_SMP	/*	 * After ->oncpu is cleared, the task can be moved to a different CPU.	 * We must ensure this doesn't happen until the switch is completely	 * finished.	 */	smp_wmb();	prev->oncpu = 0;#endif#ifndef __ARCH_WANT_INTERRUPTS_ON_CTXSW	local_irq_enable();#endif}#endif /* __ARCH_WANT_UNLOCKED_CTXSW */ /* * __task_rq_lock - lock the runqueue a given task resides on. * Must be called interrupts disabled. */static inline struct rq *__task_rq_lock(struct task_struct *p)	__acquires(rq->lock){	struct rq *rq; 

Lines 1–500 of 6741. Load more