sched: more accurate min_vruntime accounting
[linux-2.6.git] / kernel / sched_fair.c
1 /*
2  * Completely Fair Scheduling (CFS) Class (SCHED_NORMAL/SCHED_BATCH)
3  *
4  *  Copyright (C) 2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
5  *
6  *  Interactivity improvements by Mike Galbraith
7  *  (C) 2007 Mike Galbraith <efault@gmx.de>
8  *
9  *  Various enhancements by Dmitry Adamushko.
10  *  (C) 2007 Dmitry Adamushko <dmitry.adamushko@gmail.com>
11  *
12  *  Group scheduling enhancements by Srivatsa Vaddagiri
13  *  Copyright IBM Corporation, 2007
14  *  Author: Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com>
15  *
16  *  Scaled math optimizations by Thomas Gleixner
17  *  Copyright (C) 2007, Thomas Gleixner <tglx@linutronix.de>
18  *
19  *  Adaptive scheduling granularity, math enhancements by Peter Zijlstra
20  *  Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra <pzijlstr@redhat.com>
21  */
22
23 #include <linux/latencytop.h>
24
25 /*
26  * Targeted preemption latency for CPU-bound tasks:
27  * (default: 20ms * (1 + ilog(ncpus)), units: nanoseconds)
28  *
29  * NOTE: this latency value is not the same as the concept of
30  * 'timeslice length' - timeslices in CFS are of variable length
31  * and have no persistent notion like in traditional, time-slice
32  * based scheduling concepts.
33  *
34  * (to see the precise effective timeslice length of your workload,
35  *  run vmstat and monitor the context-switches (cs) field)
36  */
37 unsigned int sysctl_sched_latency = 20000000ULL;
38
39 /*
40  * Minimal preemption granularity for CPU-bound tasks:
41  * (default: 4 msec * (1 + ilog(ncpus)), units: nanoseconds)
42  */
43 unsigned int sysctl_sched_min_granularity = 4000000ULL;
44
45 /*
46  * is kept at sysctl_sched_latency / sysctl_sched_min_granularity
47  */
48 static unsigned int sched_nr_latency = 5;
49
50 /*
51  * After fork, child runs first. (default) If set to 0 then
52  * parent will (try to) run first.
53  */
54 const_debug unsigned int sysctl_sched_child_runs_first = 1;
55
56 /*
57  * sys_sched_yield() compat mode
58  *
59  * This option switches the agressive yield implementation of the
60  * old scheduler back on.
61  */
62 unsigned int __read_mostly sysctl_sched_compat_yield;
63
64 /*
65  * SCHED_OTHER wake-up granularity.
66  * (default: 5 msec * (1 + ilog(ncpus)), units: nanoseconds)
67  *
68  * This option delays the preemption effects of decoupled workloads
69  * and reduces their over-scheduling. Synchronous workloads will still
70  * have immediate wakeup/sleep latencies.
71  */
72 unsigned int sysctl_sched_wakeup_granularity = 5000000UL;
73
74 const_debug unsigned int sysctl_sched_migration_cost = 500000UL;
75
76 static const struct sched_class fair_sched_class;
77
78 /**************************************************************
79  * CFS operations on generic schedulable entities:
80  */
81
82 static inline struct task_struct *task_of(struct sched_entity *se)
83 {
84         return container_of(se, struct task_struct, se);
85 }
86
87 #ifdef CONFIG_FAIR_GROUP_SCHED
88
89 /* cpu runqueue to which this cfs_rq is attached */
90 static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
91 {
92         return cfs_rq->rq;
93 }
94
95 /* An entity is a task if it doesn't "own" a runqueue */
96 #define entity_is_task(se)      (!se->my_q)
97
98 /* Walk up scheduling entities hierarchy */
99 #define for_each_sched_entity(se) \
100                 for (; se; se = se->parent)
101
102 static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
103 {
104         return p->se.cfs_rq;
105 }
106
107 /* runqueue on which this entity is (to be) queued */
108 static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
109 {
110         return se->cfs_rq;
111 }
112
113 /* runqueue "owned" by this group */
114 static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
115 {
116         return grp->my_q;
117 }
118
119 /* Given a group's cfs_rq on one cpu, return its corresponding cfs_rq on
120  * another cpu ('this_cpu')
121  */
122 static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu)
123 {
124         return cfs_rq->tg->cfs_rq[this_cpu];
125 }
126
127 /* Iterate thr' all leaf cfs_rq's on a runqueue */
128 #define for_each_leaf_cfs_rq(rq, cfs_rq) \
129         list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
130
131 /* Do the two (enqueued) entities belong to the same group ? */
132 static inline int
133 is_same_group(struct sched_entity *se, struct sched_entity *pse)
134 {
135         if (se->cfs_rq == pse->cfs_rq)
136                 return 1;
137
138         return 0;
139 }
140
141 static inline struct sched_entity *parent_entity(struct sched_entity *se)
142 {
143         return se->parent;
144 }
145
146 #else   /* CONFIG_FAIR_GROUP_SCHED */
147
148 static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
149 {
150         return container_of(cfs_rq, struct rq, cfs);
151 }
152
153 #define entity_is_task(se)      1
154
155 #define for_each_sched_entity(se) \
156                 for (; se; se = NULL)
157
158 static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
159 {
160         return &task_rq(p)->cfs;
161 }
162
163 static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
164 {
165         struct task_struct *p = task_of(se);
166         struct rq *rq = task_rq(p);
167
168         return &rq->cfs;
169 }
170
171 /* runqueue "owned" by this group */
172 static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
173 {
174         return NULL;
175 }
176
177 static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu)
178 {
179         return &cpu_rq(this_cpu)->cfs;
180 }
181
182 #define for_each_leaf_cfs_rq(rq, cfs_rq) \
183                 for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)
184
185 static inline int
186 is_same_group(struct sched_entity *se, struct sched_entity *pse)
187 {
188         return 1;
189 }
190
191 static inline struct sched_entity *parent_entity(struct sched_entity *se)
192 {
193         return NULL;
194 }
195
196 #endif  /* CONFIG_FAIR_GROUP_SCHED */
197
198
199 /**************************************************************
200  * Scheduling class tree data structure manipulation methods:
201  */
202
203 static inline u64 max_vruntime(u64 min_vruntime, u64 vruntime)
204 {
205         s64 delta = (s64)(vruntime - min_vruntime);
206         if (delta > 0)
207                 min_vruntime = vruntime;
208
209         return min_vruntime;
210 }
211
212 static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime)
213 {
214         s64 delta = (s64)(vruntime - min_vruntime);
215         if (delta < 0)
216                 min_vruntime = vruntime;
217
218         return min_vruntime;
219 }
220
221 static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
222 {
223         return se->vruntime - cfs_rq->min_vruntime;
224 }
225
226 static void update_min_vruntime(struct cfs_rq *cfs_rq)
227 {
228         u64 vruntime = cfs_rq->min_vruntime;
229
230         if (cfs_rq->curr)
231                 vruntime = cfs_rq->curr->vruntime;
232
233         if (cfs_rq->rb_leftmost) {
234                 struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
235                                                    struct sched_entity,
236                                                    run_node);
237
238                 if (vruntime == cfs_rq->min_vruntime)
239                         vruntime = se->vruntime;
240                 else
241                         vruntime = min_vruntime(vruntime, se->vruntime);
242         }
243
244         cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
245 }
246
247 /*
248  * Enqueue an entity into the rb-tree:
249  */
250 static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
251 {
252         struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
253         struct rb_node *parent = NULL;
254         struct sched_entity *entry;
255         s64 key = entity_key(cfs_rq, se);
256         int leftmost = 1;
257
258         /*
259          * Find the right place in the rbtree:
260          */
261         while (*link) {
262                 parent = *link;
263                 entry = rb_entry(parent, struct sched_entity, run_node);
264                 /*
265                  * We dont care about collisions. Nodes with
266                  * the same key stay together.
267                  */
268                 if (key < entity_key(cfs_rq, entry)) {
269                         link = &parent->rb_left;
270                 } else {
271                         link = &parent->rb_right;
272                         leftmost = 0;
273                 }
274         }
275
276         /*
277          * Maintain a cache of leftmost tree entries (it is frequently
278          * used):
279          */
280         if (leftmost)
281                 cfs_rq->rb_leftmost = &se->run_node;
282
283         rb_link_node(&se->run_node, parent, link);
284         rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
285 }
286
287 static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
288 {
289         if (cfs_rq->rb_leftmost == &se->run_node) {
290                 struct rb_node *next_node;
291
292                 next_node = rb_next(&se->run_node);
293                 cfs_rq->rb_leftmost = next_node;
294         }
295
296         if (cfs_rq->next == se)
297                 cfs_rq->next = NULL;
298
299         rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
300 }
301
302 static inline struct rb_node *first_fair(struct cfs_rq *cfs_rq)
303 {
304         return cfs_rq->rb_leftmost;
305 }
306
307 static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
308 {
309         return rb_entry(first_fair(cfs_rq), struct sched_entity, run_node);
310 }
311
312 static inline struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
313 {
314         struct rb_node *last = rb_last(&cfs_rq->tasks_timeline);
315
316         if (!last)
317                 return NULL;
318
319         return rb_entry(last, struct sched_entity, run_node);
320 }
321
322 /**************************************************************
323  * Scheduling class statistics methods:
324  */
325
326 #ifdef CONFIG_SCHED_DEBUG
327 int sched_nr_latency_handler(struct ctl_table *table, int write,
328                 struct file *filp, void __user *buffer, size_t *lenp,
329                 loff_t *ppos)
330 {
331         int ret = proc_dointvec_minmax(table, write, filp, buffer, lenp, ppos);
332
333         if (ret || !write)
334                 return ret;
335
336         sched_nr_latency = DIV_ROUND_UP(sysctl_sched_latency,
337                                         sysctl_sched_min_granularity);
338
339         return 0;
340 }
341 #endif
342
343 /*
344  * delta *= P[w / rw]
345  */
346 static inline unsigned long
347 calc_delta_weight(unsigned long delta, struct sched_entity *se)
348 {
349         for_each_sched_entity(se) {
350                 delta = calc_delta_mine(delta,
351                                 se->load.weight, &cfs_rq_of(se)->load);
352         }
353
354         return delta;
355 }
356
357 /*
358  * delta /= w
359  */
360 static inline unsigned long
361 calc_delta_fair(unsigned long delta, struct sched_entity *se)
362 {
363         if (unlikely(se->load.weight != NICE_0_LOAD))
364                 delta = calc_delta_mine(delta, NICE_0_LOAD, &se->load);
365
366         return delta;
367 }
368
369 /*
370  * The idea is to set a period in which each task runs once.
371  *
372  * When there are too many tasks (sysctl_sched_nr_latency) we have to stretch
373  * this period because otherwise the slices get too small.
374  *
375  * p = (nr <= nl) ? l : l*nr/nl
376  */
377 static u64 __sched_period(unsigned long nr_running)
378 {
379         u64 period = sysctl_sched_latency;
380         unsigned long nr_latency = sched_nr_latency;
381
382         if (unlikely(nr_running > nr_latency)) {
383                 period = sysctl_sched_min_granularity;
384                 period *= nr_running;
385         }
386
387         return period;
388 }
389
390 /*
391  * We calculate the wall-time slice from the period by taking a part
392  * proportional to the weight.
393  *
394  * s = p*P[w/rw]
395  */
396 static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
397 {
398         unsigned long nr_running = cfs_rq->nr_running;
399
400         if (unlikely(!se->on_rq))
401                 nr_running++;
402
403         return calc_delta_weight(__sched_period(nr_running), se);
404 }
405
406 /*
407  * We calculate the vruntime slice of a to be inserted task
408  *
409  * vs = s/w
410  */
411 static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
412 {
413         return calc_delta_fair(sched_slice(cfs_rq, se), se);
414 }
415
416 /*
417  * Update the current task's runtime statistics. Skip current tasks that
418  * are not in our scheduling class.
419  */
420 static inline void
421 __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
422               unsigned long delta_exec)
423 {
424         unsigned long delta_exec_weighted;
425
426         schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
427
428         curr->sum_exec_runtime += delta_exec;
429         schedstat_add(cfs_rq, exec_clock, delta_exec);
430         delta_exec_weighted = calc_delta_fair(delta_exec, curr);
431         curr->vruntime += delta_exec_weighted;
432         update_min_vruntime(cfs_rq);
433 }
434
435 static void update_curr(struct cfs_rq *cfs_rq)
436 {
437         struct sched_entity *curr = cfs_rq->curr;
438         u64 now = rq_of(cfs_rq)->clock;
439         unsigned long delta_exec;
440
441         if (unlikely(!curr))
442                 return;
443
444         /*
445          * Get the amount of time the current task was running
446          * since the last time we changed load (this cannot
447          * overflow on 32 bits):
448          */
449         delta_exec = (unsigned long)(now - curr->exec_start);
450
451         __update_curr(cfs_rq, curr, delta_exec);
452         curr->exec_start = now;
453
454         if (entity_is_task(curr)) {
455                 struct task_struct *curtask = task_of(curr);
456
457                 cpuacct_charge(curtask, delta_exec);
458                 account_group_exec_runtime(curtask, delta_exec);
459         }
460 }
461
462 static inline void
463 update_stats_wait_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
464 {
465         schedstat_set(se->wait_start, rq_of(cfs_rq)->clock);
466 }
467
468 /*
469  * Task is being enqueued - update stats:
470  */
471 static void update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
472 {
473         /*
474          * Are we enqueueing a waiting task? (for current tasks
475          * a dequeue/enqueue event is a NOP)
476          */
477         if (se != cfs_rq->curr)
478                 update_stats_wait_start(cfs_rq, se);
479 }
480
481 static void
482 update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se)
483 {
484         schedstat_set(se->wait_max, max(se->wait_max,
485                         rq_of(cfs_rq)->clock - se->wait_start));
486         schedstat_set(se->wait_count, se->wait_count + 1);
487         schedstat_set(se->wait_sum, se->wait_sum +
488                         rq_of(cfs_rq)->clock - se->wait_start);
489         schedstat_set(se->wait_start, 0);
490 }
491
492 static inline void
493 update_stats_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
494 {
495         /*
496          * Mark the end of the wait period if dequeueing a
497          * waiting task:
498          */
499         if (se != cfs_rq->curr)
500                 update_stats_wait_end(cfs_rq, se);
501 }
502
503 /*
504  * We are picking a new current task - update its stats:
505  */
506 static inline void
507 update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
508 {
509         /*
510          * We are starting a new run period:
511          */
512         se->exec_start = rq_of(cfs_rq)->clock;
513 }
514
515 /**************************************************
516  * Scheduling class queueing methods:
517  */
518
519 #if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
520 static void
521 add_cfs_task_weight(struct cfs_rq *cfs_rq, unsigned long weight)
522 {
523         cfs_rq->task_weight += weight;
524 }
525 #else
526 static inline void
527 add_cfs_task_weight(struct cfs_rq *cfs_rq, unsigned long weight)
528 {
529 }
530 #endif
531
532 static void
533 account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
534 {
535         update_load_add(&cfs_rq->load, se->load.weight);
536         if (!parent_entity(se))
537                 inc_cpu_load(rq_of(cfs_rq), se->load.weight);
538         if (entity_is_task(se)) {
539                 add_cfs_task_weight(cfs_rq, se->load.weight);
540                 list_add(&se->group_node, &cfs_rq->tasks);
541         }
542         cfs_rq->nr_running++;
543         se->on_rq = 1;
544 }
545
546 static void
547 account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
548 {
549         update_load_sub(&cfs_rq->load, se->load.weight);
550         if (!parent_entity(se))
551                 dec_cpu_load(rq_of(cfs_rq), se->load.weight);
552         if (entity_is_task(se)) {
553                 add_cfs_task_weight(cfs_rq, -se->load.weight);
554                 list_del_init(&se->group_node);
555         }
556         cfs_rq->nr_running--;
557         se->on_rq = 0;
558 }
559
560 static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
561 {
562 #ifdef CONFIG_SCHEDSTATS
563         if (se->sleep_start) {
564                 u64 delta = rq_of(cfs_rq)->clock - se->sleep_start;
565                 struct task_struct *tsk = task_of(se);
566
567                 if ((s64)delta < 0)
568                         delta = 0;
569
570                 if (unlikely(delta > se->sleep_max))
571                         se->sleep_max = delta;
572
573                 se->sleep_start = 0;
574                 se->sum_sleep_runtime += delta;
575
576                 account_scheduler_latency(tsk, delta >> 10, 1);
577         }
578         if (se->block_start) {
579                 u64 delta = rq_of(cfs_rq)->clock - se->block_start;
580                 struct task_struct *tsk = task_of(se);
581
582                 if ((s64)delta < 0)
583                         delta = 0;
584
585                 if (unlikely(delta > se->block_max))
586                         se->block_max = delta;
587
588                 se->block_start = 0;
589                 se->sum_sleep_runtime += delta;
590
591                 /*
592                  * Blocking time is in units of nanosecs, so shift by 20 to
593                  * get a milliseconds-range estimation of the amount of
594                  * time that the task spent sleeping:
595                  */
596                 if (unlikely(prof_on == SLEEP_PROFILING)) {
597
598                         profile_hits(SLEEP_PROFILING, (void *)get_wchan(tsk),
599                                      delta >> 20);
600                 }
601                 account_scheduler_latency(tsk, delta >> 10, 0);
602         }
603 #endif
604 }
605
606 static void check_spread(struct cfs_rq *cfs_rq, struct sched_entity *se)
607 {
608 #ifdef CONFIG_SCHED_DEBUG
609         s64 d = se->vruntime - cfs_rq->min_vruntime;
610
611         if (d < 0)
612                 d = -d;
613
614         if (d > 3*sysctl_sched_latency)
615                 schedstat_inc(cfs_rq, nr_spread_over);
616 #endif
617 }
618
619 static void
620 place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
621 {
622         u64 vruntime = cfs_rq->min_vruntime;
623
624         /*
625          * The 'current' period is already promised to the current tasks,
626          * however the extra weight of the new task will slow them down a
627          * little, place the new task so that it fits in the slot that
628          * stays open at the end.
629          */
630         if (initial && sched_feat(START_DEBIT))
631                 vruntime += sched_vslice(cfs_rq, se);
632
633         if (!initial) {
634                 /* sleeps upto a single latency don't count. */
635                 if (sched_feat(NEW_FAIR_SLEEPERS)) {
636                         unsigned long thresh = sysctl_sched_latency;
637
638                         /*
639                          * convert the sleeper threshold into virtual time
640                          */
641                         if (sched_feat(NORMALIZED_SLEEPER))
642                                 thresh = calc_delta_fair(thresh, se);
643
644                         vruntime -= thresh;
645                 }
646
647                 /* ensure we never gain time by being placed backwards. */
648                 vruntime = max_vruntime(se->vruntime, vruntime);
649         }
650
651         se->vruntime = vruntime;
652 }
653
654 static void
655 enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int wakeup)
656 {
657         /*
658          * Update run-time statistics of the 'current'.
659          */
660         update_curr(cfs_rq);
661         account_entity_enqueue(cfs_rq, se);
662
663         if (wakeup) {
664                 place_entity(cfs_rq, se, 0);
665                 enqueue_sleeper(cfs_rq, se);
666         }
667
668         update_stats_enqueue(cfs_rq, se);
669         check_spread(cfs_rq, se);
670         if (se != cfs_rq->curr)
671                 __enqueue_entity(cfs_rq, se);
672 }
673
674 static void
675 dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int sleep)
676 {
677         /*
678          * Update run-time statistics of the 'current'.
679          */
680         update_curr(cfs_rq);
681
682         update_stats_dequeue(cfs_rq, se);
683         if (sleep) {
684 #ifdef CONFIG_SCHEDSTATS
685                 if (entity_is_task(se)) {
686                         struct task_struct *tsk = task_of(se);
687
688                         if (tsk->state & TASK_INTERRUPTIBLE)
689                                 se->sleep_start = rq_of(cfs_rq)->clock;
690                         if (tsk->state & TASK_UNINTERRUPTIBLE)
691                                 se->block_start = rq_of(cfs_rq)->clock;
692                 }
693 #endif
694         }
695
696         if (se != cfs_rq->curr)
697                 __dequeue_entity(cfs_rq, se);
698         account_entity_dequeue(cfs_rq, se);
699         update_min_vruntime(cfs_rq);
700 }
701
702 /*
703  * Preempt the current task with a newly woken task if needed:
704  */
705 static void
706 check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
707 {
708         unsigned long ideal_runtime, delta_exec;
709
710         ideal_runtime = sched_slice(cfs_rq, curr);
711         delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
712         if (delta_exec > ideal_runtime)
713                 resched_task(rq_of(cfs_rq)->curr);
714 }
715
716 static void
717 set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
718 {
719         /* 'current' is not kept within the tree. */
720         if (se->on_rq) {
721                 /*
722                  * Any task has to be enqueued before it get to execute on
723                  * a CPU. So account for the time it spent waiting on the
724                  * runqueue.
725                  */
726                 update_stats_wait_end(cfs_rq, se);
727                 __dequeue_entity(cfs_rq, se);
728         }
729
730         update_stats_curr_start(cfs_rq, se);
731         cfs_rq->curr = se;
732 #ifdef CONFIG_SCHEDSTATS
733         /*
734          * Track our maximum slice length, if the CPU's load is at
735          * least twice that of our own weight (i.e. dont track it
736          * when there are only lesser-weight tasks around):
737          */
738         if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {
739                 se->slice_max = max(se->slice_max,
740                         se->sum_exec_runtime - se->prev_sum_exec_runtime);
741         }
742 #endif
743         se->prev_sum_exec_runtime = se->sum_exec_runtime;
744 }
745
746 static struct sched_entity *
747 pick_next(struct cfs_rq *cfs_rq, struct sched_entity *se)
748 {
749         struct rq *rq = rq_of(cfs_rq);
750         u64 pair_slice = rq->clock - cfs_rq->pair_start;
751
752         if (!cfs_rq->next || pair_slice > sysctl_sched_min_granularity) {
753                 cfs_rq->pair_start = rq->clock;
754                 return se;
755         }
756
757         return cfs_rq->next;
758 }
759
760 static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
761 {
762         struct sched_entity *se = NULL;
763
764         if (first_fair(cfs_rq)) {
765                 se = __pick_next_entity(cfs_rq);
766                 se = pick_next(cfs_rq, se);
767                 set_next_entity(cfs_rq, se);
768         }
769
770         return se;
771 }
772
773 static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
774 {
775         /*
776          * If still on the runqueue then deactivate_task()
777          * was not called and update_curr() has to be done:
778          */
779         if (prev->on_rq)
780                 update_curr(cfs_rq);
781
782         check_spread(cfs_rq, prev);
783         if (prev->on_rq) {
784                 update_stats_wait_start(cfs_rq, prev);
785                 /* Put 'current' back into the tree. */
786                 __enqueue_entity(cfs_rq, prev);
787         }
788         cfs_rq->curr = NULL;
789 }
790
791 static void
792 entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
793 {
794         /*
795          * Update run-time statistics of the 'current'.
796          */
797         update_curr(cfs_rq);
798
799 #ifdef CONFIG_SCHED_HRTICK
800         /*
801          * queued ticks are scheduled to match the slice, so don't bother
802          * validating it and just reschedule.
803          */
804         if (queued) {
805                 resched_task(rq_of(cfs_rq)->curr);
806                 return;
807         }
808         /*
809          * don't let the period tick interfere with the hrtick preemption
810          */
811         if (!sched_feat(DOUBLE_TICK) &&
812                         hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))
813                 return;
814 #endif
815
816         if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))
817                 check_preempt_tick(cfs_rq, curr);
818 }
819
820 /**************************************************
821  * CFS operations on tasks:
822  */
823
824 #ifdef CONFIG_SCHED_HRTICK
825 static void hrtick_start_fair(struct rq *rq, struct task_struct *p)
826 {
827         struct sched_entity *se = &p->se;
828         struct cfs_rq *cfs_rq = cfs_rq_of(se);
829
830         WARN_ON(task_rq(p) != rq);
831
832         if (hrtick_enabled(rq) && cfs_rq->nr_running > 1) {
833                 u64 slice = sched_slice(cfs_rq, se);
834                 u64 ran = se->sum_exec_runtime - se->prev_sum_exec_runtime;
835                 s64 delta = slice - ran;
836
837                 if (delta < 0) {
838                         if (rq->curr == p)
839                                 resched_task(p);
840                         return;
841                 }
842
843                 /*
844                  * Don't schedule slices shorter than 10000ns, that just
845                  * doesn't make sense. Rely on vruntime for fairness.
846                  */
847                 if (rq->curr != p)
848                         delta = max_t(s64, 10000LL, delta);
849
850                 hrtick_start(rq, delta);
851         }
852 }
853
854 /*
855  * called from enqueue/dequeue and updates the hrtick when the
856  * current task is from our class and nr_running is low enough
857  * to matter.
858  */
859 static void hrtick_update(struct rq *rq)
860 {
861         struct task_struct *curr = rq->curr;
862
863         if (curr->sched_class != &fair_sched_class)
864                 return;
865
866         if (cfs_rq_of(&curr->se)->nr_running < sched_nr_latency)
867                 hrtick_start_fair(rq, curr);
868 }
869 #else /* !CONFIG_SCHED_HRTICK */
870 static inline void
871 hrtick_start_fair(struct rq *rq, struct task_struct *p)
872 {
873 }
874
875 static inline void hrtick_update(struct rq *rq)
876 {
877 }
878 #endif
879
880 /*
881  * The enqueue_task method is called before nr_running is
882  * increased. Here we update the fair scheduling stats and
883  * then put the task into the rbtree:
884  */
885 static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup)
886 {
887         struct cfs_rq *cfs_rq;
888         struct sched_entity *se = &p->se;
889
890         for_each_sched_entity(se) {
891                 if (se->on_rq)
892                         break;
893                 cfs_rq = cfs_rq_of(se);
894                 enqueue_entity(cfs_rq, se, wakeup);
895                 wakeup = 1;
896         }
897
898         hrtick_update(rq);
899 }
900
901 /*
902  * The dequeue_task method is called before nr_running is
903  * decreased. We remove the task from the rbtree and
904  * update the fair scheduling stats:
905  */
906 static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int sleep)
907 {
908         struct cfs_rq *cfs_rq;
909         struct sched_entity *se = &p->se;
910
911         for_each_sched_entity(se) {
912                 cfs_rq = cfs_rq_of(se);
913                 dequeue_entity(cfs_rq, se, sleep);
914                 /* Don't dequeue parent if it has other entities besides us */
915                 if (cfs_rq->load.weight)
916                         break;
917                 sleep = 1;
918         }
919
920         hrtick_update(rq);
921 }
922
923 /*
924  * sched_yield() support is very simple - we dequeue and enqueue.
925  *
926  * If compat_yield is turned on then we requeue to the end of the tree.
927  */
928 static void yield_task_fair(struct rq *rq)
929 {
930         struct task_struct *curr = rq->curr;
931         struct cfs_rq *cfs_rq = task_cfs_rq(curr);
932         struct sched_entity *rightmost, *se = &curr->se;
933
934         /*
935          * Are we the only task in the tree?
936          */
937         if (unlikely(cfs_rq->nr_running == 1))
938                 return;
939
940         if (likely(!sysctl_sched_compat_yield) && curr->policy != SCHED_BATCH) {
941                 update_rq_clock(rq);
942                 /*
943                  * Update run-time statistics of the 'current'.
944                  */
945                 update_curr(cfs_rq);
946
947                 return;
948         }
949         /*
950          * Find the rightmost entry in the rbtree:
951          */
952         rightmost = __pick_last_entity(cfs_rq);
953         /*
954          * Already in the rightmost position?
955          */
956         if (unlikely(!rightmost || rightmost->vruntime < se->vruntime))
957                 return;
958
959         /*
960          * Minimally necessary key value to be last in the tree:
961          * Upon rescheduling, sched_class::put_prev_task() will place
962          * 'current' within the tree based on its new key value.
963          */
964         se->vruntime = rightmost->vruntime + 1;
965 }
966
967 /*
968  * wake_idle() will wake a task on an idle cpu if task->cpu is
969  * not idle and an idle cpu is available.  The span of cpus to
970  * search starts with cpus closest then further out as needed,
971  * so we always favor a closer, idle cpu.
972  * Domains may include CPUs that are not usable for migration,
973  * hence we need to mask them out (cpu_active_map)
974  *
975  * Returns the CPU we should wake onto.
976  */
977 #if defined(ARCH_HAS_SCHED_WAKE_IDLE)
978 static int wake_idle(int cpu, struct task_struct *p)
979 {
980         cpumask_t tmp;
981         struct sched_domain *sd;
982         int i;
983
984         /*
985          * If it is idle, then it is the best cpu to run this task.
986          *
987          * This cpu is also the best, if it has more than one task already.
988          * Siblings must be also busy(in most cases) as they didn't already
989          * pickup the extra load from this cpu and hence we need not check
990          * sibling runqueue info. This will avoid the checks and cache miss
991          * penalities associated with that.
992          */
993         if (idle_cpu(cpu) || cpu_rq(cpu)->cfs.nr_running > 1)
994                 return cpu;
995
996         for_each_domain(cpu, sd) {
997                 if ((sd->flags & SD_WAKE_IDLE)
998                     || ((sd->flags & SD_WAKE_IDLE_FAR)
999                         && !task_hot(p, task_rq(p)->clock, sd))) {
1000                         cpus_and(tmp, sd->span, p->cpus_allowed);
1001                         cpus_and(tmp, tmp, cpu_active_map);
1002                         for_each_cpu_mask_nr(i, tmp) {
1003                                 if (idle_cpu(i)) {
1004                                         if (i != task_cpu(p)) {
1005                                                 schedstat_inc(p,
1006                                                        se.nr_wakeups_idle);
1007                                         }
1008                                         return i;
1009                                 }
1010                         }
1011                 } else {
1012                         break;
1013                 }
1014         }
1015         return cpu;
1016 }
1017 #else /* !ARCH_HAS_SCHED_WAKE_IDLE*/
1018 static inline int wake_idle(int cpu, struct task_struct *p)
1019 {
1020         return cpu;
1021 }
1022 #endif
1023
1024 #ifdef CONFIG_SMP
1025
1026 #ifdef CONFIG_FAIR_GROUP_SCHED
1027 /*
1028  * effective_load() calculates the load change as seen from the root_task_group
1029  *
1030  * Adding load to a group doesn't make a group heavier, but can cause movement
1031  * of group shares between cpus. Assuming the shares were perfectly aligned one
1032  * can calculate the shift in shares.
1033  *
1034  * The problem is that perfectly aligning the shares is rather expensive, hence
1035  * we try to avoid doing that too often - see update_shares(), which ratelimits
1036  * this change.
1037  *
1038  * We compensate this by not only taking the current delta into account, but
1039  * also considering the delta between when the shares were last adjusted and
1040  * now.
1041  *
1042  * We still saw a performance dip, some tracing learned us that between
1043  * cgroup:/ and cgroup:/foo balancing the number of affine wakeups increased
1044  * significantly. Therefore try to bias the error in direction of failing
1045  * the affine wakeup.
1046  *
1047  */
1048 static long effective_load(struct task_group *tg, int cpu,
1049                 long wl, long wg)
1050 {
1051         struct sched_entity *se = tg->se[cpu];
1052
1053         if (!tg->parent)
1054                 return wl;
1055
1056         /*
1057          * By not taking the decrease of shares on the other cpu into
1058          * account our error leans towards reducing the affine wakeups.
1059          */
1060         if (!wl && sched_feat(ASYM_EFF_LOAD))
1061                 return wl;
1062
1063         for_each_sched_entity(se) {
1064                 long S, rw, s, a, b;
1065                 long more_w;
1066
1067                 /*
1068                  * Instead of using this increment, also add the difference
1069                  * between when the shares were last updated and now.
1070                  */
1071                 more_w = se->my_q->load.weight - se->my_q->rq_weight;
1072                 wl += more_w;
1073                 wg += more_w;
1074
1075                 S = se->my_q->tg->shares;
1076                 s = se->my_q->shares;
1077                 rw = se->my_q->rq_weight;
1078
1079                 a = S*(rw + wl);
1080                 b = S*rw + s*wg;
1081
1082                 wl = s*(a-b);
1083
1084                 if (likely(b))
1085                         wl /= b;
1086
1087                 /*
1088                  * Assume the group is already running and will
1089                  * thus already be accounted for in the weight.
1090                  *
1091                  * That is, moving shares between CPUs, does not
1092                  * alter the group weight.
1093                  */
1094                 wg = 0;
1095         }
1096
1097         return wl;
1098 }
1099
1100 #else
1101
1102 static inline unsigned long effective_load(struct task_group *tg, int cpu,
1103                 unsigned long wl, unsigned long wg)
1104 {
1105         return wl;
1106 }
1107
1108 #endif
1109
1110 static int
1111 wake_affine(struct sched_domain *this_sd, struct rq *this_rq,
1112             struct task_struct *p, int prev_cpu, int this_cpu, int sync,
1113             int idx, unsigned long load, unsigned long this_load,
1114             unsigned int imbalance)
1115 {
1116         struct task_struct *curr = this_rq->curr;
1117         struct task_group *tg;
1118         unsigned long tl = this_load;
1119         unsigned long tl_per_task;
1120         unsigned long weight;
1121         int balanced;
1122
1123         if (!(this_sd->flags & SD_WAKE_AFFINE) || !sched_feat(AFFINE_WAKEUPS))
1124                 return 0;
1125
1126         if (!sync && sched_feat(SYNC_WAKEUPS) &&
1127             curr->se.avg_overlap < sysctl_sched_migration_cost &&
1128             p->se.avg_overlap < sysctl_sched_migration_cost)
1129                 sync = 1;
1130
1131         /*
1132          * If sync wakeup then subtract the (maximum possible)
1133          * effect of the currently running task from the load
1134          * of the current CPU:
1135          */
1136         if (sync) {
1137                 tg = task_group(current);
1138                 weight = current->se.load.weight;
1139
1140                 tl += effective_load(tg, this_cpu, -weight, -weight);
1141                 load += effective_load(tg, prev_cpu, 0, -weight);
1142         }
1143
1144         tg = task_group(p);
1145         weight = p->se.load.weight;
1146
1147         balanced = 100*(tl + effective_load(tg, this_cpu, weight, weight)) <=
1148                 imbalance*(load + effective_load(tg, prev_cpu, 0, weight));
1149
1150         /*
1151          * If the currently running task will sleep within
1152          * a reasonable amount of time then attract this newly
1153          * woken task:
1154          */
1155         if (sync && balanced)
1156                 return 1;
1157
1158         schedstat_inc(p, se.nr_wakeups_affine_attempts);
1159         tl_per_task = cpu_avg_load_per_task(this_cpu);
1160
1161         if (balanced || (tl <= load && tl + target_load(prev_cpu, idx) <=
1162                         tl_per_task)) {
1163                 /*
1164                  * This domain has SD_WAKE_AFFINE and
1165                  * p is cache cold in this domain, and
1166                  * there is no bad imbalance.
1167                  */
1168                 schedstat_inc(this_sd, ttwu_move_affine);
1169                 schedstat_inc(p, se.nr_wakeups_affine);
1170
1171                 return 1;
1172         }
1173         return 0;
1174 }
1175
1176 static int select_task_rq_fair(struct task_struct *p, int sync)
1177 {
1178         struct sched_domain *sd, *this_sd = NULL;
1179         int prev_cpu, this_cpu, new_cpu;
1180         unsigned long load, this_load;
1181         struct rq *this_rq;
1182         unsigned int imbalance;
1183         int idx;
1184
1185         prev_cpu        = task_cpu(p);
1186         this_cpu        = smp_processor_id();
1187         this_rq         = cpu_rq(this_cpu);
1188         new_cpu         = prev_cpu;
1189
1190         if (prev_cpu == this_cpu)
1191                 goto out;
1192         /*
1193          * 'this_sd' is the first domain that both
1194          * this_cpu and prev_cpu are present in:
1195          */
1196         for_each_domain(this_cpu, sd) {
1197                 if (cpu_isset(prev_cpu, sd->span)) {
1198                         this_sd = sd;
1199                         break;
1200                 }
1201         }
1202
1203         if (unlikely(!cpu_isset(this_cpu, p->cpus_allowed)))
1204                 goto out;
1205
1206         /*
1207          * Check for affine wakeup and passive balancing possibilities.
1208          */
1209         if (!this_sd)
1210                 goto out;
1211
1212         idx = this_sd->wake_idx;
1213
1214         imbalance = 100 + (this_sd->imbalance_pct - 100) / 2;
1215
1216         load = source_load(prev_cpu, idx);
1217         this_load = target_load(this_cpu, idx);
1218
1219         if (wake_affine(this_sd, this_rq, p, prev_cpu, this_cpu, sync, idx,
1220                                      load, this_load, imbalance))
1221                 return this_cpu;
1222
1223         /*
1224          * Start passive balancing when half the imbalance_pct
1225          * limit is reached.
1226          */
1227         if (this_sd->flags & SD_WAKE_BALANCE) {
1228                 if (imbalance*this_load <= 100*load) {
1229                         schedstat_inc(this_sd, ttwu_move_balance);
1230                         schedstat_inc(p, se.nr_wakeups_passive);
1231                         return this_cpu;
1232                 }
1233         }
1234
1235 out:
1236         return wake_idle(new_cpu, p);
1237 }
1238 #endif /* CONFIG_SMP */
1239
1240 static unsigned long wakeup_gran(struct sched_entity *se)
1241 {
1242         unsigned long gran = sysctl_sched_wakeup_granularity;
1243
1244         /*
1245          * More easily preempt - nice tasks, while not making it harder for
1246          * + nice tasks.
1247          */
1248         if (sched_feat(ASYM_GRAN))
1249                 gran = calc_delta_mine(gran, NICE_0_LOAD, &se->load);
1250
1251         return gran;
1252 }
1253
1254 /*
1255  * Preempt the current task with a newly woken task if needed:
1256  */
1257 static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int sync)
1258 {
1259         struct task_struct *curr = rq->curr;
1260         struct cfs_rq *cfs_rq = task_cfs_rq(curr);
1261         struct sched_entity *se = &curr->se, *pse = &p->se;
1262         s64 delta_exec;
1263
1264         if (unlikely(rt_prio(p->prio))) {
1265                 update_rq_clock(rq);
1266                 update_curr(cfs_rq);
1267                 resched_task(curr);
1268                 return;
1269         }
1270
1271         if (unlikely(se == pse))
1272                 return;
1273
1274         cfs_rq_of(pse)->next = pse;
1275
1276         /*
1277          * We can come here with TIF_NEED_RESCHED already set from new task
1278          * wake up path.
1279          */
1280         if (test_tsk_need_resched(curr))
1281                 return;
1282
1283         /*
1284          * Batch tasks do not preempt (their preemption is driven by
1285          * the tick):
1286          */
1287         if (unlikely(p->policy == SCHED_BATCH))
1288                 return;
1289
1290         if (!sched_feat(WAKEUP_PREEMPT))
1291                 return;
1292
1293         if (sched_feat(WAKEUP_OVERLAP) && (sync ||
1294                         (se->avg_overlap < sysctl_sched_migration_cost &&
1295                          pse->avg_overlap < sysctl_sched_migration_cost))) {
1296                 resched_task(curr);
1297                 return;
1298         }
1299
1300         delta_exec = se->sum_exec_runtime - se->prev_sum_exec_runtime;
1301         if (delta_exec > wakeup_gran(pse))
1302                 resched_task(curr);
1303 }
1304
1305 static struct task_struct *pick_next_task_fair(struct rq *rq)
1306 {
1307         struct task_struct *p;
1308         struct cfs_rq *cfs_rq = &rq->cfs;
1309         struct sched_entity *se;
1310
1311         if (unlikely(!cfs_rq->nr_running))
1312                 return NULL;
1313
1314         do {
1315                 se = pick_next_entity(cfs_rq);
1316                 cfs_rq = group_cfs_rq(se);
1317         } while (cfs_rq);
1318
1319         p = task_of(se);
1320         hrtick_start_fair(rq, p);
1321
1322         return p;
1323 }
1324
1325 /*
1326  * Account for a descheduled task:
1327  */
1328 static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
1329 {
1330         struct sched_entity *se = &prev->se;
1331         struct cfs_rq *cfs_rq;
1332
1333         for_each_sched_entity(se) {
1334                 cfs_rq = cfs_rq_of(se);
1335                 put_prev_entity(cfs_rq, se);
1336         }
1337 }
1338
1339 #ifdef CONFIG_SMP
1340 /**************************************************
1341  * Fair scheduling class load-balancing methods:
1342  */
1343
1344 /*
1345  * Load-balancing iterator. Note: while the runqueue stays locked
1346  * during the whole iteration, the current task might be
1347  * dequeued so the iterator has to be dequeue-safe. Here we
1348  * achieve that by always pre-iterating before returning
1349  * the current task:
1350  */
1351 static struct task_struct *
1352 __load_balance_iterator(struct cfs_rq *cfs_rq, struct list_head *next)
1353 {
1354         struct task_struct *p = NULL;
1355         struct sched_entity *se;
1356
1357         if (next == &cfs_rq->tasks)
1358                 return NULL;
1359
1360         se = list_entry(next, struct sched_entity, group_node);
1361         p = task_of(se);
1362         cfs_rq->balance_iterator = next->next;
1363
1364         return p;
1365 }
1366
1367 static struct task_struct *load_balance_start_fair(void *arg)
1368 {
1369         struct cfs_rq *cfs_rq = arg;
1370
1371         return __load_balance_iterator(cfs_rq, cfs_rq->tasks.next);
1372 }
1373
1374 static struct task_struct *load_balance_next_fair(void *arg)
1375 {
1376         struct cfs_rq *cfs_rq = arg;
1377
1378         return __load_balance_iterator(cfs_rq, cfs_rq->balance_iterator);
1379 }
1380
1381 static unsigned long
1382 __load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
1383                 unsigned long max_load_move, struct sched_domain *sd,
1384                 enum cpu_idle_type idle, int *all_pinned, int *this_best_prio,
1385                 struct cfs_rq *cfs_rq)
1386 {
1387         struct rq_iterator cfs_rq_iterator;
1388
1389         cfs_rq_iterator.start = load_balance_start_fair;
1390         cfs_rq_iterator.next = load_balance_next_fair;
1391         cfs_rq_iterator.arg = cfs_rq;
1392
1393         return balance_tasks(this_rq, this_cpu, busiest,
1394                         max_load_move, sd, idle, all_pinned,
1395                         this_best_prio, &cfs_rq_iterator);
1396 }
1397
1398 #ifdef CONFIG_FAIR_GROUP_SCHED
1399 static unsigned long
1400 load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
1401                   unsigned long max_load_move,
1402                   struct sched_domain *sd, enum cpu_idle_type idle,
1403                   int *all_pinned, int *this_best_prio)
1404 {
1405         long rem_load_move = max_load_move;
1406         int busiest_cpu = cpu_of(busiest);
1407         struct task_group *tg;
1408
1409         rcu_read_lock();
1410         update_h_load(busiest_cpu);
1411
1412         list_for_each_entry_rcu(tg, &task_groups, list) {
1413                 struct cfs_rq *busiest_cfs_rq = tg->cfs_rq[busiest_cpu];
1414                 unsigned long busiest_h_load = busiest_cfs_rq->h_load;
1415                 unsigned long busiest_weight = busiest_cfs_rq->load.weight;
1416                 u64 rem_load, moved_load;
1417
1418                 /*
1419                  * empty group
1420                  */
1421                 if (!busiest_cfs_rq->task_weight)
1422                         continue;
1423
1424                 rem_load = (u64)rem_load_move * busiest_weight;
1425                 rem_load = div_u64(rem_load, busiest_h_load + 1);
1426
1427                 moved_load = __load_balance_fair(this_rq, this_cpu, busiest,
1428                                 rem_load, sd, idle, all_pinned, this_best_prio,
1429                                 tg->cfs_rq[busiest_cpu]);
1430
1431                 if (!moved_load)
1432                         continue;
1433
1434                 moved_load *= busiest_h_load;
1435                 moved_load = div_u64(moved_load, busiest_weight + 1);
1436
1437                 rem_load_move -= moved_load;
1438                 if (rem_load_move < 0)
1439                         break;
1440         }
1441         rcu_read_unlock();
1442
1443         return max_load_move - rem_load_move;
1444 }
1445 #else
1446 static unsigned long
1447 load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
1448                   unsigned long max_load_move,
1449                   struct sched_domain *sd, enum cpu_idle_type idle,
1450                   int *all_pinned, int *this_best_prio)
1451 {
1452         return __load_balance_fair(this_rq, this_cpu, busiest,
1453                         max_load_move, sd, idle, all_pinned,
1454                         this_best_prio, &busiest->cfs);
1455 }
1456 #endif
1457
1458 static int
1459 move_one_task_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
1460                    struct sched_domain *sd, enum cpu_idle_type idle)
1461 {
1462         struct cfs_rq *busy_cfs_rq;
1463         struct rq_iterator cfs_rq_iterator;
1464
1465         cfs_rq_iterator.start = load_balance_start_fair;
1466         cfs_rq_iterator.next = load_balance_next_fair;
1467
1468         for_each_leaf_cfs_rq(busiest, busy_cfs_rq) {
1469                 /*
1470                  * pass busy_cfs_rq argument into
1471                  * load_balance_[start|next]_fair iterators
1472                  */
1473                 cfs_rq_iterator.arg = busy_cfs_rq;
1474                 if (iter_move_one_task(this_rq, this_cpu, busiest, sd, idle,
1475                                        &cfs_rq_iterator))
1476                     return 1;
1477         }
1478
1479         return 0;
1480 }
1481 #endif /* CONFIG_SMP */
1482
1483 /*
1484  * scheduler tick hitting a task of our scheduling class:
1485  */
1486 static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
1487 {
1488         struct cfs_rq *cfs_rq;
1489         struct sched_entity *se = &curr->se;
1490
1491         for_each_sched_entity(se) {
1492                 cfs_rq = cfs_rq_of(se);
1493                 entity_tick(cfs_rq, se, queued);
1494         }
1495 }
1496
1497 #define swap(a, b) do { typeof(a) tmp = (a); (a) = (b); (b) = tmp; } while (0)
1498
1499 /*
1500  * Share the fairness runtime between parent and child, thus the
1501  * total amount of pressure for CPU stays equal - new tasks
1502  * get a chance to run but frequent forkers are not allowed to
1503  * monopolize the CPU. Note: the parent runqueue is locked,
1504  * the child is not running yet.
1505  */
1506 static void task_new_fair(struct rq *rq, struct task_struct *p)
1507 {
1508         struct cfs_rq *cfs_rq = task_cfs_rq(p);
1509         struct sched_entity *se = &p->se, *curr = cfs_rq->curr;
1510         int this_cpu = smp_processor_id();
1511
1512         sched_info_queued(p);
1513
1514         update_curr(cfs_rq);
1515         place_entity(cfs_rq, se, 1);
1516
1517         /* 'curr' will be NULL if the child belongs to a different group */
1518         if (sysctl_sched_child_runs_first && this_cpu == task_cpu(p) &&
1519                         curr && curr->vruntime < se->vruntime) {
1520                 /*
1521                  * Upon rescheduling, sched_class::put_prev_task() will place
1522                  * 'current' within the tree based on its new key value.
1523                  */
1524                 swap(curr->vruntime, se->vruntime);
1525                 resched_task(rq->curr);
1526         }
1527
1528         enqueue_task_fair(rq, p, 0);
1529 }
1530
1531 /*
1532  * Priority of the task has changed. Check to see if we preempt
1533  * the current task.
1534  */
1535 static void prio_changed_fair(struct rq *rq, struct task_struct *p,
1536                               int oldprio, int running)
1537 {
1538         /*
1539          * Reschedule if we are currently running on this runqueue and
1540          * our priority decreased, or if we are not currently running on
1541          * this runqueue and our priority is higher than the current's
1542          */
1543         if (running) {
1544                 if (p->prio > oldprio)
1545                         resched_task(rq->curr);
1546         } else
1547                 check_preempt_curr(rq, p, 0);
1548 }
1549
1550 /*
1551  * We switched to the sched_fair class.
1552  */
1553 static void switched_to_fair(struct rq *rq, struct task_struct *p,
1554                              int running)
1555 {
1556         /*
1557          * We were most likely switched from sched_rt, so
1558          * kick off the schedule if running, otherwise just see
1559          * if we can still preempt the current task.
1560          */
1561         if (running)
1562                 resched_task(rq->curr);
1563         else
1564                 check_preempt_curr(rq, p, 0);
1565 }
1566
1567 /* Account for a task changing its policy or group.
1568  *
1569  * This routine is mostly called to set cfs_rq->curr field when a task
1570  * migrates between groups/classes.
1571  */
1572 static void set_curr_task_fair(struct rq *rq)
1573 {
1574         struct sched_entity *se = &rq->curr->se;
1575
1576         for_each_sched_entity(se)
1577                 set_next_entity(cfs_rq_of(se), se);
1578 }
1579
1580 #ifdef CONFIG_FAIR_GROUP_SCHED
1581 static void moved_group_fair(struct task_struct *p)
1582 {
1583         struct cfs_rq *cfs_rq = task_cfs_rq(p);
1584
1585         update_curr(cfs_rq);
1586         place_entity(cfs_rq, &p->se, 1);
1587 }
1588 #endif
1589
1590 /*
1591  * All the scheduling class methods:
1592  */
1593 static const struct sched_class fair_sched_class = {
1594         .next                   = &idle_sched_class,
1595         .enqueue_task           = enqueue_task_fair,
1596         .dequeue_task           = dequeue_task_fair,
1597         .yield_task             = yield_task_fair,
1598
1599         .check_preempt_curr     = check_preempt_wakeup,
1600
1601         .pick_next_task         = pick_next_task_fair,
1602         .put_prev_task          = put_prev_task_fair,
1603
1604 #ifdef CONFIG_SMP
1605         .select_task_rq         = select_task_rq_fair,
1606
1607         .load_balance           = load_balance_fair,
1608         .move_one_task          = move_one_task_fair,
1609 #endif
1610
1611         .set_curr_task          = set_curr_task_fair,
1612         .task_tick              = task_tick_fair,
1613         .task_new               = task_new_fair,
1614
1615         .prio_changed           = prio_changed_fair,
1616         .switched_to            = switched_to_fair,
1617
1618 #ifdef CONFIG_FAIR_GROUP_SCHED
1619         .moved_group            = moved_group_fair,
1620 #endif
1621 };
1622
1623 #ifdef CONFIG_SCHED_DEBUG
1624 static void print_cfs_stats(struct seq_file *m, int cpu)
1625 {
1626         struct cfs_rq *cfs_rq;
1627
1628         rcu_read_lock();
1629         for_each_leaf_cfs_rq(cpu_rq(cpu), cfs_rq)
1630                 print_cfs_rq(m, cpu, cfs_rq);
1631         rcu_read_unlock();
1632 }
1633 #endif