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