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