sched: max_vruntime() simplification
[linux-2.6] / 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 /*
24  * Targeted preemption latency for CPU-bound tasks:
25  * (default: 20ms, units: nanoseconds)
26  *
27  * NOTE: this latency value is not the same as the concept of
28  * 'timeslice length' - timeslices in CFS are of variable length.
29  * (to see the precise effective timeslice length of your workload,
30  *  run vmstat and monitor the context-switches field)
31  *
32  * On SMP systems the value of this is multiplied by the log2 of the
33  * number of CPUs. (i.e. factor 2x on 2-way systems, 3x on 4-way
34  * systems, 4x on 8-way systems, 5x on 16-way systems, etc.)
35  * Targeted preemption latency for CPU-bound tasks:
36  */
37 const_debug unsigned int sysctl_sched_latency = 20000000ULL;
38
39 /*
40  * After fork, child runs first. (default) If set to 0 then
41  * parent will (try to) run first.
42  */
43 const_debug unsigned int sysctl_sched_child_runs_first = 1;
44
45 /*
46  * Minimal preemption granularity for CPU-bound tasks:
47  * (default: 2 msec, units: nanoseconds)
48  */
49 unsigned int sysctl_sched_min_granularity __read_mostly = 2000000ULL;
50
51 /*
52  * sys_sched_yield() compat mode
53  *
54  * This option switches the agressive yield implementation of the
55  * old scheduler back on.
56  */
57 unsigned int __read_mostly sysctl_sched_compat_yield;
58
59 /*
60  * SCHED_BATCH wake-up granularity.
61  * (default: 25 msec, units: nanoseconds)
62  *
63  * This option delays the preemption effects of decoupled workloads
64  * and reduces their over-scheduling. Synchronous workloads will still
65  * have immediate wakeup/sleep latencies.
66  */
67 const_debug unsigned int sysctl_sched_batch_wakeup_granularity = 25000000UL;
68
69 /*
70  * SCHED_OTHER wake-up granularity.
71  * (default: 1 msec, units: nanoseconds)
72  *
73  * This option delays the preemption effects of decoupled workloads
74  * and reduces their over-scheduling. Synchronous workloads will still
75  * have immediate wakeup/sleep latencies.
76  */
77 const_debug unsigned int sysctl_sched_wakeup_granularity = 2000000UL;
78
79 extern struct sched_class fair_sched_class;
80
81 /**************************************************************
82  * CFS operations on generic schedulable entities:
83  */
84
85 #ifdef CONFIG_FAIR_GROUP_SCHED
86
87 /* cpu runqueue to which this cfs_rq is attached */
88 static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
89 {
90         return cfs_rq->rq;
91 }
92
93 /* An entity is a task if it doesn't "own" a runqueue */
94 #define entity_is_task(se)      (!se->my_q)
95
96 #else   /* CONFIG_FAIR_GROUP_SCHED */
97
98 static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
99 {
100         return container_of(cfs_rq, struct rq, cfs);
101 }
102
103 #define entity_is_task(se)      1
104
105 #endif  /* CONFIG_FAIR_GROUP_SCHED */
106
107 static inline struct task_struct *task_of(struct sched_entity *se)
108 {
109         return container_of(se, struct task_struct, se);
110 }
111
112
113 /**************************************************************
114  * Scheduling class tree data structure manipulation methods:
115  */
116
117 static inline u64
118 max_vruntime(u64 min_vruntime, u64 vruntime)
119 {
120         s64 delta = (s64)(vruntime - min_vruntime);
121         if (delta > 0)
122                 min_vruntime = vruntime;
123
124         return min_vruntime;
125 }
126
127 static inline void
128 set_leftmost(struct cfs_rq *cfs_rq, struct rb_node *leftmost)
129 {
130         struct sched_entity *se;
131
132         cfs_rq->rb_leftmost = leftmost;
133         if (leftmost)
134                 se = rb_entry(leftmost, struct sched_entity, run_node);
135 }
136
137 static inline s64
138 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
139 {
140         return se->vruntime - cfs_rq->min_vruntime;
141 }
142
143 /*
144  * Enqueue an entity into the rb-tree:
145  */
146 static void
147 __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
148 {
149         struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
150         struct rb_node *parent = NULL;
151         struct sched_entity *entry;
152         s64 key = entity_key(cfs_rq, se);
153         int leftmost = 1;
154
155         /*
156          * Find the right place in the rbtree:
157          */
158         while (*link) {
159                 parent = *link;
160                 entry = rb_entry(parent, struct sched_entity, run_node);
161                 /*
162                  * We dont care about collisions. Nodes with
163                  * the same key stay together.
164                  */
165                 if (key < entity_key(cfs_rq, entry)) {
166                         link = &parent->rb_left;
167                 } else {
168                         link = &parent->rb_right;
169                         leftmost = 0;
170                 }
171         }
172
173         /*
174          * Maintain a cache of leftmost tree entries (it is frequently
175          * used):
176          */
177         if (leftmost)
178                 set_leftmost(cfs_rq, &se->run_node);
179
180         rb_link_node(&se->run_node, parent, link);
181         rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
182 }
183
184 static void
185 __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
186 {
187         if (cfs_rq->rb_leftmost == &se->run_node)
188                 set_leftmost(cfs_rq, rb_next(&se->run_node));
189
190         rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
191 }
192
193 static inline struct rb_node *first_fair(struct cfs_rq *cfs_rq)
194 {
195         return cfs_rq->rb_leftmost;
196 }
197
198 static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
199 {
200         return rb_entry(first_fair(cfs_rq), struct sched_entity, run_node);
201 }
202
203 static inline struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
204 {
205         struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
206         struct sched_entity *se = NULL;
207         struct rb_node *parent;
208
209         while (*link) {
210                 parent = *link;
211                 se = rb_entry(parent, struct sched_entity, run_node);
212                 link = &parent->rb_right;
213         }
214
215         return se;
216 }
217
218 /**************************************************************
219  * Scheduling class statistics methods:
220  */
221
222 static u64 __sched_period(unsigned long nr_running)
223 {
224         u64 period = sysctl_sched_latency;
225         unsigned long nr_latency =
226                 sysctl_sched_latency / sysctl_sched_min_granularity;
227
228         if (unlikely(nr_running > nr_latency)) {
229                 period *= nr_running;
230                 do_div(period, nr_latency);
231         }
232
233         return period;
234 }
235
236 static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
237 {
238         u64 period = __sched_period(cfs_rq->nr_running);
239
240         period *= se->load.weight;
241         do_div(period, cfs_rq->load.weight);
242
243         return period;
244 }
245
246 static u64 __sched_vslice(unsigned long nr_running)
247 {
248         u64 period = __sched_period(nr_running);
249
250         do_div(period, nr_running);
251
252         return period;
253 }
254
255 /*
256  * Update the current task's runtime statistics. Skip current tasks that
257  * are not in our scheduling class.
258  */
259 static inline void
260 __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
261               unsigned long delta_exec)
262 {
263         unsigned long delta_exec_weighted;
264         u64 next_vruntime, min_vruntime;
265
266         schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
267
268         curr->sum_exec_runtime += delta_exec;
269         schedstat_add(cfs_rq, exec_clock, delta_exec);
270         delta_exec_weighted = delta_exec;
271         if (unlikely(curr->load.weight != NICE_0_LOAD)) {
272                 delta_exec_weighted = calc_delta_fair(delta_exec_weighted,
273                                                         &curr->load);
274         }
275         curr->vruntime += delta_exec_weighted;
276
277         /*
278          * maintain cfs_rq->min_vruntime to be a monotonic increasing
279          * value tracking the leftmost vruntime in the tree.
280          */
281         if (first_fair(cfs_rq)) {
282                 next_vruntime = __pick_next_entity(cfs_rq)->vruntime;
283
284                 /* min_vruntime() := !max_vruntime() */
285                 min_vruntime = max_vruntime(curr->vruntime, next_vruntime);
286                 if (min_vruntime == next_vruntime)
287                         min_vruntime = curr->vruntime;
288                 else
289                         min_vruntime = next_vruntime;
290         } else
291                 min_vruntime = curr->vruntime;
292
293         cfs_rq->min_vruntime =
294                 max_vruntime(cfs_rq->min_vruntime, min_vruntime);
295 }
296
297 static void update_curr(struct cfs_rq *cfs_rq)
298 {
299         struct sched_entity *curr = cfs_rq->curr;
300         u64 now = rq_of(cfs_rq)->clock;
301         unsigned long delta_exec;
302
303         if (unlikely(!curr))
304                 return;
305
306         /*
307          * Get the amount of time the current task was running
308          * since the last time we changed load (this cannot
309          * overflow on 32 bits):
310          */
311         delta_exec = (unsigned long)(now - curr->exec_start);
312
313         __update_curr(cfs_rq, curr, delta_exec);
314         curr->exec_start = now;
315 }
316
317 static inline void
318 update_stats_wait_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
319 {
320         schedstat_set(se->wait_start, rq_of(cfs_rq)->clock);
321 }
322
323 static inline unsigned long
324 calc_weighted(unsigned long delta, struct sched_entity *se)
325 {
326         unsigned long weight = se->load.weight;
327
328         if (unlikely(weight != NICE_0_LOAD))
329                 return (u64)delta * se->load.weight >> NICE_0_SHIFT;
330         else
331                 return delta;
332 }
333
334 /*
335  * Task is being enqueued - update stats:
336  */
337 static void update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
338 {
339         /*
340          * Are we enqueueing a waiting task? (for current tasks
341          * a dequeue/enqueue event is a NOP)
342          */
343         if (se != cfs_rq->curr)
344                 update_stats_wait_start(cfs_rq, se);
345 }
346
347 static void
348 update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se)
349 {
350         schedstat_set(se->wait_max, max(se->wait_max,
351                         rq_of(cfs_rq)->clock - se->wait_start));
352         schedstat_set(se->wait_start, 0);
353 }
354
355 static inline void
356 update_stats_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
357 {
358         update_curr(cfs_rq);
359         /*
360          * Mark the end of the wait period if dequeueing a
361          * waiting task:
362          */
363         if (se != cfs_rq->curr)
364                 update_stats_wait_end(cfs_rq, se);
365 }
366
367 /*
368  * We are picking a new current task - update its stats:
369  */
370 static inline void
371 update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
372 {
373         /*
374          * We are starting a new run period:
375          */
376         se->exec_start = rq_of(cfs_rq)->clock;
377 }
378
379 /*
380  * We are descheduling a task - update its stats:
381  */
382 static inline void
383 update_stats_curr_end(struct cfs_rq *cfs_rq, struct sched_entity *se)
384 {
385         se->exec_start = 0;
386 }
387
388 /**************************************************
389  * Scheduling class queueing methods:
390  */
391
392 static void
393 account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
394 {
395         update_load_add(&cfs_rq->load, se->load.weight);
396         cfs_rq->nr_running++;
397         se->on_rq = 1;
398 }
399
400 static void
401 account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
402 {
403         update_load_sub(&cfs_rq->load, se->load.weight);
404         cfs_rq->nr_running--;
405         se->on_rq = 0;
406 }
407
408 static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
409 {
410 #ifdef CONFIG_SCHEDSTATS
411         if (se->sleep_start) {
412                 u64 delta = rq_of(cfs_rq)->clock - se->sleep_start;
413
414                 if ((s64)delta < 0)
415                         delta = 0;
416
417                 if (unlikely(delta > se->sleep_max))
418                         se->sleep_max = delta;
419
420                 se->sleep_start = 0;
421                 se->sum_sleep_runtime += delta;
422         }
423         if (se->block_start) {
424                 u64 delta = rq_of(cfs_rq)->clock - se->block_start;
425
426                 if ((s64)delta < 0)
427                         delta = 0;
428
429                 if (unlikely(delta > se->block_max))
430                         se->block_max = delta;
431
432                 se->block_start = 0;
433                 se->sum_sleep_runtime += delta;
434
435                 /*
436                  * Blocking time is in units of nanosecs, so shift by 20 to
437                  * get a milliseconds-range estimation of the amount of
438                  * time that the task spent sleeping:
439                  */
440                 if (unlikely(prof_on == SLEEP_PROFILING)) {
441                         struct task_struct *tsk = task_of(se);
442
443                         profile_hits(SLEEP_PROFILING, (void *)get_wchan(tsk),
444                                      delta >> 20);
445                 }
446         }
447 #endif
448 }
449
450 static void check_spread(struct cfs_rq *cfs_rq, struct sched_entity *se)
451 {
452 #ifdef CONFIG_SCHED_DEBUG
453         s64 d = se->vruntime - cfs_rq->min_vruntime;
454
455         if (d < 0)
456                 d = -d;
457
458         if (d > 3*sysctl_sched_latency)
459                 schedstat_inc(cfs_rq, nr_spread_over);
460 #endif
461 }
462
463 static void
464 place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
465 {
466         u64 vruntime;
467
468         vruntime = cfs_rq->min_vruntime;
469
470         if (sched_feat(USE_TREE_AVG)) {
471                 struct sched_entity *last = __pick_last_entity(cfs_rq);
472                 if (last) {
473                         vruntime += last->vruntime;
474                         vruntime >>= 1;
475                 }
476         } else if (sched_feat(APPROX_AVG) && cfs_rq->nr_running)
477                 vruntime += __sched_vslice(cfs_rq->nr_running)/2;
478
479         if (initial && sched_feat(START_DEBIT))
480                 vruntime += __sched_vslice(cfs_rq->nr_running + 1);
481
482         if (!initial) {
483                 if (sched_feat(NEW_FAIR_SLEEPERS))
484                         vruntime -= sysctl_sched_latency;
485
486                 vruntime = max_t(s64, vruntime, se->vruntime);
487         }
488
489         se->vruntime = vruntime;
490
491 }
492
493 static void
494 enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int wakeup)
495 {
496         /*
497          * Update the fair clock.
498          */
499         update_curr(cfs_rq);
500
501         if (wakeup) {
502                 /* se->vruntime += cfs_rq->min_vruntime; */
503                 place_entity(cfs_rq, se, 0);
504                 enqueue_sleeper(cfs_rq, se);
505         }
506
507         update_stats_enqueue(cfs_rq, se);
508         check_spread(cfs_rq, se);
509         if (se != cfs_rq->curr)
510                 __enqueue_entity(cfs_rq, se);
511         account_entity_enqueue(cfs_rq, se);
512 }
513
514 static void
515 dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int sleep)
516 {
517         update_stats_dequeue(cfs_rq, se);
518         if (sleep) {
519 #ifdef CONFIG_SCHEDSTATS
520                 if (entity_is_task(se)) {
521                         struct task_struct *tsk = task_of(se);
522
523                         if (tsk->state & TASK_INTERRUPTIBLE)
524                                 se->sleep_start = rq_of(cfs_rq)->clock;
525                         if (tsk->state & TASK_UNINTERRUPTIBLE)
526                                 se->block_start = rq_of(cfs_rq)->clock;
527                 }
528 #endif
529         }
530
531         if (se != cfs_rq->curr)
532                 __dequeue_entity(cfs_rq, se);
533         account_entity_dequeue(cfs_rq, se);
534 }
535
536 /*
537  * Preempt the current task with a newly woken task if needed:
538  */
539 static void
540 check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
541 {
542         unsigned long ideal_runtime, delta_exec;
543
544         ideal_runtime = sched_slice(cfs_rq, curr);
545         delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
546         if (delta_exec > ideal_runtime)
547                 resched_task(rq_of(cfs_rq)->curr);
548 }
549
550 static void
551 set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
552 {
553         /* 'current' is not kept within the tree. */
554         if (se->on_rq) {
555                 /*
556                  * Any task has to be enqueued before it get to execute on
557                  * a CPU. So account for the time it spent waiting on the
558                  * runqueue.
559                  */
560                 update_stats_wait_end(cfs_rq, se);
561                 __dequeue_entity(cfs_rq, se);
562         }
563
564         update_stats_curr_start(cfs_rq, se);
565         cfs_rq->curr = se;
566 #ifdef CONFIG_SCHEDSTATS
567         /*
568          * Track our maximum slice length, if the CPU's load is at
569          * least twice that of our own weight (i.e. dont track it
570          * when there are only lesser-weight tasks around):
571          */
572         if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {
573                 se->slice_max = max(se->slice_max,
574                         se->sum_exec_runtime - se->prev_sum_exec_runtime);
575         }
576 #endif
577         se->prev_sum_exec_runtime = se->sum_exec_runtime;
578 }
579
580 static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
581 {
582         struct sched_entity *se = __pick_next_entity(cfs_rq);
583
584         set_next_entity(cfs_rq, se);
585
586         return se;
587 }
588
589 static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
590 {
591         /*
592          * If still on the runqueue then deactivate_task()
593          * was not called and update_curr() has to be done:
594          */
595         if (prev->on_rq)
596                 update_curr(cfs_rq);
597
598         update_stats_curr_end(cfs_rq, prev);
599
600         check_spread(cfs_rq, prev);
601         if (prev->on_rq) {
602                 update_stats_wait_start(cfs_rq, prev);
603                 /* Put 'current' back into the tree. */
604                 __enqueue_entity(cfs_rq, prev);
605         }
606         cfs_rq->curr = NULL;
607 }
608
609 static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
610 {
611         /*
612          * Update run-time statistics of the 'current'.
613          */
614         update_curr(cfs_rq);
615
616         if (cfs_rq->nr_running > 1)
617                 check_preempt_tick(cfs_rq, curr);
618 }
619
620 /**************************************************
621  * CFS operations on tasks:
622  */
623
624 #ifdef CONFIG_FAIR_GROUP_SCHED
625
626 /* Walk up scheduling entities hierarchy */
627 #define for_each_sched_entity(se) \
628                 for (; se; se = se->parent)
629
630 static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
631 {
632         return p->se.cfs_rq;
633 }
634
635 /* runqueue on which this entity is (to be) queued */
636 static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
637 {
638         return se->cfs_rq;
639 }
640
641 /* runqueue "owned" by this group */
642 static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
643 {
644         return grp->my_q;
645 }
646
647 /* Given a group's cfs_rq on one cpu, return its corresponding cfs_rq on
648  * another cpu ('this_cpu')
649  */
650 static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu)
651 {
652         return cfs_rq->tg->cfs_rq[this_cpu];
653 }
654
655 /* Iterate thr' all leaf cfs_rq's on a runqueue */
656 #define for_each_leaf_cfs_rq(rq, cfs_rq) \
657         list_for_each_entry(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
658
659 /* Do the two (enqueued) tasks belong to the same group ? */
660 static inline int is_same_group(struct task_struct *curr, struct task_struct *p)
661 {
662         if (curr->se.cfs_rq == p->se.cfs_rq)
663                 return 1;
664
665         return 0;
666 }
667
668 #else   /* CONFIG_FAIR_GROUP_SCHED */
669
670 #define for_each_sched_entity(se) \
671                 for (; se; se = NULL)
672
673 static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
674 {
675         return &task_rq(p)->cfs;
676 }
677
678 static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
679 {
680         struct task_struct *p = task_of(se);
681         struct rq *rq = task_rq(p);
682
683         return &rq->cfs;
684 }
685
686 /* runqueue "owned" by this group */
687 static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
688 {
689         return NULL;
690 }
691
692 static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu)
693 {
694         return &cpu_rq(this_cpu)->cfs;
695 }
696
697 #define for_each_leaf_cfs_rq(rq, cfs_rq) \
698                 for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)
699
700 static inline int is_same_group(struct task_struct *curr, struct task_struct *p)
701 {
702         return 1;
703 }
704
705 #endif  /* CONFIG_FAIR_GROUP_SCHED */
706
707 /*
708  * The enqueue_task method is called before nr_running is
709  * increased. Here we update the fair scheduling stats and
710  * then put the task into the rbtree:
711  */
712 static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup)
713 {
714         struct cfs_rq *cfs_rq;
715         struct sched_entity *se = &p->se;
716
717         for_each_sched_entity(se) {
718                 if (se->on_rq)
719                         break;
720                 cfs_rq = cfs_rq_of(se);
721                 enqueue_entity(cfs_rq, se, wakeup);
722         }
723 }
724
725 /*
726  * The dequeue_task method is called before nr_running is
727  * decreased. We remove the task from the rbtree and
728  * update the fair scheduling stats:
729  */
730 static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int sleep)
731 {
732         struct cfs_rq *cfs_rq;
733         struct sched_entity *se = &p->se;
734
735         for_each_sched_entity(se) {
736                 cfs_rq = cfs_rq_of(se);
737                 dequeue_entity(cfs_rq, se, sleep);
738                 /* Don't dequeue parent if it has other entities besides us */
739                 if (cfs_rq->load.weight)
740                         break;
741         }
742 }
743
744 /*
745  * sched_yield() support is very simple - we dequeue and enqueue.
746  *
747  * If compat_yield is turned on then we requeue to the end of the tree.
748  */
749 static void yield_task_fair(struct rq *rq)
750 {
751         struct cfs_rq *cfs_rq = task_cfs_rq(rq->curr);
752         struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
753         struct sched_entity *rightmost, *se = &rq->curr->se;
754         struct rb_node *parent;
755
756         /*
757          * Are we the only task in the tree?
758          */
759         if (unlikely(cfs_rq->nr_running == 1))
760                 return;
761
762         if (likely(!sysctl_sched_compat_yield)) {
763                 __update_rq_clock(rq);
764                 /*
765                  * Dequeue and enqueue the task to update its
766                  * position within the tree:
767                  */
768                 dequeue_entity(cfs_rq, se, 0);
769                 enqueue_entity(cfs_rq, se, 0);
770
771                 return;
772         }
773         /*
774          * Find the rightmost entry in the rbtree:
775          */
776         do {
777                 parent = *link;
778                 link = &parent->rb_right;
779         } while (*link);
780
781         rightmost = rb_entry(parent, struct sched_entity, run_node);
782         /*
783          * Already in the rightmost position?
784          */
785         if (unlikely(rightmost == se))
786                 return;
787
788         /*
789          * Minimally necessary key value to be last in the tree:
790          */
791         se->vruntime = rightmost->vruntime + 1;
792
793         if (cfs_rq->rb_leftmost == &se->run_node)
794                 cfs_rq->rb_leftmost = rb_next(&se->run_node);
795         /*
796          * Relink the task to the rightmost position:
797          */
798         rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
799         rb_link_node(&se->run_node, parent, link);
800         rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
801 }
802
803 /*
804  * Preempt the current task with a newly woken task if needed:
805  */
806 static void check_preempt_wakeup(struct rq *rq, struct task_struct *p)
807 {
808         struct task_struct *curr = rq->curr;
809         struct cfs_rq *cfs_rq = task_cfs_rq(curr);
810
811         if (unlikely(rt_prio(p->prio))) {
812                 update_rq_clock(rq);
813                 update_curr(cfs_rq);
814                 resched_task(curr);
815                 return;
816         }
817         if (is_same_group(curr, p)) {
818                 s64 delta = curr->se.vruntime - p->se.vruntime;
819
820                 if (delta > (s64)sysctl_sched_wakeup_granularity)
821                         resched_task(curr);
822         }
823 }
824
825 static struct task_struct *pick_next_task_fair(struct rq *rq)
826 {
827         struct cfs_rq *cfs_rq = &rq->cfs;
828         struct sched_entity *se;
829
830         if (unlikely(!cfs_rq->nr_running))
831                 return NULL;
832
833         do {
834                 se = pick_next_entity(cfs_rq);
835                 cfs_rq = group_cfs_rq(se);
836         } while (cfs_rq);
837
838         return task_of(se);
839 }
840
841 /*
842  * Account for a descheduled task:
843  */
844 static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
845 {
846         struct sched_entity *se = &prev->se;
847         struct cfs_rq *cfs_rq;
848
849         for_each_sched_entity(se) {
850                 cfs_rq = cfs_rq_of(se);
851                 put_prev_entity(cfs_rq, se);
852         }
853 }
854
855 /**************************************************
856  * Fair scheduling class load-balancing methods:
857  */
858
859 /*
860  * Load-balancing iterator. Note: while the runqueue stays locked
861  * during the whole iteration, the current task might be
862  * dequeued so the iterator has to be dequeue-safe. Here we
863  * achieve that by always pre-iterating before returning
864  * the current task:
865  */
866 static inline struct task_struct *
867 __load_balance_iterator(struct cfs_rq *cfs_rq, struct rb_node *curr)
868 {
869         struct task_struct *p;
870
871         if (!curr)
872                 return NULL;
873
874         p = rb_entry(curr, struct task_struct, se.run_node);
875         cfs_rq->rb_load_balance_curr = rb_next(curr);
876
877         return p;
878 }
879
880 static struct task_struct *load_balance_start_fair(void *arg)
881 {
882         struct cfs_rq *cfs_rq = arg;
883
884         return __load_balance_iterator(cfs_rq, first_fair(cfs_rq));
885 }
886
887 static struct task_struct *load_balance_next_fair(void *arg)
888 {
889         struct cfs_rq *cfs_rq = arg;
890
891         return __load_balance_iterator(cfs_rq, cfs_rq->rb_load_balance_curr);
892 }
893
894 #ifdef CONFIG_FAIR_GROUP_SCHED
895 static int cfs_rq_best_prio(struct cfs_rq *cfs_rq)
896 {
897         struct sched_entity *curr;
898         struct task_struct *p;
899
900         if (!cfs_rq->nr_running)
901                 return MAX_PRIO;
902
903         curr = cfs_rq->curr;
904         if (!curr)
905                 curr = __pick_next_entity(cfs_rq);
906
907         p = task_of(curr);
908
909         return p->prio;
910 }
911 #endif
912
913 static unsigned long
914 load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
915                   unsigned long max_nr_move, unsigned long max_load_move,
916                   struct sched_domain *sd, enum cpu_idle_type idle,
917                   int *all_pinned, int *this_best_prio)
918 {
919         struct cfs_rq *busy_cfs_rq;
920         unsigned long load_moved, total_nr_moved = 0, nr_moved;
921         long rem_load_move = max_load_move;
922         struct rq_iterator cfs_rq_iterator;
923
924         cfs_rq_iterator.start = load_balance_start_fair;
925         cfs_rq_iterator.next = load_balance_next_fair;
926
927         for_each_leaf_cfs_rq(busiest, busy_cfs_rq) {
928 #ifdef CONFIG_FAIR_GROUP_SCHED
929                 struct cfs_rq *this_cfs_rq;
930                 long imbalance;
931                 unsigned long maxload;
932
933                 this_cfs_rq = cpu_cfs_rq(busy_cfs_rq, this_cpu);
934
935                 imbalance = busy_cfs_rq->load.weight - this_cfs_rq->load.weight;
936                 /* Don't pull if this_cfs_rq has more load than busy_cfs_rq */
937                 if (imbalance <= 0)
938                         continue;
939
940                 /* Don't pull more than imbalance/2 */
941                 imbalance /= 2;
942                 maxload = min(rem_load_move, imbalance);
943
944                 *this_best_prio = cfs_rq_best_prio(this_cfs_rq);
945 #else
946 # define maxload rem_load_move
947 #endif
948                 /* pass busy_cfs_rq argument into
949                  * load_balance_[start|next]_fair iterators
950                  */
951                 cfs_rq_iterator.arg = busy_cfs_rq;
952                 nr_moved = balance_tasks(this_rq, this_cpu, busiest,
953                                 max_nr_move, maxload, sd, idle, all_pinned,
954                                 &load_moved, this_best_prio, &cfs_rq_iterator);
955
956                 total_nr_moved += nr_moved;
957                 max_nr_move -= nr_moved;
958                 rem_load_move -= load_moved;
959
960                 if (max_nr_move <= 0 || rem_load_move <= 0)
961                         break;
962         }
963
964         return max_load_move - rem_load_move;
965 }
966
967 /*
968  * scheduler tick hitting a task of our scheduling class:
969  */
970 static void task_tick_fair(struct rq *rq, struct task_struct *curr)
971 {
972         struct cfs_rq *cfs_rq;
973         struct sched_entity *se = &curr->se;
974
975         for_each_sched_entity(se) {
976                 cfs_rq = cfs_rq_of(se);
977                 entity_tick(cfs_rq, se);
978         }
979 }
980
981 #define swap(a,b) do { typeof(a) tmp = (a); (a) = (b); (b) = tmp; } while (0)
982
983 /*
984  * Share the fairness runtime between parent and child, thus the
985  * total amount of pressure for CPU stays equal - new tasks
986  * get a chance to run but frequent forkers are not allowed to
987  * monopolize the CPU. Note: the parent runqueue is locked,
988  * the child is not running yet.
989  */
990 static void task_new_fair(struct rq *rq, struct task_struct *p)
991 {
992         struct cfs_rq *cfs_rq = task_cfs_rq(p);
993         struct sched_entity *se = &p->se, *curr = cfs_rq->curr;
994
995         sched_info_queued(p);
996
997         update_curr(cfs_rq);
998         place_entity(cfs_rq, se, 1);
999
1000         if (sysctl_sched_child_runs_first &&
1001                         curr->vruntime < se->vruntime) {
1002                 /*
1003                  * Upon rescheduling, sched_class::put_prev_task() will place
1004                  * 'current' within the tree based on its new key value.
1005                  */
1006                 swap(curr->vruntime, se->vruntime);
1007         }
1008
1009         update_stats_enqueue(cfs_rq, se);
1010         check_spread(cfs_rq, se);
1011         check_spread(cfs_rq, curr);
1012         __enqueue_entity(cfs_rq, se);
1013         account_entity_enqueue(cfs_rq, se);
1014         resched_task(rq->curr);
1015 }
1016
1017 /* Account for a task changing its policy or group.
1018  *
1019  * This routine is mostly called to set cfs_rq->curr field when a task
1020  * migrates between groups/classes.
1021  */
1022 static void set_curr_task_fair(struct rq *rq)
1023 {
1024         struct sched_entity *se = &rq->curr->se;
1025
1026         for_each_sched_entity(se)
1027                 set_next_entity(cfs_rq_of(se), se);
1028 }
1029
1030 /*
1031  * All the scheduling class methods:
1032  */
1033 struct sched_class fair_sched_class __read_mostly = {
1034         .enqueue_task           = enqueue_task_fair,
1035         .dequeue_task           = dequeue_task_fair,
1036         .yield_task             = yield_task_fair,
1037
1038         .check_preempt_curr     = check_preempt_wakeup,
1039
1040         .pick_next_task         = pick_next_task_fair,
1041         .put_prev_task          = put_prev_task_fair,
1042
1043         .load_balance           = load_balance_fair,
1044
1045         .set_curr_task          = set_curr_task_fair,
1046         .task_tick              = task_tick_fair,
1047         .task_new               = task_new_fair,
1048 };
1049
1050 #ifdef CONFIG_SCHED_DEBUG
1051 static void print_cfs_stats(struct seq_file *m, int cpu)
1052 {
1053         struct cfs_rq *cfs_rq;
1054
1055 #ifdef CONFIG_FAIR_GROUP_SCHED
1056         print_cfs_rq(m, cpu, &cpu_rq(cpu)->cfs);
1057 #endif
1058         for_each_leaf_cfs_rq(cpu_rq(cpu), cfs_rq)
1059                 print_cfs_rq(m, cpu, cfs_rq);
1060 }
1061 #endif