1 /* 2 * Completely Fair Scheduling (CFS) Class (SCHED_NORMAL/SCHED_BATCH) 3 * 4 * Copyright (C) 2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com> 5 * 6 * Interactivity improvements by Mike Galbraith 7 * (C) 2007 Mike Galbraith <efault@gmx.de> 8 * 9 * Various enhancements by Dmitry Adamushko. 10 * (C) 2007 Dmitry Adamushko <dmitry.adamushko@gmail.com> 11 * 12 * Group scheduling enhancements by Srivatsa Vaddagiri 13 * Copyright IBM Corporation, 2007 14 * Author: Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com> 15 * 16 * Scaled math optimizations by Thomas Gleixner 17 * Copyright (C) 2007, Thomas Gleixner <tglx@linutronix.de> 18 * 19 * Adaptive scheduling granularity, math enhancements by Peter Zijlstra 20 * Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra <pzijlstr@redhat.com> 21 */ 22 23 #include <linux/latencytop.h> 24 #include <linux/sched.h> 25 #include <linux/cpumask.h> 26 #include <linux/slab.h> 27 #include <linux/profile.h> 28 #include <linux/interrupt.h> 29 #include <linux/mempolicy.h> 30 #include <linux/migrate.h> 31 #include <linux/task_work.h> 32 33 #include <trace/events/sched.h> 34 35 #include "sched.h" 36 37 /* 38 * Targeted preemption latency for CPU-bound tasks: 39 * (default: 6ms * (1 + ilog(ncpus)), units: nanoseconds) 40 * 41 * NOTE: this latency value is not the same as the concept of 42 * 'timeslice length' - timeslices in CFS are of variable length 43 * and have no persistent notion like in traditional, time-slice 44 * based scheduling concepts. 45 * 46 * (to see the precise effective timeslice length of your workload, 47 * run vmstat and monitor the context-switches (cs) field) 48 */ 49 unsigned int sysctl_sched_latency = 6000000ULL; 50 unsigned int normalized_sysctl_sched_latency = 6000000ULL; 51 52 /* 53 * The initial- and re-scaling of tunables is configurable 54 * (default SCHED_TUNABLESCALING_LOG = *(1+ilog(ncpus)) 55 * 56 * Options are: 57 * SCHED_TUNABLESCALING_NONE - unscaled, always *1 58 * SCHED_TUNABLESCALING_LOG - scaled logarithmical, *1+ilog(ncpus) 59 * SCHED_TUNABLESCALING_LINEAR - scaled linear, *ncpus 60 */ 61 enum sched_tunable_scaling sysctl_sched_tunable_scaling 62 = SCHED_TUNABLESCALING_LOG; 63 64 /* 65 * Minimal preemption granularity for CPU-bound tasks: 66 * (default: 0.75 msec * (1 + ilog(ncpus)), units: nanoseconds) 67 */ 68 unsigned int sysctl_sched_min_granularity = 750000ULL; 69 unsigned int normalized_sysctl_sched_min_granularity = 750000ULL; 70 71 /* 72 * is kept at sysctl_sched_latency / sysctl_sched_min_granularity 73 */ 74 static unsigned int sched_nr_latency = 8; 75 76 /* 77 * After fork, child runs first. If set to 0 (default) then 78 * parent will (try to) run first. 79 */ 80 unsigned int sysctl_sched_child_runs_first __read_mostly; 81 82 /* 83 * SCHED_OTHER wake-up granularity. 84 * (default: 1 msec * (1 + ilog(ncpus)), units: nanoseconds) 85 * 86 * This option delays the preemption effects of decoupled workloads 87 * and reduces their over-scheduling. Synchronous workloads will still 88 * have immediate wakeup/sleep latencies. 89 */ 90 unsigned int sysctl_sched_wakeup_granularity = 1000000UL; 91 unsigned int normalized_sysctl_sched_wakeup_granularity = 1000000UL; 92 93 const_debug unsigned int sysctl_sched_migration_cost = 500000UL; 94 95 /* 96 * The exponential sliding window over which load is averaged for shares 97 * distribution. 98 * (default: 10msec) 99 */ 100 unsigned int __read_mostly sysctl_sched_shares_window = 10000000UL; 101 102 #ifdef CONFIG_CFS_BANDWIDTH 103 /* 104 * Amount of runtime to allocate from global (tg) to local (per-cfs_rq) pool 105 * each time a cfs_rq requests quota. 106 * 107 * Note: in the case that the slice exceeds the runtime remaining (either due 108 * to consumption or the quota being specified to be smaller than the slice) 109 * we will always only issue the remaining available time. 110 * 111 * default: 5 msec, units: microseconds 112 */ 113 unsigned int sysctl_sched_cfs_bandwidth_slice = 5000UL; 114 #endif 115 116 static inline void update_load_add(struct load_weight *lw, unsigned long inc) 117 { 118 lw->weight += inc; 119 lw->inv_weight = 0; 120 } 121 122 static inline void update_load_sub(struct load_weight *lw, unsigned long dec) 123 { 124 lw->weight -= dec; 125 lw->inv_weight = 0; 126 } 127 128 static inline void update_load_set(struct load_weight *lw, unsigned long w) 129 { 130 lw->weight = w; 131 lw->inv_weight = 0; 132 } 133 134 /* 135 * Increase the granularity value when there are more CPUs, 136 * because with more CPUs the 'effective latency' as visible 137 * to users decreases. But the relationship is not linear, 138 * so pick a second-best guess by going with the log2 of the 139 * number of CPUs. 140 * 141 * This idea comes from the SD scheduler of Con Kolivas: 142 */ 143 static int get_update_sysctl_factor(void) 144 { 145 unsigned int cpus = min_t(int, num_online_cpus(), 8); 146 unsigned int factor; 147 148 switch (sysctl_sched_tunable_scaling) { 149 case SCHED_TUNABLESCALING_NONE: 150 factor = 1; 151 break; 152 case SCHED_TUNABLESCALING_LINEAR: 153 factor = cpus; 154 break; 155 case SCHED_TUNABLESCALING_LOG: 156 default: 157 factor = 1 + ilog2(cpus); 158 break; 159 } 160 161 return factor; 162 } 163 164 static void update_sysctl(void) 165 { 166 unsigned int factor = get_update_sysctl_factor(); 167 168 #define SET_SYSCTL(name) \ 169 (sysctl_##name = (factor) * normalized_sysctl_##name) 170 SET_SYSCTL(sched_min_granularity); 171 SET_SYSCTL(sched_latency); 172 SET_SYSCTL(sched_wakeup_granularity); 173 #undef SET_SYSCTL 174 } 175 176 void sched_init_granularity(void) 177 { 178 update_sysctl(); 179 } 180 181 #define WMULT_CONST (~0U) 182 #define WMULT_SHIFT 32 183 184 static void __update_inv_weight(struct load_weight *lw) 185 { 186 unsigned long w; 187 188 if (likely(lw->inv_weight)) 189 return; 190 191 w = scale_load_down(lw->weight); 192 193 if (BITS_PER_LONG > 32 && unlikely(w >= WMULT_CONST)) 194 lw->inv_weight = 1; 195 else if (unlikely(!w)) 196 lw->inv_weight = WMULT_CONST; 197 else 198 lw->inv_weight = WMULT_CONST / w; 199 } 200 201 /* 202 * delta_exec * weight / lw.weight 203 * OR 204 * (delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT 205 * 206 * Either weight := NICE_0_LOAD and lw \e prio_to_wmult[], in which case 207 * we're guaranteed shift stays positive because inv_weight is guaranteed to 208 * fit 32 bits, and NICE_0_LOAD gives another 10 bits; therefore shift >= 22. 209 * 210 * Or, weight =< lw.weight (because lw.weight is the runqueue weight), thus 211 * weight/lw.weight <= 1, and therefore our shift will also be positive. 212 */ 213 static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw) 214 { 215 u64 fact = scale_load_down(weight); 216 int shift = WMULT_SHIFT; 217 218 __update_inv_weight(lw); 219 220 if (unlikely(fact >> 32)) { 221 while (fact >> 32) { 222 fact >>= 1; 223 shift--; 224 } 225 } 226 227 /* hint to use a 32x32->64 mul */ 228 fact = (u64)(u32)fact * lw->inv_weight; 229 230 while (fact >> 32) { 231 fact >>= 1; 232 shift--; 233 } 234 235 return mul_u64_u32_shr(delta_exec, fact, shift); 236 } 237 238 239 const struct sched_class fair_sched_class; 240 241 /************************************************************** 242 * CFS operations on generic schedulable entities: 243 */ 244 245 #ifdef CONFIG_FAIR_GROUP_SCHED 246 247 /* cpu runqueue to which this cfs_rq is attached */ 248 static inline struct rq *rq_of(struct cfs_rq *cfs_rq) 249 { 250 return cfs_rq->rq; 251 } 252 253 /* An entity is a task if it doesn't "own" a runqueue */ 254 #define entity_is_task(se) (!se->my_q) 255 256 static inline struct task_struct *task_of(struct sched_entity *se) 257 { 258 #ifdef CONFIG_SCHED_DEBUG 259 WARN_ON_ONCE(!entity_is_task(se)); 260 #endif 261 return container_of(se, struct task_struct, se); 262 } 263 264 /* Walk up scheduling entities hierarchy */ 265 #define for_each_sched_entity(se) \ 266 for (; se; se = se->parent) 267 268 static inline struct cfs_rq *task_cfs_rq(struct task_struct *p) 269 { 270 return p->se.cfs_rq; 271 } 272 273 /* runqueue on which this entity is (to be) queued */ 274 static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se) 275 { 276 return se->cfs_rq; 277 } 278 279 /* runqueue "owned" by this group */ 280 static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp) 281 { 282 return grp->my_q; 283 } 284 285 static void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq, 286 int force_update); 287 288 static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq) 289 { 290 if (!cfs_rq->on_list) { 291 /* 292 * Ensure we either appear before our parent (if already 293 * enqueued) or force our parent to appear after us when it is 294 * enqueued. The fact that we always enqueue bottom-up 295 * reduces this to two cases. 296 */ 297 if (cfs_rq->tg->parent && 298 cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->on_list) { 299 list_add_rcu(&cfs_rq->leaf_cfs_rq_list, 300 &rq_of(cfs_rq)->leaf_cfs_rq_list); 301 } else { 302 list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list, 303 &rq_of(cfs_rq)->leaf_cfs_rq_list); 304 } 305 306 cfs_rq->on_list = 1; 307 /* We should have no load, but we need to update last_decay. */ 308 update_cfs_rq_blocked_load(cfs_rq, 0); 309 } 310 } 311 312 static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq) 313 { 314 if (cfs_rq->on_list) { 315 list_del_rcu(&cfs_rq->leaf_cfs_rq_list); 316 cfs_rq->on_list = 0; 317 } 318 } 319 320 /* Iterate thr' all leaf cfs_rq's on a runqueue */ 321 #define for_each_leaf_cfs_rq(rq, cfs_rq) \ 322 list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list) 323 324 /* Do the two (enqueued) entities belong to the same group ? */ 325 static inline int 326 is_same_group(struct sched_entity *se, struct sched_entity *pse) 327 { 328 if (se->cfs_rq == pse->cfs_rq) 329 return 1; 330 331 return 0; 332 } 333 334 static inline struct sched_entity *parent_entity(struct sched_entity *se) 335 { 336 return se->parent; 337 } 338 339 /* return depth at which a sched entity is present in the hierarchy */ 340 static inline int depth_se(struct sched_entity *se) 341 { 342 int depth = 0; 343 344 for_each_sched_entity(se) 345 depth++; 346 347 return depth; 348 } 349 350 static void 351 find_matching_se(struct sched_entity **se, struct sched_entity **pse) 352 { 353 int se_depth, pse_depth; 354 355 /* 356 * preemption test can be made between sibling entities who are in the 357 * same cfs_rq i.e who have a common parent. Walk up the hierarchy of 358 * both tasks until we find their ancestors who are siblings of common 359 * parent. 360 */ 361 362 /* First walk up until both entities are at same depth */ 363 se_depth = depth_se(*se); 364 pse_depth = depth_se(*pse); 365 366 while (se_depth > pse_depth) { 367 se_depth--; 368 *se = parent_entity(*se); 369 } 370 371 while (pse_depth > se_depth) { 372 pse_depth--; 373 *pse = parent_entity(*pse); 374 } 375 376 while (!is_same_group(*se, *pse)) { 377 *se = parent_entity(*se); 378 *pse = parent_entity(*pse); 379 } 380 } 381 382 #else /* !CONFIG_FAIR_GROUP_SCHED */ 383 384 static inline struct task_struct *task_of(struct sched_entity *se) 385 { 386 return container_of(se, struct task_struct, se); 387 } 388 389 static inline struct rq *rq_of(struct cfs_rq *cfs_rq) 390 { 391 return container_of(cfs_rq, struct rq, cfs); 392 } 393 394 #define entity_is_task(se) 1 395 396 #define for_each_sched_entity(se) \ 397 for (; se; se = NULL) 398 399 static inline struct cfs_rq *task_cfs_rq(struct task_struct *p) 400 { 401 return &task_rq(p)->cfs; 402 } 403 404 static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se) 405 { 406 struct task_struct *p = task_of(se); 407 struct rq *rq = task_rq(p); 408 409 return &rq->cfs; 410 } 411 412 /* runqueue "owned" by this group */ 413 static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp) 414 { 415 return NULL; 416 } 417 418 static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq) 419 { 420 } 421 422 static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq) 423 { 424 } 425 426 #define for_each_leaf_cfs_rq(rq, cfs_rq) \ 427 for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL) 428 429 static inline int 430 is_same_group(struct sched_entity *se, struct sched_entity *pse) 431 { 432 return 1; 433 } 434 435 static inline struct sched_entity *parent_entity(struct sched_entity *se) 436 { 437 return NULL; 438 } 439 440 static inline void 441 find_matching_se(struct sched_entity **se, struct sched_entity **pse) 442 { 443 } 444 445 #endif /* CONFIG_FAIR_GROUP_SCHED */ 446 447 static __always_inline 448 void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec); 449 450 /************************************************************** 451 * Scheduling class tree data structure manipulation methods: 452 */ 453 454 static inline u64 max_vruntime(u64 max_vruntime, u64 vruntime) 455 { 456 s64 delta = (s64)(vruntime - max_vruntime); 457 if (delta > 0) 458 max_vruntime = vruntime; 459 460 return max_vruntime; 461 } 462 463 static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime) 464 { 465 s64 delta = (s64)(vruntime - min_vruntime); 466 if (delta < 0) 467 min_vruntime = vruntime; 468 469 return min_vruntime; 470 } 471 472 static inline int entity_before(struct sched_entity *a, 473 struct sched_entity *b) 474 { 475 return (s64)(a->vruntime - b->vruntime) < 0; 476 } 477 478 static void update_min_vruntime(struct cfs_rq *cfs_rq) 479 { 480 u64 vruntime = cfs_rq->min_vruntime; 481 482 if (cfs_rq->curr) 483 vruntime = cfs_rq->curr->vruntime; 484 485 if (cfs_rq->rb_leftmost) { 486 struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost, 487 struct sched_entity, 488 run_node); 489 490 if (!cfs_rq->curr) 491 vruntime = se->vruntime; 492 else 493 vruntime = min_vruntime(vruntime, se->vruntime); 494 } 495 496 /* ensure we never gain time by being placed backwards. */ 497 cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime); 498 #ifndef CONFIG_64BIT 499 smp_wmb(); 500 cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime; 501 #endif 502 } 503 504 /* 505 * Enqueue an entity into the rb-tree: 506 */ 507 static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) 508 { 509 struct rb_node **link = &cfs_rq->tasks_timeline.rb_node; 510 struct rb_node *parent = NULL; 511 struct sched_entity *entry; 512 int leftmost = 1; 513 514 /* 515 * Find the right place in the rbtree: 516 */ 517 while (*link) { 518 parent = *link; 519 entry = rb_entry(parent, struct sched_entity, run_node); 520 /* 521 * We dont care about collisions. Nodes with 522 * the same key stay together. 523 */ 524 if (entity_before(se, entry)) { 525 link = &parent->rb_left; 526 } else { 527 link = &parent->rb_right; 528 leftmost = 0; 529 } 530 } 531 532 /* 533 * Maintain a cache of leftmost tree entries (it is frequently 534 * used): 535 */ 536 if (leftmost) 537 cfs_rq->rb_leftmost = &se->run_node; 538 539 rb_link_node(&se->run_node, parent, link); 540 rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline); 541 } 542 543 static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) 544 { 545 if (cfs_rq->rb_leftmost == &se->run_node) { 546 struct rb_node *next_node; 547 548 next_node = rb_next(&se->run_node); 549 cfs_rq->rb_leftmost = next_node; 550 } 551 552 rb_erase(&se->run_node, &cfs_rq->tasks_timeline); 553 } 554 555 struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq) 556 { 557 struct rb_node *left = cfs_rq->rb_leftmost; 558 559 if (!left) 560 return NULL; 561 562 return rb_entry(left, struct sched_entity, run_node); 563 } 564 565 static struct sched_entity *__pick_next_entity(struct sched_entity *se) 566 { 567 struct rb_node *next = rb_next(&se->run_node); 568 569 if (!next) 570 return NULL; 571 572 return rb_entry(next, struct sched_entity, run_node); 573 } 574 575 #ifdef CONFIG_SCHED_DEBUG 576 struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq) 577 { 578 struct rb_node *last = rb_last(&cfs_rq->tasks_timeline); 579 580 if (!last) 581 return NULL; 582 583 return rb_entry(last, struct sched_entity, run_node); 584 } 585 586 /************************************************************** 587 * Scheduling class statistics methods: 588 */ 589 590 int sched_proc_update_handler(struct ctl_table *table, int write, 591 void __user *buffer, size_t *lenp, 592 loff_t *ppos) 593 { 594 int ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos); 595 int factor = get_update_sysctl_factor(); 596 597 if (ret || !write) 598 return ret; 599 600 sched_nr_latency = DIV_ROUND_UP(sysctl_sched_latency, 601 sysctl_sched_min_granularity); 602 603 #define WRT_SYSCTL(name) \ 604 (normalized_sysctl_##name = sysctl_##name / (factor)) 605 WRT_SYSCTL(sched_min_granularity); 606 WRT_SYSCTL(sched_latency); 607 WRT_SYSCTL(sched_wakeup_granularity); 608 #undef WRT_SYSCTL 609 610 return 0; 611 } 612 #endif 613 614 /* 615 * delta /= w 616 */ 617 static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se) 618 { 619 if (unlikely(se->load.weight != NICE_0_LOAD)) 620 delta = __calc_delta(delta, NICE_0_LOAD, &se->load); 621 622 return delta; 623 } 624 625 /* 626 * The idea is to set a period in which each task runs once. 627 * 628 * When there are too many tasks (sched_nr_latency) we have to stretch 629 * this period because otherwise the slices get too small. 630 * 631 * p = (nr <= nl) ? l : l*nr/nl 632 */ 633 static u64 __sched_period(unsigned long nr_running) 634 { 635 u64 period = sysctl_sched_latency; 636 unsigned long nr_latency = sched_nr_latency; 637 638 if (unlikely(nr_running > nr_latency)) { 639 period = sysctl_sched_min_granularity; 640 period *= nr_running; 641 } 642 643 return period; 644 } 645 646 /* 647 * We calculate the wall-time slice from the period by taking a part 648 * proportional to the weight. 649 * 650 * s = p*P[w/rw] 651 */ 652 static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se) 653 { 654 u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq); 655 656 for_each_sched_entity(se) { 657 struct load_weight *load; 658 struct load_weight lw; 659 660 cfs_rq = cfs_rq_of(se); 661 load = &cfs_rq->load; 662 663 if (unlikely(!se->on_rq)) { 664 lw = cfs_rq->load; 665 666 update_load_add(&lw, se->load.weight); 667 load = &lw; 668 } 669 slice = __calc_delta(slice, se->load.weight, load); 670 } 671 return slice; 672 } 673 674 /* 675 * We calculate the vruntime slice of a to-be-inserted task. 676 * 677 * vs = s/w 678 */ 679 static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se) 680 { 681 return calc_delta_fair(sched_slice(cfs_rq, se), se); 682 } 683 684 #ifdef CONFIG_SMP 685 static unsigned long task_h_load(struct task_struct *p); 686 687 static inline void __update_task_entity_contrib(struct sched_entity *se); 688 689 /* Give new task start runnable values to heavy its load in infant time */ 690 void init_task_runnable_average(struct task_struct *p) 691 { 692 u32 slice; 693 694 p->se.avg.decay_count = 0; 695 slice = sched_slice(task_cfs_rq(p), &p->se) >> 10; 696 p->se.avg.runnable_avg_sum = slice; 697 p->se.avg.runnable_avg_period = slice; 698 __update_task_entity_contrib(&p->se); 699 } 700 #else 701 void init_task_runnable_average(struct task_struct *p) 702 { 703 } 704 #endif 705 706 /* 707 * Update the current task's runtime statistics. 708 */ 709 static void update_curr(struct cfs_rq *cfs_rq) 710 { 711 struct sched_entity *curr = cfs_rq->curr; 712 u64 now = rq_clock_task(rq_of(cfs_rq)); 713 u64 delta_exec; 714 715 if (unlikely(!curr)) 716 return; 717 718 delta_exec = now - curr->exec_start; 719 if (unlikely((s64)delta_exec <= 0)) 720 return; 721 722 curr->exec_start = now; 723 724 schedstat_set(curr->statistics.exec_max, 725 max(delta_exec, curr->statistics.exec_max)); 726 727 curr->sum_exec_runtime += delta_exec; 728 schedstat_add(cfs_rq, exec_clock, delta_exec); 729 730 curr->vruntime += calc_delta_fair(delta_exec, curr); 731 update_min_vruntime(cfs_rq); 732 733 if (entity_is_task(curr)) { 734 struct task_struct *curtask = task_of(curr); 735 736 trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime); 737 cpuacct_charge(curtask, delta_exec); 738 account_group_exec_runtime(curtask, delta_exec); 739 } 740 741 account_cfs_rq_runtime(cfs_rq, delta_exec); 742 } 743 744 static inline void 745 update_stats_wait_start(struct cfs_rq *cfs_rq, struct sched_entity *se) 746 { 747 schedstat_set(se->statistics.wait_start, rq_clock(rq_of(cfs_rq))); 748 } 749 750 /* 751 * Task is being enqueued - update stats: 752 */ 753 static void update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se) 754 { 755 /* 756 * Are we enqueueing a waiting task? (for current tasks 757 * a dequeue/enqueue event is a NOP) 758 */ 759 if (se != cfs_rq->curr) 760 update_stats_wait_start(cfs_rq, se); 761 } 762 763 static void 764 update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se) 765 { 766 schedstat_set(se->statistics.wait_max, max(se->statistics.wait_max, 767 rq_clock(rq_of(cfs_rq)) - se->statistics.wait_start)); 768 schedstat_set(se->statistics.wait_count, se->statistics.wait_count + 1); 769 schedstat_set(se->statistics.wait_sum, se->statistics.wait_sum + 770 rq_clock(rq_of(cfs_rq)) - se->statistics.wait_start); 771 #ifdef CONFIG_SCHEDSTATS 772 if (entity_is_task(se)) { 773 trace_sched_stat_wait(task_of(se), 774 rq_clock(rq_of(cfs_rq)) - se->statistics.wait_start); 775 } 776 #endif 777 schedstat_set(se->statistics.wait_start, 0); 778 } 779 780 static inline void 781 update_stats_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se) 782 { 783 /* 784 * Mark the end of the wait period if dequeueing a 785 * waiting task: 786 */ 787 if (se != cfs_rq->curr) 788 update_stats_wait_end(cfs_rq, se); 789 } 790 791 /* 792 * We are picking a new current task - update its stats: 793 */ 794 static inline void 795 update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se) 796 { 797 /* 798 * We are starting a new run period: 799 */ 800 se->exec_start = rq_clock_task(rq_of(cfs_rq)); 801 } 802 803 /************************************************** 804 * Scheduling class queueing methods: 805 */ 806 807 #ifdef CONFIG_NUMA_BALANCING 808 /* 809 * Approximate time to scan a full NUMA task in ms. The task scan period is 810 * calculated based on the tasks virtual memory size and 811 * numa_balancing_scan_size. 812 */ 813 unsigned int sysctl_numa_balancing_scan_period_min = 1000; 814 unsigned int sysctl_numa_balancing_scan_period_max = 60000; 815 816 /* Portion of address space to scan in MB */ 817 unsigned int sysctl_numa_balancing_scan_size = 256; 818 819 /* Scan @scan_size MB every @scan_period after an initial @scan_delay in ms */ 820 unsigned int sysctl_numa_balancing_scan_delay = 1000; 821 822 /* 823 * After skipping a page migration on a shared page, skip N more numa page 824 * migrations unconditionally. This reduces the number of NUMA migrations 825 * in shared memory workloads, and has the effect of pulling tasks towards 826 * where their memory lives, over pulling the memory towards the task. 827 */ 828 unsigned int sysctl_numa_balancing_migrate_deferred = 16; 829 830 static unsigned int task_nr_scan_windows(struct task_struct *p) 831 { 832 unsigned long rss = 0; 833 unsigned long nr_scan_pages; 834 835 /* 836 * Calculations based on RSS as non-present and empty pages are skipped 837 * by the PTE scanner and NUMA hinting faults should be trapped based 838 * on resident pages 839 */ 840 nr_scan_pages = sysctl_numa_balancing_scan_size << (20 - PAGE_SHIFT); 841 rss = get_mm_rss(p->mm); 842 if (!rss) 843 rss = nr_scan_pages; 844 845 rss = round_up(rss, nr_scan_pages); 846 return rss / nr_scan_pages; 847 } 848 849 /* For sanitys sake, never scan more PTEs than MAX_SCAN_WINDOW MB/sec. */ 850 #define MAX_SCAN_WINDOW 2560 851 852 static unsigned int task_scan_min(struct task_struct *p) 853 { 854 unsigned int scan, floor; 855 unsigned int windows = 1; 856 857 if (sysctl_numa_balancing_scan_size < MAX_SCAN_WINDOW) 858 windows = MAX_SCAN_WINDOW / sysctl_numa_balancing_scan_size; 859 floor = 1000 / windows; 860 861 scan = sysctl_numa_balancing_scan_period_min / task_nr_scan_windows(p); 862 return max_t(unsigned int, floor, scan); 863 } 864 865 static unsigned int task_scan_max(struct task_struct *p) 866 { 867 unsigned int smin = task_scan_min(p); 868 unsigned int smax; 869 870 /* Watch for min being lower than max due to floor calculations */ 871 smax = sysctl_numa_balancing_scan_period_max / task_nr_scan_windows(p); 872 return max(smin, smax); 873 } 874 875 static void account_numa_enqueue(struct rq *rq, struct task_struct *p) 876 { 877 rq->nr_numa_running += (p->numa_preferred_nid != -1); 878 rq->nr_preferred_running += (p->numa_preferred_nid == task_node(p)); 879 } 880 881 static void account_numa_dequeue(struct rq *rq, struct task_struct *p) 882 { 883 rq->nr_numa_running -= (p->numa_preferred_nid != -1); 884 rq->nr_preferred_running -= (p->numa_preferred_nid == task_node(p)); 885 } 886 887 struct numa_group { 888 atomic_t refcount; 889 890 spinlock_t lock; /* nr_tasks, tasks */ 891 int nr_tasks; 892 pid_t gid; 893 struct list_head task_list; 894 895 struct rcu_head rcu; 896 unsigned long total_faults; 897 unsigned long faults[0]; 898 }; 899 900 pid_t task_numa_group_id(struct task_struct *p) 901 { 902 return p->numa_group ? p->numa_group->gid : 0; 903 } 904 905 static inline int task_faults_idx(int nid, int priv) 906 { 907 return 2 * nid + priv; 908 } 909 910 static inline unsigned long task_faults(struct task_struct *p, int nid) 911 { 912 if (!p->numa_faults) 913 return 0; 914 915 return p->numa_faults[task_faults_idx(nid, 0)] + 916 p->numa_faults[task_faults_idx(nid, 1)]; 917 } 918 919 static inline unsigned long group_faults(struct task_struct *p, int nid) 920 { 921 if (!p->numa_group) 922 return 0; 923 924 return p->numa_group->faults[task_faults_idx(nid, 0)] + 925 p->numa_group->faults[task_faults_idx(nid, 1)]; 926 } 927 928 /* 929 * These return the fraction of accesses done by a particular task, or 930 * task group, on a particular numa node. The group weight is given a 931 * larger multiplier, in order to group tasks together that are almost 932 * evenly spread out between numa nodes. 933 */ 934 static inline unsigned long task_weight(struct task_struct *p, int nid) 935 { 936 unsigned long total_faults; 937 938 if (!p->numa_faults) 939 return 0; 940 941 total_faults = p->total_numa_faults; 942 943 if (!total_faults) 944 return 0; 945 946 return 1000 * task_faults(p, nid) / total_faults; 947 } 948 949 static inline unsigned long group_weight(struct task_struct *p, int nid) 950 { 951 if (!p->numa_group || !p->numa_group->total_faults) 952 return 0; 953 954 return 1000 * group_faults(p, nid) / p->numa_group->total_faults; 955 } 956 957 static unsigned long weighted_cpuload(const int cpu); 958 static unsigned long source_load(int cpu, int type); 959 static unsigned long target_load(int cpu, int type); 960 static unsigned long power_of(int cpu); 961 static long effective_load(struct task_group *tg, int cpu, long wl, long wg); 962 963 /* Cached statistics for all CPUs within a node */ 964 struct numa_stats { 965 unsigned long nr_running; 966 unsigned long load; 967 968 /* Total compute capacity of CPUs on a node */ 969 unsigned long power; 970 971 /* Approximate capacity in terms of runnable tasks on a node */ 972 unsigned long capacity; 973 int has_capacity; 974 }; 975 976 /* 977 * XXX borrowed from update_sg_lb_stats 978 */ 979 static void update_numa_stats(struct numa_stats *ns, int nid) 980 { 981 int cpu, cpus = 0; 982 983 memset(ns, 0, sizeof(*ns)); 984 for_each_cpu(cpu, cpumask_of_node(nid)) { 985 struct rq *rq = cpu_rq(cpu); 986 987 ns->nr_running += rq->nr_running; 988 ns->load += weighted_cpuload(cpu); 989 ns->power += power_of(cpu); 990 991 cpus++; 992 } 993 994 /* 995 * If we raced with hotplug and there are no CPUs left in our mask 996 * the @ns structure is NULL'ed and task_numa_compare() will 997 * not find this node attractive. 998 * 999 * We'll either bail at !has_capacity, or we'll detect a huge imbalance 1000 * and bail there. 1001 */ 1002 if (!cpus) 1003 return; 1004 1005 ns->load = (ns->load * SCHED_POWER_SCALE) / ns->power; 1006 ns->capacity = DIV_ROUND_CLOSEST(ns->power, SCHED_POWER_SCALE); 1007 ns->has_capacity = (ns->nr_running < ns->capacity); 1008 } 1009 1010 struct task_numa_env { 1011 struct task_struct *p; 1012 1013 int src_cpu, src_nid; 1014 int dst_cpu, dst_nid; 1015 1016 struct numa_stats src_stats, dst_stats; 1017 1018 int imbalance_pct; 1019 1020 struct task_struct *best_task; 1021 long best_imp; 1022 int best_cpu; 1023 }; 1024 1025 static void task_numa_assign(struct task_numa_env *env, 1026 struct task_struct *p, long imp) 1027 { 1028 if (env->best_task) 1029 put_task_struct(env->best_task); 1030 if (p) 1031 get_task_struct(p); 1032 1033 env->best_task = p; 1034 env->best_imp = imp; 1035 env->best_cpu = env->dst_cpu; 1036 } 1037 1038 /* 1039 * This checks if the overall compute and NUMA accesses of the system would 1040 * be improved if the source tasks was migrated to the target dst_cpu taking 1041 * into account that it might be best if task running on the dst_cpu should 1042 * be exchanged with the source task 1043 */ 1044 static void task_numa_compare(struct task_numa_env *env, 1045 long taskimp, long groupimp) 1046 { 1047 struct rq *src_rq = cpu_rq(env->src_cpu); 1048 struct rq *dst_rq = cpu_rq(env->dst_cpu); 1049 struct task_struct *cur; 1050 long dst_load, src_load; 1051 long load; 1052 long imp = (groupimp > 0) ? groupimp : taskimp; 1053 1054 rcu_read_lock(); 1055 cur = ACCESS_ONCE(dst_rq->curr); 1056 if (cur->pid == 0) /* idle */ 1057 cur = NULL; 1058 1059 /* 1060 * "imp" is the fault differential for the source task between the 1061 * source and destination node. Calculate the total differential for 1062 * the source task and potential destination task. The more negative 1063 * the value is, the more rmeote accesses that would be expected to 1064 * be incurred if the tasks were swapped. 1065 */ 1066 if (cur) { 1067 /* Skip this swap candidate if cannot move to the source cpu */ 1068 if (!cpumask_test_cpu(env->src_cpu, tsk_cpus_allowed(cur))) 1069 goto unlock; 1070 1071 /* 1072 * If dst and source tasks are in the same NUMA group, or not 1073 * in any group then look only at task weights. 1074 */ 1075 if (cur->numa_group == env->p->numa_group) { 1076 imp = taskimp + task_weight(cur, env->src_nid) - 1077 task_weight(cur, env->dst_nid); 1078 /* 1079 * Add some hysteresis to prevent swapping the 1080 * tasks within a group over tiny differences. 1081 */ 1082 if (cur->numa_group) 1083 imp -= imp/16; 1084 } else { 1085 /* 1086 * Compare the group weights. If a task is all by 1087 * itself (not part of a group), use the task weight 1088 * instead. 1089 */ 1090 if (env->p->numa_group) 1091 imp = groupimp; 1092 else 1093 imp = taskimp; 1094 1095 if (cur->numa_group) 1096 imp += group_weight(cur, env->src_nid) - 1097 group_weight(cur, env->dst_nid); 1098 else 1099 imp += task_weight(cur, env->src_nid) - 1100 task_weight(cur, env->dst_nid); 1101 } 1102 } 1103 1104 if (imp < env->best_imp) 1105 goto unlock; 1106 1107 if (!cur) { 1108 /* Is there capacity at our destination? */ 1109 if (env->src_stats.has_capacity && 1110 !env->dst_stats.has_capacity) 1111 goto unlock; 1112 1113 goto balance; 1114 } 1115 1116 /* Balance doesn't matter much if we're running a task per cpu */ 1117 if (src_rq->nr_running == 1 && dst_rq->nr_running == 1) 1118 goto assign; 1119 1120 /* 1121 * In the overloaded case, try and keep the load balanced. 1122 */ 1123 balance: 1124 dst_load = env->dst_stats.load; 1125 src_load = env->src_stats.load; 1126 1127 /* XXX missing power terms */ 1128 load = task_h_load(env->p); 1129 dst_load += load; 1130 src_load -= load; 1131 1132 if (cur) { 1133 load = task_h_load(cur); 1134 dst_load -= load; 1135 src_load += load; 1136 } 1137 1138 /* make src_load the smaller */ 1139 if (dst_load < src_load) 1140 swap(dst_load, src_load); 1141 1142 if (src_load * env->imbalance_pct < dst_load * 100) 1143 goto unlock; 1144 1145 assign: 1146 task_numa_assign(env, cur, imp); 1147 unlock: 1148 rcu_read_unlock(); 1149 } 1150 1151 static void task_numa_find_cpu(struct task_numa_env *env, 1152 long taskimp, long groupimp) 1153 { 1154 int cpu; 1155 1156 for_each_cpu(cpu, cpumask_of_node(env->dst_nid)) { 1157 /* Skip this CPU if the source task cannot migrate */ 1158 if (!cpumask_test_cpu(cpu, tsk_cpus_allowed(env->p))) 1159 continue; 1160 1161 env->dst_cpu = cpu; 1162 task_numa_compare(env, taskimp, groupimp); 1163 } 1164 } 1165 1166 static int task_numa_migrate(struct task_struct *p) 1167 { 1168 struct task_numa_env env = { 1169 .p = p, 1170 1171 .src_cpu = task_cpu(p), 1172 .src_nid = task_node(p), 1173 1174 .imbalance_pct = 112, 1175 1176 .best_task = NULL, 1177 .best_imp = 0, 1178 .best_cpu = -1 1179 }; 1180 struct sched_domain *sd; 1181 unsigned long taskweight, groupweight; 1182 int nid, ret; 1183 long taskimp, groupimp; 1184 1185 /* 1186 * Pick the lowest SD_NUMA domain, as that would have the smallest 1187 * imbalance and would be the first to start moving tasks about. 1188 * 1189 * And we want to avoid any moving of tasks about, as that would create 1190 * random movement of tasks -- counter the numa conditions we're trying 1191 * to satisfy here. 1192 */ 1193 rcu_read_lock(); 1194 sd = rcu_dereference(per_cpu(sd_numa, env.src_cpu)); 1195 if (sd) 1196 env.imbalance_pct = 100 + (sd->imbalance_pct - 100) / 2; 1197 rcu_read_unlock(); 1198 1199 /* 1200 * Cpusets can break the scheduler domain tree into smaller 1201 * balance domains, some of which do not cross NUMA boundaries. 1202 * Tasks that are "trapped" in such domains cannot be migrated 1203 * elsewhere, so there is no point in (re)trying. 1204 */ 1205 if (unlikely(!sd)) { 1206 p->numa_preferred_nid = task_node(p); 1207 return -EINVAL; 1208 } 1209 1210 taskweight = task_weight(p, env.src_nid); 1211 groupweight = group_weight(p, env.src_nid); 1212 update_numa_stats(&env.src_stats, env.src_nid); 1213 env.dst_nid = p->numa_preferred_nid; 1214 taskimp = task_weight(p, env.dst_nid) - taskweight; 1215 groupimp = group_weight(p, env.dst_nid) - groupweight; 1216 update_numa_stats(&env.dst_stats, env.dst_nid); 1217 1218 /* If the preferred nid has capacity, try to use it. */ 1219 if (env.dst_stats.has_capacity) 1220 task_numa_find_cpu(&env, taskimp, groupimp); 1221 1222 /* No space available on the preferred nid. Look elsewhere. */ 1223 if (env.best_cpu == -1) { 1224 for_each_online_node(nid) { 1225 if (nid == env.src_nid || nid == p->numa_preferred_nid) 1226 continue; 1227 1228 /* Only consider nodes where both task and groups benefit */ 1229 taskimp = task_weight(p, nid) - taskweight; 1230 groupimp = group_weight(p, nid) - groupweight; 1231 if (taskimp < 0 && groupimp < 0) 1232 continue; 1233 1234 env.dst_nid = nid; 1235 update_numa_stats(&env.dst_stats, env.dst_nid); 1236 task_numa_find_cpu(&env, taskimp, groupimp); 1237 } 1238 } 1239 1240 /* No better CPU than the current one was found. */ 1241 if (env.best_cpu == -1) 1242 return -EAGAIN; 1243 1244 sched_setnuma(p, env.dst_nid); 1245 1246 /* 1247 * Reset the scan period if the task is being rescheduled on an 1248 * alternative node to recheck if the tasks is now properly placed. 1249 */ 1250 p->numa_scan_period = task_scan_min(p); 1251 1252 if (env.best_task == NULL) { 1253 ret = migrate_task_to(p, env.best_cpu); 1254 if (ret != 0) 1255 trace_sched_stick_numa(p, env.src_cpu, env.best_cpu); 1256 return ret; 1257 } 1258 1259 ret = migrate_swap(p, env.best_task); 1260 if (ret != 0) 1261 trace_sched_stick_numa(p, env.src_cpu, task_cpu(env.best_task)); 1262 put_task_struct(env.best_task); 1263 return ret; 1264 } 1265 1266 /* Attempt to migrate a task to a CPU on the preferred node. */ 1267 static void numa_migrate_preferred(struct task_struct *p) 1268 { 1269 /* This task has no NUMA fault statistics yet */ 1270 if (unlikely(p->numa_preferred_nid == -1 || !p->numa_faults)) 1271 return; 1272 1273 /* Periodically retry migrating the task to the preferred node */ 1274 p->numa_migrate_retry = jiffies + HZ; 1275 1276 /* Success if task is already running on preferred CPU */ 1277 if (task_node(p) == p->numa_preferred_nid) 1278 return; 1279 1280 /* Otherwise, try migrate to a CPU on the preferred node */ 1281 task_numa_migrate(p); 1282 } 1283 1284 /* 1285 * When adapting the scan rate, the period is divided into NUMA_PERIOD_SLOTS 1286 * increments. The more local the fault statistics are, the higher the scan 1287 * period will be for the next scan window. If local/remote ratio is below 1288 * NUMA_PERIOD_THRESHOLD (where range of ratio is 1..NUMA_PERIOD_SLOTS) the 1289 * scan period will decrease 1290 */ 1291 #define NUMA_PERIOD_SLOTS 10 1292 #define NUMA_PERIOD_THRESHOLD 3 1293 1294 /* 1295 * Increase the scan period (slow down scanning) if the majority of 1296 * our memory is already on our local node, or if the majority of 1297 * the page accesses are shared with other processes. 1298 * Otherwise, decrease the scan period. 1299 */ 1300 static void update_task_scan_period(struct task_struct *p, 1301 unsigned long shared, unsigned long private) 1302 { 1303 unsigned int period_slot; 1304 int ratio; 1305 int diff; 1306 1307 unsigned long remote = p->numa_faults_locality[0]; 1308 unsigned long local = p->numa_faults_locality[1]; 1309 1310 /* 1311 * If there were no record hinting faults then either the task is 1312 * completely idle or all activity is areas that are not of interest 1313 * to automatic numa balancing. Scan slower 1314 */ 1315 if (local + shared == 0) { 1316 p->numa_scan_period = min(p->numa_scan_period_max, 1317 p->numa_scan_period << 1); 1318 1319 p->mm->numa_next_scan = jiffies + 1320 msecs_to_jiffies(p->numa_scan_period); 1321 1322 return; 1323 } 1324 1325 /* 1326 * Prepare to scale scan period relative to the current period. 1327 * == NUMA_PERIOD_THRESHOLD scan period stays the same 1328 * < NUMA_PERIOD_THRESHOLD scan period decreases (scan faster) 1329 * >= NUMA_PERIOD_THRESHOLD scan period increases (scan slower) 1330 */ 1331 period_slot = DIV_ROUND_UP(p->numa_scan_period, NUMA_PERIOD_SLOTS); 1332 ratio = (local * NUMA_PERIOD_SLOTS) / (local + remote); 1333 if (ratio >= NUMA_PERIOD_THRESHOLD) { 1334 int slot = ratio - NUMA_PERIOD_THRESHOLD; 1335 if (!slot) 1336 slot = 1; 1337 diff = slot * period_slot; 1338 } else { 1339 diff = -(NUMA_PERIOD_THRESHOLD - ratio) * period_slot; 1340 1341 /* 1342 * Scale scan rate increases based on sharing. There is an 1343 * inverse relationship between the degree of sharing and 1344 * the adjustment made to the scanning period. Broadly 1345 * speaking the intent is that there is little point 1346 * scanning faster if shared accesses dominate as it may 1347 * simply bounce migrations uselessly 1348 */ 1349 ratio = DIV_ROUND_UP(private * NUMA_PERIOD_SLOTS, (private + shared)); 1350 diff = (diff * ratio) / NUMA_PERIOD_SLOTS; 1351 } 1352 1353 p->numa_scan_period = clamp(p->numa_scan_period + diff, 1354 task_scan_min(p), task_scan_max(p)); 1355 memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality)); 1356 } 1357 1358 static void task_numa_placement(struct task_struct *p) 1359 { 1360 int seq, nid, max_nid = -1, max_group_nid = -1; 1361 unsigned long max_faults = 0, max_group_faults = 0; 1362 unsigned long fault_types[2] = { 0, 0 }; 1363 spinlock_t *group_lock = NULL; 1364 1365 seq = ACCESS_ONCE(p->mm->numa_scan_seq); 1366 if (p->numa_scan_seq == seq) 1367 return; 1368 p->numa_scan_seq = seq; 1369 p->numa_scan_period_max = task_scan_max(p); 1370 1371 /* If the task is part of a group prevent parallel updates to group stats */ 1372 if (p->numa_group) { 1373 group_lock = &p->numa_group->lock; 1374 spin_lock(group_lock); 1375 } 1376 1377 /* Find the node with the highest number of faults */ 1378 for_each_online_node(nid) { 1379 unsigned long faults = 0, group_faults = 0; 1380 int priv, i; 1381 1382 for (priv = 0; priv < 2; priv++) { 1383 long diff; 1384 1385 i = task_faults_idx(nid, priv); 1386 diff = -p->numa_faults[i]; 1387 1388 /* Decay existing window, copy faults since last scan */ 1389 p->numa_faults[i] >>= 1; 1390 p->numa_faults[i] += p->numa_faults_buffer[i]; 1391 fault_types[priv] += p->numa_faults_buffer[i]; 1392 p->numa_faults_buffer[i] = 0; 1393 1394 faults += p->numa_faults[i]; 1395 diff += p->numa_faults[i]; 1396 p->total_numa_faults += diff; 1397 if (p->numa_group) { 1398 /* safe because we can only change our own group */ 1399 p->numa_group->faults[i] += diff; 1400 p->numa_group->total_faults += diff; 1401 group_faults += p->numa_group->faults[i]; 1402 } 1403 } 1404 1405 if (faults > max_faults) { 1406 max_faults = faults; 1407 max_nid = nid; 1408 } 1409 1410 if (group_faults > max_group_faults) { 1411 max_group_faults = group_faults; 1412 max_group_nid = nid; 1413 } 1414 } 1415 1416 update_task_scan_period(p, fault_types[0], fault_types[1]); 1417 1418 if (p->numa_group) { 1419 /* 1420 * If the preferred task and group nids are different, 1421 * iterate over the nodes again to find the best place. 1422 */ 1423 if (max_nid != max_group_nid) { 1424 unsigned long weight, max_weight = 0; 1425 1426 for_each_online_node(nid) { 1427 weight = task_weight(p, nid) + group_weight(p, nid); 1428 if (weight > max_weight) { 1429 max_weight = weight; 1430 max_nid = nid; 1431 } 1432 } 1433 } 1434 1435 spin_unlock(group_lock); 1436 } 1437 1438 /* Preferred node as the node with the most faults */ 1439 if (max_faults && max_nid != p->numa_preferred_nid) { 1440 /* Update the preferred nid and migrate task if possible */ 1441 sched_setnuma(p, max_nid); 1442 numa_migrate_preferred(p); 1443 } 1444 } 1445 1446 static inline int get_numa_group(struct numa_group *grp) 1447 { 1448 return atomic_inc_not_zero(&grp->refcount); 1449 } 1450 1451 static inline void put_numa_group(struct numa_group *grp) 1452 { 1453 if (atomic_dec_and_test(&grp->refcount)) 1454 kfree_rcu(grp, rcu); 1455 } 1456 1457 static void task_numa_group(struct task_struct *p, int cpupid, int flags, 1458 int *priv) 1459 { 1460 struct numa_group *grp, *my_grp; 1461 struct task_struct *tsk; 1462 bool join = false; 1463 int cpu = cpupid_to_cpu(cpupid); 1464 int i; 1465 1466 if (unlikely(!p->numa_group)) { 1467 unsigned int size = sizeof(struct numa_group) + 1468 2*nr_node_ids*sizeof(unsigned long); 1469 1470 grp = kzalloc(size, GFP_KERNEL | __GFP_NOWARN); 1471 if (!grp) 1472 return; 1473 1474 atomic_set(&grp->refcount, 1); 1475 spin_lock_init(&grp->lock); 1476 INIT_LIST_HEAD(&grp->task_list); 1477 grp->gid = p->pid; 1478 1479 for (i = 0; i < 2*nr_node_ids; i++) 1480 grp->faults[i] = p->numa_faults[i]; 1481 1482 grp->total_faults = p->total_numa_faults; 1483 1484 list_add(&p->numa_entry, &grp->task_list); 1485 grp->nr_tasks++; 1486 rcu_assign_pointer(p->numa_group, grp); 1487 } 1488 1489 rcu_read_lock(); 1490 tsk = ACCESS_ONCE(cpu_rq(cpu)->curr); 1491 1492 if (!cpupid_match_pid(tsk, cpupid)) 1493 goto no_join; 1494 1495 grp = rcu_dereference(tsk->numa_group); 1496 if (!grp) 1497 goto no_join; 1498 1499 my_grp = p->numa_group; 1500 if (grp == my_grp) 1501 goto no_join; 1502 1503 /* 1504 * Only join the other group if its bigger; if we're the bigger group, 1505 * the other task will join us. 1506 */ 1507 if (my_grp->nr_tasks > grp->nr_tasks) 1508 goto no_join; 1509 1510 /* 1511 * Tie-break on the grp address. 1512 */ 1513 if (my_grp->nr_tasks == grp->nr_tasks && my_grp > grp) 1514 goto no_join; 1515 1516 /* Always join threads in the same process. */ 1517 if (tsk->mm == current->mm) 1518 join = true; 1519 1520 /* Simple filter to avoid false positives due to PID collisions */ 1521 if (flags & TNF_SHARED) 1522 join = true; 1523 1524 /* Update priv based on whether false sharing was detected */ 1525 *priv = !join; 1526 1527 if (join && !get_numa_group(grp)) 1528 goto no_join; 1529 1530 rcu_read_unlock(); 1531 1532 if (!join) 1533 return; 1534 1535 double_lock(&my_grp->lock, &grp->lock); 1536 1537 for (i = 0; i < 2*nr_node_ids; i++) { 1538 my_grp->faults[i] -= p->numa_faults[i]; 1539 grp->faults[i] += p->numa_faults[i]; 1540 } 1541 my_grp->total_faults -= p->total_numa_faults; 1542 grp->total_faults += p->total_numa_faults; 1543 1544 list_move(&p->numa_entry, &grp->task_list); 1545 my_grp->nr_tasks--; 1546 grp->nr_tasks++; 1547 1548 spin_unlock(&my_grp->lock); 1549 spin_unlock(&grp->lock); 1550 1551 rcu_assign_pointer(p->numa_group, grp); 1552 1553 put_numa_group(my_grp); 1554 return; 1555 1556 no_join: 1557 rcu_read_unlock(); 1558 return; 1559 } 1560 1561 void task_numa_free(struct task_struct *p) 1562 { 1563 struct numa_group *grp = p->numa_group; 1564 int i; 1565 void *numa_faults = p->numa_faults; 1566 1567 if (grp) { 1568 spin_lock(&grp->lock); 1569 for (i = 0; i < 2*nr_node_ids; i++) 1570 grp->faults[i] -= p->numa_faults[i]; 1571 grp->total_faults -= p->total_numa_faults; 1572 1573 list_del(&p->numa_entry); 1574 grp->nr_tasks--; 1575 spin_unlock(&grp->lock); 1576 rcu_assign_pointer(p->numa_group, NULL); 1577 put_numa_group(grp); 1578 } 1579 1580 p->numa_faults = NULL; 1581 p->numa_faults_buffer = NULL; 1582 kfree(numa_faults); 1583 } 1584 1585 /* 1586 * Got a PROT_NONE fault for a page on @node. 1587 */ 1588 void task_numa_fault(int last_cpupid, int node, int pages, int flags) 1589 { 1590 struct task_struct *p = current; 1591 bool migrated = flags & TNF_MIGRATED; 1592 int priv; 1593 1594 if (!numabalancing_enabled) 1595 return; 1596 1597 /* for example, ksmd faulting in a user's mm */ 1598 if (!p->mm) 1599 return; 1600 1601 /* Do not worry about placement if exiting */ 1602 if (p->state == TASK_DEAD) 1603 return; 1604 1605 /* Allocate buffer to track faults on a per-node basis */ 1606 if (unlikely(!p->numa_faults)) { 1607 int size = sizeof(*p->numa_faults) * 2 * nr_node_ids; 1608 1609 /* numa_faults and numa_faults_buffer share the allocation */ 1610 p->numa_faults = kzalloc(size * 2, GFP_KERNEL|__GFP_NOWARN); 1611 if (!p->numa_faults) 1612 return; 1613 1614 BUG_ON(p->numa_faults_buffer); 1615 p->numa_faults_buffer = p->numa_faults + (2 * nr_node_ids); 1616 p->total_numa_faults = 0; 1617 memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality)); 1618 } 1619 1620 /* 1621 * First accesses are treated as private, otherwise consider accesses 1622 * to be private if the accessing pid has not changed 1623 */ 1624 if (unlikely(last_cpupid == (-1 & LAST_CPUPID_MASK))) { 1625 priv = 1; 1626 } else { 1627 priv = cpupid_match_pid(p, last_cpupid); 1628 if (!priv && !(flags & TNF_NO_GROUP)) 1629 task_numa_group(p, last_cpupid, flags, &priv); 1630 } 1631 1632 task_numa_placement(p); 1633 1634 /* 1635 * Retry task to preferred node migration periodically, in case it 1636 * case it previously failed, or the scheduler moved us. 1637 */ 1638 if (time_after(jiffies, p->numa_migrate_retry)) 1639 numa_migrate_preferred(p); 1640 1641 if (migrated) 1642 p->numa_pages_migrated += pages; 1643 1644 p->numa_faults_buffer[task_faults_idx(node, priv)] += pages; 1645 p->numa_faults_locality[!!(flags & TNF_FAULT_LOCAL)] += pages; 1646 } 1647 1648 static void reset_ptenuma_scan(struct task_struct *p) 1649 { 1650 ACCESS_ONCE(p->mm->numa_scan_seq)++; 1651 p->mm->numa_scan_offset = 0; 1652 } 1653 1654 /* 1655 * The expensive part of numa migration is done from task_work context. 1656 * Triggered from task_tick_numa(). 1657 */ 1658 void task_numa_work(struct callback_head *work) 1659 { 1660 unsigned long migrate, next_scan, now = jiffies; 1661 struct task_struct *p = current; 1662 struct mm_struct *mm = p->mm; 1663 struct vm_area_struct *vma; 1664 unsigned long start, end; 1665 unsigned long nr_pte_updates = 0; 1666 long pages; 1667 1668 WARN_ON_ONCE(p != container_of(work, struct task_struct, numa_work)); 1669 1670 work->next = work; /* protect against double add */ 1671 /* 1672 * Who cares about NUMA placement when they're dying. 1673 * 1674 * NOTE: make sure not to dereference p->mm before this check, 1675 * exit_task_work() happens _after_ exit_mm() so we could be called 1676 * without p->mm even though we still had it when we enqueued this 1677 * work. 1678 */ 1679 if (p->flags & PF_EXITING) 1680 return; 1681 1682 if (!mm->numa_next_scan) { 1683 mm->numa_next_scan = now + 1684 msecs_to_jiffies(sysctl_numa_balancing_scan_delay); 1685 } 1686 1687 /* 1688 * Enforce maximal scan/migration frequency.. 1689 */ 1690 migrate = mm->numa_next_scan; 1691 if (time_before(now, migrate)) 1692 return; 1693 1694 if (p->numa_scan_period == 0) { 1695 p->numa_scan_period_max = task_scan_max(p); 1696 p->numa_scan_period = task_scan_min(p); 1697 } 1698 1699 next_scan = now + msecs_to_jiffies(p->numa_scan_period); 1700 if (cmpxchg(&mm->numa_next_scan, migrate, next_scan) != migrate) 1701 return; 1702 1703 /* 1704 * Delay this task enough that another task of this mm will likely win 1705 * the next time around. 1706 */ 1707 p->node_stamp += 2 * TICK_NSEC; 1708 1709 start = mm->numa_scan_offset; 1710 pages = sysctl_numa_balancing_scan_size; 1711 pages <<= 20 - PAGE_SHIFT; /* MB in pages */ 1712 if (!pages) 1713 return; 1714 1715 down_read(&mm->mmap_sem); 1716 vma = find_vma(mm, start); 1717 if (!vma) { 1718 reset_ptenuma_scan(p); 1719 start = 0; 1720 vma = mm->mmap; 1721 } 1722 for (; vma; vma = vma->vm_next) { 1723 if (!vma_migratable(vma) || !vma_policy_mof(p, vma)) 1724 continue; 1725 1726 /* 1727 * Shared library pages mapped by multiple processes are not 1728 * migrated as it is expected they are cache replicated. Avoid 1729 * hinting faults in read-only file-backed mappings or the vdso 1730 * as migrating the pages will be of marginal benefit. 1731 */ 1732 if (!vma->vm_mm || 1733 (vma->vm_file && (vma->vm_flags & (VM_READ|VM_WRITE)) == (VM_READ))) 1734 continue; 1735 1736 /* 1737 * Skip inaccessible VMAs to avoid any confusion between 1738 * PROT_NONE and NUMA hinting ptes 1739 */ 1740 if (!(vma->vm_flags & (VM_READ | VM_EXEC | VM_WRITE))) 1741 continue; 1742 1743 do { 1744 start = max(start, vma->vm_start); 1745 end = ALIGN(start + (pages << PAGE_SHIFT), HPAGE_SIZE); 1746 end = min(end, vma->vm_end); 1747 nr_pte_updates += change_prot_numa(vma, start, end); 1748 1749 /* 1750 * Scan sysctl_numa_balancing_scan_size but ensure that 1751 * at least one PTE is updated so that unused virtual 1752 * address space is quickly skipped. 1753 */ 1754 if (nr_pte_updates) 1755 pages -= (end - start) >> PAGE_SHIFT; 1756 1757 start = end; 1758 if (pages <= 0) 1759 goto out; 1760 1761 cond_resched(); 1762 } while (end != vma->vm_end); 1763 } 1764 1765 out: 1766 /* 1767 * It is possible to reach the end of the VMA list but the last few 1768 * VMAs are not guaranteed to the vma_migratable. If they are not, we 1769 * would find the !migratable VMA on the next scan but not reset the 1770 * scanner to the start so check it now. 1771 */ 1772 if (vma) 1773 mm->numa_scan_offset = start; 1774 else 1775 reset_ptenuma_scan(p); 1776 up_read(&mm->mmap_sem); 1777 } 1778 1779 /* 1780 * Drive the periodic memory faults.. 1781 */ 1782 void task_tick_numa(struct rq *rq, struct task_struct *curr) 1783 { 1784 struct callback_head *work = &curr->numa_work; 1785 u64 period, now; 1786 1787 /* 1788 * We don't care about NUMA placement if we don't have memory. 1789 */ 1790 if (!curr->mm || (curr->flags & PF_EXITING) || work->next != work) 1791 return; 1792 1793 /* 1794 * Using runtime rather than walltime has the dual advantage that 1795 * we (mostly) drive the selection from busy threads and that the 1796 * task needs to have done some actual work before we bother with 1797 * NUMA placement. 1798 */ 1799 now = curr->se.sum_exec_runtime; 1800 period = (u64)curr->numa_scan_period * NSEC_PER_MSEC; 1801 1802 if (now - curr->node_stamp > period) { 1803 if (!curr->node_stamp) 1804 curr->numa_scan_period = task_scan_min(curr); 1805 curr->node_stamp += period; 1806 1807 if (!time_before(jiffies, curr->mm->numa_next_scan)) { 1808 init_task_work(work, task_numa_work); /* TODO: move this into sched_fork() */ 1809 task_work_add(curr, work, true); 1810 } 1811 } 1812 } 1813 #else 1814 static void task_tick_numa(struct rq *rq, struct task_struct *curr) 1815 { 1816 } 1817 1818 static inline void account_numa_enqueue(struct rq *rq, struct task_struct *p) 1819 { 1820 } 1821 1822 static inline void account_numa_dequeue(struct rq *rq, struct task_struct *p) 1823 { 1824 } 1825 #endif /* CONFIG_NUMA_BALANCING */ 1826 1827 static void 1828 account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se) 1829 { 1830 update_load_add(&cfs_rq->load, se->load.weight); 1831 if (!parent_entity(se)) 1832 update_load_add(&rq_of(cfs_rq)->load, se->load.weight); 1833 #ifdef CONFIG_SMP 1834 if (entity_is_task(se)) { 1835 struct rq *rq = rq_of(cfs_rq); 1836 1837 account_numa_enqueue(rq, task_of(se)); 1838 list_add(&se->group_node, &rq->cfs_tasks); 1839 } 1840 #endif 1841 cfs_rq->nr_running++; 1842 } 1843 1844 static void 1845 account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se) 1846 { 1847 update_load_sub(&cfs_rq->load, se->load.weight); 1848 if (!parent_entity(se)) 1849 update_load_sub(&rq_of(cfs_rq)->load, se->load.weight); 1850 if (entity_is_task(se)) { 1851 account_numa_dequeue(rq_of(cfs_rq), task_of(se)); 1852 list_del_init(&se->group_node); 1853 } 1854 cfs_rq->nr_running--; 1855 } 1856 1857 #ifdef CONFIG_FAIR_GROUP_SCHED 1858 # ifdef CONFIG_SMP 1859 static inline long calc_tg_weight(struct task_group *tg, struct cfs_rq *cfs_rq) 1860 { 1861 long tg_weight; 1862 1863 /* 1864 * Use this CPU's actual weight instead of the last load_contribution 1865 * to gain a more accurate current total weight. See 1866 * update_cfs_rq_load_contribution(). 1867 */ 1868 tg_weight = atomic_long_read(&tg->load_avg); 1869 tg_weight -= cfs_rq->tg_load_contrib; 1870 tg_weight += cfs_rq->load.weight; 1871 1872 return tg_weight; 1873 } 1874 1875 static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg) 1876 { 1877 long tg_weight, load, shares; 1878 1879 tg_weight = calc_tg_weight(tg, cfs_rq); 1880 load = cfs_rq->load.weight; 1881 1882 shares = (tg->shares * load); 1883 if (tg_weight) 1884 shares /= tg_weight; 1885 1886 if (shares < MIN_SHARES) 1887 shares = MIN_SHARES; 1888 if (shares > tg->shares) 1889 shares = tg->shares; 1890 1891 return shares; 1892 } 1893 # else /* CONFIG_SMP */ 1894 static inline long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg) 1895 { 1896 return tg->shares; 1897 } 1898 # endif /* CONFIG_SMP */ 1899 static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, 1900 unsigned long weight) 1901 { 1902 if (se->on_rq) { 1903 /* commit outstanding execution time */ 1904 if (cfs_rq->curr == se) 1905 update_curr(cfs_rq); 1906 account_entity_dequeue(cfs_rq, se); 1907 } 1908 1909 update_load_set(&se->load, weight); 1910 1911 if (se->on_rq) 1912 account_entity_enqueue(cfs_rq, se); 1913 } 1914 1915 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq); 1916 1917 static void update_cfs_shares(struct cfs_rq *cfs_rq) 1918 { 1919 struct task_group *tg; 1920 struct sched_entity *se; 1921 long shares; 1922 1923 tg = cfs_rq->tg; 1924 se = tg->se[cpu_of(rq_of(cfs_rq))]; 1925 if (!se || throttled_hierarchy(cfs_rq)) 1926 return; 1927 #ifndef CONFIG_SMP 1928 if (likely(se->load.weight == tg->shares)) 1929 return; 1930 #endif 1931 shares = calc_cfs_shares(cfs_rq, tg); 1932 1933 reweight_entity(cfs_rq_of(se), se, shares); 1934 } 1935 #else /* CONFIG_FAIR_GROUP_SCHED */ 1936 static inline void update_cfs_shares(struct cfs_rq *cfs_rq) 1937 { 1938 } 1939 #endif /* CONFIG_FAIR_GROUP_SCHED */ 1940 1941 #ifdef CONFIG_SMP 1942 /* 1943 * We choose a half-life close to 1 scheduling period. 1944 * Note: The tables below are dependent on this value. 1945 */ 1946 #define LOAD_AVG_PERIOD 32 1947 #define LOAD_AVG_MAX 47742 /* maximum possible load avg */ 1948 #define LOAD_AVG_MAX_N 345 /* number of full periods to produce LOAD_MAX_AVG */ 1949 1950 /* Precomputed fixed inverse multiplies for multiplication by y^n */ 1951 static const u32 runnable_avg_yN_inv[] = { 1952 0xffffffff, 0xfa83b2da, 0xf5257d14, 0xefe4b99a, 0xeac0c6e6, 0xe5b906e6, 1953 0xe0ccdeeb, 0xdbfbb796, 0xd744fcc9, 0xd2a81d91, 0xce248c14, 0xc9b9bd85, 1954 0xc5672a10, 0xc12c4cc9, 0xbd08a39e, 0xb8fbaf46, 0xb504f333, 0xb123f581, 1955 0xad583ee9, 0xa9a15ab4, 0xa5fed6a9, 0xa2704302, 0x9ef5325f, 0x9b8d39b9, 1956 0x9837f050, 0x94f4efa8, 0x91c3d373, 0x8ea4398a, 0x8b95c1e3, 0x88980e80, 1957 0x85aac367, 0x82cd8698, 1958 }; 1959 1960 /* 1961 * Precomputed \Sum y^k { 1<=k<=n }. These are floor(true_value) to prevent 1962 * over-estimates when re-combining. 1963 */ 1964 static const u32 runnable_avg_yN_sum[] = { 1965 0, 1002, 1982, 2941, 3880, 4798, 5697, 6576, 7437, 8279, 9103, 1966 9909,10698,11470,12226,12966,13690,14398,15091,15769,16433,17082, 1967 17718,18340,18949,19545,20128,20698,21256,21802,22336,22859,23371, 1968 }; 1969 1970 /* 1971 * Approximate: 1972 * val * y^n, where y^32 ~= 0.5 (~1 scheduling period) 1973 */ 1974 static __always_inline u64 decay_load(u64 val, u64 n) 1975 { 1976 unsigned int local_n; 1977 1978 if (!n) 1979 return val; 1980 else if (unlikely(n > LOAD_AVG_PERIOD * 63)) 1981 return 0; 1982 1983 /* after bounds checking we can collapse to 32-bit */ 1984 local_n = n; 1985 1986 /* 1987 * As y^PERIOD = 1/2, we can combine 1988 * y^n = 1/2^(n/PERIOD) * k^(n%PERIOD) 1989 * With a look-up table which covers k^n (n<PERIOD) 1990 * 1991 * To achieve constant time decay_load. 1992 */ 1993 if (unlikely(local_n >= LOAD_AVG_PERIOD)) { 1994 val >>= local_n / LOAD_AVG_PERIOD; 1995 local_n %= LOAD_AVG_PERIOD; 1996 } 1997 1998 val *= runnable_avg_yN_inv[local_n]; 1999 /* We don't use SRR here since we always want to round down. */ 2000 return val >> 32; 2001 } 2002 2003 /* 2004 * For updates fully spanning n periods, the contribution to runnable 2005 * average will be: \Sum 1024*y^n 2006 * 2007 * We can compute this reasonably efficiently by combining: 2008 * y^PERIOD = 1/2 with precomputed \Sum 1024*y^n {for n <PERIOD} 2009 */ 2010 static u32 __compute_runnable_contrib(u64 n) 2011 { 2012 u32 contrib = 0; 2013 2014 if (likely(n <= LOAD_AVG_PERIOD)) 2015 return runnable_avg_yN_sum[n]; 2016 else if (unlikely(n >= LOAD_AVG_MAX_N)) 2017 return LOAD_AVG_MAX; 2018 2019 /* Compute \Sum k^n combining precomputed values for k^i, \Sum k^j */ 2020 do { 2021 contrib /= 2; /* y^LOAD_AVG_PERIOD = 1/2 */ 2022 contrib += runnable_avg_yN_sum[LOAD_AVG_PERIOD]; 2023 2024 n -= LOAD_AVG_PERIOD; 2025 } while (n > LOAD_AVG_PERIOD); 2026 2027 contrib = decay_load(contrib, n); 2028 return contrib + runnable_avg_yN_sum[n]; 2029 } 2030 2031 /* 2032 * We can represent the historical contribution to runnable average as the 2033 * coefficients of a geometric series. To do this we sub-divide our runnable 2034 * history into segments of approximately 1ms (1024us); label the segment that 2035 * occurred N-ms ago p_N, with p_0 corresponding to the current period, e.g. 2036 * 2037 * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ... 2038 * p0 p1 p2 2039 * (now) (~1ms ago) (~2ms ago) 2040 * 2041 * Let u_i denote the fraction of p_i that the entity was runnable. 2042 * 2043 * We then designate the fractions u_i as our co-efficients, yielding the 2044 * following representation of historical load: 2045 * u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ... 2046 * 2047 * We choose y based on the with of a reasonably scheduling period, fixing: 2048 * y^32 = 0.5 2049 * 2050 * This means that the contribution to load ~32ms ago (u_32) will be weighted 2051 * approximately half as much as the contribution to load within the last ms 2052 * (u_0). 2053 * 2054 * When a period "rolls over" and we have new u_0`, multiplying the previous 2055 * sum again by y is sufficient to update: 2056 * load_avg = u_0` + y*(u_0 + u_1*y + u_2*y^2 + ... ) 2057 * = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}] 2058 */ 2059 static __always_inline int __update_entity_runnable_avg(u64 now, 2060 struct sched_avg *sa, 2061 int runnable) 2062 { 2063 u64 delta, periods; 2064 u32 runnable_contrib; 2065 int delta_w, decayed = 0; 2066 2067 delta = now - sa->last_runnable_update; 2068 /* 2069 * This should only happen when time goes backwards, which it 2070 * unfortunately does during sched clock init when we swap over to TSC. 2071 */ 2072 if ((s64)delta < 0) { 2073 sa->last_runnable_update = now; 2074 return 0; 2075 } 2076 2077 /* 2078 * Use 1024ns as the unit of measurement since it's a reasonable 2079 * approximation of 1us and fast to compute. 2080 */ 2081 delta >>= 10; 2082 if (!delta) 2083 return 0; 2084 sa->last_runnable_update = now; 2085 2086 /* delta_w is the amount already accumulated against our next period */ 2087 delta_w = sa->runnable_avg_period % 1024; 2088 if (delta + delta_w >= 1024) { 2089 /* period roll-over */ 2090 decayed = 1; 2091 2092 /* 2093 * Now that we know we're crossing a period boundary, figure 2094 * out how much from delta we need to complete the current 2095 * period and accrue it. 2096 */ 2097 delta_w = 1024 - delta_w; 2098 if (runnable) 2099 sa->runnable_avg_sum += delta_w; 2100 sa->runnable_avg_period += delta_w; 2101 2102 delta -= delta_w; 2103 2104 /* Figure out how many additional periods this update spans */ 2105 periods = delta / 1024; 2106 delta %= 1024; 2107 2108 sa->runnable_avg_sum = decay_load(sa->runnable_avg_sum, 2109 periods + 1); 2110 sa->runnable_avg_period = decay_load(sa->runnable_avg_period, 2111 periods + 1); 2112 2113 /* Efficiently calculate \sum (1..n_period) 1024*y^i */ 2114 runnable_contrib = __compute_runnable_contrib(periods); 2115 if (runnable) 2116 sa->runnable_avg_sum += runnable_contrib; 2117 sa->runnable_avg_period += runnable_contrib; 2118 } 2119 2120 /* Remainder of delta accrued against u_0` */ 2121 if (runnable) 2122 sa->runnable_avg_sum += delta; 2123 sa->runnable_avg_period += delta; 2124 2125 return decayed; 2126 } 2127 2128 /* Synchronize an entity's decay with its parenting cfs_rq.*/ 2129 static inline u64 __synchronize_entity_decay(struct sched_entity *se) 2130 { 2131 struct cfs_rq *cfs_rq = cfs_rq_of(se); 2132 u64 decays = atomic64_read(&cfs_rq->decay_counter); 2133 2134 decays -= se->avg.decay_count; 2135 if (!decays) 2136 return 0; 2137 2138 se->avg.load_avg_contrib = decay_load(se->avg.load_avg_contrib, decays); 2139 se->avg.decay_count = 0; 2140 2141 return decays; 2142 } 2143 2144 #ifdef CONFIG_FAIR_GROUP_SCHED 2145 static inline void __update_cfs_rq_tg_load_contrib(struct cfs_rq *cfs_rq, 2146 int force_update) 2147 { 2148 struct task_group *tg = cfs_rq->tg; 2149 long tg_contrib; 2150 2151 tg_contrib = cfs_rq->runnable_load_avg + cfs_rq->blocked_load_avg; 2152 tg_contrib -= cfs_rq->tg_load_contrib; 2153 2154 if (force_update || abs(tg_contrib) > cfs_rq->tg_load_contrib / 8) { 2155 atomic_long_add(tg_contrib, &tg->load_avg); 2156 cfs_rq->tg_load_contrib += tg_contrib; 2157 } 2158 } 2159 2160 /* 2161 * Aggregate cfs_rq runnable averages into an equivalent task_group 2162 * representation for computing load contributions. 2163 */ 2164 static inline void __update_tg_runnable_avg(struct sched_avg *sa, 2165 struct cfs_rq *cfs_rq) 2166 { 2167 struct task_group *tg = cfs_rq->tg; 2168 long contrib; 2169 2170 /* The fraction of a cpu used by this cfs_rq */ 2171 contrib = div_u64((u64)sa->runnable_avg_sum << NICE_0_SHIFT, 2172 sa->runnable_avg_period + 1); 2173 contrib -= cfs_rq->tg_runnable_contrib; 2174 2175 if (abs(contrib) > cfs_rq->tg_runnable_contrib / 64) { 2176 atomic_add(contrib, &tg->runnable_avg); 2177 cfs_rq->tg_runnable_contrib += contrib; 2178 } 2179 } 2180 2181 static inline void __update_group_entity_contrib(struct sched_entity *se) 2182 { 2183 struct cfs_rq *cfs_rq = group_cfs_rq(se); 2184 struct task_group *tg = cfs_rq->tg; 2185 int runnable_avg; 2186 2187 u64 contrib; 2188 2189 contrib = cfs_rq->tg_load_contrib * tg->shares; 2190 se->avg.load_avg_contrib = div_u64(contrib, 2191 atomic_long_read(&tg->load_avg) + 1); 2192 2193 /* 2194 * For group entities we need to compute a correction term in the case 2195 * that they are consuming <1 cpu so that we would contribute the same 2196 * load as a task of equal weight. 2197 * 2198 * Explicitly co-ordinating this measurement would be expensive, but 2199 * fortunately the sum of each cpus contribution forms a usable 2200 * lower-bound on the true value. 2201 * 2202 * Consider the aggregate of 2 contributions. Either they are disjoint 2203 * (and the sum represents true value) or they are disjoint and we are 2204 * understating by the aggregate of their overlap. 2205 * 2206 * Extending this to N cpus, for a given overlap, the maximum amount we 2207 * understand is then n_i(n_i+1)/2 * w_i where n_i is the number of 2208 * cpus that overlap for this interval and w_i is the interval width. 2209 * 2210 * On a small machine; the first term is well-bounded which bounds the 2211 * total error since w_i is a subset of the period. Whereas on a 2212 * larger machine, while this first term can be larger, if w_i is the 2213 * of consequential size guaranteed to see n_i*w_i quickly converge to 2214 * our upper bound of 1-cpu. 2215 */ 2216 runnable_avg = atomic_read(&tg->runnable_avg); 2217 if (runnable_avg < NICE_0_LOAD) { 2218 se->avg.load_avg_contrib *= runnable_avg; 2219 se->avg.load_avg_contrib >>= NICE_0_SHIFT; 2220 } 2221 } 2222 #else 2223 static inline void __update_cfs_rq_tg_load_contrib(struct cfs_rq *cfs_rq, 2224 int force_update) {} 2225 static inline void __update_tg_runnable_avg(struct sched_avg *sa, 2226 struct cfs_rq *cfs_rq) {} 2227 static inline void __update_group_entity_contrib(struct sched_entity *se) {} 2228 #endif 2229 2230 static inline void __update_task_entity_contrib(struct sched_entity *se) 2231 { 2232 u32 contrib; 2233 2234 /* avoid overflowing a 32-bit type w/ SCHED_LOAD_SCALE */ 2235 contrib = se->avg.runnable_avg_sum * scale_load_down(se->load.weight); 2236 contrib /= (se->avg.runnable_avg_period + 1); 2237 se->avg.load_avg_contrib = scale_load(contrib); 2238 } 2239 2240 /* Compute the current contribution to load_avg by se, return any delta */ 2241 static long __update_entity_load_avg_contrib(struct sched_entity *se) 2242 { 2243 long old_contrib = se->avg.load_avg_contrib; 2244 2245 if (entity_is_task(se)) { 2246 __update_task_entity_contrib(se); 2247 } else { 2248 __update_tg_runnable_avg(&se->avg, group_cfs_rq(se)); 2249 __update_group_entity_contrib(se); 2250 } 2251 2252 return se->avg.load_avg_contrib - old_contrib; 2253 } 2254 2255 static inline void subtract_blocked_load_contrib(struct cfs_rq *cfs_rq, 2256 long load_contrib) 2257 { 2258 if (likely(load_contrib < cfs_rq->blocked_load_avg)) 2259 cfs_rq->blocked_load_avg -= load_contrib; 2260 else 2261 cfs_rq->blocked_load_avg = 0; 2262 } 2263 2264 static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq); 2265 2266 /* Update a sched_entity's runnable average */ 2267 static inline void update_entity_load_avg(struct sched_entity *se, 2268 int update_cfs_rq) 2269 { 2270 struct cfs_rq *cfs_rq = cfs_rq_of(se); 2271 long contrib_delta; 2272 u64 now; 2273 2274 /* 2275 * For a group entity we need to use their owned cfs_rq_clock_task() in 2276 * case they are the parent of a throttled hierarchy. 2277 */ 2278 if (entity_is_task(se)) 2279 now = cfs_rq_clock_task(cfs_rq); 2280 else 2281 now = cfs_rq_clock_task(group_cfs_rq(se)); 2282 2283 if (!__update_entity_runnable_avg(now, &se->avg, se->on_rq)) 2284 return; 2285 2286 contrib_delta = __update_entity_load_avg_contrib(se); 2287 2288 if (!update_cfs_rq) 2289 return; 2290 2291 if (se->on_rq) 2292 cfs_rq->runnable_load_avg += contrib_delta; 2293 else 2294 subtract_blocked_load_contrib(cfs_rq, -contrib_delta); 2295 } 2296 2297 /* 2298 * Decay the load contributed by all blocked children and account this so that 2299 * their contribution may appropriately discounted when they wake up. 2300 */ 2301 static void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq, int force_update) 2302 { 2303 u64 now = cfs_rq_clock_task(cfs_rq) >> 20; 2304 u64 decays; 2305 2306 decays = now - cfs_rq->last_decay; 2307 if (!decays && !force_update) 2308 return; 2309 2310 if (atomic_long_read(&cfs_rq->removed_load)) { 2311 unsigned long removed_load; 2312 removed_load = atomic_long_xchg(&cfs_rq->removed_load, 0); 2313 subtract_blocked_load_contrib(cfs_rq, removed_load); 2314 } 2315 2316 if (decays) { 2317 cfs_rq->blocked_load_avg = decay_load(cfs_rq->blocked_load_avg, 2318 decays); 2319 atomic64_add(decays, &cfs_rq->decay_counter); 2320 cfs_rq->last_decay = now; 2321 } 2322 2323 __update_cfs_rq_tg_load_contrib(cfs_rq, force_update); 2324 } 2325 2326 static inline void update_rq_runnable_avg(struct rq *rq, int runnable) 2327 { 2328 __update_entity_runnable_avg(rq_clock_task(rq), &rq->avg, runnable); 2329 __update_tg_runnable_avg(&rq->avg, &rq->cfs); 2330 } 2331 2332 /* Add the load generated by se into cfs_rq's child load-average */ 2333 static inline void enqueue_entity_load_avg(struct cfs_rq *cfs_rq, 2334 struct sched_entity *se, 2335 int wakeup) 2336 { 2337 /* 2338 * We track migrations using entity decay_count <= 0, on a wake-up 2339 * migration we use a negative decay count to track the remote decays 2340 * accumulated while sleeping. 2341 * 2342 * Newly forked tasks are enqueued with se->avg.decay_count == 0, they 2343 * are seen by enqueue_entity_load_avg() as a migration with an already 2344 * constructed load_avg_contrib. 2345 */ 2346 if (unlikely(se->avg.decay_count <= 0)) { 2347 se->avg.last_runnable_update = rq_clock_task(rq_of(cfs_rq)); 2348 if (se->avg.decay_count) { 2349 /* 2350 * In a wake-up migration we have to approximate the 2351 * time sleeping. This is because we can't synchronize 2352 * clock_task between the two cpus, and it is not 2353 * guaranteed to be read-safe. Instead, we can 2354 * approximate this using our carried decays, which are 2355 * explicitly atomically readable. 2356 */ 2357 se->avg.last_runnable_update -= (-se->avg.decay_count) 2358 << 20; 2359 update_entity_load_avg(se, 0); 2360 /* Indicate that we're now synchronized and on-rq */ 2361 se->avg.decay_count = 0; 2362 } 2363 wakeup = 0; 2364 } else { 2365 __synchronize_entity_decay(se); 2366 } 2367 2368 /* migrated tasks did not contribute to our blocked load */ 2369 if (wakeup) { 2370 subtract_blocked_load_contrib(cfs_rq, se->avg.load_avg_contrib); 2371 update_entity_load_avg(se, 0); 2372 } 2373 2374 cfs_rq->runnable_load_avg += se->avg.load_avg_contrib; 2375 /* we force update consideration on load-balancer moves */ 2376 update_cfs_rq_blocked_load(cfs_rq, !wakeup); 2377 } 2378 2379 /* 2380 * Remove se's load from this cfs_rq child load-average, if the entity is 2381 * transitioning to a blocked state we track its projected decay using 2382 * blocked_load_avg. 2383 */ 2384 static inline void dequeue_entity_load_avg(struct cfs_rq *cfs_rq, 2385 struct sched_entity *se, 2386 int sleep) 2387 { 2388 update_entity_load_avg(se, 1); 2389 /* we force update consideration on load-balancer moves */ 2390 update_cfs_rq_blocked_load(cfs_rq, !sleep); 2391 2392 cfs_rq->runnable_load_avg -= se->avg.load_avg_contrib; 2393 if (sleep) { 2394 cfs_rq->blocked_load_avg += se->avg.load_avg_contrib; 2395 se->avg.decay_count = atomic64_read(&cfs_rq->decay_counter); 2396 } /* migrations, e.g. sleep=0 leave decay_count == 0 */ 2397 } 2398 2399 /* 2400 * Update the rq's load with the elapsed running time before entering 2401 * idle. if the last scheduled task is not a CFS task, idle_enter will 2402 * be the only way to update the runnable statistic. 2403 */ 2404 void idle_enter_fair(struct rq *this_rq) 2405 { 2406 update_rq_runnable_avg(this_rq, 1); 2407 } 2408 2409 /* 2410 * Update the rq's load with the elapsed idle time before a task is 2411 * scheduled. if the newly scheduled task is not a CFS task, idle_exit will 2412 * be the only way to update the runnable statistic. 2413 */ 2414 void idle_exit_fair(struct rq *this_rq) 2415 { 2416 update_rq_runnable_avg(this_rq, 0); 2417 } 2418 2419 #else 2420 static inline void update_entity_load_avg(struct sched_entity *se, 2421 int update_cfs_rq) {} 2422 static inline void update_rq_runnable_avg(struct rq *rq, int runnable) {} 2423 static inline void enqueue_entity_load_avg(struct cfs_rq *cfs_rq, 2424 struct sched_entity *se, 2425 int wakeup) {} 2426 static inline void dequeue_entity_load_avg(struct cfs_rq *cfs_rq, 2427 struct sched_entity *se, 2428 int sleep) {} 2429 static inline void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq, 2430 int force_update) {} 2431 #endif 2432 2433 static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se) 2434 { 2435 #ifdef CONFIG_SCHEDSTATS 2436 struct task_struct *tsk = NULL; 2437 2438 if (entity_is_task(se)) 2439 tsk = task_of(se); 2440 2441 if (se->statistics.sleep_start) { 2442 u64 delta = rq_clock(rq_of(cfs_rq)) - se->statistics.sleep_start; 2443 2444 if ((s64)delta < 0) 2445 delta = 0; 2446 2447 if (unlikely(delta > se->statistics.sleep_max)) 2448 se->statistics.sleep_max = delta; 2449 2450 se->statistics.sleep_start = 0; 2451 se->statistics.sum_sleep_runtime += delta; 2452 2453 if (tsk) { 2454 account_scheduler_latency(tsk, delta >> 10, 1); 2455 trace_sched_stat_sleep(tsk, delta); 2456 } 2457 } 2458 if (se->statistics.block_start) { 2459 u64 delta = rq_clock(rq_of(cfs_rq)) - se->statistics.block_start; 2460 2461 if ((s64)delta < 0) 2462 delta = 0; 2463 2464 if (unlikely(delta > se->statistics.block_max)) 2465 se->statistics.block_max = delta; 2466 2467 se->statistics.block_start = 0; 2468 se->statistics.sum_sleep_runtime += delta; 2469 2470 if (tsk) { 2471 if (tsk->in_iowait) { 2472 se->statistics.iowait_sum += delta; 2473 se->statistics.iowait_count++; 2474 trace_sched_stat_iowait(tsk, delta); 2475 } 2476 2477 trace_sched_stat_blocked(tsk, delta); 2478 2479 /* 2480 * Blocking time is in units of nanosecs, so shift by 2481 * 20 to get a milliseconds-range estimation of the 2482 * amount of time that the task spent sleeping: 2483 */ 2484 if (unlikely(prof_on == SLEEP_PROFILING)) { 2485 profile_hits(SLEEP_PROFILING, 2486 (void *)get_wchan(tsk), 2487 delta >> 20); 2488 } 2489 account_scheduler_latency(tsk, delta >> 10, 0); 2490 } 2491 } 2492 #endif 2493 } 2494 2495 static void check_spread(struct cfs_rq *cfs_rq, struct sched_entity *se) 2496 { 2497 #ifdef CONFIG_SCHED_DEBUG 2498 s64 d = se->vruntime - cfs_rq->min_vruntime; 2499 2500 if (d < 0) 2501 d = -d; 2502 2503 if (d > 3*sysctl_sched_latency) 2504 schedstat_inc(cfs_rq, nr_spread_over); 2505 #endif 2506 } 2507 2508 static void 2509 place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial) 2510 { 2511 u64 vruntime = cfs_rq->min_vruntime; 2512 2513 /* 2514 * The 'current' period is already promised to the current tasks, 2515 * however the extra weight of the new task will slow them down a 2516 * little, place the new task so that it fits in the slot that 2517 * stays open at the end. 2518 */ 2519 if (initial && sched_feat(START_DEBIT)) 2520 vruntime += sched_vslice(cfs_rq, se); 2521 2522 /* sleeps up to a single latency don't count. */ 2523 if (!initial) { 2524 unsigned long thresh = sysctl_sched_latency; 2525 2526 /* 2527 * Halve their sleep time's effect, to allow 2528 * for a gentler effect of sleepers: 2529 */ 2530 if (sched_feat(GENTLE_FAIR_SLEEPERS)) 2531 thresh >>= 1; 2532 2533 vruntime -= thresh; 2534 } 2535 2536 /* ensure we never gain time by being placed backwards. */ 2537 se->vruntime = max_vruntime(se->vruntime, vruntime); 2538 } 2539 2540 static void check_enqueue_throttle(struct cfs_rq *cfs_rq); 2541 2542 static void 2543 enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) 2544 { 2545 /* 2546 * Update the normalized vruntime before updating min_vruntime 2547 * through calling update_curr(). 2548 */ 2549 if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING)) 2550 se->vruntime += cfs_rq->min_vruntime; 2551 2552 /* 2553 * Update run-time statistics of the 'current'. 2554 */ 2555 update_curr(cfs_rq); 2556 enqueue_entity_load_avg(cfs_rq, se, flags & ENQUEUE_WAKEUP); 2557 account_entity_enqueue(cfs_rq, se); 2558 update_cfs_shares(cfs_rq); 2559 2560 if (flags & ENQUEUE_WAKEUP) { 2561 place_entity(cfs_rq, se, 0); 2562 enqueue_sleeper(cfs_rq, se); 2563 } 2564 2565 update_stats_enqueue(cfs_rq, se); 2566 check_spread(cfs_rq, se); 2567 if (se != cfs_rq->curr) 2568 __enqueue_entity(cfs_rq, se); 2569 se->on_rq = 1; 2570 2571 if (cfs_rq->nr_running == 1) { 2572 list_add_leaf_cfs_rq(cfs_rq); 2573 check_enqueue_throttle(cfs_rq); 2574 } 2575 } 2576 2577 static void __clear_buddies_last(struct sched_entity *se) 2578 { 2579 for_each_sched_entity(se) { 2580 struct cfs_rq *cfs_rq = cfs_rq_of(se); 2581 if (cfs_rq->last == se) 2582 cfs_rq->last = NULL; 2583 else 2584 break; 2585 } 2586 } 2587 2588 static void __clear_buddies_next(struct sched_entity *se) 2589 { 2590 for_each_sched_entity(se) { 2591 struct cfs_rq *cfs_rq = cfs_rq_of(se); 2592 if (cfs_rq->next == se) 2593 cfs_rq->next = NULL; 2594 else 2595 break; 2596 } 2597 } 2598 2599 static void __clear_buddies_skip(struct sched_entity *se) 2600 { 2601 for_each_sched_entity(se) { 2602 struct cfs_rq *cfs_rq = cfs_rq_of(se); 2603 if (cfs_rq->skip == se) 2604 cfs_rq->skip = NULL; 2605 else 2606 break; 2607 } 2608 } 2609 2610 static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se) 2611 { 2612 if (cfs_rq->last == se) 2613 __clear_buddies_last(se); 2614 2615 if (cfs_rq->next == se) 2616 __clear_buddies_next(se); 2617 2618 if (cfs_rq->skip == se) 2619 __clear_buddies_skip(se); 2620 } 2621 2622 static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq); 2623 2624 static void 2625 dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) 2626 { 2627 /* 2628 * Update run-time statistics of the 'current'. 2629 */ 2630 update_curr(cfs_rq); 2631 dequeue_entity_load_avg(cfs_rq, se, flags & DEQUEUE_SLEEP); 2632 2633 update_stats_dequeue(cfs_rq, se); 2634 if (flags & DEQUEUE_SLEEP) { 2635 #ifdef CONFIG_SCHEDSTATS 2636 if (entity_is_task(se)) { 2637 struct task_struct *tsk = task_of(se); 2638 2639 if (tsk->state & TASK_INTERRUPTIBLE) 2640 se->statistics.sleep_start = rq_clock(rq_of(cfs_rq)); 2641 if (tsk->state & TASK_UNINTERRUPTIBLE) 2642 se->statistics.block_start = rq_clock(rq_of(cfs_rq)); 2643 } 2644 #endif 2645 } 2646 2647 clear_buddies(cfs_rq, se); 2648 2649 if (se != cfs_rq->curr) 2650 __dequeue_entity(cfs_rq, se); 2651 se->on_rq = 0; 2652 account_entity_dequeue(cfs_rq, se); 2653 2654 /* 2655 * Normalize the entity after updating the min_vruntime because the 2656 * update can refer to the ->curr item and we need to reflect this 2657 * movement in our normalized position. 2658 */ 2659 if (!(flags & DEQUEUE_SLEEP)) 2660 se->vruntime -= cfs_rq->min_vruntime; 2661 2662 /* return excess runtime on last dequeue */ 2663 return_cfs_rq_runtime(cfs_rq); 2664 2665 update_min_vruntime(cfs_rq); 2666 update_cfs_shares(cfs_rq); 2667 } 2668 2669 /* 2670 * Preempt the current task with a newly woken task if needed: 2671 */ 2672 static void 2673 check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr) 2674 { 2675 unsigned long ideal_runtime, delta_exec; 2676 struct sched_entity *se; 2677 s64 delta; 2678 2679 ideal_runtime = sched_slice(cfs_rq, curr); 2680 delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime; 2681 if (delta_exec > ideal_runtime) { 2682 resched_task(rq_of(cfs_rq)->curr); 2683 /* 2684 * The current task ran long enough, ensure it doesn't get 2685 * re-elected due to buddy favours. 2686 */ 2687 clear_buddies(cfs_rq, curr); 2688 return; 2689 } 2690 2691 /* 2692 * Ensure that a task that missed wakeup preemption by a 2693 * narrow margin doesn't have to wait for a full slice. 2694 * This also mitigates buddy induced latencies under load. 2695 */ 2696 if (delta_exec < sysctl_sched_min_granularity) 2697 return; 2698 2699 se = __pick_first_entity(cfs_rq); 2700 delta = curr->vruntime - se->vruntime; 2701 2702 if (delta < 0) 2703 return; 2704 2705 if (delta > ideal_runtime) 2706 resched_task(rq_of(cfs_rq)->curr); 2707 } 2708 2709 static void 2710 set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) 2711 { 2712 /* 'current' is not kept within the tree. */ 2713 if (se->on_rq) { 2714 /* 2715 * Any task has to be enqueued before it get to execute on 2716 * a CPU. So account for the time it spent waiting on the 2717 * runqueue. 2718 */ 2719 update_stats_wait_end(cfs_rq, se); 2720 __dequeue_entity(cfs_rq, se); 2721 } 2722 2723 update_stats_curr_start(cfs_rq, se); 2724 cfs_rq->curr = se; 2725 #ifdef CONFIG_SCHEDSTATS 2726 /* 2727 * Track our maximum slice length, if the CPU's load is at 2728 * least twice that of our own weight (i.e. dont track it 2729 * when there are only lesser-weight tasks around): 2730 */ 2731 if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) { 2732 se->statistics.slice_max = max(se->statistics.slice_max, 2733 se->sum_exec_runtime - se->prev_sum_exec_runtime); 2734 } 2735 #endif 2736 se->prev_sum_exec_runtime = se->sum_exec_runtime; 2737 } 2738 2739 static int 2740 wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se); 2741 2742 /* 2743 * Pick the next process, keeping these things in mind, in this order: 2744 * 1) keep things fair between processes/task groups 2745 * 2) pick the "next" process, since someone really wants that to run 2746 * 3) pick the "last" process, for cache locality 2747 * 4) do not run the "skip" process, if something else is available 2748 */ 2749 static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq) 2750 { 2751 struct sched_entity *se = __pick_first_entity(cfs_rq); 2752 struct sched_entity *left = se; 2753 2754 /* 2755 * Avoid running the skip buddy, if running something else can 2756 * be done without getting too unfair. 2757 */ 2758 if (cfs_rq->skip == se) { 2759 struct sched_entity *second = __pick_next_entity(se); 2760 if (second && wakeup_preempt_entity(second, left) < 1) 2761 se = second; 2762 } 2763 2764 /* 2765 * Prefer last buddy, try to return the CPU to a preempted task. 2766 */ 2767 if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1) 2768 se = cfs_rq->last; 2769 2770 /* 2771 * Someone really wants this to run. If it's not unfair, run it. 2772 */ 2773 if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1) 2774 se = cfs_rq->next; 2775 2776 clear_buddies(cfs_rq, se); 2777 2778 return se; 2779 } 2780 2781 static void check_cfs_rq_runtime(struct cfs_rq *cfs_rq); 2782 2783 static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev) 2784 { 2785 /* 2786 * If still on the runqueue then deactivate_task() 2787 * was not called and update_curr() has to be done: 2788 */ 2789 if (prev->on_rq) 2790 update_curr(cfs_rq); 2791 2792 /* throttle cfs_rqs exceeding runtime */ 2793 check_cfs_rq_runtime(cfs_rq); 2794 2795 check_spread(cfs_rq, prev); 2796 if (prev->on_rq) { 2797 update_stats_wait_start(cfs_rq, prev); 2798 /* Put 'current' back into the tree. */ 2799 __enqueue_entity(cfs_rq, prev); 2800 /* in !on_rq case, update occurred at dequeue */ 2801 update_entity_load_avg(prev, 1); 2802 } 2803 cfs_rq->curr = NULL; 2804 } 2805 2806 static void 2807 entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued) 2808 { 2809 /* 2810 * Update run-time statistics of the 'current'. 2811 */ 2812 update_curr(cfs_rq); 2813 2814 /* 2815 * Ensure that runnable average is periodically updated. 2816 */ 2817 update_entity_load_avg(curr, 1); 2818 update_cfs_rq_blocked_load(cfs_rq, 1); 2819 update_cfs_shares(cfs_rq); 2820 2821 #ifdef CONFIG_SCHED_HRTICK 2822 /* 2823 * queued ticks are scheduled to match the slice, so don't bother 2824 * validating it and just reschedule. 2825 */ 2826 if (queued) { 2827 resched_task(rq_of(cfs_rq)->curr); 2828 return; 2829 } 2830 /* 2831 * don't let the period tick interfere with the hrtick preemption 2832 */ 2833 if (!sched_feat(DOUBLE_TICK) && 2834 hrtimer_active(&rq_of(cfs_rq)->hrtick_timer)) 2835 return; 2836 #endif 2837 2838 if (cfs_rq->nr_running > 1) 2839 check_preempt_tick(cfs_rq, curr); 2840 } 2841 2842 2843 /************************************************** 2844 * CFS bandwidth control machinery 2845 */ 2846 2847 #ifdef CONFIG_CFS_BANDWIDTH 2848 2849 #ifdef HAVE_JUMP_LABEL 2850 static struct static_key __cfs_bandwidth_used; 2851 2852 static inline bool cfs_bandwidth_used(void) 2853 { 2854 return static_key_false(&__cfs_bandwidth_used); 2855 } 2856 2857 void cfs_bandwidth_usage_inc(void) 2858 { 2859 static_key_slow_inc(&__cfs_bandwidth_used); 2860 } 2861 2862 void cfs_bandwidth_usage_dec(void) 2863 { 2864 static_key_slow_dec(&__cfs_bandwidth_used); 2865 } 2866 #else /* HAVE_JUMP_LABEL */ 2867 static bool cfs_bandwidth_used(void) 2868 { 2869 return true; 2870 } 2871 2872 void cfs_bandwidth_usage_inc(void) {} 2873 void cfs_bandwidth_usage_dec(void) {} 2874 #endif /* HAVE_JUMP_LABEL */ 2875 2876 /* 2877 * default period for cfs group bandwidth. 2878 * default: 0.1s, units: nanoseconds 2879 */ 2880 static inline u64 default_cfs_period(void) 2881 { 2882 return 100000000ULL; 2883 } 2884 2885 static inline u64 sched_cfs_bandwidth_slice(void) 2886 { 2887 return (u64)sysctl_sched_cfs_bandwidth_slice * NSEC_PER_USEC; 2888 } 2889 2890 /* 2891 * Replenish runtime according to assigned quota and update expiration time. 2892 * We use sched_clock_cpu directly instead of rq->clock to avoid adding 2893 * additional synchronization around rq->lock. 2894 * 2895 * requires cfs_b->lock 2896 */ 2897 void __refill_cfs_bandwidth_runtime(struct cfs_bandwidth *cfs_b) 2898 { 2899 u64 now; 2900 2901 if (cfs_b->quota == RUNTIME_INF) 2902 return; 2903 2904 now = sched_clock_cpu(smp_processor_id()); 2905 cfs_b->runtime = cfs_b->quota; 2906 cfs_b->runtime_expires = now + ktime_to_ns(cfs_b->period); 2907 } 2908 2909 static inline struct cfs_bandwidth *tg_cfs_bandwidth(struct task_group *tg) 2910 { 2911 return &tg->cfs_bandwidth; 2912 } 2913 2914 /* rq->task_clock normalized against any time this cfs_rq has spent throttled */ 2915 static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq) 2916 { 2917 if (unlikely(cfs_rq->throttle_count)) 2918 return cfs_rq->throttled_clock_task; 2919 2920 return rq_clock_task(rq_of(cfs_rq)) - cfs_rq->throttled_clock_task_time; 2921 } 2922 2923 /* returns 0 on failure to allocate runtime */ 2924 static int assign_cfs_rq_runtime(struct cfs_rq *cfs_rq) 2925 { 2926 struct task_group *tg = cfs_rq->tg; 2927 struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(tg); 2928 u64 amount = 0, min_amount, expires; 2929 2930 /* note: this is a positive sum as runtime_remaining <= 0 */ 2931 min_amount = sched_cfs_bandwidth_slice() - cfs_rq->runtime_remaining; 2932 2933 raw_spin_lock(&cfs_b->lock); 2934 if (cfs_b->quota == RUNTIME_INF) 2935 amount = min_amount; 2936 else { 2937 /* 2938 * If the bandwidth pool has become inactive, then at least one 2939 * period must have elapsed since the last consumption. 2940 * Refresh the global state and ensure bandwidth timer becomes 2941 * active. 2942 */ 2943 if (!cfs_b->timer_active) { 2944 __refill_cfs_bandwidth_runtime(cfs_b); 2945 __start_cfs_bandwidth(cfs_b); 2946 } 2947 2948 if (cfs_b->runtime > 0) { 2949 amount = min(cfs_b->runtime, min_amount); 2950 cfs_b->runtime -= amount; 2951 cfs_b->idle = 0; 2952 } 2953 } 2954 expires = cfs_b->runtime_expires; 2955 raw_spin_unlock(&cfs_b->lock); 2956 2957 cfs_rq->runtime_remaining += amount; 2958 /* 2959 * we may have advanced our local expiration to account for allowed 2960 * spread between our sched_clock and the one on which runtime was 2961 * issued. 2962 */ 2963 if ((s64)(expires - cfs_rq->runtime_expires) > 0) 2964 cfs_rq->runtime_expires = expires; 2965 2966 return cfs_rq->runtime_remaining > 0; 2967 } 2968 2969 /* 2970 * Note: This depends on the synchronization provided by sched_clock and the 2971 * fact that rq->clock snapshots this value. 2972 */ 2973 static void expire_cfs_rq_runtime(struct cfs_rq *cfs_rq) 2974 { 2975 struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg); 2976 2977 /* if the deadline is ahead of our clock, nothing to do */ 2978 if (likely((s64)(rq_clock(rq_of(cfs_rq)) - cfs_rq->runtime_expires) < 0)) 2979 return; 2980 2981 if (cfs_rq->runtime_remaining < 0) 2982 return; 2983 2984 /* 2985 * If the local deadline has passed we have to consider the 2986 * possibility that our sched_clock is 'fast' and the global deadline 2987 * has not truly expired. 2988 * 2989 * Fortunately we can check determine whether this the case by checking 2990 * whether the global deadline has advanced. 2991 */ 2992 2993 if ((s64)(cfs_rq->runtime_expires - cfs_b->runtime_expires) >= 0) { 2994 /* extend local deadline, drift is bounded above by 2 ticks */ 2995 cfs_rq->runtime_expires += TICK_NSEC; 2996 } else { 2997 /* global deadline is ahead, expiration has passed */ 2998 cfs_rq->runtime_remaining = 0; 2999 } 3000 } 3001 3002 static void __account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec) 3003 { 3004 /* dock delta_exec before expiring quota (as it could span periods) */ 3005 cfs_rq->runtime_remaining -= delta_exec; 3006 expire_cfs_rq_runtime(cfs_rq); 3007 3008 if (likely(cfs_rq->runtime_remaining > 0)) 3009 return; 3010 3011 /* 3012 * if we're unable to extend our runtime we resched so that the active 3013 * hierarchy can be throttled 3014 */ 3015 if (!assign_cfs_rq_runtime(cfs_rq) && likely(cfs_rq->curr)) 3016 resched_task(rq_of(cfs_rq)->curr); 3017 } 3018 3019 static __always_inline 3020 void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec) 3021 { 3022 if (!cfs_bandwidth_used() || !cfs_rq->runtime_enabled) 3023 return; 3024 3025 __account_cfs_rq_runtime(cfs_rq, delta_exec); 3026 } 3027 3028 static inline int cfs_rq_throttled(struct cfs_rq *cfs_rq) 3029 { 3030 return cfs_bandwidth_used() && cfs_rq->throttled; 3031 } 3032 3033 /* check whether cfs_rq, or any parent, is throttled */ 3034 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq) 3035 { 3036 return cfs_bandwidth_used() && cfs_rq->throttle_count; 3037 } 3038 3039 /* 3040 * Ensure that neither of the group entities corresponding to src_cpu or 3041 * dest_cpu are members of a throttled hierarchy when performing group 3042 * load-balance operations. 3043 */ 3044 static inline int throttled_lb_pair(struct task_group *tg, 3045 int src_cpu, int dest_cpu) 3046 { 3047 struct cfs_rq *src_cfs_rq, *dest_cfs_rq; 3048 3049 src_cfs_rq = tg->cfs_rq[src_cpu]; 3050 dest_cfs_rq = tg->cfs_rq[dest_cpu]; 3051 3052 return throttled_hierarchy(src_cfs_rq) || 3053 throttled_hierarchy(dest_cfs_rq); 3054 } 3055 3056 /* updated child weight may affect parent so we have to do this bottom up */ 3057 static int tg_unthrottle_up(struct task_group *tg, void *data) 3058 { 3059 struct rq *rq = data; 3060 struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)]; 3061 3062 cfs_rq->throttle_count--; 3063 #ifdef CONFIG_SMP 3064 if (!cfs_rq->throttle_count) { 3065 /* adjust cfs_rq_clock_task() */ 3066 cfs_rq->throttled_clock_task_time += rq_clock_task(rq) - 3067 cfs_rq->throttled_clock_task; 3068 } 3069 #endif 3070 3071 return 0; 3072 } 3073 3074 static int tg_throttle_down(struct task_group *tg, void *data) 3075 { 3076 struct rq *rq = data; 3077 struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)]; 3078 3079 /* group is entering throttled state, stop time */ 3080 if (!cfs_rq->throttle_count) 3081 cfs_rq->throttled_clock_task = rq_clock_task(rq); 3082 cfs_rq->throttle_count++; 3083 3084 return 0; 3085 } 3086 3087 static void throttle_cfs_rq(struct cfs_rq *cfs_rq) 3088 { 3089 struct rq *rq = rq_of(cfs_rq); 3090 struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg); 3091 struct sched_entity *se; 3092 long task_delta, dequeue = 1; 3093 3094 se = cfs_rq->tg->se[cpu_of(rq_of(cfs_rq))]; 3095 3096 /* freeze hierarchy runnable averages while throttled */ 3097 rcu_read_lock(); 3098 walk_tg_tree_from(cfs_rq->tg, tg_throttle_down, tg_nop, (void *)rq); 3099 rcu_read_unlock(); 3100 3101 task_delta = cfs_rq->h_nr_running; 3102 for_each_sched_entity(se) { 3103 struct cfs_rq *qcfs_rq = cfs_rq_of(se); 3104 /* throttled entity or throttle-on-deactivate */ 3105 if (!se->on_rq) 3106 break; 3107 3108 if (dequeue) 3109 dequeue_entity(qcfs_rq, se, DEQUEUE_SLEEP); 3110 qcfs_rq->h_nr_running -= task_delta; 3111 3112 if (qcfs_rq->load.weight) 3113 dequeue = 0; 3114 } 3115 3116 if (!se) 3117 rq->nr_running -= task_delta; 3118 3119 cfs_rq->throttled = 1; 3120 cfs_rq->throttled_clock = rq_clock(rq); 3121 raw_spin_lock(&cfs_b->lock); 3122 list_add_tail_rcu(&cfs_rq->throttled_list, &cfs_b->throttled_cfs_rq); 3123 if (!cfs_b->timer_active) 3124 __start_cfs_bandwidth(cfs_b); 3125 raw_spin_unlock(&cfs_b->lock); 3126 } 3127 3128 void unthrottle_cfs_rq(struct cfs_rq *cfs_rq) 3129 { 3130 struct rq *rq = rq_of(cfs_rq); 3131 struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg); 3132 struct sched_entity *se; 3133 int enqueue = 1; 3134 long task_delta; 3135 3136 se = cfs_rq->tg->se[cpu_of(rq)]; 3137 3138 cfs_rq->throttled = 0; 3139 3140 update_rq_clock(rq); 3141 3142 raw_spin_lock(&cfs_b->lock); 3143 cfs_b->throttled_time += rq_clock(rq) - cfs_rq->throttled_clock; 3144 list_del_rcu(&cfs_rq->throttled_list); 3145 raw_spin_unlock(&cfs_b->lock); 3146 3147 /* update hierarchical throttle state */ 3148 walk_tg_tree_from(cfs_rq->tg, tg_nop, tg_unthrottle_up, (void *)rq); 3149 3150 if (!cfs_rq->load.weight) 3151 return; 3152 3153 task_delta = cfs_rq->h_nr_running; 3154 for_each_sched_entity(se) { 3155 if (se->on_rq) 3156 enqueue = 0; 3157 3158 cfs_rq = cfs_rq_of(se); 3159 if (enqueue) 3160 enqueue_entity(cfs_rq, se, ENQUEUE_WAKEUP); 3161 cfs_rq->h_nr_running += task_delta; 3162 3163 if (cfs_rq_throttled(cfs_rq)) 3164 break; 3165 } 3166 3167 if (!se) 3168 rq->nr_running += task_delta; 3169 3170 /* determine whether we need to wake up potentially idle cpu */ 3171 if (rq->curr == rq->idle && rq->cfs.nr_running) 3172 resched_task(rq->curr); 3173 } 3174 3175 static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b, 3176 u64 remaining, u64 expires) 3177 { 3178 struct cfs_rq *cfs_rq; 3179 u64 runtime = remaining; 3180 3181 rcu_read_lock(); 3182 list_for_each_entry_rcu(cfs_rq, &cfs_b->throttled_cfs_rq, 3183 throttled_list) { 3184 struct rq *rq = rq_of(cfs_rq); 3185 3186 raw_spin_lock(&rq->lock); 3187 if (!cfs_rq_throttled(cfs_rq)) 3188 goto next; 3189 3190 runtime = -cfs_rq->runtime_remaining + 1; 3191 if (runtime > remaining) 3192 runtime = remaining; 3193 remaining -= runtime; 3194 3195 cfs_rq->runtime_remaining += runtime; 3196 cfs_rq->runtime_expires = expires; 3197 3198 /* we check whether we're throttled above */ 3199 if (cfs_rq->runtime_remaining > 0) 3200 unthrottle_cfs_rq(cfs_rq); 3201 3202 next: 3203 raw_spin_unlock(&rq->lock); 3204 3205 if (!remaining) 3206 break; 3207 } 3208 rcu_read_unlock(); 3209 3210 return remaining; 3211 } 3212 3213 /* 3214 * Responsible for refilling a task_group's bandwidth and unthrottling its 3215 * cfs_rqs as appropriate. If there has been no activity within the last 3216 * period the timer is deactivated until scheduling resumes; cfs_b->idle is 3217 * used to track this state. 3218 */ 3219 static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun) 3220 { 3221 u64 runtime, runtime_expires; 3222 int idle = 1, throttled; 3223 3224 raw_spin_lock(&cfs_b->lock); 3225 /* no need to continue the timer with no bandwidth constraint */ 3226 if (cfs_b->quota == RUNTIME_INF) 3227 goto out_unlock; 3228 3229 throttled = !list_empty(&cfs_b->throttled_cfs_rq); 3230 /* idle depends on !throttled (for the case of a large deficit) */ 3231 idle = cfs_b->idle && !throttled; 3232 cfs_b->nr_periods += overrun; 3233 3234 /* if we're going inactive then everything else can be deferred */ 3235 if (idle) 3236 goto out_unlock; 3237 3238 /* 3239 * if we have relooped after returning idle once, we need to update our 3240 * status as actually running, so that other cpus doing 3241 * __start_cfs_bandwidth will stop trying to cancel us. 3242 */ 3243 cfs_b->timer_active = 1; 3244 3245 __refill_cfs_bandwidth_runtime(cfs_b); 3246 3247 if (!throttled) { 3248 /* mark as potentially idle for the upcoming period */ 3249 cfs_b->idle = 1; 3250 goto out_unlock; 3251 } 3252 3253 /* account preceding periods in which throttling occurred */ 3254 cfs_b->nr_throttled += overrun; 3255 3256 /* 3257 * There are throttled entities so we must first use the new bandwidth 3258 * to unthrottle them before making it generally available. This 3259 * ensures that all existing debts will be paid before a new cfs_rq is 3260 * allowed to run. 3261 */ 3262 runtime = cfs_b->runtime; 3263 runtime_expires = cfs_b->runtime_expires; 3264 cfs_b->runtime = 0; 3265 3266 /* 3267 * This check is repeated as we are holding onto the new bandwidth 3268 * while we unthrottle. This can potentially race with an unthrottled 3269 * group trying to acquire new bandwidth from the global pool. 3270 */ 3271 while (throttled && runtime > 0) { 3272 raw_spin_unlock(&cfs_b->lock); 3273 /* we can't nest cfs_b->lock while distributing bandwidth */ 3274 runtime = distribute_cfs_runtime(cfs_b, runtime, 3275 runtime_expires); 3276 raw_spin_lock(&cfs_b->lock); 3277 3278 throttled = !list_empty(&cfs_b->throttled_cfs_rq); 3279 } 3280 3281 /* return (any) remaining runtime */ 3282 cfs_b->runtime = runtime; 3283 /* 3284 * While we are ensured activity in the period following an 3285 * unthrottle, this also covers the case in which the new bandwidth is 3286 * insufficient to cover the existing bandwidth deficit. (Forcing the 3287 * timer to remain active while there are any throttled entities.) 3288 */ 3289 cfs_b->idle = 0; 3290 out_unlock: 3291 if (idle) 3292 cfs_b->timer_active = 0; 3293 raw_spin_unlock(&cfs_b->lock); 3294 3295 return idle; 3296 } 3297 3298 /* a cfs_rq won't donate quota below this amount */ 3299 static const u64 min_cfs_rq_runtime = 1 * NSEC_PER_MSEC; 3300 /* minimum remaining period time to redistribute slack quota */ 3301 static const u64 min_bandwidth_expiration = 2 * NSEC_PER_MSEC; 3302 /* how long we wait to gather additional slack before distributing */ 3303 static const u64 cfs_bandwidth_slack_period = 5 * NSEC_PER_MSEC; 3304 3305 /* 3306 * Are we near the end of the current quota period? 3307 * 3308 * Requires cfs_b->lock for hrtimer_expires_remaining to be safe against the 3309 * hrtimer base being cleared by __hrtimer_start_range_ns. In the case of 3310 * migrate_hrtimers, base is never cleared, so we are fine. 3311 */ 3312 static int runtime_refresh_within(struct cfs_bandwidth *cfs_b, u64 min_expire) 3313 { 3314 struct hrtimer *refresh_timer = &cfs_b->period_timer; 3315 u64 remaining; 3316 3317 /* if the call-back is running a quota refresh is already occurring */ 3318 if (hrtimer_callback_running(refresh_timer)) 3319 return 1; 3320 3321 /* is a quota refresh about to occur? */ 3322 remaining = ktime_to_ns(hrtimer_expires_remaining(refresh_timer)); 3323 if (remaining < min_expire) 3324 return 1; 3325 3326 return 0; 3327 } 3328 3329 static void start_cfs_slack_bandwidth(struct cfs_bandwidth *cfs_b) 3330 { 3331 u64 min_left = cfs_bandwidth_slack_period + min_bandwidth_expiration; 3332 3333 /* if there's a quota refresh soon don't bother with slack */ 3334 if (runtime_refresh_within(cfs_b, min_left)) 3335 return; 3336 3337 start_bandwidth_timer(&cfs_b->slack_timer, 3338 ns_to_ktime(cfs_bandwidth_slack_period)); 3339 } 3340 3341 /* we know any runtime found here is valid as update_curr() precedes return */ 3342 static void __return_cfs_rq_runtime(struct cfs_rq *cfs_rq) 3343 { 3344 struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg); 3345 s64 slack_runtime = cfs_rq->runtime_remaining - min_cfs_rq_runtime; 3346 3347 if (slack_runtime <= 0) 3348 return; 3349 3350 raw_spin_lock(&cfs_b->lock); 3351 if (cfs_b->quota != RUNTIME_INF && 3352 cfs_rq->runtime_expires == cfs_b->runtime_expires) { 3353 cfs_b->runtime += slack_runtime; 3354 3355 /* we are under rq->lock, defer unthrottling using a timer */ 3356 if (cfs_b->runtime > sched_cfs_bandwidth_slice() && 3357 !list_empty(&cfs_b->throttled_cfs_rq)) 3358 start_cfs_slack_bandwidth(cfs_b); 3359 } 3360 raw_spin_unlock(&cfs_b->lock); 3361 3362 /* even if it's not valid for return we don't want to try again */ 3363 cfs_rq->runtime_remaining -= slack_runtime; 3364 } 3365 3366 static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq) 3367 { 3368 if (!cfs_bandwidth_used()) 3369 return; 3370 3371 if (!cfs_rq->runtime_enabled || cfs_rq->nr_running) 3372 return; 3373 3374 __return_cfs_rq_runtime(cfs_rq); 3375 } 3376 3377 /* 3378 * This is done with a timer (instead of inline with bandwidth return) since 3379 * it's necessary to juggle rq->locks to unthrottle their respective cfs_rqs. 3380 */ 3381 static void do_sched_cfs_slack_timer(struct cfs_bandwidth *cfs_b) 3382 { 3383 u64 runtime = 0, slice = sched_cfs_bandwidth_slice(); 3384 u64 expires; 3385 3386 /* confirm we're still not at a refresh boundary */ 3387 raw_spin_lock(&cfs_b->lock); 3388 if (runtime_refresh_within(cfs_b, min_bandwidth_expiration)) { 3389 raw_spin_unlock(&cfs_b->lock); 3390 return; 3391 } 3392 3393 if (cfs_b->quota != RUNTIME_INF && cfs_b->runtime > slice) { 3394 runtime = cfs_b->runtime; 3395 cfs_b->runtime = 0; 3396 } 3397 expires = cfs_b->runtime_expires; 3398 raw_spin_unlock(&cfs_b->lock); 3399 3400 if (!runtime) 3401 return; 3402 3403 runtime = distribute_cfs_runtime(cfs_b, runtime, expires); 3404 3405 raw_spin_lock(&cfs_b->lock); 3406 if (expires == cfs_b->runtime_expires) 3407 cfs_b->runtime = runtime; 3408 raw_spin_unlock(&cfs_b->lock); 3409 } 3410 3411 /* 3412 * When a group wakes up we want to make sure that its quota is not already 3413 * expired/exceeded, otherwise it may be allowed to steal additional ticks of 3414 * runtime as update_curr() throttling can not not trigger until it's on-rq. 3415 */ 3416 static void check_enqueue_throttle(struct cfs_rq *cfs_rq) 3417 { 3418 if (!cfs_bandwidth_used()) 3419 return; 3420 3421 /* an active group must be handled by the update_curr()->put() path */ 3422 if (!cfs_rq->runtime_enabled || cfs_rq->curr) 3423 return; 3424 3425 /* ensure the group is not already throttled */ 3426 if (cfs_rq_throttled(cfs_rq)) 3427 return; 3428 3429 /* update runtime allocation */ 3430 account_cfs_rq_runtime(cfs_rq, 0); 3431 if (cfs_rq->runtime_remaining <= 0) 3432 throttle_cfs_rq(cfs_rq); 3433 } 3434 3435 /* conditionally throttle active cfs_rq's from put_prev_entity() */ 3436 static void check_cfs_rq_runtime(struct cfs_rq *cfs_rq) 3437 { 3438 if (!cfs_bandwidth_used()) 3439 return; 3440 3441 if (likely(!cfs_rq->runtime_enabled || cfs_rq->runtime_remaining > 0)) 3442 return; 3443 3444 /* 3445 * it's possible for a throttled entity to be forced into a running 3446 * state (e.g. set_curr_task), in this case we're finished. 3447 */ 3448 if (cfs_rq_throttled(cfs_rq)) 3449 return; 3450 3451 throttle_cfs_rq(cfs_rq); 3452 } 3453 3454 static enum hrtimer_restart sched_cfs_slack_timer(struct hrtimer *timer) 3455 { 3456 struct cfs_bandwidth *cfs_b = 3457 container_of(timer, struct cfs_bandwidth, slack_timer); 3458 do_sched_cfs_slack_timer(cfs_b); 3459 3460 return HRTIMER_NORESTART; 3461 } 3462 3463 static enum hrtimer_restart sched_cfs_period_timer(struct hrtimer *timer) 3464 { 3465 struct cfs_bandwidth *cfs_b = 3466 container_of(timer, struct cfs_bandwidth, period_timer); 3467 ktime_t now; 3468 int overrun; 3469 int idle = 0; 3470 3471 for (;;) { 3472 now = hrtimer_cb_get_time(timer); 3473 overrun = hrtimer_forward(timer, now, cfs_b->period); 3474 3475 if (!overrun) 3476 break; 3477 3478 idle = do_sched_cfs_period_timer(cfs_b, overrun); 3479 } 3480 3481 return idle ? HRTIMER_NORESTART : HRTIMER_RESTART; 3482 } 3483 3484 void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b) 3485 { 3486 raw_spin_lock_init(&cfs_b->lock); 3487 cfs_b->runtime = 0; 3488 cfs_b->quota = RUNTIME_INF; 3489 cfs_b->period = ns_to_ktime(default_cfs_period()); 3490 3491 INIT_LIST_HEAD(&cfs_b->throttled_cfs_rq); 3492 hrtimer_init(&cfs_b->period_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL); 3493 cfs_b->period_timer.function = sched_cfs_period_timer; 3494 hrtimer_init(&cfs_b->slack_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL); 3495 cfs_b->slack_timer.function = sched_cfs_slack_timer; 3496 } 3497 3498 static void init_cfs_rq_runtime(struct cfs_rq *cfs_rq) 3499 { 3500 cfs_rq->runtime_enabled = 0; 3501 INIT_LIST_HEAD(&cfs_rq->throttled_list); 3502 } 3503 3504 /* requires cfs_b->lock, may release to reprogram timer */ 3505 void __start_cfs_bandwidth(struct cfs_bandwidth *cfs_b) 3506 { 3507 /* 3508 * The timer may be active because we're trying to set a new bandwidth 3509 * period or because we're racing with the tear-down path 3510 * (timer_active==0 becomes visible before the hrtimer call-back 3511 * terminates). In either case we ensure that it's re-programmed 3512 */ 3513 while (unlikely(hrtimer_active(&cfs_b->period_timer)) && 3514 hrtimer_try_to_cancel(&cfs_b->period_timer) < 0) { 3515 /* bounce the lock to allow do_sched_cfs_period_timer to run */ 3516 raw_spin_unlock(&cfs_b->lock); 3517 cpu_relax(); 3518 raw_spin_lock(&cfs_b->lock); 3519 /* if someone else restarted the timer then we're done */ 3520 if (cfs_b->timer_active) 3521 return; 3522 } 3523 3524 cfs_b->timer_active = 1; 3525 start_bandwidth_timer(&cfs_b->period_timer, cfs_b->period); 3526 } 3527 3528 static void destroy_cfs_bandwidth(struct cfs_bandwidth *cfs_b) 3529 { 3530 hrtimer_cancel(&cfs_b->period_timer); 3531 hrtimer_cancel(&cfs_b->slack_timer); 3532 } 3533 3534 static void __maybe_unused unthrottle_offline_cfs_rqs(struct rq *rq) 3535 { 3536 struct cfs_rq *cfs_rq; 3537 3538 for_each_leaf_cfs_rq(rq, cfs_rq) { 3539 struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg); 3540 3541 if (!cfs_rq->runtime_enabled) 3542 continue; 3543 3544 /* 3545 * clock_task is not advancing so we just need to make sure 3546 * there's some valid quota amount 3547 */ 3548 cfs_rq->runtime_remaining = cfs_b->quota; 3549 if (cfs_rq_throttled(cfs_rq)) 3550 unthrottle_cfs_rq(cfs_rq); 3551 } 3552 } 3553 3554 #else /* CONFIG_CFS_BANDWIDTH */ 3555 static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq) 3556 { 3557 return rq_clock_task(rq_of(cfs_rq)); 3558 } 3559 3560 static void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec) {} 3561 static void check_cfs_rq_runtime(struct cfs_rq *cfs_rq) {} 3562 static void check_enqueue_throttle(struct cfs_rq *cfs_rq) {} 3563 static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq) {} 3564 3565 static inline int cfs_rq_throttled(struct cfs_rq *cfs_rq) 3566 { 3567 return 0; 3568 } 3569 3570 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq) 3571 { 3572 return 0; 3573 } 3574 3575 static inline int throttled_lb_pair(struct task_group *tg, 3576 int src_cpu, int dest_cpu) 3577 { 3578 return 0; 3579 } 3580 3581 void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b) {} 3582 3583 #ifdef CONFIG_FAIR_GROUP_SCHED 3584 static void init_cfs_rq_runtime(struct cfs_rq *cfs_rq) {} 3585 #endif 3586 3587 static inline struct cfs_bandwidth *tg_cfs_bandwidth(struct task_group *tg) 3588 { 3589 return NULL; 3590 } 3591 static inline void destroy_cfs_bandwidth(struct cfs_bandwidth *cfs_b) {} 3592 static inline void unthrottle_offline_cfs_rqs(struct rq *rq) {} 3593 3594 #endif /* CONFIG_CFS_BANDWIDTH */ 3595 3596 /************************************************** 3597 * CFS operations on tasks: 3598 */ 3599 3600 #ifdef CONFIG_SCHED_HRTICK 3601 static void hrtick_start_fair(struct rq *rq, struct task_struct *p) 3602 { 3603 struct sched_entity *se = &p->se; 3604 struct cfs_rq *cfs_rq = cfs_rq_of(se); 3605 3606 WARN_ON(task_rq(p) != rq); 3607 3608 if (cfs_rq->nr_running > 1) { 3609 u64 slice = sched_slice(cfs_rq, se); 3610 u64 ran = se->sum_exec_runtime - se->prev_sum_exec_runtime; 3611 s64 delta = slice - ran; 3612 3613 if (delta < 0) { 3614 if (rq->curr == p) 3615 resched_task(p); 3616 return; 3617 } 3618 3619 /* 3620 * Don't schedule slices shorter than 10000ns, that just 3621 * doesn't make sense. Rely on vruntime for fairness. 3622 */ 3623 if (rq->curr != p) 3624 delta = max_t(s64, 10000LL, delta); 3625 3626 hrtick_start(rq, delta); 3627 } 3628 } 3629 3630 /* 3631 * called from enqueue/dequeue and updates the hrtick when the 3632 * current task is from our class and nr_running is low enough 3633 * to matter. 3634 */ 3635 static void hrtick_update(struct rq *rq) 3636 { 3637 struct task_struct *curr = rq->curr; 3638 3639 if (!hrtick_enabled(rq) || curr->sched_class != &fair_sched_class) 3640 return; 3641 3642 if (cfs_rq_of(&curr->se)->nr_running < sched_nr_latency) 3643 hrtick_start_fair(rq, curr); 3644 } 3645 #else /* !CONFIG_SCHED_HRTICK */ 3646 static inline void 3647 hrtick_start_fair(struct rq *rq, struct task_struct *p) 3648 { 3649 } 3650 3651 static inline void hrtick_update(struct rq *rq) 3652 { 3653 } 3654 #endif 3655 3656 /* 3657 * The enqueue_task method is called before nr_running is 3658 * increased. Here we update the fair scheduling stats and 3659 * then put the task into the rbtree: 3660 */ 3661 static void 3662 enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags) 3663 { 3664 struct cfs_rq *cfs_rq; 3665 struct sched_entity *se = &p->se; 3666 3667 for_each_sched_entity(se) { 3668 if (se->on_rq) 3669 break; 3670 cfs_rq = cfs_rq_of(se); 3671 enqueue_entity(cfs_rq, se, flags); 3672 3673 /* 3674 * end evaluation on encountering a throttled cfs_rq 3675 * 3676 * note: in the case of encountering a throttled cfs_rq we will 3677 * post the final h_nr_running increment below. 3678 */ 3679 if (cfs_rq_throttled(cfs_rq)) 3680 break; 3681 cfs_rq->h_nr_running++; 3682 3683 flags = ENQUEUE_WAKEUP; 3684 } 3685 3686 for_each_sched_entity(se) { 3687 cfs_rq = cfs_rq_of(se); 3688 cfs_rq->h_nr_running++; 3689 3690 if (cfs_rq_throttled(cfs_rq)) 3691 break; 3692 3693 update_cfs_shares(cfs_rq); 3694 update_entity_load_avg(se, 1); 3695 } 3696 3697 if (!se) { 3698 update_rq_runnable_avg(rq, rq->nr_running); 3699 inc_nr_running(rq); 3700 } 3701 hrtick_update(rq); 3702 } 3703 3704 static void set_next_buddy(struct sched_entity *se); 3705 3706 /* 3707 * The dequeue_task method is called before nr_running is 3708 * decreased. We remove the task from the rbtree and 3709 * update the fair scheduling stats: 3710 */ 3711 static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags) 3712 { 3713 struct cfs_rq *cfs_rq; 3714 struct sched_entity *se = &p->se; 3715 int task_sleep = flags & DEQUEUE_SLEEP; 3716 3717 for_each_sched_entity(se) { 3718 cfs_rq = cfs_rq_of(se); 3719 dequeue_entity(cfs_rq, se, flags); 3720 3721 /* 3722 * end evaluation on encountering a throttled cfs_rq 3723 * 3724 * note: in the case of encountering a throttled cfs_rq we will 3725 * post the final h_nr_running decrement below. 3726 */ 3727 if (cfs_rq_throttled(cfs_rq)) 3728 break; 3729 cfs_rq->h_nr_running--; 3730 3731 /* Don't dequeue parent if it has other entities besides us */ 3732 if (cfs_rq->load.weight) { 3733 /* 3734 * Bias pick_next to pick a task from this cfs_rq, as 3735 * p is sleeping when it is within its sched_slice. 3736 */ 3737 if (task_sleep && parent_entity(se)) 3738 set_next_buddy(parent_entity(se)); 3739 3740 /* avoid re-evaluating load for this entity */ 3741 se = parent_entity(se); 3742 break; 3743 } 3744 flags |= DEQUEUE_SLEEP; 3745 } 3746 3747 for_each_sched_entity(se) { 3748 cfs_rq = cfs_rq_of(se); 3749 cfs_rq->h_nr_running--; 3750 3751 if (cfs_rq_throttled(cfs_rq)) 3752 break; 3753 3754 update_cfs_shares(cfs_rq); 3755 update_entity_load_avg(se, 1); 3756 } 3757 3758 if (!se) { 3759 dec_nr_running(rq); 3760 update_rq_runnable_avg(rq, 1); 3761 } 3762 hrtick_update(rq); 3763 } 3764 3765 #ifdef CONFIG_SMP 3766 /* Used instead of source_load when we know the type == 0 */ 3767 static unsigned long weighted_cpuload(const int cpu) 3768 { 3769 return cpu_rq(cpu)->cfs.runnable_load_avg; 3770 } 3771 3772 /* 3773 * Return a low guess at the load of a migration-source cpu weighted 3774 * according to the scheduling class and "nice" value. 3775 * 3776 * We want to under-estimate the load of migration sources, to 3777 * balance conservatively. 3778 */ 3779 static unsigned long source_load(int cpu, int type) 3780 { 3781 struct rq *rq = cpu_rq(cpu); 3782 unsigned long total = weighted_cpuload(cpu); 3783 3784 if (type == 0 || !sched_feat(LB_BIAS)) 3785 return total; 3786 3787 return min(rq->cpu_load[type-1], total); 3788 } 3789 3790 /* 3791 * Return a high guess at the load of a migration-target cpu weighted 3792 * according to the scheduling class and "nice" value. 3793 */ 3794 static unsigned long target_load(int cpu, int type) 3795 { 3796 struct rq *rq = cpu_rq(cpu); 3797 unsigned long total = weighted_cpuload(cpu); 3798 3799 if (type == 0 || !sched_feat(LB_BIAS)) 3800 return total; 3801 3802 return max(rq->cpu_load[type-1], total); 3803 } 3804 3805 static unsigned long power_of(int cpu) 3806 { 3807 return cpu_rq(cpu)->cpu_power; 3808 } 3809 3810 static unsigned long cpu_avg_load_per_task(int cpu) 3811 { 3812 struct rq *rq = cpu_rq(cpu); 3813 unsigned long nr_running = ACCESS_ONCE(rq->nr_running); 3814 unsigned long load_avg = rq->cfs.runnable_load_avg; 3815 3816 if (nr_running) 3817 return load_avg / nr_running; 3818 3819 return 0; 3820 } 3821 3822 static void record_wakee(struct task_struct *p) 3823 { 3824 /* 3825 * Rough decay (wiping) for cost saving, don't worry 3826 * about the boundary, really active task won't care 3827 * about the loss. 3828 */ 3829 if (jiffies > current->wakee_flip_decay_ts + HZ) { 3830 current->wakee_flips = 0; 3831 current->wakee_flip_decay_ts = jiffies; 3832 } 3833 3834 if (current->last_wakee != p) { 3835 current->last_wakee = p; 3836 current->wakee_flips++; 3837 } 3838 } 3839 3840 static void task_waking_fair(struct task_struct *p) 3841 { 3842 struct sched_entity *se = &p->se; 3843 struct cfs_rq *cfs_rq = cfs_rq_of(se); 3844 u64 min_vruntime; 3845 3846 #ifndef CONFIG_64BIT 3847 u64 min_vruntime_copy; 3848 3849 do { 3850 min_vruntime_copy = cfs_rq->min_vruntime_copy; 3851 smp_rmb(); 3852 min_vruntime = cfs_rq->min_vruntime; 3853 } while (min_vruntime != min_vruntime_copy); 3854 #else 3855 min_vruntime = cfs_rq->min_vruntime; 3856 #endif 3857 3858 se->vruntime -= min_vruntime; 3859 record_wakee(p); 3860 } 3861 3862 #ifdef CONFIG_FAIR_GROUP_SCHED 3863 /* 3864 * effective_load() calculates the load change as seen from the root_task_group 3865 * 3866 * Adding load to a group doesn't make a group heavier, but can cause movement 3867 * of group shares between cpus. Assuming the shares were perfectly aligned one 3868 * can calculate the shift in shares. 3869 * 3870 * Calculate the effective load difference if @wl is added (subtracted) to @tg 3871 * on this @cpu and results in a total addition (subtraction) of @wg to the 3872 * total group weight. 3873 * 3874 * Given a runqueue weight distribution (rw_i) we can compute a shares 3875 * distribution (s_i) using: 3876 * 3877 * s_i = rw_i / \Sum rw_j (1) 3878 * 3879 * Suppose we have 4 CPUs and our @tg is a direct child of the root group and 3880 * has 7 equal weight tasks, distributed as below (rw_i), with the resulting 3881 * shares distribution (s_i): 3882 * 3883 * rw_i = { 2, 4, 1, 0 } 3884 * s_i = { 2/7, 4/7, 1/7, 0 } 3885 * 3886 * As per wake_affine() we're interested in the load of two CPUs (the CPU the 3887 * task used to run on and the CPU the waker is running on), we need to 3888 * compute the effect of waking a task on either CPU and, in case of a sync 3889 * wakeup, compute the effect of the current task going to sleep. 3890 * 3891 * So for a change of @wl to the local @cpu with an overall group weight change 3892 * of @wl we can compute the new shares distribution (s'_i) using: 3893 * 3894 * s'_i = (rw_i + @wl) / (@wg + \Sum rw_j) (2) 3895 * 3896 * Suppose we're interested in CPUs 0 and 1, and want to compute the load 3897 * differences in waking a task to CPU 0. The additional task changes the 3898 * weight and shares distributions like: 3899 * 3900 * rw'_i = { 3, 4, 1, 0 } 3901 * s'_i = { 3/8, 4/8, 1/8, 0 } 3902 * 3903 * We can then compute the difference in effective weight by using: 3904 * 3905 * dw_i = S * (s'_i - s_i) (3) 3906 * 3907 * Where 'S' is the group weight as seen by its parent. 3908 * 3909 * Therefore the effective change in loads on CPU 0 would be 5/56 (3/8 - 2/7) 3910 * times the weight of the group. The effect on CPU 1 would be -4/56 (4/8 - 3911 * 4/7) times the weight of the group. 3912 */ 3913 static long effective_load(struct task_group *tg, int cpu, long wl, long wg) 3914 { 3915 struct sched_entity *se = tg->se[cpu]; 3916 3917 if (!tg->parent) /* the trivial, non-cgroup case */ 3918 return wl; 3919 3920 for_each_sched_entity(se) { 3921 long w, W; 3922 3923 tg = se->my_q->tg; 3924 3925 /* 3926 * W = @wg + \Sum rw_j 3927 */ 3928 W = wg + calc_tg_weight(tg, se->my_q); 3929 3930 /* 3931 * w = rw_i + @wl 3932 */ 3933 w = se->my_q->load.weight + wl; 3934 3935 /* 3936 * wl = S * s'_i; see (2) 3937 */ 3938 if (W > 0 && w < W) 3939 wl = (w * tg->shares) / W; 3940 else 3941 wl = tg->shares; 3942 3943 /* 3944 * Per the above, wl is the new se->load.weight value; since 3945 * those are clipped to [MIN_SHARES, ...) do so now. See 3946 * calc_cfs_shares(). 3947 */ 3948 if (wl < MIN_SHARES) 3949 wl = MIN_SHARES; 3950 3951 /* 3952 * wl = dw_i = S * (s'_i - s_i); see (3) 3953 */ 3954 wl -= se->load.weight; 3955 3956 /* 3957 * Recursively apply this logic to all parent groups to compute 3958 * the final effective load change on the root group. Since 3959 * only the @tg group gets extra weight, all parent groups can 3960 * only redistribute existing shares. @wl is the shift in shares 3961 * resulting from this level per the above. 3962 */ 3963 wg = 0; 3964 } 3965 3966 return wl; 3967 } 3968 #else 3969 3970 static long effective_load(struct task_group *tg, int cpu, long wl, long wg) 3971 { 3972 return wl; 3973 } 3974 3975 #endif 3976 3977 static int wake_wide(struct task_struct *p) 3978 { 3979 int factor = this_cpu_read(sd_llc_size); 3980 3981 /* 3982 * Yeah, it's the switching-frequency, could means many wakee or 3983 * rapidly switch, use factor here will just help to automatically 3984 * adjust the loose-degree, so bigger node will lead to more pull. 3985 */ 3986 if (p->wakee_flips > factor) { 3987 /* 3988 * wakee is somewhat hot, it needs certain amount of cpu 3989 * resource, so if waker is far more hot, prefer to leave 3990 * it alone. 3991 */ 3992 if (current->wakee_flips > (factor * p->wakee_flips)) 3993 return 1; 3994 } 3995 3996 return 0; 3997 } 3998 3999 static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync) 4000 { 4001 s64 this_load, load; 4002 int idx, this_cpu, prev_cpu; 4003 unsigned long tl_per_task; 4004 struct task_group *tg; 4005 unsigned long weight; 4006 int balanced; 4007 4008 /* 4009 * If we wake multiple tasks be careful to not bounce 4010 * ourselves around too much. 4011 */ 4012 if (wake_wide(p)) 4013 return 0; 4014 4015 idx = sd->wake_idx; 4016 this_cpu = smp_processor_id(); 4017 prev_cpu = task_cpu(p); 4018 load = source_load(prev_cpu, idx); 4019 this_load = target_load(this_cpu, idx); 4020 4021 /* 4022 * If sync wakeup then subtract the (maximum possible) 4023 * effect of the currently running task from the load 4024 * of the current CPU: 4025 */ 4026 if (sync) { 4027 tg = task_group(current); 4028 weight = current->se.load.weight; 4029 4030 this_load += effective_load(tg, this_cpu, -weight, -weight); 4031 load += effective_load(tg, prev_cpu, 0, -weight); 4032 } 4033 4034 tg = task_group(p); 4035 weight = p->se.load.weight; 4036 4037 /* 4038 * In low-load situations, where prev_cpu is idle and this_cpu is idle 4039 * due to the sync cause above having dropped this_load to 0, we'll 4040 * always have an imbalance, but there's really nothing you can do 4041 * about that, so that's good too. 4042 * 4043 * Otherwise check if either cpus are near enough in load to allow this 4044 * task to be woken on this_cpu. 4045 */ 4046 if (this_load > 0) { 4047 s64 this_eff_load, prev_eff_load; 4048 4049 this_eff_load = 100; 4050 this_eff_load *= power_of(prev_cpu); 4051 this_eff_load *= this_load + 4052 effective_load(tg, this_cpu, weight, weight); 4053 4054 prev_eff_load = 100 + (sd->imbalance_pct - 100) / 2; 4055 prev_eff_load *= power_of(this_cpu); 4056 prev_eff_load *= load + effective_load(tg, prev_cpu, 0, weight); 4057 4058 balanced = this_eff_load <= prev_eff_load; 4059 } else 4060 balanced = true; 4061 4062 /* 4063 * If the currently running task will sleep within 4064 * a reasonable amount of time then attract this newly 4065 * woken task: 4066 */ 4067 if (sync && balanced) 4068 return 1; 4069 4070 schedstat_inc(p, se.statistics.nr_wakeups_affine_attempts); 4071 tl_per_task = cpu_avg_load_per_task(this_cpu); 4072 4073 if (balanced || 4074 (this_load <= load && 4075 this_load + target_load(prev_cpu, idx) <= tl_per_task)) { 4076 /* 4077 * This domain has SD_WAKE_AFFINE and 4078 * p is cache cold in this domain, and 4079 * there is no bad imbalance. 4080 */ 4081 schedstat_inc(sd, ttwu_move_affine); 4082 schedstat_inc(p, se.statistics.nr_wakeups_affine); 4083 4084 return 1; 4085 } 4086 return 0; 4087 } 4088 4089 /* 4090 * find_idlest_group finds and returns the least busy CPU group within the 4091 * domain. 4092 */ 4093 static struct sched_group * 4094 find_idlest_group(struct sched_domain *sd, struct task_struct *p, 4095 int this_cpu, int sd_flag) 4096 { 4097 struct sched_group *idlest = NULL, *group = sd->groups; 4098 unsigned long min_load = ULONG_MAX, this_load = 0; 4099 int load_idx = sd->forkexec_idx; 4100 int imbalance = 100 + (sd->imbalance_pct-100)/2; 4101 4102 if (sd_flag & SD_BALANCE_WAKE) 4103 load_idx = sd->wake_idx; 4104 4105 do { 4106 unsigned long load, avg_load; 4107 int local_group; 4108 int i; 4109 4110 /* Skip over this group if it has no CPUs allowed */ 4111 if (!cpumask_intersects(sched_group_cpus(group), 4112 tsk_cpus_allowed(p))) 4113 continue; 4114 4115 local_group = cpumask_test_cpu(this_cpu, 4116 sched_group_cpus(group)); 4117 4118 /* Tally up the load of all CPUs in the group */ 4119 avg_load = 0; 4120 4121 for_each_cpu(i, sched_group_cpus(group)) { 4122 /* Bias balancing toward cpus of our domain */ 4123 if (local_group) 4124 load = source_load(i, load_idx); 4125 else 4126 load = target_load(i, load_idx); 4127 4128 avg_load += load; 4129 } 4130 4131 /* Adjust by relative CPU power of the group */ 4132 avg_load = (avg_load * SCHED_POWER_SCALE) / group->sgp->power; 4133 4134 if (local_group) { 4135 this_load = avg_load; 4136 } else if (avg_load < min_load) { 4137 min_load = avg_load; 4138 idlest = group; 4139 } 4140 } while (group = group->next, group != sd->groups); 4141 4142 if (!idlest || 100*this_load < imbalance*min_load) 4143 return NULL; 4144 return idlest; 4145 } 4146 4147 /* 4148 * find_idlest_cpu - find the idlest cpu among the cpus in group. 4149 */ 4150 static int 4151 find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu) 4152 { 4153 unsigned long load, min_load = ULONG_MAX; 4154 int idlest = -1; 4155 int i; 4156 4157 /* Traverse only the allowed CPUs */ 4158 for_each_cpu_and(i, sched_group_cpus(group), tsk_cpus_allowed(p)) { 4159 load = weighted_cpuload(i); 4160 4161 if (load < min_load || (load == min_load && i == this_cpu)) { 4162 min_load = load; 4163 idlest = i; 4164 } 4165 } 4166 4167 return idlest; 4168 } 4169 4170 /* 4171 * Try and locate an idle CPU in the sched_domain. 4172 */ 4173 static int select_idle_sibling(struct task_struct *p, int target) 4174 { 4175 struct sched_domain *sd; 4176 struct sched_group *sg; 4177 int i = task_cpu(p); 4178 4179 if (idle_cpu(target)) 4180 return target; 4181 4182 /* 4183 * If the prevous cpu is cache affine and idle, don't be stupid. 4184 */ 4185 if (i != target && cpus_share_cache(i, target) && idle_cpu(i)) 4186 return i; 4187 4188 /* 4189 * Otherwise, iterate the domains and find an elegible idle cpu. 4190 */ 4191 sd = rcu_dereference(per_cpu(sd_llc, target)); 4192 for_each_lower_domain(sd) { 4193 sg = sd->groups; 4194 do { 4195 if (!cpumask_intersects(sched_group_cpus(sg), 4196 tsk_cpus_allowed(p))) 4197 goto next; 4198 4199 for_each_cpu(i, sched_group_cpus(sg)) { 4200 if (i == target || !idle_cpu(i)) 4201 goto next; 4202 } 4203 4204 target = cpumask_first_and(sched_group_cpus(sg), 4205 tsk_cpus_allowed(p)); 4206 goto done; 4207 next: 4208 sg = sg->next; 4209 } while (sg != sd->groups); 4210 } 4211 done: 4212 return target; 4213 } 4214 4215 /* 4216 * sched_balance_self: balance the current task (running on cpu) in domains 4217 * that have the 'flag' flag set. In practice, this is SD_BALANCE_FORK and 4218 * SD_BALANCE_EXEC. 4219 * 4220 * Balance, ie. select the least loaded group. 4221 * 4222 * Returns the target CPU number, or the same CPU if no balancing is needed. 4223 * 4224 * preempt must be disabled. 4225 */ 4226 static int 4227 select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_flags) 4228 { 4229 struct sched_domain *tmp, *affine_sd = NULL, *sd = NULL; 4230 int cpu = smp_processor_id(); 4231 int new_cpu = cpu; 4232 int want_affine = 0; 4233 int sync = wake_flags & WF_SYNC; 4234 4235 if (p->nr_cpus_allowed == 1) 4236 return prev_cpu; 4237 4238 if (sd_flag & SD_BALANCE_WAKE) { 4239 if (cpumask_test_cpu(cpu, tsk_cpus_allowed(p))) 4240 want_affine = 1; 4241 new_cpu = prev_cpu; 4242 } 4243 4244 rcu_read_lock(); 4245 for_each_domain(cpu, tmp) { 4246 if (!(tmp->flags & SD_LOAD_BALANCE)) 4247 continue; 4248 4249 /* 4250 * If both cpu and prev_cpu are part of this domain, 4251 * cpu is a valid SD_WAKE_AFFINE target. 4252 */ 4253 if (want_affine && (tmp->flags & SD_WAKE_AFFINE) && 4254 cpumask_test_cpu(prev_cpu, sched_domain_span(tmp))) { 4255 affine_sd = tmp; 4256 break; 4257 } 4258 4259 if (tmp->flags & sd_flag) 4260 sd = tmp; 4261 } 4262 4263 if (affine_sd) { 4264 if (cpu != prev_cpu && wake_affine(affine_sd, p, sync)) 4265 prev_cpu = cpu; 4266 4267 new_cpu = select_idle_sibling(p, prev_cpu); 4268 goto unlock; 4269 } 4270 4271 while (sd) { 4272 struct sched_group *group; 4273 int weight; 4274 4275 if (!(sd->flags & sd_flag)) { 4276 sd = sd->child; 4277 continue; 4278 } 4279 4280 group = find_idlest_group(sd, p, cpu, sd_flag); 4281 if (!group) { 4282 sd = sd->child; 4283 continue; 4284 } 4285 4286 new_cpu = find_idlest_cpu(group, p, cpu); 4287 if (new_cpu == -1 || new_cpu == cpu) { 4288 /* Now try balancing at a lower domain level of cpu */ 4289 sd = sd->child; 4290 continue; 4291 } 4292 4293 /* Now try balancing at a lower domain level of new_cpu */ 4294 cpu = new_cpu; 4295 weight = sd->span_weight; 4296 sd = NULL; 4297 for_each_domain(cpu, tmp) { 4298 if (weight <= tmp->span_weight) 4299 break; 4300 if (tmp->flags & sd_flag) 4301 sd = tmp; 4302 } 4303 /* while loop will break here if sd == NULL */ 4304 } 4305 unlock: 4306 rcu_read_unlock(); 4307 4308 return new_cpu; 4309 } 4310 4311 /* 4312 * Called immediately before a task is migrated to a new cpu; task_cpu(p) and 4313 * cfs_rq_of(p) references at time of call are still valid and identify the 4314 * previous cpu. However, the caller only guarantees p->pi_lock is held; no 4315 * other assumptions, including the state of rq->lock, should be made. 4316 */ 4317 static void 4318 migrate_task_rq_fair(struct task_struct *p, int next_cpu) 4319 { 4320 struct sched_entity *se = &p->se; 4321 struct cfs_rq *cfs_rq = cfs_rq_of(se); 4322 4323 /* 4324 * Load tracking: accumulate removed load so that it can be processed 4325 * when we next update owning cfs_rq under rq->lock. Tasks contribute 4326 * to blocked load iff they have a positive decay-count. It can never 4327 * be negative here since on-rq tasks have decay-count == 0. 4328 */ 4329 if (se->avg.decay_count) { 4330 se->avg.decay_count = -__synchronize_entity_decay(se); 4331 atomic_long_add(se->avg.load_avg_contrib, 4332 &cfs_rq->removed_load); 4333 } 4334 } 4335 #endif /* CONFIG_SMP */ 4336 4337 static unsigned long 4338 wakeup_gran(struct sched_entity *curr, struct sched_entity *se) 4339 { 4340 unsigned long gran = sysctl_sched_wakeup_granularity; 4341 4342 /* 4343 * Since its curr running now, convert the gran from real-time 4344 * to virtual-time in his units. 4345 * 4346 * By using 'se' instead of 'curr' we penalize light tasks, so 4347 * they get preempted easier. That is, if 'se' < 'curr' then 4348 * the resulting gran will be larger, therefore penalizing the 4349 * lighter, if otoh 'se' > 'curr' then the resulting gran will 4350 * be smaller, again penalizing the lighter task. 4351 * 4352 * This is especially important for buddies when the leftmost 4353 * task is higher priority than the buddy. 4354 */ 4355 return calc_delta_fair(gran, se); 4356 } 4357 4358 /* 4359 * Should 'se' preempt 'curr'. 4360 * 4361 * |s1 4362 * |s2 4363 * |s3 4364 * g 4365 * |<--->|c 4366 * 4367 * w(c, s1) = -1 4368 * w(c, s2) = 0 4369 * w(c, s3) = 1 4370 * 4371 */ 4372 static int 4373 wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se) 4374 { 4375 s64 gran, vdiff = curr->vruntime - se->vruntime; 4376 4377 if (vdiff <= 0) 4378 return -1; 4379 4380 gran = wakeup_gran(curr, se); 4381 if (vdiff > gran) 4382 return 1; 4383 4384 return 0; 4385 } 4386 4387 static void set_last_buddy(struct sched_entity *se) 4388 { 4389 if (entity_is_task(se) && unlikely(task_of(se)->policy == SCHED_IDLE)) 4390 return; 4391 4392 for_each_sched_entity(se) 4393 cfs_rq_of(se)->last = se; 4394 } 4395 4396 static void set_next_buddy(struct sched_entity *se) 4397 { 4398 if (entity_is_task(se) && unlikely(task_of(se)->policy == SCHED_IDLE)) 4399 return; 4400 4401 for_each_sched_entity(se) 4402 cfs_rq_of(se)->next = se; 4403 } 4404 4405 static void set_skip_buddy(struct sched_entity *se) 4406 { 4407 for_each_sched_entity(se) 4408 cfs_rq_of(se)->skip = se; 4409 } 4410 4411 /* 4412 * Preempt the current task with a newly woken task if needed: 4413 */ 4414 static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags) 4415 { 4416 struct task_struct *curr = rq->curr; 4417 struct sched_entity *se = &curr->se, *pse = &p->se; 4418 struct cfs_rq *cfs_rq = task_cfs_rq(curr); 4419 int scale = cfs_rq->nr_running >= sched_nr_latency; 4420 int next_buddy_marked = 0; 4421 4422 if (unlikely(se == pse)) 4423 return; 4424 4425 /* 4426 * This is possible from callers such as move_task(), in which we 4427 * unconditionally check_prempt_curr() after an enqueue (which may have 4428 * lead to a throttle). This both saves work and prevents false 4429 * next-buddy nomination below. 4430 */ 4431 if (unlikely(throttled_hierarchy(cfs_rq_of(pse)))) 4432 return; 4433 4434 if (sched_feat(NEXT_BUDDY) && scale && !(wake_flags & WF_FORK)) { 4435 set_next_buddy(pse); 4436 next_buddy_marked = 1; 4437 } 4438 4439 /* 4440 * We can come here with TIF_NEED_RESCHED already set from new task 4441 * wake up path. 4442 * 4443 * Note: this also catches the edge-case of curr being in a throttled 4444 * group (e.g. via set_curr_task), since update_curr() (in the 4445 * enqueue of curr) will have resulted in resched being set. This 4446 * prevents us from potentially nominating it as a false LAST_BUDDY 4447 * below. 4448 */ 4449 if (test_tsk_need_resched(curr)) 4450 return; 4451 4452 /* Idle tasks are by definition preempted by non-idle tasks. */ 4453 if (unlikely(curr->policy == SCHED_IDLE) && 4454 likely(p->policy != SCHED_IDLE)) 4455 goto preempt; 4456 4457 /* 4458 * Batch and idle tasks do not preempt non-idle tasks (their preemption 4459 * is driven by the tick): 4460 */ 4461 if (unlikely(p->policy != SCHED_NORMAL) || !sched_feat(WAKEUP_PREEMPTION)) 4462 return; 4463 4464 find_matching_se(&se, &pse); 4465 update_curr(cfs_rq_of(se)); 4466 BUG_ON(!pse); 4467 if (wakeup_preempt_entity(se, pse) == 1) { 4468 /* 4469 * Bias pick_next to pick the sched entity that is 4470 * triggering this preemption. 4471 */ 4472 if (!next_buddy_marked) 4473 set_next_buddy(pse); 4474 goto preempt; 4475 } 4476 4477 return; 4478 4479 preempt: 4480 resched_task(curr); 4481 /* 4482 * Only set the backward buddy when the current task is still 4483 * on the rq. This can happen when a wakeup gets interleaved 4484 * with schedule on the ->pre_schedule() or idle_balance() 4485 * point, either of which can * drop the rq lock. 4486 * 4487 * Also, during early boot the idle thread is in the fair class, 4488 * for obvious reasons its a bad idea to schedule back to it. 4489 */ 4490 if (unlikely(!se->on_rq || curr == rq->idle)) 4491 return; 4492 4493 if (sched_feat(LAST_BUDDY) && scale && entity_is_task(se)) 4494 set_last_buddy(se); 4495 } 4496 4497 static struct task_struct *pick_next_task_fair(struct rq *rq) 4498 { 4499 struct task_struct *p; 4500 struct cfs_rq *cfs_rq = &rq->cfs; 4501 struct sched_entity *se; 4502 4503 if (!cfs_rq->nr_running) 4504 return NULL; 4505 4506 do { 4507 se = pick_next_entity(cfs_rq); 4508 set_next_entity(cfs_rq, se); 4509 cfs_rq = group_cfs_rq(se); 4510 } while (cfs_rq); 4511 4512 p = task_of(se); 4513 if (hrtick_enabled(rq)) 4514 hrtick_start_fair(rq, p); 4515 4516 return p; 4517 } 4518 4519 /* 4520 * Account for a descheduled task: 4521 */ 4522 static void put_prev_task_fair(struct rq *rq, struct task_struct *prev) 4523 { 4524 struct sched_entity *se = &prev->se; 4525 struct cfs_rq *cfs_rq; 4526 4527 for_each_sched_entity(se) { 4528 cfs_rq = cfs_rq_of(se); 4529 put_prev_entity(cfs_rq, se); 4530 } 4531 } 4532 4533 /* 4534 * sched_yield() is very simple 4535 * 4536 * The magic of dealing with the ->skip buddy is in pick_next_entity. 4537 */ 4538 static void yield_task_fair(struct rq *rq) 4539 { 4540 struct task_struct *curr = rq->curr; 4541 struct cfs_rq *cfs_rq = task_cfs_rq(curr); 4542 struct sched_entity *se = &curr->se; 4543 4544 /* 4545 * Are we the only task in the tree? 4546 */ 4547 if (unlikely(rq->nr_running == 1)) 4548 return; 4549 4550 clear_buddies(cfs_rq, se); 4551 4552 if (curr->policy != SCHED_BATCH) { 4553 update_rq_clock(rq); 4554 /* 4555 * Update run-time statistics of the 'current'. 4556 */ 4557 update_curr(cfs_rq); 4558 /* 4559 * Tell update_rq_clock() that we've just updated, 4560 * so we don't do microscopic update in schedule() 4561 * and double the fastpath cost. 4562 */ 4563 rq->skip_clock_update = 1; 4564 } 4565 4566 set_skip_buddy(se); 4567 } 4568 4569 static bool yield_to_task_fair(struct rq *rq, struct task_struct *p, bool preempt) 4570 { 4571 struct sched_entity *se = &p->se; 4572 4573 /* throttled hierarchies are not runnable */ 4574 if (!se->on_rq || throttled_hierarchy(cfs_rq_of(se))) 4575 return false; 4576 4577 /* Tell the scheduler that we'd really like pse to run next. */ 4578 set_next_buddy(se); 4579 4580 yield_task_fair(rq); 4581 4582 return true; 4583 } 4584 4585 #ifdef CONFIG_SMP 4586 /************************************************** 4587 * Fair scheduling class load-balancing methods. 4588 * 4589 * BASICS 4590 * 4591 * The purpose of load-balancing is to achieve the same basic fairness the 4592 * per-cpu scheduler provides, namely provide a proportional amount of compute 4593 * time to each task. This is expressed in the following equation: 4594 * 4595 * W_i,n/P_i == W_j,n/P_j for all i,j (1) 4596 * 4597 * Where W_i,n is the n-th weight average for cpu i. The instantaneous weight 4598 * W_i,0 is defined as: 4599 * 4600 * W_i,0 = \Sum_j w_i,j (2) 4601 * 4602 * Where w_i,j is the weight of the j-th runnable task on cpu i. This weight 4603 * is derived from the nice value as per prio_to_weight[]. 4604 * 4605 * The weight average is an exponential decay average of the instantaneous 4606 * weight: 4607 * 4608 * W'_i,n = (2^n - 1) / 2^n * W_i,n + 1 / 2^n * W_i,0 (3) 4609 * 4610 * P_i is the cpu power (or compute capacity) of cpu i, typically it is the 4611 * fraction of 'recent' time available for SCHED_OTHER task execution. But it 4612 * can also include other factors [XXX]. 4613 * 4614 * To achieve this balance we define a measure of imbalance which follows 4615 * directly from (1): 4616 * 4617 * imb_i,j = max{ avg(W/P), W_i/P_i } - min{ avg(W/P), W_j/P_j } (4) 4618 * 4619 * We them move tasks around to minimize the imbalance. In the continuous 4620 * function space it is obvious this converges, in the discrete case we get 4621 * a few fun cases generally called infeasible weight scenarios. 4622 * 4623 * [XXX expand on: 4624 * - infeasible weights; 4625 * - local vs global optima in the discrete case. ] 4626 * 4627 * 4628 * SCHED DOMAINS 4629 * 4630 * In order to solve the imbalance equation (4), and avoid the obvious O(n^2) 4631 * for all i,j solution, we create a tree of cpus that follows the hardware 4632 * topology where each level pairs two lower groups (or better). This results 4633 * in O(log n) layers. Furthermore we reduce the number of cpus going up the 4634 * tree to only the first of the previous level and we decrease the frequency 4635 * of load-balance at each level inv. proportional to the number of cpus in 4636 * the groups. 4637 * 4638 * This yields: 4639 * 4640 * log_2 n 1 n 4641 * \Sum { --- * --- * 2^i } = O(n) (5) 4642 * i = 0 2^i 2^i 4643 * `- size of each group 4644 * | | `- number of cpus doing load-balance 4645 * | `- freq 4646 * `- sum over all levels 4647 * 4648 * Coupled with a limit on how many tasks we can migrate every balance pass, 4649 * this makes (5) the runtime complexity of the balancer. 4650 * 4651 * An important property here is that each CPU is still (indirectly) connected 4652 * to every other cpu in at most O(log n) steps: 4653 * 4654 * The adjacency matrix of the resulting graph is given by: 4655 * 4656 * log_2 n 4657 * A_i,j = \Union (i % 2^k == 0) && i / 2^(k+1) == j / 2^(k+1) (6) 4658 * k = 0 4659 * 4660 * And you'll find that: 4661 * 4662 * A^(log_2 n)_i,j != 0 for all i,j (7) 4663 * 4664 * Showing there's indeed a path between every cpu in at most O(log n) steps. 4665 * The task movement gives a factor of O(m), giving a convergence complexity 4666 * of: 4667 * 4668 * O(nm log n), n := nr_cpus, m := nr_tasks (8) 4669 * 4670 * 4671 * WORK CONSERVING 4672 * 4673 * In order to avoid CPUs going idle while there's still work to do, new idle 4674 * balancing is more aggressive and has the newly idle cpu iterate up the domain 4675 * tree itself instead of relying on other CPUs to bring it work. 4676 * 4677 * This adds some complexity to both (5) and (8) but it reduces the total idle 4678 * time. 4679 * 4680 * [XXX more?] 4681 * 4682 * 4683 * CGROUPS 4684 * 4685 * Cgroups make a horror show out of (2), instead of a simple sum we get: 4686 * 4687 * s_k,i 4688 * W_i,0 = \Sum_j \Prod_k w_k * ----- (9) 4689 * S_k 4690 * 4691 * Where 4692 * 4693 * s_k,i = \Sum_j w_i,j,k and S_k = \Sum_i s_k,i (10) 4694 * 4695 * w_i,j,k is the weight of the j-th runnable task in the k-th cgroup on cpu i. 4696 * 4697 * The big problem is S_k, its a global sum needed to compute a local (W_i) 4698 * property. 4699 * 4700 * [XXX write more on how we solve this.. _after_ merging pjt's patches that 4701 * rewrite all of this once again.] 4702 */ 4703 4704 static unsigned long __read_mostly max_load_balance_interval = HZ/10; 4705 4706 enum fbq_type { regular, remote, all }; 4707 4708 #define LBF_ALL_PINNED 0x01 4709 #define LBF_NEED_BREAK 0x02 4710 #define LBF_DST_PINNED 0x04 4711 #define LBF_SOME_PINNED 0x08 4712 4713 struct lb_env { 4714 struct sched_domain *sd; 4715 4716 struct rq *src_rq; 4717 int src_cpu; 4718 4719 int dst_cpu; 4720 struct rq *dst_rq; 4721 4722 struct cpumask *dst_grpmask; 4723 int new_dst_cpu; 4724 enum cpu_idle_type idle; 4725 long imbalance; 4726 /* The set of CPUs under consideration for load-balancing */ 4727 struct cpumask *cpus; 4728 4729 unsigned int flags; 4730 4731 unsigned int loop; 4732 unsigned int loop_break; 4733 unsigned int loop_max; 4734 4735 enum fbq_type fbq_type; 4736 }; 4737 4738 /* 4739 * move_task - move a task from one runqueue to another runqueue. 4740 * Both runqueues must be locked. 4741 */ 4742 static void move_task(struct task_struct *p, struct lb_env *env) 4743 { 4744 deactivate_task(env->src_rq, p, 0); 4745 set_task_cpu(p, env->dst_cpu); 4746 activate_task(env->dst_rq, p, 0); 4747 check_preempt_curr(env->dst_rq, p, 0); 4748 } 4749 4750 /* 4751 * Is this task likely cache-hot: 4752 */ 4753 static int 4754 task_hot(struct task_struct *p, u64 now, struct sched_domain *sd) 4755 { 4756 s64 delta; 4757 4758 if (p->sched_class != &fair_sched_class) 4759 return 0; 4760 4761 if (unlikely(p->policy == SCHED_IDLE)) 4762 return 0; 4763 4764 /* 4765 * Buddy candidates are cache hot: 4766 */ 4767 if (sched_feat(CACHE_HOT_BUDDY) && this_rq()->nr_running && 4768 (&p->se == cfs_rq_of(&p->se)->next || 4769 &p->se == cfs_rq_of(&p->se)->last)) 4770 return 1; 4771 4772 if (sysctl_sched_migration_cost == -1) 4773 return 1; 4774 if (sysctl_sched_migration_cost == 0) 4775 return 0; 4776 4777 delta = now - p->se.exec_start; 4778 4779 return delta < (s64)sysctl_sched_migration_cost; 4780 } 4781 4782 #ifdef CONFIG_NUMA_BALANCING 4783 /* Returns true if the destination node has incurred more faults */ 4784 static bool migrate_improves_locality(struct task_struct *p, struct lb_env *env) 4785 { 4786 int src_nid, dst_nid; 4787 4788 if (!sched_feat(NUMA_FAVOUR_HIGHER) || !p->numa_faults || 4789 !(env->sd->flags & SD_NUMA)) { 4790 return false; 4791 } 4792 4793 src_nid = cpu_to_node(env->src_cpu); 4794 dst_nid = cpu_to_node(env->dst_cpu); 4795 4796 if (src_nid == dst_nid) 4797 return false; 4798 4799 /* Always encourage migration to the preferred node. */ 4800 if (dst_nid == p->numa_preferred_nid) 4801 return true; 4802 4803 /* If both task and group weight improve, this move is a winner. */ 4804 if (task_weight(p, dst_nid) > task_weight(p, src_nid) && 4805 group_weight(p, dst_nid) > group_weight(p, src_nid)) 4806 return true; 4807 4808 return false; 4809 } 4810 4811 4812 static bool migrate_degrades_locality(struct task_struct *p, struct lb_env *env) 4813 { 4814 int src_nid, dst_nid; 4815 4816 if (!sched_feat(NUMA) || !sched_feat(NUMA_RESIST_LOWER)) 4817 return false; 4818 4819 if (!p->numa_faults || !(env->sd->flags & SD_NUMA)) 4820 return false; 4821 4822 src_nid = cpu_to_node(env->src_cpu); 4823 dst_nid = cpu_to_node(env->dst_cpu); 4824 4825 if (src_nid == dst_nid) 4826 return false; 4827 4828 /* Migrating away from the preferred node is always bad. */ 4829 if (src_nid == p->numa_preferred_nid) 4830 return true; 4831 4832 /* If either task or group weight get worse, don't do it. */ 4833 if (task_weight(p, dst_nid) < task_weight(p, src_nid) || 4834 group_weight(p, dst_nid) < group_weight(p, src_nid)) 4835 return true; 4836 4837 return false; 4838 } 4839 4840 #else 4841 static inline bool migrate_improves_locality(struct task_struct *p, 4842 struct lb_env *env) 4843 { 4844 return false; 4845 } 4846 4847 static inline bool migrate_degrades_locality(struct task_struct *p, 4848 struct lb_env *env) 4849 { 4850 return false; 4851 } 4852 #endif 4853 4854 /* 4855 * can_migrate_task - may task p from runqueue rq be migrated to this_cpu? 4856 */ 4857 static 4858 int can_migrate_task(struct task_struct *p, struct lb_env *env) 4859 { 4860 int tsk_cache_hot = 0; 4861 /* 4862 * We do not migrate tasks that are: 4863 * 1) throttled_lb_pair, or 4864 * 2) cannot be migrated to this CPU due to cpus_allowed, or 4865 * 3) running (obviously), or 4866 * 4) are cache-hot on their current CPU. 4867 */ 4868 if (throttled_lb_pair(task_group(p), env->src_cpu, env->dst_cpu)) 4869 return 0; 4870 4871 if (!cpumask_test_cpu(env->dst_cpu, tsk_cpus_allowed(p))) { 4872 int cpu; 4873 4874 schedstat_inc(p, se.statistics.nr_failed_migrations_affine); 4875 4876 env->flags |= LBF_SOME_PINNED; 4877 4878 /* 4879 * Remember if this task can be migrated to any other cpu in 4880 * our sched_group. We may want to revisit it if we couldn't 4881 * meet load balance goals by pulling other tasks on src_cpu. 4882 * 4883 * Also avoid computing new_dst_cpu if we have already computed 4884 * one in current iteration. 4885 */ 4886 if (!env->dst_grpmask || (env->flags & LBF_DST_PINNED)) 4887 return 0; 4888 4889 /* Prevent to re-select dst_cpu via env's cpus */ 4890 for_each_cpu_and(cpu, env->dst_grpmask, env->cpus) { 4891 if (cpumask_test_cpu(cpu, tsk_cpus_allowed(p))) { 4892 env->flags |= LBF_DST_PINNED; 4893 env->new_dst_cpu = cpu; 4894 break; 4895 } 4896 } 4897 4898 return 0; 4899 } 4900 4901 /* Record that we found atleast one task that could run on dst_cpu */ 4902 env->flags &= ~LBF_ALL_PINNED; 4903 4904 if (task_running(env->src_rq, p)) { 4905 schedstat_inc(p, se.statistics.nr_failed_migrations_running); 4906 return 0; 4907 } 4908 4909 /* 4910 * Aggressive migration if: 4911 * 1) destination numa is preferred 4912 * 2) task is cache cold, or 4913 * 3) too many balance attempts have failed. 4914 */ 4915 tsk_cache_hot = task_hot(p, rq_clock_task(env->src_rq), env->sd); 4916 if (!tsk_cache_hot) 4917 tsk_cache_hot = migrate_degrades_locality(p, env); 4918 4919 if (migrate_improves_locality(p, env)) { 4920 #ifdef CONFIG_SCHEDSTATS 4921 if (tsk_cache_hot) { 4922 schedstat_inc(env->sd, lb_hot_gained[env->idle]); 4923 schedstat_inc(p, se.statistics.nr_forced_migrations); 4924 } 4925 #endif 4926 return 1; 4927 } 4928 4929 if (!tsk_cache_hot || 4930 env->sd->nr_balance_failed > env->sd->cache_nice_tries) { 4931 4932 if (tsk_cache_hot) { 4933 schedstat_inc(env->sd, lb_hot_gained[env->idle]); 4934 schedstat_inc(p, se.statistics.nr_forced_migrations); 4935 } 4936 4937 return 1; 4938 } 4939 4940 schedstat_inc(p, se.statistics.nr_failed_migrations_hot); 4941 return 0; 4942 } 4943 4944 /* 4945 * move_one_task tries to move exactly one task from busiest to this_rq, as 4946 * part of active balancing operations within "domain". 4947 * Returns 1 if successful and 0 otherwise. 4948 * 4949 * Called with both runqueues locked. 4950 */ 4951 static int move_one_task(struct lb_env *env) 4952 { 4953 struct task_struct *p, *n; 4954 4955 list_for_each_entry_safe(p, n, &env->src_rq->cfs_tasks, se.group_node) { 4956 if (!can_migrate_task(p, env)) 4957 continue; 4958 4959 move_task(p, env); 4960 /* 4961 * Right now, this is only the second place move_task() 4962 * is called, so we can safely collect move_task() 4963 * stats here rather than inside move_task(). 4964 */ 4965 schedstat_inc(env->sd, lb_gained[env->idle]); 4966 return 1; 4967 } 4968 return 0; 4969 } 4970 4971 static const unsigned int sched_nr_migrate_break = 32; 4972 4973 /* 4974 * move_tasks tries to move up to imbalance weighted load from busiest to 4975 * this_rq, as part of a balancing operation within domain "sd". 4976 * Returns 1 if successful and 0 otherwise. 4977 * 4978 * Called with both runqueues locked. 4979 */ 4980 static int move_tasks(struct lb_env *env) 4981 { 4982 struct list_head *tasks = &env->src_rq->cfs_tasks; 4983 struct task_struct *p; 4984 unsigned long load; 4985 int pulled = 0; 4986 4987 if (env->imbalance <= 0) 4988 return 0; 4989 4990 while (!list_empty(tasks)) { 4991 p = list_first_entry(tasks, struct task_struct, se.group_node); 4992 4993 env->loop++; 4994 /* We've more or less seen every task there is, call it quits */ 4995 if (env->loop > env->loop_max) 4996 break; 4997 4998 /* take a breather every nr_migrate tasks */ 4999 if (env->loop > env->loop_break) { 5000 env->loop_break += sched_nr_migrate_break; 5001 env->flags |= LBF_NEED_BREAK; 5002 break; 5003 } 5004 5005 if (!can_migrate_task(p, env)) 5006 goto next; 5007 5008 load = task_h_load(p); 5009 5010 if (sched_feat(LB_MIN) && load < 16 && !env->sd->nr_balance_failed) 5011 goto next; 5012 5013 if ((load / 2) > env->imbalance) 5014 goto next; 5015 5016 move_task(p, env); 5017 pulled++; 5018 env->imbalance -= load; 5019 5020 #ifdef CONFIG_PREEMPT 5021 /* 5022 * NEWIDLE balancing is a source of latency, so preemptible 5023 * kernels will stop after the first task is pulled to minimize 5024 * the critical section. 5025 */ 5026 if (env->idle == CPU_NEWLY_IDLE) 5027 break; 5028 #endif 5029 5030 /* 5031 * We only want to steal up to the prescribed amount of 5032 * weighted load. 5033 */ 5034 if (env->imbalance <= 0) 5035 break; 5036 5037 continue; 5038 next: 5039 list_move_tail(&p->se.group_node, tasks); 5040 } 5041 5042 /* 5043 * Right now, this is one of only two places move_task() is called, 5044 * so we can safely collect move_task() stats here rather than 5045 * inside move_task(). 5046 */ 5047 schedstat_add(env->sd, lb_gained[env->idle], pulled); 5048 5049 return pulled; 5050 } 5051 5052 #ifdef CONFIG_FAIR_GROUP_SCHED 5053 /* 5054 * update tg->load_weight by folding this cpu's load_avg 5055 */ 5056 static void __update_blocked_averages_cpu(struct task_group *tg, int cpu) 5057 { 5058 struct sched_entity *se = tg->se[cpu]; 5059 struct cfs_rq *cfs_rq = tg->cfs_rq[cpu]; 5060 5061 /* throttled entities do not contribute to load */ 5062 if (throttled_hierarchy(cfs_rq)) 5063 return; 5064 5065 update_cfs_rq_blocked_load(cfs_rq, 1); 5066 5067 if (se) { 5068 update_entity_load_avg(se, 1); 5069 /* 5070 * We pivot on our runnable average having decayed to zero for 5071 * list removal. This generally implies that all our children 5072 * have also been removed (modulo rounding error or bandwidth 5073 * control); however, such cases are rare and we can fix these 5074 * at enqueue. 5075 * 5076 * TODO: fix up out-of-order children on enqueue. 5077 */ 5078 if (!se->avg.runnable_avg_sum && !cfs_rq->nr_running) 5079 list_del_leaf_cfs_rq(cfs_rq); 5080 } else { 5081 struct rq *rq = rq_of(cfs_rq); 5082 update_rq_runnable_avg(rq, rq->nr_running); 5083 } 5084 } 5085 5086 static void update_blocked_averages(int cpu) 5087 { 5088 struct rq *rq = cpu_rq(cpu); 5089 struct cfs_rq *cfs_rq; 5090 unsigned long flags; 5091 5092 raw_spin_lock_irqsave(&rq->lock, flags); 5093 update_rq_clock(rq); 5094 /* 5095 * Iterates the task_group tree in a bottom up fashion, see 5096 * list_add_leaf_cfs_rq() for details. 5097 */ 5098 for_each_leaf_cfs_rq(rq, cfs_rq) { 5099 /* 5100 * Note: We may want to consider periodically releasing 5101 * rq->lock about these updates so that creating many task 5102 * groups does not result in continually extending hold time. 5103 */ 5104 __update_blocked_averages_cpu(cfs_rq->tg, rq->cpu); 5105 } 5106 5107 raw_spin_unlock_irqrestore(&rq->lock, flags); 5108 } 5109 5110 /* 5111 * Compute the hierarchical load factor for cfs_rq and all its ascendants. 5112 * This needs to be done in a top-down fashion because the load of a child 5113 * group is a fraction of its parents load. 5114 */ 5115 static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq) 5116 { 5117 struct rq *rq = rq_of(cfs_rq); 5118 struct sched_entity *se = cfs_rq->tg->se[cpu_of(rq)]; 5119 unsigned long now = jiffies; 5120 unsigned long load; 5121 5122 if (cfs_rq->last_h_load_update == now) 5123 return; 5124 5125 cfs_rq->h_load_next = NULL; 5126 for_each_sched_entity(se) { 5127 cfs_rq = cfs_rq_of(se); 5128 cfs_rq->h_load_next = se; 5129 if (cfs_rq->last_h_load_update == now) 5130 break; 5131 } 5132 5133 if (!se) { 5134 cfs_rq->h_load = cfs_rq->runnable_load_avg; 5135 cfs_rq->last_h_load_update = now; 5136 } 5137 5138 while ((se = cfs_rq->h_load_next) != NULL) { 5139 load = cfs_rq->h_load; 5140 load = div64_ul(load * se->avg.load_avg_contrib, 5141 cfs_rq->runnable_load_avg + 1); 5142 cfs_rq = group_cfs_rq(se); 5143 cfs_rq->h_load = load; 5144 cfs_rq->last_h_load_update = now; 5145 } 5146 } 5147 5148 static unsigned long task_h_load(struct task_struct *p) 5149 { 5150 struct cfs_rq *cfs_rq = task_cfs_rq(p); 5151 5152 update_cfs_rq_h_load(cfs_rq); 5153 return div64_ul(p->se.avg.load_avg_contrib * cfs_rq->h_load, 5154 cfs_rq->runnable_load_avg + 1); 5155 } 5156 #else 5157 static inline void update_blocked_averages(int cpu) 5158 { 5159 } 5160 5161 static unsigned long task_h_load(struct task_struct *p) 5162 { 5163 return p->se.avg.load_avg_contrib; 5164 } 5165 #endif 5166 5167 /********** Helpers for find_busiest_group ************************/ 5168 /* 5169 * sg_lb_stats - stats of a sched_group required for load_balancing 5170 */ 5171 struct sg_lb_stats { 5172 unsigned long avg_load; /*Avg load across the CPUs of the group */ 5173 unsigned long group_load; /* Total load over the CPUs of the group */ 5174 unsigned long sum_weighted_load; /* Weighted load of group's tasks */ 5175 unsigned long load_per_task; 5176 unsigned long group_power; 5177 unsigned int sum_nr_running; /* Nr tasks running in the group */ 5178 unsigned int group_capacity; 5179 unsigned int idle_cpus; 5180 unsigned int group_weight; 5181 int group_imb; /* Is there an imbalance in the group ? */ 5182 int group_has_capacity; /* Is there extra capacity in the group? */ 5183 #ifdef CONFIG_NUMA_BALANCING 5184 unsigned int nr_numa_running; 5185 unsigned int nr_preferred_running; 5186 #endif 5187 }; 5188 5189 /* 5190 * sd_lb_stats - Structure to store the statistics of a sched_domain 5191 * during load balancing. 5192 */ 5193 struct sd_lb_stats { 5194 struct sched_group *busiest; /* Busiest group in this sd */ 5195 struct sched_group *local; /* Local group in this sd */ 5196 unsigned long total_load; /* Total load of all groups in sd */ 5197 unsigned long total_pwr; /* Total power of all groups in sd */ 5198 unsigned long avg_load; /* Average load across all groups in sd */ 5199 5200 struct sg_lb_stats busiest_stat;/* Statistics of the busiest group */ 5201 struct sg_lb_stats local_stat; /* Statistics of the local group */ 5202 }; 5203 5204 static inline void init_sd_lb_stats(struct sd_lb_stats *sds) 5205 { 5206 /* 5207 * Skimp on the clearing to avoid duplicate work. We can avoid clearing 5208 * local_stat because update_sg_lb_stats() does a full clear/assignment. 5209 * We must however clear busiest_stat::avg_load because 5210 * update_sd_pick_busiest() reads this before assignment. 5211 */ 5212 *sds = (struct sd_lb_stats){ 5213 .busiest = NULL, 5214 .local = NULL, 5215 .total_load = 0UL, 5216 .total_pwr = 0UL, 5217 .busiest_stat = { 5218 .avg_load = 0UL, 5219 }, 5220 }; 5221 } 5222 5223 /** 5224 * get_sd_load_idx - Obtain the load index for a given sched domain. 5225 * @sd: The sched_domain whose load_idx is to be obtained. 5226 * @idle: The idle status of the CPU for whose sd load_idx is obtained. 5227 * 5228 * Return: The load index. 5229 */ 5230 static inline int get_sd_load_idx(struct sched_domain *sd, 5231 enum cpu_idle_type idle) 5232 { 5233 int load_idx; 5234 5235 switch (idle) { 5236 case CPU_NOT_IDLE: 5237 load_idx = sd->busy_idx; 5238 break; 5239 5240 case CPU_NEWLY_IDLE: 5241 load_idx = sd->newidle_idx; 5242 break; 5243 default: 5244 load_idx = sd->idle_idx; 5245 break; 5246 } 5247 5248 return load_idx; 5249 } 5250 5251 static unsigned long default_scale_freq_power(struct sched_domain *sd, int cpu) 5252 { 5253 return SCHED_POWER_SCALE; 5254 } 5255 5256 unsigned long __weak arch_scale_freq_power(struct sched_domain *sd, int cpu) 5257 { 5258 return default_scale_freq_power(sd, cpu); 5259 } 5260 5261 static unsigned long default_scale_smt_power(struct sched_domain *sd, int cpu) 5262 { 5263 unsigned long weight = sd->span_weight; 5264 unsigned long smt_gain = sd->smt_gain; 5265 5266 smt_gain /= weight; 5267 5268 return smt_gain; 5269 } 5270 5271 unsigned long __weak arch_scale_smt_power(struct sched_domain *sd, int cpu) 5272 { 5273 return default_scale_smt_power(sd, cpu); 5274 } 5275 5276 static unsigned long scale_rt_power(int cpu) 5277 { 5278 struct rq *rq = cpu_rq(cpu); 5279 u64 total, available, age_stamp, avg; 5280 5281 /* 5282 * Since we're reading these variables without serialization make sure 5283 * we read them once before doing sanity checks on them. 5284 */ 5285 age_stamp = ACCESS_ONCE(rq->age_stamp); 5286 avg = ACCESS_ONCE(rq->rt_avg); 5287 5288 total = sched_avg_period() + (rq_clock(rq) - age_stamp); 5289 5290 if (unlikely(total < avg)) { 5291 /* Ensures that power won't end up being negative */ 5292 available = 0; 5293 } else { 5294 available = total - avg; 5295 } 5296 5297 if (unlikely((s64)total < SCHED_POWER_SCALE)) 5298 total = SCHED_POWER_SCALE; 5299 5300 total >>= SCHED_POWER_SHIFT; 5301 5302 return div_u64(available, total); 5303 } 5304 5305 static void update_cpu_power(struct sched_domain *sd, int cpu) 5306 { 5307 unsigned long weight = sd->span_weight; 5308 unsigned long power = SCHED_POWER_SCALE; 5309 struct sched_group *sdg = sd->groups; 5310 5311 if ((sd->flags & SD_SHARE_CPUPOWER) && weight > 1) { 5312 if (sched_feat(ARCH_POWER)) 5313 power *= arch_scale_smt_power(sd, cpu); 5314 else 5315 power *= default_scale_smt_power(sd, cpu); 5316 5317 power >>= SCHED_POWER_SHIFT; 5318 } 5319 5320 sdg->sgp->power_orig = power; 5321 5322 if (sched_feat(ARCH_POWER)) 5323 power *= arch_scale_freq_power(sd, cpu); 5324 else 5325 power *= default_scale_freq_power(sd, cpu); 5326 5327 power >>= SCHED_POWER_SHIFT; 5328 5329 power *= scale_rt_power(cpu); 5330 power >>= SCHED_POWER_SHIFT; 5331 5332 if (!power) 5333 power = 1; 5334 5335 cpu_rq(cpu)->cpu_power = power; 5336 sdg->sgp->power = power; 5337 } 5338 5339 void update_group_power(struct sched_domain *sd, int cpu) 5340 { 5341 struct sched_domain *child = sd->child; 5342 struct sched_group *group, *sdg = sd->groups; 5343 unsigned long power, power_orig; 5344 unsigned long interval; 5345 5346 interval = msecs_to_jiffies(sd->balance_interval); 5347 interval = clamp(interval, 1UL, max_load_balance_interval); 5348 sdg->sgp->next_update = jiffies + interval; 5349 5350 if (!child) { 5351 update_cpu_power(sd, cpu); 5352 return; 5353 } 5354 5355 power_orig = power = 0; 5356 5357 if (child->flags & SD_OVERLAP) { 5358 /* 5359 * SD_OVERLAP domains cannot assume that child groups 5360 * span the current group. 5361 */ 5362 5363 for_each_cpu(cpu, sched_group_cpus(sdg)) { 5364 struct sched_group_power *sgp; 5365 struct rq *rq = cpu_rq(cpu); 5366 5367 /* 5368 * build_sched_domains() -> init_sched_groups_power() 5369 * gets here before we've attached the domains to the 5370 * runqueues. 5371 * 5372 * Use power_of(), which is set irrespective of domains 5373 * in update_cpu_power(). 5374 * 5375 * This avoids power/power_orig from being 0 and 5376 * causing divide-by-zero issues on boot. 5377 * 5378 * Runtime updates will correct power_orig. 5379 */ 5380 if (unlikely(!rq->sd)) { 5381 power_orig += power_of(cpu); 5382 power += power_of(cpu); 5383 continue; 5384 } 5385 5386 sgp = rq->sd->groups->sgp; 5387 power_orig += sgp->power_orig; 5388 power += sgp->power; 5389 } 5390 } else { 5391 /* 5392 * !SD_OVERLAP domains can assume that child groups 5393 * span the current group. 5394 */ 5395 5396 group = child->groups; 5397 do { 5398 power_orig += group->sgp->power_orig; 5399 power += group->sgp->power; 5400 group = group->next; 5401 } while (group != child->groups); 5402 } 5403 5404 sdg->sgp->power_orig = power_orig; 5405 sdg->sgp->power = power; 5406 } 5407 5408 /* 5409 * Try and fix up capacity for tiny siblings, this is needed when 5410 * things like SD_ASYM_PACKING need f_b_g to select another sibling 5411 * which on its own isn't powerful enough. 5412 * 5413 * See update_sd_pick_busiest() and check_asym_packing(). 5414 */ 5415 static inline int 5416 fix_small_capacity(struct sched_domain *sd, struct sched_group *group) 5417 { 5418 /* 5419 * Only siblings can have significantly less than SCHED_POWER_SCALE 5420 */ 5421 if (!(sd->flags & SD_SHARE_CPUPOWER)) 5422 return 0; 5423 5424 /* 5425 * If ~90% of the cpu_power is still there, we're good. 5426 */ 5427 if (group->sgp->power * 32 > group->sgp->power_orig * 29) 5428 return 1; 5429 5430 return 0; 5431 } 5432 5433 /* 5434 * Group imbalance indicates (and tries to solve) the problem where balancing 5435 * groups is inadequate due to tsk_cpus_allowed() constraints. 5436 * 5437 * Imagine a situation of two groups of 4 cpus each and 4 tasks each with a 5438 * cpumask covering 1 cpu of the first group and 3 cpus of the second group. 5439 * Something like: 5440 * 5441 * { 0 1 2 3 } { 4 5 6 7 } 5442 * * * * * 5443 * 5444 * If we were to balance group-wise we'd place two tasks in the first group and 5445 * two tasks in the second group. Clearly this is undesired as it will overload 5446 * cpu 3 and leave one of the cpus in the second group unused. 5447 * 5448 * The current solution to this issue is detecting the skew in the first group 5449 * by noticing the lower domain failed to reach balance and had difficulty 5450 * moving tasks due to affinity constraints. 5451 * 5452 * When this is so detected; this group becomes a candidate for busiest; see 5453 * update_sd_pick_busiest(). And calculate_imbalance() and 5454 * find_busiest_group() avoid some of the usual balance conditions to allow it 5455 * to create an effective group imbalance. 5456 * 5457 * This is a somewhat tricky proposition since the next run might not find the 5458 * group imbalance and decide the groups need to be balanced again. A most 5459 * subtle and fragile situation. 5460 */ 5461 5462 static inline int sg_imbalanced(struct sched_group *group) 5463 { 5464 return group->sgp->imbalance; 5465 } 5466 5467 /* 5468 * Compute the group capacity. 5469 * 5470 * Avoid the issue where N*frac(smt_power) >= 1 creates 'phantom' cores by 5471 * first dividing out the smt factor and computing the actual number of cores 5472 * and limit power unit capacity with that. 5473 */ 5474 static inline int sg_capacity(struct lb_env *env, struct sched_group *group) 5475 { 5476 unsigned int capacity, smt, cpus; 5477 unsigned int power, power_orig; 5478 5479 power = group->sgp->power; 5480 power_orig = group->sgp->power_orig; 5481 cpus = group->group_weight; 5482 5483 /* smt := ceil(cpus / power), assumes: 1 < smt_power < 2 */ 5484 smt = DIV_ROUND_UP(SCHED_POWER_SCALE * cpus, power_orig); 5485 capacity = cpus / smt; /* cores */ 5486 5487 capacity = min_t(unsigned, capacity, DIV_ROUND_CLOSEST(power, SCHED_POWER_SCALE)); 5488 if (!capacity) 5489 capacity = fix_small_capacity(env->sd, group); 5490 5491 return capacity; 5492 } 5493 5494 /** 5495 * update_sg_lb_stats - Update sched_group's statistics for load balancing. 5496 * @env: The load balancing environment. 5497 * @group: sched_group whose statistics are to be updated. 5498 * @load_idx: Load index of sched_domain of this_cpu for load calc. 5499 * @local_group: Does group contain this_cpu. 5500 * @sgs: variable to hold the statistics for this group. 5501 */ 5502 static inline void update_sg_lb_stats(struct lb_env *env, 5503 struct sched_group *group, int load_idx, 5504 int local_group, struct sg_lb_stats *sgs) 5505 { 5506 unsigned long load; 5507 int i; 5508 5509 memset(sgs, 0, sizeof(*sgs)); 5510 5511 for_each_cpu_and(i, sched_group_cpus(group), env->cpus) { 5512 struct rq *rq = cpu_rq(i); 5513 5514 /* Bias balancing toward cpus of our domain */ 5515 if (local_group) 5516 load = target_load(i, load_idx); 5517 else 5518 load = source_load(i, load_idx); 5519 5520 sgs->group_load += load; 5521 sgs->sum_nr_running += rq->nr_running; 5522 #ifdef CONFIG_NUMA_BALANCING 5523 sgs->nr_numa_running += rq->nr_numa_running; 5524 sgs->nr_preferred_running += rq->nr_preferred_running; 5525 #endif 5526 sgs->sum_weighted_load += weighted_cpuload(i); 5527 if (idle_cpu(i)) 5528 sgs->idle_cpus++; 5529 } 5530 5531 /* Adjust by relative CPU power of the group */ 5532 sgs->group_power = group->sgp->power; 5533 sgs->avg_load = (sgs->group_load*SCHED_POWER_SCALE) / sgs->group_power; 5534 5535 if (sgs->sum_nr_running) 5536 sgs->load_per_task = sgs->sum_weighted_load / sgs->sum_nr_running; 5537 5538 sgs->group_weight = group->group_weight; 5539 5540 sgs->group_imb = sg_imbalanced(group); 5541 sgs->group_capacity = sg_capacity(env, group); 5542 5543 if (sgs->group_capacity > sgs->sum_nr_running) 5544 sgs->group_has_capacity = 1; 5545 } 5546 5547 /** 5548 * update_sd_pick_busiest - return 1 on busiest group 5549 * @env: The load balancing environment. 5550 * @sds: sched_domain statistics 5551 * @sg: sched_group candidate to be checked for being the busiest 5552 * @sgs: sched_group statistics 5553 * 5554 * Determine if @sg is a busier group than the previously selected 5555 * busiest group. 5556 * 5557 * Return: %true if @sg is a busier group than the previously selected 5558 * busiest group. %false otherwise. 5559 */ 5560 static bool update_sd_pick_busiest(struct lb_env *env, 5561 struct sd_lb_stats *sds, 5562 struct sched_group *sg, 5563 struct sg_lb_stats *sgs) 5564 { 5565 if (sgs->avg_load <= sds->busiest_stat.avg_load) 5566 return false; 5567 5568 if (sgs->sum_nr_running > sgs->group_capacity) 5569 return true; 5570 5571 if (sgs->group_imb) 5572 return true; 5573 5574 /* 5575 * ASYM_PACKING needs to move all the work to the lowest 5576 * numbered CPUs in the group, therefore mark all groups 5577 * higher than ourself as busy. 5578 */ 5579 if ((env->sd->flags & SD_ASYM_PACKING) && sgs->sum_nr_running && 5580 env->dst_cpu < group_first_cpu(sg)) { 5581 if (!sds->busiest) 5582 return true; 5583 5584 if (group_first_cpu(sds->busiest) > group_first_cpu(sg)) 5585 return true; 5586 } 5587 5588 return false; 5589 } 5590 5591 #ifdef CONFIG_NUMA_BALANCING 5592 static inline enum fbq_type fbq_classify_group(struct sg_lb_stats *sgs) 5593 { 5594 if (sgs->sum_nr_running > sgs->nr_numa_running) 5595 return regular; 5596 if (sgs->sum_nr_running > sgs->nr_preferred_running) 5597 return remote; 5598 return all; 5599 } 5600 5601 static inline enum fbq_type fbq_classify_rq(struct rq *rq) 5602 { 5603 if (rq->nr_running > rq->nr_numa_running) 5604 return regular; 5605 if (rq->nr_running > rq->nr_preferred_running) 5606 return remote; 5607 return all; 5608 } 5609 #else 5610 static inline enum fbq_type fbq_classify_group(struct sg_lb_stats *sgs) 5611 { 5612 return all; 5613 } 5614 5615 static inline enum fbq_type fbq_classify_rq(struct rq *rq) 5616 { 5617 return regular; 5618 } 5619 #endif /* CONFIG_NUMA_BALANCING */ 5620 5621 /** 5622 * update_sd_lb_stats - Update sched_domain's statistics for load balancing. 5623 * @env: The load balancing environment. 5624 * @sds: variable to hold the statistics for this sched_domain. 5625 */ 5626 static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sds) 5627 { 5628 struct sched_domain *child = env->sd->child; 5629 struct sched_group *sg = env->sd->groups; 5630 struct sg_lb_stats tmp_sgs; 5631 int load_idx, prefer_sibling = 0; 5632 5633 if (child && child->flags & SD_PREFER_SIBLING) 5634 prefer_sibling = 1; 5635 5636 load_idx = get_sd_load_idx(env->sd, env->idle); 5637 5638 do { 5639 struct sg_lb_stats *sgs = &tmp_sgs; 5640 int local_group; 5641 5642 local_group = cpumask_test_cpu(env->dst_cpu, sched_group_cpus(sg)); 5643 if (local_group) { 5644 sds->local = sg; 5645 sgs = &sds->local_stat; 5646 5647 if (env->idle != CPU_NEWLY_IDLE || 5648 time_after_eq(jiffies, sg->sgp->next_update)) 5649 update_group_power(env->sd, env->dst_cpu); 5650 } 5651 5652 update_sg_lb_stats(env, sg, load_idx, local_group, sgs); 5653 5654 if (local_group) 5655 goto next_group; 5656 5657 /* 5658 * In case the child domain prefers tasks go to siblings 5659 * first, lower the sg capacity to one so that we'll try 5660 * and move all the excess tasks away. We lower the capacity 5661 * of a group only if the local group has the capacity to fit 5662 * these excess tasks, i.e. nr_running < group_capacity. The 5663 * extra check prevents the case where you always pull from the 5664 * heaviest group when it is already under-utilized (possible 5665 * with a large weight task outweighs the tasks on the system). 5666 */ 5667 if (prefer_sibling && sds->local && 5668 sds->local_stat.group_has_capacity) 5669 sgs->group_capacity = min(sgs->group_capacity, 1U); 5670 5671 if (update_sd_pick_busiest(env, sds, sg, sgs)) { 5672 sds->busiest = sg; 5673 sds->busiest_stat = *sgs; 5674 } 5675 5676 next_group: 5677 /* Now, start updating sd_lb_stats */ 5678 sds->total_load += sgs->group_load; 5679 sds->total_pwr += sgs->group_power; 5680 5681 sg = sg->next; 5682 } while (sg != env->sd->groups); 5683 5684 if (env->sd->flags & SD_NUMA) 5685 env->fbq_type = fbq_classify_group(&sds->busiest_stat); 5686 } 5687 5688 /** 5689 * check_asym_packing - Check to see if the group is packed into the 5690 * sched doman. 5691 * 5692 * This is primarily intended to used at the sibling level. Some 5693 * cores like POWER7 prefer to use lower numbered SMT threads. In the 5694 * case of POWER7, it can move to lower SMT modes only when higher 5695 * threads are idle. When in lower SMT modes, the threads will 5696 * perform better since they share less core resources. Hence when we 5697 * have idle threads, we want them to be the higher ones. 5698 * 5699 * This packing function is run on idle threads. It checks to see if 5700 * the busiest CPU in this domain (core in the P7 case) has a higher 5701 * CPU number than the packing function is being run on. Here we are 5702 * assuming lower CPU number will be equivalent to lower a SMT thread 5703 * number. 5704 * 5705 * Return: 1 when packing is required and a task should be moved to 5706 * this CPU. The amount of the imbalance is returned in *imbalance. 5707 * 5708 * @env: The load balancing environment. 5709 * @sds: Statistics of the sched_domain which is to be packed 5710 */ 5711 static int check_asym_packing(struct lb_env *env, struct sd_lb_stats *sds) 5712 { 5713 int busiest_cpu; 5714 5715 if (!(env->sd->flags & SD_ASYM_PACKING)) 5716 return 0; 5717 5718 if (!sds->busiest) 5719 return 0; 5720 5721 busiest_cpu = group_first_cpu(sds->busiest); 5722 if (env->dst_cpu > busiest_cpu) 5723 return 0; 5724 5725 env->imbalance = DIV_ROUND_CLOSEST( 5726 sds->busiest_stat.avg_load * sds->busiest_stat.group_power, 5727 SCHED_POWER_SCALE); 5728 5729 return 1; 5730 } 5731 5732 /** 5733 * fix_small_imbalance - Calculate the minor imbalance that exists 5734 * amongst the groups of a sched_domain, during 5735 * load balancing. 5736 * @env: The load balancing environment. 5737 * @sds: Statistics of the sched_domain whose imbalance is to be calculated. 5738 */ 5739 static inline 5740 void fix_small_imbalance(struct lb_env *env, struct sd_lb_stats *sds) 5741 { 5742 unsigned long tmp, pwr_now = 0, pwr_move = 0; 5743 unsigned int imbn = 2; 5744 unsigned long scaled_busy_load_per_task; 5745 struct sg_lb_stats *local, *busiest; 5746 5747 local = &sds->local_stat; 5748 busiest = &sds->busiest_stat; 5749 5750 if (!local->sum_nr_running) 5751 local->load_per_task = cpu_avg_load_per_task(env->dst_cpu); 5752 else if (busiest->load_per_task > local->load_per_task) 5753 imbn = 1; 5754 5755 scaled_busy_load_per_task = 5756 (busiest->load_per_task * SCHED_POWER_SCALE) / 5757 busiest->group_power; 5758 5759 if (busiest->avg_load + scaled_busy_load_per_task >= 5760 local->avg_load + (scaled_busy_load_per_task * imbn)) { 5761 env->imbalance = busiest->load_per_task; 5762 return; 5763 } 5764 5765 /* 5766 * OK, we don't have enough imbalance to justify moving tasks, 5767 * however we may be able to increase total CPU power used by 5768 * moving them. 5769 */ 5770 5771 pwr_now += busiest->group_power * 5772 min(busiest->load_per_task, busiest->avg_load); 5773 pwr_now += local->group_power * 5774 min(local->load_per_task, local->avg_load); 5775 pwr_now /= SCHED_POWER_SCALE; 5776 5777 /* Amount of load we'd subtract */ 5778 tmp = (busiest->load_per_task * SCHED_POWER_SCALE) / 5779 busiest->group_power; 5780 if (busiest->avg_load > tmp) { 5781 pwr_move += busiest->group_power * 5782 min(busiest->load_per_task, 5783 busiest->avg_load - tmp); 5784 } 5785 5786 /* Amount of load we'd add */ 5787 if (busiest->avg_load * busiest->group_power < 5788 busiest->load_per_task * SCHED_POWER_SCALE) { 5789 tmp = (busiest->avg_load * busiest->group_power) / 5790 local->group_power; 5791 } else { 5792 tmp = (busiest->load_per_task * SCHED_POWER_SCALE) / 5793 local->group_power; 5794 } 5795 pwr_move += local->group_power * 5796 min(local->load_per_task, local->avg_load + tmp); 5797 pwr_move /= SCHED_POWER_SCALE; 5798 5799 /* Move if we gain throughput */ 5800 if (pwr_move > pwr_now) 5801 env->imbalance = busiest->load_per_task; 5802 } 5803 5804 /** 5805 * calculate_imbalance - Calculate the amount of imbalance present within the 5806 * groups of a given sched_domain during load balance. 5807 * @env: load balance environment 5808 * @sds: statistics of the sched_domain whose imbalance is to be calculated. 5809 */ 5810 static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *sds) 5811 { 5812 unsigned long max_pull, load_above_capacity = ~0UL; 5813 struct sg_lb_stats *local, *busiest; 5814 5815 local = &sds->local_stat; 5816 busiest = &sds->busiest_stat; 5817 5818 if (busiest->group_imb) { 5819 /* 5820 * In the group_imb case we cannot rely on group-wide averages 5821 * to ensure cpu-load equilibrium, look at wider averages. XXX 5822 */ 5823 busiest->load_per_task = 5824 min(busiest->load_per_task, sds->avg_load); 5825 } 5826 5827 /* 5828 * In the presence of smp nice balancing, certain scenarios can have 5829 * max load less than avg load(as we skip the groups at or below 5830 * its cpu_power, while calculating max_load..) 5831 */ 5832 if (busiest->avg_load <= sds->avg_load || 5833 local->avg_load >= sds->avg_load) { 5834 env->imbalance = 0; 5835 return fix_small_imbalance(env, sds); 5836 } 5837 5838 if (!busiest->group_imb) { 5839 /* 5840 * Don't want to pull so many tasks that a group would go idle. 5841 * Except of course for the group_imb case, since then we might 5842 * have to drop below capacity to reach cpu-load equilibrium. 5843 */ 5844 load_above_capacity = 5845 (busiest->sum_nr_running - busiest->group_capacity); 5846 5847 load_above_capacity *= (SCHED_LOAD_SCALE * SCHED_POWER_SCALE); 5848 load_above_capacity /= busiest->group_power; 5849 } 5850 5851 /* 5852 * We're trying to get all the cpus to the average_load, so we don't 5853 * want to push ourselves above the average load, nor do we wish to 5854 * reduce the max loaded cpu below the average load. At the same time, 5855 * we also don't want to reduce the group load below the group capacity 5856 * (so that we can implement power-savings policies etc). Thus we look 5857 * for the minimum possible imbalance. 5858 */ 5859 max_pull = min(busiest->avg_load - sds->avg_load, load_above_capacity); 5860 5861 /* How much load to actually move to equalise the imbalance */ 5862 env->imbalance = min( 5863 max_pull * busiest->group_power, 5864 (sds->avg_load - local->avg_load) * local->group_power 5865 ) / SCHED_POWER_SCALE; 5866 5867 /* 5868 * if *imbalance is less than the average load per runnable task 5869 * there is no guarantee that any tasks will be moved so we'll have 5870 * a think about bumping its value to force at least one task to be 5871 * moved 5872 */ 5873 if (env->imbalance < busiest->load_per_task) 5874 return fix_small_imbalance(env, sds); 5875 } 5876 5877 /******* find_busiest_group() helpers end here *********************/ 5878 5879 /** 5880 * find_busiest_group - Returns the busiest group within the sched_domain 5881 * if there is an imbalance. If there isn't an imbalance, and 5882 * the user has opted for power-savings, it returns a group whose 5883 * CPUs can be put to idle by rebalancing those tasks elsewhere, if 5884 * such a group exists. 5885 * 5886 * Also calculates the amount of weighted load which should be moved 5887 * to restore balance. 5888 * 5889 * @env: The load balancing environment. 5890 * 5891 * Return: - The busiest group if imbalance exists. 5892 * - If no imbalance and user has opted for power-savings balance, 5893 * return the least loaded group whose CPUs can be 5894 * put to idle by rebalancing its tasks onto our group. 5895 */ 5896 static struct sched_group *find_busiest_group(struct lb_env *env) 5897 { 5898 struct sg_lb_stats *local, *busiest; 5899 struct sd_lb_stats sds; 5900 5901 init_sd_lb_stats(&sds); 5902 5903 /* 5904 * Compute the various statistics relavent for load balancing at 5905 * this level. 5906 */ 5907 update_sd_lb_stats(env, &sds); 5908 local = &sds.local_stat; 5909 busiest = &sds.busiest_stat; 5910 5911 if ((env->idle == CPU_IDLE || env->idle == CPU_NEWLY_IDLE) && 5912 check_asym_packing(env, &sds)) 5913 return sds.busiest; 5914 5915 /* There is no busy sibling group to pull tasks from */ 5916 if (!sds.busiest || busiest->sum_nr_running == 0) 5917 goto out_balanced; 5918 5919 sds.avg_load = (SCHED_POWER_SCALE * sds.total_load) / sds.total_pwr; 5920 5921 /* 5922 * If the busiest group is imbalanced the below checks don't 5923 * work because they assume all things are equal, which typically 5924 * isn't true due to cpus_allowed constraints and the like. 5925 */ 5926 if (busiest->group_imb) 5927 goto force_balance; 5928 5929 /* SD_BALANCE_NEWIDLE trumps SMP nice when underutilized */ 5930 if (env->idle == CPU_NEWLY_IDLE && local->group_has_capacity && 5931 !busiest->group_has_capacity) 5932 goto force_balance; 5933 5934 /* 5935 * If the local group is more busy than the selected busiest group 5936 * don't try and pull any tasks. 5937 */ 5938 if (local->avg_load >= busiest->avg_load) 5939 goto out_balanced; 5940 5941 /* 5942 * Don't pull any tasks if this group is already above the domain 5943 * average load. 5944 */ 5945 if (local->avg_load >= sds.avg_load) 5946 goto out_balanced; 5947 5948 if (env->idle == CPU_IDLE) { 5949 /* 5950 * This cpu is idle. If the busiest group load doesn't 5951 * have more tasks than the number of available cpu's and 5952 * there is no imbalance between this and busiest group 5953 * wrt to idle cpu's, it is balanced. 5954 */ 5955 if ((local->idle_cpus < busiest->idle_cpus) && 5956 busiest->sum_nr_running <= busiest->group_weight) 5957 goto out_balanced; 5958 } else { 5959 /* 5960 * In the CPU_NEWLY_IDLE, CPU_NOT_IDLE cases, use 5961 * imbalance_pct to be conservative. 5962 */ 5963 if (100 * busiest->avg_load <= 5964 env->sd->imbalance_pct * local->avg_load) 5965 goto out_balanced; 5966 } 5967 5968 force_balance: 5969 /* Looks like there is an imbalance. Compute it */ 5970 calculate_imbalance(env, &sds); 5971 return sds.busiest; 5972 5973 out_balanced: 5974 env->imbalance = 0; 5975 return NULL; 5976 } 5977 5978 /* 5979 * find_busiest_queue - find the busiest runqueue among the cpus in group. 5980 */ 5981 static struct rq *find_busiest_queue(struct lb_env *env, 5982 struct sched_group *group) 5983 { 5984 struct rq *busiest = NULL, *rq; 5985 unsigned long busiest_load = 0, busiest_power = 1; 5986 int i; 5987 5988 for_each_cpu_and(i, sched_group_cpus(group), env->cpus) { 5989 unsigned long power, capacity, wl; 5990 enum fbq_type rt; 5991 5992 rq = cpu_rq(i); 5993 rt = fbq_classify_rq(rq); 5994 5995 /* 5996 * We classify groups/runqueues into three groups: 5997 * - regular: there are !numa tasks 5998 * - remote: there are numa tasks that run on the 'wrong' node 5999 * - all: there is no distinction 6000 * 6001 * In order to avoid migrating ideally placed numa tasks, 6002 * ignore those when there's better options. 6003 * 6004 * If we ignore the actual busiest queue to migrate another 6005 * task, the next balance pass can still reduce the busiest 6006 * queue by moving tasks around inside the node. 6007 * 6008 * If we cannot move enough load due to this classification 6009 * the next pass will adjust the group classification and 6010 * allow migration of more tasks. 6011 * 6012 * Both cases only affect the total convergence complexity. 6013 */ 6014 if (rt > env->fbq_type) 6015 continue; 6016 6017 power = power_of(i); 6018 capacity = DIV_ROUND_CLOSEST(power, SCHED_POWER_SCALE); 6019 if (!capacity) 6020 capacity = fix_small_capacity(env->sd, group); 6021 6022 wl = weighted_cpuload(i); 6023 6024 /* 6025 * When comparing with imbalance, use weighted_cpuload() 6026 * which is not scaled with the cpu power. 6027 */ 6028 if (capacity && rq->nr_running == 1 && wl > env->imbalance) 6029 continue; 6030 6031 /* 6032 * For the load comparisons with the other cpu's, consider 6033 * the weighted_cpuload() scaled with the cpu power, so that 6034 * the load can be moved away from the cpu that is potentially 6035 * running at a lower capacity. 6036 * 6037 * Thus we're looking for max(wl_i / power_i), crosswise 6038 * multiplication to rid ourselves of the division works out 6039 * to: wl_i * power_j > wl_j * power_i; where j is our 6040 * previous maximum. 6041 */ 6042 if (wl * busiest_power > busiest_load * power) { 6043 busiest_load = wl; 6044 busiest_power = power; 6045 busiest = rq; 6046 } 6047 } 6048 6049 return busiest; 6050 } 6051 6052 /* 6053 * Max backoff if we encounter pinned tasks. Pretty arbitrary value, but 6054 * so long as it is large enough. 6055 */ 6056 #define MAX_PINNED_INTERVAL 512 6057 6058 /* Working cpumask for load_balance and load_balance_newidle. */ 6059 DEFINE_PER_CPU(cpumask_var_t, load_balance_mask); 6060 6061 static int need_active_balance(struct lb_env *env) 6062 { 6063 struct sched_domain *sd = env->sd; 6064 6065 if (env->idle == CPU_NEWLY_IDLE) { 6066 6067 /* 6068 * ASYM_PACKING needs to force migrate tasks from busy but 6069 * higher numbered CPUs in order to pack all tasks in the 6070 * lowest numbered CPUs. 6071 */ 6072 if ((sd->flags & SD_ASYM_PACKING) && env->src_cpu > env->dst_cpu) 6073 return 1; 6074 } 6075 6076 return unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2); 6077 } 6078 6079 static int active_load_balance_cpu_stop(void *data); 6080 6081 static int should_we_balance(struct lb_env *env) 6082 { 6083 struct sched_group *sg = env->sd->groups; 6084 struct cpumask *sg_cpus, *sg_mask; 6085 int cpu, balance_cpu = -1; 6086 6087 /* 6088 * In the newly idle case, we will allow all the cpu's 6089 * to do the newly idle load balance. 6090 */ 6091 if (env->idle == CPU_NEWLY_IDLE) 6092 return 1; 6093 6094 sg_cpus = sched_group_cpus(sg); 6095 sg_mask = sched_group_mask(sg); 6096 /* Try to find first idle cpu */ 6097 for_each_cpu_and(cpu, sg_cpus, env->cpus) { 6098 if (!cpumask_test_cpu(cpu, sg_mask) || !idle_cpu(cpu)) 6099 continue; 6100 6101 balance_cpu = cpu; 6102 break; 6103 } 6104 6105 if (balance_cpu == -1) 6106 balance_cpu = group_balance_cpu(sg); 6107 6108 /* 6109 * First idle cpu or the first cpu(busiest) in this sched group 6110 * is eligible for doing load balancing at this and above domains. 6111 */ 6112 return balance_cpu == env->dst_cpu; 6113 } 6114 6115 /* 6116 * Check this_cpu to ensure it is balanced within domain. Attempt to move 6117 * tasks if there is an imbalance. 6118 */ 6119 static int load_balance(int this_cpu, struct rq *this_rq, 6120 struct sched_domain *sd, enum cpu_idle_type idle, 6121 int *continue_balancing) 6122 { 6123 int ld_moved, cur_ld_moved, active_balance = 0; 6124 struct sched_domain *sd_parent = sd->parent; 6125 struct sched_group *group; 6126 struct rq *busiest; 6127 unsigned long flags; 6128 struct cpumask *cpus = __get_cpu_var(load_balance_mask); 6129 6130 struct lb_env env = { 6131 .sd = sd, 6132 .dst_cpu = this_cpu, 6133 .dst_rq = this_rq, 6134 .dst_grpmask = sched_group_cpus(sd->groups), 6135 .idle = idle, 6136 .loop_break = sched_nr_migrate_break, 6137 .cpus = cpus, 6138 .fbq_type = all, 6139 }; 6140 6141 /* 6142 * For NEWLY_IDLE load_balancing, we don't need to consider 6143 * other cpus in our group 6144 */ 6145 if (idle == CPU_NEWLY_IDLE) 6146 env.dst_grpmask = NULL; 6147 6148 cpumask_copy(cpus, cpu_active_mask); 6149 6150 schedstat_inc(sd, lb_count[idle]); 6151 6152 redo: 6153 if (!should_we_balance(&env)) { 6154 *continue_balancing = 0; 6155 goto out_balanced; 6156 } 6157 6158 group = find_busiest_group(&env); 6159 if (!group) { 6160 schedstat_inc(sd, lb_nobusyg[idle]); 6161 goto out_balanced; 6162 } 6163 6164 busiest = find_busiest_queue(&env, group); 6165 if (!busiest) { 6166 schedstat_inc(sd, lb_nobusyq[idle]); 6167 goto out_balanced; 6168 } 6169 6170 BUG_ON(busiest == env.dst_rq); 6171 6172 schedstat_add(sd, lb_imbalance[idle], env.imbalance); 6173 6174 ld_moved = 0; 6175 if (busiest->nr_running > 1) { 6176 /* 6177 * Attempt to move tasks. If find_busiest_group has found 6178 * an imbalance but busiest->nr_running <= 1, the group is 6179 * still unbalanced. ld_moved simply stays zero, so it is 6180 * correctly treated as an imbalance. 6181 */ 6182 env.flags |= LBF_ALL_PINNED; 6183 env.src_cpu = busiest->cpu; 6184 env.src_rq = busiest; 6185 env.loop_max = min(sysctl_sched_nr_migrate, busiest->nr_running); 6186 6187 more_balance: 6188 local_irq_save(flags); 6189 double_rq_lock(env.dst_rq, busiest); 6190 6191 /* 6192 * cur_ld_moved - load moved in current iteration 6193 * ld_moved - cumulative load moved across iterations 6194 */ 6195 cur_ld_moved = move_tasks(&env); 6196 ld_moved += cur_ld_moved; 6197 double_rq_unlock(env.dst_rq, busiest); 6198 local_irq_restore(flags); 6199 6200 /* 6201 * some other cpu did the load balance for us. 6202 */ 6203 if (cur_ld_moved && env.dst_cpu != smp_processor_id()) 6204 resched_cpu(env.dst_cpu); 6205 6206 if (env.flags & LBF_NEED_BREAK) { 6207 env.flags &= ~LBF_NEED_BREAK; 6208 goto more_balance; 6209 } 6210 6211 /* 6212 * Revisit (affine) tasks on src_cpu that couldn't be moved to 6213 * us and move them to an alternate dst_cpu in our sched_group 6214 * where they can run. The upper limit on how many times we 6215 * iterate on same src_cpu is dependent on number of cpus in our 6216 * sched_group. 6217 * 6218 * This changes load balance semantics a bit on who can move 6219 * load to a given_cpu. In addition to the given_cpu itself 6220 * (or a ilb_cpu acting on its behalf where given_cpu is 6221 * nohz-idle), we now have balance_cpu in a position to move 6222 * load to given_cpu. In rare situations, this may cause 6223 * conflicts (balance_cpu and given_cpu/ilb_cpu deciding 6224 * _independently_ and at _same_ time to move some load to 6225 * given_cpu) causing exceess load to be moved to given_cpu. 6226 * This however should not happen so much in practice and 6227 * moreover subsequent load balance cycles should correct the 6228 * excess load moved. 6229 */ 6230 if ((env.flags & LBF_DST_PINNED) && env.imbalance > 0) { 6231 6232 /* Prevent to re-select dst_cpu via env's cpus */ 6233 cpumask_clear_cpu(env.dst_cpu, env.cpus); 6234 6235 env.dst_rq = cpu_rq(env.new_dst_cpu); 6236 env.dst_cpu = env.new_dst_cpu; 6237 env.flags &= ~LBF_DST_PINNED; 6238 env.loop = 0; 6239 env.loop_break = sched_nr_migrate_break; 6240 6241 /* 6242 * Go back to "more_balance" rather than "redo" since we 6243 * need to continue with same src_cpu. 6244 */ 6245 goto more_balance; 6246 } 6247 6248 /* 6249 * We failed to reach balance because of affinity. 6250 */ 6251 if (sd_parent) { 6252 int *group_imbalance = &sd_parent->groups->sgp->imbalance; 6253 6254 if ((env.flags & LBF_SOME_PINNED) && env.imbalance > 0) { 6255 *group_imbalance = 1; 6256 } else if (*group_imbalance) 6257 *group_imbalance = 0; 6258 } 6259 6260 /* All tasks on this runqueue were pinned by CPU affinity */ 6261 if (unlikely(env.flags & LBF_ALL_PINNED)) { 6262 cpumask_clear_cpu(cpu_of(busiest), cpus); 6263 if (!cpumask_empty(cpus)) { 6264 env.loop = 0; 6265 env.loop_break = sched_nr_migrate_break; 6266 goto redo; 6267 } 6268 goto out_balanced; 6269 } 6270 } 6271 6272 if (!ld_moved) { 6273 schedstat_inc(sd, lb_failed[idle]); 6274 /* 6275 * Increment the failure counter only on periodic balance. 6276 * We do not want newidle balance, which can be very 6277 * frequent, pollute the failure counter causing 6278 * excessive cache_hot migrations and active balances. 6279 */ 6280 if (idle != CPU_NEWLY_IDLE) 6281 sd->nr_balance_failed++; 6282 6283 if (need_active_balance(&env)) { 6284 raw_spin_lock_irqsave(&busiest->lock, flags); 6285 6286 /* don't kick the active_load_balance_cpu_stop, 6287 * if the curr task on busiest cpu can't be 6288 * moved to this_cpu 6289 */ 6290 if (!cpumask_test_cpu(this_cpu, 6291 tsk_cpus_allowed(busiest->curr))) { 6292 raw_spin_unlock_irqrestore(&busiest->lock, 6293 flags); 6294 env.flags |= LBF_ALL_PINNED; 6295 goto out_one_pinned; 6296 } 6297 6298 /* 6299 * ->active_balance synchronizes accesses to 6300 * ->active_balance_work. Once set, it's cleared 6301 * only after active load balance is finished. 6302 */ 6303 if (!busiest->active_balance) { 6304 busiest->active_balance = 1; 6305 busiest->push_cpu = this_cpu; 6306 active_balance = 1; 6307 } 6308 raw_spin_unlock_irqrestore(&busiest->lock, flags); 6309 6310 if (active_balance) { 6311 stop_one_cpu_nowait(cpu_of(busiest), 6312 active_load_balance_cpu_stop, busiest, 6313 &busiest->active_balance_work); 6314 } 6315 6316 /* 6317 * We've kicked active balancing, reset the failure 6318 * counter. 6319 */ 6320 sd->nr_balance_failed = sd->cache_nice_tries+1; 6321 } 6322 } else 6323 sd->nr_balance_failed = 0; 6324 6325 if (likely(!active_balance)) { 6326 /* We were unbalanced, so reset the balancing interval */ 6327 sd->balance_interval = sd->min_interval; 6328 } else { 6329 /* 6330 * If we've begun active balancing, start to back off. This 6331 * case may not be covered by the all_pinned logic if there 6332 * is only 1 task on the busy runqueue (because we don't call 6333 * move_tasks). 6334 */ 6335 if (sd->balance_interval < sd->max_interval) 6336 sd->balance_interval *= 2; 6337 } 6338 6339 goto out; 6340 6341 out_balanced: 6342 schedstat_inc(sd, lb_balanced[idle]); 6343 6344 sd->nr_balance_failed = 0; 6345 6346 out_one_pinned: 6347 /* tune up the balancing interval */ 6348 if (((env.flags & LBF_ALL_PINNED) && 6349 sd->balance_interval < MAX_PINNED_INTERVAL) || 6350 (sd->balance_interval < sd->max_interval)) 6351 sd->balance_interval *= 2; 6352 6353 ld_moved = 0; 6354 out: 6355 return ld_moved; 6356 } 6357 6358 /* 6359 * idle_balance is called by schedule() if this_cpu is about to become 6360 * idle. Attempts to pull tasks from other CPUs. 6361 */ 6362 void idle_balance(int this_cpu, struct rq *this_rq) 6363 { 6364 struct sched_domain *sd; 6365 int pulled_task = 0; 6366 unsigned long next_balance = jiffies + HZ; 6367 u64 curr_cost = 0; 6368 6369 this_rq->idle_stamp = rq_clock(this_rq); 6370 6371 if (this_rq->avg_idle < sysctl_sched_migration_cost) 6372 return; 6373 6374 /* 6375 * Drop the rq->lock, but keep IRQ/preempt disabled. 6376 */ 6377 raw_spin_unlock(&this_rq->lock); 6378 6379 update_blocked_averages(this_cpu); 6380 rcu_read_lock(); 6381 for_each_domain(this_cpu, sd) { 6382 unsigned long interval; 6383 int continue_balancing = 1; 6384 u64 t0, domain_cost; 6385 6386 if (!(sd->flags & SD_LOAD_BALANCE)) 6387 continue; 6388 6389 if (this_rq->avg_idle < curr_cost + sd->max_newidle_lb_cost) 6390 break; 6391 6392 if (sd->flags & SD_BALANCE_NEWIDLE) { 6393 t0 = sched_clock_cpu(this_cpu); 6394 6395 /* If we've pulled tasks over stop searching: */ 6396 pulled_task = load_balance(this_cpu, this_rq, 6397 sd, CPU_NEWLY_IDLE, 6398 &continue_balancing); 6399 6400 domain_cost = sched_clock_cpu(this_cpu) - t0; 6401 if (domain_cost > sd->max_newidle_lb_cost) 6402 sd->max_newidle_lb_cost = domain_cost; 6403 6404 curr_cost += domain_cost; 6405 } 6406 6407 interval = msecs_to_jiffies(sd->balance_interval); 6408 if (time_after(next_balance, sd->last_balance + interval)) 6409 next_balance = sd->last_balance + interval; 6410 if (pulled_task) { 6411 this_rq->idle_stamp = 0; 6412 break; 6413 } 6414 } 6415 rcu_read_unlock(); 6416 6417 raw_spin_lock(&this_rq->lock); 6418 6419 if (pulled_task || time_after(jiffies, this_rq->next_balance)) { 6420 /* 6421 * We are going idle. next_balance may be set based on 6422 * a busy processor. So reset next_balance. 6423 */ 6424 this_rq->next_balance = next_balance; 6425 } 6426 6427 if (curr_cost > this_rq->max_idle_balance_cost) 6428 this_rq->max_idle_balance_cost = curr_cost; 6429 } 6430 6431 /* 6432 * active_load_balance_cpu_stop is run by cpu stopper. It pushes 6433 * running tasks off the busiest CPU onto idle CPUs. It requires at 6434 * least 1 task to be running on each physical CPU where possible, and 6435 * avoids physical / logical imbalances. 6436 */ 6437 static int active_load_balance_cpu_stop(void *data) 6438 { 6439 struct rq *busiest_rq = data; 6440 int busiest_cpu = cpu_of(busiest_rq); 6441 int target_cpu = busiest_rq->push_cpu; 6442 struct rq *target_rq = cpu_rq(target_cpu); 6443 struct sched_domain *sd; 6444 6445 raw_spin_lock_irq(&busiest_rq->lock); 6446 6447 /* make sure the requested cpu hasn't gone down in the meantime */ 6448 if (unlikely(busiest_cpu != smp_processor_id() || 6449 !busiest_rq->active_balance)) 6450 goto out_unlock; 6451 6452 /* Is there any task to move? */ 6453 if (busiest_rq->nr_running <= 1) 6454 goto out_unlock; 6455 6456 /* 6457 * This condition is "impossible", if it occurs 6458 * we need to fix it. Originally reported by 6459 * Bjorn Helgaas on a 128-cpu setup. 6460 */ 6461 BUG_ON(busiest_rq == target_rq); 6462 6463 /* move a task from busiest_rq to target_rq */ 6464 double_lock_balance(busiest_rq, target_rq); 6465 6466 /* Search for an sd spanning us and the target CPU. */ 6467 rcu_read_lock(); 6468 for_each_domain(target_cpu, sd) { 6469 if ((sd->flags & SD_LOAD_BALANCE) && 6470 cpumask_test_cpu(busiest_cpu, sched_domain_span(sd))) 6471 break; 6472 } 6473 6474 if (likely(sd)) { 6475 struct lb_env env = { 6476 .sd = sd, 6477 .dst_cpu = target_cpu, 6478 .dst_rq = target_rq, 6479 .src_cpu = busiest_rq->cpu, 6480 .src_rq = busiest_rq, 6481 .idle = CPU_IDLE, 6482 }; 6483 6484 schedstat_inc(sd, alb_count); 6485 6486 if (move_one_task(&env)) 6487 schedstat_inc(sd, alb_pushed); 6488 else 6489 schedstat_inc(sd, alb_failed); 6490 } 6491 rcu_read_unlock(); 6492 double_unlock_balance(busiest_rq, target_rq); 6493 out_unlock: 6494 busiest_rq->active_balance = 0; 6495 raw_spin_unlock_irq(&busiest_rq->lock); 6496 return 0; 6497 } 6498 6499 #ifdef CONFIG_NO_HZ_COMMON 6500 /* 6501 * idle load balancing details 6502 * - When one of the busy CPUs notice that there may be an idle rebalancing 6503 * needed, they will kick the idle load balancer, which then does idle 6504 * load balancing for all the idle CPUs. 6505 */ 6506 static struct { 6507 cpumask_var_t idle_cpus_mask; 6508 atomic_t nr_cpus; 6509 unsigned long next_balance; /* in jiffy units */ 6510 } nohz ____cacheline_aligned; 6511 6512 static inline int find_new_ilb(void) 6513 { 6514 int ilb = cpumask_first(nohz.idle_cpus_mask); 6515 6516 if (ilb < nr_cpu_ids && idle_cpu(ilb)) 6517 return ilb; 6518 6519 return nr_cpu_ids; 6520 } 6521 6522 /* 6523 * Kick a CPU to do the nohz balancing, if it is time for it. We pick the 6524 * nohz_load_balancer CPU (if there is one) otherwise fallback to any idle 6525 * CPU (if there is one). 6526 */ 6527 static void nohz_balancer_kick(void) 6528 { 6529 int ilb_cpu; 6530 6531 nohz.next_balance++; 6532 6533 ilb_cpu = find_new_ilb(); 6534 6535 if (ilb_cpu >= nr_cpu_ids) 6536 return; 6537 6538 if (test_and_set_bit(NOHZ_BALANCE_KICK, nohz_flags(ilb_cpu))) 6539 return; 6540 /* 6541 * Use smp_send_reschedule() instead of resched_cpu(). 6542 * This way we generate a sched IPI on the target cpu which 6543 * is idle. And the softirq performing nohz idle load balance 6544 * will be run before returning from the IPI. 6545 */ 6546 smp_send_reschedule(ilb_cpu); 6547 return; 6548 } 6549 6550 static inline void nohz_balance_exit_idle(int cpu) 6551 { 6552 if (unlikely(test_bit(NOHZ_TICK_STOPPED, nohz_flags(cpu)))) { 6553 cpumask_clear_cpu(cpu, nohz.idle_cpus_mask); 6554 atomic_dec(&nohz.nr_cpus); 6555 clear_bit(NOHZ_TICK_STOPPED, nohz_flags(cpu)); 6556 } 6557 } 6558 6559 static inline void set_cpu_sd_state_busy(void) 6560 { 6561 struct sched_domain *sd; 6562 int cpu = smp_processor_id(); 6563 6564 rcu_read_lock(); 6565 sd = rcu_dereference(per_cpu(sd_busy, cpu)); 6566 6567 if (!sd || !sd->nohz_idle) 6568 goto unlock; 6569 sd->nohz_idle = 0; 6570 6571 atomic_inc(&sd->groups->sgp->nr_busy_cpus); 6572 unlock: 6573 rcu_read_unlock(); 6574 } 6575 6576 void set_cpu_sd_state_idle(void) 6577 { 6578 struct sched_domain *sd; 6579 int cpu = smp_processor_id(); 6580 6581 rcu_read_lock(); 6582 sd = rcu_dereference(per_cpu(sd_busy, cpu)); 6583 6584 if (!sd || sd->nohz_idle) 6585 goto unlock; 6586 sd->nohz_idle = 1; 6587 6588 atomic_dec(&sd->groups->sgp->nr_busy_cpus); 6589 unlock: 6590 rcu_read_unlock(); 6591 } 6592 6593 /* 6594 * This routine will record that the cpu is going idle with tick stopped. 6595 * This info will be used in performing idle load balancing in the future. 6596 */ 6597 void nohz_balance_enter_idle(int cpu) 6598 { 6599 /* 6600 * If this cpu is going down, then nothing needs to be done. 6601 */ 6602 if (!cpu_active(cpu)) 6603 return; 6604 6605 if (test_bit(NOHZ_TICK_STOPPED, nohz_flags(cpu))) 6606 return; 6607 6608 cpumask_set_cpu(cpu, nohz.idle_cpus_mask); 6609 atomic_inc(&nohz.nr_cpus); 6610 set_bit(NOHZ_TICK_STOPPED, nohz_flags(cpu)); 6611 } 6612 6613 static int sched_ilb_notifier(struct notifier_block *nfb, 6614 unsigned long action, void *hcpu) 6615 { 6616 switch (action & ~CPU_TASKS_FROZEN) { 6617 case CPU_DYING: 6618 nohz_balance_exit_idle(smp_processor_id()); 6619 return NOTIFY_OK; 6620 default: 6621 return NOTIFY_DONE; 6622 } 6623 } 6624 #endif 6625 6626 static DEFINE_SPINLOCK(balancing); 6627 6628 /* 6629 * Scale the max load_balance interval with the number of CPUs in the system. 6630 * This trades load-balance latency on larger machines for less cross talk. 6631 */ 6632 void update_max_interval(void) 6633 { 6634 max_load_balance_interval = HZ*num_online_cpus()/10; 6635 } 6636 6637 /* 6638 * It checks each scheduling domain to see if it is due to be balanced, 6639 * and initiates a balancing operation if so. 6640 * 6641 * Balancing parameters are set up in init_sched_domains. 6642 */ 6643 static void rebalance_domains(struct rq *rq, enum cpu_idle_type idle) 6644 { 6645 int continue_balancing = 1; 6646 int cpu = rq->cpu; 6647 unsigned long interval; 6648 struct sched_domain *sd; 6649 /* Earliest time when we have to do rebalance again */ 6650 unsigned long next_balance = jiffies + 60*HZ; 6651 int update_next_balance = 0; 6652 int need_serialize, need_decay = 0; 6653 u64 max_cost = 0; 6654 6655 update_blocked_averages(cpu); 6656 6657 rcu_read_lock(); 6658 for_each_domain(cpu, sd) { 6659 /* 6660 * Decay the newidle max times here because this is a regular 6661 * visit to all the domains. Decay ~1% per second. 6662 */ 6663 if (time_after(jiffies, sd->next_decay_max_lb_cost)) { 6664 sd->max_newidle_lb_cost = 6665 (sd->max_newidle_lb_cost * 253) / 256; 6666 sd->next_decay_max_lb_cost = jiffies + HZ; 6667 need_decay = 1; 6668 } 6669 max_cost += sd->max_newidle_lb_cost; 6670 6671 if (!(sd->flags & SD_LOAD_BALANCE)) 6672 continue; 6673 6674 /* 6675 * Stop the load balance at this level. There is another 6676 * CPU in our sched group which is doing load balancing more 6677 * actively. 6678 */ 6679 if (!continue_balancing) { 6680 if (need_decay) 6681 continue; 6682 break; 6683 } 6684 6685 interval = sd->balance_interval; 6686 if (idle != CPU_IDLE) 6687 interval *= sd->busy_factor; 6688 6689 /* scale ms to jiffies */ 6690 interval = msecs_to_jiffies(interval); 6691 interval = clamp(interval, 1UL, max_load_balance_interval); 6692 6693 need_serialize = sd->flags & SD_SERIALIZE; 6694 6695 if (need_serialize) { 6696 if (!spin_trylock(&balancing)) 6697 goto out; 6698 } 6699 6700 if (time_after_eq(jiffies, sd->last_balance + interval)) { 6701 if (load_balance(cpu, rq, sd, idle, &continue_balancing)) { 6702 /* 6703 * The LBF_DST_PINNED logic could have changed 6704 * env->dst_cpu, so we can't know our idle 6705 * state even if we migrated tasks. Update it. 6706 */ 6707 idle = idle_cpu(cpu) ? CPU_IDLE : CPU_NOT_IDLE; 6708 } 6709 sd->last_balance = jiffies; 6710 } 6711 if (need_serialize) 6712 spin_unlock(&balancing); 6713 out: 6714 if (time_after(next_balance, sd->last_balance + interval)) { 6715 next_balance = sd->last_balance + interval; 6716 update_next_balance = 1; 6717 } 6718 } 6719 if (need_decay) { 6720 /* 6721 * Ensure the rq-wide value also decays but keep it at a 6722 * reasonable floor to avoid funnies with rq->avg_idle. 6723 */ 6724 rq->max_idle_balance_cost = 6725 max((u64)sysctl_sched_migration_cost, max_cost); 6726 } 6727 rcu_read_unlock(); 6728 6729 /* 6730 * next_balance will be updated only when there is a need. 6731 * When the cpu is attached to null domain for ex, it will not be 6732 * updated. 6733 */ 6734 if (likely(update_next_balance)) 6735 rq->next_balance = next_balance; 6736 } 6737 6738 #ifdef CONFIG_NO_HZ_COMMON 6739 /* 6740 * In CONFIG_NO_HZ_COMMON case, the idle balance kickee will do the 6741 * rebalancing for all the cpus for whom scheduler ticks are stopped. 6742 */ 6743 static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle) 6744 { 6745 int this_cpu = this_rq->cpu; 6746 struct rq *rq; 6747 int balance_cpu; 6748 6749 if (idle != CPU_IDLE || 6750 !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu))) 6751 goto end; 6752 6753 for_each_cpu(balance_cpu, nohz.idle_cpus_mask) { 6754 if (balance_cpu == this_cpu || !idle_cpu(balance_cpu)) 6755 continue; 6756 6757 /* 6758 * If this cpu gets work to do, stop the load balancing 6759 * work being done for other cpus. Next load 6760 * balancing owner will pick it up. 6761 */ 6762 if (need_resched()) 6763 break; 6764 6765 rq = cpu_rq(balance_cpu); 6766 6767 raw_spin_lock_irq(&rq->lock); 6768 update_rq_clock(rq); 6769 update_idle_cpu_load(rq); 6770 raw_spin_unlock_irq(&rq->lock); 6771 6772 rebalance_domains(rq, CPU_IDLE); 6773 6774 if (time_after(this_rq->next_balance, rq->next_balance)) 6775 this_rq->next_balance = rq->next_balance; 6776 } 6777 nohz.next_balance = this_rq->next_balance; 6778 end: 6779 clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu)); 6780 } 6781 6782 /* 6783 * Current heuristic for kicking the idle load balancer in the presence 6784 * of an idle cpu is the system. 6785 * - This rq has more than one task. 6786 * - At any scheduler domain level, this cpu's scheduler group has multiple 6787 * busy cpu's exceeding the group's power. 6788 * - For SD_ASYM_PACKING, if the lower numbered cpu's in the scheduler 6789 * domain span are idle. 6790 */ 6791 static inline int nohz_kick_needed(struct rq *rq) 6792 { 6793 unsigned long now = jiffies; 6794 struct sched_domain *sd; 6795 struct sched_group_power *sgp; 6796 int nr_busy, cpu = rq->cpu; 6797 6798 if (unlikely(rq->idle_balance)) 6799 return 0; 6800 6801 /* 6802 * We may be recently in ticked or tickless idle mode. At the first 6803 * busy tick after returning from idle, we will update the busy stats. 6804 */ 6805 set_cpu_sd_state_busy(); 6806 nohz_balance_exit_idle(cpu); 6807 6808 /* 6809 * None are in tickless mode and hence no need for NOHZ idle load 6810 * balancing. 6811 */ 6812 if (likely(!atomic_read(&nohz.nr_cpus))) 6813 return 0; 6814 6815 if (time_before(now, nohz.next_balance)) 6816 return 0; 6817 6818 if (rq->nr_running >= 2) 6819 goto need_kick; 6820 6821 rcu_read_lock(); 6822 sd = rcu_dereference(per_cpu(sd_busy, cpu)); 6823 6824 if (sd) { 6825 sgp = sd->groups->sgp; 6826 nr_busy = atomic_read(&sgp->nr_busy_cpus); 6827 6828 if (nr_busy > 1) 6829 goto need_kick_unlock; 6830 } 6831 6832 sd = rcu_dereference(per_cpu(sd_asym, cpu)); 6833 6834 if (sd && (cpumask_first_and(nohz.idle_cpus_mask, 6835 sched_domain_span(sd)) < cpu)) 6836 goto need_kick_unlock; 6837 6838 rcu_read_unlock(); 6839 return 0; 6840 6841 need_kick_unlock: 6842 rcu_read_unlock(); 6843 need_kick: 6844 return 1; 6845 } 6846 #else 6847 static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle) { } 6848 #endif 6849 6850 /* 6851 * run_rebalance_domains is triggered when needed from the scheduler tick. 6852 * Also triggered for nohz idle balancing (with nohz_balancing_kick set). 6853 */ 6854 static void run_rebalance_domains(struct softirq_action *h) 6855 { 6856 struct rq *this_rq = this_rq(); 6857 enum cpu_idle_type idle = this_rq->idle_balance ? 6858 CPU_IDLE : CPU_NOT_IDLE; 6859 6860 rebalance_domains(this_rq, idle); 6861 6862 /* 6863 * If this cpu has a pending nohz_balance_kick, then do the 6864 * balancing on behalf of the other idle cpus whose ticks are 6865 * stopped. 6866 */ 6867 nohz_idle_balance(this_rq, idle); 6868 } 6869 6870 static inline int on_null_domain(struct rq *rq) 6871 { 6872 return !rcu_dereference_sched(rq->sd); 6873 } 6874 6875 /* 6876 * Trigger the SCHED_SOFTIRQ if it is time to do periodic load balancing. 6877 */ 6878 void trigger_load_balance(struct rq *rq) 6879 { 6880 /* Don't need to rebalance while attached to NULL domain */ 6881 if (unlikely(on_null_domain(rq))) 6882 return; 6883 6884 if (time_after_eq(jiffies, rq->next_balance)) 6885 raise_softirq(SCHED_SOFTIRQ); 6886 #ifdef CONFIG_NO_HZ_COMMON 6887 if (nohz_kick_needed(rq)) 6888 nohz_balancer_kick(); 6889 #endif 6890 } 6891 6892 static void rq_online_fair(struct rq *rq) 6893 { 6894 update_sysctl(); 6895 } 6896 6897 static void rq_offline_fair(struct rq *rq) 6898 { 6899 update_sysctl(); 6900 6901 /* Ensure any throttled groups are reachable by pick_next_task */ 6902 unthrottle_offline_cfs_rqs(rq); 6903 } 6904 6905 #endif /* CONFIG_SMP */ 6906 6907 /* 6908 * scheduler tick hitting a task of our scheduling class: 6909 */ 6910 static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued) 6911 { 6912 struct cfs_rq *cfs_rq; 6913 struct sched_entity *se = &curr->se; 6914 6915 for_each_sched_entity(se) { 6916 cfs_rq = cfs_rq_of(se); 6917 entity_tick(cfs_rq, se, queued); 6918 } 6919 6920 if (numabalancing_enabled) 6921 task_tick_numa(rq, curr); 6922 6923 update_rq_runnable_avg(rq, 1); 6924 } 6925 6926 /* 6927 * called on fork with the child task as argument from the parent's context 6928 * - child not yet on the tasklist 6929 * - preemption disabled 6930 */ 6931 static void task_fork_fair(struct task_struct *p) 6932 { 6933 struct cfs_rq *cfs_rq; 6934 struct sched_entity *se = &p->se, *curr; 6935 int this_cpu = smp_processor_id(); 6936 struct rq *rq = this_rq(); 6937 unsigned long flags; 6938 6939 raw_spin_lock_irqsave(&rq->lock, flags); 6940 6941 update_rq_clock(rq); 6942 6943 cfs_rq = task_cfs_rq(current); 6944 curr = cfs_rq->curr; 6945 6946 /* 6947 * Not only the cpu but also the task_group of the parent might have 6948 * been changed after parent->se.parent,cfs_rq were copied to 6949 * child->se.parent,cfs_rq. So call __set_task_cpu() to make those 6950 * of child point to valid ones. 6951 */ 6952 rcu_read_lock(); 6953 __set_task_cpu(p, this_cpu); 6954 rcu_read_unlock(); 6955 6956 update_curr(cfs_rq); 6957 6958 if (curr) 6959 se->vruntime = curr->vruntime; 6960 place_entity(cfs_rq, se, 1); 6961 6962 if (sysctl_sched_child_runs_first && curr && entity_before(curr, se)) { 6963 /* 6964 * Upon rescheduling, sched_class::put_prev_task() will place 6965 * 'current' within the tree based on its new key value. 6966 */ 6967 swap(curr->vruntime, se->vruntime); 6968 resched_task(rq->curr); 6969 } 6970 6971 se->vruntime -= cfs_rq->min_vruntime; 6972 6973 raw_spin_unlock_irqrestore(&rq->lock, flags); 6974 } 6975 6976 /* 6977 * Priority of the task has changed. Check to see if we preempt 6978 * the current task. 6979 */ 6980 static void 6981 prio_changed_fair(struct rq *rq, struct task_struct *p, int oldprio) 6982 { 6983 if (!p->se.on_rq) 6984 return; 6985 6986 /* 6987 * Reschedule if we are currently running on this runqueue and 6988 * our priority decreased, or if we are not currently running on 6989 * this runqueue and our priority is higher than the current's 6990 */ 6991 if (rq->curr == p) { 6992 if (p->prio > oldprio) 6993 resched_task(rq->curr); 6994 } else 6995 check_preempt_curr(rq, p, 0); 6996 } 6997 6998 static void switched_from_fair(struct rq *rq, struct task_struct *p) 6999 { 7000 struct sched_entity *se = &p->se; 7001 struct cfs_rq *cfs_rq = cfs_rq_of(se); 7002 7003 /* 7004 * Ensure the task's vruntime is normalized, so that when it's 7005 * switched back to the fair class the enqueue_entity(.flags=0) will 7006 * do the right thing. 7007 * 7008 * If it's on_rq, then the dequeue_entity(.flags=0) will already 7009 * have normalized the vruntime, if it's !on_rq, then only when 7010 * the task is sleeping will it still have non-normalized vruntime. 7011 */ 7012 if (!p->on_rq && p->state != TASK_RUNNING) { 7013 /* 7014 * Fix up our vruntime so that the current sleep doesn't 7015 * cause 'unlimited' sleep bonus. 7016 */ 7017 place_entity(cfs_rq, se, 0); 7018 se->vruntime -= cfs_rq->min_vruntime; 7019 } 7020 7021 #ifdef CONFIG_SMP 7022 /* 7023 * Remove our load from contribution when we leave sched_fair 7024 * and ensure we don't carry in an old decay_count if we 7025 * switch back. 7026 */ 7027 if (se->avg.decay_count) { 7028 __synchronize_entity_decay(se); 7029 subtract_blocked_load_contrib(cfs_rq, se->avg.load_avg_contrib); 7030 } 7031 #endif 7032 } 7033 7034 /* 7035 * We switched to the sched_fair class. 7036 */ 7037 static void switched_to_fair(struct rq *rq, struct task_struct *p) 7038 { 7039 if (!p->se.on_rq) 7040 return; 7041 7042 /* 7043 * We were most likely switched from sched_rt, so 7044 * kick off the schedule if running, otherwise just see 7045 * if we can still preempt the current task. 7046 */ 7047 if (rq->curr == p) 7048 resched_task(rq->curr); 7049 else 7050 check_preempt_curr(rq, p, 0); 7051 } 7052 7053 /* Account for a task changing its policy or group. 7054 * 7055 * This routine is mostly called to set cfs_rq->curr field when a task 7056 * migrates between groups/classes. 7057 */ 7058 static void set_curr_task_fair(struct rq *rq) 7059 { 7060 struct sched_entity *se = &rq->curr->se; 7061 7062 for_each_sched_entity(se) { 7063 struct cfs_rq *cfs_rq = cfs_rq_of(se); 7064 7065 set_next_entity(cfs_rq, se); 7066 /* ensure bandwidth has been allocated on our new cfs_rq */ 7067 account_cfs_rq_runtime(cfs_rq, 0); 7068 } 7069 } 7070 7071 void init_cfs_rq(struct cfs_rq *cfs_rq) 7072 { 7073 cfs_rq->tasks_timeline = RB_ROOT; 7074 cfs_rq->min_vruntime = (u64)(-(1LL << 20)); 7075 #ifndef CONFIG_64BIT 7076 cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime; 7077 #endif 7078 #ifdef CONFIG_SMP 7079 atomic64_set(&cfs_rq->decay_counter, 1); 7080 atomic_long_set(&cfs_rq->removed_load, 0); 7081 #endif 7082 } 7083 7084 #ifdef CONFIG_FAIR_GROUP_SCHED 7085 static void task_move_group_fair(struct task_struct *p, int on_rq) 7086 { 7087 struct cfs_rq *cfs_rq; 7088 /* 7089 * If the task was not on the rq at the time of this cgroup movement 7090 * it must have been asleep, sleeping tasks keep their ->vruntime 7091 * absolute on their old rq until wakeup (needed for the fair sleeper 7092 * bonus in place_entity()). 7093 * 7094 * If it was on the rq, we've just 'preempted' it, which does convert 7095 * ->vruntime to a relative base. 7096 * 7097 * Make sure both cases convert their relative position when migrating 7098 * to another cgroup's rq. This does somewhat interfere with the 7099 * fair sleeper stuff for the first placement, but who cares. 7100 */ 7101 /* 7102 * When !on_rq, vruntime of the task has usually NOT been normalized. 7103 * But there are some cases where it has already been normalized: 7104 * 7105 * - Moving a forked child which is waiting for being woken up by 7106 * wake_up_new_task(). 7107 * - Moving a task which has been woken up by try_to_wake_up() and 7108 * waiting for actually being woken up by sched_ttwu_pending(). 7109 * 7110 * To prevent boost or penalty in the new cfs_rq caused by delta 7111 * min_vruntime between the two cfs_rqs, we skip vruntime adjustment. 7112 */ 7113 if (!on_rq && (!p->se.sum_exec_runtime || p->state == TASK_WAKING)) 7114 on_rq = 1; 7115 7116 if (!on_rq) 7117 p->se.vruntime -= cfs_rq_of(&p->se)->min_vruntime; 7118 set_task_rq(p, task_cpu(p)); 7119 if (!on_rq) { 7120 cfs_rq = cfs_rq_of(&p->se); 7121 p->se.vruntime += cfs_rq->min_vruntime; 7122 #ifdef CONFIG_SMP 7123 /* 7124 * migrate_task_rq_fair() will have removed our previous 7125 * contribution, but we must synchronize for ongoing future 7126 * decay. 7127 */ 7128 p->se.avg.decay_count = atomic64_read(&cfs_rq->decay_counter); 7129 cfs_rq->blocked_load_avg += p->se.avg.load_avg_contrib; 7130 #endif 7131 } 7132 } 7133 7134 void free_fair_sched_group(struct task_group *tg) 7135 { 7136 int i; 7137 7138 destroy_cfs_bandwidth(tg_cfs_bandwidth(tg)); 7139 7140 for_each_possible_cpu(i) { 7141 if (tg->cfs_rq) 7142 kfree(tg->cfs_rq[i]); 7143 if (tg->se) 7144 kfree(tg->se[i]); 7145 } 7146 7147 kfree(tg->cfs_rq); 7148 kfree(tg->se); 7149 } 7150 7151 int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent) 7152 { 7153 struct cfs_rq *cfs_rq; 7154 struct sched_entity *se; 7155 int i; 7156 7157 tg->cfs_rq = kzalloc(sizeof(cfs_rq) * nr_cpu_ids, GFP_KERNEL); 7158 if (!tg->cfs_rq) 7159 goto err; 7160 tg->se = kzalloc(sizeof(se) * nr_cpu_ids, GFP_KERNEL); 7161 if (!tg->se) 7162 goto err; 7163 7164 tg->shares = NICE_0_LOAD; 7165 7166 init_cfs_bandwidth(tg_cfs_bandwidth(tg)); 7167 7168 for_each_possible_cpu(i) { 7169 cfs_rq = kzalloc_node(sizeof(struct cfs_rq), 7170 GFP_KERNEL, cpu_to_node(i)); 7171 if (!cfs_rq) 7172 goto err; 7173 7174 se = kzalloc_node(sizeof(struct sched_entity), 7175 GFP_KERNEL, cpu_to_node(i)); 7176 if (!se) 7177 goto err_free_rq; 7178 7179 init_cfs_rq(cfs_rq); 7180 init_tg_cfs_entry(tg, cfs_rq, se, i, parent->se[i]); 7181 } 7182 7183 return 1; 7184 7185 err_free_rq: 7186 kfree(cfs_rq); 7187 err: 7188 return 0; 7189 } 7190 7191 void unregister_fair_sched_group(struct task_group *tg, int cpu) 7192 { 7193 struct rq *rq = cpu_rq(cpu); 7194 unsigned long flags; 7195 7196 /* 7197 * Only empty task groups can be destroyed; so we can speculatively 7198 * check on_list without danger of it being re-added. 7199 */ 7200 if (!tg->cfs_rq[cpu]->on_list) 7201 return; 7202 7203 raw_spin_lock_irqsave(&rq->lock, flags); 7204 list_del_leaf_cfs_rq(tg->cfs_rq[cpu]); 7205 raw_spin_unlock_irqrestore(&rq->lock, flags); 7206 } 7207 7208 void init_tg_cfs_entry(struct task_group *tg, struct cfs_rq *cfs_rq, 7209 struct sched_entity *se, int cpu, 7210 struct sched_entity *parent) 7211 { 7212 struct rq *rq = cpu_rq(cpu); 7213 7214 cfs_rq->tg = tg; 7215 cfs_rq->rq = rq; 7216 init_cfs_rq_runtime(cfs_rq); 7217 7218 tg->cfs_rq[cpu] = cfs_rq; 7219 tg->se[cpu] = se; 7220 7221 /* se could be NULL for root_task_group */ 7222 if (!se) 7223 return; 7224 7225 if (!parent) 7226 se->cfs_rq = &rq->cfs; 7227 else 7228 se->cfs_rq = parent->my_q; 7229 7230 se->my_q = cfs_rq; 7231 /* guarantee group entities always have weight */ 7232 update_load_set(&se->load, NICE_0_LOAD); 7233 se->parent = parent; 7234 } 7235 7236 static DEFINE_MUTEX(shares_mutex); 7237 7238 int sched_group_set_shares(struct task_group *tg, unsigned long shares) 7239 { 7240 int i; 7241 unsigned long flags; 7242 7243 /* 7244 * We can't change the weight of the root cgroup. 7245 */ 7246 if (!tg->se[0]) 7247 return -EINVAL; 7248 7249 shares = clamp(shares, scale_load(MIN_SHARES), scale_load(MAX_SHARES)); 7250 7251 mutex_lock(&shares_mutex); 7252 if (tg->shares == shares) 7253 goto done; 7254 7255 tg->shares = shares; 7256 for_each_possible_cpu(i) { 7257 struct rq *rq = cpu_rq(i); 7258 struct sched_entity *se; 7259 7260 se = tg->se[i]; 7261 /* Propagate contribution to hierarchy */ 7262 raw_spin_lock_irqsave(&rq->lock, flags); 7263 7264 /* Possible calls to update_curr() need rq clock */ 7265 update_rq_clock(rq); 7266 for_each_sched_entity(se) 7267 update_cfs_shares(group_cfs_rq(se)); 7268 raw_spin_unlock_irqrestore(&rq->lock, flags); 7269 } 7270 7271 done: 7272 mutex_unlock(&shares_mutex); 7273 return 0; 7274 } 7275 #else /* CONFIG_FAIR_GROUP_SCHED */ 7276 7277 void free_fair_sched_group(struct task_group *tg) { } 7278 7279 int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent) 7280 { 7281 return 1; 7282 } 7283 7284 void unregister_fair_sched_group(struct task_group *tg, int cpu) { } 7285 7286 #endif /* CONFIG_FAIR_GROUP_SCHED */ 7287 7288 7289 static unsigned int get_rr_interval_fair(struct rq *rq, struct task_struct *task) 7290 { 7291 struct sched_entity *se = &task->se; 7292 unsigned int rr_interval = 0; 7293 7294 /* 7295 * Time slice is 0 for SCHED_OTHER tasks that are on an otherwise 7296 * idle runqueue: 7297 */ 7298 if (rq->cfs.load.weight) 7299 rr_interval = NS_TO_JIFFIES(sched_slice(cfs_rq_of(se), se)); 7300 7301 return rr_interval; 7302 } 7303 7304 /* 7305 * All the scheduling class methods: 7306 */ 7307 const struct sched_class fair_sched_class = { 7308 .next = &idle_sched_class, 7309 .enqueue_task = enqueue_task_fair, 7310 .dequeue_task = dequeue_task_fair, 7311 .yield_task = yield_task_fair, 7312 .yield_to_task = yield_to_task_fair, 7313 7314 .check_preempt_curr = check_preempt_wakeup, 7315 7316 .pick_next_task = pick_next_task_fair, 7317 .put_prev_task = put_prev_task_fair, 7318 7319 #ifdef CONFIG_SMP 7320 .select_task_rq = select_task_rq_fair, 7321 .migrate_task_rq = migrate_task_rq_fair, 7322 7323 .rq_online = rq_online_fair, 7324 .rq_offline = rq_offline_fair, 7325 7326 .task_waking = task_waking_fair, 7327 #endif 7328 7329 .set_curr_task = set_curr_task_fair, 7330 .task_tick = task_tick_fair, 7331 .task_fork = task_fork_fair, 7332 7333 .prio_changed = prio_changed_fair, 7334 .switched_from = switched_from_fair, 7335 .switched_to = switched_to_fair, 7336 7337 .get_rr_interval = get_rr_interval_fair, 7338 7339 #ifdef CONFIG_FAIR_GROUP_SCHED 7340 .task_move_group = task_move_group_fair, 7341 #endif 7342 }; 7343 7344 #ifdef CONFIG_SCHED_DEBUG 7345 void print_cfs_stats(struct seq_file *m, int cpu) 7346 { 7347 struct cfs_rq *cfs_rq; 7348 7349 rcu_read_lock(); 7350 for_each_leaf_cfs_rq(cpu_rq(cpu), cfs_rq) 7351 print_cfs_rq(m, cpu, cfs_rq); 7352 rcu_read_unlock(); 7353 } 7354 #endif 7355 7356 __init void init_sched_fair_class(void) 7357 { 7358 #ifdef CONFIG_SMP 7359 open_softirq(SCHED_SOFTIRQ, run_rebalance_domains); 7360 7361 #ifdef CONFIG_NO_HZ_COMMON 7362 nohz.next_balance = jiffies; 7363 zalloc_cpumask_var(&nohz.idle_cpus_mask, GFP_NOWAIT); 7364 cpu_notifier(sched_ilb_notifier, 0); 7365 #endif 7366 #endif /* SMP */ 7367 7368 } 7369