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