Merge branch 'timers-nohz-for-linus' of git://git.kernel.org/pub/scm/linux/kernel...
[linux-3.10.git] / kernel / sched / core.c
1 /*
2  *  kernel/sched/core.c
3  *
4  *  Kernel scheduler and related syscalls
5  *
6  *  Copyright (C) 1991-2002  Linus Torvalds
7  *
8  *  1996-12-23  Modified by Dave Grothe to fix bugs in semaphores and
9  *              make semaphores SMP safe
10  *  1998-11-19  Implemented schedule_timeout() and related stuff
11  *              by Andrea Arcangeli
12  *  2002-01-04  New ultra-scalable O(1) scheduler by Ingo Molnar:
13  *              hybrid priority-list and round-robin design with
14  *              an array-switch method of distributing timeslices
15  *              and per-CPU runqueues.  Cleanups and useful suggestions
16  *              by Davide Libenzi, preemptible kernel bits by Robert Love.
17  *  2003-09-03  Interactivity tuning by Con Kolivas.
18  *  2004-04-02  Scheduler domains code by Nick Piggin
19  *  2007-04-15  Work begun on replacing all interactivity tuning with a
20  *              fair scheduling design by Con Kolivas.
21  *  2007-05-05  Load balancing (smp-nice) and other improvements
22  *              by Peter Williams
23  *  2007-05-06  Interactivity improvements to CFS by Mike Galbraith
24  *  2007-07-01  Group scheduling enhancements by Srivatsa Vaddagiri
25  *  2007-11-29  RT balancing improvements by Steven Rostedt, Gregory Haskins,
26  *              Thomas Gleixner, Mike Kravetz
27  */
28
29 #include <linux/mm.h>
30 #include <linux/module.h>
31 #include <linux/nmi.h>
32 #include <linux/init.h>
33 #include <linux/uaccess.h>
34 #include <linux/highmem.h>
35 #include <asm/mmu_context.h>
36 #include <linux/interrupt.h>
37 #include <linux/capability.h>
38 #include <linux/completion.h>
39 #include <linux/kernel_stat.h>
40 #include <linux/debug_locks.h>
41 #include <linux/perf_event.h>
42 #include <linux/security.h>
43 #include <linux/notifier.h>
44 #include <linux/profile.h>
45 #include <linux/freezer.h>
46 #include <linux/vmalloc.h>
47 #include <linux/blkdev.h>
48 #include <linux/delay.h>
49 #include <linux/pid_namespace.h>
50 #include <linux/smp.h>
51 #include <linux/threads.h>
52 #include <linux/timer.h>
53 #include <linux/rcupdate.h>
54 #include <linux/cpu.h>
55 #include <linux/cpuset.h>
56 #include <linux/percpu.h>
57 #include <linux/proc_fs.h>
58 #include <linux/seq_file.h>
59 #include <linux/sysctl.h>
60 #include <linux/syscalls.h>
61 #include <linux/times.h>
62 #include <linux/tsacct_kern.h>
63 #include <linux/kprobes.h>
64 #include <linux/delayacct.h>
65 #include <linux/unistd.h>
66 #include <linux/pagemap.h>
67 #include <linux/hrtimer.h>
68 #include <linux/tick.h>
69 #include <linux/debugfs.h>
70 #include <linux/ctype.h>
71 #include <linux/ftrace.h>
72 #include <linux/slab.h>
73 #include <linux/init_task.h>
74 #include <linux/binfmts.h>
75 #include <linux/context_tracking.h>
76
77 #include <asm/switch_to.h>
78 #include <asm/tlb.h>
79 #include <asm/irq_regs.h>
80 #include <asm/mutex.h>
81 #ifdef CONFIG_PARAVIRT
82 #include <asm/paravirt.h>
83 #endif
84
85 #include "sched.h"
86 #include "../workqueue_internal.h"
87 #include "../smpboot.h"
88
89 #define CREATE_TRACE_POINTS
90 #include <trace/events/sched.h>
91
92 void start_bandwidth_timer(struct hrtimer *period_timer, ktime_t period)
93 {
94         unsigned long delta;
95         ktime_t soft, hard, now;
96
97         for (;;) {
98                 if (hrtimer_active(period_timer))
99                         break;
100
101                 now = hrtimer_cb_get_time(period_timer);
102                 hrtimer_forward(period_timer, now, period);
103
104                 soft = hrtimer_get_softexpires(period_timer);
105                 hard = hrtimer_get_expires(period_timer);
106                 delta = ktime_to_ns(ktime_sub(hard, soft));
107                 __hrtimer_start_range_ns(period_timer, soft, delta,
108                                          HRTIMER_MODE_ABS_PINNED, 0);
109         }
110 }
111
112 DEFINE_MUTEX(sched_domains_mutex);
113 DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
114
115 static void update_rq_clock_task(struct rq *rq, s64 delta);
116
117 void update_rq_clock(struct rq *rq)
118 {
119         s64 delta;
120
121         if (rq->skip_clock_update > 0)
122                 return;
123
124         delta = sched_clock_cpu(cpu_of(rq)) - rq->clock;
125         rq->clock += delta;
126         update_rq_clock_task(rq, delta);
127 }
128
129 /*
130  * Debugging: various feature bits
131  */
132
133 #define SCHED_FEAT(name, enabled)       \
134         (1UL << __SCHED_FEAT_##name) * enabled |
135
136 const_debug unsigned int sysctl_sched_features =
137 #include "features.h"
138         0;
139
140 #undef SCHED_FEAT
141
142 #ifdef CONFIG_SCHED_DEBUG
143 #define SCHED_FEAT(name, enabled)       \
144         #name ,
145
146 static const char * const sched_feat_names[] = {
147 #include "features.h"
148 };
149
150 #undef SCHED_FEAT
151
152 static int sched_feat_show(struct seq_file *m, void *v)
153 {
154         int i;
155
156         for (i = 0; i < __SCHED_FEAT_NR; i++) {
157                 if (!(sysctl_sched_features & (1UL << i)))
158                         seq_puts(m, "NO_");
159                 seq_printf(m, "%s ", sched_feat_names[i]);
160         }
161         seq_puts(m, "\n");
162
163         return 0;
164 }
165
166 #ifdef HAVE_JUMP_LABEL
167
168 #define jump_label_key__true  STATIC_KEY_INIT_TRUE
169 #define jump_label_key__false STATIC_KEY_INIT_FALSE
170
171 #define SCHED_FEAT(name, enabled)       \
172         jump_label_key__##enabled ,
173
174 struct static_key sched_feat_keys[__SCHED_FEAT_NR] = {
175 #include "features.h"
176 };
177
178 #undef SCHED_FEAT
179
180 static void sched_feat_disable(int i)
181 {
182         if (static_key_enabled(&sched_feat_keys[i]))
183                 static_key_slow_dec(&sched_feat_keys[i]);
184 }
185
186 static void sched_feat_enable(int i)
187 {
188         if (!static_key_enabled(&sched_feat_keys[i]))
189                 static_key_slow_inc(&sched_feat_keys[i]);
190 }
191 #else
192 static void sched_feat_disable(int i) { };
193 static void sched_feat_enable(int i) { };
194 #endif /* HAVE_JUMP_LABEL */
195
196 static int sched_feat_set(char *cmp)
197 {
198         int i;
199         int neg = 0;
200
201         if (strncmp(cmp, "NO_", 3) == 0) {
202                 neg = 1;
203                 cmp += 3;
204         }
205
206         for (i = 0; i < __SCHED_FEAT_NR; i++) {
207                 if (strcmp(cmp, sched_feat_names[i]) == 0) {
208                         if (neg) {
209                                 sysctl_sched_features &= ~(1UL << i);
210                                 sched_feat_disable(i);
211                         } else {
212                                 sysctl_sched_features |= (1UL << i);
213                                 sched_feat_enable(i);
214                         }
215                         break;
216                 }
217         }
218
219         return i;
220 }
221
222 static ssize_t
223 sched_feat_write(struct file *filp, const char __user *ubuf,
224                 size_t cnt, loff_t *ppos)
225 {
226         char buf[64];
227         char *cmp;
228         int i;
229
230         if (cnt > 63)
231                 cnt = 63;
232
233         if (copy_from_user(&buf, ubuf, cnt))
234                 return -EFAULT;
235
236         buf[cnt] = 0;
237         cmp = strstrip(buf);
238
239         i = sched_feat_set(cmp);
240         if (i == __SCHED_FEAT_NR)
241                 return -EINVAL;
242
243         *ppos += cnt;
244
245         return cnt;
246 }
247
248 static int sched_feat_open(struct inode *inode, struct file *filp)
249 {
250         return single_open(filp, sched_feat_show, NULL);
251 }
252
253 static const struct file_operations sched_feat_fops = {
254         .open           = sched_feat_open,
255         .write          = sched_feat_write,
256         .read           = seq_read,
257         .llseek         = seq_lseek,
258         .release        = single_release,
259 };
260
261 static __init int sched_init_debug(void)
262 {
263         debugfs_create_file("sched_features", 0644, NULL, NULL,
264                         &sched_feat_fops);
265
266         return 0;
267 }
268 late_initcall(sched_init_debug);
269 #endif /* CONFIG_SCHED_DEBUG */
270
271 /*
272  * Number of tasks to iterate in a single balance run.
273  * Limited because this is done with IRQs disabled.
274  */
275 const_debug unsigned int sysctl_sched_nr_migrate = 32;
276
277 /*
278  * period over which we average the RT time consumption, measured
279  * in ms.
280  *
281  * default: 1s
282  */
283 const_debug unsigned int sysctl_sched_time_avg = MSEC_PER_SEC;
284
285 /*
286  * period over which we measure -rt task cpu usage in us.
287  * default: 1s
288  */
289 unsigned int sysctl_sched_rt_period = 1000000;
290
291 __read_mostly int scheduler_running;
292
293 /*
294  * part of the period that we allow rt tasks to run in us.
295  * default: 0.95s
296  */
297 int sysctl_sched_rt_runtime = 950000;
298
299
300
301 /*
302  * __task_rq_lock - lock the rq @p resides on.
303  */
304 static inline struct rq *__task_rq_lock(struct task_struct *p)
305         __acquires(rq->lock)
306 {
307         struct rq *rq;
308
309         lockdep_assert_held(&p->pi_lock);
310
311         for (;;) {
312                 rq = task_rq(p);
313                 raw_spin_lock(&rq->lock);
314                 if (likely(rq == task_rq(p)))
315                         return rq;
316                 raw_spin_unlock(&rq->lock);
317         }
318 }
319
320 /*
321  * task_rq_lock - lock p->pi_lock and lock the rq @p resides on.
322  */
323 static struct rq *task_rq_lock(struct task_struct *p, unsigned long *flags)
324         __acquires(p->pi_lock)
325         __acquires(rq->lock)
326 {
327         struct rq *rq;
328
329         for (;;) {
330                 raw_spin_lock_irqsave(&p->pi_lock, *flags);
331                 rq = task_rq(p);
332                 raw_spin_lock(&rq->lock);
333                 if (likely(rq == task_rq(p)))
334                         return rq;
335                 raw_spin_unlock(&rq->lock);
336                 raw_spin_unlock_irqrestore(&p->pi_lock, *flags);
337         }
338 }
339
340 static void __task_rq_unlock(struct rq *rq)
341         __releases(rq->lock)
342 {
343         raw_spin_unlock(&rq->lock);
344 }
345
346 static inline void
347 task_rq_unlock(struct rq *rq, struct task_struct *p, unsigned long *flags)
348         __releases(rq->lock)
349         __releases(p->pi_lock)
350 {
351         raw_spin_unlock(&rq->lock);
352         raw_spin_unlock_irqrestore(&p->pi_lock, *flags);
353 }
354
355 /*
356  * this_rq_lock - lock this runqueue and disable interrupts.
357  */
358 static struct rq *this_rq_lock(void)
359         __acquires(rq->lock)
360 {
361         struct rq *rq;
362
363         local_irq_disable();
364         rq = this_rq();
365         raw_spin_lock(&rq->lock);
366
367         return rq;
368 }
369
370 #ifdef CONFIG_SCHED_HRTICK
371 /*
372  * Use HR-timers to deliver accurate preemption points.
373  *
374  * Its all a bit involved since we cannot program an hrt while holding the
375  * rq->lock. So what we do is store a state in in rq->hrtick_* and ask for a
376  * reschedule event.
377  *
378  * When we get rescheduled we reprogram the hrtick_timer outside of the
379  * rq->lock.
380  */
381
382 static void hrtick_clear(struct rq *rq)
383 {
384         if (hrtimer_active(&rq->hrtick_timer))
385                 hrtimer_cancel(&rq->hrtick_timer);
386 }
387
388 /*
389  * High-resolution timer tick.
390  * Runs from hardirq context with interrupts disabled.
391  */
392 static enum hrtimer_restart hrtick(struct hrtimer *timer)
393 {
394         struct rq *rq = container_of(timer, struct rq, hrtick_timer);
395
396         WARN_ON_ONCE(cpu_of(rq) != smp_processor_id());
397
398         raw_spin_lock(&rq->lock);
399         update_rq_clock(rq);
400         rq->curr->sched_class->task_tick(rq, rq->curr, 1);
401         raw_spin_unlock(&rq->lock);
402
403         return HRTIMER_NORESTART;
404 }
405
406 #ifdef CONFIG_SMP
407 /*
408  * called from hardirq (IPI) context
409  */
410 static void __hrtick_start(void *arg)
411 {
412         struct rq *rq = arg;
413
414         raw_spin_lock(&rq->lock);
415         hrtimer_restart(&rq->hrtick_timer);
416         rq->hrtick_csd_pending = 0;
417         raw_spin_unlock(&rq->lock);
418 }
419
420 /*
421  * Called to set the hrtick timer state.
422  *
423  * called with rq->lock held and irqs disabled
424  */
425 void hrtick_start(struct rq *rq, u64 delay)
426 {
427         struct hrtimer *timer = &rq->hrtick_timer;
428         ktime_t time = ktime_add_ns(timer->base->get_time(), delay);
429
430         hrtimer_set_expires(timer, time);
431
432         if (rq == this_rq()) {
433                 hrtimer_restart(timer);
434         } else if (!rq->hrtick_csd_pending) {
435                 __smp_call_function_single(cpu_of(rq), &rq->hrtick_csd, 0);
436                 rq->hrtick_csd_pending = 1;
437         }
438 }
439
440 static int
441 hotplug_hrtick(struct notifier_block *nfb, unsigned long action, void *hcpu)
442 {
443         int cpu = (int)(long)hcpu;
444
445         switch (action) {
446         case CPU_UP_CANCELED:
447         case CPU_UP_CANCELED_FROZEN:
448         case CPU_DOWN_PREPARE:
449         case CPU_DOWN_PREPARE_FROZEN:
450         case CPU_DEAD:
451         case CPU_DEAD_FROZEN:
452                 hrtick_clear(cpu_rq(cpu));
453                 return NOTIFY_OK;
454         }
455
456         return NOTIFY_DONE;
457 }
458
459 static __init void init_hrtick(void)
460 {
461         hotcpu_notifier(hotplug_hrtick, 0);
462 }
463 #else
464 /*
465  * Called to set the hrtick timer state.
466  *
467  * called with rq->lock held and irqs disabled
468  */
469 void hrtick_start(struct rq *rq, u64 delay)
470 {
471         __hrtimer_start_range_ns(&rq->hrtick_timer, ns_to_ktime(delay), 0,
472                         HRTIMER_MODE_REL_PINNED, 0);
473 }
474
475 static inline void init_hrtick(void)
476 {
477 }
478 #endif /* CONFIG_SMP */
479
480 static void init_rq_hrtick(struct rq *rq)
481 {
482 #ifdef CONFIG_SMP
483         rq->hrtick_csd_pending = 0;
484
485         rq->hrtick_csd.flags = 0;
486         rq->hrtick_csd.func = __hrtick_start;
487         rq->hrtick_csd.info = rq;
488 #endif
489
490         hrtimer_init(&rq->hrtick_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
491         rq->hrtick_timer.function = hrtick;
492 }
493 #else   /* CONFIG_SCHED_HRTICK */
494 static inline void hrtick_clear(struct rq *rq)
495 {
496 }
497
498 static inline void init_rq_hrtick(struct rq *rq)
499 {
500 }
501
502 static inline void init_hrtick(void)
503 {
504 }
505 #endif  /* CONFIG_SCHED_HRTICK */
506
507 /*
508  * resched_task - mark a task 'to be rescheduled now'.
509  *
510  * On UP this means the setting of the need_resched flag, on SMP it
511  * might also involve a cross-CPU call to trigger the scheduler on
512  * the target CPU.
513  */
514 #ifdef CONFIG_SMP
515 void resched_task(struct task_struct *p)
516 {
517         int cpu;
518
519         assert_raw_spin_locked(&task_rq(p)->lock);
520
521         if (test_tsk_need_resched(p))
522                 return;
523
524         set_tsk_need_resched(p);
525
526         cpu = task_cpu(p);
527         if (cpu == smp_processor_id())
528                 return;
529
530         /* NEED_RESCHED must be visible before we test polling */
531         smp_mb();
532         if (!tsk_is_polling(p))
533                 smp_send_reschedule(cpu);
534 }
535
536 void resched_cpu(int cpu)
537 {
538         struct rq *rq = cpu_rq(cpu);
539         unsigned long flags;
540
541         if (!raw_spin_trylock_irqsave(&rq->lock, flags))
542                 return;
543         resched_task(cpu_curr(cpu));
544         raw_spin_unlock_irqrestore(&rq->lock, flags);
545 }
546
547 #ifdef CONFIG_NO_HZ_COMMON
548 /*
549  * In the semi idle case, use the nearest busy cpu for migrating timers
550  * from an idle cpu.  This is good for power-savings.
551  *
552  * We don't do similar optimization for completely idle system, as
553  * selecting an idle cpu will add more delays to the timers than intended
554  * (as that cpu's timer base may not be uptodate wrt jiffies etc).
555  */
556 int get_nohz_timer_target(void)
557 {
558         int cpu = smp_processor_id();
559         int i;
560         struct sched_domain *sd;
561
562         rcu_read_lock();
563         for_each_domain(cpu, sd) {
564                 for_each_cpu(i, sched_domain_span(sd)) {
565                         if (!idle_cpu(i)) {
566                                 cpu = i;
567                                 goto unlock;
568                         }
569                 }
570         }
571 unlock:
572         rcu_read_unlock();
573         return cpu;
574 }
575 /*
576  * When add_timer_on() enqueues a timer into the timer wheel of an
577  * idle CPU then this timer might expire before the next timer event
578  * which is scheduled to wake up that CPU. In case of a completely
579  * idle system the next event might even be infinite time into the
580  * future. wake_up_idle_cpu() ensures that the CPU is woken up and
581  * leaves the inner idle loop so the newly added timer is taken into
582  * account when the CPU goes back to idle and evaluates the timer
583  * wheel for the next timer event.
584  */
585 static void wake_up_idle_cpu(int cpu)
586 {
587         struct rq *rq = cpu_rq(cpu);
588
589         if (cpu == smp_processor_id())
590                 return;
591
592         /*
593          * This is safe, as this function is called with the timer
594          * wheel base lock of (cpu) held. When the CPU is on the way
595          * to idle and has not yet set rq->curr to idle then it will
596          * be serialized on the timer wheel base lock and take the new
597          * timer into account automatically.
598          */
599         if (rq->curr != rq->idle)
600                 return;
601
602         /*
603          * We can set TIF_RESCHED on the idle task of the other CPU
604          * lockless. The worst case is that the other CPU runs the
605          * idle task through an additional NOOP schedule()
606          */
607         set_tsk_need_resched(rq->idle);
608
609         /* NEED_RESCHED must be visible before we test polling */
610         smp_mb();
611         if (!tsk_is_polling(rq->idle))
612                 smp_send_reschedule(cpu);
613 }
614
615 static bool wake_up_full_nohz_cpu(int cpu)
616 {
617         if (tick_nohz_full_cpu(cpu)) {
618                 if (cpu != smp_processor_id() ||
619                     tick_nohz_tick_stopped())
620                         smp_send_reschedule(cpu);
621                 return true;
622         }
623
624         return false;
625 }
626
627 void wake_up_nohz_cpu(int cpu)
628 {
629         if (!wake_up_full_nohz_cpu(cpu))
630                 wake_up_idle_cpu(cpu);
631 }
632
633 static inline bool got_nohz_idle_kick(void)
634 {
635         int cpu = smp_processor_id();
636         return idle_cpu(cpu) && test_bit(NOHZ_BALANCE_KICK, nohz_flags(cpu));
637 }
638
639 #else /* CONFIG_NO_HZ_COMMON */
640
641 static inline bool got_nohz_idle_kick(void)
642 {
643         return false;
644 }
645
646 #endif /* CONFIG_NO_HZ_COMMON */
647
648 #ifdef CONFIG_NO_HZ_FULL
649 bool sched_can_stop_tick(void)
650 {
651        struct rq *rq;
652
653        rq = this_rq();
654
655        /* Make sure rq->nr_running update is visible after the IPI */
656        smp_rmb();
657
658        /* More than one running task need preemption */
659        if (rq->nr_running > 1)
660                return false;
661
662        return true;
663 }
664 #endif /* CONFIG_NO_HZ_FULL */
665
666 void sched_avg_update(struct rq *rq)
667 {
668         s64 period = sched_avg_period();
669
670         while ((s64)(rq->clock - rq->age_stamp) > period) {
671                 /*
672                  * Inline assembly required to prevent the compiler
673                  * optimising this loop into a divmod call.
674                  * See __iter_div_u64_rem() for another example of this.
675                  */
676                 asm("" : "+rm" (rq->age_stamp));
677                 rq->age_stamp += period;
678                 rq->rt_avg /= 2;
679         }
680 }
681
682 #else /* !CONFIG_SMP */
683 void resched_task(struct task_struct *p)
684 {
685         assert_raw_spin_locked(&task_rq(p)->lock);
686         set_tsk_need_resched(p);
687 }
688 #endif /* CONFIG_SMP */
689
690 #if defined(CONFIG_RT_GROUP_SCHED) || (defined(CONFIG_FAIR_GROUP_SCHED) && \
691                         (defined(CONFIG_SMP) || defined(CONFIG_CFS_BANDWIDTH)))
692 /*
693  * Iterate task_group tree rooted at *from, calling @down when first entering a
694  * node and @up when leaving it for the final time.
695  *
696  * Caller must hold rcu_lock or sufficient equivalent.
697  */
698 int walk_tg_tree_from(struct task_group *from,
699                              tg_visitor down, tg_visitor up, void *data)
700 {
701         struct task_group *parent, *child;
702         int ret;
703
704         parent = from;
705
706 down:
707         ret = (*down)(parent, data);
708         if (ret)
709                 goto out;
710         list_for_each_entry_rcu(child, &parent->children, siblings) {
711                 parent = child;
712                 goto down;
713
714 up:
715                 continue;
716         }
717         ret = (*up)(parent, data);
718         if (ret || parent == from)
719                 goto out;
720
721         child = parent;
722         parent = parent->parent;
723         if (parent)
724                 goto up;
725 out:
726         return ret;
727 }
728
729 int tg_nop(struct task_group *tg, void *data)
730 {
731         return 0;
732 }
733 #endif
734
735 static void set_load_weight(struct task_struct *p)
736 {
737         int prio = p->static_prio - MAX_RT_PRIO;
738         struct load_weight *load = &p->se.load;
739
740         /*
741          * SCHED_IDLE tasks get minimal weight:
742          */
743         if (p->policy == SCHED_IDLE) {
744                 load->weight = scale_load(WEIGHT_IDLEPRIO);
745                 load->inv_weight = WMULT_IDLEPRIO;
746                 return;
747         }
748
749         load->weight = scale_load(prio_to_weight[prio]);
750         load->inv_weight = prio_to_wmult[prio];
751 }
752
753 static void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
754 {
755         update_rq_clock(rq);
756         sched_info_queued(p);
757         p->sched_class->enqueue_task(rq, p, flags);
758 }
759
760 static void dequeue_task(struct rq *rq, struct task_struct *p, int flags)
761 {
762         update_rq_clock(rq);
763         sched_info_dequeued(p);
764         p->sched_class->dequeue_task(rq, p, flags);
765 }
766
767 void activate_task(struct rq *rq, struct task_struct *p, int flags)
768 {
769         if (task_contributes_to_load(p))
770                 rq->nr_uninterruptible--;
771
772         enqueue_task(rq, p, flags);
773 }
774
775 void deactivate_task(struct rq *rq, struct task_struct *p, int flags)
776 {
777         if (task_contributes_to_load(p))
778                 rq->nr_uninterruptible++;
779
780         dequeue_task(rq, p, flags);
781 }
782
783 static void update_rq_clock_task(struct rq *rq, s64 delta)
784 {
785 /*
786  * In theory, the compile should just see 0 here, and optimize out the call
787  * to sched_rt_avg_update. But I don't trust it...
788  */
789 #if defined(CONFIG_IRQ_TIME_ACCOUNTING) || defined(CONFIG_PARAVIRT_TIME_ACCOUNTING)
790         s64 steal = 0, irq_delta = 0;
791 #endif
792 #ifdef CONFIG_IRQ_TIME_ACCOUNTING
793         irq_delta = irq_time_read(cpu_of(rq)) - rq->prev_irq_time;
794
795         /*
796          * Since irq_time is only updated on {soft,}irq_exit, we might run into
797          * this case when a previous update_rq_clock() happened inside a
798          * {soft,}irq region.
799          *
800          * When this happens, we stop ->clock_task and only update the
801          * prev_irq_time stamp to account for the part that fit, so that a next
802          * update will consume the rest. This ensures ->clock_task is
803          * monotonic.
804          *
805          * It does however cause some slight miss-attribution of {soft,}irq
806          * time, a more accurate solution would be to update the irq_time using
807          * the current rq->clock timestamp, except that would require using
808          * atomic ops.
809          */
810         if (irq_delta > delta)
811                 irq_delta = delta;
812
813         rq->prev_irq_time += irq_delta;
814         delta -= irq_delta;
815 #endif
816 #ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
817         if (static_key_false((&paravirt_steal_rq_enabled))) {
818                 u64 st;
819
820                 steal = paravirt_steal_clock(cpu_of(rq));
821                 steal -= rq->prev_steal_time_rq;
822
823                 if (unlikely(steal > delta))
824                         steal = delta;
825
826                 st = steal_ticks(steal);
827                 steal = st * TICK_NSEC;
828
829                 rq->prev_steal_time_rq += steal;
830
831                 delta -= steal;
832         }
833 #endif
834
835         rq->clock_task += delta;
836
837 #if defined(CONFIG_IRQ_TIME_ACCOUNTING) || defined(CONFIG_PARAVIRT_TIME_ACCOUNTING)
838         if ((irq_delta + steal) && sched_feat(NONTASK_POWER))
839                 sched_rt_avg_update(rq, irq_delta + steal);
840 #endif
841 }
842
843 void sched_set_stop_task(int cpu, struct task_struct *stop)
844 {
845         struct sched_param param = { .sched_priority = MAX_RT_PRIO - 1 };
846         struct task_struct *old_stop = cpu_rq(cpu)->stop;
847
848         if (stop) {
849                 /*
850                  * Make it appear like a SCHED_FIFO task, its something
851                  * userspace knows about and won't get confused about.
852                  *
853                  * Also, it will make PI more or less work without too
854                  * much confusion -- but then, stop work should not
855                  * rely on PI working anyway.
856                  */
857                 sched_setscheduler_nocheck(stop, SCHED_FIFO, &param);
858
859                 stop->sched_class = &stop_sched_class;
860         }
861
862         cpu_rq(cpu)->stop = stop;
863
864         if (old_stop) {
865                 /*
866                  * Reset it back to a normal scheduling class so that
867                  * it can die in pieces.
868                  */
869                 old_stop->sched_class = &rt_sched_class;
870         }
871 }
872
873 /*
874  * __normal_prio - return the priority that is based on the static prio
875  */
876 static inline int __normal_prio(struct task_struct *p)
877 {
878         return p->static_prio;
879 }
880
881 /*
882  * Calculate the expected normal priority: i.e. priority
883  * without taking RT-inheritance into account. Might be
884  * boosted by interactivity modifiers. Changes upon fork,
885  * setprio syscalls, and whenever the interactivity
886  * estimator recalculates.
887  */
888 static inline int normal_prio(struct task_struct *p)
889 {
890         int prio;
891
892         if (task_has_rt_policy(p))
893                 prio = MAX_RT_PRIO-1 - p->rt_priority;
894         else
895                 prio = __normal_prio(p);
896         return prio;
897 }
898
899 /*
900  * Calculate the current priority, i.e. the priority
901  * taken into account by the scheduler. This value might
902  * be boosted by RT tasks, or might be boosted by
903  * interactivity modifiers. Will be RT if the task got
904  * RT-boosted. If not then it returns p->normal_prio.
905  */
906 static int effective_prio(struct task_struct *p)
907 {
908         p->normal_prio = normal_prio(p);
909         /*
910          * If we are RT tasks or we were boosted to RT priority,
911          * keep the priority unchanged. Otherwise, update priority
912          * to the normal priority:
913          */
914         if (!rt_prio(p->prio))
915                 return p->normal_prio;
916         return p->prio;
917 }
918
919 /**
920  * task_curr - is this task currently executing on a CPU?
921  * @p: the task in question.
922  */
923 inline int task_curr(const struct task_struct *p)
924 {
925         return cpu_curr(task_cpu(p)) == p;
926 }
927
928 static inline void check_class_changed(struct rq *rq, struct task_struct *p,
929                                        const struct sched_class *prev_class,
930                                        int oldprio)
931 {
932         if (prev_class != p->sched_class) {
933                 if (prev_class->switched_from)
934                         prev_class->switched_from(rq, p);
935                 p->sched_class->switched_to(rq, p);
936         } else if (oldprio != p->prio)
937                 p->sched_class->prio_changed(rq, p, oldprio);
938 }
939
940 void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
941 {
942         const struct sched_class *class;
943
944         if (p->sched_class == rq->curr->sched_class) {
945                 rq->curr->sched_class->check_preempt_curr(rq, p, flags);
946         } else {
947                 for_each_class(class) {
948                         if (class == rq->curr->sched_class)
949                                 break;
950                         if (class == p->sched_class) {
951                                 resched_task(rq->curr);
952                                 break;
953                         }
954                 }
955         }
956
957         /*
958          * A queue event has occurred, and we're going to schedule.  In
959          * this case, we can save a useless back to back clock update.
960          */
961         if (rq->curr->on_rq && test_tsk_need_resched(rq->curr))
962                 rq->skip_clock_update = 1;
963 }
964
965 static ATOMIC_NOTIFIER_HEAD(task_migration_notifier);
966
967 void register_task_migration_notifier(struct notifier_block *n)
968 {
969         atomic_notifier_chain_register(&task_migration_notifier, n);
970 }
971
972 #ifdef CONFIG_SMP
973 void set_task_cpu(struct task_struct *p, unsigned int new_cpu)
974 {
975 #ifdef CONFIG_SCHED_DEBUG
976         /*
977          * We should never call set_task_cpu() on a blocked task,
978          * ttwu() will sort out the placement.
979          */
980         WARN_ON_ONCE(p->state != TASK_RUNNING && p->state != TASK_WAKING &&
981                         !(task_thread_info(p)->preempt_count & PREEMPT_ACTIVE));
982
983 #ifdef CONFIG_LOCKDEP
984         /*
985          * The caller should hold either p->pi_lock or rq->lock, when changing
986          * a task's CPU. ->pi_lock for waking tasks, rq->lock for runnable tasks.
987          *
988          * sched_move_task() holds both and thus holding either pins the cgroup,
989          * see task_group().
990          *
991          * Furthermore, all task_rq users should acquire both locks, see
992          * task_rq_lock().
993          */
994         WARN_ON_ONCE(debug_locks && !(lockdep_is_held(&p->pi_lock) ||
995                                       lockdep_is_held(&task_rq(p)->lock)));
996 #endif
997 #endif
998
999         trace_sched_migrate_task(p, new_cpu);
1000
1001         if (task_cpu(p) != new_cpu) {
1002                 struct task_migration_notifier tmn;
1003
1004                 if (p->sched_class->migrate_task_rq)
1005                         p->sched_class->migrate_task_rq(p, new_cpu);
1006                 p->se.nr_migrations++;
1007                 perf_sw_event(PERF_COUNT_SW_CPU_MIGRATIONS, 1, NULL, 0);
1008
1009                 tmn.task = p;
1010                 tmn.from_cpu = task_cpu(p);
1011                 tmn.to_cpu = new_cpu;
1012
1013                 atomic_notifier_call_chain(&task_migration_notifier, 0, &tmn);
1014         }
1015
1016         __set_task_cpu(p, new_cpu);
1017 }
1018
1019 struct migration_arg {
1020         struct task_struct *task;
1021         int dest_cpu;
1022 };
1023
1024 static int migration_cpu_stop(void *data);
1025
1026 /*
1027  * wait_task_inactive - wait for a thread to unschedule.
1028  *
1029  * If @match_state is nonzero, it's the @p->state value just checked and
1030  * not expected to change.  If it changes, i.e. @p might have woken up,
1031  * then return zero.  When we succeed in waiting for @p to be off its CPU,
1032  * we return a positive number (its total switch count).  If a second call
1033  * a short while later returns the same number, the caller can be sure that
1034  * @p has remained unscheduled the whole time.
1035  *
1036  * The caller must ensure that the task *will* unschedule sometime soon,
1037  * else this function might spin for a *long* time. This function can't
1038  * be called with interrupts off, or it may introduce deadlock with
1039  * smp_call_function() if an IPI is sent by the same process we are
1040  * waiting to become inactive.
1041  */
1042 unsigned long wait_task_inactive(struct task_struct *p, long match_state)
1043 {
1044         unsigned long flags;
1045         int running, on_rq;
1046         unsigned long ncsw;
1047         struct rq *rq;
1048
1049         for (;;) {
1050                 /*
1051                  * We do the initial early heuristics without holding
1052                  * any task-queue locks at all. We'll only try to get
1053                  * the runqueue lock when things look like they will
1054                  * work out!
1055                  */
1056                 rq = task_rq(p);
1057
1058                 /*
1059                  * If the task is actively running on another CPU
1060                  * still, just relax and busy-wait without holding
1061                  * any locks.
1062                  *
1063                  * NOTE! Since we don't hold any locks, it's not
1064                  * even sure that "rq" stays as the right runqueue!
1065                  * But we don't care, since "task_running()" will
1066                  * return false if the runqueue has changed and p
1067                  * is actually now running somewhere else!
1068                  */
1069                 while (task_running(rq, p)) {
1070                         if (match_state && unlikely(p->state != match_state))
1071                                 return 0;
1072                         cpu_relax();
1073                 }
1074
1075                 /*
1076                  * Ok, time to look more closely! We need the rq
1077                  * lock now, to be *sure*. If we're wrong, we'll
1078                  * just go back and repeat.
1079                  */
1080                 rq = task_rq_lock(p, &flags);
1081                 trace_sched_wait_task(p);
1082                 running = task_running(rq, p);
1083                 on_rq = p->on_rq;
1084                 ncsw = 0;
1085                 if (!match_state || p->state == match_state)
1086                         ncsw = p->nvcsw | LONG_MIN; /* sets MSB */
1087                 task_rq_unlock(rq, p, &flags);
1088
1089                 /*
1090                  * If it changed from the expected state, bail out now.
1091                  */
1092                 if (unlikely(!ncsw))
1093                         break;
1094
1095                 /*
1096                  * Was it really running after all now that we
1097                  * checked with the proper locks actually held?
1098                  *
1099                  * Oops. Go back and try again..
1100                  */
1101                 if (unlikely(running)) {
1102                         cpu_relax();
1103                         continue;
1104                 }
1105
1106                 /*
1107                  * It's not enough that it's not actively running,
1108                  * it must be off the runqueue _entirely_, and not
1109                  * preempted!
1110                  *
1111                  * So if it was still runnable (but just not actively
1112                  * running right now), it's preempted, and we should
1113                  * yield - it could be a while.
1114                  */
1115                 if (unlikely(on_rq)) {
1116                         ktime_t to = ktime_set(0, NSEC_PER_SEC/HZ);
1117
1118                         set_current_state(TASK_UNINTERRUPTIBLE);
1119                         schedule_hrtimeout(&to, HRTIMER_MODE_REL);
1120                         continue;
1121                 }
1122
1123                 /*
1124                  * Ahh, all good. It wasn't running, and it wasn't
1125                  * runnable, which means that it will never become
1126                  * running in the future either. We're all done!
1127                  */
1128                 break;
1129         }
1130
1131         return ncsw;
1132 }
1133
1134 /***
1135  * kick_process - kick a running thread to enter/exit the kernel
1136  * @p: the to-be-kicked thread
1137  *
1138  * Cause a process which is running on another CPU to enter
1139  * kernel-mode, without any delay. (to get signals handled.)
1140  *
1141  * NOTE: this function doesn't have to take the runqueue lock,
1142  * because all it wants to ensure is that the remote task enters
1143  * the kernel. If the IPI races and the task has been migrated
1144  * to another CPU then no harm is done and the purpose has been
1145  * achieved as well.
1146  */
1147 void kick_process(struct task_struct *p)
1148 {
1149         int cpu;
1150
1151         preempt_disable();
1152         cpu = task_cpu(p);
1153         if ((cpu != smp_processor_id()) && task_curr(p))
1154                 smp_send_reschedule(cpu);
1155         preempt_enable();
1156 }
1157 EXPORT_SYMBOL_GPL(kick_process);
1158 #endif /* CONFIG_SMP */
1159
1160 #ifdef CONFIG_SMP
1161 /*
1162  * ->cpus_allowed is protected by both rq->lock and p->pi_lock
1163  */
1164 static int select_fallback_rq(int cpu, struct task_struct *p)
1165 {
1166         int nid = cpu_to_node(cpu);
1167         const struct cpumask *nodemask = NULL;
1168         enum { cpuset, possible, fail } state = cpuset;
1169         int dest_cpu;
1170
1171         /*
1172          * If the node that the cpu is on has been offlined, cpu_to_node()
1173          * will return -1. There is no cpu on the node, and we should
1174          * select the cpu on the other node.
1175          */
1176         if (nid != -1) {
1177                 nodemask = cpumask_of_node(nid);
1178
1179                 /* Look for allowed, online CPU in same node. */
1180                 for_each_cpu(dest_cpu, nodemask) {
1181                         if (!cpu_online(dest_cpu))
1182                                 continue;
1183                         if (!cpu_active(dest_cpu))
1184                                 continue;
1185                         if (cpumask_test_cpu(dest_cpu, tsk_cpus_allowed(p)))
1186                                 return dest_cpu;
1187                 }
1188         }
1189
1190         for (;;) {
1191                 /* Any allowed, online CPU? */
1192                 for_each_cpu(dest_cpu, tsk_cpus_allowed(p)) {
1193                         if (!cpu_online(dest_cpu))
1194                                 continue;
1195                         if (!cpu_active(dest_cpu))
1196                                 continue;
1197                         goto out;
1198                 }
1199
1200                 switch (state) {
1201                 case cpuset:
1202                         /* No more Mr. Nice Guy. */
1203                         cpuset_cpus_allowed_fallback(p);
1204                         state = possible;
1205                         break;
1206
1207                 case possible:
1208                         do_set_cpus_allowed(p, cpu_possible_mask);
1209                         state = fail;
1210                         break;
1211
1212                 case fail:
1213                         BUG();
1214                         break;
1215                 }
1216         }
1217
1218 out:
1219         if (state != cpuset) {
1220                 /*
1221                  * Don't tell them about moving exiting tasks or
1222                  * kernel threads (both mm NULL), since they never
1223                  * leave kernel.
1224                  */
1225                 if (p->mm && printk_ratelimit()) {
1226                         printk_sched("process %d (%s) no longer affine to cpu%d\n",
1227                                         task_pid_nr(p), p->comm, cpu);
1228                 }
1229         }
1230
1231         return dest_cpu;
1232 }
1233
1234 /*
1235  * The caller (fork, wakeup) owns p->pi_lock, ->cpus_allowed is stable.
1236  */
1237 static inline
1238 int select_task_rq(struct task_struct *p, int sd_flags, int wake_flags)
1239 {
1240         int cpu = p->sched_class->select_task_rq(p, sd_flags, wake_flags);
1241
1242         /*
1243          * In order not to call set_task_cpu() on a blocking task we need
1244          * to rely on ttwu() to place the task on a valid ->cpus_allowed
1245          * cpu.
1246          *
1247          * Since this is common to all placement strategies, this lives here.
1248          *
1249          * [ this allows ->select_task() to simply return task_cpu(p) and
1250          *   not worry about this generic constraint ]
1251          */
1252         if (unlikely(!cpumask_test_cpu(cpu, tsk_cpus_allowed(p)) ||
1253                      !cpu_online(cpu)))
1254                 cpu = select_fallback_rq(task_cpu(p), p);
1255
1256         return cpu;
1257 }
1258
1259 static void update_avg(u64 *avg, u64 sample)
1260 {
1261         s64 diff = sample - *avg;
1262         *avg += diff >> 3;
1263 }
1264 #endif
1265
1266 static void
1267 ttwu_stat(struct task_struct *p, int cpu, int wake_flags)
1268 {
1269 #ifdef CONFIG_SCHEDSTATS
1270         struct rq *rq = this_rq();
1271
1272 #ifdef CONFIG_SMP
1273         int this_cpu = smp_processor_id();
1274
1275         if (cpu == this_cpu) {
1276                 schedstat_inc(rq, ttwu_local);
1277                 schedstat_inc(p, se.statistics.nr_wakeups_local);
1278         } else {
1279                 struct sched_domain *sd;
1280
1281                 schedstat_inc(p, se.statistics.nr_wakeups_remote);
1282                 rcu_read_lock();
1283                 for_each_domain(this_cpu, sd) {
1284                         if (cpumask_test_cpu(cpu, sched_domain_span(sd))) {
1285                                 schedstat_inc(sd, ttwu_wake_remote);
1286                                 break;
1287                         }
1288                 }
1289                 rcu_read_unlock();
1290         }
1291
1292         if (wake_flags & WF_MIGRATED)
1293                 schedstat_inc(p, se.statistics.nr_wakeups_migrate);
1294
1295 #endif /* CONFIG_SMP */
1296
1297         schedstat_inc(rq, ttwu_count);
1298         schedstat_inc(p, se.statistics.nr_wakeups);
1299
1300         if (wake_flags & WF_SYNC)
1301                 schedstat_inc(p, se.statistics.nr_wakeups_sync);
1302
1303 #endif /* CONFIG_SCHEDSTATS */
1304 }
1305
1306 static void ttwu_activate(struct rq *rq, struct task_struct *p, int en_flags)
1307 {
1308         activate_task(rq, p, en_flags);
1309         p->on_rq = 1;
1310
1311         /* if a worker is waking up, notify workqueue */
1312         if (p->flags & PF_WQ_WORKER)
1313                 wq_worker_waking_up(p, cpu_of(rq));
1314 }
1315
1316 /*
1317  * Mark the task runnable and perform wakeup-preemption.
1318  */
1319 static void
1320 ttwu_do_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
1321 {
1322         check_preempt_curr(rq, p, wake_flags);
1323         trace_sched_wakeup(p, true);
1324
1325         p->state = TASK_RUNNING;
1326 #ifdef CONFIG_SMP
1327         if (p->sched_class->task_woken)
1328                 p->sched_class->task_woken(rq, p);
1329
1330         if (rq->idle_stamp) {
1331                 u64 delta = rq->clock - rq->idle_stamp;
1332                 u64 max = 2*sysctl_sched_migration_cost;
1333
1334                 if (delta > max)
1335                         rq->avg_idle = max;
1336                 else
1337                         update_avg(&rq->avg_idle, delta);
1338                 rq->idle_stamp = 0;
1339         }
1340 #endif
1341 }
1342
1343 static void
1344 ttwu_do_activate(struct rq *rq, struct task_struct *p, int wake_flags)
1345 {
1346 #ifdef CONFIG_SMP
1347         if (p->sched_contributes_to_load)
1348                 rq->nr_uninterruptible--;
1349 #endif
1350
1351         ttwu_activate(rq, p, ENQUEUE_WAKEUP | ENQUEUE_WAKING);
1352         ttwu_do_wakeup(rq, p, wake_flags);
1353 }
1354
1355 /*
1356  * Called in case the task @p isn't fully descheduled from its runqueue,
1357  * in this case we must do a remote wakeup. Its a 'light' wakeup though,
1358  * since all we need to do is flip p->state to TASK_RUNNING, since
1359  * the task is still ->on_rq.
1360  */
1361 static int ttwu_remote(struct task_struct *p, int wake_flags)
1362 {
1363         struct rq *rq;
1364         int ret = 0;
1365
1366         rq = __task_rq_lock(p);
1367         if (p->on_rq) {
1368                 ttwu_do_wakeup(rq, p, wake_flags);
1369                 ret = 1;
1370         }
1371         __task_rq_unlock(rq);
1372
1373         return ret;
1374 }
1375
1376 #ifdef CONFIG_SMP
1377 static void sched_ttwu_pending(void)
1378 {
1379         struct rq *rq = this_rq();
1380         struct llist_node *llist = llist_del_all(&rq->wake_list);
1381         struct task_struct *p;
1382
1383         raw_spin_lock(&rq->lock);
1384
1385         while (llist) {
1386                 p = llist_entry(llist, struct task_struct, wake_entry);
1387                 llist = llist_next(llist);
1388                 ttwu_do_activate(rq, p, 0);
1389         }
1390
1391         raw_spin_unlock(&rq->lock);
1392 }
1393
1394 void scheduler_ipi(void)
1395 {
1396         if (llist_empty(&this_rq()->wake_list) && !got_nohz_idle_kick()
1397             && !tick_nohz_full_cpu(smp_processor_id()))
1398                 return;
1399
1400         /*
1401          * Not all reschedule IPI handlers call irq_enter/irq_exit, since
1402          * traditionally all their work was done from the interrupt return
1403          * path. Now that we actually do some work, we need to make sure
1404          * we do call them.
1405          *
1406          * Some archs already do call them, luckily irq_enter/exit nest
1407          * properly.
1408          *
1409          * Arguably we should visit all archs and update all handlers,
1410          * however a fair share of IPIs are still resched only so this would
1411          * somewhat pessimize the simple resched case.
1412          */
1413         irq_enter();
1414         tick_nohz_full_check();
1415         sched_ttwu_pending();
1416
1417         /*
1418          * Check if someone kicked us for doing the nohz idle load balance.
1419          */
1420         if (unlikely(got_nohz_idle_kick() && !need_resched())) {
1421                 this_rq()->idle_balance = 1;
1422                 raise_softirq_irqoff(SCHED_SOFTIRQ);
1423         }
1424         irq_exit();
1425 }
1426
1427 static void ttwu_queue_remote(struct task_struct *p, int cpu)
1428 {
1429         if (llist_add(&p->wake_entry, &cpu_rq(cpu)->wake_list))
1430                 smp_send_reschedule(cpu);
1431 }
1432
1433 bool cpus_share_cache(int this_cpu, int that_cpu)
1434 {
1435         return per_cpu(sd_llc_id, this_cpu) == per_cpu(sd_llc_id, that_cpu);
1436 }
1437 #endif /* CONFIG_SMP */
1438
1439 static void ttwu_queue(struct task_struct *p, int cpu)
1440 {
1441         struct rq *rq = cpu_rq(cpu);
1442
1443 #if defined(CONFIG_SMP)
1444         if (sched_feat(TTWU_QUEUE) && !cpus_share_cache(smp_processor_id(), cpu)) {
1445                 sched_clock_cpu(cpu); /* sync clocks x-cpu */
1446                 ttwu_queue_remote(p, cpu);
1447                 return;
1448         }
1449 #endif
1450
1451         raw_spin_lock(&rq->lock);
1452         ttwu_do_activate(rq, p, 0);
1453         raw_spin_unlock(&rq->lock);
1454 }
1455
1456 /**
1457  * try_to_wake_up - wake up a thread
1458  * @p: the thread to be awakened
1459  * @state: the mask of task states that can be woken
1460  * @wake_flags: wake modifier flags (WF_*)
1461  *
1462  * Put it on the run-queue if it's not already there. The "current"
1463  * thread is always on the run-queue (except when the actual
1464  * re-schedule is in progress), and as such you're allowed to do
1465  * the simpler "current->state = TASK_RUNNING" to mark yourself
1466  * runnable without the overhead of this.
1467  *
1468  * Returns %true if @p was woken up, %false if it was already running
1469  * or @state didn't match @p's state.
1470  */
1471 static int
1472 try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
1473 {
1474         unsigned long flags;
1475         int cpu, success = 0;
1476
1477         smp_wmb();
1478         raw_spin_lock_irqsave(&p->pi_lock, flags);
1479         if (!(p->state & state))
1480                 goto out;
1481
1482         success = 1; /* we're going to change ->state */
1483         cpu = task_cpu(p);
1484
1485         if (p->on_rq && ttwu_remote(p, wake_flags))
1486                 goto stat;
1487
1488 #ifdef CONFIG_SMP
1489         /*
1490          * If the owning (remote) cpu is still in the middle of schedule() with
1491          * this task as prev, wait until its done referencing the task.
1492          */
1493         while (p->on_cpu)
1494                 cpu_relax();
1495         /*
1496          * Pairs with the smp_wmb() in finish_lock_switch().
1497          */
1498         smp_rmb();
1499
1500         p->sched_contributes_to_load = !!task_contributes_to_load(p);
1501         p->state = TASK_WAKING;
1502
1503         if (p->sched_class->task_waking)
1504                 p->sched_class->task_waking(p);
1505
1506         cpu = select_task_rq(p, SD_BALANCE_WAKE, wake_flags);
1507         if (task_cpu(p) != cpu) {
1508                 wake_flags |= WF_MIGRATED;
1509                 set_task_cpu(p, cpu);
1510         }
1511 #endif /* CONFIG_SMP */
1512
1513         ttwu_queue(p, cpu);
1514 stat:
1515         ttwu_stat(p, cpu, wake_flags);
1516 out:
1517         raw_spin_unlock_irqrestore(&p->pi_lock, flags);
1518
1519         return success;
1520 }
1521
1522 /**
1523  * try_to_wake_up_local - try to wake up a local task with rq lock held
1524  * @p: the thread to be awakened
1525  *
1526  * Put @p on the run-queue if it's not already there. The caller must
1527  * ensure that this_rq() is locked, @p is bound to this_rq() and not
1528  * the current task.
1529  */
1530 static void try_to_wake_up_local(struct task_struct *p)
1531 {
1532         struct rq *rq = task_rq(p);
1533
1534         if (WARN_ON_ONCE(rq != this_rq()) ||
1535             WARN_ON_ONCE(p == current))
1536                 return;
1537
1538         lockdep_assert_held(&rq->lock);
1539
1540         if (!raw_spin_trylock(&p->pi_lock)) {
1541                 raw_spin_unlock(&rq->lock);
1542                 raw_spin_lock(&p->pi_lock);
1543                 raw_spin_lock(&rq->lock);
1544         }
1545
1546         if (!(p->state & TASK_NORMAL))
1547                 goto out;
1548
1549         if (!p->on_rq)
1550                 ttwu_activate(rq, p, ENQUEUE_WAKEUP);
1551
1552         ttwu_do_wakeup(rq, p, 0);
1553         ttwu_stat(p, smp_processor_id(), 0);
1554 out:
1555         raw_spin_unlock(&p->pi_lock);
1556 }
1557
1558 /**
1559  * wake_up_process - Wake up a specific process
1560  * @p: The process to be woken up.
1561  *
1562  * Attempt to wake up the nominated process and move it to the set of runnable
1563  * processes.  Returns 1 if the process was woken up, 0 if it was already
1564  * running.
1565  *
1566  * It may be assumed that this function implies a write memory barrier before
1567  * changing the task state if and only if any tasks are woken up.
1568  */
1569 int wake_up_process(struct task_struct *p)
1570 {
1571         WARN_ON(task_is_stopped_or_traced(p));
1572         return try_to_wake_up(p, TASK_NORMAL, 0);
1573 }
1574 EXPORT_SYMBOL(wake_up_process);
1575
1576 int wake_up_state(struct task_struct *p, unsigned int state)
1577 {
1578         return try_to_wake_up(p, state, 0);
1579 }
1580
1581 /*
1582  * Perform scheduler related setup for a newly forked process p.
1583  * p is forked by current.
1584  *
1585  * __sched_fork() is basic setup used by init_idle() too:
1586  */
1587 static void __sched_fork(struct task_struct *p)
1588 {
1589         p->on_rq                        = 0;
1590
1591         p->se.on_rq                     = 0;
1592         p->se.exec_start                = 0;
1593         p->se.sum_exec_runtime          = 0;
1594         p->se.prev_sum_exec_runtime     = 0;
1595         p->se.nr_migrations             = 0;
1596         p->se.vruntime                  = 0;
1597         INIT_LIST_HEAD(&p->se.group_node);
1598
1599 /*
1600  * Load-tracking only depends on SMP, FAIR_GROUP_SCHED dependency below may be
1601  * removed when useful for applications beyond shares distribution (e.g.
1602  * load-balance).
1603  */
1604 #if defined(CONFIG_SMP) && defined(CONFIG_FAIR_GROUP_SCHED)
1605         p->se.avg.runnable_avg_period = 0;
1606         p->se.avg.runnable_avg_sum = 0;
1607 #endif
1608 #ifdef CONFIG_SCHEDSTATS
1609         memset(&p->se.statistics, 0, sizeof(p->se.statistics));
1610 #endif
1611
1612         INIT_LIST_HEAD(&p->rt.run_list);
1613
1614 #ifdef CONFIG_PREEMPT_NOTIFIERS
1615         INIT_HLIST_HEAD(&p->preempt_notifiers);
1616 #endif
1617
1618 #ifdef CONFIG_NUMA_BALANCING
1619         if (p->mm && atomic_read(&p->mm->mm_users) == 1) {
1620                 p->mm->numa_next_scan = jiffies;
1621                 p->mm->numa_next_reset = jiffies;
1622                 p->mm->numa_scan_seq = 0;
1623         }
1624
1625         p->node_stamp = 0ULL;
1626         p->numa_scan_seq = p->mm ? p->mm->numa_scan_seq : 0;
1627         p->numa_migrate_seq = p->mm ? p->mm->numa_scan_seq - 1 : 0;
1628         p->numa_scan_period = sysctl_numa_balancing_scan_delay;
1629         p->numa_work.next = &p->numa_work;
1630 #endif /* CONFIG_NUMA_BALANCING */
1631 }
1632
1633 #ifdef CONFIG_NUMA_BALANCING
1634 #ifdef CONFIG_SCHED_DEBUG
1635 void set_numabalancing_state(bool enabled)
1636 {
1637         if (enabled)
1638                 sched_feat_set("NUMA");
1639         else
1640                 sched_feat_set("NO_NUMA");
1641 }
1642 #else
1643 __read_mostly bool numabalancing_enabled;
1644
1645 void set_numabalancing_state(bool enabled)
1646 {
1647         numabalancing_enabled = enabled;
1648 }
1649 #endif /* CONFIG_SCHED_DEBUG */
1650 #endif /* CONFIG_NUMA_BALANCING */
1651
1652 /*
1653  * fork()/clone()-time setup:
1654  */
1655 void sched_fork(struct task_struct *p)
1656 {
1657         unsigned long flags;
1658         int cpu = get_cpu();
1659
1660         __sched_fork(p);
1661         /*
1662          * We mark the process as running here. This guarantees that
1663          * nobody will actually run it, and a signal or other external
1664          * event cannot wake it up and insert it on the runqueue either.
1665          */
1666         p->state = TASK_RUNNING;
1667
1668         /*
1669          * Make sure we do not leak PI boosting priority to the child.
1670          */
1671         p->prio = current->normal_prio;
1672
1673         /*
1674          * Revert to default priority/policy on fork if requested.
1675          */
1676         if (unlikely(p->sched_reset_on_fork)) {
1677                 if (task_has_rt_policy(p)) {
1678                         p->policy = SCHED_NORMAL;
1679                         p->static_prio = NICE_TO_PRIO(0);
1680                         p->rt_priority = 0;
1681                 } else if (PRIO_TO_NICE(p->static_prio) < 0)
1682                         p->static_prio = NICE_TO_PRIO(0);
1683
1684                 p->prio = p->normal_prio = __normal_prio(p);
1685                 set_load_weight(p);
1686
1687                 /*
1688                  * We don't need the reset flag anymore after the fork. It has
1689                  * fulfilled its duty:
1690                  */
1691                 p->sched_reset_on_fork = 0;
1692         }
1693
1694         if (!rt_prio(p->prio))
1695                 p->sched_class = &fair_sched_class;
1696
1697         if (p->sched_class->task_fork)
1698                 p->sched_class->task_fork(p);
1699
1700         /*
1701          * The child is not yet in the pid-hash so no cgroup attach races,
1702          * and the cgroup is pinned to this child due to cgroup_fork()
1703          * is ran before sched_fork().
1704          *
1705          * Silence PROVE_RCU.
1706          */
1707         raw_spin_lock_irqsave(&p->pi_lock, flags);
1708         set_task_cpu(p, cpu);
1709         raw_spin_unlock_irqrestore(&p->pi_lock, flags);
1710
1711 #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
1712         if (likely(sched_info_on()))
1713                 memset(&p->sched_info, 0, sizeof(p->sched_info));
1714 #endif
1715 #if defined(CONFIG_SMP)
1716         p->on_cpu = 0;
1717 #endif
1718 #ifdef CONFIG_PREEMPT_COUNT
1719         /* Want to start with kernel preemption disabled. */
1720         task_thread_info(p)->preempt_count = 1;
1721 #endif
1722 #ifdef CONFIG_SMP
1723         plist_node_init(&p->pushable_tasks, MAX_PRIO);
1724 #endif
1725
1726         put_cpu();
1727 }
1728
1729 /*
1730  * wake_up_new_task - wake up a newly created task for the first time.
1731  *
1732  * This function will do some initial scheduler statistics housekeeping
1733  * that must be done for every newly created context, then puts the task
1734  * on the runqueue and wakes it.
1735  */
1736 void wake_up_new_task(struct task_struct *p)
1737 {
1738         unsigned long flags;
1739         struct rq *rq;
1740
1741         raw_spin_lock_irqsave(&p->pi_lock, flags);
1742 #ifdef CONFIG_SMP
1743         /*
1744          * Fork balancing, do it here and not earlier because:
1745          *  - cpus_allowed can change in the fork path
1746          *  - any previously selected cpu might disappear through hotplug
1747          */
1748         set_task_cpu(p, select_task_rq(p, SD_BALANCE_FORK, 0));
1749 #endif
1750
1751         rq = __task_rq_lock(p);
1752         activate_task(rq, p, 0);
1753         p->on_rq = 1;
1754         trace_sched_wakeup_new(p, true);
1755         check_preempt_curr(rq, p, WF_FORK);
1756 #ifdef CONFIG_SMP
1757         if (p->sched_class->task_woken)
1758                 p->sched_class->task_woken(rq, p);
1759 #endif
1760         task_rq_unlock(rq, p, &flags);
1761 }
1762
1763 #ifdef CONFIG_PREEMPT_NOTIFIERS
1764
1765 /**
1766  * preempt_notifier_register - tell me when current is being preempted & rescheduled
1767  * @notifier: notifier struct to register
1768  */
1769 void preempt_notifier_register(struct preempt_notifier *notifier)
1770 {
1771         hlist_add_head(&notifier->link, &current->preempt_notifiers);
1772 }
1773 EXPORT_SYMBOL_GPL(preempt_notifier_register);
1774
1775 /**
1776  * preempt_notifier_unregister - no longer interested in preemption notifications
1777  * @notifier: notifier struct to unregister
1778  *
1779  * This is safe to call from within a preemption notifier.
1780  */
1781 void preempt_notifier_unregister(struct preempt_notifier *notifier)
1782 {
1783         hlist_del(&notifier->link);
1784 }
1785 EXPORT_SYMBOL_GPL(preempt_notifier_unregister);
1786
1787 static void fire_sched_in_preempt_notifiers(struct task_struct *curr)
1788 {
1789         struct preempt_notifier *notifier;
1790
1791         hlist_for_each_entry(notifier, &curr->preempt_notifiers, link)
1792                 notifier->ops->sched_in(notifier, raw_smp_processor_id());
1793 }
1794
1795 static void
1796 fire_sched_out_preempt_notifiers(struct task_struct *curr,
1797                                  struct task_struct *next)
1798 {
1799         struct preempt_notifier *notifier;
1800
1801         hlist_for_each_entry(notifier, &curr->preempt_notifiers, link)
1802                 notifier->ops->sched_out(notifier, next);
1803 }
1804
1805 #else /* !CONFIG_PREEMPT_NOTIFIERS */
1806
1807 static void fire_sched_in_preempt_notifiers(struct task_struct *curr)
1808 {
1809 }
1810
1811 static void
1812 fire_sched_out_preempt_notifiers(struct task_struct *curr,
1813                                  struct task_struct *next)
1814 {
1815 }
1816
1817 #endif /* CONFIG_PREEMPT_NOTIFIERS */
1818
1819 /**
1820  * prepare_task_switch - prepare to switch tasks
1821  * @rq: the runqueue preparing to switch
1822  * @prev: the current task that is being switched out
1823  * @next: the task we are going to switch to.
1824  *
1825  * This is called with the rq lock held and interrupts off. It must
1826  * be paired with a subsequent finish_task_switch after the context
1827  * switch.
1828  *
1829  * prepare_task_switch sets up locking and calls architecture specific
1830  * hooks.
1831  */
1832 static inline void
1833 prepare_task_switch(struct rq *rq, struct task_struct *prev,
1834                     struct task_struct *next)
1835 {
1836         trace_sched_switch(prev, next);
1837         sched_info_switch(prev, next);
1838         perf_event_task_sched_out(prev, next);
1839         fire_sched_out_preempt_notifiers(prev, next);
1840         prepare_lock_switch(rq, next);
1841         prepare_arch_switch(next);
1842 }
1843
1844 /**
1845  * finish_task_switch - clean up after a task-switch
1846  * @rq: runqueue associated with task-switch
1847  * @prev: the thread we just switched away from.
1848  *
1849  * finish_task_switch must be called after the context switch, paired
1850  * with a prepare_task_switch call before the context switch.
1851  * finish_task_switch will reconcile locking set up by prepare_task_switch,
1852  * and do any other architecture-specific cleanup actions.
1853  *
1854  * Note that we may have delayed dropping an mm in context_switch(). If
1855  * so, we finish that here outside of the runqueue lock. (Doing it
1856  * with the lock held can cause deadlocks; see schedule() for
1857  * details.)
1858  */
1859 static void finish_task_switch(struct rq *rq, struct task_struct *prev)
1860         __releases(rq->lock)
1861 {
1862         struct mm_struct *mm = rq->prev_mm;
1863         long prev_state;
1864
1865         rq->prev_mm = NULL;
1866
1867         /*
1868          * A task struct has one reference for the use as "current".
1869          * If a task dies, then it sets TASK_DEAD in tsk->state and calls
1870          * schedule one last time. The schedule call will never return, and
1871          * the scheduled task must drop that reference.
1872          * The test for TASK_DEAD must occur while the runqueue locks are
1873          * still held, otherwise prev could be scheduled on another cpu, die
1874          * there before we look at prev->state, and then the reference would
1875          * be dropped twice.
1876          *              Manfred Spraul <manfred@colorfullife.com>
1877          */
1878         prev_state = prev->state;
1879         vtime_task_switch(prev);
1880         finish_arch_switch(prev);
1881         perf_event_task_sched_in(prev, current);
1882         finish_lock_switch(rq, prev);
1883         finish_arch_post_lock_switch();
1884
1885         fire_sched_in_preempt_notifiers(current);
1886         if (mm)
1887                 mmdrop(mm);
1888         if (unlikely(prev_state == TASK_DEAD)) {
1889                 /*
1890                  * Remove function-return probe instances associated with this
1891                  * task and put them back on the free list.
1892                  */
1893                 kprobe_flush_task(prev);
1894                 put_task_struct(prev);
1895         }
1896
1897         tick_nohz_task_switch(current);
1898 }
1899
1900 #ifdef CONFIG_SMP
1901
1902 /* assumes rq->lock is held */
1903 static inline void pre_schedule(struct rq *rq, struct task_struct *prev)
1904 {
1905         if (prev->sched_class->pre_schedule)
1906                 prev->sched_class->pre_schedule(rq, prev);
1907 }
1908
1909 /* rq->lock is NOT held, but preemption is disabled */
1910 static inline void post_schedule(struct rq *rq)
1911 {
1912         if (rq->post_schedule) {
1913                 unsigned long flags;
1914
1915                 raw_spin_lock_irqsave(&rq->lock, flags);
1916                 if (rq->curr->sched_class->post_schedule)
1917                         rq->curr->sched_class->post_schedule(rq);
1918                 raw_spin_unlock_irqrestore(&rq->lock, flags);
1919
1920                 rq->post_schedule = 0;
1921         }
1922 }
1923
1924 #else
1925
1926 static inline void pre_schedule(struct rq *rq, struct task_struct *p)
1927 {
1928 }
1929
1930 static inline void post_schedule(struct rq *rq)
1931 {
1932 }
1933
1934 #endif
1935
1936 /**
1937  * schedule_tail - first thing a freshly forked thread must call.
1938  * @prev: the thread we just switched away from.
1939  */
1940 asmlinkage void schedule_tail(struct task_struct *prev)
1941         __releases(rq->lock)
1942 {
1943         struct rq *rq = this_rq();
1944
1945         finish_task_switch(rq, prev);
1946
1947         /*
1948          * FIXME: do we need to worry about rq being invalidated by the
1949          * task_switch?
1950          */
1951         post_schedule(rq);
1952
1953 #ifdef __ARCH_WANT_UNLOCKED_CTXSW
1954         /* In this case, finish_task_switch does not reenable preemption */
1955         preempt_enable();
1956 #endif
1957         if (current->set_child_tid)
1958                 put_user(task_pid_vnr(current), current->set_child_tid);
1959 }
1960
1961 /*
1962  * context_switch - switch to the new MM and the new
1963  * thread's register state.
1964  */
1965 static inline void
1966 context_switch(struct rq *rq, struct task_struct *prev,
1967                struct task_struct *next)
1968 {
1969         struct mm_struct *mm, *oldmm;
1970
1971         prepare_task_switch(rq, prev, next);
1972
1973         mm = next->mm;
1974         oldmm = prev->active_mm;
1975         /*
1976          * For paravirt, this is coupled with an exit in switch_to to
1977          * combine the page table reload and the switch backend into
1978          * one hypercall.
1979          */
1980         arch_start_context_switch(prev);
1981
1982         if (!mm) {
1983                 next->active_mm = oldmm;
1984                 atomic_inc(&oldmm->mm_count);
1985                 enter_lazy_tlb(oldmm, next);
1986         } else
1987                 switch_mm(oldmm, mm, next);
1988
1989         if (!prev->mm) {
1990                 prev->active_mm = NULL;
1991                 rq->prev_mm = oldmm;
1992         }
1993         /*
1994          * Since the runqueue lock will be released by the next
1995          * task (which is an invalid locking op but in the case
1996          * of the scheduler it's an obvious special-case), so we
1997          * do an early lockdep release here:
1998          */
1999 #ifndef __ARCH_WANT_UNLOCKED_CTXSW
2000         spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
2001 #endif
2002
2003         context_tracking_task_switch(prev, next);
2004         /* Here we just switch the register state and the stack. */
2005         switch_to(prev, next, prev);
2006
2007         barrier();
2008         /*
2009          * this_rq must be evaluated again because prev may have moved
2010          * CPUs since it called schedule(), thus the 'rq' on its stack
2011          * frame will be invalid.
2012          */
2013         finish_task_switch(this_rq(), prev);
2014 }
2015
2016 /*
2017  * nr_running and nr_context_switches:
2018  *
2019  * externally visible scheduler statistics: current number of runnable
2020  * threads, total number of context switches performed since bootup.
2021  */
2022 unsigned long nr_running(void)
2023 {
2024         unsigned long i, sum = 0;
2025
2026         for_each_online_cpu(i)
2027                 sum += cpu_rq(i)->nr_running;
2028
2029         return sum;
2030 }
2031
2032 unsigned long long nr_context_switches(void)
2033 {
2034         int i;
2035         unsigned long long sum = 0;
2036
2037         for_each_possible_cpu(i)
2038                 sum += cpu_rq(i)->nr_switches;
2039
2040         return sum;
2041 }
2042
2043 unsigned long nr_iowait(void)
2044 {
2045         unsigned long i, sum = 0;
2046
2047         for_each_possible_cpu(i)
2048                 sum += atomic_read(&cpu_rq(i)->nr_iowait);
2049
2050         return sum;
2051 }
2052
2053 unsigned long nr_iowait_cpu(int cpu)
2054 {
2055         struct rq *this = cpu_rq(cpu);
2056         return atomic_read(&this->nr_iowait);
2057 }
2058
2059 unsigned long this_cpu_load(void)
2060 {
2061         struct rq *this = this_rq();
2062         return this->cpu_load[0];
2063 }
2064
2065
2066 /*
2067  * Global load-average calculations
2068  *
2069  * We take a distributed and async approach to calculating the global load-avg
2070  * in order to minimize overhead.
2071  *
2072  * The global load average is an exponentially decaying average of nr_running +
2073  * nr_uninterruptible.
2074  *
2075  * Once every LOAD_FREQ:
2076  *
2077  *   nr_active = 0;
2078  *   for_each_possible_cpu(cpu)
2079  *      nr_active += cpu_of(cpu)->nr_running + cpu_of(cpu)->nr_uninterruptible;
2080  *
2081  *   avenrun[n] = avenrun[0] * exp_n + nr_active * (1 - exp_n)
2082  *
2083  * Due to a number of reasons the above turns in the mess below:
2084  *
2085  *  - for_each_possible_cpu() is prohibitively expensive on machines with
2086  *    serious number of cpus, therefore we need to take a distributed approach
2087  *    to calculating nr_active.
2088  *
2089  *        \Sum_i x_i(t) = \Sum_i x_i(t) - x_i(t_0) | x_i(t_0) := 0
2090  *                      = \Sum_i { \Sum_j=1 x_i(t_j) - x_i(t_j-1) }
2091  *
2092  *    So assuming nr_active := 0 when we start out -- true per definition, we
2093  *    can simply take per-cpu deltas and fold those into a global accumulate
2094  *    to obtain the same result. See calc_load_fold_active().
2095  *
2096  *    Furthermore, in order to avoid synchronizing all per-cpu delta folding
2097  *    across the machine, we assume 10 ticks is sufficient time for every
2098  *    cpu to have completed this task.
2099  *
2100  *    This places an upper-bound on the IRQ-off latency of the machine. Then
2101  *    again, being late doesn't loose the delta, just wrecks the sample.
2102  *
2103  *  - cpu_rq()->nr_uninterruptible isn't accurately tracked per-cpu because
2104  *    this would add another cross-cpu cacheline miss and atomic operation
2105  *    to the wakeup path. Instead we increment on whatever cpu the task ran
2106  *    when it went into uninterruptible state and decrement on whatever cpu
2107  *    did the wakeup. This means that only the sum of nr_uninterruptible over
2108  *    all cpus yields the correct result.
2109  *
2110  *  This covers the NO_HZ=n code, for extra head-aches, see the comment below.
2111  */
2112
2113 /* Variables and functions for calc_load */
2114 static atomic_long_t calc_load_tasks;
2115 static unsigned long calc_load_update;
2116 unsigned long avenrun[3];
2117 EXPORT_SYMBOL(avenrun); /* should be removed */
2118
2119 /**
2120  * get_avenrun - get the load average array
2121  * @loads:      pointer to dest load array
2122  * @offset:     offset to add
2123  * @shift:      shift count to shift the result left
2124  *
2125  * These values are estimates at best, so no need for locking.
2126  */
2127 void get_avenrun(unsigned long *loads, unsigned long offset, int shift)
2128 {
2129         loads[0] = (avenrun[0] + offset) << shift;
2130         loads[1] = (avenrun[1] + offset) << shift;
2131         loads[2] = (avenrun[2] + offset) << shift;
2132 }
2133
2134 static long calc_load_fold_active(struct rq *this_rq)
2135 {
2136         long nr_active, delta = 0;
2137
2138         nr_active = this_rq->nr_running;
2139         nr_active += (long) this_rq->nr_uninterruptible;
2140
2141         if (nr_active != this_rq->calc_load_active) {
2142                 delta = nr_active - this_rq->calc_load_active;
2143                 this_rq->calc_load_active = nr_active;
2144         }
2145
2146         return delta;
2147 }
2148
2149 /*
2150  * a1 = a0 * e + a * (1 - e)
2151  */
2152 static unsigned long
2153 calc_load(unsigned long load, unsigned long exp, unsigned long active)
2154 {
2155         load *= exp;
2156         load += active * (FIXED_1 - exp);
2157         load += 1UL << (FSHIFT - 1);
2158         return load >> FSHIFT;
2159 }
2160
2161 #ifdef CONFIG_NO_HZ_COMMON
2162 /*
2163  * Handle NO_HZ for the global load-average.
2164  *
2165  * Since the above described distributed algorithm to compute the global
2166  * load-average relies on per-cpu sampling from the tick, it is affected by
2167  * NO_HZ.
2168  *
2169  * The basic idea is to fold the nr_active delta into a global idle-delta upon
2170  * entering NO_HZ state such that we can include this as an 'extra' cpu delta
2171  * when we read the global state.
2172  *
2173  * Obviously reality has to ruin such a delightfully simple scheme:
2174  *
2175  *  - When we go NO_HZ idle during the window, we can negate our sample
2176  *    contribution, causing under-accounting.
2177  *
2178  *    We avoid this by keeping two idle-delta counters and flipping them
2179  *    when the window starts, thus separating old and new NO_HZ load.
2180  *
2181  *    The only trick is the slight shift in index flip for read vs write.
2182  *
2183  *        0s            5s            10s           15s
2184  *          +10           +10           +10           +10
2185  *        |-|-----------|-|-----------|-|-----------|-|
2186  *    r:0 0 1           1 0           0 1           1 0
2187  *    w:0 1 1           0 0           1 1           0 0
2188  *
2189  *    This ensures we'll fold the old idle contribution in this window while
2190  *    accumlating the new one.
2191  *
2192  *  - When we wake up from NO_HZ idle during the window, we push up our
2193  *    contribution, since we effectively move our sample point to a known
2194  *    busy state.
2195  *
2196  *    This is solved by pushing the window forward, and thus skipping the
2197  *    sample, for this cpu (effectively using the idle-delta for this cpu which
2198  *    was in effect at the time the window opened). This also solves the issue
2199  *    of having to deal with a cpu having been in NOHZ idle for multiple
2200  *    LOAD_FREQ intervals.
2201  *
2202  * When making the ILB scale, we should try to pull this in as well.
2203  */
2204 static atomic_long_t calc_load_idle[2];
2205 static int calc_load_idx;
2206
2207 static inline int calc_load_write_idx(void)
2208 {
2209         int idx = calc_load_idx;
2210
2211         /*
2212          * See calc_global_nohz(), if we observe the new index, we also
2213          * need to observe the new update time.
2214          */
2215         smp_rmb();
2216
2217         /*
2218          * If the folding window started, make sure we start writing in the
2219          * next idle-delta.
2220          */
2221         if (!time_before(jiffies, calc_load_update))
2222                 idx++;
2223
2224         return idx & 1;
2225 }
2226
2227 static inline int calc_load_read_idx(void)
2228 {
2229         return calc_load_idx & 1;
2230 }
2231
2232 void calc_load_enter_idle(void)
2233 {
2234         struct rq *this_rq = this_rq();
2235         long delta;
2236
2237         /*
2238          * We're going into NOHZ mode, if there's any pending delta, fold it
2239          * into the pending idle delta.
2240          */
2241         delta = calc_load_fold_active(this_rq);
2242         if (delta) {
2243                 int idx = calc_load_write_idx();
2244                 atomic_long_add(delta, &calc_load_idle[idx]);
2245         }
2246 }
2247
2248 void calc_load_exit_idle(void)
2249 {
2250         struct rq *this_rq = this_rq();
2251
2252         /*
2253          * If we're still before the sample window, we're done.
2254          */
2255         if (time_before(jiffies, this_rq->calc_load_update))
2256                 return;
2257
2258         /*
2259          * We woke inside or after the sample window, this means we're already
2260          * accounted through the nohz accounting, so skip the entire deal and
2261          * sync up for the next window.
2262          */
2263         this_rq->calc_load_update = calc_load_update;
2264         if (time_before(jiffies, this_rq->calc_load_update + 10))
2265                 this_rq->calc_load_update += LOAD_FREQ;
2266 }
2267
2268 static long calc_load_fold_idle(void)
2269 {
2270         int idx = calc_load_read_idx();
2271         long delta = 0;
2272
2273         if (atomic_long_read(&calc_load_idle[idx]))
2274                 delta = atomic_long_xchg(&calc_load_idle[idx], 0);
2275
2276         return delta;
2277 }
2278
2279 /**
2280  * fixed_power_int - compute: x^n, in O(log n) time
2281  *
2282  * @x:         base of the power
2283  * @frac_bits: fractional bits of @x
2284  * @n:         power to raise @x to.
2285  *
2286  * By exploiting the relation between the definition of the natural power
2287  * function: x^n := x*x*...*x (x multiplied by itself for n times), and
2288  * the binary encoding of numbers used by computers: n := \Sum n_i * 2^i,
2289  * (where: n_i \elem {0, 1}, the binary vector representing n),
2290  * we find: x^n := x^(\Sum n_i * 2^i) := \Prod x^(n_i * 2^i), which is
2291  * of course trivially computable in O(log_2 n), the length of our binary
2292  * vector.
2293  */
2294 static unsigned long
2295 fixed_power_int(unsigned long x, unsigned int frac_bits, unsigned int n)
2296 {
2297         unsigned long result = 1UL << frac_bits;
2298
2299         if (n) for (;;) {
2300                 if (n & 1) {
2301                         result *= x;
2302                         result += 1UL << (frac_bits - 1);
2303                         result >>= frac_bits;
2304                 }
2305                 n >>= 1;
2306                 if (!n)
2307                         break;
2308                 x *= x;
2309                 x += 1UL << (frac_bits - 1);
2310                 x >>= frac_bits;
2311         }
2312
2313         return result;
2314 }
2315
2316 /*
2317  * a1 = a0 * e + a * (1 - e)
2318  *
2319  * a2 = a1 * e + a * (1 - e)
2320  *    = (a0 * e + a * (1 - e)) * e + a * (1 - e)
2321  *    = a0 * e^2 + a * (1 - e) * (1 + e)
2322  *
2323  * a3 = a2 * e + a * (1 - e)
2324  *    = (a0 * e^2 + a * (1 - e) * (1 + e)) * e + a * (1 - e)
2325  *    = a0 * e^3 + a * (1 - e) * (1 + e + e^2)
2326  *
2327  *  ...
2328  *
2329  * an = a0 * e^n + a * (1 - e) * (1 + e + ... + e^n-1) [1]
2330  *    = a0 * e^n + a * (1 - e) * (1 - e^n)/(1 - e)
2331  *    = a0 * e^n + a * (1 - e^n)
2332  *
2333  * [1] application of the geometric series:
2334  *
2335  *              n         1 - x^(n+1)
2336  *     S_n := \Sum x^i = -------------
2337  *             i=0          1 - x
2338  */
2339 static unsigned long
2340 calc_load_n(unsigned long load, unsigned long exp,
2341             unsigned long active, unsigned int n)
2342 {
2343
2344         return calc_load(load, fixed_power_int(exp, FSHIFT, n), active);
2345 }
2346
2347 /*
2348  * NO_HZ can leave us missing all per-cpu ticks calling
2349  * calc_load_account_active(), but since an idle CPU folds its delta into
2350  * calc_load_tasks_idle per calc_load_account_idle(), all we need to do is fold
2351  * in the pending idle delta if our idle period crossed a load cycle boundary.
2352  *
2353  * Once we've updated the global active value, we need to apply the exponential
2354  * weights adjusted to the number of cycles missed.
2355  */
2356 static void calc_global_nohz(void)
2357 {
2358         long delta, active, n;
2359
2360         if (!time_before(jiffies, calc_load_update + 10)) {
2361                 /*
2362                  * Catch-up, fold however many we are behind still
2363                  */
2364                 delta = jiffies - calc_load_update - 10;
2365                 n = 1 + (delta / LOAD_FREQ);
2366
2367                 active = atomic_long_read(&calc_load_tasks);
2368                 active = active > 0 ? active * FIXED_1 : 0;
2369
2370                 avenrun[0] = calc_load_n(avenrun[0], EXP_1, active, n);
2371                 avenrun[1] = calc_load_n(avenrun[1], EXP_5, active, n);
2372                 avenrun[2] = calc_load_n(avenrun[2], EXP_15, active, n);
2373
2374                 calc_load_update += n * LOAD_FREQ;
2375         }
2376
2377         /*
2378          * Flip the idle index...
2379          *
2380          * Make sure we first write the new time then flip the index, so that
2381          * calc_load_write_idx() will see the new time when it reads the new
2382          * index, this avoids a double flip messing things up.
2383          */
2384         smp_wmb();
2385         calc_load_idx++;
2386 }
2387 #else /* !CONFIG_NO_HZ_COMMON */
2388
2389 static inline long calc_load_fold_idle(void) { return 0; }
2390 static inline void calc_global_nohz(void) { }
2391
2392 #endif /* CONFIG_NO_HZ_COMMON */
2393
2394 /*
2395  * calc_load - update the avenrun load estimates 10 ticks after the
2396  * CPUs have updated calc_load_tasks.
2397  */
2398 void calc_global_load(unsigned long ticks)
2399 {
2400         long active, delta;
2401
2402         if (time_before(jiffies, calc_load_update + 10))
2403                 return;
2404
2405         /*
2406          * Fold the 'old' idle-delta to include all NO_HZ cpus.
2407          */
2408         delta = calc_load_fold_idle();
2409         if (delta)
2410                 atomic_long_add(delta, &calc_load_tasks);
2411
2412         active = atomic_long_read(&calc_load_tasks);
2413         active = active > 0 ? active * FIXED_1 : 0;
2414
2415         avenrun[0] = calc_load(avenrun[0], EXP_1, active);
2416         avenrun[1] = calc_load(avenrun[1], EXP_5, active);
2417         avenrun[2] = calc_load(avenrun[2], EXP_15, active);
2418
2419         calc_load_update += LOAD_FREQ;
2420
2421         /*
2422          * In case we idled for multiple LOAD_FREQ intervals, catch up in bulk.
2423          */
2424         calc_global_nohz();
2425 }
2426
2427 /*
2428  * Called from update_cpu_load() to periodically update this CPU's
2429  * active count.
2430  */
2431 static void calc_load_account_active(struct rq *this_rq)
2432 {
2433         long delta;
2434
2435         if (time_before(jiffies, this_rq->calc_load_update))
2436                 return;
2437
2438         delta  = calc_load_fold_active(this_rq);
2439         if (delta)
2440                 atomic_long_add(delta, &calc_load_tasks);
2441
2442         this_rq->calc_load_update += LOAD_FREQ;
2443 }
2444
2445 /*
2446  * End of global load-average stuff
2447  */
2448
2449 /*
2450  * The exact cpuload at various idx values, calculated at every tick would be
2451  * load = (2^idx - 1) / 2^idx * load + 1 / 2^idx * cur_load
2452  *
2453  * If a cpu misses updates for n-1 ticks (as it was idle) and update gets called
2454  * on nth tick when cpu may be busy, then we have:
2455  * load = ((2^idx - 1) / 2^idx)^(n-1) * load
2456  * load = (2^idx - 1) / 2^idx) * load + 1 / 2^idx * cur_load
2457  *
2458  * decay_load_missed() below does efficient calculation of
2459  * load = ((2^idx - 1) / 2^idx)^(n-1) * load
2460  * avoiding 0..n-1 loop doing load = ((2^idx - 1) / 2^idx) * load
2461  *
2462  * The calculation is approximated on a 128 point scale.
2463  * degrade_zero_ticks is the number of ticks after which load at any
2464  * particular idx is approximated to be zero.
2465  * degrade_factor is a precomputed table, a row for each load idx.
2466  * Each column corresponds to degradation factor for a power of two ticks,
2467  * based on 128 point scale.
2468  * Example:
2469  * row 2, col 3 (=12) says that the degradation at load idx 2 after
2470  * 8 ticks is 12/128 (which is an approximation of exact factor 3^8/4^8).
2471  *
2472  * With this power of 2 load factors, we can degrade the load n times
2473  * by looking at 1 bits in n and doing as many mult/shift instead of
2474  * n mult/shifts needed by the exact degradation.
2475  */
2476 #define DEGRADE_SHIFT           7
2477 static const unsigned char
2478                 degrade_zero_ticks[CPU_LOAD_IDX_MAX] = {0, 8, 32, 64, 128};
2479 static const unsigned char
2480                 degrade_factor[CPU_LOAD_IDX_MAX][DEGRADE_SHIFT + 1] = {
2481                                         {0, 0, 0, 0, 0, 0, 0, 0},
2482                                         {64, 32, 8, 0, 0, 0, 0, 0},
2483                                         {96, 72, 40, 12, 1, 0, 0},
2484                                         {112, 98, 75, 43, 15, 1, 0},
2485                                         {120, 112, 98, 76, 45, 16, 2} };
2486
2487 /*
2488  * Update cpu_load for any missed ticks, due to tickless idle. The backlog
2489  * would be when CPU is idle and so we just decay the old load without
2490  * adding any new load.
2491  */
2492 static unsigned long
2493 decay_load_missed(unsigned long load, unsigned long missed_updates, int idx)
2494 {
2495         int j = 0;
2496
2497         if (!missed_updates)
2498                 return load;
2499
2500         if (missed_updates >= degrade_zero_ticks[idx])
2501                 return 0;
2502
2503         if (idx == 1)
2504                 return load >> missed_updates;
2505
2506         while (missed_updates) {
2507                 if (missed_updates % 2)
2508                         load = (load * degrade_factor[idx][j]) >> DEGRADE_SHIFT;
2509
2510                 missed_updates >>= 1;
2511                 j++;
2512         }
2513         return load;
2514 }
2515
2516 /*
2517  * Update rq->cpu_load[] statistics. This function is usually called every
2518  * scheduler tick (TICK_NSEC). With tickless idle this will not be called
2519  * every tick. We fix it up based on jiffies.
2520  */
2521 static void __update_cpu_load(struct rq *this_rq, unsigned long this_load,
2522                               unsigned long pending_updates)
2523 {
2524         int i, scale;
2525
2526         this_rq->nr_load_updates++;
2527
2528         /* Update our load: */
2529         this_rq->cpu_load[0] = this_load; /* Fasttrack for idx 0 */
2530         for (i = 1, scale = 2; i < CPU_LOAD_IDX_MAX; i++, scale += scale) {
2531                 unsigned long old_load, new_load;
2532
2533                 /* scale is effectively 1 << i now, and >> i divides by scale */
2534
2535                 old_load = this_rq->cpu_load[i];
2536                 old_load = decay_load_missed(old_load, pending_updates - 1, i);
2537                 new_load = this_load;
2538                 /*
2539                  * Round up the averaging division if load is increasing. This
2540                  * prevents us from getting stuck on 9 if the load is 10, for
2541                  * example.
2542                  */
2543                 if (new_load > old_load)
2544                         new_load += scale - 1;
2545
2546                 this_rq->cpu_load[i] = (old_load * (scale - 1) + new_load) >> i;
2547         }
2548
2549         sched_avg_update(this_rq);
2550 }
2551
2552 #ifdef CONFIG_NO_HZ_COMMON
2553 /*
2554  * There is no sane way to deal with nohz on smp when using jiffies because the
2555  * cpu doing the jiffies update might drift wrt the cpu doing the jiffy reading
2556  * causing off-by-one errors in observed deltas; {0,2} instead of {1,1}.
2557  *
2558  * Therefore we cannot use the delta approach from the regular tick since that
2559  * would seriously skew the load calculation. However we'll make do for those
2560  * updates happening while idle (nohz_idle_balance) or coming out of idle
2561  * (tick_nohz_idle_exit).
2562  *
2563  * This means we might still be one tick off for nohz periods.
2564  */
2565
2566 /*
2567  * Called from nohz_idle_balance() to update the load ratings before doing the
2568  * idle balance.
2569  */
2570 void update_idle_cpu_load(struct rq *this_rq)
2571 {
2572         unsigned long curr_jiffies = ACCESS_ONCE(jiffies);
2573         unsigned long load = this_rq->load.weight;
2574         unsigned long pending_updates;
2575
2576         /*
2577          * bail if there's load or we're actually up-to-date.
2578          */
2579         if (load || curr_jiffies == this_rq->last_load_update_tick)
2580                 return;
2581
2582         pending_updates = curr_jiffies - this_rq->last_load_update_tick;
2583         this_rq->last_load_update_tick = curr_jiffies;
2584
2585         __update_cpu_load(this_rq, load, pending_updates);
2586 }
2587
2588 /*
2589  * Called from tick_nohz_idle_exit() -- try and fix up the ticks we missed.
2590  */
2591 void update_cpu_load_nohz(void)
2592 {
2593         struct rq *this_rq = this_rq();
2594         unsigned long curr_jiffies = ACCESS_ONCE(jiffies);
2595         unsigned long pending_updates;
2596
2597         if (curr_jiffies == this_rq->last_load_update_tick)
2598                 return;
2599
2600         raw_spin_lock(&this_rq->lock);
2601         pending_updates = curr_jiffies - this_rq->last_load_update_tick;
2602         if (pending_updates) {
2603                 this_rq->last_load_update_tick = curr_jiffies;
2604                 /*
2605                  * We were idle, this means load 0, the current load might be
2606                  * !0 due to remote wakeups and the sort.
2607                  */
2608                 __update_cpu_load(this_rq, 0, pending_updates);
2609         }
2610         raw_spin_unlock(&this_rq->lock);
2611 }
2612 #endif /* CONFIG_NO_HZ_COMMON */
2613
2614 /*
2615  * Called from scheduler_tick()
2616  */
2617 static void update_cpu_load_active(struct rq *this_rq)
2618 {
2619         /*
2620          * See the mess around update_idle_cpu_load() / update_cpu_load_nohz().
2621          */
2622         this_rq->last_load_update_tick = jiffies;
2623         __update_cpu_load(this_rq, this_rq->load.weight, 1);
2624
2625         calc_load_account_active(this_rq);
2626 }
2627
2628 #ifdef CONFIG_SMP
2629
2630 /*
2631  * sched_exec - execve() is a valuable balancing opportunity, because at
2632  * this point the task has the smallest effective memory and cache footprint.
2633  */
2634 void sched_exec(void)
2635 {
2636         struct task_struct *p = current;
2637         unsigned long flags;
2638         int dest_cpu;
2639
2640         raw_spin_lock_irqsave(&p->pi_lock, flags);
2641         dest_cpu = p->sched_class->select_task_rq(p, SD_BALANCE_EXEC, 0);
2642         if (dest_cpu == smp_processor_id())
2643                 goto unlock;
2644
2645         if (likely(cpu_active(dest_cpu))) {
2646                 struct migration_arg arg = { p, dest_cpu };
2647
2648                 raw_spin_unlock_irqrestore(&p->pi_lock, flags);
2649                 stop_one_cpu(task_cpu(p), migration_cpu_stop, &arg);
2650                 return;
2651         }
2652 unlock:
2653         raw_spin_unlock_irqrestore(&p->pi_lock, flags);
2654 }
2655
2656 #endif
2657
2658 DEFINE_PER_CPU(struct kernel_stat, kstat);
2659 DEFINE_PER_CPU(struct kernel_cpustat, kernel_cpustat);
2660
2661 EXPORT_PER_CPU_SYMBOL(kstat);
2662 EXPORT_PER_CPU_SYMBOL(kernel_cpustat);
2663
2664 /*
2665  * Return any ns on the sched_clock that have not yet been accounted in
2666  * @p in case that task is currently running.
2667  *
2668  * Called with task_rq_lock() held on @rq.
2669  */
2670 static u64 do_task_delta_exec(struct task_struct *p, struct rq *rq)
2671 {
2672         u64 ns = 0;
2673
2674         if (task_current(rq, p)) {
2675                 update_rq_clock(rq);
2676                 ns = rq->clock_task - p->se.exec_start;
2677                 if ((s64)ns < 0)
2678                         ns = 0;
2679         }
2680
2681         return ns;
2682 }
2683
2684 unsigned long long task_delta_exec(struct task_struct *p)
2685 {
2686         unsigned long flags;
2687         struct rq *rq;
2688         u64 ns = 0;
2689
2690         rq = task_rq_lock(p, &flags);
2691         ns = do_task_delta_exec(p, rq);
2692         task_rq_unlock(rq, p, &flags);
2693
2694         return ns;
2695 }
2696
2697 /*
2698  * Return accounted runtime for the task.
2699  * In case the task is currently running, return the runtime plus current's
2700  * pending runtime that have not been accounted yet.
2701  */
2702 unsigned long long task_sched_runtime(struct task_struct *p)
2703 {
2704         unsigned long flags;
2705         struct rq *rq;
2706         u64 ns = 0;
2707
2708         rq = task_rq_lock(p, &flags);
2709         ns = p->se.sum_exec_runtime + do_task_delta_exec(p, rq);
2710         task_rq_unlock(rq, p, &flags);
2711
2712         return ns;
2713 }
2714
2715 /*
2716  * This function gets called by the timer code, with HZ frequency.
2717  * We call it with interrupts disabled.
2718  */
2719 void scheduler_tick(void)
2720 {
2721         int cpu = smp_processor_id();
2722         struct rq *rq = cpu_rq(cpu);
2723         struct task_struct *curr = rq->curr;
2724
2725         sched_clock_tick();
2726
2727         raw_spin_lock(&rq->lock);
2728         update_rq_clock(rq);
2729         update_cpu_load_active(rq);
2730         curr->sched_class->task_tick(rq, curr, 0);
2731         raw_spin_unlock(&rq->lock);
2732
2733         perf_event_task_tick();
2734
2735 #ifdef CONFIG_SMP
2736         rq->idle_balance = idle_cpu(cpu);
2737         trigger_load_balance(rq, cpu);
2738 #endif
2739         rq_last_tick_reset(rq);
2740 }
2741
2742 #ifdef CONFIG_NO_HZ_FULL
2743 /**
2744  * scheduler_tick_max_deferment
2745  *
2746  * Keep at least one tick per second when a single
2747  * active task is running because the scheduler doesn't
2748  * yet completely support full dynticks environment.
2749  *
2750  * This makes sure that uptime, CFS vruntime, load
2751  * balancing, etc... continue to move forward, even
2752  * with a very low granularity.
2753  */
2754 u64 scheduler_tick_max_deferment(void)
2755 {
2756         struct rq *rq = this_rq();
2757         unsigned long next, now = ACCESS_ONCE(jiffies);
2758
2759         next = rq->last_sched_tick + HZ;
2760
2761         if (time_before_eq(next, now))
2762                 return 0;
2763
2764         return jiffies_to_usecs(next - now) * NSEC_PER_USEC;
2765 }
2766 #endif
2767
2768 notrace unsigned long get_parent_ip(unsigned long addr)
2769 {
2770         if (in_lock_functions(addr)) {
2771                 addr = CALLER_ADDR2;
2772                 if (in_lock_functions(addr))
2773                         addr = CALLER_ADDR3;
2774         }
2775         return addr;
2776 }
2777
2778 #if defined(CONFIG_PREEMPT) && (defined(CONFIG_DEBUG_PREEMPT) || \
2779                                 defined(CONFIG_PREEMPT_TRACER))
2780
2781 void __kprobes add_preempt_count(int val)
2782 {
2783 #ifdef CONFIG_DEBUG_PREEMPT
2784         /*
2785          * Underflow?
2786          */
2787         if (DEBUG_LOCKS_WARN_ON((preempt_count() < 0)))
2788                 return;
2789 #endif
2790         preempt_count() += val;
2791 #ifdef CONFIG_DEBUG_PREEMPT
2792         /*
2793          * Spinlock count overflowing soon?
2794          */
2795         DEBUG_LOCKS_WARN_ON((preempt_count() & PREEMPT_MASK) >=
2796                                 PREEMPT_MASK - 10);
2797 #endif
2798         if (preempt_count() == val)
2799                 trace_preempt_off(CALLER_ADDR0, get_parent_ip(CALLER_ADDR1));
2800 }
2801 EXPORT_SYMBOL(add_preempt_count);
2802
2803 void __kprobes sub_preempt_count(int val)
2804 {
2805 #ifdef CONFIG_DEBUG_PREEMPT
2806         /*
2807          * Underflow?
2808          */
2809         if (DEBUG_LOCKS_WARN_ON(val > preempt_count()))
2810                 return;
2811         /*
2812          * Is the spinlock portion underflowing?
2813          */
2814         if (DEBUG_LOCKS_WARN_ON((val < PREEMPT_MASK) &&
2815                         !(preempt_count() & PREEMPT_MASK)))
2816                 return;
2817 #endif
2818
2819         if (preempt_count() == val)
2820                 trace_preempt_on(CALLER_ADDR0, get_parent_ip(CALLER_ADDR1));
2821         preempt_count() -= val;
2822 }
2823 EXPORT_SYMBOL(sub_preempt_count);
2824
2825 #endif
2826
2827 /*
2828  * Print scheduling while atomic bug:
2829  */
2830 static noinline void __schedule_bug(struct task_struct *prev)
2831 {
2832         if (oops_in_progress)
2833                 return;
2834
2835         printk(KERN_ERR "BUG: scheduling while atomic: %s/%d/0x%08x\n",
2836                 prev->comm, prev->pid, preempt_count());
2837
2838         debug_show_held_locks(prev);
2839         print_modules();
2840         if (irqs_disabled())
2841                 print_irqtrace_events(prev);
2842         dump_stack();
2843         add_taint(TAINT_WARN, LOCKDEP_STILL_OK);
2844 }
2845
2846 /*
2847  * Various schedule()-time debugging checks and statistics:
2848  */
2849 static inline void schedule_debug(struct task_struct *prev)
2850 {
2851         /*
2852          * Test if we are atomic. Since do_exit() needs to call into
2853          * schedule() atomically, we ignore that path for now.
2854          * Otherwise, whine if we are scheduling when we should not be.
2855          */
2856         if (unlikely(in_atomic_preempt_off() && !prev->exit_state))
2857                 __schedule_bug(prev);
2858         rcu_sleep_check();
2859
2860         profile_hit(SCHED_PROFILING, __builtin_return_address(0));
2861
2862         schedstat_inc(this_rq(), sched_count);
2863 }
2864
2865 static void put_prev_task(struct rq *rq, struct task_struct *prev)
2866 {
2867         if (prev->on_rq || rq->skip_clock_update < 0)
2868                 update_rq_clock(rq);
2869         prev->sched_class->put_prev_task(rq, prev);
2870 }
2871
2872 /*
2873  * Pick up the highest-prio task:
2874  */
2875 static inline struct task_struct *
2876 pick_next_task(struct rq *rq)
2877 {
2878         const struct sched_class *class;
2879         struct task_struct *p;
2880
2881         /*
2882          * Optimization: we know that if all tasks are in
2883          * the fair class we can call that function directly:
2884          */
2885         if (likely(rq->nr_running == rq->cfs.h_nr_running)) {
2886                 p = fair_sched_class.pick_next_task(rq);
2887                 if (likely(p))
2888                         return p;
2889         }
2890
2891         for_each_class(class) {
2892                 p = class->pick_next_task(rq);
2893                 if (p)
2894                         return p;
2895         }
2896
2897         BUG(); /* the idle class will always have a runnable task */
2898 }
2899
2900 /*
2901  * __schedule() is the main scheduler function.
2902  *
2903  * The main means of driving the scheduler and thus entering this function are:
2904  *
2905  *   1. Explicit blocking: mutex, semaphore, waitqueue, etc.
2906  *
2907  *   2. TIF_NEED_RESCHED flag is checked on interrupt and userspace return
2908  *      paths. For example, see arch/x86/entry_64.S.
2909  *
2910  *      To drive preemption between tasks, the scheduler sets the flag in timer
2911  *      interrupt handler scheduler_tick().
2912  *
2913  *   3. Wakeups don't really cause entry into schedule(). They add a
2914  *      task to the run-queue and that's it.
2915  *
2916  *      Now, if the new task added to the run-queue preempts the current
2917  *      task, then the wakeup sets TIF_NEED_RESCHED and schedule() gets
2918  *      called on the nearest possible occasion:
2919  *
2920  *       - If the kernel is preemptible (CONFIG_PREEMPT=y):
2921  *
2922  *         - in syscall or exception context, at the next outmost
2923  *           preempt_enable(). (this might be as soon as the wake_up()'s
2924  *           spin_unlock()!)
2925  *
2926  *         - in IRQ context, return from interrupt-handler to
2927  *           preemptible context
2928  *
2929  *       - If the kernel is not preemptible (CONFIG_PREEMPT is not set)
2930  *         then at the next:
2931  *
2932  *          - cond_resched() call
2933  *          - explicit schedule() call
2934  *          - return from syscall or exception to user-space
2935  *          - return from interrupt-handler to user-space
2936  */
2937 static void __sched __schedule(void)
2938 {
2939         struct task_struct *prev, *next;
2940         unsigned long *switch_count;
2941         struct rq *rq;
2942         int cpu;
2943
2944 need_resched:
2945         preempt_disable();
2946         cpu = smp_processor_id();
2947         rq = cpu_rq(cpu);
2948         rcu_note_context_switch(cpu);
2949         prev = rq->curr;
2950
2951         schedule_debug(prev);
2952
2953         if (sched_feat(HRTICK))
2954                 hrtick_clear(rq);
2955
2956         raw_spin_lock_irq(&rq->lock);
2957
2958         switch_count = &prev->nivcsw;
2959         if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
2960                 if (unlikely(signal_pending_state(prev->state, prev))) {
2961                         prev->state = TASK_RUNNING;
2962                 } else {
2963                         deactivate_task(rq, prev, DEQUEUE_SLEEP);
2964                         prev->on_rq = 0;
2965
2966                         /*
2967                          * If a worker went to sleep, notify and ask workqueue
2968                          * whether it wants to wake up a task to maintain
2969                          * concurrency.
2970                          */
2971                         if (prev->flags & PF_WQ_WORKER) {
2972                                 struct task_struct *to_wakeup;
2973
2974                                 to_wakeup = wq_worker_sleeping(prev, cpu);
2975                                 if (to_wakeup)
2976                                         try_to_wake_up_local(to_wakeup);
2977                         }
2978                 }
2979                 switch_count = &prev->nvcsw;
2980         }
2981
2982         pre_schedule(rq, prev);
2983
2984         if (unlikely(!rq->nr_running))
2985                 idle_balance(cpu, rq);
2986
2987         put_prev_task(rq, prev);
2988         next = pick_next_task(rq);
2989         clear_tsk_need_resched(prev);
2990         rq->skip_clock_update = 0;
2991
2992         if (likely(prev != next)) {
2993                 rq->nr_switches++;
2994                 rq->curr = next;
2995                 ++*switch_count;
2996
2997                 context_switch(rq, prev, next); /* unlocks the rq */
2998                 /*
2999                  * The context switch have flipped the stack from under us
3000                  * and restored the local variables which were saved when
3001                  * this task called schedule() in the past. prev == current
3002                  * is still correct, but it can be moved to another cpu/rq.
3003                  */
3004                 cpu = smp_processor_id();
3005                 rq = cpu_rq(cpu);
3006         } else
3007                 raw_spin_unlock_irq(&rq->lock);
3008
3009         post_schedule(rq);
3010
3011         sched_preempt_enable_no_resched();
3012         if (need_resched())
3013                 goto need_resched;
3014 }
3015
3016 static inline void sched_submit_work(struct task_struct *tsk)
3017 {
3018         if (!tsk->state || tsk_is_pi_blocked(tsk))
3019                 return;
3020         /*
3021          * If we are going to sleep and we have plugged IO queued,
3022          * make sure to submit it to avoid deadlocks.
3023          */
3024         if (blk_needs_flush_plug(tsk))
3025                 blk_schedule_flush_plug(tsk);
3026 }
3027
3028 asmlinkage void __sched schedule(void)
3029 {
3030         struct task_struct *tsk = current;
3031
3032         sched_submit_work(tsk);
3033         __schedule();
3034 }
3035 EXPORT_SYMBOL(schedule);
3036
3037 #ifdef CONFIG_CONTEXT_TRACKING
3038 asmlinkage void __sched schedule_user(void)
3039 {
3040         /*
3041          * If we come here after a random call to set_need_resched(),
3042          * or we have been woken up remotely but the IPI has not yet arrived,
3043          * we haven't yet exited the RCU idle mode. Do it here manually until
3044          * we find a better solution.
3045          */
3046         user_exit();
3047         schedule();
3048         user_enter();
3049 }
3050 #endif
3051
3052 /**
3053  * schedule_preempt_disabled - called with preemption disabled
3054  *
3055  * Returns with preemption disabled. Note: preempt_count must be 1
3056  */
3057 void __sched schedule_preempt_disabled(void)
3058 {
3059         sched_preempt_enable_no_resched();
3060         schedule();
3061         preempt_disable();
3062 }
3063
3064 #ifdef CONFIG_PREEMPT
3065 /*
3066  * this is the entry point to schedule() from in-kernel preemption
3067  * off of preempt_enable. Kernel preemptions off return from interrupt
3068  * occur there and call schedule directly.
3069  */
3070 asmlinkage void __sched notrace preempt_schedule(void)
3071 {
3072         struct thread_info *ti = current_thread_info();
3073
3074         /*
3075          * If there is a non-zero preempt_count or interrupts are disabled,
3076          * we do not want to preempt the current task. Just return..
3077          */
3078         if (likely(ti->preempt_count || irqs_disabled()))
3079                 return;
3080
3081         do {
3082                 add_preempt_count_notrace(PREEMPT_ACTIVE);
3083                 __schedule();
3084                 sub_preempt_count_notrace(PREEMPT_ACTIVE);
3085
3086                 /*
3087                  * Check again in case we missed a preemption opportunity
3088                  * between schedule and now.
3089                  */
3090                 barrier();
3091         } while (need_resched());
3092 }
3093 EXPORT_SYMBOL(preempt_schedule);
3094
3095 /*
3096  * this is the entry point to schedule() from kernel preemption
3097  * off of irq context.
3098  * Note, that this is called and return with irqs disabled. This will
3099  * protect us against recursive calling from irq.
3100  */
3101 asmlinkage void __sched preempt_schedule_irq(void)
3102 {
3103         struct thread_info *ti = current_thread_info();
3104         enum ctx_state prev_state;
3105
3106         /* Catch callers which need to be fixed */
3107         BUG_ON(ti->preempt_count || !irqs_disabled());
3108
3109         prev_state = exception_enter();
3110
3111         do {
3112                 add_preempt_count(PREEMPT_ACTIVE);
3113                 local_irq_enable();
3114                 __schedule();
3115                 local_irq_disable();
3116                 sub_preempt_count(PREEMPT_ACTIVE);
3117
3118                 /*
3119                  * Check again in case we missed a preemption opportunity
3120                  * between schedule and now.
3121                  */
3122                 barrier();
3123         } while (need_resched());
3124
3125         exception_exit(prev_state);
3126 }
3127
3128 #endif /* CONFIG_PREEMPT */
3129
3130 int default_wake_function(wait_queue_t *curr, unsigned mode, int wake_flags,
3131                           void *key)
3132 {
3133         return try_to_wake_up(curr->private, mode, wake_flags);
3134 }
3135 EXPORT_SYMBOL(default_wake_function);
3136
3137 /*
3138  * The core wakeup function. Non-exclusive wakeups (nr_exclusive == 0) just
3139  * wake everything up. If it's an exclusive wakeup (nr_exclusive == small +ve
3140  * number) then we wake all the non-exclusive tasks and one exclusive task.
3141  *
3142  * There are circumstances in which we can try to wake a task which has already
3143  * started to run but is not in state TASK_RUNNING. try_to_wake_up() returns
3144  * zero in this (rare) case, and we handle it by continuing to scan the queue.
3145  */
3146 static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
3147                         int nr_exclusive, int wake_flags, void *key)
3148 {
3149         wait_queue_t *curr, *next;
3150
3151         list_for_each_entry_safe(curr, next, &q->task_list, task_list) {
3152                 unsigned flags = curr->flags;
3153
3154                 if (curr->func(curr, mode, wake_flags, key) &&
3155                                 (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
3156                         break;
3157         }
3158 }
3159
3160 /**
3161  * __wake_up - wake up threads blocked on a waitqueue.
3162  * @q: the waitqueue
3163  * @mode: which threads
3164  * @nr_exclusive: how many wake-one or wake-many threads to wake up
3165  * @key: is directly passed to the wakeup function
3166  *
3167  * It may be assumed that this function implies a write memory barrier before
3168  * changing the task state if and only if any tasks are woken up.
3169  */
3170 void __wake_up(wait_queue_head_t *q, unsigned int mode,
3171                         int nr_exclusive, void *key)
3172 {
3173         unsigned long flags;
3174
3175         spin_lock_irqsave(&q->lock, flags);
3176         __wake_up_common(q, mode, nr_exclusive, 0, key);
3177         spin_unlock_irqrestore(&q->lock, flags);
3178 }
3179 EXPORT_SYMBOL(__wake_up);
3180
3181 /*
3182  * Same as __wake_up but called with the spinlock in wait_queue_head_t held.
3183  */
3184 void __wake_up_locked(wait_queue_head_t *q, unsigned int mode, int nr)
3185 {
3186         __wake_up_common(q, mode, nr, 0, NULL);
3187 }
3188 EXPORT_SYMBOL_GPL(__wake_up_locked);
3189
3190 void __wake_up_locked_key(wait_queue_head_t *q, unsigned int mode, void *key)
3191 {
3192         __wake_up_common(q, mode, 1, 0, key);
3193 }
3194 EXPORT_SYMBOL_GPL(__wake_up_locked_key);
3195
3196 /**
3197  * __wake_up_sync_key - wake up threads blocked on a waitqueue.
3198  * @q: the waitqueue
3199  * @mode: which threads
3200  * @nr_exclusive: how many wake-one or wake-many threads to wake up
3201  * @key: opaque value to be passed to wakeup targets
3202  *
3203  * The sync wakeup differs that the waker knows that it will schedule
3204  * away soon, so while the target thread will be woken up, it will not
3205  * be migrated to another CPU - ie. the two threads are 'synchronized'
3206  * with each other. This can prevent needless bouncing between CPUs.
3207  *
3208  * On UP it can prevent extra preemption.
3209  *
3210  * It may be assumed that this function implies a write memory barrier before
3211  * changing the task state if and only if any tasks are woken up.
3212  */
3213 void __wake_up_sync_key(wait_queue_head_t *q, unsigned int mode,
3214                         int nr_exclusive, void *key)
3215 {
3216         unsigned long flags;
3217         int wake_flags = WF_SYNC;
3218
3219         if (unlikely(!q))
3220                 return;
3221
3222         if (unlikely(!nr_exclusive))
3223                 wake_flags = 0;
3224
3225         spin_lock_irqsave(&q->lock, flags);
3226         __wake_up_common(q, mode, nr_exclusive, wake_flags, key);
3227         spin_unlock_irqrestore(&q->lock, flags);
3228 }
3229 EXPORT_SYMBOL_GPL(__wake_up_sync_key);
3230
3231 /*
3232  * __wake_up_sync - see __wake_up_sync_key()
3233  */
3234 void __wake_up_sync(wait_queue_head_t *q, unsigned int mode, int nr_exclusive)
3235 {
3236         __wake_up_sync_key(q, mode, nr_exclusive, NULL);
3237 }
3238 EXPORT_SYMBOL_GPL(__wake_up_sync);      /* For internal use only */
3239
3240 /**
3241  * complete: - signals a single thread waiting on this completion
3242  * @x:  holds the state of this particular completion
3243  *
3244  * This will wake up a single thread waiting on this completion. Threads will be
3245  * awakened in the same order in which they were queued.
3246  *
3247  * See also complete_all(), wait_for_completion() and related routines.
3248  *
3249  * It may be assumed that this function implies a write memory barrier before
3250  * changing the task state if and only if any tasks are woken up.
3251  */
3252 void complete(struct completion *x)
3253 {
3254         unsigned long flags;
3255
3256         spin_lock_irqsave(&x->wait.lock, flags);
3257         x->done++;
3258         __wake_up_common(&x->wait, TASK_NORMAL, 1, 0, NULL);
3259         spin_unlock_irqrestore(&x->wait.lock, flags);
3260 }
3261 EXPORT_SYMBOL(complete);
3262
3263 /**
3264  * complete_all: - signals all threads waiting on this completion
3265  * @x:  holds the state of this particular completion
3266  *
3267  * This will wake up all threads waiting on this particular completion event.
3268  *
3269  * It may be assumed that this function implies a write memory barrier before
3270  * changing the task state if and only if any tasks are woken up.
3271  */
3272 void complete_all(struct completion *x)
3273 {
3274         unsigned long flags;
3275
3276         spin_lock_irqsave(&x->wait.lock, flags);
3277         x->done += UINT_MAX/2;
3278         __wake_up_common(&x->wait, TASK_NORMAL, 0, 0, NULL);
3279         spin_unlock_irqrestore(&x->wait.lock, flags);
3280 }
3281 EXPORT_SYMBOL(complete_all);
3282
3283 static inline long __sched
3284 do_wait_for_common(struct completion *x,
3285                    long (*action)(long), long timeout, int state)
3286 {
3287         if (!x->done) {
3288                 DECLARE_WAITQUEUE(wait, current);
3289
3290                 __add_wait_queue_tail_exclusive(&x->wait, &wait);
3291                 do {
3292                         if (signal_pending_state(state, current)) {
3293                                 timeout = -ERESTARTSYS;
3294                                 break;
3295                         }
3296                         __set_current_state(state);
3297                         spin_unlock_irq(&x->wait.lock);
3298                         timeout = action(timeout);
3299                         spin_lock_irq(&x->wait.lock);
3300                 } while (!x->done && timeout);
3301                 __remove_wait_queue(&x->wait, &wait);
3302                 if (!x->done)
3303                         return timeout;
3304         }
3305         x->done--;
3306         return timeout ?: 1;
3307 }
3308
3309 static inline long __sched
3310 __wait_for_common(struct completion *x,
3311                   long (*action)(long), long timeout, int state)
3312 {
3313         might_sleep();
3314
3315         spin_lock_irq(&x->wait.lock);
3316         timeout = do_wait_for_common(x, action, timeout, state);
3317         spin_unlock_irq(&x->wait.lock);
3318         return timeout;
3319 }
3320
3321 static long __sched
3322 wait_for_common(struct completion *x, long timeout, int state)
3323 {
3324         return __wait_for_common(x, schedule_timeout, timeout, state);
3325 }
3326
3327 static long __sched
3328 wait_for_common_io(struct completion *x, long timeout, int state)
3329 {
3330         return __wait_for_common(x, io_schedule_timeout, timeout, state);
3331 }
3332
3333 /**
3334  * wait_for_completion: - waits for completion of a task
3335  * @x:  holds the state of this particular completion
3336  *
3337  * This waits to be signaled for completion of a specific task. It is NOT
3338  * interruptible and there is no timeout.
3339  *
3340  * See also similar routines (i.e. wait_for_completion_timeout()) with timeout
3341  * and interrupt capability. Also see complete().
3342  */
3343 void __sched wait_for_completion(struct completion *x)
3344 {
3345         wait_for_common(x, MAX_SCHEDULE_TIMEOUT, TASK_UNINTERRUPTIBLE);
3346 }
3347 EXPORT_SYMBOL(wait_for_completion);
3348
3349 /**
3350  * wait_for_completion_timeout: - waits for completion of a task (w/timeout)
3351  * @x:  holds the state of this particular completion
3352  * @timeout:  timeout value in jiffies
3353  *
3354  * This waits for either a completion of a specific task to be signaled or for a
3355  * specified timeout to expire. The timeout is in jiffies. It is not
3356  * interruptible.
3357  *
3358  * The return value is 0 if timed out, and positive (at least 1, or number of
3359  * jiffies left till timeout) if completed.
3360  */
3361 unsigned long __sched
3362 wait_for_completion_timeout(struct completion *x, unsigned long timeout)
3363 {
3364         return wait_for_common(x, timeout, TASK_UNINTERRUPTIBLE);
3365 }
3366 EXPORT_SYMBOL(wait_for_completion_timeout);
3367
3368 /**
3369  * wait_for_completion_io: - waits for completion of a task
3370  * @x:  holds the state of this particular completion
3371  *
3372  * This waits to be signaled for completion of a specific task. It is NOT
3373  * interruptible and there is no timeout. The caller is accounted as waiting
3374  * for IO.
3375  */
3376 void __sched wait_for_completion_io(struct completion *x)
3377 {
3378         wait_for_common_io(x, MAX_SCHEDULE_TIMEOUT, TASK_UNINTERRUPTIBLE);
3379 }
3380 EXPORT_SYMBOL(wait_for_completion_io);
3381
3382 /**
3383  * wait_for_completion_io_timeout: - waits for completion of a task (w/timeout)
3384  * @x:  holds the state of this particular completion
3385  * @timeout:  timeout value in jiffies
3386  *
3387  * This waits for either a completion of a specific task to be signaled or for a
3388  * specified timeout to expire. The timeout is in jiffies. It is not
3389  * interruptible. The caller is accounted as waiting for IO.
3390  *
3391  * The return value is 0 if timed out, and positive (at least 1, or number of
3392  * jiffies left till timeout) if completed.
3393  */
3394 unsigned long __sched
3395 wait_for_completion_io_timeout(struct completion *x, unsigned long timeout)
3396 {
3397         return wait_for_common_io(x, timeout, TASK_UNINTERRUPTIBLE);
3398 }
3399 EXPORT_SYMBOL(wait_for_completion_io_timeout);
3400
3401 /**
3402  * wait_for_completion_interruptible: - waits for completion of a task (w/intr)
3403  * @x:  holds the state of this particular completion
3404  *
3405  * This waits for completion of a specific task to be signaled. It is
3406  * interruptible.
3407  *
3408  * The return value is -ERESTARTSYS if interrupted, 0 if completed.
3409  */
3410 int __sched wait_for_completion_interruptible(struct completion *x)
3411 {
3412         long t = wait_for_common(x, MAX_SCHEDULE_TIMEOUT, TASK_INTERRUPTIBLE);
3413         if (t == -ERESTARTSYS)
3414                 return t;
3415         return 0;
3416 }
3417 EXPORT_SYMBOL(wait_for_completion_interruptible);
3418
3419 /**
3420  * wait_for_completion_interruptible_timeout: - waits for completion (w/(to,intr))
3421  * @x:  holds the state of this particular completion
3422  * @timeout:  timeout value in jiffies
3423  *
3424  * This waits for either a completion of a specific task to be signaled or for a
3425  * specified timeout to expire. It is interruptible. The timeout is in jiffies.
3426  *
3427  * The return value is -ERESTARTSYS if interrupted, 0 if timed out,
3428  * positive (at least 1, or number of jiffies left till timeout) if completed.
3429  */
3430 long __sched
3431 wait_for_completion_interruptible_timeout(struct completion *x,
3432                                           unsigned long timeout)
3433 {
3434         return wait_for_common(x, timeout, TASK_INTERRUPTIBLE);
3435 }
3436 EXPORT_SYMBOL(wait_for_completion_interruptible_timeout);
3437
3438 /**
3439  * wait_for_completion_killable: - waits for completion of a task (killable)
3440  * @x:  holds the state of this particular completion
3441  *
3442  * This waits to be signaled for completion of a specific task. It can be
3443  * interrupted by a kill signal.
3444  *
3445  * The return value is -ERESTARTSYS if interrupted, 0 if completed.
3446  */
3447 int __sched wait_for_completion_killable(struct completion *x)
3448 {
3449         long t = wait_for_common(x, MAX_SCHEDULE_TIMEOUT, TASK_KILLABLE);
3450         if (t == -ERESTARTSYS)
3451                 return t;
3452         return 0;
3453 }
3454 EXPORT_SYMBOL(wait_for_completion_killable);
3455
3456 /**
3457  * wait_for_completion_killable_timeout: - waits for completion of a task (w/(to,killable))
3458  * @x:  holds the state of this particular completion
3459  * @timeout:  timeout value in jiffies
3460  *
3461  * This waits for either a completion of a specific task to be
3462  * signaled or for a specified timeout to expire. It can be
3463  * interrupted by a kill signal. The timeout is in jiffies.
3464  *
3465  * The return value is -ERESTARTSYS if interrupted, 0 if timed out,
3466  * positive (at least 1, or number of jiffies left till timeout) if completed.
3467  */
3468 long __sched
3469 wait_for_completion_killable_timeout(struct completion *x,
3470                                      unsigned long timeout)
3471 {
3472         return wait_for_common(x, timeout, TASK_KILLABLE);
3473 }
3474 EXPORT_SYMBOL(wait_for_completion_killable_timeout);
3475
3476 /**
3477  *      try_wait_for_completion - try to decrement a completion without blocking
3478  *      @x:     completion structure
3479  *
3480  *      Returns: 0 if a decrement cannot be done without blocking
3481  *               1 if a decrement succeeded.
3482  *
3483  *      If a completion is being used as a counting completion,
3484  *      attempt to decrement the counter without blocking. This
3485  *      enables us to avoid waiting if the resource the completion
3486  *      is protecting is not available.
3487  */
3488 bool try_wait_for_completion(struct completion *x)
3489 {
3490         unsigned long flags;
3491         int ret = 1;
3492
3493         spin_lock_irqsave(&x->wait.lock, flags);
3494         if (!x->done)
3495                 ret = 0;
3496         else
3497                 x->done--;
3498         spin_unlock_irqrestore(&x->wait.lock, flags);
3499         return ret;
3500 }
3501 EXPORT_SYMBOL(try_wait_for_completion);
3502
3503 /**
3504  *      completion_done - Test to see if a completion has any waiters
3505  *      @x:     completion structure
3506  *
3507  *      Returns: 0 if there are waiters (wait_for_completion() in progress)
3508  *               1 if there are no waiters.
3509  *
3510  */
3511 bool completion_done(struct completion *x)
3512 {
3513         unsigned long flags;
3514         int ret = 1;
3515
3516         spin_lock_irqsave(&x->wait.lock, flags);
3517         if (!x->done)
3518                 ret = 0;
3519         spin_unlock_irqrestore(&x->wait.lock, flags);
3520         return ret;
3521 }
3522 EXPORT_SYMBOL(completion_done);
3523
3524 static long __sched
3525 sleep_on_common(wait_queue_head_t *q, int state, long timeout)
3526 {
3527         unsigned long flags;
3528         wait_queue_t wait;
3529
3530         init_waitqueue_entry(&wait, current);
3531
3532         __set_current_state(state);
3533
3534         spin_lock_irqsave(&q->lock, flags);
3535         __add_wait_queue(q, &wait);
3536         spin_unlock(&q->lock);
3537         timeout = schedule_timeout(timeout);
3538         spin_lock_irq(&q->lock);
3539         __remove_wait_queue(q, &wait);
3540         spin_unlock_irqrestore(&q->lock, flags);
3541
3542         return timeout;
3543 }
3544
3545 void __sched interruptible_sleep_on(wait_queue_head_t *q)
3546 {
3547         sleep_on_common(q, TASK_INTERRUPTIBLE, MAX_SCHEDULE_TIMEOUT);
3548 }
3549 EXPORT_SYMBOL(interruptible_sleep_on);
3550
3551 long __sched
3552 interruptible_sleep_on_timeout(wait_queue_head_t *q, long timeout)
3553 {
3554         return sleep_on_common(q, TASK_INTERRUPTIBLE, timeout);
3555 }
3556 EXPORT_SYMBOL(interruptible_sleep_on_timeout);
3557
3558 void __sched sleep_on(wait_queue_head_t *q)
3559 {
3560         sleep_on_common(q, TASK_UNINTERRUPTIBLE, MAX_SCHEDULE_TIMEOUT);
3561 }
3562 EXPORT_SYMBOL(sleep_on);
3563
3564 long __sched sleep_on_timeout(wait_queue_head_t *q, long timeout)
3565 {
3566         return sleep_on_common(q, TASK_UNINTERRUPTIBLE, timeout);
3567 }
3568 EXPORT_SYMBOL(sleep_on_timeout);
3569
3570 #ifdef CONFIG_RT_MUTEXES
3571
3572 /*
3573  * rt_mutex_setprio - set the current priority of a task
3574  * @p: task
3575  * @prio: prio value (kernel-internal form)
3576  *
3577  * This function changes the 'effective' priority of a task. It does
3578  * not touch ->normal_prio like __setscheduler().
3579  *
3580  * Used by the rt_mutex code to implement priority inheritance logic.
3581  */
3582 void rt_mutex_setprio(struct task_struct *p, int prio)
3583 {
3584         int oldprio, on_rq, running;
3585         struct rq *rq;
3586         const struct sched_class *prev_class;
3587
3588         BUG_ON(prio < 0 || prio > MAX_PRIO);
3589
3590         rq = __task_rq_lock(p);
3591
3592         /*
3593          * Idle task boosting is a nono in general. There is one
3594          * exception, when PREEMPT_RT and NOHZ is active:
3595          *
3596          * The idle task calls get_next_timer_interrupt() and holds
3597          * the timer wheel base->lock on the CPU and another CPU wants
3598          * to access the timer (probably to cancel it). We can safely
3599          * ignore the boosting request, as the idle CPU runs this code
3600          * with interrupts disabled and will complete the lock
3601          * protected section without being interrupted. So there is no
3602          * real need to boost.
3603          */
3604         if (unlikely(p == rq->idle)) {
3605                 WARN_ON(p != rq->curr);
3606                 WARN_ON(p->pi_blocked_on);
3607                 goto out_unlock;
3608         }
3609
3610         trace_sched_pi_setprio(p, prio);
3611         oldprio = p->prio;
3612         prev_class = p->sched_class;
3613         on_rq = p->on_rq;
3614         running = task_current(rq, p);
3615         if (on_rq)
3616                 dequeue_task(rq, p, 0);
3617         if (running)
3618                 p->sched_class->put_prev_task(rq, p);
3619
3620         if (rt_prio(prio))
3621                 p->sched_class = &rt_sched_class;
3622         else
3623                 p->sched_class = &fair_sched_class;
3624
3625         p->prio = prio;
3626
3627         if (running)
3628                 p->sched_class->set_curr_task(rq);
3629         if (on_rq)
3630                 enqueue_task(rq, p, oldprio < prio ? ENQUEUE_HEAD : 0);
3631
3632         check_class_changed(rq, p, prev_class, oldprio);
3633 out_unlock:
3634         __task_rq_unlock(rq);
3635 }
3636 #endif
3637 void set_user_nice(struct task_struct *p, long nice)
3638 {
3639         int old_prio, delta, on_rq;
3640         unsigned long flags;
3641         struct rq *rq;
3642
3643         if (TASK_NICE(p) == nice || nice < -20 || nice > 19)
3644                 return;
3645         /*
3646          * We have to be careful, if called from sys_setpriority(),
3647          * the task might be in the middle of scheduling on another CPU.
3648          */
3649         rq = task_rq_lock(p, &flags);
3650         /*
3651          * The RT priorities are set via sched_setscheduler(), but we still
3652          * allow the 'normal' nice value to be set - but as expected
3653          * it wont have any effect on scheduling until the task is
3654          * SCHED_FIFO/SCHED_RR:
3655          */
3656         if (task_has_rt_policy(p)) {
3657                 p->static_prio = NICE_TO_PRIO(nice);
3658                 goto out_unlock;
3659         }
3660         on_rq = p->on_rq;
3661         if (on_rq)
3662                 dequeue_task(rq, p, 0);
3663
3664         p->static_prio = NICE_TO_PRIO(nice);
3665         set_load_weight(p);
3666         old_prio = p->prio;
3667         p->prio = effective_prio(p);
3668         delta = p->prio - old_prio;
3669
3670         if (on_rq) {
3671                 enqueue_task(rq, p, 0);
3672                 /*
3673                  * If the task increased its priority or is running and
3674                  * lowered its priority, then reschedule its CPU:
3675                  */
3676                 if (delta < 0 || (delta > 0 && task_running(rq, p)))
3677                         resched_task(rq->curr);
3678         }
3679 out_unlock:
3680         task_rq_unlock(rq, p, &flags);
3681 }
3682 EXPORT_SYMBOL(set_user_nice);
3683
3684 /*
3685  * can_nice - check if a task can reduce its nice value
3686  * @p: task
3687  * @nice: nice value
3688  */
3689 int can_nice(const struct task_struct *p, const int nice)
3690 {
3691         /* convert nice value [19,-20] to rlimit style value [1,40] */
3692         int nice_rlim = 20 - nice;
3693
3694         return (nice_rlim <= task_rlimit(p, RLIMIT_NICE) ||
3695                 capable(CAP_SYS_NICE));
3696 }
3697
3698 #ifdef __ARCH_WANT_SYS_NICE
3699
3700 /*
3701  * sys_nice - change the priority of the current process.
3702  * @increment: priority increment
3703  *
3704  * sys_setpriority is a more generic, but much slower function that
3705  * does similar things.
3706  */
3707 SYSCALL_DEFINE1(nice, int, increment)
3708 {
3709         long nice, retval;
3710
3711         /*
3712          * Setpriority might change our priority at the same moment.
3713          * We don't have to worry. Conceptually one call occurs first
3714          * and we have a single winner.
3715          */
3716         if (increment < -40)
3717                 increment = -40;
3718         if (increment > 40)
3719                 increment = 40;
3720
3721         nice = TASK_NICE(current) + increment;
3722         if (nice < -20)
3723                 nice = -20;
3724         if (nice > 19)
3725                 nice = 19;
3726
3727         if (increment < 0 && !can_nice(current, nice))
3728                 return -EPERM;
3729
3730         retval = security_task_setnice(current, nice);
3731         if (retval)
3732                 return retval;
3733
3734         set_user_nice(current, nice);
3735         return 0;
3736 }
3737
3738 #endif
3739
3740 /**
3741  * task_prio - return the priority value of a given task.
3742  * @p: the task in question.
3743  *
3744  * This is the priority value as seen by users in /proc.
3745  * RT tasks are offset by -200. Normal tasks are centered
3746  * around 0, value goes from -16 to +15.
3747  */
3748 int task_prio(const struct task_struct *p)
3749 {
3750         return p->prio - MAX_RT_PRIO;
3751 }
3752
3753 /**
3754  * task_nice - return the nice value of a given task.
3755  * @p: the task in question.
3756  */
3757 int task_nice(const struct task_struct *p)
3758 {
3759         return TASK_NICE(p);
3760 }
3761 EXPORT_SYMBOL(task_nice);
3762
3763 /**
3764  * idle_cpu - is a given cpu idle currently?
3765  * @cpu: the processor in question.
3766  */
3767 int idle_cpu(int cpu)
3768 {
3769         struct rq *rq = cpu_rq(cpu);
3770
3771         if (rq->curr != rq->idle)
3772                 return 0;
3773
3774         if (rq->nr_running)
3775                 return 0;
3776
3777 #ifdef CONFIG_SMP
3778         if (!llist_empty(&rq->wake_list))
3779                 return 0;
3780 #endif
3781
3782         return 1;
3783 }
3784
3785 /**
3786  * idle_task - return the idle task for a given cpu.
3787  * @cpu: the processor in question.
3788  */
3789 struct task_struct *idle_task(int cpu)
3790 {
3791         return cpu_rq(cpu)->idle;
3792 }
3793
3794 /**
3795  * find_process_by_pid - find a process with a matching PID value.
3796  * @pid: the pid in question.
3797  */
3798 static struct task_struct *find_process_by_pid(pid_t pid)
3799 {
3800         return pid ? find_task_by_vpid(pid) : current;
3801 }
3802
3803 /* Actually do priority change: must hold rq lock. */
3804 static void
3805 __setscheduler(struct rq *rq, struct task_struct *p, int policy, int prio)
3806 {
3807         p->policy = policy;
3808         p->rt_priority = prio;
3809         p->normal_prio = normal_prio(p);
3810         /* we are holding p->pi_lock already */
3811         p->prio = rt_mutex_getprio(p);
3812         if (rt_prio(p->prio))
3813                 p->sched_class = &rt_sched_class;
3814         else
3815                 p->sched_class = &fair_sched_class;
3816         set_load_weight(p);
3817 }
3818
3819 /*
3820  * check the target process has a UID that matches the current process's
3821  */
3822 static bool check_same_owner(struct task_struct *p)
3823 {
3824         const struct cred *cred = current_cred(), *pcred;
3825         bool match;
3826
3827         rcu_read_lock();
3828         pcred = __task_cred(p);
3829         match = (uid_eq(cred->euid, pcred->euid) ||
3830                  uid_eq(cred->euid, pcred->uid));
3831         rcu_read_unlock();
3832         return match;
3833 }
3834
3835 static int __sched_setscheduler(struct task_struct *p, int policy,
3836                                 const struct sched_param *param, bool user)
3837 {
3838         int retval, oldprio, oldpolicy = -1, on_rq, running;
3839         unsigned long flags;
3840         const struct sched_class *prev_class;
3841         struct rq *rq;
3842         int reset_on_fork;
3843
3844         /* may grab non-irq protected spin_locks */
3845         BUG_ON(in_interrupt());
3846 recheck:
3847         /* double check policy once rq lock held */
3848         if (policy < 0) {
3849                 reset_on_fork = p->sched_reset_on_fork;
3850                 policy = oldpolicy = p->policy;
3851         } else {
3852                 reset_on_fork = !!(policy & SCHED_RESET_ON_FORK);
3853                 policy &= ~SCHED_RESET_ON_FORK;
3854
3855                 if (policy != SCHED_FIFO && policy != SCHED_RR &&
3856                                 policy != SCHED_NORMAL && policy != SCHED_BATCH &&
3857                                 policy != SCHED_IDLE)
3858                         return -EINVAL;
3859         }
3860
3861         /*
3862          * Valid priorities for SCHED_FIFO and SCHED_RR are
3863          * 1..MAX_USER_RT_PRIO-1, valid priority for SCHED_NORMAL,
3864          * SCHED_BATCH and SCHED_IDLE is 0.
3865          */
3866         if (param->sched_priority < 0 ||
3867             (p->mm && param->sched_priority > MAX_USER_RT_PRIO-1) ||
3868             (!p->mm && param->sched_priority > MAX_RT_PRIO-1))
3869                 return -EINVAL;
3870         if (rt_policy(policy) != (param->sched_priority != 0))
3871                 return -EINVAL;
3872
3873         /*
3874          * Allow unprivileged RT tasks to decrease priority:
3875          */
3876         if (user && !capable(CAP_SYS_NICE)) {
3877                 if (rt_policy(policy)) {
3878                         unsigned long rlim_rtprio =
3879                                         task_rlimit(p, RLIMIT_RTPRIO);
3880
3881                         /* can't set/change the rt policy */
3882                         if (policy != p->policy && !rlim_rtprio)
3883                                 return -EPERM;
3884
3885                         /* can't increase priority */
3886                         if (param->sched_priority > p->rt_priority &&
3887                             param->sched_priority > rlim_rtprio)
3888                                 return -EPERM;
3889                 }
3890
3891                 /*
3892                  * Treat SCHED_IDLE as nice 20. Only allow a switch to
3893                  * SCHED_NORMAL if the RLIMIT_NICE would normally permit it.
3894                  */
3895                 if (p->policy == SCHED_IDLE && policy != SCHED_IDLE) {
3896                         if (!can_nice(p, TASK_NICE(p)))
3897                                 return -EPERM;
3898                 }
3899
3900                 /* can't change other user's priorities */
3901                 if (!check_same_owner(p))
3902                         return -EPERM;
3903
3904                 /* Normal users shall not reset the sched_reset_on_fork flag */
3905                 if (p->sched_reset_on_fork && !reset_on_fork)
3906                         return -EPERM;
3907         }
3908
3909         if (user) {
3910                 retval = security_task_setscheduler(p);
3911                 if (retval)
3912                         return retval;
3913         }
3914
3915         /*
3916          * make sure no PI-waiters arrive (or leave) while we are
3917          * changing the priority of the task:
3918          *
3919          * To be able to change p->policy safely, the appropriate
3920          * runqueue lock must be held.
3921          */
3922         rq = task_rq_lock(p, &flags);
3923
3924         /*
3925          * Changing the policy of the stop threads its a very bad idea
3926          */
3927         if (p == rq->stop) {
3928                 task_rq_unlock(rq, p, &flags);
3929                 return -EINVAL;
3930         }
3931
3932         /*
3933          * If not changing anything there's no need to proceed further:
3934          */
3935         if (unlikely(policy == p->policy && (!rt_policy(policy) ||
3936                         param->sched_priority == p->rt_priority))) {
3937                 task_rq_unlock(rq, p, &flags);
3938                 return 0;
3939         }
3940
3941 #ifdef CONFIG_RT_GROUP_SCHED
3942         if (user) {
3943                 /*
3944                  * Do not allow realtime tasks into groups that have no runtime
3945                  * assigned.
3946                  */
3947                 if (rt_bandwidth_enabled() && rt_policy(policy) &&
3948                                 task_group(p)->rt_bandwidth.rt_runtime == 0 &&
3949                                 !task_group_is_autogroup(task_group(p))) {
3950                         task_rq_unlock(rq, p, &flags);
3951                         return -EPERM;
3952                 }
3953         }
3954 #endif
3955
3956         /* recheck policy now with rq lock held */
3957         if (unlikely(oldpolicy != -1 && oldpolicy != p->policy)) {
3958                 policy = oldpolicy = -1;
3959                 task_rq_unlock(rq, p, &flags);
3960                 goto recheck;
3961         }
3962         on_rq = p->on_rq;
3963         running = task_current(rq, p);
3964         if (on_rq)
3965                 dequeue_task(rq, p, 0);
3966         if (running)
3967                 p->sched_class->put_prev_task(rq, p);
3968
3969         p->sched_reset_on_fork = reset_on_fork;
3970
3971         oldprio = p->prio;
3972         prev_class = p->sched_class;
3973         __setscheduler(rq, p, policy, param->sched_priority);
3974
3975         if (running)
3976                 p->sched_class->set_curr_task(rq);
3977         if (on_rq)
3978                 enqueue_task(rq, p, 0);
3979
3980         check_class_changed(rq, p, prev_class, oldprio);
3981         task_rq_unlock(rq, p, &flags);
3982
3983         rt_mutex_adjust_pi(p);
3984
3985         return 0;
3986 }
3987
3988 /**
3989  * sched_setscheduler - change the scheduling policy and/or RT priority of a thread.
3990  * @p: the task in question.
3991  * @policy: new policy.
3992  * @param: structure containing the new RT priority.
3993  *
3994  * NOTE that the task may be already dead.
3995  */
3996 int sched_setscheduler(struct task_struct *p, int policy,
3997                        const struct sched_param *param)
3998 {
3999         return __sched_setscheduler(p, policy, param, true);
4000 }
4001 EXPORT_SYMBOL_GPL(sched_setscheduler);
4002
4003 /**
4004  * sched_setscheduler_nocheck - change the scheduling policy and/or RT priority of a thread from kernelspace.
4005  * @p: the task in question.
4006  * @policy: new policy.
4007  * @param: structure containing the new RT priority.
4008  *
4009  * Just like sched_setscheduler, only don't bother checking if the
4010  * current context has permission.  For example, this is needed in
4011  * stop_machine(): we create temporary high priority worker threads,
4012  * but our caller might not have that capability.
4013  */
4014 int sched_setscheduler_nocheck(struct task_struct *p, int policy,
4015                                const struct sched_param *param)
4016 {
4017         return __sched_setscheduler(p, policy, param, false);
4018 }
4019
4020 static int
4021 do_sched_setscheduler(pid_t pid, int policy, struct sched_param __user *param)
4022 {
4023         struct sched_param lparam;
4024         struct task_struct *p;
4025         int retval;
4026
4027         if (!param || pid < 0)
4028                 return -EINVAL;
4029         if (copy_from_user(&lparam, param, sizeof(struct sched_param)))
4030                 return -EFAULT;
4031
4032         rcu_read_lock();
4033         retval = -ESRCH;
4034         p = find_process_by_pid(pid);
4035         if (p != NULL)
4036                 retval = sched_setscheduler(p, policy, &lparam);
4037         rcu_read_unlock();
4038
4039         return retval;
4040 }
4041
4042 /**
4043  * sys_sched_setscheduler - set/change the scheduler policy and RT priority
4044  * @pid: the pid in question.
4045  * @policy: new policy.
4046  * @param: structure containing the new RT priority.
4047  */
4048 SYSCALL_DEFINE3(sched_setscheduler, pid_t, pid, int, policy,
4049                 struct sched_param __user *, param)
4050 {
4051         /* negative values for policy are not valid */
4052         if (policy < 0)
4053                 return -EINVAL;
4054
4055         return do_sched_setscheduler(pid, policy, param);
4056 }
4057
4058 /**
4059  * sys_sched_setparam - set/change the RT priority of a thread
4060  * @pid: the pid in question.
4061  * @param: structure containing the new RT priority.
4062  */
4063 SYSCALL_DEFINE2(sched_setparam, pid_t, pid, struct sched_param __user *, param)
4064 {
4065         return do_sched_setscheduler(pid, -1, param);
4066 }
4067
4068 /**
4069  * sys_sched_getscheduler - get the policy (scheduling class) of a thread
4070  * @pid: the pid in question.
4071  */
4072 SYSCALL_DEFINE1(sched_getscheduler, pid_t, pid)
4073 {
4074         struct task_struct *p;
4075         int retval;
4076
4077         if (pid < 0)
4078                 return -EINVAL;
4079
4080         retval = -ESRCH;
4081         rcu_read_lock();
4082         p = find_process_by_pid(pid);
4083         if (p) {
4084                 retval = security_task_getscheduler(p);
4085                 if (!retval)
4086                         retval = p->policy
4087                                 | (p->sched_reset_on_fork ? SCHED_RESET_ON_FORK : 0);
4088         }
4089         rcu_read_unlock();
4090         return retval;
4091 }
4092
4093 /**
4094  * sys_sched_getparam - get the RT priority of a thread
4095  * @pid: the pid in question.
4096  * @param: structure containing the RT priority.
4097  */
4098 SYSCALL_DEFINE2(sched_getparam, pid_t, pid, struct sched_param __user *, param)
4099 {
4100         struct sched_param lp;
4101         struct task_struct *p;
4102         int retval;
4103
4104         if (!param || pid < 0)
4105                 return -EINVAL;
4106
4107         rcu_read_lock();
4108         p = find_process_by_pid(pid);
4109         retval = -ESRCH;
4110         if (!p)
4111                 goto out_unlock;
4112
4113         retval = security_task_getscheduler(p);
4114         if (retval)
4115                 goto out_unlock;
4116
4117         lp.sched_priority = p->rt_priority;
4118         rcu_read_unlock();
4119
4120         /*
4121          * This one might sleep, we cannot do it with a spinlock held ...
4122          */
4123         retval = copy_to_user(param, &lp, sizeof(*param)) ? -EFAULT : 0;
4124
4125         return retval;
4126
4127 out_unlock:
4128         rcu_read_unlock();
4129         return retval;
4130 }
4131
4132 long sched_setaffinity(pid_t pid, const struct cpumask *in_mask)
4133 {
4134         cpumask_var_t cpus_allowed, new_mask;
4135         struct task_struct *p;
4136         int retval;
4137
4138         get_online_cpus();
4139         rcu_read_lock();
4140
4141         p = find_process_by_pid(pid);
4142         if (!p) {
4143                 rcu_read_unlock();
4144                 put_online_cpus();
4145                 return -ESRCH;
4146         }
4147
4148         /* Prevent p going away */
4149         get_task_struct(p);
4150         rcu_read_unlock();
4151
4152         if (p->flags & PF_NO_SETAFFINITY) {
4153                 retval = -EINVAL;
4154                 goto out_put_task;
4155         }
4156         if (!alloc_cpumask_var(&cpus_allowed, GFP_KERNEL)) {
4157                 retval = -ENOMEM;
4158                 goto out_put_task;
4159         }
4160         if (!alloc_cpumask_var(&new_mask, GFP_KERNEL)) {
4161                 retval = -ENOMEM;
4162                 goto out_free_cpus_allowed;
4163         }
4164         retval = -EPERM;
4165         if (!check_same_owner(p)) {
4166                 rcu_read_lock();
4167                 if (!ns_capable(__task_cred(p)->user_ns, CAP_SYS_NICE)) {
4168                         rcu_read_unlock();
4169                         goto out_unlock;
4170                 }
4171                 rcu_read_unlock();
4172         }
4173
4174         retval = security_task_setscheduler(p);
4175         if (retval)
4176                 goto out_unlock;
4177
4178         cpuset_cpus_allowed(p, cpus_allowed);
4179         cpumask_and(new_mask, in_mask, cpus_allowed);
4180 again:
4181         retval = set_cpus_allowed_ptr(p, new_mask);
4182
4183         if (!retval) {
4184                 cpuset_cpus_allowed(p, cpus_allowed);
4185                 if (!cpumask_subset(new_mask, cpus_allowed)) {
4186                         /*
4187                          * We must have raced with a concurrent cpuset
4188                          * update. Just reset the cpus_allowed to the
4189                          * cpuset's cpus_allowed
4190                          */
4191                         cpumask_copy(new_mask, cpus_allowed);
4192                         goto again;
4193                 }
4194         }
4195 out_unlock:
4196         free_cpumask_var(new_mask);
4197 out_free_cpus_allowed:
4198         free_cpumask_var(cpus_allowed);
4199 out_put_task:
4200         put_task_struct(p);
4201         put_online_cpus();
4202         return retval;
4203 }
4204
4205 static int get_user_cpu_mask(unsigned long __user *user_mask_ptr, unsigned len,
4206                              struct cpumask *new_mask)
4207 {
4208         if (len < cpumask_size())
4209                 cpumask_clear(new_mask);
4210         else if (len > cpumask_size())
4211                 len = cpumask_size();
4212
4213         return copy_from_user(new_mask, user_mask_ptr, len) ? -EFAULT : 0;
4214 }
4215
4216 /**
4217  * sys_sched_setaffinity - set the cpu affinity of a process
4218  * @pid: pid of the process
4219  * @len: length in bytes of the bitmask pointed to by user_mask_ptr
4220  * @user_mask_ptr: user-space pointer to the new cpu mask
4221  */
4222 SYSCALL_DEFINE3(sched_setaffinity, pid_t, pid, unsigned int, len,
4223                 unsigned long __user *, user_mask_ptr)
4224 {
4225         cpumask_var_t new_mask;
4226         int retval;
4227
4228         if (!alloc_cpumask_var(&new_mask, GFP_KERNEL))
4229                 return -ENOMEM;
4230
4231         retval = get_user_cpu_mask(user_mask_ptr, len, new_mask);
4232         if (retval == 0)
4233                 retval = sched_setaffinity(pid, new_mask);
4234         free_cpumask_var(new_mask);
4235         return retval;
4236 }
4237
4238 long sched_getaffinity(pid_t pid, struct cpumask *mask)
4239 {
4240         struct task_struct *p;
4241         unsigned long flags;
4242         int retval;
4243
4244         get_online_cpus();
4245         rcu_read_lock();
4246
4247         retval = -ESRCH;
4248         p = find_process_by_pid(pid);
4249         if (!p)
4250                 goto out_unlock;
4251
4252         retval = security_task_getscheduler(p);
4253         if (retval)
4254                 goto out_unlock;
4255
4256         raw_spin_lock_irqsave(&p->pi_lock, flags);
4257         cpumask_and(mask, &p->cpus_allowed, cpu_online_mask);
4258         raw_spin_unlock_irqrestore(&p->pi_lock, flags);
4259
4260 out_unlock:
4261         rcu_read_unlock();
4262         put_online_cpus();
4263
4264         return retval;
4265 }
4266
4267 /**
4268  * sys_sched_getaffinity - get the cpu affinity of a process
4269  * @pid: pid of the process
4270  * @len: length in bytes of the bitmask pointed to by user_mask_ptr
4271  * @user_mask_ptr: user-space pointer to hold the current cpu mask
4272  */
4273 SYSCALL_DEFINE3(sched_getaffinity, pid_t, pid, unsigned int, len,
4274                 unsigned long __user *, user_mask_ptr)
4275 {
4276         int ret;
4277         cpumask_var_t mask;
4278
4279         if ((len * BITS_PER_BYTE) < nr_cpu_ids)
4280                 return -EINVAL;
4281         if (len & (sizeof(unsigned long)-1))
4282                 return -EINVAL;
4283
4284         if (!alloc_cpumask_var(&mask, GFP_KERNEL))
4285                 return -ENOMEM;
4286
4287         ret = sched_getaffinity(pid, mask);
4288         if (ret == 0) {
4289                 size_t retlen = min_t(size_t, len, cpumask_size());
4290
4291                 if (copy_to_user(user_mask_ptr, mask, retlen))
4292                         ret = -EFAULT;
4293                 else
4294                         ret = retlen;
4295         }
4296         free_cpumask_var(mask);
4297
4298         return ret;
4299 }
4300
4301 /**
4302  * sys_sched_yield - yield the current processor to other threads.
4303  *
4304  * This function yields the current CPU to other tasks. If there are no
4305  * other threads running on this CPU then this function will return.
4306  */
4307 SYSCALL_DEFINE0(sched_yield)
4308 {
4309         struct rq *rq = this_rq_lock();
4310
4311         schedstat_inc(rq, yld_count);
4312         current->sched_class->yield_task(rq);
4313
4314         /*
4315          * Since we are going to call schedule() anyway, there's
4316          * no need to preempt or enable interrupts:
4317          */
4318         __release(rq->lock);
4319         spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
4320         do_raw_spin_unlock(&rq->lock);
4321         sched_preempt_enable_no_resched();
4322
4323         schedule();
4324
4325         return 0;
4326 }
4327
4328 static inline int should_resched(void)
4329 {
4330         return need_resched() && !(preempt_count() & PREEMPT_ACTIVE);
4331 }
4332
4333 static void __cond_resched(void)
4334 {
4335         add_preempt_count(PREEMPT_ACTIVE);
4336         __schedule();
4337         sub_preempt_count(PREEMPT_ACTIVE);
4338 }
4339
4340 int __sched _cond_resched(void)
4341 {
4342         if (should_resched()) {
4343                 __cond_resched();
4344                 return 1;
4345         }
4346         return 0;
4347 }
4348 EXPORT_SYMBOL(_cond_resched);
4349
4350 /*
4351  * __cond_resched_lock() - if a reschedule is pending, drop the given lock,
4352  * call schedule, and on return reacquire the lock.
4353  *
4354  * This works OK both with and without CONFIG_PREEMPT. We do strange low-level
4355  * operations here to prevent schedule() from being called twice (once via
4356  * spin_unlock(), once by hand).
4357  */
4358 int __cond_resched_lock(spinlock_t *lock)
4359 {
4360         int resched = should_resched();
4361         int ret = 0;
4362
4363         lockdep_assert_held(lock);
4364
4365         if (spin_needbreak(lock) || resched) {
4366                 spin_unlock(lock);
4367                 if (resched)
4368                         __cond_resched();
4369                 else
4370                         cpu_relax();
4371                 ret = 1;
4372                 spin_lock(lock);
4373         }
4374         return ret;
4375 }
4376 EXPORT_SYMBOL(__cond_resched_lock);
4377
4378 int __sched __cond_resched_softirq(void)
4379 {
4380         BUG_ON(!in_softirq());
4381
4382         if (should_resched()) {
4383                 local_bh_enable();
4384                 __cond_resched();
4385                 local_bh_disable();
4386                 return 1;
4387         }
4388         return 0;
4389 }
4390 EXPORT_SYMBOL(__cond_resched_softirq);
4391
4392 /**
4393  * yield - yield the current processor to other threads.
4394  *
4395  * Do not ever use this function, there's a 99% chance you're doing it wrong.
4396  *
4397  * The scheduler is at all times free to pick the calling task as the most
4398  * eligible task to run, if removing the yield() call from your code breaks
4399  * it, its already broken.
4400  *
4401  * Typical broken usage is:
4402  *
4403  * while (!event)
4404  *      yield();
4405  *
4406  * where one assumes that yield() will let 'the other' process run that will
4407  * make event true. If the current task is a SCHED_FIFO task that will never
4408  * happen. Never use yield() as a progress guarantee!!
4409  *
4410  * If you want to use yield() to wait for something, use wait_event().
4411  * If you want to use yield() to be 'nice' for others, use cond_resched().
4412  * If you still want to use yield(), do not!
4413  */
4414 void __sched yield(void)
4415 {
4416         set_current_state(TASK_RUNNING);
4417         sys_sched_yield();
4418 }
4419 EXPORT_SYMBOL(yield);
4420
4421 /**
4422  * yield_to - yield the current processor to another thread in
4423  * your thread group, or accelerate that thread toward the
4424  * processor it's on.
4425  * @p: target task
4426  * @preempt: whether task preemption is allowed or not
4427  *
4428  * It's the caller's job to ensure that the target task struct
4429  * can't go away on us before we can do any checks.
4430  *
4431  * Returns:
4432  *      true (>0) if we indeed boosted the target task.
4433  *      false (0) if we failed to boost the target.
4434  *      -ESRCH if there's no task to yield to.
4435  */
4436 bool __sched yield_to(struct task_struct *p, bool preempt)
4437 {
4438         struct task_struct *curr = current;
4439         struct rq *rq, *p_rq;
4440         unsigned long flags;
4441         int yielded = 0;
4442
4443         local_irq_save(flags);
4444         rq = this_rq();
4445
4446 again:
4447         p_rq = task_rq(p);
4448         /*
4449          * If we're the only runnable task on the rq and target rq also
4450          * has only one task, there's absolutely no point in yielding.
4451          */
4452         if (rq->nr_running == 1 && p_rq->nr_running == 1) {
4453                 yielded = -ESRCH;
4454                 goto out_irq;
4455         }
4456
4457         double_rq_lock(rq, p_rq);
4458         while (task_rq(p) != p_rq) {
4459                 double_rq_unlock(rq, p_rq);
4460                 goto again;
4461         }
4462
4463         if (!curr->sched_class->yield_to_task)
4464                 goto out_unlock;
4465
4466         if (curr->sched_class != p->sched_class)
4467                 goto out_unlock;
4468
4469         if (task_running(p_rq, p) || p->state)
4470                 goto out_unlock;
4471
4472         yielded = curr->sched_class->yield_to_task(rq, p, preempt);
4473         if (yielded) {
4474                 schedstat_inc(rq, yld_count);
4475                 /*
4476                  * Make p's CPU reschedule; pick_next_entity takes care of
4477                  * fairness.
4478                  */
4479                 if (preempt && rq != p_rq)
4480                         resched_task(p_rq->curr);
4481         }
4482
4483 out_unlock:
4484         double_rq_unlock(rq, p_rq);
4485 out_irq:
4486         local_irq_restore(flags);
4487
4488         if (yielded > 0)
4489                 schedule();
4490
4491         return yielded;
4492 }
4493 EXPORT_SYMBOL_GPL(yield_to);
4494
4495 /*
4496  * This task is about to go to sleep on IO. Increment rq->nr_iowait so
4497  * that process accounting knows that this is a task in IO wait state.
4498  */
4499 void __sched io_schedule(void)
4500 {
4501         struct rq *rq = raw_rq();
4502
4503         delayacct_blkio_start();
4504         atomic_inc(&rq->nr_iowait);
4505         blk_flush_plug(current);
4506         current->in_iowait = 1;
4507         schedule();
4508         current->in_iowait = 0;
4509         atomic_dec(&rq->nr_iowait);
4510         delayacct_blkio_end();
4511 }
4512 EXPORT_SYMBOL(io_schedule);
4513
4514 long __sched io_schedule_timeout(long timeout)
4515 {
4516         struct rq *rq = raw_rq();
4517         long ret;
4518
4519         delayacct_blkio_start();
4520         atomic_inc(&rq->nr_iowait);
4521         blk_flush_plug(current);
4522         current->in_iowait = 1;
4523         ret = schedule_timeout(timeout);
4524         current->in_iowait = 0;
4525         atomic_dec(&rq->nr_iowait);
4526         delayacct_blkio_end();
4527         return ret;
4528 }
4529
4530 /**
4531  * sys_sched_get_priority_max - return maximum RT priority.
4532  * @policy: scheduling class.
4533  *
4534  * this syscall returns the maximum rt_priority that can be used
4535  * by a given scheduling class.
4536  */
4537 SYSCALL_DEFINE1(sched_get_priority_max, int, policy)
4538 {
4539         int ret = -EINVAL;
4540
4541         switch (policy) {
4542         case SCHED_FIFO:
4543         case SCHED_RR:
4544                 ret = MAX_USER_RT_PRIO-1;
4545                 break;
4546         case SCHED_NORMAL:
4547         case SCHED_BATCH:
4548         case SCHED_IDLE:
4549                 ret = 0;
4550                 break;
4551         }
4552         return ret;
4553 }
4554
4555 /**
4556  * sys_sched_get_priority_min - return minimum RT priority.
4557  * @policy: scheduling class.
4558  *
4559  * this syscall returns the minimum rt_priority that can be used
4560  * by a given scheduling class.
4561  */
4562 SYSCALL_DEFINE1(sched_get_priority_min, int, policy)
4563 {
4564         int ret = -EINVAL;
4565
4566         switch (policy) {
4567         case SCHED_FIFO:
4568         case SCHED_RR:
4569                 ret = 1;
4570                 break;
4571         case SCHED_NORMAL:
4572         case SCHED_BATCH:
4573         case SCHED_IDLE:
4574                 ret = 0;
4575         }
4576         return ret;
4577 }
4578
4579 /**
4580  * sys_sched_rr_get_interval - return the default timeslice of a process.
4581  * @pid: pid of the process.
4582  * @interval: userspace pointer to the timeslice value.
4583  *
4584  * this syscall writes the default timeslice value of a given process
4585  * into the user-space timespec buffer. A value of '0' means infinity.
4586  */
4587 SYSCALL_DEFINE2(sched_rr_get_interval, pid_t, pid,
4588                 struct timespec __user *, interval)
4589 {
4590         struct task_struct *p;
4591         unsigned int time_slice;
4592         unsigned long flags;
4593         struct rq *rq;
4594         int retval;
4595         struct timespec t;
4596
4597         if (pid < 0)
4598                 return -EINVAL;
4599
4600         retval = -ESRCH;
4601         rcu_read_lock();
4602         p = find_process_by_pid(pid);
4603         if (!p)
4604                 goto out_unlock;
4605
4606         retval = security_task_getscheduler(p);
4607         if (retval)
4608                 goto out_unlock;
4609
4610         rq = task_rq_lock(p, &flags);
4611         time_slice = p->sched_class->get_rr_interval(rq, p);
4612         task_rq_unlock(rq, p, &flags);
4613
4614         rcu_read_unlock();
4615         jiffies_to_timespec(time_slice, &t);
4616         retval = copy_to_user(interval, &t, sizeof(t)) ? -EFAULT : 0;
4617         return retval;
4618
4619 out_unlock:
4620         rcu_read_unlock();
4621         return retval;
4622 }
4623
4624 static const char stat_nam[] = TASK_STATE_TO_CHAR_STR;
4625
4626 void sched_show_task(struct task_struct *p)
4627 {
4628         unsigned long free = 0;
4629         int ppid;
4630         unsigned state;
4631
4632         state = p->state ? __ffs(p->state) + 1 : 0;
4633         printk(KERN_INFO "%-15.15s %c", p->comm,
4634                 state < sizeof(stat_nam) - 1 ? stat_nam[state] : '?');
4635 #if BITS_PER_LONG == 32
4636         if (state == TASK_RUNNING)
4637                 printk(KERN_CONT " running  ");
4638         else
4639                 printk(KERN_CONT " %08lx ", thread_saved_pc(p));
4640 #else
4641         if (state == TASK_RUNNING)
4642                 printk(KERN_CONT "  running task    ");
4643         else
4644                 printk(KERN_CONT " %016lx ", thread_saved_pc(p));
4645 #endif
4646 #ifdef CONFIG_DEBUG_STACK_USAGE
4647         free = stack_not_used(p);
4648 #endif
4649         rcu_read_lock();
4650         ppid = task_pid_nr(rcu_dereference(p->real_parent));
4651         rcu_read_unlock();
4652         printk(KERN_CONT "%5lu %5d %6d 0x%08lx\n", free,
4653                 task_pid_nr(p), ppid,
4654                 (unsigned long)task_thread_info(p)->flags);
4655
4656         print_worker_info(KERN_INFO, p);
4657         show_stack(p, NULL);
4658 }
4659
4660 void show_state_filter(unsigned long state_filter)
4661 {
4662         struct task_struct *g, *p;
4663
4664 #if BITS_PER_LONG == 32
4665         printk(KERN_INFO
4666                 "  task                PC stack   pid father\n");
4667 #else
4668         printk(KERN_INFO
4669                 "  task                        PC stack   pid father\n");
4670 #endif
4671         rcu_read_lock();
4672         do_each_thread(g, p) {
4673                 /*
4674                  * reset the NMI-timeout, listing all files on a slow
4675                  * console might take a lot of time:
4676                  */
4677                 touch_nmi_watchdog();
4678                 if (!state_filter || (p->state & state_filter))
4679                         sched_show_task(p);
4680         } while_each_thread(g, p);
4681
4682         touch_all_softlockup_watchdogs();
4683
4684 #ifdef CONFIG_SCHED_DEBUG
4685         sysrq_sched_debug_show();
4686 #endif
4687         rcu_read_unlock();
4688         /*
4689          * Only show locks if all tasks are dumped:
4690          */
4691         if (!state_filter)
4692                 debug_show_all_locks();
4693 }
4694
4695 void __cpuinit init_idle_bootup_task(struct task_struct *idle)
4696 {
4697         idle->sched_class = &idle_sched_class;
4698 }
4699
4700 /**
4701  * init_idle - set up an idle thread for a given CPU
4702  * @idle: task in question
4703  * @cpu: cpu the idle task belongs to
4704  *
4705  * NOTE: this function does not set the idle thread's NEED_RESCHED
4706  * flag, to make booting more robust.
4707  */
4708 void __cpuinit init_idle(struct task_struct *idle, int cpu)
4709 {
4710         struct rq *rq = cpu_rq(cpu);
4711         unsigned long flags;
4712
4713         raw_spin_lock_irqsave(&rq->lock, flags);
4714
4715         __sched_fork(idle);
4716         idle->state = TASK_RUNNING;
4717         idle->se.exec_start = sched_clock();
4718
4719         do_set_cpus_allowed(idle, cpumask_of(cpu));
4720         /*
4721          * We're having a chicken and egg problem, even though we are
4722          * holding rq->lock, the cpu isn't yet set to this cpu so the
4723          * lockdep check in task_group() will fail.
4724          *
4725          * Similar case to sched_fork(). / Alternatively we could
4726          * use task_rq_lock() here and obtain the other rq->lock.
4727          *
4728          * Silence PROVE_RCU
4729          */
4730         rcu_read_lock();
4731         __set_task_cpu(idle, cpu);
4732         rcu_read_unlock();
4733
4734         rq->curr = rq->idle = idle;
4735 #if defined(CONFIG_SMP)
4736         idle->on_cpu = 1;
4737 #endif
4738         raw_spin_unlock_irqrestore(&rq->lock, flags);
4739
4740         /* Set the preempt count _outside_ the spinlocks! */
4741         task_thread_info(idle)->preempt_count = 0;
4742
4743         /*
4744          * The idle tasks have their own, simple scheduling class:
4745          */
4746         idle->sched_class = &idle_sched_class;
4747         ftrace_graph_init_idle_task(idle, cpu);
4748         vtime_init_idle(idle);
4749 #if defined(CONFIG_SMP)
4750         sprintf(idle->comm, "%s/%d", INIT_TASK_COMM, cpu);
4751 #endif
4752 }
4753
4754 #ifdef CONFIG_SMP
4755 void do_set_cpus_allowed(struct task_struct *p, const struct cpumask *new_mask)
4756 {
4757         if (p->sched_class && p->sched_class->set_cpus_allowed)
4758                 p->sched_class->set_cpus_allowed(p, new_mask);
4759
4760         cpumask_copy(&p->cpus_allowed, new_mask);
4761         p->nr_cpus_allowed = cpumask_weight(new_mask);
4762 }
4763
4764 /*
4765  * This is how migration works:
4766  *
4767  * 1) we invoke migration_cpu_stop() on the target CPU using
4768  *    stop_one_cpu().
4769  * 2) stopper starts to run (implicitly forcing the migrated thread
4770  *    off the CPU)
4771  * 3) it checks whether the migrated task is still in the wrong runqueue.
4772  * 4) if it's in the wrong runqueue then the migration thread removes
4773  *    it and puts it into the right queue.
4774  * 5) stopper completes and stop_one_cpu() returns and the migration
4775  *    is done.
4776  */
4777
4778 /*
4779  * Change a given task's CPU affinity. Migrate the thread to a
4780  * proper CPU and schedule it away if the CPU it's executing on
4781  * is removed from the allowed bitmask.
4782  *
4783  * NOTE: the caller must have a valid reference to the task, the
4784  * task must not exit() & deallocate itself prematurely. The
4785  * call is not atomic; no spinlocks may be held.
4786  */
4787 int set_cpus_allowed_ptr(struct task_struct *p, const struct cpumask *new_mask)
4788 {
4789         unsigned long flags;
4790         struct rq *rq;
4791         unsigned int dest_cpu;
4792         int ret = 0;
4793
4794         rq = task_rq_lock(p, &flags);
4795
4796         if (cpumask_equal(&p->cpus_allowed, new_mask))
4797                 goto out;
4798
4799         if (!cpumask_intersects(new_mask, cpu_active_mask)) {
4800                 ret = -EINVAL;
4801                 goto out;
4802         }
4803
4804         do_set_cpus_allowed(p, new_mask);
4805
4806         /* Can the task run on the task's current CPU? If so, we're done */
4807         if (cpumask_test_cpu(task_cpu(p), new_mask))
4808                 goto out;
4809
4810         dest_cpu = cpumask_any_and(cpu_active_mask, new_mask);
4811         if (p->on_rq) {
4812                 struct migration_arg arg = { p, dest_cpu };
4813                 /* Need help from migration thread: drop lock and wait. */
4814                 task_rq_unlock(rq, p, &flags);
4815                 stop_one_cpu(cpu_of(rq), migration_cpu_stop, &arg);
4816                 tlb_migrate_finish(p->mm);
4817                 return 0;
4818         }
4819 out:
4820         task_rq_unlock(rq, p, &flags);
4821
4822         return ret;
4823 }
4824 EXPORT_SYMBOL_GPL(set_cpus_allowed_ptr);
4825
4826 /*
4827  * Move (not current) task off this cpu, onto dest cpu. We're doing
4828  * this because either it can't run here any more (set_cpus_allowed()
4829  * away from this CPU, or CPU going down), or because we're
4830  * attempting to rebalance this task on exec (sched_exec).
4831  *
4832  * So we race with normal scheduler movements, but that's OK, as long
4833  * as the task is no longer on this CPU.
4834  *
4835  * Returns non-zero if task was successfully migrated.
4836  */
4837 static int __migrate_task(struct task_struct *p, int src_cpu, int dest_cpu)
4838 {
4839         struct rq *rq_dest, *rq_src;
4840         int ret = 0;
4841
4842         if (unlikely(!cpu_active(dest_cpu)))
4843                 return ret;
4844
4845         rq_src = cpu_rq(src_cpu);
4846         rq_dest = cpu_rq(dest_cpu);
4847
4848         raw_spin_lock(&p->pi_lock);
4849         double_rq_lock(rq_src, rq_dest);
4850         /* Already moved. */
4851         if (task_cpu(p) != src_cpu)
4852                 goto done;
4853         /* Affinity changed (again). */
4854         if (!cpumask_test_cpu(dest_cpu, tsk_cpus_allowed(p)))
4855                 goto fail;
4856
4857         /*
4858          * If we're not on a rq, the next wake-up will ensure we're
4859          * placed properly.
4860          */
4861         if (p->on_rq) {
4862                 dequeue_task(rq_src, p, 0);
4863                 set_task_cpu(p, dest_cpu);
4864                 enqueue_task(rq_dest, p, 0);
4865                 check_preempt_curr(rq_dest, p, 0);
4866         }
4867 done:
4868         ret = 1;
4869 fail:
4870         double_rq_unlock(rq_src, rq_dest);
4871         raw_spin_unlock(&p->pi_lock);
4872         return ret;
4873 }
4874
4875 /*
4876  * migration_cpu_stop - this will be executed by a highprio stopper thread
4877  * and performs thread migration by bumping thread off CPU then
4878  * 'pushing' onto another runqueue.
4879  */
4880 static int migration_cpu_stop(void *data)
4881 {
4882         struct migration_arg *arg = data;
4883
4884         /*
4885          * The original target cpu might have gone down and we might
4886          * be on another cpu but it doesn't matter.
4887          */
4888         local_irq_disable();
4889         __migrate_task(arg->task, raw_smp_processor_id(), arg->dest_cpu);
4890         local_irq_enable();
4891         return 0;
4892 }
4893
4894 #ifdef CONFIG_HOTPLUG_CPU
4895
4896 /*
4897  * Ensures that the idle task is using init_mm right before its cpu goes
4898  * offline.
4899  */
4900 void idle_task_exit(void)
4901 {
4902         struct mm_struct *mm = current->active_mm;
4903
4904         BUG_ON(cpu_online(smp_processor_id()));
4905
4906         if (mm != &init_mm)
4907                 switch_mm(mm, &init_mm, current);
4908         mmdrop(mm);
4909 }
4910
4911 /*
4912  * Since this CPU is going 'away' for a while, fold any nr_active delta
4913  * we might have. Assumes we're called after migrate_tasks() so that the
4914  * nr_active count is stable.
4915  *
4916  * Also see the comment "Global load-average calculations".
4917  */
4918 static void calc_load_migrate(struct rq *rq)
4919 {
4920         long delta = calc_load_fold_active(rq);
4921         if (delta)
4922                 atomic_long_add(delta, &calc_load_tasks);
4923 }
4924
4925 /*
4926  * Migrate all tasks from the rq, sleeping tasks will be migrated by
4927  * try_to_wake_up()->select_task_rq().
4928  *
4929  * Called with rq->lock held even though we'er in stop_machine() and
4930  * there's no concurrency possible, we hold the required locks anyway
4931  * because of lock validation efforts.
4932  */
4933 static void migrate_tasks(unsigned int dead_cpu)
4934 {
4935         struct rq *rq = cpu_rq(dead_cpu);
4936         struct task_struct *next, *stop = rq->stop;
4937         int dest_cpu;
4938
4939         /*
4940          * Fudge the rq selection such that the below task selection loop
4941          * doesn't get stuck on the currently eligible stop task.
4942          *
4943          * We're currently inside stop_machine() and the rq is either stuck
4944          * in the stop_machine_cpu_stop() loop, or we're executing this code,
4945          * either way we should never end up calling schedule() until we're
4946          * done here.
4947          */
4948         rq->stop = NULL;
4949
4950         for ( ; ; ) {
4951                 /*
4952                  * There's this thread running, bail when that's the only
4953                  * remaining thread.
4954                  */
4955                 if (rq->nr_running == 1)
4956                         break;
4957
4958                 next = pick_next_task(rq);
4959                 BUG_ON(!next);
4960                 next->sched_class->put_prev_task(rq, next);
4961
4962                 /* Find suitable destination for @next, with force if needed. */
4963                 dest_cpu = select_fallback_rq(dead_cpu, next);
4964                 raw_spin_unlock(&rq->lock);
4965
4966                 __migrate_task(next, dead_cpu, dest_cpu);
4967
4968                 raw_spin_lock(&rq->lock);
4969         }
4970
4971         rq->stop = stop;
4972 }
4973
4974 #endif /* CONFIG_HOTPLUG_CPU */
4975
4976 #if defined(CONFIG_SCHED_DEBUG) && defined(CONFIG_SYSCTL)
4977
4978 static struct ctl_table sd_ctl_dir[] = {
4979         {
4980                 .procname       = "sched_domain",
4981                 .mode           = 0555,
4982         },
4983         {}
4984 };
4985
4986 static struct ctl_table sd_ctl_root[] = {
4987         {
4988                 .procname       = "kernel",
4989                 .mode           = 0555,
4990                 .child          = sd_ctl_dir,
4991         },
4992         {}
4993 };
4994
4995 static struct ctl_table *sd_alloc_ctl_entry(int n)
4996 {
4997         struct ctl_table *entry =
4998                 kcalloc(n, sizeof(struct ctl_table), GFP_KERNEL);
4999
5000         return entry;
5001 }
5002
5003 static void sd_free_ctl_entry(struct ctl_table **tablep)
5004 {
5005         struct ctl_table *entry;
5006
5007         /*
5008          * In the intermediate directories, both the child directory and
5009          * procname are dynamically allocated and could fail but the mode
5010          * will always be set. In the lowest directory the names are
5011          * static strings and all have proc handlers.
5012          */
5013         for (entry = *tablep; entry->mode; entry++) {
5014                 if (entry->child)
5015                         sd_free_ctl_entry(&entry->child);
5016                 if (entry->proc_handler == NULL)
5017                         kfree(entry->procname);
5018         }
5019
5020         kfree(*tablep);
5021         *tablep = NULL;
5022 }
5023
5024 static int min_load_idx = 0;
5025 static int max_load_idx = CPU_LOAD_IDX_MAX-1;
5026
5027 static void
5028 set_table_entry(struct ctl_table *entry,
5029                 const char *procname, void *data, int maxlen,
5030                 umode_t mode, proc_handler *proc_handler,
5031                 bool load_idx)
5032 {
5033         entry->procname = procname;
5034         entry->data = data;
5035         entry->maxlen = maxlen;
5036         entry->mode = mode;
5037         entry->proc_handler = proc_handler;
5038
5039         if (load_idx) {
5040                 entry->extra1 = &min_load_idx;
5041                 entry->extra2 = &max_load_idx;
5042         }
5043 }
5044
5045 static struct ctl_table *
5046 sd_alloc_ctl_domain_table(struct sched_domain *sd)
5047 {
5048         struct ctl_table *table = sd_alloc_ctl_entry(13);
5049
5050         if (table == NULL)
5051                 return NULL;
5052
5053         set_table_entry(&table[0], "min_interval", &sd->min_interval,
5054                 sizeof(long), 0644, proc_doulongvec_minmax, false);
5055         set_table_entry(&table[1], "max_interval", &sd->max_interval,
5056                 sizeof(long), 0644, proc_doulongvec_minmax, false);
5057         set_table_entry(&table[2], "busy_idx", &sd->busy_idx,
5058                 sizeof(int), 0644, proc_dointvec_minmax, true);
5059         set_table_entry(&table[3], "idle_idx", &sd->idle_idx,
5060                 sizeof(int), 0644, proc_dointvec_minmax, true);
5061         set_table_entry(&table[4], "newidle_idx", &sd->newidle_idx,
5062                 sizeof(int), 0644, proc_dointvec_minmax, true);
5063         set_table_entry(&table[5], "wake_idx", &sd->wake_idx,
5064                 sizeof(int), 0644, proc_dointvec_minmax, true);
5065         set_table_entry(&table[6], "forkexec_idx", &sd->forkexec_idx,
5066                 sizeof(int), 0644, proc_dointvec_minmax, true);
5067         set_table_entry(&table[7], "busy_factor", &sd->busy_factor,
5068                 sizeof(int), 0644, proc_dointvec_minmax, false);
5069         set_table_entry(&table[8], "imbalance_pct", &sd->imbalance_pct,
5070                 sizeof(int), 0644, proc_dointvec_minmax, false);
5071         set_table_entry(&table[9], "cache_nice_tries",
5072                 &sd->cache_nice_tries,
5073                 sizeof(int), 0644, proc_dointvec_minmax, false);
5074         set_table_entry(&table[10], "flags", &sd->flags,
5075                 sizeof(int), 0644, proc_dointvec_minmax, false);
5076         set_table_entry(&table[11], "name", sd->name,
5077                 CORENAME_MAX_SIZE, 0444, proc_dostring, false);
5078         /* &table[12] is terminator */
5079
5080         return table;
5081 }
5082
5083 static ctl_table *sd_alloc_ctl_cpu_table(int cpu)
5084 {
5085         struct ctl_table *entry, *table;
5086         struct sched_domain *sd;
5087         int domain_num = 0, i;
5088         char buf[32];
5089
5090         for_each_domain(cpu, sd)
5091                 domain_num++;
5092         entry = table = sd_alloc_ctl_entry(domain_num + 1);
5093         if (table == NULL)
5094                 return NULL;
5095
5096         i = 0;
5097         for_each_domain(cpu, sd) {
5098                 snprintf(buf, 32, "domain%d", i);
5099                 entry->procname = kstrdup(buf, GFP_KERNEL);
5100                 entry->mode = 0555;
5101                 entry->child = sd_alloc_ctl_domain_table(sd);
5102                 entry++;
5103                 i++;
5104         }
5105         return table;
5106 }
5107
5108 static struct ctl_table_header *sd_sysctl_header;
5109 static void register_sched_domain_sysctl(void)
5110 {
5111         int i, cpu_num = num_possible_cpus();
5112         struct ctl_table *entry = sd_alloc_ctl_entry(cpu_num + 1);
5113         char buf[32];
5114
5115         WARN_ON(sd_ctl_dir[0].child);
5116         sd_ctl_dir[0].child = entry;
5117
5118         if (entry == NULL)
5119                 return;
5120
5121         for_each_possible_cpu(i) {
5122                 snprintf(buf, 32, "cpu%d", i);
5123                 entry->procname = kstrdup(buf, GFP_KERNEL);
5124                 entry->mode = 0555;
5125                 entry->child = sd_alloc_ctl_cpu_table(i);
5126                 entry++;
5127         }
5128
5129         WARN_ON(sd_sysctl_header);
5130         sd_sysctl_header = register_sysctl_table(sd_ctl_root);
5131 }
5132
5133 /* may be called multiple times per register */
5134 static void unregister_sched_domain_sysctl(void)
5135 {
5136         if (sd_sysctl_header)
5137                 unregister_sysctl_table(sd_sysctl_header);
5138         sd_sysctl_header = NULL;
5139         if (sd_ctl_dir[0].child)
5140                 sd_free_ctl_entry(&sd_ctl_dir[0].child);
5141 }
5142 #else
5143 static void register_sched_domain_sysctl(void)
5144 {
5145 }
5146 static void unregister_sched_domain_sysctl(void)
5147 {
5148 }
5149 #endif
5150
5151 static void set_rq_online(struct rq *rq)
5152 {
5153         if (!rq->online) {
5154                 const struct sched_class *class;
5155
5156                 cpumask_set_cpu(rq->cpu, rq->rd->online);
5157                 rq->online = 1;
5158
5159                 for_each_class(class) {
5160                         if (class->rq_online)
5161                                 class->rq_online(rq);
5162                 }
5163         }
5164 }
5165
5166 static void set_rq_offline(struct rq *rq)
5167 {
5168         if (rq->online) {
5169                 const struct sched_class *class;
5170
5171                 for_each_class(class) {
5172                         if (class->rq_offline)
5173                                 class->rq_offline(rq);
5174                 }
5175
5176                 cpumask_clear_cpu(rq->cpu, rq->rd->online);
5177                 rq->online = 0;
5178         }
5179 }
5180
5181 /*
5182  * migration_call - callback that gets triggered when a CPU is added.
5183  * Here we can start up the necessary migration thread for the new CPU.
5184  */
5185 static int __cpuinit
5186 migration_call(struct notifier_block *nfb, unsigned long action, void *hcpu)
5187 {
5188         int cpu = (long)hcpu;
5189         unsigned long flags;
5190         struct rq *rq = cpu_rq(cpu);
5191
5192         switch (action & ~CPU_TASKS_FROZEN) {
5193
5194         case CPU_UP_PREPARE:
5195                 rq->calc_load_update = calc_load_update;
5196                 break;
5197
5198         case CPU_ONLINE:
5199                 /* Update our root-domain */
5200                 raw_spin_lock_irqsave(&rq->lock, flags);
5201                 if (rq->rd) {
5202                         BUG_ON(!cpumask_test_cpu(cpu, rq->rd->span));
5203
5204                         set_rq_online(rq);
5205                 }
5206                 raw_spin_unlock_irqrestore(&rq->lock, flags);
5207                 break;
5208
5209 #ifdef CONFIG_HOTPLUG_CPU
5210         case CPU_DYING:
5211                 sched_ttwu_pending();
5212                 /* Update our root-domain */
5213                 raw_spin_lock_irqsave(&rq->lock, flags);
5214                 if (rq->rd) {
5215                         BUG_ON(!cpumask_test_cpu(cpu, rq->rd->span));
5216                         set_rq_offline(rq);
5217                 }
5218                 migrate_tasks(cpu);
5219                 BUG_ON(rq->nr_running != 1); /* the migration thread */
5220                 raw_spin_unlock_irqrestore(&rq->lock, flags);
5221                 break;
5222
5223         case CPU_DEAD:
5224                 calc_load_migrate(rq);
5225                 break;
5226 #endif
5227         }
5228
5229         update_max_interval();
5230
5231         return NOTIFY_OK;
5232 }
5233
5234 /*
5235  * Register at high priority so that task migration (migrate_all_tasks)
5236  * happens before everything else.  This has to be lower priority than
5237  * the notifier in the perf_event subsystem, though.
5238  */
5239 static struct notifier_block __cpuinitdata migration_notifier = {
5240         .notifier_call = migration_call,
5241         .priority = CPU_PRI_MIGRATION,
5242 };
5243
5244 static int __cpuinit sched_cpu_active(struct notifier_block *nfb,
5245                                       unsigned long action, void *hcpu)
5246 {
5247         switch (action & ~CPU_TASKS_FROZEN) {
5248         case CPU_STARTING:
5249         case CPU_DOWN_FAILED:
5250                 set_cpu_active((long)hcpu, true);
5251                 return NOTIFY_OK;
5252         default:
5253                 return NOTIFY_DONE;
5254         }
5255 }
5256
5257 static int __cpuinit sched_cpu_inactive(struct notifier_block *nfb,
5258                                         unsigned long action, void *hcpu)
5259 {
5260         switch (action & ~CPU_TASKS_FROZEN) {
5261         case CPU_DOWN_PREPARE:
5262                 set_cpu_active((long)hcpu, false);
5263                 return NOTIFY_OK;
5264         default:
5265                 return NOTIFY_DONE;
5266         }
5267 }
5268
5269 static int __init migration_init(void)
5270 {
5271         void *cpu = (void *)(long)smp_processor_id();
5272         int err;
5273
5274         /* Initialize migration for the boot CPU */
5275         err = migration_call(&migration_notifier, CPU_UP_PREPARE, cpu);
5276         BUG_ON(err == NOTIFY_BAD);
5277         migration_call(&migration_notifier, CPU_ONLINE, cpu);
5278         register_cpu_notifier(&migration_notifier);
5279
5280         /* Register cpu active notifiers */
5281         cpu_notifier(sched_cpu_active, CPU_PRI_SCHED_ACTIVE);
5282         cpu_notifier(sched_cpu_inactive, CPU_PRI_SCHED_INACTIVE);
5283
5284         return 0;
5285 }
5286 early_initcall(migration_init);
5287 #endif
5288
5289 #ifdef CONFIG_SMP
5290
5291 static cpumask_var_t sched_domains_tmpmask; /* sched_domains_mutex */
5292
5293 #ifdef CONFIG_SCHED_DEBUG
5294
5295 static __read_mostly int sched_debug_enabled;
5296
5297 static int __init sched_debug_setup(char *str)
5298 {
5299         sched_debug_enabled = 1;
5300
5301         return 0;
5302 }
5303 early_param("sched_debug", sched_debug_setup);
5304
5305 static inline bool sched_debug(void)
5306 {
5307         return sched_debug_enabled;
5308 }
5309
5310 static int sched_domain_debug_one(struct sched_domain *sd, int cpu, int level,
5311                                   struct cpumask *groupmask)
5312 {
5313         struct sched_group *group = sd->groups;
5314         char str[256];
5315
5316         cpulist_scnprintf(str, sizeof(str), sched_domain_span(sd));
5317         cpumask_clear(groupmask);
5318
5319         printk(KERN_DEBUG "%*s domain %d: ", level, "", level);
5320
5321         if (!(sd->flags & SD_LOAD_BALANCE)) {
5322                 printk("does not load-balance\n");
5323                 if (sd->parent)
5324                         printk(KERN_ERR "ERROR: !SD_LOAD_BALANCE domain"
5325                                         " has parent");
5326                 return -1;
5327         }
5328
5329         printk(KERN_CONT "span %s level %s\n", str, sd->name);
5330
5331         if (!cpumask_test_cpu(cpu, sched_domain_span(sd))) {
5332                 printk(KERN_ERR "ERROR: domain->span does not contain "
5333                                 "CPU%d\n", cpu);
5334         }
5335         if (!cpumask_test_cpu(cpu, sched_group_cpus(group))) {
5336                 printk(KERN_ERR "ERROR: domain->groups does not contain"
5337                                 " CPU%d\n", cpu);
5338         }
5339
5340         printk(KERN_DEBUG "%*s groups:", level + 1, "");
5341         do {
5342                 if (!group) {
5343                         printk("\n");
5344                         printk(KERN_ERR "ERROR: group is NULL\n");
5345                         break;
5346                 }
5347
5348                 /*
5349                  * Even though we initialize ->power to something semi-sane,
5350                  * we leave power_orig unset. This allows us to detect if
5351                  * domain iteration is still funny without causing /0 traps.
5352                  */
5353                 if (!group->sgp->power_orig) {
5354                         printk(KERN_CONT "\n");
5355                         printk(KERN_ERR "ERROR: domain->cpu_power not "
5356                                         "set\n");
5357                         break;
5358                 }
5359
5360                 if (!cpumask_weight(sched_group_cpus(group))) {
5361                         printk(KERN_CONT "\n");
5362                         printk(KERN_ERR "ERROR: empty group\n");
5363                         break;
5364                 }
5365
5366                 if (!(sd->flags & SD_OVERLAP) &&
5367                     cpumask_intersects(groupmask, sched_group_cpus(group))) {
5368                         printk(KERN_CONT "\n");
5369                         printk(KERN_ERR "ERROR: repeated CPUs\n");
5370                         break;
5371                 }
5372
5373                 cpumask_or(groupmask, groupmask, sched_group_cpus(group));
5374
5375                 cpulist_scnprintf(str, sizeof(str), sched_group_cpus(group));
5376
5377                 printk(KERN_CONT " %s", str);
5378                 if (group->sgp->power != SCHED_POWER_SCALE) {
5379                         printk(KERN_CONT " (cpu_power = %d)",
5380                                 group->sgp->power);
5381                 }
5382
5383                 group = group->next;
5384         } while (group != sd->groups);
5385         printk(KERN_CONT "\n");
5386
5387         if (!cpumask_equal(sched_domain_span(sd), groupmask))
5388                 printk(KERN_ERR "ERROR: groups don't span domain->span\n");
5389
5390         if (sd->parent &&
5391             !cpumask_subset(groupmask, sched_domain_span(sd->parent)))
5392                 printk(KERN_ERR "ERROR: parent span is not a superset "
5393                         "of domain->span\n");
5394         return 0;
5395 }
5396
5397 static void sched_domain_debug(struct sched_domain *sd, int cpu)
5398 {
5399         int level = 0;
5400
5401         if (!sched_debug_enabled)
5402                 return;
5403
5404         if (!sd) {
5405                 printk(KERN_DEBUG "CPU%d attaching NULL sched-domain.\n", cpu);
5406                 return;
5407         }
5408
5409         printk(KERN_DEBUG "CPU%d attaching sched-domain:\n", cpu);
5410
5411         for (;;) {
5412                 if (sched_domain_debug_one(sd, cpu, level, sched_domains_tmpmask))
5413                         break;
5414                 level++;
5415                 sd = sd->parent;
5416                 if (!sd)
5417                         break;
5418         }
5419 }
5420 #else /* !CONFIG_SCHED_DEBUG */
5421 # define sched_domain_debug(sd, cpu) do { } while (0)
5422 static inline bool sched_debug(void)
5423 {
5424         return false;
5425 }
5426 #endif /* CONFIG_SCHED_DEBUG */
5427
5428 static int sd_degenerate(struct sched_domain *sd)
5429 {
5430         if (cpumask_weight(sched_domain_span(sd)) == 1)
5431                 return 1;
5432
5433         /* Following flags need at least 2 groups */
5434         if (sd->flags & (SD_LOAD_BALANCE |
5435                          SD_BALANCE_NEWIDLE |
5436                          SD_BALANCE_FORK |
5437                          SD_BALANCE_EXEC |
5438                          SD_SHARE_CPUPOWER |
5439                          SD_SHARE_PKG_RESOURCES)) {
5440                 if (sd->groups != sd->groups->next)
5441                         return 0;
5442         }
5443
5444         /* Following flags don't use groups */
5445         if (sd->flags & (SD_WAKE_AFFINE))
5446                 return 0;
5447
5448         return 1;
5449 }
5450
5451 static int
5452 sd_parent_degenerate(struct sched_domain *sd, struct sched_domain *parent)
5453 {
5454         unsigned long cflags = sd->flags, pflags = parent->flags;
5455
5456         if (sd_degenerate(parent))
5457                 return 1;
5458
5459         if (!cpumask_equal(sched_domain_span(sd), sched_domain_span(parent)))
5460                 return 0;
5461
5462         /* Flags needing groups don't count if only 1 group in parent */
5463         if (parent->groups == parent->groups->next) {
5464                 pflags &= ~(SD_LOAD_BALANCE |
5465                                 SD_BALANCE_NEWIDLE |
5466                                 SD_BALANCE_FORK |
5467                                 SD_BALANCE_EXEC |
5468                                 SD_SHARE_CPUPOWER |
5469                                 SD_SHARE_PKG_RESOURCES);
5470                 if (nr_node_ids == 1)
5471                         pflags &= ~SD_SERIALIZE;
5472         }
5473         if (~cflags & pflags)
5474                 return 0;
5475
5476         return 1;
5477 }
5478
5479 static void free_rootdomain(struct rcu_head *rcu)
5480 {
5481         struct root_domain *rd = container_of(rcu, struct root_domain, rcu);
5482
5483         cpupri_cleanup(&rd->cpupri);
5484         free_cpumask_var(rd->rto_mask);
5485         free_cpumask_var(rd->online);
5486         free_cpumask_var(rd->span);
5487         kfree(rd);
5488 }
5489
5490 static void rq_attach_root(struct rq *rq, struct root_domain *rd)
5491 {
5492         struct root_domain *old_rd = NULL;
5493         unsigned long flags;
5494
5495         raw_spin_lock_irqsave(&rq->lock, flags);
5496
5497         if (rq->rd) {
5498                 old_rd = rq->rd;
5499
5500                 if (cpumask_test_cpu(rq->cpu, old_rd->online))
5501                         set_rq_offline(rq);
5502
5503                 cpumask_clear_cpu(rq->cpu, old_rd->span);
5504
5505                 /*
5506                  * If we dont want to free the old_rt yet then
5507                  * set old_rd to NULL to skip the freeing later
5508                  * in this function:
5509                  */
5510                 if (!atomic_dec_and_test(&old_rd->refcount))
5511                         old_rd = NULL;
5512         }
5513
5514         atomic_inc(&rd->refcount);
5515         rq->rd = rd;
5516
5517         cpumask_set_cpu(rq->cpu, rd->span);
5518         if (cpumask_test_cpu(rq->cpu, cpu_active_mask))
5519                 set_rq_online(rq);
5520
5521         raw_spin_unlock_irqrestore(&rq->lock, flags);
5522
5523         if (old_rd)
5524                 call_rcu_sched(&old_rd->rcu, free_rootdomain);
5525 }
5526
5527 static int init_rootdomain(struct root_domain *rd)
5528 {
5529         memset(rd, 0, sizeof(*rd));
5530
5531         if (!alloc_cpumask_var(&rd->span, GFP_KERNEL))
5532                 goto out;
5533         if (!alloc_cpumask_var(&rd->online, GFP_KERNEL))
5534                 goto free_span;
5535         if (!alloc_cpumask_var(&rd->rto_mask, GFP_KERNEL))
5536                 goto free_online;
5537
5538         if (cpupri_init(&rd->cpupri) != 0)
5539                 goto free_rto_mask;
5540         return 0;
5541
5542 free_rto_mask:
5543         free_cpumask_var(rd->rto_mask);
5544 free_online:
5545         free_cpumask_var(rd->online);
5546 free_span:
5547         free_cpumask_var(rd->span);
5548 out:
5549         return -ENOMEM;
5550 }
5551
5552 /*
5553  * By default the system creates a single root-domain with all cpus as
5554  * members (mimicking the global state we have today).
5555  */
5556 struct root_domain def_root_domain;
5557
5558 static void init_defrootdomain(void)
5559 {
5560         init_rootdomain(&def_root_domain);
5561
5562         atomic_set(&def_root_domain.refcount, 1);
5563 }
5564
5565 static struct root_domain *alloc_rootdomain(void)
5566 {
5567         struct root_domain *rd;
5568
5569         rd = kmalloc(sizeof(*rd), GFP_KERNEL);
5570         if (!rd)
5571                 return NULL;
5572
5573         if (init_rootdomain(rd) != 0) {
5574                 kfree(rd);
5575                 return NULL;
5576         }
5577
5578         return rd;
5579 }
5580
5581 static void free_sched_groups(struct sched_group *sg, int free_sgp)
5582 {
5583         struct sched_group *tmp, *first;
5584
5585         if (!sg)
5586                 return;
5587
5588         first = sg;
5589         do {
5590                 tmp = sg->next;
5591
5592                 if (free_sgp && atomic_dec_and_test(&sg->sgp->ref))
5593                         kfree(sg->sgp);
5594
5595                 kfree(sg);
5596                 sg = tmp;
5597         } while (sg != first);
5598 }
5599
5600 static void free_sched_domain(struct rcu_head *rcu)
5601 {
5602         struct sched_domain *sd = container_of(rcu, struct sched_domain, rcu);
5603
5604         /*
5605          * If its an overlapping domain it has private groups, iterate and
5606          * nuke them all.
5607          */
5608         if (sd->flags & SD_OVERLAP) {
5609                 free_sched_groups(sd->groups, 1);
5610         } else if (atomic_dec_and_test(&sd->groups->ref)) {
5611                 kfree(sd->groups->sgp);
5612                 kfree(sd->groups);
5613         }
5614         kfree(sd);
5615 }
5616
5617 static void destroy_sched_domain(struct sched_domain *sd, int cpu)
5618 {
5619         call_rcu(&sd->rcu, free_sched_domain);
5620 }
5621
5622 static void destroy_sched_domains(struct sched_domain *sd, int cpu)
5623 {
5624         for (; sd; sd = sd->parent)
5625                 destroy_sched_domain(sd, cpu);
5626 }
5627
5628 /*
5629  * Keep a special pointer to the highest sched_domain that has
5630  * SD_SHARE_PKG_RESOURCE set (Last Level Cache Domain) for this
5631  * allows us to avoid some pointer chasing select_idle_sibling().
5632  *
5633  * Also keep a unique ID per domain (we use the first cpu number in
5634  * the cpumask of the domain), this allows us to quickly tell if
5635  * two cpus are in the same cache domain, see cpus_share_cache().
5636  */
5637 DEFINE_PER_CPU(struct sched_domain *, sd_llc);
5638 DEFINE_PER_CPU(int, sd_llc_id);
5639
5640 static void update_top_cache_domain(int cpu)
5641 {
5642         struct sched_domain *sd;
5643         int id = cpu;
5644
5645         sd = highest_flag_domain(cpu, SD_SHARE_PKG_RESOURCES);
5646         if (sd)
5647                 id = cpumask_first(sched_domain_span(sd));
5648
5649         rcu_assign_pointer(per_cpu(sd_llc, cpu), sd);
5650         per_cpu(sd_llc_id, cpu) = id;
5651 }
5652
5653 /*
5654  * Attach the domain 'sd' to 'cpu' as its base domain. Callers must
5655  * hold the hotplug lock.
5656  */
5657 static void
5658 cpu_attach_domain(struct sched_domain *sd, struct root_domain *rd, int cpu)
5659 {
5660         struct rq *rq = cpu_rq(cpu);
5661         struct sched_domain *tmp;
5662
5663         /* Remove the sched domains which do not contribute to scheduling. */
5664         for (tmp = sd; tmp; ) {
5665                 struct sched_domain *parent = tmp->parent;
5666                 if (!parent)
5667                         break;
5668
5669                 if (sd_parent_degenerate(tmp, parent)) {
5670                         tmp->parent = parent->parent;
5671                         if (parent->parent)
5672                                 parent->parent->child = tmp;
5673                         destroy_sched_domain(parent, cpu);
5674                 } else
5675                         tmp = tmp->parent;
5676         }
5677
5678         if (sd && sd_degenerate(sd)) {
5679                 tmp = sd;
5680                 sd = sd->parent;
5681                 destroy_sched_domain(tmp, cpu);
5682                 if (sd)
5683                         sd->child = NULL;
5684         }
5685
5686         sched_domain_debug(sd, cpu);
5687
5688         rq_attach_root(rq, rd);
5689         tmp = rq->sd;
5690         rcu_assign_pointer(rq->sd, sd);
5691         destroy_sched_domains(tmp, cpu);
5692
5693         update_top_cache_domain(cpu);
5694 }
5695
5696 /* cpus with isolated domains */
5697 static cpumask_var_t cpu_isolated_map;
5698
5699 /* Setup the mask of cpus configured for isolated domains */
5700 static int __init isolated_cpu_setup(char *str)
5701 {
5702         alloc_bootmem_cpumask_var(&cpu_isolated_map);
5703         cpulist_parse(str, cpu_isolated_map);
5704         return 1;
5705 }
5706
5707 __setup("isolcpus=", isolated_cpu_setup);
5708
5709 static const struct cpumask *cpu_cpu_mask(int cpu)
5710 {
5711         return cpumask_of_node(cpu_to_node(cpu));
5712 }
5713
5714 struct sd_data {
5715         struct sched_domain **__percpu sd;
5716         struct sched_group **__percpu sg;
5717         struct sched_group_power **__percpu sgp;
5718 };
5719
5720 struct s_data {
5721         struct sched_domain ** __percpu sd;
5722         struct root_domain      *rd;
5723 };
5724
5725 enum s_alloc {
5726         sa_rootdomain,
5727         sa_sd,
5728         sa_sd_storage,
5729         sa_none,
5730 };
5731
5732 struct sched_domain_topology_level;
5733
5734 typedef struct sched_domain *(*sched_domain_init_f)(struct sched_domain_topology_level *tl, int cpu);
5735 typedef const struct cpumask *(*sched_domain_mask_f)(int cpu);
5736
5737 #define SDTL_OVERLAP    0x01
5738
5739 struct sched_domain_topology_level {
5740         sched_domain_init_f init;
5741         sched_domain_mask_f mask;
5742         int                 flags;
5743         int                 numa_level;
5744         struct sd_data      data;
5745 };
5746
5747 /*
5748  * Build an iteration mask that can exclude certain CPUs from the upwards
5749  * domain traversal.
5750  *
5751  * Asymmetric node setups can result in situations where the domain tree is of
5752  * unequal depth, make sure to skip domains that already cover the entire
5753  * range.
5754  *
5755  * In that case build_sched_domains() will have terminated the iteration early
5756  * and our sibling sd spans will be empty. Domains should always include the
5757  * cpu they're built on, so check that.
5758  *
5759  */
5760 static void build_group_mask(struct sched_domain *sd, struct sched_group *sg)
5761 {
5762         const struct cpumask *span = sched_domain_span(sd);
5763         struct sd_data *sdd = sd->private;
5764         struct sched_domain *sibling;
5765         int i;
5766
5767         for_each_cpu(i, span) {
5768                 sibling = *per_cpu_ptr(sdd->sd, i);
5769                 if (!cpumask_test_cpu(i, sched_domain_span(sibling)))
5770                         continue;
5771
5772                 cpumask_set_cpu(i, sched_group_mask(sg));
5773         }
5774 }
5775
5776 /*
5777  * Return the canonical balance cpu for this group, this is the first cpu
5778  * of this group that's also in the iteration mask.
5779  */
5780 int group_balance_cpu(struct sched_group *sg)
5781 {
5782         return cpumask_first_and(sched_group_cpus(sg), sched_group_mask(sg));
5783 }
5784
5785 static int
5786 build_overlap_sched_groups(struct sched_domain *sd, int cpu)
5787 {
5788         struct sched_group *first = NULL, *last = NULL, *groups = NULL, *sg;
5789         const struct cpumask *span = sched_domain_span(sd);
5790         struct cpumask *covered = sched_domains_tmpmask;
5791         struct sd_data *sdd = sd->private;
5792         struct sched_domain *child;
5793         int i;
5794
5795         cpumask_clear(covered);
5796
5797         for_each_cpu(i, span) {
5798                 struct cpumask *sg_span;
5799
5800                 if (cpumask_test_cpu(i, covered))
5801                         continue;
5802
5803                 child = *per_cpu_ptr(sdd->sd, i);
5804
5805                 /* See the comment near build_group_mask(). */
5806                 if (!cpumask_test_cpu(i, sched_domain_span(child)))
5807                         continue;
5808
5809                 sg = kzalloc_node(sizeof(struct sched_group) + cpumask_size(),
5810                                 GFP_KERNEL, cpu_to_node(cpu));
5811
5812                 if (!sg)
5813                         goto fail;
5814
5815                 sg_span = sched_group_cpus(sg);
5816                 if (child->child) {
5817                         child = child->child;
5818                         cpumask_copy(sg_span, sched_domain_span(child));
5819                 } else
5820                         cpumask_set_cpu(i, sg_span);
5821
5822                 cpumask_or(covered, covered, sg_span);
5823
5824                 sg->sgp = *per_cpu_ptr(sdd->sgp, i);
5825                 if (atomic_inc_return(&sg->sgp->ref) == 1)
5826                         build_group_mask(sd, sg);
5827
5828                 /*
5829                  * Initialize sgp->power such that even if we mess up the
5830                  * domains and no possible iteration will get us here, we won't
5831                  * die on a /0 trap.
5832                  */
5833                 sg->sgp->power = SCHED_POWER_SCALE * cpumask_weight(sg_span);
5834
5835                 /*
5836                  * Make sure the first group of this domain contains the
5837                  * canonical balance cpu. Otherwise the sched_domain iteration
5838                  * breaks. See update_sg_lb_stats().
5839                  */
5840                 if ((!groups && cpumask_test_cpu(cpu, sg_span)) ||
5841                     group_balance_cpu(sg) == cpu)
5842                         groups = sg;
5843
5844                 if (!first)
5845                         first = sg;
5846                 if (last)
5847                         last->next = sg;
5848                 last = sg;
5849                 last->next = first;
5850         }
5851         sd->groups = groups;
5852
5853         return 0;
5854
5855 fail:
5856         free_sched_groups(first, 0);
5857
5858         return -ENOMEM;
5859 }
5860
5861 static int get_group(int cpu, struct sd_data *sdd, struct sched_group **sg)
5862 {
5863         struct sched_domain *sd = *per_cpu_ptr(sdd->sd, cpu);
5864         struct sched_domain *child = sd->child;
5865
5866         if (child)
5867                 cpu = cpumask_first(sched_domain_span(child));
5868
5869         if (sg) {
5870                 *sg = *per_cpu_ptr(sdd->sg, cpu);
5871                 (*sg)->sgp = *per_cpu_ptr(sdd->sgp, cpu);
5872                 atomic_set(&(*sg)->sgp->ref, 1); /* for claim_allocations */
5873         }
5874
5875         return cpu;
5876 }
5877
5878 /*
5879  * build_sched_groups will build a circular linked list of the groups
5880  * covered by the given span, and will set each group's ->cpumask correctly,
5881  * and ->cpu_power to 0.
5882  *
5883  * Assumes the sched_domain tree is fully constructed
5884  */
5885 static int
5886 build_sched_groups(struct sched_domain *sd, int cpu)
5887 {
5888         struct sched_group *first = NULL, *last = NULL;
5889         struct sd_data *sdd = sd->private;
5890         const struct cpumask *span = sched_domain_span(sd);
5891         struct cpumask *covered;
5892         int i;
5893
5894         get_group(cpu, sdd, &sd->groups);
5895         atomic_inc(&sd->groups->ref);
5896
5897         if (cpu != cpumask_first(sched_domain_span(sd)))
5898                 return 0;
5899
5900         lockdep_assert_held(&sched_domains_mutex);
5901         covered = sched_domains_tmpmask;
5902
5903         cpumask_clear(covered);
5904
5905         for_each_cpu(i, span) {
5906                 struct sched_group *sg;
5907                 int group = get_group(i, sdd, &sg);
5908                 int j;
5909
5910                 if (cpumask_test_cpu(i, covered))
5911                         continue;
5912
5913                 cpumask_clear(sched_group_cpus(sg));
5914                 sg->sgp->power = 0;
5915                 cpumask_setall(sched_group_mask(sg));
5916
5917                 for_each_cpu(j, span) {
5918                         if (get_group(j, sdd, NULL) != group)
5919                                 continue;
5920
5921                         cpumask_set_cpu(j, covered);
5922                         cpumask_set_cpu(j, sched_group_cpus(sg));
5923                 }
5924
5925                 if (!first)
5926                         first = sg;
5927                 if (last)
5928                         last->next = sg;
5929                 last = sg;
5930         }
5931         last->next = first;
5932
5933         return 0;
5934 }
5935
5936 /*
5937  * Initialize sched groups cpu_power.
5938  *
5939  * cpu_power indicates the capacity of sched group, which is used while
5940  * distributing the load between different sched groups in a sched domain.
5941  * Typically cpu_power for all the groups in a sched domain will be same unless
5942  * there are asymmetries in the topology. If there are asymmetries, group
5943  * having more cpu_power will pickup more load compared to the group having
5944  * less cpu_power.
5945  */
5946 static void init_sched_groups_power(int cpu, struct sched_domain *sd)
5947 {
5948         struct sched_group *sg = sd->groups;
5949
5950         WARN_ON(!sd || !sg);
5951
5952         do {
5953                 sg->group_weight = cpumask_weight(sched_group_cpus(sg));
5954                 sg = sg->next;
5955         } while (sg != sd->groups);
5956
5957         if (cpu != group_balance_cpu(sg))
5958                 return;
5959
5960         update_group_power(sd, cpu);
5961         atomic_set(&sg->sgp->nr_busy_cpus, sg->group_weight);
5962 }
5963
5964 int __weak arch_sd_sibling_asym_packing(void)
5965 {
5966        return 0*SD_ASYM_PACKING;
5967 }
5968
5969 /*
5970  * Initializers for schedule domains
5971  * Non-inlined to reduce accumulated stack pressure in build_sched_domains()
5972  */
5973
5974 #ifdef CONFIG_SCHED_DEBUG
5975 # define SD_INIT_NAME(sd, type)         sd->name = #type
5976 #else
5977 # define SD_INIT_NAME(sd, type)         do { } while (0)
5978 #endif
5979
5980 #define SD_INIT_FUNC(type)                                              \
5981 static noinline struct sched_domain *                                   \
5982 sd_init_##type(struct sched_domain_topology_level *tl, int cpu)         \
5983 {                                                                       \
5984         struct sched_domain *sd = *per_cpu_ptr(tl->data.sd, cpu);       \
5985         *sd = SD_##type##_INIT;                                         \
5986         SD_INIT_NAME(sd, type);                                         \
5987         sd->private = &tl->data;                                        \
5988         return sd;                                                      \
5989 }
5990
5991 SD_INIT_FUNC(CPU)
5992 #ifdef CONFIG_SCHED_SMT
5993  SD_INIT_FUNC(SIBLING)
5994 #endif
5995 #ifdef CONFIG_SCHED_MC
5996  SD_INIT_FUNC(MC)
5997 #endif
5998 #ifdef CONFIG_SCHED_BOOK
5999  SD_INIT_FUNC(BOOK)
6000 #endif
6001
6002 static int default_relax_domain_level = -1;
6003 int sched_domain_level_max;
6004
6005 static int __init setup_relax_domain_level(char *str)
6006 {
6007         if (kstrtoint(str, 0, &default_relax_domain_level))
6008                 pr_warn("Unable to set relax_domain_level\n");
6009
6010         return 1;
6011 }
6012 __setup("relax_domain_level=", setup_relax_domain_level);
6013
6014 static void set_domain_attribute(struct sched_domain *sd,
6015                                  struct sched_domain_attr *attr)
6016 {
6017         int request;
6018
6019         if (!attr || attr->relax_domain_level < 0) {
6020                 if (default_relax_domain_level < 0)
6021                         return;
6022                 else
6023                         request = default_relax_domain_level;
6024         } else
6025                 request = attr->relax_domain_level;
6026         if (request < sd->level) {
6027                 /* turn off idle balance on this domain */
6028                 sd->flags &= ~(SD_BALANCE_WAKE|SD_BALANCE_NEWIDLE);
6029         } else {
6030                 /* turn on idle balance on this domain */
6031                 sd->flags |= (SD_BALANCE_WAKE|SD_BALANCE_NEWIDLE);
6032         }
6033 }
6034
6035 static void __sdt_free(const struct cpumask *cpu_map);
6036 static int __sdt_alloc(const struct cpumask *cpu_map);
6037
6038 static void __free_domain_allocs(struct s_data *d, enum s_alloc what,
6039                                  const struct cpumask *cpu_map)
6040 {
6041         switch (what) {
6042         case sa_rootdomain:
6043                 if (!atomic_read(&d->rd->refcount))
6044                         free_rootdomain(&d->rd->rcu); /* fall through */
6045         case sa_sd:
6046                 free_percpu(d->sd); /* fall through */
6047         case sa_sd_storage:
6048                 __sdt_free(cpu_map); /* fall through */
6049         case sa_none:
6050                 break;
6051         }
6052 }
6053
6054 static enum s_alloc __visit_domain_allocation_hell(struct s_data *d,
6055                                                    const struct cpumask *cpu_map)
6056 {
6057         memset(d, 0, sizeof(*d));
6058
6059         if (__sdt_alloc(cpu_map))
6060                 return sa_sd_storage;
6061         d->sd = alloc_percpu(struct sched_domain *);
6062         if (!d->sd)
6063                 return sa_sd_storage;
6064         d->rd = alloc_rootdomain();
6065         if (!d->rd)
6066                 return sa_sd;
6067         return sa_rootdomain;
6068 }
6069
6070 /*
6071  * NULL the sd_data elements we've used to build the sched_domain and
6072  * sched_group structure so that the subsequent __free_domain_allocs()
6073  * will not free the data we're using.
6074  */
6075 static void claim_allocations(int cpu, struct sched_domain *sd)
6076 {
6077         struct sd_data *sdd = sd->private;
6078
6079         WARN_ON_ONCE(*per_cpu_ptr(sdd->sd, cpu) != sd);
6080         *per_cpu_ptr(sdd->sd, cpu) = NULL;
6081
6082         if (atomic_read(&(*per_cpu_ptr(sdd->sg, cpu))->ref))
6083                 *per_cpu_ptr(sdd->sg, cpu) = NULL;
6084
6085         if (atomic_read(&(*per_cpu_ptr(sdd->sgp, cpu))->ref))
6086                 *per_cpu_ptr(sdd->sgp, cpu) = NULL;
6087 }
6088
6089 #ifdef CONFIG_SCHED_SMT
6090 static const struct cpumask *cpu_smt_mask(int cpu)
6091 {
6092         return topology_thread_cpumask(cpu);
6093 }
6094 #endif
6095
6096 /*
6097  * Topology list, bottom-up.
6098  */
6099 static struct sched_domain_topology_level default_topology[] = {
6100 #ifdef CONFIG_SCHED_SMT
6101         { sd_init_SIBLING, cpu_smt_mask, },
6102 #endif
6103 #ifdef CONFIG_SCHED_MC
6104         { sd_init_MC, cpu_coregroup_mask, },
6105 #endif
6106 #ifdef CONFIG_SCHED_BOOK
6107         { sd_init_BOOK, cpu_book_mask, },
6108 #endif
6109         { sd_init_CPU, cpu_cpu_mask, },
6110         { NULL, },
6111 };
6112
6113 static struct sched_domain_topology_level *sched_domain_topology = default_topology;
6114
6115 #ifdef CONFIG_NUMA
6116
6117 static int sched_domains_numa_levels;
6118 static int *sched_domains_numa_distance;
6119 static struct cpumask ***sched_domains_numa_masks;
6120 static int sched_domains_curr_level;
6121
6122 static inline int sd_local_flags(int level)
6123 {
6124         if (sched_domains_numa_distance[level] > RECLAIM_DISTANCE)
6125                 return 0;
6126
6127         return SD_BALANCE_EXEC | SD_BALANCE_FORK | SD_WAKE_AFFINE;
6128 }
6129
6130 static struct sched_domain *
6131 sd_numa_init(struct sched_domain_topology_level *tl, int cpu)
6132 {
6133         struct sched_domain *sd = *per_cpu_ptr(tl->data.sd, cpu);
6134         int level = tl->numa_level;
6135         int sd_weight = cpumask_weight(
6136                         sched_domains_numa_masks[level][cpu_to_node(cpu)]);
6137
6138         *sd = (struct sched_domain){
6139                 .min_interval           = sd_weight,
6140                 .max_interval           = 2*sd_weight,
6141                 .busy_factor            = 32,
6142                 .imbalance_pct          = 125,
6143                 .cache_nice_tries       = 2,
6144                 .busy_idx               = 3,
6145                 .idle_idx               = 2,
6146                 .newidle_idx            = 0,
6147                 .wake_idx               = 0,
6148                 .forkexec_idx           = 0,
6149
6150                 .flags                  = 1*SD_LOAD_BALANCE
6151                                         | 1*SD_BALANCE_NEWIDLE
6152                                         | 0*SD_BALANCE_EXEC
6153                                         | 0*SD_BALANCE_FORK
6154                                         | 0*SD_BALANCE_WAKE
6155                                         | 0*SD_WAKE_AFFINE
6156                                         | 0*SD_SHARE_CPUPOWER
6157                                         | 0*SD_SHARE_PKG_RESOURCES
6158                                         | 1*SD_SERIALIZE
6159                                         | 0*SD_PREFER_SIBLING
6160                                         | sd_local_flags(level)
6161                                         ,
6162                 .last_balance           = jiffies,
6163                 .balance_interval       = sd_weight,
6164         };
6165         SD_INIT_NAME(sd, NUMA);
6166         sd->private = &tl->data;
6167
6168         /*
6169          * Ugly hack to pass state to sd_numa_mask()...
6170          */
6171         sched_domains_curr_level = tl->numa_level;
6172
6173         return sd;
6174 }
6175
6176 static const struct cpumask *sd_numa_mask(int cpu)
6177 {
6178         return sched_domains_numa_masks[sched_domains_curr_level][cpu_to_node(cpu)];
6179 }
6180
6181 static void sched_numa_warn(const char *str)
6182 {
6183         static int done = false;
6184         int i,j;
6185
6186         if (done)
6187                 return;
6188
6189         done = true;
6190
6191         printk(KERN_WARNING "ERROR: %s\n\n", str);
6192
6193         for (i = 0; i < nr_node_ids; i++) {
6194                 printk(KERN_WARNING "  ");
6195                 for (j = 0; j < nr_node_ids; j++)
6196                         printk(KERN_CONT "%02d ", node_distance(i,j));
6197                 printk(KERN_CONT "\n");
6198         }
6199         printk(KERN_WARNING "\n");
6200 }
6201
6202 static bool find_numa_distance(int distance)
6203 {
6204         int i;
6205
6206         if (distance == node_distance(0, 0))
6207                 return true;
6208
6209         for (i = 0; i < sched_domains_numa_levels; i++) {
6210                 if (sched_domains_numa_distance[i] == distance)
6211                         return true;
6212         }
6213
6214         return false;
6215 }
6216
6217 static void sched_init_numa(void)
6218 {
6219         int next_distance, curr_distance = node_distance(0, 0);
6220         struct sched_domain_topology_level *tl;
6221         int level = 0;
6222         int i, j, k;
6223
6224         sched_domains_numa_distance = kzalloc(sizeof(int) * nr_node_ids, GFP_KERNEL);
6225         if (!sched_domains_numa_distance)
6226                 return;
6227
6228         /*
6229          * O(nr_nodes^2) deduplicating selection sort -- in order to find the
6230          * unique distances in the node_distance() table.
6231          *
6232          * Assumes node_distance(0,j) includes all distances in
6233          * node_distance(i,j) in order to avoid cubic time.
6234          */
6235         next_distance = curr_distance;
6236         for (i = 0; i < nr_node_ids; i++) {
6237                 for (j = 0; j < nr_node_ids; j++) {
6238                         for (k = 0; k < nr_node_ids; k++) {
6239                                 int distance = node_distance(i, k);
6240
6241                                 if (distance > curr_distance &&
6242                                     (distance < next_distance ||
6243                                      next_distance == curr_distance))
6244                                         next_distance = distance;
6245
6246                                 /*
6247                                  * While not a strong assumption it would be nice to know
6248                                  * about cases where if node A is connected to B, B is not
6249                                  * equally connected to A.
6250                                  */
6251                                 if (sched_debug() && node_distance(k, i) != distance)
6252                                         sched_numa_warn("Node-distance not symmetric");
6253
6254                                 if (sched_debug() && i && !find_numa_distance(distance))
6255                                         sched_numa_warn("Node-0 not representative");
6256                         }
6257                         if (next_distance != curr_distance) {
6258                                 sched_domains_numa_distance[level++] = next_distance;
6259                                 sched_domains_numa_levels = level;
6260                                 curr_distance = next_distance;
6261                         } else break;
6262                 }
6263
6264                 /*
6265                  * In case of sched_debug() we verify the above assumption.
6266                  */
6267                 if (!sched_debug())
6268                         break;
6269         }
6270         /*
6271          * 'level' contains the number of unique distances, excluding the
6272          * identity distance node_distance(i,i).
6273          *
6274          * The sched_domains_numa_distance[] array includes the actual distance
6275          * numbers.
6276          */
6277
6278         /*
6279          * Here, we should temporarily reset sched_domains_numa_levels to 0.
6280          * If it fails to allocate memory for array sched_domains_numa_masks[][],
6281          * the array will contain less then 'level' members. This could be
6282          * dangerous when we use it to iterate array sched_domains_numa_masks[][]
6283          * in other functions.
6284          *
6285          * We reset it to 'level' at the end of this function.
6286          */
6287         sched_domains_numa_levels = 0;
6288
6289         sched_domains_numa_masks = kzalloc(sizeof(void *) * level, GFP_KERNEL);
6290         if (!sched_domains_numa_masks)
6291                 return;
6292
6293         /*
6294          * Now for each level, construct a mask per node which contains all
6295          * cpus of nodes that are that many hops away from us.
6296          */
6297         for (i = 0; i < level; i++) {
6298                 sched_domains_numa_masks[i] =
6299                         kzalloc(nr_node_ids * sizeof(void *), GFP_KERNEL);
6300                 if (!sched_domains_numa_masks[i])
6301                         return;
6302
6303                 for (j = 0; j < nr_node_ids; j++) {
6304                         struct cpumask *mask = kzalloc(cpumask_size(), GFP_KERNEL);
6305                         if (!mask)
6306                                 return;
6307
6308                         sched_domains_numa_masks[i][j] = mask;
6309
6310                         for (k = 0; k < nr_node_ids; k++) {
6311                                 if (node_distance(j, k) > sched_domains_numa_distance[i])
6312                                         continue;
6313
6314                                 cpumask_or(mask, mask, cpumask_of_node(k));
6315                         }
6316                 }
6317         }
6318
6319         tl = kzalloc((ARRAY_SIZE(default_topology) + level) *
6320                         sizeof(struct sched_domain_topology_level), GFP_KERNEL);
6321         if (!tl)
6322                 return;
6323
6324         /*
6325          * Copy the default topology bits..
6326          */
6327         for (i = 0; default_topology[i].init; i++)
6328                 tl[i] = default_topology[i];
6329
6330         /*
6331          * .. and append 'j' levels of NUMA goodness.
6332          */
6333         for (j = 0; j < level; i++, j++) {
6334                 tl[i] = (struct sched_domain_topology_level){
6335                         .init = sd_numa_init,
6336                         .mask = sd_numa_mask,
6337                         .flags = SDTL_OVERLAP,
6338                         .numa_level = j,
6339                 };
6340         }
6341
6342         sched_domain_topology = tl;
6343
6344         sched_domains_numa_levels = level;
6345 }
6346
6347 static void sched_domains_numa_masks_set(int cpu)
6348 {
6349         int i, j;
6350         int node = cpu_to_node(cpu);
6351
6352         for (i = 0; i < sched_domains_numa_levels; i++) {
6353                 for (j = 0; j < nr_node_ids; j++) {
6354                         if (node_distance(j, node) <= sched_domains_numa_distance[i])
6355                                 cpumask_set_cpu(cpu, sched_domains_numa_masks[i][j]);
6356                 }
6357         }
6358 }
6359
6360 static void sched_domains_numa_masks_clear(int cpu)
6361 {
6362         int i, j;
6363         for (i = 0; i < sched_domains_numa_levels; i++) {
6364                 for (j = 0; j < nr_node_ids; j++)
6365                         cpumask_clear_cpu(cpu, sched_domains_numa_masks[i][j]);
6366         }
6367 }
6368
6369 /*
6370  * Update sched_domains_numa_masks[level][node] array when new cpus
6371  * are onlined.
6372  */
6373 static int sched_domains_numa_masks_update(struct notifier_block *nfb,
6374                                            unsigned long action,
6375                                            void *hcpu)
6376 {
6377         int cpu = (long)hcpu;
6378
6379         switch (action & ~CPU_TASKS_FROZEN) {
6380         case CPU_ONLINE:
6381                 sched_domains_numa_masks_set(cpu);
6382                 break;
6383
6384         case CPU_DEAD:
6385                 sched_domains_numa_masks_clear(cpu);
6386                 break;
6387
6388         default:
6389                 return NOTIFY_DONE;
6390         }
6391
6392         return NOTIFY_OK;
6393 }
6394 #else
6395 static inline void sched_init_numa(void)
6396 {
6397 }
6398
6399 static int sched_domains_numa_masks_update(struct notifier_block *nfb,
6400                                            unsigned long action,
6401                                            void *hcpu)
6402 {
6403         return 0;
6404 }
6405 #endif /* CONFIG_NUMA */
6406
6407 static int __sdt_alloc(const struct cpumask *cpu_map)
6408 {
6409         struct sched_domain_topology_level *tl;
6410         int j;
6411
6412         for (tl = sched_domain_topology; tl->init; tl++) {
6413                 struct sd_data *sdd = &tl->data;
6414
6415                 sdd->sd = alloc_percpu(struct sched_domain *);
6416                 if (!sdd->sd)
6417                         return -ENOMEM;
6418
6419                 sdd->sg = alloc_percpu(struct sched_group *);
6420                 if (!sdd->sg)
6421                         return -ENOMEM;
6422
6423                 sdd->sgp = alloc_percpu(struct sched_group_power *);
6424                 if (!sdd->sgp)
6425                         return -ENOMEM;
6426
6427                 for_each_cpu(j, cpu_map) {
6428                         struct sched_domain *sd;
6429                         struct sched_group *sg;
6430                         struct sched_group_power *sgp;
6431
6432                         sd = kzalloc_node(sizeof(struct sched_domain) + cpumask_size(),
6433                                         GFP_KERNEL, cpu_to_node(j));
6434                         if (!sd)
6435                                 return -ENOMEM;
6436
6437                         *per_cpu_ptr(sdd->sd, j) = sd;
6438
6439                         sg = kzalloc_node(sizeof(struct sched_group) + cpumask_size(),
6440                                         GFP_KERNEL, cpu_to_node(j));
6441                         if (!sg)
6442                                 return -ENOMEM;
6443
6444                         sg->next = sg;
6445
6446                         *per_cpu_ptr(sdd->sg, j) = sg;
6447
6448                         sgp = kzalloc_node(sizeof(struct sched_group_power) + cpumask_size(),
6449                                         GFP_KERNEL, cpu_to_node(j));
6450                         if (!sgp)
6451                                 return -ENOMEM;
6452
6453                         *per_cpu_ptr(sdd->sgp, j) = sgp;
6454                 }
6455         }
6456
6457         return 0;
6458 }
6459
6460 static void __sdt_free(const struct cpumask *cpu_map)
6461 {
6462         struct sched_domain_topology_level *tl;
6463         int j;
6464
6465         for (tl = sched_domain_topology; tl->init; tl++) {
6466                 struct sd_data *sdd = &tl->data;
6467
6468                 for_each_cpu(j, cpu_map) {
6469                         struct sched_domain *sd;
6470
6471                         if (sdd->sd) {
6472                                 sd = *per_cpu_ptr(sdd->sd, j);
6473                                 if (sd && (sd->flags & SD_OVERLAP))
6474                                         free_sched_groups(sd->groups, 0);
6475                                 kfree(*per_cpu_ptr(sdd->sd, j));
6476                         }
6477
6478                         if (sdd->sg)
6479                                 kfree(*per_cpu_ptr(sdd->sg, j));
6480                         if (sdd->sgp)
6481                                 kfree(*per_cpu_ptr(sdd->sgp, j));
6482                 }
6483                 free_percpu(sdd->sd);
6484                 sdd->sd = NULL;
6485                 free_percpu(sdd->sg);
6486                 sdd->sg = NULL;
6487                 free_percpu(sdd->sgp);
6488                 sdd->sgp = NULL;
6489         }
6490 }
6491
6492 struct sched_domain *build_sched_domain(struct sched_domain_topology_level *tl,
6493                 struct s_data *d, const struct cpumask *cpu_map,
6494                 struct sched_domain_attr *attr, struct sched_domain *child,
6495                 int cpu)
6496 {
6497         struct sched_domain *sd = tl->init(tl, cpu);
6498         if (!sd)
6499                 return child;
6500
6501         cpumask_and(sched_domain_span(sd), cpu_map, tl->mask(cpu));
6502         if (child) {
6503                 sd->level = child->level + 1;
6504                 sched_domain_level_max = max(sched_domain_level_max, sd->level);
6505                 child->parent = sd;
6506         }
6507         sd->child = child;
6508         set_domain_attribute(sd, attr);
6509
6510         return sd;
6511 }
6512
6513 /*
6514  * Build sched domains for a given set of cpus and attach the sched domains
6515  * to the individual cpus
6516  */
6517 static int build_sched_domains(const struct cpumask *cpu_map,
6518                                struct sched_domain_attr *attr)
6519 {
6520         enum s_alloc alloc_state = sa_none;
6521         struct sched_domain *sd;
6522         struct s_data d;
6523         int i, ret = -ENOMEM;
6524
6525         alloc_state = __visit_domain_allocation_hell(&d, cpu_map);
6526         if (alloc_state != sa_rootdomain)
6527                 goto error;
6528
6529         /* Set up domains for cpus specified by the cpu_map. */
6530         for_each_cpu(i, cpu_map) {
6531                 struct sched_domain_topology_level *tl;
6532
6533                 sd = NULL;
6534                 for (tl = sched_domain_topology; tl->init; tl++) {
6535                         sd = build_sched_domain(tl, &d, cpu_map, attr, sd, i);
6536                         if (tl->flags & SDTL_OVERLAP || sched_feat(FORCE_SD_OVERLAP))
6537                                 sd->flags |= SD_OVERLAP;
6538                         if (cpumask_equal(cpu_map, sched_domain_span(sd)))
6539                                 break;
6540                 }
6541
6542                 while (sd->child)
6543                         sd = sd->child;
6544
6545                 *per_cpu_ptr(d.sd, i) = sd;
6546         }
6547
6548         /* Build the groups for the domains */
6549         for_each_cpu(i, cpu_map) {
6550                 for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
6551                         sd->span_weight = cpumask_weight(sched_domain_span(sd));
6552                         if (sd->flags & SD_OVERLAP) {
6553                                 if (build_overlap_sched_groups(sd, i))
6554                                         goto error;
6555                         } else {
6556                                 if (build_sched_groups(sd, i))
6557                                         goto error;
6558                         }
6559                 }
6560         }
6561
6562         /* Calculate CPU power for physical packages and nodes */
6563         for (i = nr_cpumask_bits-1; i >= 0; i--) {
6564                 if (!cpumask_test_cpu(i, cpu_map))
6565                         continue;
6566
6567                 for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
6568                         claim_allocations(i, sd);
6569                         init_sched_groups_power(i, sd);
6570                 }
6571         }
6572
6573         /* Attach the domains */
6574         rcu_read_lock();
6575         for_each_cpu(i, cpu_map) {
6576                 sd = *per_cpu_ptr(d.sd, i);
6577                 cpu_attach_domain(sd, d.rd, i);
6578         }
6579         rcu_read_unlock();
6580
6581         ret = 0;
6582 error:
6583         __free_domain_allocs(&d, alloc_state, cpu_map);
6584         return ret;
6585 }
6586
6587 static cpumask_var_t *doms_cur; /* current sched domains */
6588 static int ndoms_cur;           /* number of sched domains in 'doms_cur' */
6589 static struct sched_domain_attr *dattr_cur;
6590                                 /* attribues of custom domains in 'doms_cur' */
6591
6592 /*
6593  * Special case: If a kmalloc of a doms_cur partition (array of
6594  * cpumask) fails, then fallback to a single sched domain,
6595  * as determined by the single cpumask fallback_doms.
6596  */
6597 static cpumask_var_t fallback_doms;
6598
6599 /*
6600  * arch_update_cpu_topology lets virtualized architectures update the
6601  * cpu core maps. It is supposed to return 1 if the topology changed
6602  * or 0 if it stayed the same.
6603  */
6604 int __attribute__((weak)) arch_update_cpu_topology(void)
6605 {
6606         return 0;
6607 }
6608
6609 cpumask_var_t *alloc_sched_domains(unsigned int ndoms)
6610 {
6611         int i;
6612         cpumask_var_t *doms;
6613
6614         doms = kmalloc(sizeof(*doms) * ndoms, GFP_KERNEL);
6615         if (!doms)
6616                 return NULL;
6617         for (i = 0; i < ndoms; i++) {
6618                 if (!alloc_cpumask_var(&doms[i], GFP_KERNEL)) {
6619                         free_sched_domains(doms, i);
6620                         return NULL;
6621                 }
6622         }
6623         return doms;
6624 }
6625
6626 void free_sched_domains(cpumask_var_t doms[], unsigned int ndoms)
6627 {
6628         unsigned int i;
6629         for (i = 0; i < ndoms; i++)
6630                 free_cpumask_var(doms[i]);
6631         kfree(doms);
6632 }
6633
6634 /*
6635  * Set up scheduler domains and groups. Callers must hold the hotplug lock.
6636  * For now this just excludes isolated cpus, but could be used to
6637  * exclude other special cases in the future.
6638  */
6639 static int init_sched_domains(const struct cpumask *cpu_map)
6640 {
6641         int err;
6642
6643         arch_update_cpu_topology();
6644         ndoms_cur = 1;
6645         doms_cur = alloc_sched_domains(ndoms_cur);
6646         if (!doms_cur)
6647                 doms_cur = &fallback_doms;
6648         cpumask_andnot(doms_cur[0], cpu_map, cpu_isolated_map);
6649         err = build_sched_domains(doms_cur[0], NULL);
6650         register_sched_domain_sysctl();
6651
6652         return err;
6653 }
6654
6655 /*
6656  * Detach sched domains from a group of cpus specified in cpu_map
6657  * These cpus will now be attached to the NULL domain
6658  */
6659 static void detach_destroy_domains(const struct cpumask *cpu_map)
6660 {
6661         int i;
6662
6663         rcu_read_lock();
6664         for_each_cpu(i, cpu_map)
6665                 cpu_attach_domain(NULL, &def_root_domain, i);
6666         rcu_read_unlock();
6667 }
6668
6669 /* handle null as "default" */
6670 static int dattrs_equal(struct sched_domain_attr *cur, int idx_cur,
6671                         struct sched_domain_attr *new, int idx_new)
6672 {
6673         struct sched_domain_attr tmp;
6674
6675         /* fast path */
6676         if (!new && !cur)
6677                 return 1;
6678
6679         tmp = SD_ATTR_INIT;
6680         return !memcmp(cur ? (cur + idx_cur) : &tmp,
6681                         new ? (new + idx_new) : &tmp,
6682                         sizeof(struct sched_domain_attr));
6683 }
6684
6685 /*
6686  * Partition sched domains as specified by the 'ndoms_new'
6687  * cpumasks in the array doms_new[] of cpumasks. This compares
6688  * doms_new[] to the current sched domain partitioning, doms_cur[].
6689  * It destroys each deleted domain and builds each new domain.
6690  *
6691  * 'doms_new' is an array of cpumask_var_t's of length 'ndoms_new'.
6692  * The masks don't intersect (don't overlap.) We should setup one
6693  * sched domain for each mask. CPUs not in any of the cpumasks will
6694  * not be load balanced. If the same cpumask appears both in the
6695  * current 'doms_cur' domains and in the new 'doms_new', we can leave
6696  * it as it is.
6697  *
6698  * The passed in 'doms_new' should be allocated using
6699  * alloc_sched_domains.  This routine takes ownership of it and will
6700  * free_sched_domains it when done with it. If the caller failed the
6701  * alloc call, then it can pass in doms_new == NULL && ndoms_new == 1,
6702  * and partition_sched_domains() will fallback to the single partition
6703  * 'fallback_doms', it also forces the domains to be rebuilt.
6704  *
6705  * If doms_new == NULL it will be replaced with cpu_online_mask.
6706  * ndoms_new == 0 is a special case for destroying existing domains,
6707  * and it will not create the default domain.
6708  *
6709  * Call with hotplug lock held
6710  */
6711 void partition_sched_domains(int ndoms_new, cpumask_var_t doms_new[],
6712                              struct sched_domain_attr *dattr_new)
6713 {
6714         int i, j, n;
6715         int new_topology;
6716
6717         mutex_lock(&sched_domains_mutex);
6718
6719         /* always unregister in case we don't destroy any domains */
6720         unregister_sched_domain_sysctl();
6721
6722         /* Let architecture update cpu core mappings. */
6723         new_topology = arch_update_cpu_topology();
6724
6725         n = doms_new ? ndoms_new : 0;
6726
6727         /* Destroy deleted domains */
6728         for (i = 0; i < ndoms_cur; i++) {
6729                 for (j = 0; j < n && !new_topology; j++) {
6730                         if (cpumask_equal(doms_cur[i], doms_new[j])
6731                             && dattrs_equal(dattr_cur, i, dattr_new, j))
6732                                 goto match1;
6733                 }
6734                 /* no match - a current sched domain not in new doms_new[] */
6735                 detach_destroy_domains(doms_cur[i]);
6736 match1:
6737                 ;
6738         }
6739
6740         if (doms_new == NULL) {
6741                 ndoms_cur = 0;
6742                 doms_new = &fallback_doms;
6743                 cpumask_andnot(doms_new[0], cpu_active_mask, cpu_isolated_map);
6744                 WARN_ON_ONCE(dattr_new);
6745         }
6746
6747         /* Build new domains */
6748         for (i = 0; i < ndoms_new; i++) {
6749                 for (j = 0; j < ndoms_cur && !new_topology; j++) {
6750                         if (cpumask_equal(doms_new[i], doms_cur[j])
6751                             && dattrs_equal(dattr_new, i, dattr_cur, j))
6752                                 goto match2;
6753                 }
6754                 /* no match - add a new doms_new */
6755                 build_sched_domains(doms_new[i], dattr_new ? dattr_new + i : NULL);
6756 match2:
6757                 ;
6758         }
6759
6760         /* Remember the new sched domains */
6761         if (doms_cur != &fallback_doms)
6762                 free_sched_domains(doms_cur, ndoms_cur);
6763         kfree(dattr_cur);       /* kfree(NULL) is safe */
6764         doms_cur = doms_new;
6765         dattr_cur = dattr_new;
6766         ndoms_cur = ndoms_new;
6767
6768         register_sched_domain_sysctl();
6769
6770         mutex_unlock(&sched_domains_mutex);
6771 }
6772
6773 static int num_cpus_frozen;     /* used to mark begin/end of suspend/resume */
6774
6775 /*
6776  * Update cpusets according to cpu_active mask.  If cpusets are
6777  * disabled, cpuset_update_active_cpus() becomes a simple wrapper
6778  * around partition_sched_domains().
6779  *
6780  * If we come here as part of a suspend/resume, don't touch cpusets because we
6781  * want to restore it back to its original state upon resume anyway.
6782  */
6783 static int cpuset_cpu_active(struct notifier_block *nfb, unsigned long action,
6784                              void *hcpu)
6785 {
6786         switch (action) {
6787         case CPU_ONLINE_FROZEN:
6788         case CPU_DOWN_FAILED_FROZEN:
6789
6790                 /*
6791                  * num_cpus_frozen tracks how many CPUs are involved in suspend
6792                  * resume sequence. As long as this is not the last online
6793                  * operation in the resume sequence, just build a single sched
6794                  * domain, ignoring cpusets.
6795                  */
6796                 num_cpus_frozen--;
6797                 if (likely(num_cpus_frozen)) {
6798                         partition_sched_domains(1, NULL, NULL);
6799                         break;
6800                 }
6801
6802                 /*
6803                  * This is the last CPU online operation. So fall through and
6804                  * restore the original sched domains by considering the
6805                  * cpuset configurations.
6806                  */
6807
6808         case CPU_ONLINE:
6809         case CPU_DOWN_FAILED:
6810                 cpuset_update_active_cpus(true);
6811                 break;
6812         default:
6813                 return NOTIFY_DONE;
6814         }
6815         return NOTIFY_OK;
6816 }
6817
6818 static int cpuset_cpu_inactive(struct notifier_block *nfb, unsigned long action,
6819                                void *hcpu)
6820 {
6821         switch (action) {
6822         case CPU_DOWN_PREPARE:
6823                 cpuset_update_active_cpus(false);
6824                 break;
6825         case CPU_DOWN_PREPARE_FROZEN:
6826                 num_cpus_frozen++;
6827                 partition_sched_domains(1, NULL, NULL);
6828                 break;
6829         default:
6830                 return NOTIFY_DONE;
6831         }
6832         return NOTIFY_OK;
6833 }
6834
6835 void __init sched_init_smp(void)
6836 {
6837         cpumask_var_t non_isolated_cpus;
6838
6839         alloc_cpumask_var(&non_isolated_cpus, GFP_KERNEL);
6840         alloc_cpumask_var(&fallback_doms, GFP_KERNEL);
6841
6842         sched_init_numa();
6843
6844         get_online_cpus();
6845         mutex_lock(&sched_domains_mutex);
6846         init_sched_domains(cpu_active_mask);
6847         cpumask_andnot(non_isolated_cpus, cpu_possible_mask, cpu_isolated_map);
6848         if (cpumask_empty(non_isolated_cpus))
6849                 cpumask_set_cpu(smp_processor_id(), non_isolated_cpus);
6850         mutex_unlock(&sched_domains_mutex);
6851         put_online_cpus();
6852
6853         hotcpu_notifier(sched_domains_numa_masks_update, CPU_PRI_SCHED_ACTIVE);
6854         hotcpu_notifier(cpuset_cpu_active, CPU_PRI_CPUSET_ACTIVE);
6855         hotcpu_notifier(cpuset_cpu_inactive, CPU_PRI_CPUSET_INACTIVE);
6856
6857         /* RT runtime code needs to handle some hotplug events */
6858         hotcpu_notifier(update_runtime, 0);
6859
6860         init_hrtick();
6861
6862         /* Move init over to a non-isolated CPU */
6863         if (set_cpus_allowed_ptr(current, non_isolated_cpus) < 0)
6864                 BUG();
6865         sched_init_granularity();
6866         free_cpumask_var(non_isolated_cpus);
6867
6868         init_sched_rt_class();
6869 }
6870 #else
6871 void __init sched_init_smp(void)
6872 {
6873         sched_init_granularity();
6874 }
6875 #endif /* CONFIG_SMP */
6876
6877 const_debug unsigned int sysctl_timer_migration = 1;
6878
6879 int in_sched_functions(unsigned long addr)
6880 {
6881         return in_lock_functions(addr) ||
6882                 (addr >= (unsigned long)__sched_text_start
6883                 && addr < (unsigned long)__sched_text_end);
6884 }
6885
6886 #ifdef CONFIG_CGROUP_SCHED
6887 /*
6888  * Default task group.
6889  * Every task in system belongs to this group at bootup.
6890  */
6891 struct task_group root_task_group;
6892 LIST_HEAD(task_groups);
6893 #endif
6894
6895 DECLARE_PER_CPU(cpumask_var_t, load_balance_mask);
6896
6897 void __init sched_init(void)
6898 {
6899         int i, j;
6900         unsigned long alloc_size = 0, ptr;
6901
6902 #ifdef CONFIG_FAIR_GROUP_SCHED
6903         alloc_size += 2 * nr_cpu_ids * sizeof(void **);
6904 #endif
6905 #ifdef CONFIG_RT_GROUP_SCHED
6906         alloc_size += 2 * nr_cpu_ids * sizeof(void **);
6907 #endif
6908 #ifdef CONFIG_CPUMASK_OFFSTACK
6909         alloc_size += num_possible_cpus() * cpumask_size();
6910 #endif
6911         if (alloc_size) {
6912                 ptr = (unsigned long)kzalloc(alloc_size, GFP_NOWAIT);
6913
6914 #ifdef CONFIG_FAIR_GROUP_SCHED
6915                 root_task_group.se = (struct sched_entity **)ptr;
6916                 ptr += nr_cpu_ids * sizeof(void **);
6917
6918                 root_task_group.cfs_rq = (struct cfs_rq **)ptr;
6919                 ptr += nr_cpu_ids * sizeof(void **);
6920
6921 #endif /* CONFIG_FAIR_GROUP_SCHED */
6922 #ifdef CONFIG_RT_GROUP_SCHED
6923                 root_task_group.rt_se = (struct sched_rt_entity **)ptr;
6924                 ptr += nr_cpu_ids * sizeof(void **);
6