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