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