linux - kernel/sched.c

6890 lines · 173.0 KiB

1	/*
2	* kernel/sched.c
3	*
4	* Kernel scheduler and related syscalls
5	*
6	* Copyright (C) 1991-2002 Linus Torvalds
7	*
8	* 1996-12-23 Modified by Dave Grothe to fix bugs in semaphores and
9	* make semaphores SMP safe
10	* 1998-11-19 Implemented schedule_timeout() and related stuff
11	* by Andrea Arcangeli
12	* 2002-01-04 New ultra-scalable O(1) scheduler by Ingo Molnar:
13	* hybrid priority-list and round-robin design with
14	* an array-switch method of distributing timeslices
15	* and per-CPU runqueues. Cleanups and useful suggestions
16	* by Davide Libenzi, preemptible kernel bits by Robert Love.
17	* 2003-09-03 Interactivity tuning by Con Kolivas.
18	* 2004-04-02 Scheduler domains code by Nick Piggin
19	*/
20
21	#include <linux/mm.h>
22	#include <linux/module.h>
23	#include <linux/nmi.h>
24	#include <linux/init.h>
25	#include <asm/uaccess.h>
26	#include <linux/highmem.h>
27	#include <linux/smp_lock.h>
28	#include <asm/mmu_context.h>
29	#include <linux/interrupt.h>
30	#include <linux/capability.h>
31	#include <linux/completion.h>
32	#include <linux/kernel_stat.h>
33	#include <linux/debug_locks.h>
34	#include <linux/security.h>
35	#include <linux/notifier.h>
36	#include <linux/profile.h>
37	#include <linux/freezer.h>
38	#include <linux/vmalloc.h>
39	#include <linux/blkdev.h>
40	#include <linux/delay.h>
41	#include <linux/smp.h>
42	#include <linux/threads.h>
43	#include <linux/timer.h>
44	#include <linux/rcupdate.h>
45	#include <linux/cpu.h>
46	#include <linux/cpuset.h>
47	#include <linux/percpu.h>
48	#include <linux/kthread.h>
49	#include <linux/seq_file.h>
50	#include <linux/syscalls.h>
51	#include <linux/times.h>
52	#include <linux/tsacct_kern.h>
53	#include <linux/kprobes.h>
54	#include <linux/delayacct.h>
55	#include <asm/tlb.h>
56
57	#include <asm/unistd.h>
58
59	/*
60	* Scheduler clock - returns current time in nanosec units.
61	* This is default implementation.
62	* Architectures and sub-architectures can override this.
63	*/
64	unsigned long long __attribute__((weak)) sched_clock(void)
65	{
66	return (unsigned long long)jiffies * (1000000000 / HZ);
67	}
68
69	/*
70	* Convert user-nice values [ -20 ... 0 ... 19 ]
71	* to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],
72	* and back.
73	*/
74	#define NICE_TO_PRIO(nice) (MAX_RT_PRIO + (nice) + 20)
75	#define PRIO_TO_NICE(prio) ((prio) - MAX_RT_PRIO - 20)
76	#define TASK_NICE(p) PRIO_TO_NICE((p)->static_prio)
77
78	/*
79	* 'User priority' is the nice value converted to something we
80	* can work with better when scaling various scheduler parameters,
81	* it's a [ 0 ... 39 ] range.
82	*/
83	#define USER_PRIO(p) ((p)-MAX_RT_PRIO)
84	#define TASK_USER_PRIO(p) USER_PRIO((p)->static_prio)
85	#define MAX_USER_PRIO (USER_PRIO(MAX_PRIO))
86
87	/*
88	* Some helpers for converting nanosecond timing to jiffy resolution
89	*/
90	#define NS_TO_JIFFIES(TIME) ((TIME) / (1000000000 / HZ))
91	#define JIFFIES_TO_NS(TIME) ((TIME) * (1000000000 / HZ))
92
93	/*
94	* These are the 'tuning knobs' of the scheduler:
95	*
96	* Minimum timeslice is 5 msecs (or 1 jiffy, whichever is larger),
97	* default timeslice is 100 msecs, maximum timeslice is 800 msecs.
98	* Timeslices get refilled after they expire.
99	*/
100	#define MIN_TIMESLICE max(5 * HZ / 1000, 1)
101	#define DEF_TIMESLICE (100 * HZ / 1000)
102	#define ON_RUNQUEUE_WEIGHT 30
103	#define CHILD_PENALTY 95
104	#define PARENT_PENALTY 100
105	#define EXIT_WEIGHT 3
106	#define PRIO_BONUS_RATIO 25
107	#define MAX_BONUS (MAX_USER_PRIO * PRIO_BONUS_RATIO / 100)
108	#define INTERACTIVE_DELTA 2
109	#define MAX_SLEEP_AVG (DEF_TIMESLICE * MAX_BONUS)
110	#define STARVATION_LIMIT (MAX_SLEEP_AVG)
111	#define NS_MAX_SLEEP_AVG (JIFFIES_TO_NS(MAX_SLEEP_AVG))
112
113	/*
114	* If a task is 'interactive' then we reinsert it in the active
115	* array after it has expired its current timeslice. (it will not
116	* continue to run immediately, it will still roundrobin with
117	* other interactive tasks.)
118	*
119	* This part scales the interactivity limit depending on niceness.
120	*
121	* We scale it linearly, offset by the INTERACTIVE_DELTA delta.
122	* Here are a few examples of different nice levels:
123	*
124	* TASK_INTERACTIVE(-20): [1,1,1,1,1,1,1,1,1,0,0]
125	* TASK_INTERACTIVE(-10): [1,1,1,1,1,1,1,0,0,0,0]
126	* TASK_INTERACTIVE( 0): [1,1,1,1,0,0,0,0,0,0,0]
127	* TASK_INTERACTIVE( 10): [1,1,0,0,0,0,0,0,0,0,0]
128	* TASK_INTERACTIVE( 19): [0,0,0,0,0,0,0,0,0,0,0]
129	*
130	* (the X axis represents the possible -5 ... 0 ... +5 dynamic
131	* priority range a task can explore, a value of '1' means the
132	* task is rated interactive.)
133	*
134	* Ie. nice +19 tasks can never get 'interactive' enough to be
135	* reinserted into the active array. And only heavily CPU-hog nice -20
136	* tasks will be expired. Default nice 0 tasks are somewhere between,
137	* it takes some effort for them to get interactive, but it's not
138	* too hard.
139	*/
140
141	#define CURRENT_BONUS(p) \
142	(NS_TO_JIFFIES((p)->sleep_avg) * MAX_BONUS / \
143	MAX_SLEEP_AVG)
144
145	#define GRANULARITY (10 * HZ / 1000 ? : 1)
146
147	#ifdef CONFIG_SMP
148	#define TIMESLICE_GRANULARITY(p) (GRANULARITY * \
149	(1 << (((MAX_BONUS - CURRENT_BONUS(p)) ? : 1) - 1)) * \
150	num_online_cpus())
151	#else
152	#define TIMESLICE_GRANULARITY(p) (GRANULARITY * \
153	(1 << (((MAX_BONUS - CURRENT_BONUS(p)) ? : 1) - 1)))
154	#endif
155
156	#define SCALE(v1,v1_max,v2_max) \
157	(v1) * (v2_max) / (v1_max)
158
159	#define DELTA(p) \
160	(SCALE(TASK_NICE(p) + 20, 40, MAX_BONUS) - 20 * MAX_BONUS / 40 + \
161	INTERACTIVE_DELTA)
162
163	#define TASK_INTERACTIVE(p) \
164	((p)->prio <= (p)->static_prio - DELTA(p))
165
166	#define INTERACTIVE_SLEEP(p) \
167	(JIFFIES_TO_NS(MAX_SLEEP_AVG * \
168	(MAX_BONUS / 2 + DELTA((p)) + 1) / MAX_BONUS - 1))
169
170	#define TASK_PREEMPTS_CURR(p, rq) \
171	((p)->prio < (rq)->curr->prio)
172
173	#define SCALE_PRIO(x, prio) \
174	max(x * (MAX_PRIO - prio) / (MAX_USER_PRIO / 2), MIN_TIMESLICE)
175
176	static unsigned int static_prio_timeslice(int static_prio)
177	{
178	if (static_prio < NICE_TO_PRIO(0))
179	return SCALE_PRIO(DEF_TIMESLICE * 4, static_prio);
180	else
181	return SCALE_PRIO(DEF_TIMESLICE, static_prio);
182	}
183
184	/*
185	* task_timeslice() scales user-nice values [ -20 ... 0 ... 19 ]
186	* to time slice values: [800ms ... 100ms ... 5ms]
187	*
188	* The higher a thread's priority, the bigger timeslices
189	* it gets during one round of execution. But even the lowest
190	* priority thread gets MIN_TIMESLICE worth of execution time.
191	*/
192
193	static inline unsigned int task_timeslice(struct task_struct *p)
194	{
195	return static_prio_timeslice(p->static_prio);
196	}
197
198	/*
199	* These are the runqueue data structures:
200	*/
201
202	struct prio_array {
203	unsigned int nr_active;
204	DECLARE_BITMAP(bitmap, MAX_PRIO+1); /* include 1 bit for delimiter */
205	struct list_head queue[MAX_PRIO];
206	};
207
208	/*
209	* This is the main, per-CPU runqueue data structure.
210	*
211	* Locking rule: those places that want to lock multiple runqueues
212	* (such as the load balancing or the thread migration code), lock
213	* acquire operations must be ordered by ascending &runqueue.
214	*/
215	struct rq {
216	spinlock_t lock;
217
218	/*
219	* nr_running and cpu_load should be in the same cacheline because
220	* remote CPUs use both these fields when doing load calculation.
221	*/
222	unsigned long nr_running;
223	unsigned long raw_weighted_load;
224	#ifdef CONFIG_SMP
225	unsigned long cpu_load[3];
226	#endif
227	unsigned long long nr_switches;
228
229	/*
230	* This is part of a global counter where only the total sum
231	* over all CPUs matters. A task can increase this counter on
232	* one CPU and if it got migrated afterwards it may decrease
233	* it on another CPU. Always updated under the runqueue lock:
234	*/
235	unsigned long nr_uninterruptible;
236
237	unsigned long expired_timestamp;
238	/* Cached timestamp set by update_cpu_clock() */
239	unsigned long long most_recent_timestamp;
240	struct task_struct curr, idle;
241	unsigned long next_balance;
242	struct mm_struct *prev_mm;
243	struct prio_array active, expired, arrays[2];
244	int best_expired_prio;
245	atomic_t nr_iowait;
246
247	#ifdef CONFIG_SMP
248	struct sched_domain *sd;
249
250	/* For active balancing */
251	int active_balance;
252	int push_cpu;
253	int cpu; /* cpu of this runqueue */
254
255	struct task_struct *migration_thread;
256	struct list_head migration_queue;
257	#endif
258
259	#ifdef CONFIG_SCHEDSTATS
260	/* latency stats */
261	struct sched_info rq_sched_info;
262
263	/* sys_sched_yield() stats */
264	unsigned long yld_exp_empty;
265	unsigned long yld_act_empty;
266	unsigned long yld_both_empty;
267	unsigned long yld_cnt;
268
269	/* schedule() stats */
270	unsigned long sched_switch;
271	unsigned long sched_cnt;
272	unsigned long sched_goidle;
273
274	/* try_to_wake_up() stats */
275	unsigned long ttwu_cnt;
276	unsigned long ttwu_local;
277	#endif
278	struct lock_class_key rq_lock_key;
279	};
280
281	static DEFINE_PER_CPU(struct rq, runqueues);
282
283	static inline int cpu_of(struct rq *rq)
284	{
285	#ifdef CONFIG_SMP
286	return rq->cpu;
287	#else
288	return 0;
289	#endif
290	}
291
292	/*
293	* The domain tree (rq->sd) is protected by RCU's quiescent state transition.
294	* See detach_destroy_domains: synchronize_sched for details.
295	*
296	* The domain tree of any CPU may only be accessed from within
297	* preempt-disabled sections.
298	*/
299	#define for_each_domain(cpu, __sd) \
300	for (__sd = rcu_dereference(cpu_rq(cpu)->sd); __sd; __sd = __sd->parent)
301
302	#define cpu_rq(cpu) (&per_cpu(runqueues, (cpu)))
303	#define this_rq() (&__get_cpu_var(runqueues))
304	#define task_rq(p) cpu_rq(task_cpu(p))
305	#define cpu_curr(cpu) (cpu_rq(cpu)->curr)
306
307	#ifndef prepare_arch_switch
308	# define prepare_arch_switch(next) do { } while (0)
309	#endif
310	#ifndef finish_arch_switch
311	# define finish_arch_switch(prev) do { } while (0)
312	#endif
313
314	#ifndef __ARCH_WANT_UNLOCKED_CTXSW
315	static inline int task_running(struct rq rq, struct task_struct p)
316	{
317	return rq->curr == p;
318	}
319
320	static inline void prepare_lock_switch(struct rq rq, struct task_struct next)
321	{
322	}
323
324	static inline void finish_lock_switch(struct rq rq, struct task_struct prev)
325	{
326	#ifdef CONFIG_DEBUG_SPINLOCK
327	/* this is a valid case when another task releases the spinlock */
328	rq->lock.owner = current;
329	#endif
330	/*
331	* If we are tracking spinlock dependencies then we have to
332	* fix up the runqueue lock - which gets 'carried over' from
333	* prev into current:
334	*/
335	spin_acquire(&rq->lock.dep_map, 0, 0, _THIS_IP_);
336
337	spin_unlock_irq(&rq->lock);
338	}
339
340	#else /* __ARCH_WANT_UNLOCKED_CTXSW */
341	static inline int task_running(struct rq rq, struct task_struct p)
342	{
343	#ifdef CONFIG_SMP
344	return p->oncpu;
345	#else
346	return rq->curr == p;
347	#endif
348	}
349
350	static inline void prepare_lock_switch(struct rq rq, struct task_struct next)
351	{
352	#ifdef CONFIG_SMP
353	/*
354	* We can optimise this out completely for !SMP, because the
355	* SMP rebalancing from interrupt is the only thing that cares
356	* here.
357	*/
358	next->oncpu = 1;
359	#endif
360	#ifdef __ARCH_WANT_INTERRUPTS_ON_CTXSW
361	spin_unlock_irq(&rq->lock);
362	#else
363	spin_unlock(&rq->lock);
364	#endif
365	}
366
367	static inline void finish_lock_switch(struct rq rq, struct task_struct prev)
368	{
369	#ifdef CONFIG_SMP
370	/*
371	* After ->oncpu is cleared, the task can be moved to a different CPU.
372	* We must ensure this doesn't happen until the switch is completely
373	* finished.
374	*/
375	smp_wmb();
376	prev->oncpu = 0;
377	#endif
378	#ifndef __ARCH_WANT_INTERRUPTS_ON_CTXSW
379	local_irq_enable();
380	#endif
381	}
382	#endif /* __ARCH_WANT_UNLOCKED_CTXSW */
383
384	/*
385	* __task_rq_lock - lock the runqueue a given task resides on.
386	* Must be called interrupts disabled.
387	*/
388	static inline struct rq __task_rq_lock(struct task_struct p)
389	__acquires(rq->lock)
390	{
391	struct rq *rq;
392
393	repeat_lock_task:
394	rq = task_rq(p);
395	spin_lock(&rq->lock);
396	if (unlikely(rq != task_rq(p))) {
397	spin_unlock(&rq->lock);
398	goto repeat_lock_task;
399	}
400	return rq;
401	}
402
403	/*
404	* task_rq_lock - lock the runqueue a given task resides on and disable
405	* interrupts. Note the ordering: we can safely lookup the task_rq without
406	* explicitly disabling preemption.
407	*/
408	static struct rq task_rq_lock(struct task_struct p, unsigned long *flags)
409	__acquires(rq->lock)
410	{
411	struct rq *rq;
412
413	repeat_lock_task:
414	local_irq_save(*flags);
415	rq = task_rq(p);
416	spin_lock(&rq->lock);
417	if (unlikely(rq != task_rq(p))) {
418	spin_unlock_irqrestore(&rq->lock, *flags);
419	goto repeat_lock_task;
420	}
421	return rq;
422	}
423
424	static inline void __task_rq_unlock(struct rq *rq)
425	__releases(rq->lock)
426	{
427	spin_unlock(&rq->lock);
428	}
429
430	static inline void task_rq_unlock(struct rq rq, unsigned long flags)
431	__releases(rq->lock)
432	{
433	spin_unlock_irqrestore(&rq->lock, *flags);
434	}
435
436	#ifdef CONFIG_SCHEDSTATS
437	/*
438	* bump this up when changing the output format or the meaning of an existing
439	* format, so that tools can adapt (or abort)
440	*/
441	#define SCHEDSTAT_VERSION 14
442
443	static int show_schedstat(struct seq_file seq, void v)
444	{
445	int cpu;
446
447	seq_printf(seq, "version %d\n", SCHEDSTAT_VERSION);
448	seq_printf(seq, "timestamp %lu\n", jiffies);
449	for_each_online_cpu(cpu) {
450	struct rq *rq = cpu_rq(cpu);
451	#ifdef CONFIG_SMP
452	struct sched_domain *sd;
453	int dcnt = 0;
454	#endif
455
456	/* runqueue-specific stats */
457	seq_printf(seq,
458	"cpu%d %lu %lu %lu %lu %lu %lu %lu %lu %lu %lu %lu %lu",
459	cpu, rq->yld_both_empty,
460	rq->yld_act_empty, rq->yld_exp_empty, rq->yld_cnt,
461	rq->sched_switch, rq->sched_cnt, rq->sched_goidle,
462	rq->ttwu_cnt, rq->ttwu_local,
463	rq->rq_sched_info.cpu_time,
464	rq->rq_sched_info.run_delay, rq->rq_sched_info.pcnt);
465
466	seq_printf(seq, "\n");
467
468	#ifdef CONFIG_SMP
469	/* domain-specific stats */
470	preempt_disable();
471	for_each_domain(cpu, sd) {
472	enum idle_type itype;
473	char mask_str[NR_CPUS];
474
475	cpumask_scnprintf(mask_str, NR_CPUS, sd->span);
476	seq_printf(seq, "domain%d %s", dcnt++, mask_str);
477	for (itype = SCHED_IDLE; itype < MAX_IDLE_TYPES;
478	itype++) {
479	seq_printf(seq, " %lu %lu %lu %lu %lu %lu %lu "
480	"%lu",
481	sd->lb_cnt[itype],
482	sd->lb_balanced[itype],
483	sd->lb_failed[itype],
484	sd->lb_imbalance[itype],
485	sd->lb_gained[itype],
486	sd->lb_hot_gained[itype],
487	sd->lb_nobusyq[itype],
488	sd->lb_nobusyg[itype]);
489	}
490	seq_printf(seq, " %lu %lu %lu %lu %lu %lu %lu %lu %lu"
491	" %lu %lu %lu\n",
492	sd->alb_cnt, sd->alb_failed, sd->alb_pushed,
493	sd->sbe_cnt, sd->sbe_balanced, sd->sbe_pushed,
494	sd->sbf_cnt, sd->sbf_balanced, sd->sbf_pushed,
495	sd->ttwu_wake_remote, sd->ttwu_move_affine,
496	sd->ttwu_move_balance);
497	}
498	preempt_enable();
499	#endif
500	}
501	return 0;
502	}
503
504	static int schedstat_open(struct inode inode, struct file file)
505	{
506	unsigned int size = PAGE_SIZE * (1 + num_online_cpus() / 32);
507	char *buf = kmalloc(size, GFP_KERNEL);
508	struct seq_file *m;
509	int res;
510
511	if (!buf)
512	return -ENOMEM;
513	res = single_open(file, show_schedstat, NULL);
514	if (!res) {
515	m = file->private_data;
516	m->buf = buf;
517	m->size = size;
518	} else
519	kfree(buf);
520	return res;
521	}
522
523	const struct file_operations proc_schedstat_operations = {
524	.open = schedstat_open,
525	.read = seq_read,
526	.llseek = seq_lseek,
527	.release = single_release,
528	};
529
530	/*
531	* Expects runqueue lock to be held for atomicity of update
532	*/
533	static inline void
534	rq_sched_info_arrive(struct rq *rq, unsigned long delta_jiffies)
535	{
536	if (rq) {
537	rq->rq_sched_info.run_delay += delta_jiffies;
538	rq->rq_sched_info.pcnt++;
539	}
540	}
541
542	/*
543	* Expects runqueue lock to be held for atomicity of update
544	*/
545	static inline void
546	rq_sched_info_depart(struct rq *rq, unsigned long delta_jiffies)
547	{
548	if (rq)
549	rq->rq_sched_info.cpu_time += delta_jiffies;
550	}
551	# define schedstat_inc(rq, field) do { (rq)->field++; } while (0)
552	# define schedstat_add(rq, field, amt) do { (rq)->field += (amt); } while (0)
553	#else /* !CONFIG_SCHEDSTATS */
554	static inline void
555	rq_sched_info_arrive(struct rq *rq, unsigned long delta_jiffies)
556	{}
557	static inline void
558	rq_sched_info_depart(struct rq *rq, unsigned long delta_jiffies)
559	{}
560	# define schedstat_inc(rq, field) do { } while (0)
561	# define schedstat_add(rq, field, amt) do { } while (0)
562	#endif
563
564	/*
565	* this_rq_lock - lock this runqueue and disable interrupts.
566	*/
567	static inline struct rq *this_rq_lock(void)
568	__acquires(rq->lock)
569	{
570	struct rq *rq;
571
572	local_irq_disable();
573	rq = this_rq();
574	spin_lock(&rq->lock);
575
576	return rq;
577	}
578
579	#if defined(CONFIG_SCHEDSTATS) \|\| defined(CONFIG_TASK_DELAY_ACCT)
580	/*
581	* Called when a process is dequeued from the active array and given
582	* the cpu. We should note that with the exception of interactive
583	* tasks, the expired queue will become the active queue after the active
584	* queue is empty, without explicitly dequeuing and requeuing tasks in the
585	* expired queue. (Interactive tasks may be requeued directly to the
586	* active queue, thus delaying tasks in the expired queue from running;
587	* see scheduler_tick()).
588	*
589	* This function is only called from sched_info_arrive(), rather than
590	* dequeue_task(). Even though a task may be queued and dequeued multiple
591	* times as it is shuffled about, we're really interested in knowing how
592	* long it was from the first time it was queued to the time that it
593	* finally hit a cpu.
594	*/
595	static inline void sched_info_dequeued(struct task_struct *t)
596	{
597	t->sched_info.last_queued = 0;
598	}
599
600	/*
601	* Called when a task finally hits the cpu. We can now calculate how
602	* long it was waiting to run. We also note when it began so that we
603	* can keep stats on how long its timeslice is.
604	*/
605	static void sched_info_arrive(struct task_struct *t)
606	{
607	unsigned long now = jiffies, delta_jiffies = 0;
608
609	if (t->sched_info.last_queued)
610	delta_jiffies = now - t->sched_info.last_queued;
611	sched_info_dequeued(t);
612	t->sched_info.run_delay += delta_jiffies;
613	t->sched_info.last_arrival = now;
614	t->sched_info.pcnt++;
615
616	rq_sched_info_arrive(task_rq(t), delta_jiffies);
617	}
618
619	/*
620	* Called when a process is queued into either the active or expired
621	* array. The time is noted and later used to determine how long we
622	* had to wait for us to reach the cpu. Since the expired queue will
623	* become the active queue after active queue is empty, without dequeuing
624	* and requeuing any tasks, we are interested in queuing to either. It
625	* is unusual but not impossible for tasks to be dequeued and immediately
626	* requeued in the same or another array: this can happen in sched_yield(),
627	* set_user_nice(), and even load_balance() as it moves tasks from runqueue
628	* to runqueue.
629	*
630	* This function is only called from enqueue_task(), but also only updates
631	* the timestamp if it is already not set. It's assumed that
632	* sched_info_dequeued() will clear that stamp when appropriate.
633	*/
634	static inline void sched_info_queued(struct task_struct *t)
635	{
636	if (unlikely(sched_info_on()))
637	if (!t->sched_info.last_queued)
638	t->sched_info.last_queued = jiffies;
639	}
640
641	/*
642	* Called when a process ceases being the active-running process, either
643	* voluntarily or involuntarily. Now we can calculate how long we ran.
644	*/
645	static inline void sched_info_depart(struct task_struct *t)
646	{
647	unsigned long delta_jiffies = jiffies - t->sched_info.last_arrival;
648
649	t->sched_info.cpu_time += delta_jiffies;
650	rq_sched_info_depart(task_rq(t), delta_jiffies);
651	}
652
653	/*
654	* Called when tasks are switched involuntarily due, typically, to expiring
655	* their time slice. (This may also be called when switching to or from
656	* the idle task.) We are only called when prev != next.
657	*/
658	static inline void
659	__sched_info_switch(struct task_struct prev, struct task_struct next)
660	{
661	struct rq *rq = task_rq(prev);
662
663	/*
664	* prev now departs the cpu. It's not interesting to record
665	* stats about how efficient we were at scheduling the idle
666	* process, however.
667	*/
668	if (prev != rq->idle)
669	sched_info_depart(prev);
670
671	if (next != rq->idle)
672	sched_info_arrive(next);
673	}
674	static inline void
675	sched_info_switch(struct task_struct prev, struct task_struct next)
676	{
677	if (unlikely(sched_info_on()))
678	__sched_info_switch(prev, next);
679	}
680	#else
681	#define sched_info_queued(t) do { } while (0)
682	#define sched_info_switch(t, next) do { } while (0)
683	#endif /* CONFIG_SCHEDSTATS \|\| CONFIG_TASK_DELAY_ACCT */
684
685	/*
686	* Adding/removing a task to/from a priority array:
687	*/
688	static void dequeue_task(struct task_struct p, struct prio_array array)
689	{
690	array->nr_active--;
691	list_del(&p->run_list);
692	if (list_empty(array->queue + p->prio))
693	__clear_bit(p->prio, array->bitmap);
694	}
695
696	static void enqueue_task(struct task_struct p, struct prio_array array)
697	{
698	sched_info_queued(p);
699	list_add_tail(&p->run_list, array->queue + p->prio);
700	__set_bit(p->prio, array->bitmap);
701	array->nr_active++;
702	p->array = array;
703	}
704
705	/*
706	* Put task to the end of the run list without the overhead of dequeue
707	* followed by enqueue.
708	*/
709	static void requeue_task(struct task_struct p, struct prio_array array)
710	{
711	list_move_tail(&p->run_list, array->queue + p->prio);
712	}
713
714	static inline void
715	enqueue_task_head(struct task_struct p, struct prio_array array)
716	{
717	list_add(&p->run_list, array->queue + p->prio);
718	__set_bit(p->prio, array->bitmap);
719	array->nr_active++;
720	p->array = array;
721	}
722
723	/*
724	* __normal_prio - return the priority that is based on the static
725	* priority but is modified by bonuses/penalties.
726	*
727	* We scale the actual sleep average [0 .... MAX_SLEEP_AVG]
728	* into the -5 ... 0 ... +5 bonus/penalty range.
729	*
730	* We use 25% of the full 0...39 priority range so that:
731	*
732	* 1) nice +19 interactive tasks do not preempt nice 0 CPU hogs.
733	* 2) nice -20 CPU hogs do not get preempted by nice 0 tasks.
734	*
735	* Both properties are important to certain workloads.
736	*/
737
738	static inline int __normal_prio(struct task_struct *p)
739	{
740	int bonus, prio;
741
742	bonus = CURRENT_BONUS(p) - MAX_BONUS / 2;
743
744	prio = p->static_prio - bonus;
745	if (prio < MAX_RT_PRIO)
746	prio = MAX_RT_PRIO;
747	if (prio > MAX_PRIO-1)
748	prio = MAX_PRIO-1;
749	return prio;
750	}
751
752	/*
753	* To aid in avoiding the subversion of "niceness" due to uneven distribution
754	* of tasks with abnormal "nice" values across CPUs the contribution that
755	* each task makes to its run queue's load is weighted according to its
756	* scheduling class and "nice" value. For SCHED_NORMAL tasks this is just a
757	* scaled version of the new time slice allocation that they receive on time
758	* slice expiry etc.
759	*/
760
761	/*
762	* Assume: static_prio_timeslice(NICE_TO_PRIO(0)) == DEF_TIMESLICE
763	* If static_prio_timeslice() is ever changed to break this assumption then
764	* this code will need modification
765	*/
766	#define TIME_SLICE_NICE_ZERO DEF_TIMESLICE
767	#define LOAD_WEIGHT(lp) \
768	(((lp) * SCHED_LOAD_SCALE) / TIME_SLICE_NICE_ZERO)
769	#define PRIO_TO_LOAD_WEIGHT(prio) \
770	LOAD_WEIGHT(static_prio_timeslice(prio))
771	#define RTPRIO_TO_LOAD_WEIGHT(rp) \
772	(PRIO_TO_LOAD_WEIGHT(MAX_RT_PRIO) + LOAD_WEIGHT(rp))
773
774	static void set_load_weight(struct task_struct *p)
775	{
776	if (has_rt_policy(p)) {
777	#ifdef CONFIG_SMP
778	if (p == task_rq(p)->migration_thread)
779	/*
780	* The migration thread does the actual balancing.
781	* Giving its load any weight will skew balancing
782	* adversely.
783	*/
784	p->load_weight = 0;
785	else
786	#endif
787	p->load_weight = RTPRIO_TO_LOAD_WEIGHT(p->rt_priority);
788	} else
789	p->load_weight = PRIO_TO_LOAD_WEIGHT(p->static_prio);
790	}
791
792	static inline void
793	inc_raw_weighted_load(struct rq rq, const struct task_struct p)
794	{
795	rq->raw_weighted_load += p->load_weight;
796	}
797
798	static inline void
799	dec_raw_weighted_load(struct rq rq, const struct task_struct p)
800	{
801	rq->raw_weighted_load -= p->load_weight;
802	}
803
804	static inline void inc_nr_running(struct task_struct p, struct rq rq)
805	{
806	rq->nr_running++;
807	inc_raw_weighted_load(rq, p);
808	}
809
810	static inline void dec_nr_running(struct task_struct p, struct rq rq)
811	{
812	rq->nr_running--;
813	dec_raw_weighted_load(rq, p);
814	}
815
816	/*
817	* Calculate the expected normal priority: i.e. priority
818	* without taking RT-inheritance into account. Might be
819	* boosted by interactivity modifiers. Changes upon fork,
820	* setprio syscalls, and whenever the interactivity
821	* estimator recalculates.
822	*/
823	static inline int normal_prio(struct task_struct *p)
824	{
825	int prio;
826
827	if (has_rt_policy(p))
828	prio = MAX_RT_PRIO-1 - p->rt_priority;
829	else
830	prio = __normal_prio(p);
831	return prio;
832	}
833
834	/*
835	* Calculate the current priority, i.e. the priority
836	* taken into account by the scheduler. This value might
837	* be boosted by RT tasks, or might be boosted by
838	* interactivity modifiers. Will be RT if the task got
839	* RT-boosted. If not then it returns p->normal_prio.
840	*/
841	static int effective_prio(struct task_struct *p)
842	{
843	p->normal_prio = normal_prio(p);
844	/*
845	* If we are RT tasks or we were boosted to RT priority,
846	* keep the priority unchanged. Otherwise, update priority
847	* to the normal priority:
848	*/
849	if (!rt_prio(p->prio))
850	return p->normal_prio;
851	return p->prio;
852	}
853
854	/*
855	* __activate_task - move a task to the runqueue.
856	*/
857	static void __activate_task(struct task_struct p, struct rq rq)
858	{
859	struct prio_array *target = rq->active;
860
861	if (batch_task(p))
862	target = rq->expired;
863	enqueue_task(p, target);
864	inc_nr_running(p, rq);
865	}
866
867	/*
868	* __activate_idle_task - move idle task to the _front_ of runqueue.
869	*/
870	static inline void __activate_idle_task(struct task_struct p, struct rq rq)
871	{
872	enqueue_task_head(p, rq->active);
873	inc_nr_running(p, rq);
874	}
875
876	/*
877	* Recalculate p->normal_prio and p->prio after having slept,
878	* updating the sleep-average too:
879	*/
880	static int recalc_task_prio(struct task_struct *p, unsigned long long now)
881	{
882	/* Caller must always ensure 'now >= p->timestamp' */
883	unsigned long sleep_time = now - p->timestamp;
884
885	if (batch_task(p))
886	sleep_time = 0;
887
888	if (likely(sleep_time > 0)) {
889	/*
890	* This ceiling is set to the lowest priority that would allow
891	* a task to be reinserted into the active array on timeslice
892	* completion.
893	*/
894	unsigned long ceiling = INTERACTIVE_SLEEP(p);
895
896	if (p->mm && sleep_time > ceiling && p->sleep_avg < ceiling) {
897	/*
898	* Prevents user tasks from achieving best priority
899	* with one single large enough sleep.
900	*/
901	p->sleep_avg = ceiling;
902	/*
903	* Using INTERACTIVE_SLEEP() as a ceiling places a
904	* nice(0) task 1ms sleep away from promotion, and
905	* gives it 700ms to round-robin with no chance of
906	* being demoted. This is more than generous, so
907	* mark this sleep as non-interactive to prevent the
908	* on-runqueue bonus logic from intervening should
909	* this task not receive cpu immediately.
910	*/
911	p->sleep_type = SLEEP_NONINTERACTIVE;
912	} else {
913	/*
914	* Tasks waking from uninterruptible sleep are
915	* limited in their sleep_avg rise as they
916	* are likely to be waiting on I/O
917	*/
918	if (p->sleep_type == SLEEP_NONINTERACTIVE && p->mm) {
919	if (p->sleep_avg >= ceiling)
920	sleep_time = 0;
921	else if (p->sleep_avg + sleep_time >=
922	ceiling) {
923	p->sleep_avg = ceiling;
924	sleep_time = 0;
925	}
926	}
927
928	/*
929	* This code gives a bonus to interactive tasks.
930	*
931	* The boost works by updating the 'average sleep time'
932	* value here, based on ->timestamp. The more time a
933	* task spends sleeping, the higher the average gets -
934	* and the higher the priority boost gets as well.
935	*/
936	p->sleep_avg += sleep_time;
937
938	}
939	if (p->sleep_avg > NS_MAX_SLEEP_AVG)
940	p->sleep_avg = NS_MAX_SLEEP_AVG;
941	}
942
943	return effective_prio(p);
944	}
945
946	/*
947	* activate_task - move a task to the runqueue and do priority recalculation
948	*
949	* Update all the scheduling statistics stuff. (sleep average
950	* calculation, priority modifiers, etc.)
951	*/
952	static void activate_task(struct task_struct p, struct rq rq, int local)
953	{
954	unsigned long long now;
955
956	if (rt_task(p))
957	goto out;
958
959	now = sched_clock();
960	#ifdef CONFIG_SMP
961	if (!local) {
962	/* Compensate for drifting sched_clock */
963	struct rq *this_rq = this_rq();
964	now = (now - this_rq->most_recent_timestamp)
965	+ rq->most_recent_timestamp;
966	}
967	#endif
968
969	/*
970	* Sleep time is in units of nanosecs, so shift by 20 to get a
971	* milliseconds-range estimation of the amount of time that the task
972	* spent sleeping:
973	*/
974	if (unlikely(prof_on == SLEEP_PROFILING)) {
975	if (p->state == TASK_UNINTERRUPTIBLE)
976	profile_hits(SLEEP_PROFILING, (void *)get_wchan(p),
977	(now - p->timestamp) >> 20);
978	}
979
980	p->prio = recalc_task_prio(p, now);
981
982	/*
983	* This checks to make sure it's not an uninterruptible task
984	* that is now waking up.
985	*/
986	if (p->sleep_type == SLEEP_NORMAL) {
987	/*
988	* Tasks which were woken up by interrupts (ie. hw events)
989	* are most likely of interactive nature. So we give them
990	* the credit of extending their sleep time to the period
991	* of time they spend on the runqueue, waiting for execution
992	* on a CPU, first time around:
993	*/
994	if (in_interrupt())
995	p->sleep_type = SLEEP_INTERRUPTED;
996	else {
997	/*
998	* Normal first-time wakeups get a credit too for
999	* on-runqueue time, but it will be weighted down:
1000	*/
1001	p->sleep_type = SLEEP_INTERACTIVE;
1002	}
1003	}
1004	p->timestamp = now;
1005	out:
1006	__activate_task(p, rq);
1007	}
1008
1009	/*
1010	* deactivate_task - remove a task from the runqueue.
1011	*/
1012	static void deactivate_task(struct task_struct p, struct rq rq)
1013	{
1014	dec_nr_running(p, rq);
1015	dequeue_task(p, p->array);
1016	p->array = NULL;
1017	}
1018
1019	/*
1020	* resched_task - mark a task 'to be rescheduled now'.
1021	*
1022	* On UP this means the setting of the need_resched flag, on SMP it
1023	* might also involve a cross-CPU call to trigger the scheduler on
1024	* the target CPU.
1025	*/
1026	#ifdef CONFIG_SMP
1027
1028	#ifndef tsk_is_polling
1029	#define tsk_is_polling(t) test_tsk_thread_flag(t, TIF_POLLING_NRFLAG)
1030	#endif
1031
1032	static void resched_task(struct task_struct *p)
1033	{
1034	int cpu;
1035
1036	assert_spin_locked(&task_rq(p)->lock);
1037
1038	if (unlikely(test_tsk_thread_flag(p, TIF_NEED_RESCHED)))
1039	return;
1040
1041	set_tsk_thread_flag(p, TIF_NEED_RESCHED);
1042
1043	cpu = task_cpu(p);
1044	if (cpu == smp_processor_id())
1045	return;
1046
1047	/* NEED_RESCHED must be visible before we test polling */
1048	smp_mb();
1049	if (!tsk_is_polling(p))
1050	smp_send_reschedule(cpu);
1051	}
1052	#else
1053	static inline void resched_task(struct task_struct *p)
1054	{
1055	assert_spin_locked(&task_rq(p)->lock);
1056	set_tsk_need_resched(p);
1057	}
1058	#endif
1059
1060	/**
1061	* task_curr - is this task currently executing on a CPU?
1062	* @p: the task in question.
1063	*/
1064	inline int task_curr(const struct task_struct *p)
1065	{
1066	return cpu_curr(task_cpu(p)) == p;
1067	}
1068
1069	/* Used instead of source_load when we know the type == 0 */
1070	unsigned long weighted_cpuload(const int cpu)
1071	{
1072	return cpu_rq(cpu)->raw_weighted_load;
1073	}
1074
1075	#ifdef CONFIG_SMP
1076	struct migration_req {
1077	struct list_head list;
1078
1079	struct task_struct *task;
1080	int dest_cpu;
1081
1082	struct completion done;
1083	};
1084
1085	/*
1086	* The task's runqueue lock must be held.
1087	* Returns true if you have to wait for migration thread.
1088	*/
1089	static int
1090	migrate_task(struct task_struct p, int dest_cpu, struct migration_req req)
1091	{
1092	struct rq *rq = task_rq(p);
1093
1094	/*
1095	* If the task is not on a runqueue (and not running), then
1096	* it is sufficient to simply update the task's cpu field.
1097	*/
1098	if (!p->array && !task_running(rq, p)) {
1099	set_task_cpu(p, dest_cpu);
1100	return 0;
1101	}
1102
1103	init_completion(&req->done);
1104	req->task = p;
1105	req->dest_cpu = dest_cpu;
1106	list_add(&req->list, &rq->migration_queue);
1107
1108	return 1;
1109	}
1110
1111	/*
1112	* wait_task_inactive - wait for a thread to unschedule.
1113	*
1114	* The caller must ensure that the task will unschedule sometime soon,
1115	* else this function might spin for a long time. This function can't
1116	* be called with interrupts off, or it may introduce deadlock with
1117	* smp_call_function() if an IPI is sent by the same process we are
1118	* waiting to become inactive.
1119	*/
1120	void wait_task_inactive(struct task_struct *p)
1121	{
1122	unsigned long flags;
1123	struct rq *rq;
1124	int preempted;
1125
1126	repeat:
1127	rq = task_rq_lock(p, &flags);
1128	/* Must be off runqueue entirely, not preempted. */
1129	if (unlikely(p->array \|\| task_running(rq, p))) {
1130	/* If it's preempted, we yield. It could be a while. */
1131	preempted = !task_running(rq, p);
1132	task_rq_unlock(rq, &flags);
1133	cpu_relax();
1134	if (preempted)
1135	yield();
1136	goto repeat;
1137	}
1138	task_rq_unlock(rq, &flags);
1139	}
1140
1141	/***
1142	* kick_process - kick a running thread to enter/exit the kernel
1143	* @p: the to-be-kicked thread
1144	*
1145	* Cause a process which is running on another CPU to enter
1146	* kernel-mode, without any delay. (to get signals handled.)
1147	*
1148	* NOTE: this function doesnt have to take the runqueue lock,
1149	* because all it wants to ensure is that the remote task enters
1150	* the kernel. If the IPI races and the task has been migrated
1151	* to another CPU then no harm is done and the purpose has been
1152	* achieved as well.
1153	*/
1154	void kick_process(struct task_struct *p)
1155	{
1156	int cpu;
1157
1158	preempt_disable();
1159	cpu = task_cpu(p);
1160	if ((cpu != smp_processor_id()) && task_curr(p))
1161	smp_send_reschedule(cpu);
1162	preempt_enable();
1163	}
1164
1165	/*
1166	* Return a low guess at the load of a migration-source cpu weighted
1167	* according to the scheduling class and "nice" value.
1168	*
1169	* We want to under-estimate the load of migration sources, to
1170	* balance conservatively.
1171	*/
1172	static inline unsigned long source_load(int cpu, int type)
1173	{
1174	struct rq *rq = cpu_rq(cpu);
1175
1176	if (type == 0)
1177	return rq->raw_weighted_load;
1178
1179	return min(rq->cpu_load[type-1], rq->raw_weighted_load);
1180	}
1181
1182	/*
1183	* Return a high guess at the load of a migration-target cpu weighted
1184	* according to the scheduling class and "nice" value.
1185	*/
1186	static inline unsigned long target_load(int cpu, int type)
1187	{
1188	struct rq *rq = cpu_rq(cpu);
1189
1190	if (type == 0)
1191	return rq->raw_weighted_load;
1192
1193	return max(rq->cpu_load[type-1], rq->raw_weighted_load);
1194	}
1195
1196	/*
1197	* Return the average load per task on the cpu's run queue
1198	*/
1199	static inline unsigned long cpu_avg_load_per_task(int cpu)
1200	{
1201	struct rq *rq = cpu_rq(cpu);
1202	unsigned long n = rq->nr_running;
1203
1204	return n ? rq->raw_weighted_load / n : SCHED_LOAD_SCALE;
1205	}
1206
1207	/*
1208	* find_idlest_group finds and returns the least busy CPU group within the
1209	* domain.
1210	*/
1211	static struct sched_group *
1212	find_idlest_group(struct sched_domain sd, struct task_struct p, int this_cpu)
1213	{
1214	struct sched_group idlest = NULL, this = NULL, *group = sd->groups;
1215	unsigned long min_load = ULONG_MAX, this_load = 0;
1216	int load_idx = sd->forkexec_idx;
1217	int imbalance = 100 + (sd->imbalance_pct-100)/2;
1218
1219	do {
1220	unsigned long load, avg_load;
1221	int local_group;
1222	int i;
1223
1224	/* Skip over this group if it has no CPUs allowed */
1225	if (!cpus_intersects(group->cpumask, p->cpus_allowed))
1226	goto nextgroup;
1227
1228	local_group = cpu_isset(this_cpu, group->cpumask);
1229
1230	/* Tally up the load of all CPUs in the group */
1231	avg_load = 0;
1232
1233	for_each_cpu_mask(i, group->cpumask) {
1234	/* Bias balancing toward cpus of our domain */
1235	if (local_group)
1236	load = source_load(i, load_idx);
1237	else
1238	load = target_load(i, load_idx);
1239
1240	avg_load += load;
1241	}
1242
1243	/* Adjust by relative CPU power of the group */
1244	avg_load = (avg_load * SCHED_LOAD_SCALE) / group->cpu_power;
1245
1246	if (local_group) {
1247	this_load = avg_load;
1248	this = group;
1249	} else if (avg_load < min_load) {
1250	min_load = avg_load;
1251	idlest = group;
1252	}
1253	nextgroup:
1254	group = group->next;
1255	} while (group != sd->groups);
1256
1257	if (!idlest \|\| 100this_load < imbalancemin_load)
1258	return NULL;
1259	return idlest;
1260	}
1261
1262	/*
1263	* find_idlest_cpu - find the idlest cpu among the cpus in group.
1264	*/
1265	static int
1266	find_idlest_cpu(struct sched_group group, struct task_struct p, int this_cpu)
1267	{
1268	cpumask_t tmp;
1269	unsigned long load, min_load = ULONG_MAX;
1270	int idlest = -1;
1271	int i;
1272
1273	/* Traverse only the allowed CPUs */
1274	cpus_and(tmp, group->cpumask, p->cpus_allowed);
1275
1276	for_each_cpu_mask(i, tmp) {
1277	load = weighted_cpuload(i);
1278
1279	if (load < min_load \|\| (load == min_load && i == this_cpu)) {
1280	min_load = load;
1281	idlest = i;
1282	}
1283	}
1284
1285	return idlest;
1286	}
1287
1288	/*
1289	* sched_balance_self: balance the current task (running on cpu) in domains
1290	* that have the 'flag' flag set. In practice, this is SD_BALANCE_FORK and
1291	* SD_BALANCE_EXEC.
1292	*
1293	* Balance, ie. select the least loaded group.
1294	*
1295	* Returns the target CPU number, or the same CPU if no balancing is needed.
1296	*
1297	* preempt must be disabled.
1298	*/
1299	static int sched_balance_self(int cpu, int flag)
1300	{
1301	struct task_struct *t = current;
1302	struct sched_domain tmp, sd = NULL;
1303
1304	for_each_domain(cpu, tmp) {
1305	/*
1306	* If power savings logic is enabled for a domain, stop there.
1307	*/
1308	if (tmp->flags & SD_POWERSAVINGS_BALANCE)
1309	break;
1310	if (tmp->flags & flag)
1311	sd = tmp;
1312	}
1313
1314	while (sd) {
1315	cpumask_t span;
1316	struct sched_group *group;
1317	int new_cpu, weight;
1318
1319	if (!(sd->flags & flag)) {
1320	sd = sd->child;
1321	continue;
1322	}
1323
1324	span = sd->span;
1325	group = find_idlest_group(sd, t, cpu);
1326	if (!group) {
1327	sd = sd->child;
1328	continue;
1329	}
1330
1331	new_cpu = find_idlest_cpu(group, t, cpu);
1332	if (new_cpu == -1 \|\| new_cpu == cpu) {
1333	/* Now try balancing at a lower domain level of cpu */
1334	sd = sd->child;
1335	continue;
1336	}
1337
1338	/* Now try balancing at a lower domain level of new_cpu */
1339	cpu = new_cpu;
1340	sd = NULL;
1341	weight = cpus_weight(span);
1342	for_each_domain(cpu, tmp) {
1343	if (weight <= cpus_weight(tmp->span))
1344	break;
1345	if (tmp->flags & flag)
1346	sd = tmp;
1347	}
1348	/* while loop will break here if sd == NULL */
1349	}
1350
1351	return cpu;
1352	}
1353
1354	#endif /* CONFIG_SMP */
1355
1356	/*
1357	* wake_idle() will wake a task on an idle cpu if task->cpu is
1358	* not idle and an idle cpu is available. The span of cpus to
1359	* search starts with cpus closest then further out as needed,
1360	* so we always favor a closer, idle cpu.
1361	*
1362	* Returns the CPU we should wake onto.
1363	*/
1364	#if defined(ARCH_HAS_SCHED_WAKE_IDLE)
1365	static int wake_idle(int cpu, struct task_struct *p)
1366	{
1367	cpumask_t tmp;
1368	struct sched_domain *sd;
1369	int i;
1370
1371	if (idle_cpu(cpu))
1372	return cpu;
1373
1374	for_each_domain(cpu, sd) {
1375	if (sd->flags & SD_WAKE_IDLE) {
1376	cpus_and(tmp, sd->span, p->cpus_allowed);
1377	for_each_cpu_mask(i, tmp) {
1378	if (idle_cpu(i))
1379	return i;
1380	}
1381	}
1382	else
1383	break;
1384	}
1385	return cpu;
1386	}
1387	#else
1388	static inline int wake_idle(int cpu, struct task_struct *p)
1389	{
1390	return cpu;
1391	}
1392	#endif
1393
1394	/***
1395	* try_to_wake_up - wake up a thread
1396	* @p: the to-be-woken-up thread
1397	* @state: the mask of task states that can be woken
1398	* @sync: do a synchronous wakeup?
1399	*
1400	* Put it on the run-queue if it's not already there. The "current"
1401	* thread is always on the run-queue (except when the actual
1402	* re-schedule is in progress), and as such you're allowed to do
1403	* the simpler "current->state = TASK_RUNNING" to mark yourself
1404	* runnable without the overhead of this.
1405	*
1406	* returns failure only if the task is already active.
1407	*/
1408	static int try_to_wake_up(struct task_struct *p, unsigned int state, int sync)
1409	{
1410	int cpu, this_cpu, success = 0;
1411	unsigned long flags;
1412	long old_state;
1413	struct rq *rq;
1414	#ifdef CONFIG_SMP
1415	struct sched_domain sd, this_sd = NULL;
1416	unsigned long load, this_load;
1417	int new_cpu;
1418	#endif
1419
1420	rq = task_rq_lock(p, &flags);
1421	old_state = p->state;
1422	if (!(old_state & state))
1423	goto out;
1424
1425	if (p->array)
1426	goto out_running;
1427
1428	cpu = task_cpu(p);
1429	this_cpu = smp_processor_id();
1430
1431	#ifdef CONFIG_SMP
1432	if (unlikely(task_running(rq, p)))
1433	goto out_activate;
1434
1435	new_cpu = cpu;
1436
1437	schedstat_inc(rq, ttwu_cnt);
1438	if (cpu == this_cpu) {
1439	schedstat_inc(rq, ttwu_local);
1440	goto out_set_cpu;
1441	}
1442
1443	for_each_domain(this_cpu, sd) {
1444	if (cpu_isset(cpu, sd->span)) {
1445	schedstat_inc(sd, ttwu_wake_remote);
1446	this_sd = sd;
1447	break;
1448	}
1449	}
1450
1451	if (unlikely(!cpu_isset(this_cpu, p->cpus_allowed)))
1452	goto out_set_cpu;
1453
1454	/*
1455	* Check for affine wakeup and passive balancing possibilities.
1456	*/
1457	if (this_sd) {
1458	int idx = this_sd->wake_idx;
1459	unsigned int imbalance;
1460
1461	imbalance = 100 + (this_sd->imbalance_pct - 100) / 2;
1462
1463	load = source_load(cpu, idx);
1464	this_load = target_load(this_cpu, idx);
1465
1466	new_cpu = this_cpu; /* Wake to this CPU if we can */
1467
1468	if (this_sd->flags & SD_WAKE_AFFINE) {
1469	unsigned long tl = this_load;
1470	unsigned long tl_per_task;
1471
1472	tl_per_task = cpu_avg_load_per_task(this_cpu);
1473
1474	/*
1475	* If sync wakeup then subtract the (maximum possible)
1476	* effect of the currently running task from the load
1477	* of the current CPU:
1478	*/
1479	if (sync)
1480	tl -= current->load_weight;
1481
1482	if ((tl <= load &&
1483	tl + target_load(cpu, idx) <= tl_per_task) \|\|
1484	100(tl + p->load_weight) <= imbalanceload) {
1485	/*
1486	* This domain has SD_WAKE_AFFINE and
1487	* p is cache cold in this domain, and
1488	* there is no bad imbalance.
1489	*/
1490	schedstat_inc(this_sd, ttwu_move_affine);
1491	goto out_set_cpu;
1492	}
1493	}
1494
1495	/*
1496	* Start passive balancing when half the imbalance_pct
1497	* limit is reached.
1498	*/
1499	if (this_sd->flags & SD_WAKE_BALANCE) {
1500	if (imbalancethis_load <= 100load) {
1501	schedstat_inc(this_sd, ttwu_move_balance);
1502	goto out_set_cpu;
1503	}
1504	}
1505	}
1506
1507	new_cpu = cpu; /* Could not wake to this_cpu. Wake to cpu instead */
1508	out_set_cpu:
1509	new_cpu = wake_idle(new_cpu, p);
1510	if (new_cpu != cpu) {
1511	set_task_cpu(p, new_cpu);
1512	task_rq_unlock(rq, &flags);
1513	/* might preempt at this point */
1514	rq = task_rq_lock(p, &flags);
1515	old_state = p->state;
1516	if (!(old_state & state))
1517	goto out;
1518	if (p->array)
1519	goto out_running;
1520
1521	this_cpu = smp_processor_id();
1522	cpu = task_cpu(p);
1523	}
1524
1525	out_activate:
1526	#endif /* CONFIG_SMP */
1527	if (old_state == TASK_UNINTERRUPTIBLE) {
1528	rq->nr_uninterruptible--;
1529	/*
1530	* Tasks on involuntary sleep don't earn
1531	* sleep_avg beyond just interactive state.
1532	*/
1533	p->sleep_type = SLEEP_NONINTERACTIVE;
1534	} else
1535
1536	/*
1537	* Tasks that have marked their sleep as noninteractive get
1538	* woken up with their sleep average not weighted in an
1539	* interactive way.
1540	*/
1541	if (old_state & TASK_NONINTERACTIVE)
1542	p->sleep_type = SLEEP_NONINTERACTIVE;
1543
1544
1545	activate_task(p, rq, cpu == this_cpu);
1546	/*
1547	* Sync wakeups (i.e. those types of wakeups where the waker
1548	* has indicated that it will leave the CPU in short order)
1549	* don't trigger a preemption, if the woken up task will run on
1550	* this cpu. (in this case the 'I will reschedule' promise of
1551	* the waker guarantees that the freshly woken up task is going
1552	* to be considered on this CPU.)
1553	*/
1554	if (!sync \|\| cpu != this_cpu) {
1555	if (TASK_PREEMPTS_CURR(p, rq))
1556	resched_task(rq->curr);
1557	}
1558	success = 1;
1559
1560	out_running:
1561	p->state = TASK_RUNNING;
1562	out:
1563	task_rq_unlock(rq, &flags);
1564
1565	return success;
1566	}
1567
1568	int fastcall wake_up_process(struct task_struct *p)
1569	{
1570	return try_to_wake_up(p, TASK_STOPPED \| TASK_TRACED \|
1571	TASK_INTERRUPTIBLE \| TASK_UNINTERRUPTIBLE, 0);
1572	}
1573	EXPORT_SYMBOL(wake_up_process);
1574
1575	int fastcall wake_up_state(struct task_struct *p, unsigned int state)
1576	{
1577	return try_to_wake_up(p, state, 0);
1578	}
1579
1580	static void task_running_tick(struct rq rq, struct task_struct p);
1581	/*
1582	* Perform scheduler related setup for a newly forked process p.
1583	* p is forked by current.
1584	*/
1585	void fastcall sched_fork(struct task_struct *p, int clone_flags)
1586	{
1587	int cpu = get_cpu();
1588
1589	#ifdef CONFIG_SMP
1590	cpu = sched_balance_self(cpu, SD_BALANCE_FORK);
1591	#endif
1592	set_task_cpu(p, cpu);
1593
1594	/*
1595	* We mark the process as running here, but have not actually
1596	* inserted it onto the runqueue yet. This guarantees that
1597	* nobody will actually run it, and a signal or other external
1598	* event cannot wake it up and insert it on the runqueue either.
1599	*/
1600	p->state = TASK_RUNNING;
1601
1602	/*
1603	* Make sure we do not leak PI boosting priority to the child:
1604	*/
1605	p->prio = current->normal_prio;
1606
1607	INIT_LIST_HEAD(&p->run_list);
1608	p->array = NULL;
1609	#if defined(CONFIG_SCHEDSTATS) \|\| defined(CONFIG_TASK_DELAY_ACCT)
1610	if (unlikely(sched_info_on()))
1611	memset(&p->sched_info, 0, sizeof(p->sched_info));
1612	#endif
1613	#if defined(CONFIG_SMP) && defined(__ARCH_WANT_UNLOCKED_CTXSW)
1614	p->oncpu = 0;
1615	#endif
1616	#ifdef CONFIG_PREEMPT
1617	/* Want to start with kernel preemption disabled. */
1618	task_thread_info(p)->preempt_count = 1;
1619	#endif
1620	/*
1621	* Share the timeslice between parent and child, thus the
1622	* total amount of pending timeslices in the system doesn't change,
1623	* resulting in more scheduling fairness.
1624	*/
1625	local_irq_disable();
1626	p->time_slice = (current->time_slice + 1) >> 1;
1627	/*
1628	* The remainder of the first timeslice might be recovered by
1629	* the parent if the child exits early enough.
1630	*/
1631	p->first_time_slice = 1;
1632	current->time_slice >>= 1;
1633	p->timestamp = sched_clock();
1634	if (unlikely(!current->time_slice)) {
1635	/*
1636	* This case is rare, it happens when the parent has only
1637	* a single jiffy left from its timeslice. Taking the
1638	* runqueue lock is not a problem.
1639	*/
1640	current->time_slice = 1;
1641	task_running_tick(cpu_rq(cpu), current);
1642	}
1643	local_irq_enable();
1644	put_cpu();
1645	}
1646
1647	/*
1648	* wake_up_new_task - wake up a newly created task for the first time.
1649	*
1650	* This function will do some initial scheduler statistics housekeeping
1651	* that must be done for every newly created context, then puts the task
1652	* on the runqueue and wakes it.
1653	*/
1654	void fastcall wake_up_new_task(struct task_struct *p, unsigned long clone_flags)
1655	{
1656	struct rq rq, this_rq;
1657	unsigned long flags;
1658	int this_cpu, cpu;
1659
1660	rq = task_rq_lock(p, &flags);
1661	BUG_ON(p->state != TASK_RUNNING);
1662	this_cpu = smp_processor_id();
1663	cpu = task_cpu(p);
1664
1665	/*
1666	* We decrease the sleep average of forking parents
1667	* and children as well, to keep max-interactive tasks
1668	* from forking tasks that are max-interactive. The parent
1669	* (current) is done further down, under its lock.
1670	*/
1671	p->sleep_avg = JIFFIES_TO_NS(CURRENT_BONUS(p) *
1672	CHILD_PENALTY / 100 * MAX_SLEEP_AVG / MAX_BONUS);
1673
1674	p->prio = effective_prio(p);
1675
1676	if (likely(cpu == this_cpu)) {
1677	if (!(clone_flags & CLONE_VM)) {
1678	/*
1679	* The VM isn't cloned, so we're in a good position to
1680	* do child-runs-first in anticipation of an exec. This
1681	* usually avoids a lot of COW overhead.
1682	*/
1683	if (unlikely(!current->array))
1684	__activate_task(p, rq);
1685	else {
1686	p->prio = current->prio;
1687	p->normal_prio = current->normal_prio;
1688	list_add_tail(&p->run_list, &current->run_list);
1689	p->array = current->array;
1690	p->array->nr_active++;
1691	inc_nr_running(p, rq);
1692	}
1693	set_need_resched();
1694	} else
1695	/* Run child last */
1696	__activate_task(p, rq);
1697	/*
1698	* We skip the following code due to cpu == this_cpu
1699	*
1700	* task_rq_unlock(rq, &flags);
1701	* this_rq = task_rq_lock(current, &flags);
1702	*/
1703	this_rq = rq;
1704	} else {
1705	this_rq = cpu_rq(this_cpu);
1706
1707	/*
1708	* Not the local CPU - must adjust timestamp. This should
1709	* get optimised away in the !CONFIG_SMP case.
1710	*/
1711	p->timestamp = (p->timestamp - this_rq->most_recent_timestamp)
1712	+ rq->most_recent_timestamp;
1713	__activate_task(p, rq);
1714	if (TASK_PREEMPTS_CURR(p, rq))
1715	resched_task(rq->curr);
1716
1717	/*
1718	* Parent and child are on different CPUs, now get the
1719	* parent runqueue to update the parent's ->sleep_avg:
1720	*/
1721	task_rq_unlock(rq, &flags);
1722	this_rq = task_rq_lock(current, &flags);
1723	}
1724	current->sleep_avg = JIFFIES_TO_NS(CURRENT_BONUS(current) *
1725	PARENT_PENALTY / 100 * MAX_SLEEP_AVG / MAX_BONUS);
1726	task_rq_unlock(this_rq, &flags);
1727	}
1728
1729	/*
1730	* Potentially available exiting-child timeslices are
1731	* retrieved here - this way the parent does not get
1732	* penalized for creating too many threads.
1733	*
1734	* (this cannot be used to 'generate' timeslices
1735	* artificially, because any timeslice recovered here
1736	* was given away by the parent in the first place.)
1737	*/
1738	void fastcall sched_exit(struct task_struct *p)
1739	{
1740	unsigned long flags;
1741	struct rq *rq;
1742
1743	/*
1744	* If the child was a (relative-) CPU hog then decrease
1745	* the sleep_avg of the parent as well.
1746	*/
1747	rq = task_rq_lock(p->parent, &flags);
1748	if (p->first_time_slice && task_cpu(p) == task_cpu(p->parent)) {
1749	p->parent->time_slice += p->time_slice;
1750	if (unlikely(p->parent->time_slice > task_timeslice(p)))
1751	p->parent->time_slice = task_timeslice(p);
1752	}
1753	if (p->sleep_avg < p->parent->sleep_avg)
1754	p->parent->sleep_avg = p->parent->sleep_avg /
1755	(EXIT_WEIGHT + 1) * EXIT_WEIGHT + p->sleep_avg /
1756	(EXIT_WEIGHT + 1);
1757	task_rq_unlock(rq, &flags);
1758	}
1759
1760	/**
1761	* prepare_task_switch - prepare to switch tasks
1762	* @rq: the runqueue preparing to switch
1763	* @next: the task we are going to switch to.
1764	*
1765	* This is called with the rq lock held and interrupts off. It must
1766	* be paired with a subsequent finish_task_switch after the context
1767	* switch.
1768	*
1769	* prepare_task_switch sets up locking and calls architecture specific
1770	* hooks.
1771	*/
1772	static inline void prepare_task_switch(struct rq rq, struct task_struct next)
1773	{
1774	prepare_lock_switch(rq, next);
1775	prepare_arch_switch(next);
1776	}
1777
1778	/**
1779	* finish_task_switch - clean up after a task-switch
1780	* @rq: runqueue associated with task-switch
1781	* @prev: the thread we just switched away from.
1782	*
1783	* finish_task_switch must be called after the context switch, paired
1784	* with a prepare_task_switch call before the context switch.
1785	* finish_task_switch will reconcile locking set up by prepare_task_switch,
1786	* and do any other architecture-specific cleanup actions.
1787	*
1788	* Note that we may have delayed dropping an mm in context_switch(). If
1789	* so, we finish that here outside of the runqueue lock. (Doing it
1790	* with the lock held can cause deadlocks; see schedule() for
1791	* details.)
1792	*/
1793	static inline void finish_task_switch(struct rq rq, struct task_struct prev)
1794	__releases(rq->lock)
1795	{
1796	struct mm_struct *mm = rq->prev_mm;
1797	long prev_state;
1798
1799	rq->prev_mm = NULL;
1800
1801	/*
1802	* A task struct has one reference for the use as "current".
1803	* If a task dies, then it sets TASK_DEAD in tsk->state and calls
1804	* schedule one last time. The schedule call will never return, and
1805	* the scheduled task must drop that reference.
1806	* The test for TASK_DEAD must occur while the runqueue locks are
1807	* still held, otherwise prev could be scheduled on another cpu, die
1808	* there before we look at prev->state, and then the reference would
1809	* be dropped twice.
1810	* Manfred Spraul <[email protected]>
1811	*/
1812	prev_state = prev->state;
1813	finish_arch_switch(prev);
1814	finish_lock_switch(rq, prev);
1815	if (mm)
1816	mmdrop(mm);
1817	if (unlikely(prev_state == TASK_DEAD)) {
1818	/*
1819	* Remove function-return probe instances associated with this
1820	* task and put them back on the free list.
1821	*/
1822	kprobe_flush_task(prev);
1823	put_task_struct(prev);
1824	}
1825	}
1826
1827	/**
1828	* schedule_tail - first thing a freshly forked thread must call.
1829	* @prev: the thread we just switched away from.
1830	*/
1831	asmlinkage void schedule_tail(struct task_struct *prev)
1832	__releases(rq->lock)
1833	{
1834	struct rq *rq = this_rq();
1835
1836	finish_task_switch(rq, prev);
1837	#ifdef __ARCH_WANT_UNLOCKED_CTXSW
1838	/* In this case, finish_task_switch does not reenable preemption */
1839	preempt_enable();
1840	#endif
1841	if (current->set_child_tid)
1842	put_user(current->pid, current->set_child_tid);
1843	}
1844
1845	/*
1846	* context_switch - switch to the new MM and the new
1847	* thread's register state.
1848	*/
1849	static inline struct task_struct *
1850	context_switch(struct rq rq, struct task_struct prev,
1851	struct task_struct *next)
1852	{
1853	struct mm_struct *mm = next->mm;
1854	struct mm_struct *oldmm = prev->active_mm;
1855
1856	/*
1857	* For paravirt, this is coupled with an exit in switch_to to
1858	* combine the page table reload and the switch backend into
1859	* one hypercall.
1860	*/
1861	arch_enter_lazy_cpu_mode();
1862
1863	if (!mm) {
1864	next->active_mm = oldmm;
1865	atomic_inc(&oldmm->mm_count);
1866	enter_lazy_tlb(oldmm, next);
1867	} else
1868	switch_mm(oldmm, mm, next);
1869
1870	if (!prev->mm) {
1871	prev->active_mm = NULL;
1872	WARN_ON(rq->prev_mm);
1873	rq->prev_mm = oldmm;
1874	}
1875	/*
1876	* Since the runqueue lock will be released by the next
1877	* task (which is an invalid locking op but in the case
1878	* of the scheduler it's an obvious special-case), so we
1879	* do an early lockdep release here:
1880	*/
1881	#ifndef __ARCH_WANT_UNLOCKED_CTXSW
1882	spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
1883	#endif
1884
1885	/* Here we just switch the register state and the stack. */
1886	switch_to(prev, next, prev);
1887
1888	return prev;
1889	}
1890
1891	/*
1892	* nr_running, nr_uninterruptible and nr_context_switches:
1893	*
1894	* externally visible scheduler statistics: current number of runnable
1895	* threads, current number of uninterruptible-sleeping threads, total
1896	* number of context switches performed since bootup.
1897	*/
1898	unsigned long nr_running(void)
1899	{
1900	unsigned long i, sum = 0;
1901
1902	for_each_online_cpu(i)
1903	sum += cpu_rq(i)->nr_running;
1904
1905	return sum;
1906	}
1907
1908	unsigned long nr_uninterruptible(void)
1909	{
1910	unsigned long i, sum = 0;
1911
1912	for_each_possible_cpu(i)
1913	sum += cpu_rq(i)->nr_uninterruptible;
1914
1915	/*
1916	* Since we read the counters lockless, it might be slightly
1917	* inaccurate. Do not allow it to go below zero though:
1918	*/
1919	if (unlikely((long)sum < 0))
1920	sum = 0;
1921
1922	return sum;
1923	}
1924
1925	unsigned long long nr_context_switches(void)
1926	{
1927	int i;
1928	unsigned long long sum = 0;
1929
1930	for_each_possible_cpu(i)
1931	sum += cpu_rq(i)->nr_switches;
1932
1933	return sum;
1934	}
1935
1936	unsigned long nr_iowait(void)
1937	{
1938	unsigned long i, sum = 0;
1939
1940	for_each_possible_cpu(i)
1941	sum += atomic_read(&cpu_rq(i)->nr_iowait);
1942
1943	return sum;
1944	}
1945
1946	unsigned long nr_active(void)
1947	{
1948	unsigned long i, running = 0, uninterruptible = 0;
1949
1950	for_each_online_cpu(i) {
1951	running += cpu_rq(i)->nr_running;
1952	uninterruptible += cpu_rq(i)->nr_uninterruptible;
1953	}
1954
1955	if (unlikely((long)uninterruptible < 0))
1956	uninterruptible = 0;
1957
1958	return running + uninterruptible;
1959	}
1960
1961	#ifdef CONFIG_SMP
1962
1963	/*
1964	* Is this task likely cache-hot:
1965	*/
1966	static inline int
1967	task_hot(struct task_struct p, unsigned long long now, struct sched_domain sd)
1968	{
1969	return (long long)(now - p->last_ran) < (long long)sd->cache_hot_time;
1970	}
1971
1972	/*
1973	* double_rq_lock - safely lock two runqueues
1974	*
1975	* Note this does not disable interrupts like task_rq_lock,
1976	* you need to do so manually before calling.
1977	*/
1978	static void double_rq_lock(struct rq rq1, struct rq rq2)
1979	__acquires(rq1->lock)
1980	__acquires(rq2->lock)
1981	{
1982	BUG_ON(!irqs_disabled());
1983	if (rq1 == rq2) {
1984	spin_lock(&rq1->lock);
1985	__acquire(rq2->lock); /* Fake it out ;) */
1986	} else {
1987	if (rq1 < rq2) {
1988	spin_lock(&rq1->lock);
1989	spin_lock(&rq2->lock);
1990	} else {
1991	spin_lock(&rq2->lock);
1992	spin_lock(&rq1->lock);
1993	}
1994	}
1995	}
1996
1997	/*
1998	* double_rq_unlock - safely unlock two runqueues
1999	*
2000	* Note this does not restore interrupts like task_rq_unlock,
2001	* you need to do so manually after calling.
2002	*/
2003	static void double_rq_unlock(struct rq rq1, struct rq rq2)
2004	__releases(rq1->lock)
2005	__releases(rq2->lock)
2006	{
2007	spin_unlock(&rq1->lock);
2008	if (rq1 != rq2)
2009	spin_unlock(&rq2->lock);
2010	else
2011	__release(rq2->lock);
2012	}
2013
2014	/*
2015	* double_lock_balance - lock the busiest runqueue, this_rq is locked already.
2016	*/
2017	static void double_lock_balance(struct rq this_rq, struct rq busiest)
2018	__releases(this_rq->lock)
2019	__acquires(busiest->lock)
2020	__acquires(this_rq->lock)
2021	{
2022	if (unlikely(!irqs_disabled())) {
2023	/* printk() doesn't work good under rq->lock */
2024	spin_unlock(&this_rq->lock);
2025	BUG_ON(1);
2026	}
2027	if (unlikely(!spin_trylock(&busiest->lock))) {
2028	if (busiest < this_rq) {
2029	spin_unlock(&this_rq->lock);
2030	spin_lock(&busiest->lock);
2031	spin_lock(&this_rq->lock);
2032	} else
2033	spin_lock(&busiest->lock);
2034	}
2035	}
2036
2037	/*
2038	* If dest_cpu is allowed for this process, migrate the task to it.
2039	* This is accomplished by forcing the cpu_allowed mask to only
2040	* allow dest_cpu, which will force the cpu onto dest_cpu. Then
2041	* the cpu_allowed mask is restored.
2042	*/
2043	static void sched_migrate_task(struct task_struct *p, int dest_cpu)
2044	{
2045	struct migration_req req;
2046	unsigned long flags;
2047	struct rq *rq;
2048
2049	rq = task_rq_lock(p, &flags);
2050	if (!cpu_isset(dest_cpu, p->cpus_allowed)
2051	\|\| unlikely(cpu_is_offline(dest_cpu)))
2052	goto out;
2053
2054	/* force the process onto the specified CPU */
2055	if (migrate_task(p, dest_cpu, &req)) {
2056	/* Need to wait for migration thread (might exit: take ref). */
2057	struct task_struct *mt = rq->migration_thread;
2058
2059	get_task_struct(mt);
2060	task_rq_unlock(rq, &flags);
2061	wake_up_process(mt);
2062	put_task_struct(mt);
2063	wait_for_completion(&req.done);
2064
2065	return;
2066	}
2067	out:
2068	task_rq_unlock(rq, &flags);
2069	}
2070
2071	/*
2072	* sched_exec - execve() is a valuable balancing opportunity, because at
2073	* this point the task has the smallest effective memory and cache footprint.
2074	*/
2075	void sched_exec(void)
2076	{
2077	int new_cpu, this_cpu = get_cpu();
2078	new_cpu = sched_balance_self(this_cpu, SD_BALANCE_EXEC);
2079	put_cpu();
2080	if (new_cpu != this_cpu)
2081	sched_migrate_task(current, new_cpu);
2082	}
2083
2084	/*
2085	* pull_task - move a task from a remote runqueue to the local runqueue.
2086	* Both runqueues must be locked.
2087	*/
2088	static void pull_task(struct rq src_rq, struct prio_array src_array,
2089	struct task_struct p, struct rq this_rq,
2090	struct prio_array *this_array, int this_cpu)
2091	{
2092	dequeue_task(p, src_array);
2093	dec_nr_running(p, src_rq);
2094	set_task_cpu(p, this_cpu);
2095	inc_nr_running(p, this_rq);
2096	enqueue_task(p, this_array);
2097	p->timestamp = (p->timestamp - src_rq->most_recent_timestamp)
2098	+ this_rq->most_recent_timestamp;
2099	/*
2100	* Note that idle threads have a prio of MAX_PRIO, for this test
2101	* to be always true for them.
2102	*/
2103	if (TASK_PREEMPTS_CURR(p, this_rq))
2104	resched_task(this_rq->curr);
2105	}
2106
2107	/*
2108	* can_migrate_task - may task p from runqueue rq be migrated to this_cpu?
2109	*/
2110	static
2111	int can_migrate_task(struct task_struct p, struct rq rq, int this_cpu,
2112	struct sched_domain *sd, enum idle_type idle,
2113	int *all_pinned)
2114	{
2115	/*
2116	* We do not migrate tasks that are:
2117	* 1) running (obviously), or
2118	* 2) cannot be migrated to this CPU due to cpus_allowed, or
2119	* 3) are cache-hot on their current CPU.
2120	*/
2121	if (!cpu_isset(this_cpu, p->cpus_allowed))
2122	return 0;
2123	*all_pinned = 0;
2124
2125	if (task_running(rq, p))
2126	return 0;
2127
2128	/*
2129	* Aggressive migration if:
2130	* 1) task is cache cold, or
2131	* 2) too many balance attempts have failed.
2132	*/
2133
2134	if (sd->nr_balance_failed > sd->cache_nice_tries) {
2135	#ifdef CONFIG_SCHEDSTATS
2136	if (task_hot(p, rq->most_recent_timestamp, sd))
2137	schedstat_inc(sd, lb_hot_gained[idle]);
2138	#endif
2139	return 1;
2140	}
2141
2142	if (task_hot(p, rq->most_recent_timestamp, sd))
2143	return 0;
2144	return 1;
2145	}
2146
2147	#define rq_best_prio(rq) min((rq)->curr->prio, (rq)->best_expired_prio)
2148
2149	/*
2150	* move_tasks tries to move up to max_nr_move tasks and max_load_move weighted
2151	* load from busiest to this_rq, as part of a balancing operation within
2152	* "domain". Returns the number of tasks moved.
2153	*
2154	* Called with both runqueues locked.
2155	*/
2156	static int move_tasks(struct rq this_rq, int this_cpu, struct rq busiest,
2157	unsigned long max_nr_move, unsigned long max_load_move,
2158	struct sched_domain *sd, enum idle_type idle,
2159	int *all_pinned)
2160	{
2161	int idx, pulled = 0, pinned = 0, this_best_prio, best_prio,
2162	best_prio_seen, skip_for_load;
2163	struct prio_array array, dst_array;
2164	struct list_head head, curr;
2165	struct task_struct *tmp;
2166	long rem_load_move;
2167
2168	if (max_nr_move == 0 \|\| max_load_move == 0)
2169	goto out;
2170
2171	rem_load_move = max_load_move;
2172	pinned = 1;
2173	this_best_prio = rq_best_prio(this_rq);
2174	best_prio = rq_best_prio(busiest);
2175	/*
2176	* Enable handling of the case where there is more than one task
2177	* with the best priority. If the current running task is one
2178	* of those with prio==best_prio we know it won't be moved
2179	* and therefore it's safe to override the skip (based on load) of
2180	* any task we find with that prio.
2181	*/
2182	best_prio_seen = best_prio == busiest->curr->prio;
2183
2184	/*
2185	* We first consider expired tasks. Those will likely not be
2186	* executed in the near future, and they are most likely to
2187	* be cache-cold, thus switching CPUs has the least effect
2188	* on them.
2189	*/
2190	if (busiest->expired->nr_active) {
2191	array = busiest->expired;
2192	dst_array = this_rq->expired;
2193	} else {
2194	array = busiest->active;
2195	dst_array = this_rq->active;
2196	}
2197
2198	new_array:
2199	/* Start searching at priority 0: */
2200	idx = 0;
2201	skip_bitmap:
2202	if (!idx)
2203	idx = sched_find_first_bit(array->bitmap);
2204	else
2205	idx = find_next_bit(array->bitmap, MAX_PRIO, idx);
2206	if (idx >= MAX_PRIO) {
2207	if (array == busiest->expired && busiest->active->nr_active) {
2208	array = busiest->active;
2209	dst_array = this_rq->active;
2210	goto new_array;
2211	}
2212	goto out;
2213	}
2214
2215	head = array->queue + idx;
2216	curr = head->prev;
2217	skip_queue:
2218	tmp = list_entry(curr, struct task_struct, run_list);
2219
2220	curr = curr->prev;
2221
2222	/*
2223	* To help distribute high priority tasks accross CPUs we don't
2224	* skip a task if it will be the highest priority task (i.e. smallest
2225	* prio value) on its new queue regardless of its load weight
2226	*/
2227	skip_for_load = tmp->load_weight > rem_load_move;
2228	if (skip_for_load && idx < this_best_prio)
2229	skip_for_load = !best_prio_seen && idx == best_prio;
2230	if (skip_for_load \|\|
2231	!can_migrate_task(tmp, busiest, this_cpu, sd, idle, &pinned)) {
2232
2233	best_prio_seen \|= idx == best_prio;
2234	if (curr != head)
2235	goto skip_queue;
2236	idx++;
2237	goto skip_bitmap;
2238	}
2239
2240	pull_task(busiest, array, tmp, this_rq, dst_array, this_cpu);
2241	pulled++;
2242	rem_load_move -= tmp->load_weight;
2243
2244	/*
2245	* We only want to steal up to the prescribed number of tasks
2246	* and the prescribed amount of weighted load.
2247	*/
2248	if (pulled < max_nr_move && rem_load_move > 0) {
2249	if (idx < this_best_prio)
2250	this_best_prio = idx;
2251	if (curr != head)
2252	goto skip_queue;
2253	idx++;
2254	goto skip_bitmap;
2255	}
2256	out:
2257	/*
2258	* Right now, this is the only place pull_task() is called,
2259	* so we can safely collect pull_task() stats here rather than
2260	* inside pull_task().
2261	*/
2262	schedstat_add(sd, lb_gained[idle], pulled);
2263
2264	if (all_pinned)
2265	*all_pinned = pinned;
2266	return pulled;
2267	}
2268
2269	/*
2270	* find_busiest_group finds and returns the busiest CPU group within the
2271	* domain. It calculates and returns the amount of weighted load which
2272	* should be moved to restore balance via the imbalance parameter.
2273	*/
2274	static struct sched_group *
2275	find_busiest_group(struct sched_domain *sd, int this_cpu,
2276	unsigned long imbalance, enum idle_type idle, int sd_idle,
2277	cpumask_t cpus, int balance)
2278	{
2279	struct sched_group busiest = NULL, this = NULL, *group = sd->groups;
2280	unsigned long max_load, avg_load, total_load, this_load, total_pwr;
2281	unsigned long max_pull;
2282	unsigned long busiest_load_per_task, busiest_nr_running;
2283	unsigned long this_load_per_task, this_nr_running;
2284	int load_idx;
2285	#if defined(CONFIG_SCHED_MC) \|\| defined(CONFIG_SCHED_SMT)
2286	int power_savings_balance = 1;
2287	unsigned long leader_nr_running = 0, min_load_per_task = 0;
2288	unsigned long min_nr_running = ULONG_MAX;
2289	struct sched_group group_min = NULL, group_leader = NULL;
2290	#endif
2291
2292	max_load = this_load = total_load = total_pwr = 0;
2293	busiest_load_per_task = busiest_nr_running = 0;
2294	this_load_per_task = this_nr_running = 0;
2295	if (idle == NOT_IDLE)
2296	load_idx = sd->busy_idx;
2297	else if (idle == NEWLY_IDLE)
2298	load_idx = sd->newidle_idx;
2299	else
2300	load_idx = sd->idle_idx;
2301
2302	do {
2303	unsigned long load, group_capacity;
2304	int local_group;
2305	int i;
2306	unsigned int balance_cpu = -1, first_idle_cpu = 0;
2307	unsigned long sum_nr_running, sum_weighted_load;
2308
2309	local_group = cpu_isset(this_cpu, group->cpumask);
2310
2311	if (local_group)
2312	balance_cpu = first_cpu(group->cpumask);
2313
2314	/* Tally up the load of all CPUs in the group */
2315	sum_weighted_load = sum_nr_running = avg_load = 0;
2316
2317	for_each_cpu_mask(i, group->cpumask) {
2318	struct rq *rq;
2319
2320	if (!cpu_isset(i, *cpus))
2321	continue;
2322
2323	rq = cpu_rq(i);
2324
2325	if (*sd_idle && !idle_cpu(i))
2326	*sd_idle = 0;
2327
2328	/* Bias balancing toward cpus of our domain */
2329	if (local_group) {
2330	if (idle_cpu(i) && !first_idle_cpu) {
2331	first_idle_cpu = 1;
2332	balance_cpu = i;
2333	}
2334
2335	load = target_load(i, load_idx);
2336	} else
2337	load = source_load(i, load_idx);
2338
2339	avg_load += load;
2340	sum_nr_running += rq->nr_running;
2341	sum_weighted_load += rq->raw_weighted_load;
2342	}
2343
2344	/*
2345	* First idle cpu or the first cpu(busiest) in this sched group
2346	* is eligible for doing load balancing at this and above
2347	* domains.
2348	*/
2349	if (local_group && balance_cpu != this_cpu && balance) {
2350	*balance = 0;
2351	goto ret;
2352	}
2353
2354	total_load += avg_load;
2355	total_pwr += group->cpu_power;
2356
2357	/* Adjust by relative CPU power of the group */
2358	avg_load = (avg_load * SCHED_LOAD_SCALE) / group->cpu_power;
2359
2360	group_capacity = group->cpu_power / SCHED_LOAD_SCALE;
2361
2362	if (local_group) {
2363	this_load = avg_load;
2364	this = group;
2365	this_nr_running = sum_nr_running;
2366	this_load_per_task = sum_weighted_load;
2367	} else if (avg_load > max_load &&
2368	sum_nr_running > group_capacity) {
2369	max_load = avg_load;
2370	busiest = group;
2371	busiest_nr_running = sum_nr_running;
2372	busiest_load_per_task = sum_weighted_load;
2373	}
2374
2375	#if defined(CONFIG_SCHED_MC) \|\| defined(CONFIG_SCHED_SMT)
2376	/*
2377	* Busy processors will not participate in power savings
2378	* balance.
2379	*/
2380	if (idle == NOT_IDLE \|\| !(sd->flags & SD_POWERSAVINGS_BALANCE))
2381	goto group_next;
2382
2383	/*
2384	* If the local group is idle or completely loaded
2385	* no need to do power savings balance at this domain
2386	*/
2387	if (local_group && (this_nr_running >= group_capacity \|\|
2388	!this_nr_running))
2389	power_savings_balance = 0;
2390
2391	/*
2392	* If a group is already running at full capacity or idle,
2393	* don't include that group in power savings calculations
2394	*/
2395	if (!power_savings_balance \|\| sum_nr_running >= group_capacity
2396	\|\| !sum_nr_running)
2397	goto group_next;
2398
2399	/*
2400	* Calculate the group which has the least non-idle load.
2401	* This is the group from where we need to pick up the load
2402	* for saving power
2403	*/
2404	if ((sum_nr_running < min_nr_running) \|\|
2405	(sum_nr_running == min_nr_running &&
2406	first_cpu(group->cpumask) <
2407	first_cpu(group_min->cpumask))) {
2408	group_min = group;
2409	min_nr_running = sum_nr_running;
2410	min_load_per_task = sum_weighted_load /
2411	sum_nr_running;
2412	}
2413
2414	/*
2415	* Calculate the group which is almost near its
2416	* capacity but still has some space to pick up some load
2417	* from other group and save more power
2418	*/
2419	if (sum_nr_running <= group_capacity - 1) {
2420	if (sum_nr_running > leader_nr_running \|\|
2421	(sum_nr_running == leader_nr_running &&
2422	first_cpu(group->cpumask) >
2423	first_cpu(group_leader->cpumask))) {
2424	group_leader = group;
2425	leader_nr_running = sum_nr_running;
2426	}
2427	}
2428	group_next:
2429	#endif
2430	group = group->next;
2431	} while (group != sd->groups);
2432
2433	if (!busiest \|\| this_load >= max_load \|\| busiest_nr_running == 0)
2434	goto out_balanced;
2435
2436	avg_load = (SCHED_LOAD_SCALE * total_load) / total_pwr;
2437
2438	if (this_load >= avg_load \|\|
2439	100max_load <= sd->imbalance_pctthis_load)
2440	goto out_balanced;
2441
2442	busiest_load_per_task /= busiest_nr_running;
2443	/*
2444	* We're trying to get all the cpus to the average_load, so we don't
2445	* want to push ourselves above the average load, nor do we wish to
2446	* reduce the max loaded cpu below the average load, as either of these
2447	* actions would just result in more rebalancing later, and ping-pong
2448	* tasks around. Thus we look for the minimum possible imbalance.
2449	* Negative imbalances (we are more loaded than anyone else) will
2450	* be counted as no imbalance for these purposes -- we can't fix that
2451	* by pulling tasks to us. Be careful of negative numbers as they'll
2452	* appear as very large values with unsigned longs.
2453	*/
2454	if (max_load <= busiest_load_per_task)
2455	goto out_balanced;
2456
2457	/*
2458	* In the presence of smp nice balancing, certain scenarios can have
2459	* max load less than avg load(as we skip the groups at or below
2460	* its cpu_power, while calculating max_load..)
2461	*/
2462	if (max_load < avg_load) {
2463	*imbalance = 0;
2464	goto small_imbalance;
2465	}
2466
2467	/* Don't want to pull so many tasks that a group would go idle */
2468	max_pull = min(max_load - avg_load, max_load - busiest_load_per_task);
2469
2470	/* How much load to actually move to equalise the imbalance */
2471	imbalance = min(max_pull busiest->cpu_power,
2472	(avg_load - this_load) * this->cpu_power)
2473	/ SCHED_LOAD_SCALE;
2474
2475	/*
2476	* if *imbalance is less than the average load per runnable task
2477	* there is no gaurantee that any tasks will be moved so we'll have
2478	* a think about bumping its value to force at least one task to be
2479	* moved
2480	*/
2481	if (*imbalance < busiest_load_per_task) {
2482	unsigned long tmp, pwr_now, pwr_move;
2483	unsigned int imbn;
2484
2485	small_imbalance:
2486	pwr_move = pwr_now = 0;
2487	imbn = 2;
2488	if (this_nr_running) {
2489	this_load_per_task /= this_nr_running;
2490	if (busiest_load_per_task > this_load_per_task)
2491	imbn = 1;
2492	} else
2493	this_load_per_task = SCHED_LOAD_SCALE;
2494
2495	if (max_load - this_load >= busiest_load_per_task * imbn) {
2496	*imbalance = busiest_load_per_task;
2497	return busiest;
2498	}
2499
2500	/*
2501	* OK, we don't have enough imbalance to justify moving tasks,
2502	* however we may be able to increase total CPU power used by
2503	* moving them.
2504	*/
2505
2506	pwr_now += busiest->cpu_power *
2507	min(busiest_load_per_task, max_load);
2508	pwr_now += this->cpu_power *
2509	min(this_load_per_task, this_load);
2510	pwr_now /= SCHED_LOAD_SCALE;
2511
2512	/* Amount of load we'd subtract */
2513	tmp = busiest_load_per_task * SCHED_LOAD_SCALE /
2514	busiest->cpu_power;
2515	if (max_load > tmp)
2516	pwr_move += busiest->cpu_power *
2517	min(busiest_load_per_task, max_load - tmp);
2518
2519	/* Amount of load we'd add */
2520	if (max_load * busiest->cpu_power <
2521	busiest_load_per_task * SCHED_LOAD_SCALE)
2522	tmp = max_load * busiest->cpu_power / this->cpu_power;
2523	else
2524	tmp = busiest_load_per_task * SCHED_LOAD_SCALE /
2525	this->cpu_power;
2526	pwr_move += this->cpu_power *
2527	min(this_load_per_task, this_load + tmp);
2528	pwr_move /= SCHED_LOAD_SCALE;
2529
2530	/* Move if we gain throughput */
2531	if (pwr_move <= pwr_now)
2532	goto out_balanced;
2533
2534	*imbalance = busiest_load_per_task;
2535	}
2536
2537	return busiest;
2538
2539	out_balanced:
2540	#if defined(CONFIG_SCHED_MC) \|\| defined(CONFIG_SCHED_SMT)
2541	if (idle == NOT_IDLE \|\| !(sd->flags & SD_POWERSAVINGS_BALANCE))
2542	goto ret;
2543
2544	if (this == group_leader && group_leader != group_min) {
2545	*imbalance = min_load_per_task;
2546	return group_min;
2547	}
2548	#endif
2549	ret:
2550	*imbalance = 0;
2551	return NULL;
2552	}
2553
2554	/*
2555	* find_busiest_queue - find the busiest runqueue among the cpus in group.
2556	*/
2557	static struct rq *
2558	find_busiest_queue(struct sched_group *group, enum idle_type idle,
2559	unsigned long imbalance, cpumask_t *cpus)
2560	{
2561	struct rq busiest = NULL, rq;
2562	unsigned long max_load = 0;
2563	int i;
2564
2565	for_each_cpu_mask(i, group->cpumask) {
2566
2567	if (!cpu_isset(i, *cpus))
2568	continue;
2569
2570	rq = cpu_rq(i);
2571
2572	if (rq->nr_running == 1 && rq->raw_weighted_load > imbalance)
2573	continue;
2574
2575	if (rq->raw_weighted_load > max_load) {
2576	max_load = rq->raw_weighted_load;
2577	busiest = rq;
2578	}
2579	}
2580
2581	return busiest;
2582	}
2583
2584	/*
2585	* Max backoff if we encounter pinned tasks. Pretty arbitrary value, but
2586	* so long as it is large enough.
2587	*/
2588	#define MAX_PINNED_INTERVAL 512
2589
2590	static inline unsigned long minus_1_or_zero(unsigned long n)
2591	{
2592	return n > 0 ? n - 1 : 0;
2593	}
2594
2595	/*
2596	* Check this_cpu to ensure it is balanced within domain. Attempt to move
2597	* tasks if there is an imbalance.
2598	*/
2599	static int load_balance(int this_cpu, struct rq *this_rq,
2600	struct sched_domain *sd, enum idle_type idle,
2601	int *balance)
2602	{
2603	int nr_moved, all_pinned = 0, active_balance = 0, sd_idle = 0;
2604	struct sched_group *group;
2605	unsigned long imbalance;
2606	struct rq *busiest;
2607	cpumask_t cpus = CPU_MASK_ALL;
2608	unsigned long flags;
2609
2610	/*
2611	* When power savings policy is enabled for the parent domain, idle
2612	* sibling can pick up load irrespective of busy siblings. In this case,
2613	* let the state of idle sibling percolate up as IDLE, instead of
2614	* portraying it as NOT_IDLE.
2615	*/
2616	if (idle != NOT_IDLE && sd->flags & SD_SHARE_CPUPOWER &&
2617	!test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
2618	sd_idle = 1;
2619
2620	schedstat_inc(sd, lb_cnt[idle]);
2621
2622	redo:
2623	group = find_busiest_group(sd, this_cpu, &imbalance, idle, &sd_idle,
2624	&cpus, balance);
2625
2626	if (*balance == 0)
2627	goto out_balanced;
2628
2629	if (!group) {
2630	schedstat_inc(sd, lb_nobusyg[idle]);
2631	goto out_balanced;
2632	}
2633
2634	busiest = find_busiest_queue(group, idle, imbalance, &cpus);
2635	if (!busiest) {
2636	schedstat_inc(sd, lb_nobusyq[idle]);
2637	goto out_balanced;
2638	}
2639
2640	BUG_ON(busiest == this_rq);
2641
2642	schedstat_add(sd, lb_imbalance[idle], imbalance);
2643
2644	nr_moved = 0;
2645	if (busiest->nr_running > 1) {
2646	/*
2647	* Attempt to move tasks. If find_busiest_group has found
2648	* an imbalance but busiest->nr_running <= 1, the group is
2649	* still unbalanced. nr_moved simply stays zero, so it is
2650	* correctly treated as an imbalance.
2651	*/
2652	local_irq_save(flags);
2653	double_rq_lock(this_rq, busiest);
2654	nr_moved = move_tasks(this_rq, this_cpu, busiest,
2655	minus_1_or_zero(busiest->nr_running),
2656	imbalance, sd, idle, &all_pinned);
2657	double_rq_unlock(this_rq, busiest);
2658	local_irq_restore(flags);
2659
2660	/* All tasks on this runqueue were pinned by CPU affinity */
2661	if (unlikely(all_pinned)) {
2662	cpu_clear(cpu_of(busiest), cpus);
2663	if (!cpus_empty(cpus))
2664	goto redo;
2665	goto out_balanced;
2666	}
2667	}
2668
2669	if (!nr_moved) {
2670	schedstat_inc(sd, lb_failed[idle]);
2671	sd->nr_balance_failed++;
2672
2673	if (unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2)) {
2674
2675	spin_lock_irqsave(&busiest->lock, flags);
2676
2677	/* don't kick the migration_thread, if the curr
2678	* task on busiest cpu can't be moved to this_cpu
2679	*/
2680	if (!cpu_isset(this_cpu, busiest->curr->cpus_allowed)) {
2681	spin_unlock_irqrestore(&busiest->lock, flags);
2682	all_pinned = 1;
2683	goto out_one_pinned;
2684	}
2685
2686	if (!busiest->active_balance) {
2687	busiest->active_balance = 1;
2688	busiest->push_cpu = this_cpu;
2689	active_balance = 1;
2690	}
2691	spin_unlock_irqrestore(&busiest->lock, flags);
2692	if (active_balance)
2693	wake_up_process(busiest->migration_thread);
2694
2695	/*
2696	* We've kicked active balancing, reset the failure
2697	* counter.
2698	*/
2699	sd->nr_balance_failed = sd->cache_nice_tries+1;
2700	}
2701	} else
2702	sd->nr_balance_failed = 0;
2703
2704	if (likely(!active_balance)) {
2705	/* We were unbalanced, so reset the balancing interval */
2706	sd->balance_interval = sd->min_interval;
2707	} else {
2708	/*
2709	* If we've begun active balancing, start to back off. This
2710	* case may not be covered by the all_pinned logic if there
2711	* is only 1 task on the busy runqueue (because we don't call
2712	* move_tasks).
2713	*/
2714	if (sd->balance_interval < sd->max_interval)
2715	sd->balance_interval *= 2;
2716	}
2717
2718	if (!nr_moved && !sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
2719	!test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
2720	return -1;
2721	return nr_moved;
2722
2723	out_balanced:
2724	schedstat_inc(sd, lb_balanced[idle]);
2725
2726	sd->nr_balance_failed = 0;
2727
2728	out_one_pinned:
2729	/* tune up the balancing interval */
2730	if ((all_pinned && sd->balance_interval < MAX_PINNED_INTERVAL) \|\|
2731	(sd->balance_interval < sd->max_interval))
2732	sd->balance_interval *= 2;
2733
2734	if (!sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
2735	!test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
2736	return -1;
2737	return 0;
2738	}
2739
2740	/*
2741	* Check this_cpu to ensure it is balanced within domain. Attempt to move
2742	* tasks if there is an imbalance.
2743	*
2744	* Called from schedule when this_rq is about to become idle (NEWLY_IDLE).
2745	* this_rq is locked.
2746	*/
2747	static int
2748	load_balance_newidle(int this_cpu, struct rq this_rq, struct sched_domain sd)
2749	{
2750	struct sched_group *group;
2751	struct rq *busiest = NULL;
2752	unsigned long imbalance;
2753	int nr_moved = 0;
2754	int sd_idle = 0;
2755	cpumask_t cpus = CPU_MASK_ALL;
2756
2757	/*
2758	* When power savings policy is enabled for the parent domain, idle
2759	* sibling can pick up load irrespective of busy siblings. In this case,
2760	* let the state of idle sibling percolate up as IDLE, instead of
2761	* portraying it as NOT_IDLE.
2762	*/
2763	if (sd->flags & SD_SHARE_CPUPOWER &&
2764	!test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
2765	sd_idle = 1;
2766
2767	schedstat_inc(sd, lb_cnt[NEWLY_IDLE]);
2768	redo:
2769	group = find_busiest_group(sd, this_cpu, &imbalance, NEWLY_IDLE,
2770	&sd_idle, &cpus, NULL);
2771	if (!group) {
2772	schedstat_inc(sd, lb_nobusyg[NEWLY_IDLE]);
2773	goto out_balanced;
2774	}
2775
2776	busiest = find_busiest_queue(group, NEWLY_IDLE, imbalance,
2777	&cpus);
2778	if (!busiest) {
2779	schedstat_inc(sd, lb_nobusyq[NEWLY_IDLE]);
2780	goto out_balanced;
2781	}
2782
2783	BUG_ON(busiest == this_rq);
2784
2785	schedstat_add(sd, lb_imbalance[NEWLY_IDLE], imbalance);
2786
2787	nr_moved = 0;
2788	if (busiest->nr_running > 1) {
2789	/* Attempt to move tasks */
2790	double_lock_balance(this_rq, busiest);
2791	nr_moved = move_tasks(this_rq, this_cpu, busiest,
2792	minus_1_or_zero(busiest->nr_running),
2793	imbalance, sd, NEWLY_IDLE, NULL);
2794	spin_unlock(&busiest->lock);
2795
2796	if (!nr_moved) {
2797	cpu_clear(cpu_of(busiest), cpus);
2798	if (!cpus_empty(cpus))
2799	goto redo;
2800	}
2801	}
2802
2803	if (!nr_moved) {
2804	schedstat_inc(sd, lb_failed[NEWLY_IDLE]);
2805	if (!sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
2806	!test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
2807	return -1;
2808	} else
2809	sd->nr_balance_failed = 0;
2810
2811	return nr_moved;
2812
2813	out_balanced:
2814	schedstat_inc(sd, lb_balanced[NEWLY_IDLE]);
2815	if (!sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
2816	!test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
2817	return -1;
2818	sd->nr_balance_failed = 0;
2819
2820	return 0;
2821	}
2822
2823	/*
2824	* idle_balance is called by schedule() if this_cpu is about to become
2825	* idle. Attempts to pull tasks from other CPUs.
2826	*/
2827	static void idle_balance(int this_cpu, struct rq *this_rq)
2828	{
2829	struct sched_domain *sd;
2830	int pulled_task = 0;
2831	unsigned long next_balance = jiffies + 60 * HZ;
2832
2833	for_each_domain(this_cpu, sd) {
2834	if (sd->flags & SD_BALANCE_NEWIDLE) {
2835	/* If we've pulled tasks over stop searching: */
2836	pulled_task = load_balance_newidle(this_cpu,
2837	this_rq, sd);
2838	if (time_after(next_balance,
2839	sd->last_balance + sd->balance_interval))
2840	next_balance = sd->last_balance
2841	+ sd->balance_interval;
2842	if (pulled_task)
2843	break;
2844	}
2845	}
2846	if (!pulled_task)
2847	/*
2848	* We are going idle. next_balance may be set based on
2849	* a busy processor. So reset next_balance.
2850	*/
2851	this_rq->next_balance = next_balance;
2852	}
2853
2854	/*
2855	* active_load_balance is run by migration threads. It pushes running tasks
2856	* off the busiest CPU onto idle CPUs. It requires at least 1 task to be
2857	* running on each physical CPU where possible, and avoids physical /
2858	* logical imbalances.
2859	*
2860	* Called with busiest_rq locked.
2861	*/
2862	static void active_load_balance(struct rq *busiest_rq, int busiest_cpu)
2863	{
2864	int target_cpu = busiest_rq->push_cpu;
2865	struct sched_domain *sd;
2866	struct rq *target_rq;
2867
2868	/* Is there any task to move? */
2869	if (busiest_rq->nr_running <= 1)
2870	return;
2871
2872	target_rq = cpu_rq(target_cpu);
2873
2874	/*
2875	* This condition is "impossible", if it occurs
2876	* we need to fix it. Originally reported by
2877	* Bjorn Helgaas on a 128-cpu setup.
2878	*/
2879	BUG_ON(busiest_rq == target_rq);
2880
2881	/* move a task from busiest_rq to target_rq */
2882	double_lock_balance(busiest_rq, target_rq);
2883
2884	/* Search for an sd spanning us and the target CPU. */
2885	for_each_domain(target_cpu, sd) {
2886	if ((sd->flags & SD_LOAD_BALANCE) &&
2887	cpu_isset(busiest_cpu, sd->span))
2888	break;
2889	}
2890
2891	if (likely(sd)) {
2892	schedstat_inc(sd, alb_cnt);
2893
2894	if (move_tasks(target_rq, target_cpu, busiest_rq, 1,
2895	RTPRIO_TO_LOAD_WEIGHT(100), sd, SCHED_IDLE,
2896	NULL))
2897	schedstat_inc(sd, alb_pushed);
2898	else
2899	schedstat_inc(sd, alb_failed);
2900	}
2901	spin_unlock(&target_rq->lock);
2902	}
2903
2904	static void update_load(struct rq *this_rq)
2905	{
2906	unsigned long this_load;
2907	unsigned int i, scale;
2908
2909	this_load = this_rq->raw_weighted_load;
2910
2911	/* Update our load: */
2912	for (i = 0, scale = 1; i < 3; i++, scale += scale) {
2913	unsigned long old_load, new_load;
2914
2915	/* scale is effectively 1 << i now, and >> i divides by scale */
2916
2917	old_load = this_rq->cpu_load[i];
2918	new_load = this_load;
2919	/*
2920	* Round up the averaging division if load is increasing. This
2921	* prevents us from getting stuck on 9 if the load is 10, for
2922	* example.
2923	*/
2924	if (new_load > old_load)
2925	new_load += scale-1;
2926	this_rq->cpu_load[i] = (old_load*(scale-1) + new_load) >> i;
2927	}
2928	}
2929
2930	/*
2931	* run_rebalance_domains is triggered when needed from the scheduler tick.
2932	*
2933	* It checks each scheduling domain to see if it is due to be balanced,
2934	* and initiates a balancing operation if so.
2935	*
2936	* Balancing parameters are set up in arch_init_sched_domains.
2937	*/
2938	static DEFINE_SPINLOCK(balancing);
2939
2940	static void run_rebalance_domains(struct softirq_action *h)
2941	{
2942	int this_cpu = smp_processor_id(), balance = 1;
2943	struct rq *this_rq = cpu_rq(this_cpu);
2944	unsigned long interval;
2945	struct sched_domain *sd;
2946	/*
2947	* We are idle if there are no processes running. This
2948	* is valid even if we are the idle process (SMT).
2949	*/
2950	enum idle_type idle = !this_rq->nr_running ?
2951	SCHED_IDLE : NOT_IDLE;
2952	/* Earliest time when we have to call run_rebalance_domains again */
2953	unsigned long next_balance = jiffies + 60*HZ;
2954
2955	for_each_domain(this_cpu, sd) {
2956	if (!(sd->flags & SD_LOAD_BALANCE))
2957	continue;
2958
2959	interval = sd->balance_interval;
2960	if (idle != SCHED_IDLE)
2961	interval *= sd->busy_factor;
2962
2963	/* scale ms to jiffies */
2964	interval = msecs_to_jiffies(interval);
2965	if (unlikely(!interval))
2966	interval = 1;
2967
2968	if (sd->flags & SD_SERIALIZE) {
2969	if (!spin_trylock(&balancing))
2970	goto out;
2971	}
2972
2973	if (time_after_eq(jiffies, sd->last_balance + interval)) {
2974	if (load_balance(this_cpu, this_rq, sd, idle, &balance)) {
2975	/*
2976	* We've pulled tasks over so either we're no
2977	* longer idle, or one of our SMT siblings is
2978	* not idle.
2979	*/
2980	idle = NOT_IDLE;
2981	}
2982	sd->last_balance = jiffies;
2983	}
2984	if (sd->flags & SD_SERIALIZE)
2985	spin_unlock(&balancing);
2986	out:
2987	if (time_after(next_balance, sd->last_balance + interval))
2988	next_balance = sd->last_balance + interval;
2989
2990	/*
2991	* Stop the load balance at this level. There is another
2992	* CPU in our sched group which is doing load balancing more
2993	* actively.
2994	*/
2995	if (!balance)
2996	break;
2997	}
2998	this_rq->next_balance = next_balance;
2999	}
3000	#else
3001	/*
3002	* on UP we do not need to balance between CPUs:
3003	*/
3004	static inline void idle_balance(int cpu, struct rq *rq)
3005	{
3006	}
3007	#endif
3008
3009	DEFINE_PER_CPU(struct kernel_stat, kstat);
3010
3011	EXPORT_PER_CPU_SYMBOL(kstat);
3012
3013	/*
3014	* This is called on clock ticks and on context switches.
3015	* Bank in p->sched_time the ns elapsed since the last tick or switch.
3016	*/
3017	static inline void
3018	update_cpu_clock(struct task_struct p, struct rq rq, unsigned long long now)
3019	{
3020	p->sched_time += now - p->last_ran;
3021	p->last_ran = rq->most_recent_timestamp = now;
3022	}
3023
3024	/*
3025	* Return current->sched_time plus any more ns on the sched_clock
3026	* that have not yet been banked.
3027	*/
3028	unsigned long long current_sched_time(const struct task_struct *p)
3029	{
3030	unsigned long long ns;
3031	unsigned long flags;
3032
3033	local_irq_save(flags);
3034	ns = p->sched_time + sched_clock() - p->last_ran;
3035	local_irq_restore(flags);
3036
3037	return ns;
3038	}
3039
3040	/*
3041	* We place interactive tasks back into the active array, if possible.
3042	*
3043	* To guarantee that this does not starve expired tasks we ignore the
3044	* interactivity of a task if the first expired task had to wait more
3045	* than a 'reasonable' amount of time. This deadline timeout is
3046	* load-dependent, as the frequency of array switched decreases with
3047	* increasing number of running tasks. We also ignore the interactivity
3048	* if a better static_prio task has expired:
3049	*/
3050	static inline int expired_starving(struct rq *rq)
3051	{
3052	if (rq->curr->static_prio > rq->best_expired_prio)
3053	return 1;
3054	if (!STARVATION_LIMIT \|\| !rq->expired_timestamp)
3055	return 0;
3056	if (jiffies - rq->expired_timestamp > STARVATION_LIMIT * rq->nr_running)
3057	return 1;
3058	return 0;
3059	}
3060
3061	/*
3062	* Account user cpu time to a process.
3063	* @p: the process that the cpu time gets accounted to
3064	* @hardirq_offset: the offset to subtract from hardirq_count()
3065	* @cputime: the cpu time spent in user space since the last update
3066	*/
3067	void account_user_time(struct task_struct *p, cputime_t cputime)
3068	{
3069	struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
3070	cputime64_t tmp;
3071
3072	p->utime = cputime_add(p->utime, cputime);
3073
3074	/* Add user time to cpustat. */
3075	tmp = cputime_to_cputime64(cputime);
3076	if (TASK_NICE(p) > 0)
3077	cpustat->nice = cputime64_add(cpustat->nice, tmp);
3078	else
3079	cpustat->user = cputime64_add(cpustat->user, tmp);
3080	}
3081
3082	/*
3083	* Account system cpu time to a process.
3084	* @p: the process that the cpu time gets accounted to
3085	* @hardirq_offset: the offset to subtract from hardirq_count()
3086	* @cputime: the cpu time spent in kernel space since the last update
3087	*/
3088	void account_system_time(struct task_struct *p, int hardirq_offset,
3089	cputime_t cputime)
3090	{
3091	struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
3092	struct rq *rq = this_rq();
3093	cputime64_t tmp;
3094
3095	p->stime = cputime_add(p->stime, cputime);
3096
3097	/* Add system time to cpustat. */
3098	tmp = cputime_to_cputime64(cputime);
3099	if (hardirq_count() - hardirq_offset)
3100	cpustat->irq = cputime64_add(cpustat->irq, tmp);
3101	else if (softirq_count())
3102	cpustat->softirq = cputime64_add(cpustat->softirq, tmp);
3103	else if (p != rq->idle)
3104	cpustat->system = cputime64_add(cpustat->system, tmp);
3105	else if (atomic_read(&rq->nr_iowait) > 0)
3106	cpustat->iowait = cputime64_add(cpustat->iowait, tmp);
3107	else
3108	cpustat->idle = cputime64_add(cpustat->idle, tmp);
3109	/* Account for system time used */
3110	acct_update_integrals(p);
3111	}
3112
3113	/*
3114	* Account for involuntary wait time.
3115	* @p: the process from which the cpu time has been stolen
3116	* @steal: the cpu time spent in involuntary wait
3117	*/
3118	void account_steal_time(struct task_struct *p, cputime_t steal)
3119	{
3120	struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
3121	cputime64_t tmp = cputime_to_cputime64(steal);
3122	struct rq *rq = this_rq();
3123
3124	if (p == rq->idle) {
3125	p->stime = cputime_add(p->stime, steal);
3126	if (atomic_read(&rq->nr_iowait) > 0)
3127	cpustat->iowait = cputime64_add(cpustat->iowait, tmp);
3128	else
3129	cpustat->idle = cputime64_add(cpustat->idle, tmp);
3130	} else
3131	cpustat->steal = cputime64_add(cpustat->steal, tmp);
3132	}
3133
3134	static void task_running_tick(struct rq rq, struct task_struct p)
3135	{
3136	if (p->array != rq->active) {
3137	/* Task has expired but was not scheduled yet */
3138	set_tsk_need_resched(p);
3139	return;
3140	}
3141	spin_lock(&rq->lock);
3142	/*
3143	* The task was running during this tick - update the
3144	* time slice counter. Note: we do not update a thread's
3145	* priority until it either goes to sleep or uses up its
3146	* timeslice. This makes it possible for interactive tasks
3147	* to use up their timeslices at their highest priority levels.
3148	*/
3149	if (rt_task(p)) {
3150	/*
3151	* RR tasks need a special form of timeslice management.
3152	* FIFO tasks have no timeslices.
3153	*/
3154	if ((p->policy == SCHED_RR) && !--p->time_slice) {
3155	p->time_slice = task_timeslice(p);
3156	p->first_time_slice = 0;
3157	set_tsk_need_resched(p);
3158
3159	/* put it at the end of the queue: */
3160	requeue_task(p, rq->active);
3161	}
3162	goto out_unlock;
3163	}
3164	if (!--p->time_slice) {
3165	dequeue_task(p, rq->active);
3166	set_tsk_need_resched(p);
3167	p->prio = effective_prio(p);
3168	p->time_slice = task_timeslice(p);
3169	p->first_time_slice = 0;
3170
3171	if (!rq->expired_timestamp)
3172	rq->expired_timestamp = jiffies;
3173	if (!TASK_INTERACTIVE(p) \|\| expired_starving(rq)) {
3174	enqueue_task(p, rq->expired);
3175	if (p->static_prio < rq->best_expired_prio)
3176	rq->best_expired_prio = p->static_prio;
3177	} else
3178	enqueue_task(p, rq->active);
3179	} else {
3180	/*
3181	* Prevent a too long timeslice allowing a task to monopolize
3182	* the CPU. We do this by splitting up the timeslice into
3183	* smaller pieces.
3184	*
3185	* Note: this does not mean the task's timeslices expire or
3186	* get lost in any way, they just might be preempted by
3187	* another task of equal priority. (one with higher
3188	* priority would have preempted this task already.) We
3189	* requeue this task to the end of the list on this priority
3190	* level, which is in essence a round-robin of tasks with
3191	* equal priority.
3192	*
3193	* This only applies to tasks in the interactive
3194	* delta range with at least TIMESLICE_GRANULARITY to requeue.
3195	*/
3196	if (TASK_INTERACTIVE(p) && !((task_timeslice(p) -
3197	p->time_slice) % TIMESLICE_GRANULARITY(p)) &&
3198	(p->time_slice >= TIMESLICE_GRANULARITY(p)) &&
3199	(p->array == rq->active)) {
3200
3201	requeue_task(p, rq->active);
3202	set_tsk_need_resched(p);
3203	}
3204	}
3205	out_unlock:
3206	spin_unlock(&rq->lock);
3207	}
3208
3209	/*
3210	* This function gets called by the timer code, with HZ frequency.
3211	* We call it with interrupts disabled.
3212	*
3213	* It also gets called by the fork code, when changing the parent's
3214	* timeslices.
3215	*/
3216	void scheduler_tick(void)
3217	{
3218	unsigned long long now = sched_clock();
3219	struct task_struct *p = current;
3220	int cpu = smp_processor_id();
3221	struct rq *rq = cpu_rq(cpu);
3222
3223	update_cpu_clock(p, rq, now);
3224
3225	if (p != rq->idle)
3226	task_running_tick(rq, p);
3227	#ifdef CONFIG_SMP
3228	update_load(rq);
3229	if (time_after_eq(jiffies, rq->next_balance))
3230	raise_softirq(SCHED_SOFTIRQ);
3231	#endif
3232	}
3233
3234	#if defined(CONFIG_PREEMPT) && defined(CONFIG_DEBUG_PREEMPT)
3235
3236	void fastcall add_preempt_count(int val)
3237	{
3238	/*
3239	* Underflow?
3240	*/
3241	if (DEBUG_LOCKS_WARN_ON((preempt_count() < 0)))
3242	return;
3243	preempt_count() += val;
3244	/*
3245	* Spinlock count overflowing soon?
3246	*/
3247	DEBUG_LOCKS_WARN_ON((preempt_count() & PREEMPT_MASK) >=
3248	PREEMPT_MASK - 10);
3249	}
3250	EXPORT_SYMBOL(add_preempt_count);
3251
3252	void fastcall sub_preempt_count(int val)
3253	{
3254	/*
3255	* Underflow?
3256	*/
3257	if (DEBUG_LOCKS_WARN_ON(val > preempt_count()))
3258	return;
3259	/*
3260	* Is the spinlock portion underflowing?
3261	*/
3262	if (DEBUG_LOCKS_WARN_ON((val < PREEMPT_MASK) &&
3263	!(preempt_count() & PREEMPT_MASK)))
3264	return;
3265
3266	preempt_count() -= val;
3267	}
3268	EXPORT_SYMBOL(sub_preempt_count);
3269
3270	#endif
3271
3272	static inline int interactive_sleep(enum sleep_type sleep_type)
3273	{
3274	return (sleep_type == SLEEP_INTERACTIVE \|\|
3275	sleep_type == SLEEP_INTERRUPTED);
3276	}
3277
3278	/*
3279	* schedule() is the main scheduler function.
3280	*/
3281	asmlinkage void __sched schedule(void)
3282	{
3283	struct task_struct prev, next;
3284	struct prio_array *array;
3285	struct list_head *queue;
3286	unsigned long long now;
3287	unsigned long run_time;
3288	int cpu, idx, new_prio;
3289	long *switch_count;
3290	struct rq *rq;
3291
3292	/*
3293	* Test if we are atomic. Since do_exit() needs to call into
3294	* schedule() atomically, we ignore that path for now.
3295	* Otherwise, whine if we are scheduling when we should not be.
3296	*/
3297	if (unlikely(in_atomic() && !current->exit_state)) {
3298	printk(KERN_ERR "BUG: scheduling while atomic: "
3299	"%s/0x%08x/%d\n",
3300	current->comm, preempt_count(), current->pid);
3301	debug_show_held_locks(current);
3302	if (irqs_disabled())
3303	print_irqtrace_events(current);
3304	dump_stack();
3305	}
3306	profile_hit(SCHED_PROFILING, __builtin_return_address(0));
3307
3308	need_resched:
3309	preempt_disable();
3310	prev = current;
3311	release_kernel_lock(prev);
3312	need_resched_nonpreemptible:
3313	rq = this_rq();
3314
3315	/*
3316	* The idle thread is not allowed to schedule!
3317	* Remove this check after it has been exercised a bit.
3318	*/
3319	if (unlikely(prev == rq->idle) && prev->state != TASK_RUNNING) {
3320	printk(KERN_ERR "bad: scheduling from the idle thread!\n");
3321	dump_stack();
3322	}
3323
3324	schedstat_inc(rq, sched_cnt);
3325	now = sched_clock();
3326	if (likely((long long)(now - prev->timestamp) < NS_MAX_SLEEP_AVG)) {
3327	run_time = now - prev->timestamp;
3328	if (unlikely((long long)(now - prev->timestamp) < 0))
3329	run_time = 0;
3330	} else
3331	run_time = NS_MAX_SLEEP_AVG;
3332
3333	/*
3334	* Tasks charged proportionately less run_time at high sleep_avg to
3335	* delay them losing their interactive status
3336	*/
3337	run_time /= (CURRENT_BONUS(prev) ? : 1);
3338
3339	spin_lock_irq(&rq->lock);
3340
3341	switch_count = &prev->nivcsw;
3342	if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
3343	switch_count = &prev->nvcsw;
3344	if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&
3345	unlikely(signal_pending(prev))))
3346	prev->state = TASK_RUNNING;
3347	else {
3348	if (prev->state == TASK_UNINTERRUPTIBLE)
3349	rq->nr_uninterruptible++;
3350	deactivate_task(prev, rq);
3351	}
3352	}
3353
3354	cpu = smp_processor_id();
3355	if (unlikely(!rq->nr_running)) {
3356	idle_balance(cpu, rq);
3357	if (!rq->nr_running) {
3358	next = rq->idle;
3359	rq->expired_timestamp = 0;
3360	goto switch_tasks;
3361	}
3362	}
3363
3364	array = rq->active;
3365	if (unlikely(!array->nr_active)) {
3366	/*
3367	* Switch the active and expired arrays.
3368	*/
3369	schedstat_inc(rq, sched_switch);
3370	rq->active = rq->expired;
3371	rq->expired = array;
3372	array = rq->active;
3373	rq->expired_timestamp = 0;
3374	rq->best_expired_prio = MAX_PRIO;
3375	}
3376
3377	idx = sched_find_first_bit(array->bitmap);
3378	queue = array->queue + idx;
3379	next = list_entry(queue->next, struct task_struct, run_list);
3380
3381	if (!rt_task(next) && interactive_sleep(next->sleep_type)) {
3382	unsigned long long delta = now - next->timestamp;
3383	if (unlikely((long long)(now - next->timestamp) < 0))
3384	delta = 0;
3385
3386	if (next->sleep_type == SLEEP_INTERACTIVE)
3387	delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;
3388
3389	array = next->array;
3390	new_prio = recalc_task_prio(next, next->timestamp + delta);
3391
3392	if (unlikely(next->prio != new_prio)) {
3393	dequeue_task(next, array);
3394	next->prio = new_prio;
3395	enqueue_task(next, array);
3396	}
3397	}
3398	next->sleep_type = SLEEP_NORMAL;
3399	switch_tasks:
3400	if (next == rq->idle)
3401	schedstat_inc(rq, sched_goidle);
3402	prefetch(next);
3403	prefetch_stack(next);
3404	clear_tsk_need_resched(prev);
3405	rcu_qsctr_inc(task_cpu(prev));
3406
3407	update_cpu_clock(prev, rq, now);
3408
3409	prev->sleep_avg -= run_time;
3410	if ((long)prev->sleep_avg <= 0)
3411	prev->sleep_avg = 0;
3412	prev->timestamp = prev->last_ran = now;
3413
3414	sched_info_switch(prev, next);
3415	if (likely(prev != next)) {
3416	next->timestamp = next->last_ran = now;
3417	rq->nr_switches++;
3418	rq->curr = next;
3419	++*switch_count;
3420
3421	prepare_task_switch(rq, next);
3422	prev = context_switch(rq, prev, next);
3423	barrier();
3424	/*
3425	* this_rq must be evaluated again because prev may have moved
3426	* CPUs since it called schedule(), thus the 'rq' on its stack
3427	* frame will be invalid.
3428	*/
3429	finish_task_switch(this_rq(), prev);
3430	} else
3431	spin_unlock_irq(&rq->lock);
3432
3433	prev = current;
3434	if (unlikely(reacquire_kernel_lock(prev) < 0))
3435	goto need_resched_nonpreemptible;
3436	preempt_enable_no_resched();
3437	if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
3438	goto need_resched;
3439	}
3440	EXPORT_SYMBOL(schedule);
3441
3442	#ifdef CONFIG_PREEMPT
3443	/*
3444	* this is the entry point to schedule() from in-kernel preemption
3445	* off of preempt_enable. Kernel preemptions off return from interrupt
3446	* occur there and call schedule directly.
3447	*/
3448	asmlinkage void __sched preempt_schedule(void)
3449	{
3450	struct thread_info *ti = current_thread_info();
3451	#ifdef CONFIG_PREEMPT_BKL
3452	struct task_struct *task = current;
3453	int saved_lock_depth;
3454	#endif
3455	/*
3456	* If there is a non-zero preempt_count or interrupts are disabled,
3457	* we do not want to preempt the current task. Just return..
3458	*/
3459	if (likely(ti->preempt_count \|\| irqs_disabled()))
3460	return;
3461
3462	need_resched:
3463	add_preempt_count(PREEMPT_ACTIVE);
3464	/*
3465	* We keep the big kernel semaphore locked, but we
3466	* clear ->lock_depth so that schedule() doesnt
3467	* auto-release the semaphore:
3468	*/
3469	#ifdef CONFIG_PREEMPT_BKL
3470	saved_lock_depth = task->lock_depth;
3471	task->lock_depth = -1;
3472	#endif
3473	schedule();
3474	#ifdef CONFIG_PREEMPT_BKL
3475	task->lock_depth = saved_lock_depth;
3476	#endif
3477	sub_preempt_count(PREEMPT_ACTIVE);
3478
3479	/* we could miss a preemption opportunity between schedule and now */
3480	barrier();
3481	if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
3482	goto need_resched;
3483	}
3484	EXPORT_SYMBOL(preempt_schedule);
3485
3486	/*
3487	* this is the entry point to schedule() from kernel preemption
3488	* off of irq context.
3489	* Note, that this is called and return with irqs disabled. This will
3490	* protect us against recursive calling from irq.
3491	*/
3492	asmlinkage void __sched preempt_schedule_irq(void)
3493	{
3494	struct thread_info *ti = current_thread_info();
3495	#ifdef CONFIG_PREEMPT_BKL
3496	struct task_struct *task = current;
3497	int saved_lock_depth;
3498	#endif
3499	/* Catch callers which need to be fixed */
3500	BUG_ON(ti->preempt_count \|\| !irqs_disabled());
3501
3502	need_resched:
3503	add_preempt_count(PREEMPT_ACTIVE);
3504	/*
3505	* We keep the big kernel semaphore locked, but we
3506	* clear ->lock_depth so that schedule() doesnt
3507	* auto-release the semaphore:
3508	*/
3509	#ifdef CONFIG_PREEMPT_BKL
3510	saved_lock_depth = task->lock_depth;
3511	task->lock_depth = -1;
3512	#endif
3513	local_irq_enable();
3514	schedule();
3515	local_irq_disable();
3516	#ifdef CONFIG_PREEMPT_BKL
3517	task->lock_depth = saved_lock_depth;
3518	#endif
3519	sub_preempt_count(PREEMPT_ACTIVE);
3520
3521	/* we could miss a preemption opportunity between schedule and now */
3522	barrier();
3523	if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
3524	goto need_resched;
3525	}
3526
3527	#endif /* CONFIG_PREEMPT */
3528
3529	int default_wake_function(wait_queue_t *curr, unsigned mode, int sync,
3530	void *key)
3531	{
3532	return try_to_wake_up(curr->private, mode, sync);
3533	}
3534	EXPORT_SYMBOL(default_wake_function);
3535
3536	/*
3537	* The core wakeup function. Non-exclusive wakeups (nr_exclusive == 0) just
3538	* wake everything up. If it's an exclusive wakeup (nr_exclusive == small +ve
3539	* number) then we wake all the non-exclusive tasks and one exclusive task.
3540	*
3541	* There are circumstances in which we can try to wake a task which has already
3542	* started to run but is not in state TASK_RUNNING. try_to_wake_up() returns
3543	* zero in this (rare) case, and we handle it by continuing to scan the queue.
3544	*/
3545	static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
3546	int nr_exclusive, int sync, void *key)
3547	{
3548	struct list_head tmp, next;
3549
3550	list_for_each_safe(tmp, next, &q->task_list) {
3551	wait_queue_t *curr = list_entry(tmp, wait_queue_t, task_list);
3552	unsigned flags = curr->flags;
3553
3554	if (curr->func(curr, mode, sync, key) &&
3555	(flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
3556	break;
3557	}
3558	}
3559
3560	/**
3561	* __wake_up - wake up threads blocked on a waitqueue.
3562	* @q: the waitqueue
3563	* @mode: which threads
3564	* @nr_exclusive: how many wake-one or wake-many threads to wake up
3565	* @key: is directly passed to the wakeup function
3566	*/
3567	void fastcall __wake_up(wait_queue_head_t *q, unsigned int mode,
3568	int nr_exclusive, void *key)
3569	{
3570	unsigned long flags;
3571
3572	spin_lock_irqsave(&q->lock, flags);
3573	__wake_up_common(q, mode, nr_exclusive, 0, key);
3574	spin_unlock_irqrestore(&q->lock, flags);
3575	}
3576	EXPORT_SYMBOL(__wake_up);
3577
3578	/*
3579	* Same as __wake_up but called with the spinlock in wait_queue_head_t held.
3580	*/
3581	void fastcall __wake_up_locked(wait_queue_head_t *q, unsigned int mode)
3582	{
3583	__wake_up_common(q, mode, 1, 0, NULL);
3584	}
3585
3586	/**
3587	* __wake_up_sync - wake up threads blocked on a waitqueue.
3588	* @q: the waitqueue
3589	* @mode: which threads
3590	* @nr_exclusive: how many wake-one or wake-many threads to wake up
3591	*
3592	* The sync wakeup differs that the waker knows that it will schedule
3593	* away soon, so while the target thread will be woken up, it will not
3594	* be migrated to another CPU - ie. the two threads are 'synchronized'
3595	* with each other. This can prevent needless bouncing between CPUs.
3596	*
3597	* On UP it can prevent extra preemption.
3598	*/
3599	void fastcall
3600	__wake_up_sync(wait_queue_head_t *q, unsigned int mode, int nr_exclusive)
3601	{
3602	unsigned long flags;
3603	int sync = 1;
3604
3605	if (unlikely(!q))
3606	return;
3607
3608	if (unlikely(!nr_exclusive))
3609	sync = 0;
3610
3611	spin_lock_irqsave(&q->lock, flags);
3612	__wake_up_common(q, mode, nr_exclusive, sync, NULL);
3613	spin_unlock_irqrestore(&q->lock, flags);
3614	}
3615	EXPORT_SYMBOL_GPL(__wake_up_sync); /* For internal use only */
3616
3617	void fastcall complete(struct completion *x)
3618	{
3619	unsigned long flags;
3620
3621	spin_lock_irqsave(&x->wait.lock, flags);
3622	x->done++;
3623	__wake_up_common(&x->wait, TASK_UNINTERRUPTIBLE \| TASK_INTERRUPTIBLE,
3624	1, 0, NULL);
3625	spin_unlock_irqrestore(&x->wait.lock, flags);
3626	}
3627	EXPORT_SYMBOL(complete);
3628
3629	void fastcall complete_all(struct completion *x)
3630	{
3631	unsigned long flags;
3632
3633	spin_lock_irqsave(&x->wait.lock, flags);
3634	x->done += UINT_MAX/2;
3635	__wake_up_common(&x->wait, TASK_UNINTERRUPTIBLE \| TASK_INTERRUPTIBLE,
3636	0, 0, NULL);
3637	spin_unlock_irqrestore(&x->wait.lock, flags);
3638	}
3639	EXPORT_SYMBOL(complete_all);
3640
3641	void fastcall __sched wait_for_completion(struct completion *x)
3642	{
3643	might_sleep();
3644
3645	spin_lock_irq(&x->wait.lock);
3646	if (!x->done) {
3647	DECLARE_WAITQUEUE(wait, current);
3648
3649	wait.flags \|= WQ_FLAG_EXCLUSIVE;
3650	__add_wait_queue_tail(&x->wait, &wait);
3651	do {
3652	__set_current_state(TASK_UNINTERRUPTIBLE);
3653	spin_unlock_irq(&x->wait.lock);
3654	schedule();
3655	spin_lock_irq(&x->wait.lock);
3656	} while (!x->done);
3657	__remove_wait_queue(&x->wait, &wait);
3658	}
3659	x->done--;
3660	spin_unlock_irq(&x->wait.lock);
3661	}
3662	EXPORT_SYMBOL(wait_for_completion);
3663
3664	unsigned long fastcall __sched
3665	wait_for_completion_timeout(struct completion *x, unsigned long timeout)
3666	{
3667	might_sleep();
3668
3669	spin_lock_irq(&x->wait.lock);
3670	if (!x->done) {
3671	DECLARE_WAITQUEUE(wait, current);
3672
3673	wait.flags \|= WQ_FLAG_EXCLUSIVE;
3674	__add_wait_queue_tail(&x->wait, &wait);
3675	do {
3676	__set_current_state(TASK_UNINTERRUPTIBLE);
3677	spin_unlock_irq(&x->wait.lock);
3678	timeout = schedule_timeout(timeout);
3679	spin_lock_irq(&x->wait.lock);
3680	if (!timeout) {
3681	__remove_wait_queue(&x->wait, &wait);
3682	goto out;
3683	}
3684	} while (!x->done);
3685	__remove_wait_queue(&x->wait, &wait);
3686	}
3687	x->done--;
3688	out:
3689	spin_unlock_irq(&x->wait.lock);
3690	return timeout;
3691	}
3692	EXPORT_SYMBOL(wait_for_completion_timeout);
3693
3694	int fastcall __sched wait_for_completion_interruptible(struct completion *x)
3695	{
3696	int ret = 0;
3697
3698	might_sleep();
3699
3700	spin_lock_irq(&x->wait.lock);
3701	if (!x->done) {
3702	DECLARE_WAITQUEUE(wait, current);
3703
3704	wait.flags \|= WQ_FLAG_EXCLUSIVE;
3705	__add_wait_queue_tail(&x->wait, &wait);
3706	do {
3707	if (signal_pending(current)) {
3708	ret = -ERESTARTSYS;
3709	__remove_wait_queue(&x->wait, &wait);
3710	goto out;
3711	}
3712	__set_current_state(TASK_INTERRUPTIBLE);
3713	spin_unlock_irq(&x->wait.lock);
3714	schedule();
3715	spin_lock_irq(&x->wait.lock);
3716	} while (!x->done);
3717	__remove_wait_queue(&x->wait, &wait);
3718	}
3719	x->done--;
3720	out:
3721	spin_unlock_irq(&x->wait.lock);
3722
3723	return ret;
3724	}
3725	EXPORT_SYMBOL(wait_for_completion_interruptible);
3726
3727	unsigned long fastcall __sched
3728	wait_for_completion_interruptible_timeout(struct completion *x,
3729	unsigned long timeout)
3730	{
3731	might_sleep();
3732
3733	spin_lock_irq(&x->wait.lock);
3734	if (!x->done) {
3735	DECLARE_WAITQUEUE(wait, current);
3736
3737	wait.flags \|= WQ_FLAG_EXCLUSIVE;
3738	__add_wait_queue_tail(&x->wait, &wait);
3739	do {
3740	if (signal_pending(current)) {
3741	timeout = -ERESTARTSYS;
3742	__remove_wait_queue(&x->wait, &wait);
3743	goto out;
3744	}
3745	__set_current_state(TASK_INTERRUPTIBLE);
3746	spin_unlock_irq(&x->wait.lock);
3747	timeout = schedule_timeout(timeout);
3748	spin_lock_irq(&x->wait.lock);
3749	if (!timeout) {
3750	__remove_wait_queue(&x->wait, &wait);
3751	goto out;
3752	}
3753	} while (!x->done);
3754	__remove_wait_queue(&x->wait, &wait);
3755	}
3756	x->done--;
3757	out:
3758	spin_unlock_irq(&x->wait.lock);
3759	return timeout;
3760	}
3761	EXPORT_SYMBOL(wait_for_completion_interruptible_timeout);
3762
3763
3764	#define SLEEP_ON_VAR \
3765	unsigned long flags; \
3766	wait_queue_t wait; \
3767	init_waitqueue_entry(&wait, current);
3768
3769	#define SLEEP_ON_HEAD \
3770	spin_lock_irqsave(&q->lock,flags); \
3771	__add_wait_queue(q, &wait); \
3772	spin_unlock(&q->lock);
3773
3774	#define SLEEP_ON_TAIL \
3775	spin_lock_irq(&q->lock); \
3776	__remove_wait_queue(q, &wait); \
3777	spin_unlock_irqrestore(&q->lock, flags);
3778
3779	void fastcall __sched interruptible_sleep_on(wait_queue_head_t *q)
3780	{
3781	SLEEP_ON_VAR
3782
3783	current->state = TASK_INTERRUPTIBLE;
3784
3785	SLEEP_ON_HEAD
3786	schedule();
3787	SLEEP_ON_TAIL
3788	}
3789	EXPORT_SYMBOL(interruptible_sleep_on);
3790
3791	long fastcall __sched
3792	interruptible_sleep_on_timeout(wait_queue_head_t *q, long timeout)
3793	{
3794	SLEEP_ON_VAR
3795
3796	current->state = TASK_INTERRUPTIBLE;
3797
3798	SLEEP_ON_HEAD
3799	timeout = schedule_timeout(timeout);
3800	SLEEP_ON_TAIL
3801
3802	return timeout;
3803	}
3804	EXPORT_SYMBOL(interruptible_sleep_on_timeout);
3805
3806	void fastcall __sched sleep_on(wait_queue_head_t *q)
3807	{
3808	SLEEP_ON_VAR
3809
3810	current->state = TASK_UNINTERRUPTIBLE;
3811
3812	SLEEP_ON_HEAD
3813	schedule();
3814	SLEEP_ON_TAIL
3815	}
3816	EXPORT_SYMBOL(sleep_on);
3817
3818	long fastcall __sched sleep_on_timeout(wait_queue_head_t *q, long timeout)
3819	{
3820	SLEEP_ON_VAR
3821
3822	current->state = TASK_UNINTERRUPTIBLE;
3823
3824	SLEEP_ON_HEAD
3825	timeout = schedule_timeout(timeout);
3826	SLEEP_ON_TAIL
3827
3828	return timeout;
3829	}
3830
3831	EXPORT_SYMBOL(sleep_on_timeout);
3832
3833	#ifdef CONFIG_RT_MUTEXES
3834
3835	/*
3836	* rt_mutex_setprio - set the current priority of a task
3837	* @p: task
3838	* @prio: prio value (kernel-internal form)
3839	*
3840	* This function changes the 'effective' priority of a task. It does
3841	* not touch ->normal_prio like __setscheduler().
3842	*
3843	* Used by the rt_mutex code to implement priority inheritance logic.
3844	*/
3845	void rt_mutex_setprio(struct task_struct *p, int prio)
3846	{
3847	struct prio_array *array;
3848	unsigned long flags;
3849	struct rq *rq;
3850	int oldprio;
3851
3852	BUG_ON(prio < 0 \|\| prio > MAX_PRIO);
3853
3854	rq = task_rq_lock(p, &flags);
3855
3856	oldprio = p->prio;
3857	array = p->array;
3858	if (array)
3859	dequeue_task(p, array);
3860	p->prio = prio;
3861
3862	if (array) {
3863	/*
3864	* If changing to an RT priority then queue it
3865	* in the active array!
3866	*/
3867	if (rt_task(p))
3868	array = rq->active;
3869	enqueue_task(p, array);
3870	/*
3871	* Reschedule if we are currently running on this runqueue and
3872	* our priority decreased, or if we are not currently running on
3873	* this runqueue and our priority is higher than the current's
3874	*/
3875	if (task_running(rq, p)) {
3876	if (p->prio > oldprio)
3877	resched_task(rq->curr);
3878	} else if (TASK_PREEMPTS_CURR(p, rq))
3879	resched_task(rq->curr);
3880	}
3881	task_rq_unlock(rq, &flags);
3882	}
3883
3884	#endif
3885
3886	void set_user_nice(struct task_struct *p, long nice)
3887	{
3888	struct prio_array *array;
3889	int old_prio, delta;
3890	unsigned long flags;
3891	struct rq *rq;
3892
3893	if (TASK_NICE(p) == nice \|\| nice < -20 \|\| nice > 19)
3894	return;
3895	/*
3896	* We have to be careful, if called from sys_setpriority(),
3897	* the task might be in the middle of scheduling on another CPU.
3898	*/
3899	rq = task_rq_lock(p, &flags);
3900	/*
3901	* The RT priorities are set via sched_setscheduler(), but we still
3902	* allow the 'normal' nice value to be set - but as expected
3903	* it wont have any effect on scheduling until the task is
3904	* not SCHED_NORMAL/SCHED_BATCH:
3905	*/
3906	if (has_rt_policy(p)) {
3907	p->static_prio = NICE_TO_PRIO(nice);
3908	goto out_unlock;
3909	}
3910	array = p->array;
3911	if (array) {
3912	dequeue_task(p, array);
3913	dec_raw_weighted_load(rq, p);
3914	}
3915
3916	p->static_prio = NICE_TO_PRIO(nice);
3917	set_load_weight(p);
3918	old_prio = p->prio;
3919	p->prio = effective_prio(p);
3920	delta = p->prio - old_prio;
3921
3922	if (array) {
3923	enqueue_task(p, array);
3924	inc_raw_weighted_load(rq, p);
3925	/*
3926	* If the task increased its priority or is running and
3927	* lowered its priority, then reschedule its CPU:
3928	*/
3929	if (delta < 0 \|\| (delta > 0 && task_running(rq, p)))
3930	resched_task(rq->curr);
3931	}
3932	out_unlock:
3933	task_rq_unlock(rq, &flags);
3934	}
3935	EXPORT_SYMBOL(set_user_nice);
3936
3937	/*
3938	* can_nice - check if a task can reduce its nice value
3939	* @p: task
3940	* @nice: nice value
3941	*/
3942	int can_nice(const struct task_struct *p, const int nice)
3943	{
3944	/* convert nice value [19,-20] to rlimit style value [1,40] */
3945	int nice_rlim = 20 - nice;
3946
3947	return (nice_rlim <= p->signal->rlim[RLIMIT_NICE].rlim_cur \|\|
3948	capable(CAP_SYS_NICE));
3949	}
3950
3951	#ifdef __ARCH_WANT_SYS_NICE
3952
3953	/*
3954	* sys_nice - change the priority of the current process.
3955	* @increment: priority increment
3956	*
3957	* sys_setpriority is a more generic, but much slower function that
3958	* does similar things.
3959	*/
3960	asmlinkage long sys_nice(int increment)
3961	{
3962	long nice, retval;
3963
3964	/*
3965	* Setpriority might change our priority at the same moment.
3966	* We don't have to worry. Conceptually one call occurs first
3967	* and we have a single winner.
3968	*/
3969	if (increment < -40)
3970	increment = -40;
3971	if (increment > 40)
3972	increment = 40;
3973
3974	nice = PRIO_TO_NICE(current->static_prio) + increment;
3975	if (nice < -20)
3976	nice = -20;
3977	if (nice > 19)
3978	nice = 19;
3979
3980	if (increment < 0 && !can_nice(current, nice))
3981	return -EPERM;
3982
3983	retval = security_task_setnice(current, nice);
3984	if (retval)
3985	return retval;
3986
3987	set_user_nice(current, nice);
3988	return 0;
3989	}
3990
3991	#endif
3992
3993	/**
3994	* task_prio - return the priority value of a given task.
3995	* @p: the task in question.
3996	*
3997	* This is the priority value as seen by users in /proc.
3998	* RT tasks are offset by -200. Normal tasks are centered
3999	* around 0, value goes from -16 to +15.
4000	*/
4001	int task_prio(const struct task_struct *p)
4002	{
4003	return p->prio - MAX_RT_PRIO;
4004	}
4005
4006	/**
4007	* task_nice - return the nice value of a given task.
4008	* @p: the task in question.
4009	*/
4010	int task_nice(const struct task_struct *p)
4011	{
4012	return TASK_NICE(p);
4013	}
4014	EXPORT_SYMBOL_GPL(task_nice);
4015
4016	/**
4017	* idle_cpu - is a given cpu idle currently?
4018	* @cpu: the processor in question.
4019	*/
4020	int idle_cpu(int cpu)
4021	{
4022	return cpu_curr(cpu) == cpu_rq(cpu)->idle;
4023	}
4024
4025	/**
4026	* idle_task - return the idle task for a given cpu.
4027	* @cpu: the processor in question.
4028	*/
4029	struct task_struct *idle_task(int cpu)
4030	{
4031	return cpu_rq(cpu)->idle;
4032	}
4033
4034	/**
4035	* find_process_by_pid - find a process with a matching PID value.
4036	* @pid: the pid in question.
4037	*/
4038	static inline struct task_struct *find_process_by_pid(pid_t pid)
4039	{
4040	return pid ? find_task_by_pid(pid) : current;
4041	}
4042
4043	/* Actually do priority change: must hold rq lock. */
4044	static void __setscheduler(struct task_struct *p, int policy, int prio)
4045	{
4046	BUG_ON(p->array);
4047
4048	p->policy = policy;
4049	p->rt_priority = prio;
4050	p->normal_prio = normal_prio(p);
4051	/* we are holding p->pi_lock already */
4052	p->prio = rt_mutex_getprio(p);
4053	/*
4054	* SCHED_BATCH tasks are treated as perpetual CPU hogs:
4055	*/
4056	if (policy == SCHED_BATCH)
4057	p->sleep_avg = 0;
4058	set_load_weight(p);
4059	}
4060
4061	/**
4062	* sched_setscheduler - change the scheduling policy and/or RT priority of a thread.
4063	* @p: the task in question.
4064	* @policy: new policy.
4065	* @param: structure containing the new RT priority.
4066	*
4067	* NOTE that the task may be already dead.
4068	*/
4069	int sched_setscheduler(struct task_struct *p, int policy,
4070	struct sched_param *param)
4071	{
4072	int retval, oldprio, oldpolicy = -1;
4073	struct prio_array *array;
4074	unsigned long flags;
4075	struct rq *rq;
4076
4077	/* may grab non-irq protected spin_locks */
4078	BUG_ON(in_interrupt());
4079	recheck:
4080	/* double check policy once rq lock held */
4081	if (policy < 0)
4082	policy = oldpolicy = p->policy;
4083	else if (policy != SCHED_FIFO && policy != SCHED_RR &&
4084	policy != SCHED_NORMAL && policy != SCHED_BATCH)
4085	return -EINVAL;
4086	/*
4087	* Valid priorities for SCHED_FIFO and SCHED_RR are
4088	* 1..MAX_USER_RT_PRIO-1, valid priority for SCHED_NORMAL and
4089	* SCHED_BATCH is 0.
4090	*/
4091	if (param->sched_priority < 0 \|\|
4092	(p->mm && param->sched_priority > MAX_USER_RT_PRIO-1) \|\|
4093	(!p->mm && param->sched_priority > MAX_RT_PRIO-1))
4094	return -EINVAL;
4095	if (is_rt_policy(policy) != (param->sched_priority != 0))
4096	return -EINVAL;
4097
4098	/*
4099	* Allow unprivileged RT tasks to decrease priority:
4100	*/
4101	if (!capable(CAP_SYS_NICE)) {
4102	if (is_rt_policy(policy)) {
4103	unsigned long rlim_rtprio;
4104	unsigned long flags;
4105
4106	if (!lock_task_sighand(p, &flags))
4107	return -ESRCH;
4108	rlim_rtprio = p->signal->rlim[RLIMIT_RTPRIO].rlim_cur;
4109	unlock_task_sighand(p, &flags);
4110
4111	/* can't set/change the rt policy */
4112	if (policy != p->policy && !rlim_rtprio)
4113	return -EPERM;
4114
4115	/* can't increase priority */
4116	if (param->sched_priority > p->rt_priority &&
4117	param->sched_priority > rlim_rtprio)
4118	return -EPERM;
4119	}
4120
4121	/* can't change other user's priorities */
4122	if ((current->euid != p->euid) &&
4123	(current->euid != p->uid))
4124	return -EPERM;
4125	}
4126
4127	retval = security_task_setscheduler(p, policy, param);
4128	if (retval)
4129	return retval;
4130	/*
4131	* make sure no PI-waiters arrive (or leave) while we are
4132	* changing the priority of the task:
4133	*/
4134	spin_lock_irqsave(&p->pi_lock, flags);
4135	/*
4136	* To be able to change p->policy safely, the apropriate
4137	* runqueue lock must be held.
4138	*/
4139	rq = __task_rq_lock(p);
4140	/* recheck policy now with rq lock held */
4141	if (unlikely(oldpolicy != -1 && oldpolicy != p->policy)) {
4142	policy = oldpolicy = -1;
4143	__task_rq_unlock(rq);
4144	spin_unlock_irqrestore(&p->pi_lock, flags);
4145	goto recheck;
4146	}
4147	array = p->array;
4148	if (array)
4149	deactivate_task(p, rq);
4150	oldprio = p->prio;
4151	__setscheduler(p, policy, param->sched_priority);
4152	if (array) {
4153	__activate_task(p, rq);
4154	/*
4155	* Reschedule if we are currently running on this runqueue and
4156	* our priority decreased, or if we are not currently running on
4157	* this runqueue and our priority is higher than the current's
4158	*/
4159	if (task_running(rq, p)) {
4160	if (p->prio > oldprio)
4161	resched_task(rq->curr);
4162	} else if (TASK_PREEMPTS_CURR(p, rq))
4163	resched_task(rq->curr);
4164	}
4165	__task_rq_unlock(rq);
4166	spin_unlock_irqrestore(&p->pi_lock, flags);
4167
4168	rt_mutex_adjust_pi(p);
4169
4170	return 0;
4171	}
4172	EXPORT_SYMBOL_GPL(sched_setscheduler);
4173
4174	static int
4175	do_sched_setscheduler(pid_t pid, int policy, struct sched_param __user *param)
4176	{
4177	struct sched_param lparam;
4178	struct task_struct *p;
4179	int retval;
4180
4181	if (!param \|\| pid < 0)
4182	return -EINVAL;
4183	if (copy_from_user(&lparam, param, sizeof(struct sched_param)))
4184	return -EFAULT;
4185
4186	rcu_read_lock();
4187	retval = -ESRCH;
4188	p = find_process_by_pid(pid);
4189	if (p != NULL)
4190	retval = sched_setscheduler(p, policy, &lparam);
4191	rcu_read_unlock();
4192
4193	return retval;
4194	}
4195
4196	/**
4197	* sys_sched_setscheduler - set/change the scheduler policy and RT priority
4198	* @pid: the pid in question.
4199	* @policy: new policy.
4200	* @param: structure containing the new RT priority.
4201	*/
4202	asmlinkage long sys_sched_setscheduler(pid_t pid, int policy,
4203	struct sched_param __user *param)
4204	{
4205	/* negative values for policy are not valid */
4206	if (policy < 0)
4207	return -EINVAL;
4208
4209	return do_sched_setscheduler(pid, policy, param);
4210	}
4211
4212	/**
4213	* sys_sched_setparam - set/change the RT priority of a thread
4214	* @pid: the pid in question.
4215	* @param: structure containing the new RT priority.
4216	*/
4217	asmlinkage long sys_sched_setparam(pid_t pid, struct sched_param __user *param)
4218	{
4219	return do_sched_setscheduler(pid, -1, param);
4220	}
4221
4222	/**
4223	* sys_sched_getscheduler - get the policy (scheduling class) of a thread
4224	* @pid: the pid in question.
4225	*/
4226	asmlinkage long sys_sched_getscheduler(pid_t pid)
4227	{
4228	struct task_struct *p;
4229	int retval = -EINVAL;
4230
4231	if (pid < 0)
4232	goto out_nounlock;
4233
4234	retval = -ESRCH;
4235	read_lock(&tasklist_lock);
4236	p = find_process_by_pid(pid);
4237	if (p) {
4238	retval = security_task_getscheduler(p);
4239	if (!retval)
4240	retval = p->policy;
4241	}
4242	read_unlock(&tasklist_lock);
4243
4244	out_nounlock:
4245	return retval;
4246	}
4247
4248	/**
4249	* sys_sched_getscheduler - get the RT priority of a thread
4250	* @pid: the pid in question.
4251	* @param: structure containing the RT priority.
4252	*/
4253	asmlinkage long sys_sched_getparam(pid_t pid, struct sched_param __user *param)
4254	{
4255	struct sched_param lp;
4256	struct task_struct *p;
4257	int retval = -EINVAL;
4258
4259	if (!param \|\| pid < 0)
4260	goto out_nounlock;
4261
4262	read_lock(&tasklist_lock);
4263	p = find_process_by_pid(pid);
4264	retval = -ESRCH;
4265	if (!p)
4266	goto out_unlock;
4267
4268	retval = security_task_getscheduler(p);
4269	if (retval)
4270	goto out_unlock;
4271
4272	lp.sched_priority = p->rt_priority;
4273	read_unlock(&tasklist_lock);
4274
4275	/*
4276	* This one might sleep, we cannot do it with a spinlock held ...
4277	*/
4278	retval = copy_to_user(param, &lp, sizeof(*param)) ? -EFAULT : 0;
4279
4280	out_nounlock:
4281	return retval;
4282
4283	out_unlock:
4284	read_unlock(&tasklist_lock);
4285	return retval;
4286	}
4287
4288	long sched_setaffinity(pid_t pid, cpumask_t new_mask)
4289	{
4290	cpumask_t cpus_allowed;
4291	struct task_struct *p;
4292	int retval;
4293
4294	lock_cpu_hotplug();
4295	read_lock(&tasklist_lock);
4296
4297	p = find_process_by_pid(pid);
4298	if (!p) {
4299	read_unlock(&tasklist_lock);
4300	unlock_cpu_hotplug();
4301	return -ESRCH;
4302	}
4303
4304	/*
4305	* It is not safe to call set_cpus_allowed with the
4306	* tasklist_lock held. We will bump the task_struct's
4307	* usage count and then drop tasklist_lock.
4308	*/
4309	get_task_struct(p);
4310	read_unlock(&tasklist_lock);
4311
4312	retval = -EPERM;
4313	if ((current->euid != p->euid) && (current->euid != p->uid) &&
4314	!capable(CAP_SYS_NICE))
4315	goto out_unlock;
4316
4317	retval = security_task_setscheduler(p, 0, NULL);
4318	if (retval)
4319	goto out_unlock;
4320
4321	cpus_allowed = cpuset_cpus_allowed(p);
4322	cpus_and(new_mask, new_mask, cpus_allowed);
4323	retval = set_cpus_allowed(p, new_mask);
4324
4325	out_unlock:
4326	put_task_struct(p);
4327	unlock_cpu_hotplug();
4328	return retval;
4329	}
4330
4331	static int get_user_cpu_mask(unsigned long __user *user_mask_ptr, unsigned len,
4332	cpumask_t *new_mask)
4333	{
4334	if (len < sizeof(cpumask_t)) {
4335	memset(new_mask, 0, sizeof(cpumask_t));
4336	} else if (len > sizeof(cpumask_t)) {
4337	len = sizeof(cpumask_t);
4338	}
4339	return copy_from_user(new_mask, user_mask_ptr, len) ? -EFAULT : 0;
4340	}
4341
4342	/**
4343	* sys_sched_setaffinity - set the cpu affinity of a process
4344	* @pid: pid of the process
4345	* @len: length in bytes of the bitmask pointed to by user_mask_ptr
4346	* @user_mask_ptr: user-space pointer to the new cpu mask
4347	*/
4348	asmlinkage long sys_sched_setaffinity(pid_t pid, unsigned int len,
4349	unsigned long __user *user_mask_ptr)
4350	{
4351	cpumask_t new_mask;
4352	int retval;
4353
4354	retval = get_user_cpu_mask(user_mask_ptr, len, &new_mask);
4355	if (retval)
4356	return retval;
4357
4358	return sched_setaffinity(pid, new_mask);
4359	}
4360
4361	/*
4362	* Represents all cpu's present in the system
4363	* In systems capable of hotplug, this map could dynamically grow
4364	* as new cpu's are detected in the system via any platform specific
4365	* method, such as ACPI for e.g.
4366	*/
4367
4368	cpumask_t cpu_present_map __read_mostly;
4369	EXPORT_SYMBOL(cpu_present_map);
4370
4371	#ifndef CONFIG_SMP
4372	cpumask_t cpu_online_map __read_mostly = CPU_MASK_ALL;
4373	EXPORT_SYMBOL(cpu_online_map);
4374
4375	cpumask_t cpu_possible_map __read_mostly = CPU_MASK_ALL;
4376	EXPORT_SYMBOL(cpu_possible_map);
4377	#endif
4378
4379	long sched_getaffinity(pid_t pid, cpumask_t *mask)
4380	{
4381	struct task_struct *p;
4382	int retval;
4383
4384	lock_cpu_hotplug();
4385	read_lock(&tasklist_lock);
4386
4387	retval = -ESRCH;
4388	p = find_process_by_pid(pid);
4389	if (!p)
4390	goto out_unlock;
4391
4392	retval = security_task_getscheduler(p);
4393	if (retval)
4394	goto out_unlock;
4395
4396	cpus_and(*mask, p->cpus_allowed, cpu_online_map);
4397
4398	out_unlock:
4399	read_unlock(&tasklist_lock);
4400	unlock_cpu_hotplug();
4401	if (retval)
4402	return retval;
4403
4404	return 0;
4405	}
4406
4407	/**
4408	* sys_sched_getaffinity - get the cpu affinity of a process
4409	* @pid: pid of the process
4410	* @len: length in bytes of the bitmask pointed to by user_mask_ptr
4411	* @user_mask_ptr: user-space pointer to hold the current cpu mask
4412	*/
4413	asmlinkage long sys_sched_getaffinity(pid_t pid, unsigned int len,
4414	unsigned long __user *user_mask_ptr)
4415	{
4416	int ret;
4417	cpumask_t mask;
4418
4419	if (len < sizeof(cpumask_t))
4420	return -EINVAL;
4421
4422	ret = sched_getaffinity(pid, &mask);
4423	if (ret < 0)
4424	return ret;
4425
4426	if (copy_to_user(user_mask_ptr, &mask, sizeof(cpumask_t)))
4427	return -EFAULT;
4428
4429	return sizeof(cpumask_t);
4430	}
4431
4432	/**
4433	* sys_sched_yield - yield the current processor to other threads.
4434	*
4435	* This function yields the current CPU by moving the calling thread
4436	* to the expired array. If there are no other threads running on this
4437	* CPU then this function will return.
4438	*/
4439	asmlinkage long sys_sched_yield(void)
4440	{
4441	struct rq *rq = this_rq_lock();
4442	struct prio_array array = current->array, target = rq->expired;
4443
4444	schedstat_inc(rq, yld_cnt);
4445	/*
4446	* We implement yielding by moving the task into the expired
4447	* queue.
4448	*
4449	* (special rule: RT tasks will just roundrobin in the active
4450	* array.)
4451	*/
4452	if (rt_task(current))
4453	target = rq->active;
4454
4455	if (array->nr_active == 1) {
4456	schedstat_inc(rq, yld_act_empty);
4457	if (!rq->expired->nr_active)
4458	schedstat_inc(rq, yld_both_empty);
4459	} else if (!rq->expired->nr_active)
4460	schedstat_inc(rq, yld_exp_empty);
4461
4462	if (array != target) {
4463	dequeue_task(current, array);
4464	enqueue_task(current, target);
4465	} else
4466	/*
4467	* requeue_task is cheaper so perform that if possible.
4468	*/
4469	requeue_task(current, array);
4470
4471	/*
4472	* Since we are going to call schedule() anyway, there's
4473	* no need to preempt or enable interrupts:
4474	*/
4475	__release(rq->lock);
4476	spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
4477	_raw_spin_unlock(&rq->lock);
4478	preempt_enable_no_resched();
4479
4480	schedule();
4481
4482	return 0;
4483	}
4484
4485	static void __cond_resched(void)
4486	{
4487	#ifdef CONFIG_DEBUG_SPINLOCK_SLEEP
4488	__might_sleep(__FILE__, __LINE__);
4489	#endif
4490	/*
4491	* The BKS might be reacquired before we have dropped
4492	* PREEMPT_ACTIVE, which could trigger a second
4493	* cond_resched() call.
4494	*/
4495	do {
4496	add_preempt_count(PREEMPT_ACTIVE);
4497	schedule();
4498	sub_preempt_count(PREEMPT_ACTIVE);
4499	} while (need_resched());
4500	}
4501
4502	int __sched cond_resched(void)
4503	{
4504	if (need_resched() && !(preempt_count() & PREEMPT_ACTIVE) &&
4505	system_state == SYSTEM_RUNNING) {
4506	__cond_resched();
4507	return 1;
4508	}
4509	return 0;
4510	}
4511	EXPORT_SYMBOL(cond_resched);
4512
4513	/*
4514	* cond_resched_lock() - if a reschedule is pending, drop the given lock,
4515	* call schedule, and on return reacquire the lock.
4516	*
4517	* This works OK both with and without CONFIG_PREEMPT. We do strange low-level
4518	* operations here to prevent schedule() from being called twice (once via
4519	* spin_unlock(), once by hand).
4520	*/
4521	int cond_resched_lock(spinlock_t *lock)
4522	{
4523	int ret = 0;
4524
4525	if (need_lockbreak(lock)) {
4526	spin_unlock(lock);
4527	cpu_relax();
4528	ret = 1;
4529	spin_lock(lock);
4530	}
4531	if (need_resched() && system_state == SYSTEM_RUNNING) {
4532	spin_release(&lock->dep_map, 1, _THIS_IP_);
4533	_raw_spin_unlock(lock);
4534	preempt_enable_no_resched();
4535	__cond_resched();
4536	ret = 1;
4537	spin_lock(lock);
4538	}
4539	return ret;
4540	}
4541	EXPORT_SYMBOL(cond_resched_lock);
4542
4543	int __sched cond_resched_softirq(void)
4544	{
4545	BUG_ON(!in_softirq());
4546
4547	if (need_resched() && system_state == SYSTEM_RUNNING) {
4548	raw_local_irq_disable();
4549	_local_bh_enable();
4550	raw_local_irq_enable();
4551	__cond_resched();
4552	local_bh_disable();
4553	return 1;
4554	}
4555	return 0;
4556	}
4557	EXPORT_SYMBOL(cond_resched_softirq);
4558
4559	/**
4560	* yield - yield the current processor to other threads.
4561	*
4562	* This is a shortcut for kernel-space yielding - it marks the
4563	* thread runnable and calls sys_sched_yield().
4564	*/
4565	void __sched yield(void)
4566	{
4567	set_current_state(TASK_RUNNING);
4568	sys_sched_yield();
4569	}
4570	EXPORT_SYMBOL(yield);
4571
4572	/*
4573	* This task is about to go to sleep on IO. Increment rq->nr_iowait so
4574	* that process accounting knows that this is a task in IO wait state.
4575	*
4576	* But don't do that if it is a deliberate, throttling IO wait (this task
4577	* has set its backing_dev_info: the queue against which it should throttle)
4578	*/
4579	void __sched io_schedule(void)
4580	{
4581	struct rq *rq = &__raw_get_cpu_var(runqueues);
4582
4583	delayacct_blkio_start();
4584	atomic_inc(&rq->nr_iowait);
4585	schedule();
4586	atomic_dec(&rq->nr_iowait);
4587	delayacct_blkio_end();
4588	}
4589	EXPORT_SYMBOL(io_schedule);
4590
4591	long __sched io_schedule_timeout(long timeout)
4592	{
4593	struct rq *rq = &__raw_get_cpu_var(runqueues);
4594	long ret;
4595
4596	delayacct_blkio_start();
4597	atomic_inc(&rq->nr_iowait);
4598	ret = schedule_timeout(timeout);
4599	atomic_dec(&rq->nr_iowait);
4600	delayacct_blkio_end();
4601	return ret;
4602	}
4603
4604	/**
4605	* sys_sched_get_priority_max - return maximum RT priority.
4606	* @policy: scheduling class.
4607	*
4608	* this syscall returns the maximum rt_priority that can be used
4609	* by a given scheduling class.
4610	*/
4611	asmlinkage long sys_sched_get_priority_max(int policy)
4612	{
4613	int ret = -EINVAL;
4614
4615	switch (policy) {
4616	case SCHED_FIFO:
4617	case SCHED_RR:
4618	ret = MAX_USER_RT_PRIO-1;
4619	break;
4620	case SCHED_NORMAL:
4621	case SCHED_BATCH:
4622	ret = 0;
4623	break;
4624	}
4625	return ret;
4626	}
4627
4628	/**
4629	* sys_sched_get_priority_min - return minimum RT priority.
4630	* @policy: scheduling class.
4631	*
4632	* this syscall returns the minimum rt_priority that can be used
4633	* by a given scheduling class.
4634	*/
4635	asmlinkage long sys_sched_get_priority_min(int policy)
4636	{
4637	int ret = -EINVAL;
4638
4639	switch (policy) {
4640	case SCHED_FIFO:
4641	case SCHED_RR:
4642	ret = 1;
4643	break;
4644	case SCHED_NORMAL:
4645	case SCHED_BATCH:
4646	ret = 0;
4647	}
4648	return ret;
4649	}
4650
4651	/**
4652	* sys_sched_rr_get_interval - return the default timeslice of a process.
4653	* @pid: pid of the process.
4654	* @interval: userspace pointer to the timeslice value.
4655	*
4656	* this syscall writes the default timeslice value of a given process
4657	* into the user-space timespec buffer. A value of '0' means infinity.
4658	*/
4659	asmlinkage
4660	long sys_sched_rr_get_interval(pid_t pid, struct timespec __user *interval)
4661	{
4662	struct task_struct *p;
4663	int retval = -EINVAL;
4664	struct timespec t;
4665
4666	if (pid < 0)
4667	goto out_nounlock;
4668
4669	retval = -ESRCH;
4670	read_lock(&tasklist_lock);
4671	p = find_process_by_pid(pid);
4672	if (!p)
4673	goto out_unlock;
4674
4675	retval = security_task_getscheduler(p);
4676	if (retval)
4677	goto out_unlock;
4678
4679	jiffies_to_timespec(p->policy == SCHED_FIFO ?
4680	0 : task_timeslice(p), &t);
4681	read_unlock(&tasklist_lock);
4682	retval = copy_to_user(interval, &t, sizeof(t)) ? -EFAULT : 0;
4683	out_nounlock:
4684	return retval;
4685	out_unlock:
4686	read_unlock(&tasklist_lock);
4687	return retval;
4688	}
4689
4690	static const char stat_nam[] = "RSDTtZX";
4691
4692	static void show_task(struct task_struct *p)
4693	{
4694	unsigned long free = 0;
4695	unsigned state;
4696
4697	state = p->state ? __ffs(p->state) + 1 : 0;
4698	printk("%-13.13s %c", p->comm,
4699	state < sizeof(stat_nam) - 1 ? stat_nam[state] : '?');
4700	#if (BITS_PER_LONG == 32)
4701	if (state == TASK_RUNNING)
4702	printk(" running ");
4703	else
4704	printk(" %08lX ", thread_saved_pc(p));
4705	#else
4706	if (state == TASK_RUNNING)
4707	printk(" running task ");
4708	else
4709	printk(" %016lx ", thread_saved_pc(p));
4710	#endif
4711	#ifdef CONFIG_DEBUG_STACK_USAGE
4712	{
4713	unsigned long *n = end_of_stack(p);
4714	while (!*n)
4715	n++;
4716	free = (unsigned long)n - (unsigned long)end_of_stack(p);
4717	}
4718	#endif
4719	printk("%5lu %5d %6d", free, p->pid, p->parent->pid);
4720	if (!p->mm)
4721	printk(" (L-TLB)\n");
4722	else
4723	printk(" (NOTLB)\n");
4724
4725	if (state != TASK_RUNNING)
4726	show_stack(p, NULL);
4727	}
4728
4729	void show_state_filter(unsigned long state_filter)
4730	{
4731	struct task_struct g, p;
4732
4733	#if (BITS_PER_LONG == 32)
4734	printk("\n"
4735	" free sibling\n");
4736	printk(" task PC stack pid father child younger older\n");
4737	#else
4738	printk("\n"
4739	" free sibling\n");
4740	printk(" task PC stack pid father child younger older\n");
4741	#endif
4742	read_lock(&tasklist_lock);
4743	do_each_thread(g, p) {
4744	/*
4745	* reset the NMI-timeout, listing all files on a slow
4746	* console might take alot of time:
4747	*/
4748	touch_nmi_watchdog();
4749	if (p->state & state_filter)
4750	show_task(p);
4751	} while_each_thread(g, p);
4752
4753	read_unlock(&tasklist_lock);
4754	/*
4755	* Only show locks if all tasks are dumped:
4756	*/
4757	if (state_filter == -1)
4758	debug_show_all_locks();
4759	}
4760
4761	/**
4762	* init_idle - set up an idle thread for a given CPU
4763	* @idle: task in question
4764	* @cpu: cpu the idle task belongs to
4765	*
4766	* NOTE: this function does not set the idle thread's NEED_RESCHED
4767	* flag, to make booting more robust.
4768	*/
4769	void __cpuinit init_idle(struct task_struct *idle, int cpu)
4770	{
4771	struct rq *rq = cpu_rq(cpu);
4772	unsigned long flags;
4773
4774	idle->timestamp = sched_clock();
4775	idle->sleep_avg = 0;
4776	idle->array = NULL;
4777	idle->prio = idle->normal_prio = MAX_PRIO;
4778	idle->state = TASK_RUNNING;
4779	idle->cpus_allowed = cpumask_of_cpu(cpu);
4780	set_task_cpu(idle, cpu);
4781
4782	spin_lock_irqsave(&rq->lock, flags);
4783	rq->curr = rq->idle = idle;
4784	#if defined(CONFIG_SMP) && defined(__ARCH_WANT_UNLOCKED_CTXSW)
4785	idle->oncpu = 1;
4786	#endif
4787	spin_unlock_irqrestore(&rq->lock, flags);
4788
4789	/* Set the preempt count _outside_ the spinlocks! */
4790	#if defined(CONFIG_PREEMPT) && !defined(CONFIG_PREEMPT_BKL)
4791	task_thread_info(idle)->preempt_count = (idle->lock_depth >= 0);
4792	#else
4793	task_thread_info(idle)->preempt_count = 0;
4794	#endif
4795	}
4796
4797	/*
4798	* In a system that switches off the HZ timer nohz_cpu_mask
4799	* indicates which cpus entered this state. This is used
4800	* in the rcu update to wait only for active cpus. For system
4801	* which do not switch off the HZ timer nohz_cpu_mask should
4802	* always be CPU_MASK_NONE.
4803	*/
4804	cpumask_t nohz_cpu_mask = CPU_MASK_NONE;
4805
4806	#ifdef CONFIG_SMP
4807	/*
4808	* This is how migration works:
4809	*
4810	* 1) we queue a struct migration_req structure in the source CPU's
4811	* runqueue and wake up that CPU's migration thread.
4812	* 2) we down() the locked semaphore => thread blocks.
4813	* 3) migration thread wakes up (implicitly it forces the migrated
4814	* thread off the CPU)
4815	* 4) it gets the migration request and checks whether the migrated
4816	* task is still in the wrong runqueue.
4817	* 5) if it's in the wrong runqueue then the migration thread removes
4818	* it and puts it into the right queue.
4819	* 6) migration thread up()s the semaphore.
4820	* 7) we wake up and the migration is done.
4821	*/
4822
4823	/*
4824	* Change a given task's CPU affinity. Migrate the thread to a
4825	* proper CPU and schedule it away if the CPU it's executing on
4826	* is removed from the allowed bitmask.
4827	*
4828	* NOTE: the caller must have a valid reference to the task, the
4829	* task must not exit() & deallocate itself prematurely. The
4830	* call is not atomic; no spinlocks may be held.
4831	*/
4832	int set_cpus_allowed(struct task_struct *p, cpumask_t new_mask)
4833	{
4834	struct migration_req req;
4835	unsigned long flags;
4836	struct rq *rq;
4837	int ret = 0;
4838
4839	rq = task_rq_lock(p, &flags);
4840	if (!cpus_intersects(new_mask, cpu_online_map)) {
4841	ret = -EINVAL;
4842	goto out;
4843	}
4844
4845	p->cpus_allowed = new_mask;
4846	/* Can the task run on the task's current CPU? If so, we're done */
4847	if (cpu_isset(task_cpu(p), new_mask))
4848	goto out;
4849
4850	if (migrate_task(p, any_online_cpu(new_mask), &req)) {
4851	/* Need help from migration thread: drop lock and wait. */
4852	task_rq_unlock(rq, &flags);
4853	wake_up_process(rq->migration_thread);
4854	wait_for_completion(&req.done);
4855	tlb_migrate_finish(p->mm);
4856	return 0;
4857	}
4858	out:
4859	task_rq_unlock(rq, &flags);
4860
4861	return ret;
4862	}
4863	EXPORT_SYMBOL_GPL(set_cpus_allowed);
4864
4865	/*
4866	* Move (not current) task off this cpu, onto dest cpu. We're doing
4867	* this because either it can't run here any more (set_cpus_allowed()
4868	* away from this CPU, or CPU going down), or because we're
4869	* attempting to rebalance this task on exec (sched_exec).
4870	*
4871	* So we race with normal scheduler movements, but that's OK, as long
4872	* as the task is no longer on this CPU.
4873	*
4874	* Returns non-zero if task was successfully migrated.
4875	*/
4876	static int __migrate_task(struct task_struct *p, int src_cpu, int dest_cpu)
4877	{
4878	struct rq rq_dest, rq_src;
4879	int ret = 0;
4880
4881	if (unlikely(cpu_is_offline(dest_cpu)))
4882	return ret;
4883
4884	rq_src = cpu_rq(src_cpu);
4885	rq_dest = cpu_rq(dest_cpu);
4886
4887	double_rq_lock(rq_src, rq_dest);
4888	/* Already moved. */
4889	if (task_cpu(p) != src_cpu)
4890	goto out;
4891	/* Affinity changed (again). */
4892	if (!cpu_isset(dest_cpu, p->cpus_allowed))
4893	goto out;
4894
4895	set_task_cpu(p, dest_cpu);
4896	if (p->array) {
4897	/*
4898	* Sync timestamp with rq_dest's before activating.
4899	* The same thing could be achieved by doing this step
4900	* afterwards, and pretending it was a local activate.
4901	* This way is cleaner and logically correct.
4902	*/
4903	p->timestamp = p->timestamp - rq_src->most_recent_timestamp
4904	+ rq_dest->most_recent_timestamp;
4905	deactivate_task(p, rq_src);
4906	__activate_task(p, rq_dest);
4907	if (TASK_PREEMPTS_CURR(p, rq_dest))
4908	resched_task(rq_dest->curr);
4909	}
4910	ret = 1;
4911	out:
4912	double_rq_unlock(rq_src, rq_dest);
4913	return ret;
4914	}
4915
4916	/*
4917	* migration_thread - this is a highprio system thread that performs
4918	* thread migration by bumping thread off CPU then 'pushing' onto
4919	* another runqueue.
4920	*/
4921	static int migration_thread(void *data)
4922	{
4923	int cpu = (long)data;
4924	struct rq *rq;
4925
4926	rq = cpu_rq(cpu);
4927	BUG_ON(rq->migration_thread != current);
4928
4929	set_current_state(TASK_INTERRUPTIBLE);
4930	while (!kthread_should_stop()) {
4931	struct migration_req *req;
4932	struct list_head *head;
4933
4934	try_to_freeze();
4935
4936	spin_lock_irq(&rq->lock);
4937
4938	if (cpu_is_offline(cpu)) {
4939	spin_unlock_irq(&rq->lock);
4940	goto wait_to_die;
4941	}
4942
4943	if (rq->active_balance) {
4944	active_load_balance(rq, cpu);
4945	rq->active_balance = 0;
4946	}
4947
4948	head = &rq->migration_queue;
4949
4950	if (list_empty(head)) {
4951	spin_unlock_irq(&rq->lock);
4952	schedule();
4953	set_current_state(TASK_INTERRUPTIBLE);
4954	continue;
4955	}
4956	req = list_entry(head->next, struct migration_req, list);
4957	list_del_init(head->next);
4958
4959	spin_unlock(&rq->lock);
4960	__migrate_task(req->task, cpu, req->dest_cpu);
4961	local_irq_enable();
4962
4963	complete(&req->done);
4964	}
4965	__set_current_state(TASK_RUNNING);
4966	return 0;
4967
4968	wait_to_die:
4969	/* Wait for kthread_stop */
4970	set_current_state(TASK_INTERRUPTIBLE);
4971	while (!kthread_should_stop()) {
4972	schedule();
4973	set_current_state(TASK_INTERRUPTIBLE);
4974	}
4975	__set_current_state(TASK_RUNNING);
4976	return 0;
4977	}
4978
4979	#ifdef CONFIG_HOTPLUG_CPU
4980	/*
4981	* Figure out where task on dead CPU should go, use force if neccessary.
4982	* NOTE: interrupts should be disabled by the caller
4983	*/
4984	static void move_task_off_dead_cpu(int dead_cpu, struct task_struct *p)
4985	{
4986	unsigned long flags;
4987	cpumask_t mask;
4988	struct rq *rq;
4989	int dest_cpu;
4990
4991	restart:
4992	/* On same node? */
4993	mask = node_to_cpumask(cpu_to_node(dead_cpu));
4994	cpus_and(mask, mask, p->cpus_allowed);
4995	dest_cpu = any_online_cpu(mask);
4996
4997	/* On any allowed CPU? */
4998	if (dest_cpu == NR_CPUS)
4999	dest_cpu = any_online_cpu(p->cpus_allowed);
5000
5001	/* No more Mr. Nice Guy. */
5002	if (dest_cpu == NR_CPUS) {
5003	rq = task_rq_lock(p, &flags);
5004	cpus_setall(p->cpus_allowed);
5005	dest_cpu = any_online_cpu(p->cpus_allowed);
5006	task_rq_unlock(rq, &flags);
5007
5008	/*
5009	* Don't tell them about moving exiting tasks or
5010	* kernel threads (both mm NULL), since they never
5011	* leave kernel.
5012	*/
5013	if (p->mm && printk_ratelimit())
5014	printk(KERN_INFO "process %d (%s) no "
5015	"longer affine to cpu%d\n",
5016	p->pid, p->comm, dead_cpu);
5017	}
5018	if (!__migrate_task(p, dead_cpu, dest_cpu))
5019	goto restart;
5020	}
5021
5022	/*
5023	* While a dead CPU has no uninterruptible tasks queued at this point,
5024	* it might still have a nonzero ->nr_uninterruptible counter, because
5025	* for performance reasons the counter is not stricly tracking tasks to
5026	* their home CPUs. So we just add the counter to another CPU's counter,
5027	* to keep the global sum constant after CPU-down:
5028	*/
5029	static void migrate_nr_uninterruptible(struct rq *rq_src)
5030	{
5031	struct rq *rq_dest = cpu_rq(any_online_cpu(CPU_MASK_ALL));
5032	unsigned long flags;
5033
5034	local_irq_save(flags);
5035	double_rq_lock(rq_src, rq_dest);
5036	rq_dest->nr_uninterruptible += rq_src->nr_uninterruptible;
5037	rq_src->nr_uninterruptible = 0;
5038	double_rq_unlock(rq_src, rq_dest);
5039	local_irq_restore(flags);
5040	}
5041
5042	/* Run through task list and migrate tasks from the dead cpu. */
5043	static void migrate_live_tasks(int src_cpu)
5044	{
5045	struct task_struct p, t;
5046
5047	write_lock_irq(&tasklist_lock);
5048
5049	do_each_thread(t, p) {
5050	if (p == current)
5051	continue;
5052
5053	if (task_cpu(p) == src_cpu)
5054	move_task_off_dead_cpu(src_cpu, p);
5055	} while_each_thread(t, p);
5056
5057	write_unlock_irq(&tasklist_lock);
5058	}
5059
5060	/* Schedules idle task to be the next runnable task on current CPU.
5061	* It does so by boosting its priority to highest possible and adding it to
5062	* the _front_ of the runqueue. Used by CPU offline code.
5063	*/
5064	void sched_idle_next(void)
5065	{
5066	int this_cpu = smp_processor_id();
5067	struct rq *rq = cpu_rq(this_cpu);
5068	struct task_struct *p = rq->idle;
5069	unsigned long flags;
5070
5071	/* cpu has to be offline */
5072	BUG_ON(cpu_online(this_cpu));
5073
5074	/*
5075	* Strictly not necessary since rest of the CPUs are stopped by now
5076	* and interrupts disabled on the current cpu.
5077	*/
5078	spin_lock_irqsave(&rq->lock, flags);
5079
5080	__setscheduler(p, SCHED_FIFO, MAX_RT_PRIO-1);
5081
5082	/* Add idle task to the _front_ of its priority queue: */
5083	__activate_idle_task(p, rq);
5084
5085	spin_unlock_irqrestore(&rq->lock, flags);
5086	}
5087
5088	/*
5089	* Ensures that the idle task is using init_mm right before its cpu goes
5090	* offline.
5091	*/
5092	void idle_task_exit(void)
5093	{
5094	struct mm_struct *mm = current->active_mm;
5095
5096	BUG_ON(cpu_online(smp_processor_id()));
5097
5098	if (mm != &init_mm)
5099	switch_mm(mm, &init_mm, current);
5100	mmdrop(mm);
5101	}
5102
5103	/* called under rq->lock with disabled interrupts */
5104	static void migrate_dead(unsigned int dead_cpu, struct task_struct *p)
5105	{
5106	struct rq *rq = cpu_rq(dead_cpu);
5107
5108	/* Must be exiting, otherwise would be on tasklist. */
5109	BUG_ON(p->exit_state != EXIT_ZOMBIE && p->exit_state != EXIT_DEAD);
5110
5111	/* Cannot have done final schedule yet: would have vanished. */
5112	BUG_ON(p->state == TASK_DEAD);
5113
5114	get_task_struct(p);
5115
5116	/*
5117	* Drop lock around migration; if someone else moves it,
5118	* that's OK. No task can be added to this CPU, so iteration is
5119	* fine.
5120	* NOTE: interrupts should be left disabled --dev@
5121	*/
5122	spin_unlock(&rq->lock);
5123	move_task_off_dead_cpu(dead_cpu, p);
5124	spin_lock(&rq->lock);
5125
5126	put_task_struct(p);
5127	}
5128
5129	/* release_task() removes task from tasklist, so we won't find dead tasks. */
5130	static void migrate_dead_tasks(unsigned int dead_cpu)
5131	{
5132	struct rq *rq = cpu_rq(dead_cpu);
5133	unsigned int arr, i;
5134
5135	for (arr = 0; arr < 2; arr++) {
5136	for (i = 0; i < MAX_PRIO; i++) {
5137	struct list_head *list = &rq->arrays[arr].queue[i];
5138
5139	while (!list_empty(list))
5140	migrate_dead(dead_cpu, list_entry(list->next,
5141	struct task_struct, run_list));
5142	}
5143	}
5144	}
5145	#endif /* CONFIG_HOTPLUG_CPU */
5146
5147	/*
5148	* migration_call - callback that gets triggered when a CPU is added.
5149	* Here we can start up the necessary migration thread for the new CPU.
5150	*/
5151	static int __cpuinit
5152	migration_call(struct notifier_block nfb, unsigned long action, void hcpu)
5153	{
5154	struct task_struct *p;
5155	int cpu = (long)hcpu;
5156	unsigned long flags;
5157	struct rq *rq;
5158
5159	switch (action) {
5160	case CPU_UP_PREPARE:
5161	p = kthread_create(migration_thread, hcpu, "migration/%d",cpu);
5162	if (IS_ERR(p))
5163	return NOTIFY_BAD;
5164	p->flags \|= PF_NOFREEZE;
5165	kthread_bind(p, cpu);
5166	/* Must be high prio: stop_machine expects to yield to it. */
5167	rq = task_rq_lock(p, &flags);
5168	__setscheduler(p, SCHED_FIFO, MAX_RT_PRIO-1);
5169	task_rq_unlock(rq, &flags);
5170	cpu_rq(cpu)->migration_thread = p;
5171	break;
5172
5173	case CPU_ONLINE:
5174	/* Strictly unneccessary, as first user will wake it. */
5175	wake_up_process(cpu_rq(cpu)->migration_thread);
5176	break;
5177
5178	#ifdef CONFIG_HOTPLUG_CPU
5179	case CPU_UP_CANCELED:
5180	if (!cpu_rq(cpu)->migration_thread)
5181	break;
5182	/* Unbind it from offline cpu so it can run. Fall thru. */
5183	kthread_bind(cpu_rq(cpu)->migration_thread,
5184	any_online_cpu(cpu_online_map));
5185	kthread_stop(cpu_rq(cpu)->migration_thread);
5186	cpu_rq(cpu)->migration_thread = NULL;
5187	break;
5188
5189	case CPU_DEAD:
5190	migrate_live_tasks(cpu);
5191	rq = cpu_rq(cpu);
5192	kthread_stop(rq->migration_thread);
5193	rq->migration_thread = NULL;
5194	/* Idle task back to normal (off runqueue, low prio) */
5195	rq = task_rq_lock(rq->idle, &flags);
5196	deactivate_task(rq->idle, rq);
5197	rq->idle->static_prio = MAX_PRIO;
5198	__setscheduler(rq->idle, SCHED_NORMAL, 0);
5199	migrate_dead_tasks(cpu);
5200	task_rq_unlock(rq, &flags);
5201	migrate_nr_uninterruptible(rq);
5202	BUG_ON(rq->nr_running != 0);
5203
5204	/* No need to migrate the tasks: it was best-effort if
5205	* they didn't do lock_cpu_hotplug(). Just wake up
5206	* the requestors. */
5207	spin_lock_irq(&rq->lock);
5208	while (!list_empty(&rq->migration_queue)) {
5209	struct migration_req *req;
5210
5211	req = list_entry(rq->migration_queue.next,
5212	struct migration_req, list);
5213	list_del_init(&req->list);
5214	complete(&req->done);
5215	}
5216	spin_unlock_irq(&rq->lock);
5217	break;
5218	#endif
5219	}
5220	return NOTIFY_OK;
5221	}
5222
5223	/* Register at highest priority so that task migration (migrate_all_tasks)
5224	* happens before everything else.
5225	*/
5226	static struct notifier_block __cpuinitdata migration_notifier = {
5227	.notifier_call = migration_call,
5228	.priority = 10
5229	};
5230
5231	int __init migration_init(void)
5232	{
5233	void cpu = (void )(long)smp_processor_id();
5234	int err;
5235
5236	/* Start one for the boot CPU: */
5237	err = migration_call(&migration_notifier, CPU_UP_PREPARE, cpu);
5238	BUG_ON(err == NOTIFY_BAD);
5239	migration_call(&migration_notifier, CPU_ONLINE, cpu);
5240	register_cpu_notifier(&migration_notifier);
5241
5242	return 0;
5243	}
5244	#endif
5245
5246	#ifdef CONFIG_SMP
5247	#undef SCHED_DOMAIN_DEBUG
5248	#ifdef SCHED_DOMAIN_DEBUG
5249	static void sched_domain_debug(struct sched_domain *sd, int cpu)
5250	{
5251	int level = 0;
5252
5253	if (!sd) {
5254	printk(KERN_DEBUG "CPU%d attaching NULL sched-domain.\n", cpu);
5255	return;
5256	}
5257
5258	printk(KERN_DEBUG "CPU%d attaching sched-domain:\n", cpu);
5259
5260	do {
5261	int i;
5262	char str[NR_CPUS];
5263	struct sched_group *group = sd->groups;
5264	cpumask_t groupmask;
5265
5266	cpumask_scnprintf(str, NR_CPUS, sd->span);
5267	cpus_clear(groupmask);
5268
5269	printk(KERN_DEBUG);
5270	for (i = 0; i < level + 1; i++)
5271	printk(" ");
5272	printk("domain %d: ", level);
5273
5274	if (!(sd->flags & SD_LOAD_BALANCE)) {
5275	printk("does not load-balance\n");
5276	if (sd->parent)
5277	printk(KERN_ERR "ERROR: !SD_LOAD_BALANCE domain"
5278	" has parent");
5279	break;
5280	}
5281
5282	printk("span %s\n", str);
5283
5284	if (!cpu_isset(cpu, sd->span))
5285	printk(KERN_ERR "ERROR: domain->span does not contain "
5286	"CPU%d\n", cpu);
5287	if (!cpu_isset(cpu, group->cpumask))
5288	printk(KERN_ERR "ERROR: domain->groups does not contain"
5289	" CPU%d\n", cpu);
5290
5291	printk(KERN_DEBUG);
5292	for (i = 0; i < level + 2; i++)
5293	printk(" ");
5294	printk("groups:");
5295	do {
5296	if (!group) {
5297	printk("\n");
5298	printk(KERN_ERR "ERROR: group is NULL\n");
5299	break;
5300	}
5301
5302	if (!group->cpu_power) {
5303	printk("\n");
5304	printk(KERN_ERR "ERROR: domain->cpu_power not "
5305	"set\n");
5306	}
5307
5308	if (!cpus_weight(group->cpumask)) {
5309	printk("\n");
5310	printk(KERN_ERR "ERROR: empty group\n");
5311	}
5312
5313	if (cpus_intersects(groupmask, group->cpumask)) {
5314	printk("\n");
5315	printk(KERN_ERR "ERROR: repeated CPUs\n");
5316	}
5317
5318	cpus_or(groupmask, groupmask, group->cpumask);
5319
5320	cpumask_scnprintf(str, NR_CPUS, group->cpumask);
5321	printk(" %s", str);
5322
5323	group = group->next;
5324	} while (group != sd->groups);
5325	printk("\n");
5326
5327	if (!cpus_equal(sd->span, groupmask))
5328	printk(KERN_ERR "ERROR: groups don't span "
5329	"domain->span\n");
5330
5331	level++;
5332	sd = sd->parent;
5333	if (!sd)
5334	continue;
5335
5336	if (!cpus_subset(groupmask, sd->span))
5337	printk(KERN_ERR "ERROR: parent span is not a superset "
5338	"of domain->span\n");
5339
5340	} while (sd);
5341	}
5342	#else
5343	# define sched_domain_debug(sd, cpu) do { } while (0)
5344	#endif
5345
5346	static int sd_degenerate(struct sched_domain *sd)
5347	{
5348	if (cpus_weight(sd->span) == 1)
5349	return 1;
5350
5351	/* Following flags need at least 2 groups */
5352	if (sd->flags & (SD_LOAD_BALANCE \|
5353	SD_BALANCE_NEWIDLE \|
5354	SD_BALANCE_FORK \|
5355	SD_BALANCE_EXEC \|
5356	SD_SHARE_CPUPOWER \|
5357	SD_SHARE_PKG_RESOURCES)) {
5358	if (sd->groups != sd->groups->next)
5359	return 0;
5360	}
5361
5362	/* Following flags don't use groups */
5363	if (sd->flags & (SD_WAKE_IDLE \|
5364	SD_WAKE_AFFINE \|
5365	SD_WAKE_BALANCE))
5366	return 0;
5367
5368	return 1;
5369	}
5370
5371	static int
5372	sd_parent_degenerate(struct sched_domain sd, struct sched_domain parent)
5373	{
5374	unsigned long cflags = sd->flags, pflags = parent->flags;
5375
5376	if (sd_degenerate(parent))
5377	return 1;
5378
5379	if (!cpus_equal(sd->span, parent->span))
5380	return 0;
5381
5382	/* Does parent contain flags not in child? */
5383	/* WAKE_BALANCE is a subset of WAKE_AFFINE */
5384	if (cflags & SD_WAKE_AFFINE)
5385	pflags &= ~SD_WAKE_BALANCE;
5386	/* Flags needing groups don't count if only 1 group in parent */
5387	if (parent->groups == parent->groups->next) {
5388	pflags &= ~(SD_LOAD_BALANCE \|
5389	SD_BALANCE_NEWIDLE \|
5390	SD_BALANCE_FORK \|
5391	SD_BALANCE_EXEC \|
5392	SD_SHARE_CPUPOWER \|
5393	SD_SHARE_PKG_RESOURCES);
5394	}
5395	if (~cflags & pflags)
5396	return 0;
5397
5398	return 1;
5399	}
5400
5401	/*
5402	* Attach the domain 'sd' to 'cpu' as its base domain. Callers must
5403	* hold the hotplug lock.
5404	*/
5405	static void cpu_attach_domain(struct sched_domain *sd, int cpu)
5406	{
5407	struct rq *rq = cpu_rq(cpu);
5408	struct sched_domain *tmp;
5409
5410	/* Remove the sched domains which do not contribute to scheduling. */
5411	for (tmp = sd; tmp; tmp = tmp->parent) {
5412	struct sched_domain *parent = tmp->parent;
5413	if (!parent)
5414	break;
5415	if (sd_parent_degenerate(tmp, parent)) {
5416	tmp->parent = parent->parent;
5417	if (parent->parent)
5418	parent->parent->child = tmp;
5419	}
5420	}
5421
5422	if (sd && sd_degenerate(sd)) {
5423	sd = sd->parent;
5424	if (sd)
5425	sd->child = NULL;
5426	}
5427
5428	sched_domain_debug(sd, cpu);
5429
5430	rcu_assign_pointer(rq->sd, sd);
5431	}
5432
5433	/* cpus with isolated domains */
5434	static cpumask_t cpu_isolated_map = CPU_MASK_NONE;
5435
5436	/* Setup the mask of cpus configured for isolated domains */
5437	static int __init isolated_cpu_setup(char *str)
5438	{
5439	int ints[NR_CPUS], i;
5440
5441	str = get_options(str, ARRAY_SIZE(ints), ints);
5442	cpus_clear(cpu_isolated_map);
5443	for (i = 1; i <= ints[0]; i++)
5444	if (ints[i] < NR_CPUS)
5445	cpu_set(ints[i], cpu_isolated_map);
5446	return 1;
5447	}
5448
5449	__setup ("isolcpus=", isolated_cpu_setup);
5450
5451	/*
5452	* init_sched_build_groups takes the cpumask we wish to span, and a pointer
5453	* to a function which identifies what group(along with sched group) a CPU
5454	* belongs to. The return value of group_fn must be a >= 0 and < NR_CPUS
5455	* (due to the fact that we keep track of groups covered with a cpumask_t).
5456	*
5457	* init_sched_build_groups will build a circular linked list of the groups
5458	* covered by the given span, and will set each group's ->cpumask correctly,
5459	* and ->cpu_power to 0.
5460	*/
5461	static void
5462	init_sched_build_groups(cpumask_t span, const cpumask_t *cpu_map,
5463	int (group_fn)(int cpu, const cpumask_t cpu_map,
5464	struct sched_group **sg))
5465	{
5466	struct sched_group first = NULL, last = NULL;
5467	cpumask_t covered = CPU_MASK_NONE;
5468	int i;
5469
5470	for_each_cpu_mask(i, span) {
5471	struct sched_group *sg;
5472	int group = group_fn(i, cpu_map, &sg);
5473	int j;
5474
5475	if (cpu_isset(i, covered))
5476	continue;
5477
5478	sg->cpumask = CPU_MASK_NONE;
5479	sg->cpu_power = 0;
5480
5481	for_each_cpu_mask(j, span) {
5482	if (group_fn(j, cpu_map, NULL) != group)
5483	continue;
5484
5485	cpu_set(j, covered);
5486	cpu_set(j, sg->cpumask);
5487	}
5488	if (!first)
5489	first = sg;
5490	if (last)
5491	last->next = sg;
5492	last = sg;
5493	}
5494	last->next = first;
5495	}
5496
5497	#define SD_NODES_PER_DOMAIN 16
5498
5499	/*
5500	* Self-tuning task migration cost measurement between source and target CPUs.
5501	*
5502	* This is done by measuring the cost of manipulating buffers of varying
5503	* sizes. For a given buffer-size here are the steps that are taken:
5504	*
5505	* 1) the source CPU reads+dirties a shared buffer
5506	* 2) the target CPU reads+dirties the same shared buffer
5507	*
5508	* We measure how long they take, in the following 4 scenarios:
5509	*
5510	* - source: CPU1, target: CPU2 \| cost1
5511	* - source: CPU2, target: CPU1 \| cost2
5512	* - source: CPU1, target: CPU1 \| cost3
5513	* - source: CPU2, target: CPU2 \| cost4
5514	*
5515	* We then calculate the cost3+cost4-cost1-cost2 difference - this is
5516	* the cost of migration.
5517	*
5518	* We then start off from a small buffer-size and iterate up to larger
5519	* buffer sizes, in 5% steps - measuring each buffer-size separately, and
5520	* doing a maximum search for the cost. (The maximum cost for a migration
5521	* normally occurs when the working set size is around the effective cache
5522	* size.)
5523	*/
5524	#define SEARCH_SCOPE 2
5525	#define MIN_CACHE_SIZE (64*1024U)
5526	#define DEFAULT_CACHE_SIZE (510241024U)
5527	#define ITERATIONS 1
5528	#define SIZE_THRESH 130
5529	#define COST_THRESH 130
5530
5531	/*
5532	* The migration cost is a function of 'domain distance'. Domain
5533	* distance is the number of steps a CPU has to iterate down its
5534	* domain tree to share a domain with the other CPU. The farther
5535	* two CPUs are from each other, the larger the distance gets.
5536	*
5537	* Note that we use the distance only to cache measurement results,
5538	* the distance value is not used numerically otherwise. When two
5539	* CPUs have the same distance it is assumed that the migration
5540	* cost is the same. (this is a simplification but quite practical)
5541	*/
5542	#define MAX_DOMAIN_DISTANCE 32
5543
5544	static unsigned long long migration_cost[MAX_DOMAIN_DISTANCE] =
5545	{ [ 0 ... MAX_DOMAIN_DISTANCE-1 ] =
5546	/*
5547	* Architectures may override the migration cost and thus avoid
5548	* boot-time calibration. Unit is nanoseconds. Mostly useful for
5549	* virtualized hardware:
5550	*/
5551	#ifdef CONFIG_DEFAULT_MIGRATION_COST
5552	CONFIG_DEFAULT_MIGRATION_COST
5553	#else
5554	-1LL
5555	#endif
5556	};
5557
5558	/*
5559	* Allow override of migration cost - in units of microseconds.
5560	* E.g. migration_cost=1000,2000,3000 will set up a level-1 cost
5561	* of 1 msec, level-2 cost of 2 msecs and level3 cost of 3 msecs:
5562	*/
5563	static int __init migration_cost_setup(char *str)
5564	{
5565	int ints[MAX_DOMAIN_DISTANCE+1], i;
5566
5567	str = get_options(str, ARRAY_SIZE(ints), ints);
5568
5569	printk("#ints: %d\n", ints[0]);
5570	for (i = 1; i <= ints[0]; i++) {
5571	migration_cost[i-1] = (unsigned long long)ints[i]*1000;
5572	printk("migration_cost[%d]: %Ld\n", i-1, migration_cost[i-1]);
5573	}
5574	return 1;
5575	}
5576
5577	__setup ("migration_cost=", migration_cost_setup);
5578
5579	/*
5580	* Global multiplier (divisor) for migration-cutoff values,
5581	* in percentiles. E.g. use a value of 150 to get 1.5 times
5582	* longer cache-hot cutoff times.
5583	*
5584	* (We scale it from 100 to 128 to long long handling easier.)
5585	*/
5586
5587	#define MIGRATION_FACTOR_SCALE 128
5588
5589	static unsigned int migration_factor = MIGRATION_FACTOR_SCALE;
5590
5591	static int __init setup_migration_factor(char *str)
5592	{
5593	get_option(&str, &migration_factor);
5594	migration_factor = migration_factor * MIGRATION_FACTOR_SCALE / 100;
5595	return 1;
5596	}
5597
5598	__setup("migration_factor=", setup_migration_factor);
5599
5600	/*
5601	* Estimated distance of two CPUs, measured via the number of domains
5602	* we have to pass for the two CPUs to be in the same span:
5603	*/
5604	static unsigned long domain_distance(int cpu1, int cpu2)
5605	{
5606	unsigned long distance = 0;
5607	struct sched_domain *sd;
5608
5609	for_each_domain(cpu1, sd) {
5610	WARN_ON(!cpu_isset(cpu1, sd->span));
5611	if (cpu_isset(cpu2, sd->span))
5612	return distance;
5613	distance++;
5614	}
5615	if (distance >= MAX_DOMAIN_DISTANCE) {
5616	WARN_ON(1);
5617	distance = MAX_DOMAIN_DISTANCE-1;
5618	}
5619
5620	return distance;
5621	}
5622
5623	static unsigned int migration_debug;
5624
5625	static int __init setup_migration_debug(char *str)
5626	{
5627	get_option(&str, &migration_debug);
5628	return 1;
5629	}
5630
5631	__setup("migration_debug=", setup_migration_debug);
5632
5633	/*
5634	* Maximum cache-size that the scheduler should try to measure.
5635	* Architectures with larger caches should tune this up during
5636	* bootup. Gets used in the domain-setup code (i.e. during SMP
5637	* bootup).
5638	*/
5639	unsigned int max_cache_size;
5640
5641	static int __init setup_max_cache_size(char *str)
5642	{
5643	get_option(&str, &max_cache_size);
5644	return 1;
5645	}
5646
5647	__setup("max_cache_size=", setup_max_cache_size);
5648
5649	/*
5650	* Dirty a big buffer in a hard-to-predict (for the L2 cache) way. This
5651	* is the operation that is timed, so we try to generate unpredictable
5652	* cachemisses that still end up filling the L2 cache:
5653	*/
5654	static void touch_cache(void *__cache, unsigned long __size)
5655	{
5656	unsigned long size = __size / sizeof(long);
5657	unsigned long chunk1 = size / 3;
5658	unsigned long chunk2 = 2 * size / 3;
5659	unsigned long *cache = __cache;
5660	int i;
5661
5662	for (i = 0; i < size/6; i += 8) {
5663	switch (i % 6) {
5664	case 0: cache[i]++;
5665	case 1: cache[size-1-i]++;
5666	case 2: cache[chunk1-i]++;
5667	case 3: cache[chunk1+i]++;
5668	case 4: cache[chunk2-i]++;
5669	case 5: cache[chunk2+i]++;
5670	}
5671	}
5672	}
5673
5674	/*
5675	* Measure the cache-cost of one task migration. Returns in units of nsec.
5676	*/
5677	static unsigned long long
5678	measure_one(void *cache, unsigned long size, int source, int target)
5679	{
5680	cpumask_t mask, saved_mask;
5681	unsigned long long t0, t1, t2, t3, cost;
5682
5683	saved_mask = current->cpus_allowed;
5684
5685	/*
5686	* Flush source caches to RAM and invalidate them:
5687	*/
5688	sched_cacheflush();
5689
5690	/*
5691	* Migrate to the source CPU:
5692	*/
5693	mask = cpumask_of_cpu(source);
5694	set_cpus_allowed(current, mask);
5695	WARN_ON(smp_processor_id() != source);
5696
5697	/*
5698	* Dirty the working set:
5699	*/
5700	t0 = sched_clock();
5701	touch_cache(cache, size);
5702	t1 = sched_clock();
5703
5704	/*
5705	* Migrate to the target CPU, dirty the L2 cache and access
5706	* the shared buffer. (which represents the working set
5707	* of a migrated task.)
5708	*/
5709	mask = cpumask_of_cpu(target);
5710	set_cpus_allowed(current, mask);
5711	WARN_ON(smp_processor_id() != target);
5712
5713	t2 = sched_clock();
5714	touch_cache(cache, size);
5715	t3 = sched_clock();
5716
5717	cost = t1-t0 + t3-t2;
5718
5719	if (migration_debug >= 2)
5720	printk("[%d->%d]: %8Ld %8Ld %8Ld => %10Ld.\n",
5721	source, target, t1-t0, t1-t0, t3-t2, cost);
5722	/*
5723	* Flush target caches to RAM and invalidate them:
5724	*/
5725	sched_cacheflush();
5726
5727	set_cpus_allowed(current, saved_mask);
5728
5729	return cost;
5730	}
5731
5732	/*
5733	* Measure a series of task migrations and return the average
5734	* result. Since this code runs early during bootup the system
5735	* is 'undisturbed' and the average latency makes sense.
5736	*
5737	* The algorithm in essence auto-detects the relevant cache-size,
5738	* so it will properly detect different cachesizes for different
5739	* cache-hierarchies, depending on how the CPUs are connected.
5740	*
5741	* Architectures can prime the upper limit of the search range via
5742	* max_cache_size, otherwise the search range defaults to 20MB...64K.
5743	*/
5744	static unsigned long long
5745	measure_cost(int cpu1, int cpu2, void *cache, unsigned int size)
5746	{
5747	unsigned long long cost1, cost2;
5748	int i;
5749
5750	/*
5751	* Measure the migration cost of 'size' bytes, over an
5752	* average of 10 runs:
5753	*
5754	* (We perturb the cache size by a small (0..4k)
5755	* value to compensate size/alignment related artifacts.
5756	* We also subtract the cost of the operation done on
5757	* the same CPU.)
5758	*/
5759	cost1 = 0;
5760
5761	/*
5762	* dry run, to make sure we start off cache-cold on cpu1,
5763	* and to get any vmalloc pagefaults in advance:
5764	*/
5765	measure_one(cache, size, cpu1, cpu2);
5766	for (i = 0; i < ITERATIONS; i++)
5767	cost1 += measure_one(cache, size - i * 1024, cpu1, cpu2);
5768
5769	measure_one(cache, size, cpu2, cpu1);
5770	for (i = 0; i < ITERATIONS; i++)
5771	cost1 += measure_one(cache, size - i * 1024, cpu2, cpu1);
5772
5773	/*
5774	* (We measure the non-migrating [cached] cost on both
5775	* cpu1 and cpu2, to handle CPUs with different speeds)
5776	*/
5777	cost2 = 0;
5778
5779	measure_one(cache, size, cpu1, cpu1);
5780	for (i = 0; i < ITERATIONS; i++)
5781	cost2 += measure_one(cache, size - i * 1024, cpu1, cpu1);
5782
5783	measure_one(cache, size, cpu2, cpu2);
5784	for (i = 0; i < ITERATIONS; i++)
5785	cost2 += measure_one(cache, size - i * 1024, cpu2, cpu2);
5786
5787	/*
5788	* Get the per-iteration migration cost:
5789	*/
5790	do_div(cost1, 2 * ITERATIONS);
5791	do_div(cost2, 2 * ITERATIONS);
5792
5793	return cost1 - cost2;
5794	}
5795
5796	static unsigned long long measure_migration_cost(int cpu1, int cpu2)
5797	{
5798	unsigned long long max_cost = 0, fluct = 0, avg_fluct = 0;
5799	unsigned int max_size, size, size_found = 0;
5800	long long cost = 0, prev_cost;
5801	void *cache;
5802
5803	/*
5804	* Search from max_cache_size*5 down to 64K - the real relevant
5805	* cachesize has to lie somewhere inbetween.
5806	*/
5807	if (max_cache_size) {
5808	max_size = max(max_cache_size * SEARCH_SCOPE, MIN_CACHE_SIZE);
5809	size = max(max_cache_size / SEARCH_SCOPE, MIN_CACHE_SIZE);
5810	} else {
5811	/*
5812	* Since we have no estimation about the relevant
5813	* search range
5814	*/
5815	max_size = DEFAULT_CACHE_SIZE * SEARCH_SCOPE;
5816	size = MIN_CACHE_SIZE;
5817	}
5818
5819	if (!cpu_online(cpu1) \|\| !cpu_online(cpu2)) {
5820	printk("cpu %d and %d not both online!\n", cpu1, cpu2);
5821	return 0;
5822	}
5823
5824	/*
5825	* Allocate the working set:
5826	*/
5827	cache = vmalloc(max_size);
5828	if (!cache) {
5829	printk("could not vmalloc %d bytes for cache!\n", 2 * max_size);
5830	return 1000000; /* return 1 msec on very small boxen */
5831	}
5832
5833	while (size <= max_size) {
5834	prev_cost = cost;
5835	cost = measure_cost(cpu1, cpu2, cache, size);
5836
5837	/*
5838	* Update the max:
5839	*/
5840	if (cost > 0) {
5841	if (max_cost < cost) {
5842	max_cost = cost;
5843	size_found = size;
5844	}
5845	}
5846	/*
5847	* Calculate average fluctuation, we use this to prevent
5848	* noise from triggering an early break out of the loop:
5849	*/
5850	fluct = abs(cost - prev_cost);
5851	avg_fluct = (avg_fluct + fluct)/2;
5852
5853	if (migration_debug)
5854	printk("-> [%d][%d][%7d] %3ld.%ld [%3ld.%ld] (%ld): "
5855	"(%8Ld %8Ld)\n",
5856	cpu1, cpu2, size,
5857	(long)cost / 1000000,
5858	((long)cost / 100000) % 10,
5859	(long)max_cost / 1000000,
5860	((long)max_cost / 100000) % 10,
5861	domain_distance(cpu1, cpu2),
5862	cost, avg_fluct);
5863
5864	/*
5865	* If we iterated at least 20% past the previous maximum,
5866	* and the cost has dropped by more than 20% already,
5867	* (taking fluctuations into account) then we assume to
5868	* have found the maximum and break out of the loop early:
5869	*/
5870	if (size_found && (size100 > size_foundSIZE_THRESH))
5871	if (cost+avg_fluct <= 0 \|\|
5872	max_cost100 > (cost+avg_fluct)COST_THRESH) {
5873
5874	if (migration_debug)
5875	printk("-> found max.\n");
5876	break;
5877	}
5878	/*
5879	* Increase the cachesize in 10% steps:
5880	*/
5881	size = size * 10 / 9;
5882	}
5883
5884	if (migration_debug)
5885	printk("[%d][%d] working set size found: %d, cost: %Ld\n",
5886	cpu1, cpu2, size_found, max_cost);
5887
5888	vfree(cache);
5889
5890	/*
5891	* A task is considered 'cache cold' if at least 2 times
5892	* the worst-case cost of migration has passed.
5893	*
5894	* (this limit is only listened to if the load-balancing
5895	* situation is 'nice' - if there is a large imbalance we
5896	* ignore it for the sake of CPU utilization and
5897	* processing fairness.)
5898	*/
5899	return 2 * max_cost * migration_factor / MIGRATION_FACTOR_SCALE;
5900	}
5901
5902	static void calibrate_migration_costs(const cpumask_t *cpu_map)
5903	{
5904	int cpu1 = -1, cpu2 = -1, cpu, orig_cpu = raw_smp_processor_id();
5905	unsigned long j0, j1, distance, max_distance = 0;
5906	struct sched_domain *sd;
5907
5908	j0 = jiffies;
5909
5910	/*
5911	* First pass - calculate the cacheflush times:
5912	*/
5913	for_each_cpu_mask(cpu1, *cpu_map) {
5914	for_each_cpu_mask(cpu2, *cpu_map) {
5915	if (cpu1 == cpu2)
5916	continue;
5917	distance = domain_distance(cpu1, cpu2);
5918	max_distance = max(max_distance, distance);
5919	/*
5920	* No result cached yet?
5921	*/
5922	if (migration_cost[distance] == -1LL)
5923	migration_cost[distance] =
5924	measure_migration_cost(cpu1, cpu2);
5925	}
5926	}
5927	/*
5928	* Second pass - update the sched domain hierarchy with
5929	* the new cache-hot-time estimations:
5930	*/
5931	for_each_cpu_mask(cpu, *cpu_map) {
5932	distance = 0;
5933	for_each_domain(cpu, sd) {
5934	sd->cache_hot_time = migration_cost[distance];
5935	distance++;
5936	}
5937	}
5938	/*
5939	* Print the matrix:
5940	*/
5941	if (migration_debug)
5942	printk("migration: max_cache_size: %d, cpu: %d MHz:\n",
5943	max_cache_size,
5944	#ifdef CONFIG_X86
5945	cpu_khz/1000
5946	#else
5947	-1
5948	#endif
5949	);
5950	if (system_state == SYSTEM_BOOTING && num_online_cpus() > 1) {
5951	printk("migration_cost=");
5952	for (distance = 0; distance <= max_distance; distance++) {
5953	if (distance)
5954	printk(",");
5955	printk("%ld", (long)migration_cost[distance] / 1000);
5956	}
5957	printk("\n");
5958	}
5959	j1 = jiffies;
5960	if (migration_debug)
5961	printk("migration: %ld seconds\n", (j1-j0) / HZ);
5962
5963	/*
5964	* Move back to the original CPU. NUMA-Q gets confused
5965	* if we migrate to another quad during bootup.
5966	*/
5967	if (raw_smp_processor_id() != orig_cpu) {
5968	cpumask_t mask = cpumask_of_cpu(orig_cpu),
5969	saved_mask = current->cpus_allowed;
5970
5971	set_cpus_allowed(current, mask);
5972	set_cpus_allowed(current, saved_mask);
5973	}
5974	}
5975
5976	#ifdef CONFIG_NUMA
5977
5978	/**
5979	* find_next_best_node - find the next node to include in a sched_domain
5980	* @node: node whose sched_domain we're building
5981	* @used_nodes: nodes already in the sched_domain
5982	*
5983	* Find the next node to include in a given scheduling domain. Simply
5984	* finds the closest node not already in the @used_nodes map.
5985	*
5986	* Should use nodemask_t.
5987	*/
5988	static int find_next_best_node(int node, unsigned long *used_nodes)
5989	{
5990	int i, n, val, min_val, best_node = 0;
5991
5992	min_val = INT_MAX;
5993
5994	for (i = 0; i < MAX_NUMNODES; i++) {
5995	/* Start at @node */
5996	n = (node + i) % MAX_NUMNODES;
5997
5998	if (!nr_cpus_node(n))
5999	continue;
6000
6001	/* Skip already used nodes */
6002	if (test_bit(n, used_nodes))
6003	continue;
6004
6005	/* Simple min distance search */
6006	val = node_distance(node, n);
6007
6008	if (val < min_val) {
6009	min_val = val;
6010	best_node = n;
6011	}
6012	}
6013
6014	set_bit(best_node, used_nodes);
6015	return best_node;
6016	}
6017
6018	/**
6019	* sched_domain_node_span - get a cpumask for a node's sched_domain
6020	* @node: node whose cpumask we're constructing
6021	* @size: number of nodes to include in this span
6022	*
6023	* Given a node, construct a good cpumask for its sched_domain to span. It
6024	* should be one that prevents unnecessary balancing, but also spreads tasks
6025	* out optimally.
6026	*/
6027	static cpumask_t sched_domain_node_span(int node)
6028	{
6029	DECLARE_BITMAP(used_nodes, MAX_NUMNODES);
6030	cpumask_t span, nodemask;
6031	int i;
6032
6033	cpus_clear(span);
6034	bitmap_zero(used_nodes, MAX_NUMNODES);
6035
6036	nodemask = node_to_cpumask(node);
6037	cpus_or(span, span, nodemask);
6038	set_bit(node, used_nodes);
6039
6040	for (i = 1; i < SD_NODES_PER_DOMAIN; i++) {
6041	int next_node = find_next_best_node(node, used_nodes);
6042
6043	nodemask = node_to_cpumask(next_node);
6044	cpus_or(span, span, nodemask);
6045	}
6046
6047	return span;
6048	}
6049	#endif
6050
6051	int sched_smt_power_savings = 0, sched_mc_power_savings = 0;
6052
6053	/*
6054	* SMT sched-domains:
6055	*/
6056	#ifdef CONFIG_SCHED_SMT
6057	static DEFINE_PER_CPU(struct sched_domain, cpu_domains);
6058	static DEFINE_PER_CPU(struct sched_group, sched_group_cpus);
6059
6060	static int cpu_to_cpu_group(int cpu, const cpumask_t *cpu_map,
6061	struct sched_group **sg)
6062	{
6063	if (sg)
6064	*sg = &per_cpu(sched_group_cpus, cpu);
6065	return cpu;
6066	}
6067	#endif
6068
6069	/*
6070	* multi-core sched-domains:
6071	*/
6072	#ifdef CONFIG_SCHED_MC
6073	static DEFINE_PER_CPU(struct sched_domain, core_domains);
6074	static DEFINE_PER_CPU(struct sched_group, sched_group_core);
6075	#endif
6076
6077	#if defined(CONFIG_SCHED_MC) && defined(CONFIG_SCHED_SMT)
6078	static int cpu_to_core_group(int cpu, const cpumask_t *cpu_map,
6079	struct sched_group **sg)
6080	{
6081	int group;
6082	cpumask_t mask = cpu_sibling_map[cpu];
6083	cpus_and(mask, mask, *cpu_map);
6084	group = first_cpu(mask);
6085	if (sg)
6086	*sg = &per_cpu(sched_group_core, group);
6087	return group;
6088	}
6089	#elif defined(CONFIG_SCHED_MC)
6090	static int cpu_to_core_group(int cpu, const cpumask_t *cpu_map,
6091	struct sched_group **sg)
6092	{
6093	if (sg)
6094	*sg = &per_cpu(sched_group_core, cpu);
6095	return cpu;
6096	}
6097	#endif
6098
6099	static DEFINE_PER_CPU(struct sched_domain, phys_domains);
6100	static DEFINE_PER_CPU(struct sched_group, sched_group_phys);
6101
6102	static int cpu_to_phys_group(int cpu, const cpumask_t *cpu_map,
6103	struct sched_group **sg)
6104	{
6105	int group;
6106	#ifdef CONFIG_SCHED_MC
6107	cpumask_t mask = cpu_coregroup_map(cpu);
6108	cpus_and(mask, mask, *cpu_map);
6109	group = first_cpu(mask);
6110	#elif defined(CONFIG_SCHED_SMT)
6111	cpumask_t mask = cpu_sibling_map[cpu];
6112	cpus_and(mask, mask, *cpu_map);
6113	group = first_cpu(mask);
6114	#else
6115	group = cpu;
6116	#endif
6117	if (sg)
6118	*sg = &per_cpu(sched_group_phys, group);
6119	return group;
6120	}
6121
6122	#ifdef CONFIG_NUMA
6123	/*
6124	* The init_sched_build_groups can't handle what we want to do with node
6125	* groups, so roll our own. Now each node has its own list of groups which
6126	* gets dynamically allocated.
6127	*/
6128	static DEFINE_PER_CPU(struct sched_domain, node_domains);
6129	static struct sched_group **sched_group_nodes_bycpu[NR_CPUS];
6130
6131	static DEFINE_PER_CPU(struct sched_domain, allnodes_domains);
6132	static DEFINE_PER_CPU(struct sched_group, sched_group_allnodes);
6133
6134	static int cpu_to_allnodes_group(int cpu, const cpumask_t *cpu_map,
6135	struct sched_group **sg)
6136	{
6137	cpumask_t nodemask = node_to_cpumask(cpu_to_node(cpu));
6138	int group;
6139
6140	cpus_and(nodemask, nodemask, *cpu_map);
6141	group = first_cpu(nodemask);
6142
6143	if (sg)
6144	*sg = &per_cpu(sched_group_allnodes, group);
6145	return group;
6146	}
6147
6148	static void init_numa_sched_groups_power(struct sched_group *group_head)
6149	{
6150	struct sched_group *sg = group_head;
6151	int j;
6152
6153	if (!sg)
6154	return;
6155	next_sg:
6156	for_each_cpu_mask(j, sg->cpumask) {
6157	struct sched_domain *sd;
6158
6159	sd = &per_cpu(phys_domains, j);
6160	if (j != first_cpu(sd->groups->cpumask)) {
6161	/*
6162	* Only add "power" once for each
6163	* physical package.
6164	*/
6165	continue;
6166	}
6167
6168	sg->cpu_power += sd->groups->cpu_power;
6169	}
6170	sg = sg->next;
6171	if (sg != group_head)
6172	goto next_sg;
6173	}
6174	#endif
6175
6176	#ifdef CONFIG_NUMA
6177	/* Free memory allocated for various sched_group structures */
6178	static void free_sched_groups(const cpumask_t *cpu_map)
6179	{
6180	int cpu, i;
6181
6182	for_each_cpu_mask(cpu, *cpu_map) {
6183	struct sched_group **sched_group_nodes
6184	= sched_group_nodes_bycpu[cpu];
6185
6186	if (!sched_group_nodes)
6187	continue;
6188
6189	for (i = 0; i < MAX_NUMNODES; i++) {
6190	cpumask_t nodemask = node_to_cpumask(i);
6191	struct sched_group oldsg, sg = sched_group_nodes[i];
6192
6193	cpus_and(nodemask, nodemask, *cpu_map);
6194	if (cpus_empty(nodemask))
6195	continue;
6196
6197	if (sg == NULL)
6198	continue;
6199	sg = sg->next;
6200	next_sg:
6201	oldsg = sg;
6202	sg = sg->next;
6203	kfree(oldsg);
6204	if (oldsg != sched_group_nodes[i])
6205	goto next_sg;
6206	}
6207	kfree(sched_group_nodes);
6208	sched_group_nodes_bycpu[cpu] = NULL;
6209	}
6210	}
6211	#else
6212	static void free_sched_groups(const cpumask_t *cpu_map)
6213	{
6214	}
6215	#endif
6216
6217	/*
6218	* Initialize sched groups cpu_power.
6219	*
6220	* cpu_power indicates the capacity of sched group, which is used while
6221	* distributing the load between different sched groups in a sched domain.
6222	* Typically cpu_power for all the groups in a sched domain will be same unless
6223	* there are asymmetries in the topology. If there are asymmetries, group
6224	* having more cpu_power will pickup more load compared to the group having
6225	* less cpu_power.
6226	*
6227	* cpu_power will be a multiple of SCHED_LOAD_SCALE. This multiple represents
6228	* the maximum number of tasks a group can handle in the presence of other idle
6229	* or lightly loaded groups in the same sched domain.
6230	*/
6231	static void init_sched_groups_power(int cpu, struct sched_domain *sd)
6232	{
6233	struct sched_domain *child;
6234	struct sched_group *group;
6235
6236	WARN_ON(!sd \|\| !sd->groups);
6237
6238	if (cpu != first_cpu(sd->groups->cpumask))
6239	return;
6240
6241	child = sd->child;
6242
6243	/*
6244	* For perf policy, if the groups in child domain share resources
6245	* (for example cores sharing some portions of the cache hierarchy
6246	* or SMT), then set this domain groups cpu_power such that each group
6247	* can handle only one task, when there are other idle groups in the
6248	* same sched domain.
6249	*/
6250	if (!child \|\| (!(sd->flags & SD_POWERSAVINGS_BALANCE) &&
6251	(child->flags &
6252	(SD_SHARE_CPUPOWER \| SD_SHARE_PKG_RESOURCES)))) {
6253	sd->groups->cpu_power = SCHED_LOAD_SCALE;
6254	return;
6255	}
6256
6257	sd->groups->cpu_power = 0;
6258
6259	/*
6260	* add cpu_power of each child group to this groups cpu_power
6261	*/
6262	group = child->groups;
6263	do {
6264	sd->groups->cpu_power += group->cpu_power;
6265	group = group->next;
6266	} while (group != child->groups);
6267	}
6268
6269	/*
6270	* Build sched domains for a given set of cpus and attach the sched domains
6271	* to the individual cpus
6272	*/
6273	static int build_sched_domains(const cpumask_t *cpu_map)
6274	{
6275	int i;
6276	struct sched_domain *sd;
6277	#ifdef CONFIG_NUMA
6278	struct sched_group **sched_group_nodes = NULL;
6279	int sd_allnodes = 0;
6280
6281	/*
6282	* Allocate the per-node list of sched groups
6283	*/
6284	sched_group_nodes = kzalloc(sizeof(struct sched_group)MAX_NUMNODES,
6285	GFP_KERNEL);
6286	if (!sched_group_nodes) {
6287	printk(KERN_WARNING "Can not alloc sched group node list\n");
6288	return -ENOMEM;
6289	}
6290	sched_group_nodes_bycpu[first_cpu(*cpu_map)] = sched_group_nodes;
6291	#endif
6292
6293	/*
6294	* Set up domains for cpus specified by the cpu_map.
6295	*/
6296	for_each_cpu_mask(i, *cpu_map) {
6297	struct sched_domain sd = NULL, p;
6298	cpumask_t nodemask = node_to_cpumask(cpu_to_node(i));
6299
6300	cpus_and(nodemask, nodemask, *cpu_map);
6301
6302	#ifdef CONFIG_NUMA
6303	if (cpus_weight(*cpu_map)
6304	> SD_NODES_PER_DOMAIN*cpus_weight(nodemask)) {
6305	sd = &per_cpu(allnodes_domains, i);
6306	*sd = SD_ALLNODES_INIT;
6307	sd->span = *cpu_map;
6308	cpu_to_allnodes_group(i, cpu_map, &sd->groups);
6309	p = sd;
6310	sd_allnodes = 1;
6311	} else
6312	p = NULL;
6313
6314	sd = &per_cpu(node_domains, i);
6315	*sd = SD_NODE_INIT;
6316	sd->span = sched_domain_node_span(cpu_to_node(i));
6317	sd->parent = p;
6318	if (p)
6319	p->child = sd;
6320	cpus_and(sd->span, sd->span, *cpu_map);
6321	#endif
6322
6323	p = sd;
6324	sd = &per_cpu(phys_domains, i);
6325	*sd = SD_CPU_INIT;
6326	sd->span = nodemask;
6327	sd->parent = p;
6328	if (p)
6329	p->child = sd;
6330	cpu_to_phys_group(i, cpu_map, &sd->groups);
6331
6332	#ifdef CONFIG_SCHED_MC
6333	p = sd;
6334	sd = &per_cpu(core_domains, i);
6335	*sd = SD_MC_INIT;
6336	sd->span = cpu_coregroup_map(i);
6337	cpus_and(sd->span, sd->span, *cpu_map);
6338	sd->parent = p;
6339	p->child = sd;
6340	cpu_to_core_group(i, cpu_map, &sd->groups);
6341	#endif
6342
6343	#ifdef CONFIG_SCHED_SMT
6344	p = sd;
6345	sd = &per_cpu(cpu_domains, i);
6346	*sd = SD_SIBLING_INIT;
6347	sd->span = cpu_sibling_map[i];
6348	cpus_and(sd->span, sd->span, *cpu_map);
6349	sd->parent = p;
6350	p->child = sd;
6351	cpu_to_cpu_group(i, cpu_map, &sd->groups);
6352	#endif
6353	}
6354
6355	#ifdef CONFIG_SCHED_SMT
6356	/* Set up CPU (sibling) groups */
6357	for_each_cpu_mask(i, *cpu_map) {
6358	cpumask_t this_sibling_map = cpu_sibling_map[i];
6359	cpus_and(this_sibling_map, this_sibling_map, *cpu_map);
6360	if (i != first_cpu(this_sibling_map))
6361	continue;
6362
6363	init_sched_build_groups(this_sibling_map, cpu_map, &cpu_to_cpu_group);
6364	}
6365	#endif
6366
6367	#ifdef CONFIG_SCHED_MC
6368	/* Set up multi-core groups */
6369	for_each_cpu_mask(i, *cpu_map) {
6370	cpumask_t this_core_map = cpu_coregroup_map(i);
6371	cpus_and(this_core_map, this_core_map, *cpu_map);
6372	if (i != first_cpu(this_core_map))
6373	continue;
6374	init_sched_build_groups(this_core_map, cpu_map, &cpu_to_core_group);
6375	}
6376	#endif
6377
6378
6379	/* Set up physical groups */
6380	for (i = 0; i < MAX_NUMNODES; i++) {
6381	cpumask_t nodemask = node_to_cpumask(i);
6382
6383	cpus_and(nodemask, nodemask, *cpu_map);
6384	if (cpus_empty(nodemask))
6385	continue;
6386
6387	init_sched_build_groups(nodemask, cpu_map, &cpu_to_phys_group);
6388	}
6389
6390	#ifdef CONFIG_NUMA
6391	/* Set up node groups */
6392	if (sd_allnodes)
6393	init_sched_build_groups(*cpu_map, cpu_map, &cpu_to_allnodes_group);
6394
6395	for (i = 0; i < MAX_NUMNODES; i++) {
6396	/* Set up node groups */
6397	struct sched_group sg, prev;
6398	cpumask_t nodemask = node_to_cpumask(i);
6399	cpumask_t domainspan;
6400	cpumask_t covered = CPU_MASK_NONE;
6401	int j;
6402
6403	cpus_and(nodemask, nodemask, *cpu_map);
6404	if (cpus_empty(nodemask)) {
6405	sched_group_nodes[i] = NULL;
6406	continue;
6407	}
6408
6409	domainspan = sched_domain_node_span(i);
6410	cpus_and(domainspan, domainspan, *cpu_map);
6411
6412	sg = kmalloc_node(sizeof(struct sched_group), GFP_KERNEL, i);
6413	if (!sg) {
6414	printk(KERN_WARNING "Can not alloc domain group for "
6415	"node %d\n", i);
6416	goto error;
6417	}
6418	sched_group_nodes[i] = sg;
6419	for_each_cpu_mask(j, nodemask) {
6420	struct sched_domain *sd;
6421	sd = &per_cpu(node_domains, j);
6422	sd->groups = sg;
6423	}
6424	sg->cpu_power = 0;
6425	sg->cpumask = nodemask;
6426	sg->next = sg;
6427	cpus_or(covered, covered, nodemask);
6428	prev = sg;
6429
6430	for (j = 0; j < MAX_NUMNODES; j++) {
6431	cpumask_t tmp, notcovered;
6432	int n = (i + j) % MAX_NUMNODES;
6433
6434	cpus_complement(notcovered, covered);
6435	cpus_and(tmp, notcovered, *cpu_map);
6436	cpus_and(tmp, tmp, domainspan);
6437	if (cpus_empty(tmp))
6438	break;
6439
6440	nodemask = node_to_cpumask(n);
6441	cpus_and(tmp, tmp, nodemask);
6442	if (cpus_empty(tmp))
6443	continue;
6444
6445	sg = kmalloc_node(sizeof(struct sched_group),
6446	GFP_KERNEL, i);
6447	if (!sg) {
6448	printk(KERN_WARNING
6449	"Can not alloc domain group for node %d\n", j);
6450	goto error;
6451	}
6452	sg->cpu_power = 0;
6453	sg->cpumask = tmp;
6454	sg->next = prev->next;
6455	cpus_or(covered, covered, tmp);
6456	prev->next = sg;
6457	prev = sg;
6458	}
6459	}
6460	#endif
6461
6462	/* Calculate CPU power for physical packages and nodes */
6463	#ifdef CONFIG_SCHED_SMT
6464	for_each_cpu_mask(i, *cpu_map) {
6465	sd = &per_cpu(cpu_domains, i);
6466	init_sched_groups_power(i, sd);
6467	}
6468	#endif
6469	#ifdef CONFIG_SCHED_MC
6470	for_each_cpu_mask(i, *cpu_map) {
6471	sd = &per_cpu(core_domains, i);
6472	init_sched_groups_power(i, sd);
6473	}
6474	#endif
6475
6476	for_each_cpu_mask(i, *cpu_map) {
6477	sd = &per_cpu(phys_domains, i);
6478	init_sched_groups_power(i, sd);
6479	}
6480
6481	#ifdef CONFIG_NUMA
6482	for (i = 0; i < MAX_NUMNODES; i++)
6483	init_numa_sched_groups_power(sched_group_nodes[i]);
6484
6485	if (sd_allnodes) {
6486	struct sched_group *sg;
6487
6488	cpu_to_allnodes_group(first_cpu(*cpu_map), cpu_map, &sg);
6489	init_numa_sched_groups_power(sg);
6490	}
6491	#endif
6492
6493	/* Attach the domains */
6494	for_each_cpu_mask(i, *cpu_map) {
6495	struct sched_domain *sd;
6496	#ifdef CONFIG_SCHED_SMT
6497	sd = &per_cpu(cpu_domains, i);
6498	#elif defined(CONFIG_SCHED_MC)
6499	sd = &per_cpu(core_domains, i);
6500	#else
6501	sd = &per_cpu(phys_domains, i);
6502	#endif
6503	cpu_attach_domain(sd, i);
6504	}
6505	/*
6506	* Tune cache-hot values:
6507	*/
6508	calibrate_migration_costs(cpu_map);
6509
6510	return 0;
6511
6512	#ifdef CONFIG_NUMA
6513	error:
6514	free_sched_groups(cpu_map);
6515	return -ENOMEM;
6516	#endif
6517	}
6518	/*
6519	* Set up scheduler domains and groups. Callers must hold the hotplug lock.
6520	*/
6521	static int arch_init_sched_domains(const cpumask_t *cpu_map)
6522	{
6523	cpumask_t cpu_default_map;
6524	int err;
6525
6526	/*
6527	* Setup mask for cpus without special case scheduling requirements.
6528	* For now this just excludes isolated cpus, but could be used to
6529	* exclude other special cases in the future.
6530	*/
6531	cpus_andnot(cpu_default_map, *cpu_map, cpu_isolated_map);
6532
6533	err = build_sched_domains(&cpu_default_map);
6534
6535	return err;
6536	}
6537
6538	static void arch_destroy_sched_domains(const cpumask_t *cpu_map)
6539	{
6540	free_sched_groups(cpu_map);
6541	}
6542
6543	/*
6544	* Detach sched domains from a group of cpus specified in cpu_map
6545	* These cpus will now be attached to the NULL domain
6546	*/
6547	static void detach_destroy_domains(const cpumask_t *cpu_map)
6548	{
6549	int i;
6550
6551	for_each_cpu_mask(i, *cpu_map)
6552	cpu_attach_domain(NULL, i);
6553	synchronize_sched();
6554	arch_destroy_sched_domains(cpu_map);
6555	}
6556
6557	/*
6558	* Partition sched domains as specified by the cpumasks below.
6559	* This attaches all cpus from the cpumasks to the NULL domain,
6560	* waits for a RCU quiescent period, recalculates sched
6561	* domain information and then attaches them back to the
6562	* correct sched domains
6563	* Call with hotplug lock held
6564	*/
6565	int partition_sched_domains(cpumask_t partition1, cpumask_t partition2)
6566	{
6567	cpumask_t change_map;
6568	int err = 0;
6569
6570	cpus_and(partition1, partition1, cpu_online_map);
6571	cpus_and(partition2, partition2, cpu_online_map);
6572	cpus_or(change_map, partition1, partition2);
6573
6574	/* Detach sched domains from all of the affected cpus */
6575	detach_destroy_domains(&change_map);
6576	if (!cpus_empty(*partition1))
6577	err = build_sched_domains(partition1);
6578	if (!err && !cpus_empty(*partition2))
6579	err = build_sched_domains(partition2);
6580
6581	return err;
6582	}
6583
6584	#if defined(CONFIG_SCHED_MC) \|\| defined(CONFIG_SCHED_SMT)
6585	int arch_reinit_sched_domains(void)
6586	{
6587	int err;
6588
6589	lock_cpu_hotplug();
6590	detach_destroy_domains(&cpu_online_map);
6591	err = arch_init_sched_domains(&cpu_online_map);
6592	unlock_cpu_hotplug();
6593
6594	return err;
6595	}
6596
6597	static ssize_t sched_power_savings_store(const char *buf, size_t count, int smt)
6598	{
6599	int ret;
6600
6601	if (buf[0] != '0' && buf[0] != '1')
6602	return -EINVAL;
6603
6604	if (smt)
6605	sched_smt_power_savings = (buf[0] == '1');
6606	else
6607	sched_mc_power_savings = (buf[0] == '1');
6608
6609	ret = arch_reinit_sched_domains();
6610
6611	return ret ? ret : count;
6612	}
6613
6614	int sched_create_sysfs_power_savings_entries(struct sysdev_class *cls)
6615	{
6616	int err = 0;
6617
6618	#ifdef CONFIG_SCHED_SMT
6619	if (smt_capable())
6620	err = sysfs_create_file(&cls->kset.kobj,
6621	&attr_sched_smt_power_savings.attr);
6622	#endif
6623	#ifdef CONFIG_SCHED_MC
6624	if (!err && mc_capable())
6625	err = sysfs_create_file(&cls->kset.kobj,
6626	&attr_sched_mc_power_savings.attr);
6627	#endif
6628	return err;
6629	}
6630	#endif
6631
6632	#ifdef CONFIG_SCHED_MC
6633	static ssize_t sched_mc_power_savings_show(struct sys_device dev, char page)
6634	{
6635	return sprintf(page, "%u\n", sched_mc_power_savings);
6636	}
6637	static ssize_t sched_mc_power_savings_store(struct sys_device *dev,
6638	const char *buf, size_t count)
6639	{
6640	return sched_power_savings_store(buf, count, 0);
6641	}
6642	SYSDEV_ATTR(sched_mc_power_savings, 0644, sched_mc_power_savings_show,
6643	sched_mc_power_savings_store);
6644	#endif
6645
6646	#ifdef CONFIG_SCHED_SMT
6647	static ssize_t sched_smt_power_savings_show(struct sys_device dev, char page)
6648	{
6649	return sprintf(page, "%u\n", sched_smt_power_savings);
6650	}
6651	static ssize_t sched_smt_power_savings_store(struct sys_device *dev,
6652	const char *buf, size_t count)
6653	{
6654	return sched_power_savings_store(buf, count, 1);
6655	}
6656	SYSDEV_ATTR(sched_smt_power_savings, 0644, sched_smt_power_savings_show,
6657	sched_smt_power_savings_store);
6658	#endif
6659
6660	/*
6661	* Force a reinitialization of the sched domains hierarchy. The domains
6662	* and groups cannot be updated in place without racing with the balancing
6663	* code, so we temporarily attach all running cpus to the NULL domain
6664	* which will prevent rebalancing while the sched domains are recalculated.
6665	*/
6666	static int update_sched_domains(struct notifier_block *nfb,
6667	unsigned long action, void *hcpu)
6668	{
6669	switch (action) {
6670	case CPU_UP_PREPARE:
6671	case CPU_DOWN_PREPARE:
6672	detach_destroy_domains(&cpu_online_map);
6673	return NOTIFY_OK;
6674
6675	case CPU_UP_CANCELED:
6676	case CPU_DOWN_FAILED:
6677	case CPU_ONLINE:
6678	case CPU_DEAD:
6679	/*
6680	* Fall through and re-initialise the domains.
6681	*/
6682	break;
6683	default:
6684	return NOTIFY_DONE;
6685	}
6686
6687	/* The hotplug lock is already held by cpu_up/cpu_down */
6688	arch_init_sched_domains(&cpu_online_map);
6689
6690	return NOTIFY_OK;
6691	}
6692
6693	void __init sched_init_smp(void)
6694	{
6695	cpumask_t non_isolated_cpus;
6696
6697	lock_cpu_hotplug();
6698	arch_init_sched_domains(&cpu_online_map);
6699	cpus_andnot(non_isolated_cpus, cpu_possible_map, cpu_isolated_map);
6700	if (cpus_empty(non_isolated_cpus))
6701	cpu_set(smp_processor_id(), non_isolated_cpus);
6702	unlock_cpu_hotplug();
6703	/* XXX: Theoretical race here - CPU may be hotplugged now */
6704	hotcpu_notifier(update_sched_domains, 0);
6705
6706	/* Move init over to a non-isolated CPU */
6707	if (set_cpus_allowed(current, non_isolated_cpus) < 0)
6708	BUG();
6709	}
6710	#else
6711	void __init sched_init_smp(void)
6712	{
6713	}
6714	#endif /* CONFIG_SMP */
6715
6716	int in_sched_functions(unsigned long addr)
6717	{
6718	/* Linker adds these: start and end of __sched functions */
6719	extern char __sched_text_start[], __sched_text_end[];
6720
6721	return in_lock_functions(addr) \|\|
6722	(addr >= (unsigned long)__sched_text_start
6723	&& addr < (unsigned long)__sched_text_end);
6724	}
6725
6726	void __init sched_init(void)
6727	{
6728	int i, j, k;
6729
6730	for_each_possible_cpu(i) {
6731	struct prio_array *array;
6732	struct rq *rq;
6733
6734	rq = cpu_rq(i);
6735	spin_lock_init(&rq->lock);
6736	lockdep_set_class(&rq->lock, &rq->rq_lock_key);
6737	rq->nr_running = 0;
6738	rq->active = rq->arrays;
6739	rq->expired = rq->arrays + 1;
6740	rq->best_expired_prio = MAX_PRIO;
6741
6742	#ifdef CONFIG_SMP
6743	rq->sd = NULL;
6744	for (j = 1; j < 3; j++)
6745	rq->cpu_load[j] = 0;
6746	rq->active_balance = 0;
6747	rq->push_cpu = 0;
6748	rq->cpu = i;
6749	rq->migration_thread = NULL;
6750	INIT_LIST_HEAD(&rq->migration_queue);
6751	#endif
6752	atomic_set(&rq->nr_iowait, 0);
6753
6754	for (j = 0; j < 2; j++) {
6755	array = rq->arrays + j;
6756	for (k = 0; k < MAX_PRIO; k++) {
6757	INIT_LIST_HEAD(array->queue + k);
6758	__clear_bit(k, array->bitmap);
6759	}
6760	// delimiter for bitsearch
6761	__set_bit(MAX_PRIO, array->bitmap);
6762	}
6763	}
6764
6765	set_load_weight(&init_task);
6766
6767	#ifdef CONFIG_SMP
6768	open_softirq(SCHED_SOFTIRQ, run_rebalance_domains, NULL);
6769	#endif
6770
6771	#ifdef CONFIG_RT_MUTEXES
6772	plist_head_init(&init_task.pi_waiters, &init_task.pi_lock);
6773	#endif
6774
6775	/*
6776	* The boot idle thread does lazy MMU switching as well:
6777	*/
6778	atomic_inc(&init_mm.mm_count);
6779	enter_lazy_tlb(&init_mm, current);
6780
6781	/*
6782	* Make us the idle thread. Technically, schedule() should not be
6783	* called from this thread, however somewhere below it might be,
6784	* but because we are the idle thread, we just pick up running again
6785	* when this runqueue becomes "idle".
6786	*/
6787	init_idle(current, smp_processor_id());
6788	}
6789
6790	#ifdef CONFIG_DEBUG_SPINLOCK_SLEEP
6791	void __might_sleep(char *file, int line)
6792	{
6793	#ifdef in_atomic
6794	static unsigned long prev_jiffy; /* ratelimiting */
6795
6796	if ((in_atomic() \|\| irqs_disabled()) &&
6797	system_state == SYSTEM_RUNNING && !oops_in_progress) {
6798	if (time_before(jiffies, prev_jiffy + HZ) && prev_jiffy)
6799	return;
6800	prev_jiffy = jiffies;
6801	printk(KERN_ERR "BUG: sleeping function called from invalid"
6802	" context at %s:%d\n", file, line);
6803	printk("in_atomic():%d, irqs_disabled():%d\n",
6804	in_atomic(), irqs_disabled());
6805	debug_show_held_locks(current);
6806	if (irqs_disabled())
6807	print_irqtrace_events(current);
6808	dump_stack();
6809	}
6810	#endif
6811	}
6812	EXPORT_SYMBOL(__might_sleep);
6813	#endif
6814
6815	#ifdef CONFIG_MAGIC_SYSRQ
6816	void normalize_rt_tasks(void)
6817	{
6818	struct prio_array *array;
6819	struct task_struct *p;
6820	unsigned long flags;
6821	struct rq *rq;
6822
6823	read_lock_irq(&tasklist_lock);
6824	for_each_process(p) {
6825	if (!rt_task(p))
6826	continue;
6827
6828	spin_lock_irqsave(&p->pi_lock, flags);
6829	rq = __task_rq_lock(p);
6830
6831	array = p->array;
6832	if (array)
6833	deactivate_task(p, task_rq(p));
6834	__setscheduler(p, SCHED_NORMAL, 0);
6835	if (array) {
6836	__activate_task(p, task_rq(p));
6837	resched_task(rq->curr);
6838	}
6839
6840	__task_rq_unlock(rq);
6841	spin_unlock_irqrestore(&p->pi_lock, flags);
6842	}
6843	read_unlock_irq(&tasklist_lock);
6844	}
6845
6846	#endif /* CONFIG_MAGIC_SYSRQ */
6847
6848	#ifdef CONFIG_IA64
6849	/*
6850	* These functions are only useful for the IA64 MCA handling.
6851	*
6852	* They can only be called when the whole system has been
6853	* stopped - every CPU needs to be quiescent, and no scheduling
6854	* activity can take place. Using them for anything else would
6855	* be a serious bug, and as a result, they aren't even visible
6856	* under any other configuration.
6857	*/
6858
6859	/**
6860	* curr_task - return the current task for a given cpu.
6861	* @cpu: the processor in question.
6862	*
6863	* ONLY VALID WHEN THE WHOLE SYSTEM IS STOPPED!
6864	*/
6865	struct task_struct *curr_task(int cpu)
6866	{
6867	return cpu_curr(cpu);
6868	}
6869
6870	/**
6871	* set_curr_task - set the current task for a given cpu.
6872	* @cpu: the processor in question.
6873	* @p: the task pointer to set.
6874	*
6875	* Description: This function must only be used when non-maskable interrupts
6876	* are serviced on a separate stack. It allows the architecture to switch the
6877	* notion of the current task on a cpu in a non-blocking manner. This function
6878	* must be called with all CPU's synchronized, and interrupts disabled, the
6879	* and caller must save the original value of the current task (see
6880	* curr_task() above) and restore that value before reenabling interrupts and
6881	* re-starting the system.
6882	*
6883	* ONLY VALID WHEN THE WHOLE SYSTEM IS STOPPED!
6884	*/
6885	void set_curr_task(int cpu, struct task_struct *p)
6886	{
6887	cpu_curr(cpu) = p;
6888	}
6889
6890	#endif