1 2 #include <linux/sched.h> 3 #include <linux/sched/sysctl.h> 4 #include <linux/sched/rt.h> 5 #include <linux/u64_stats_sync.h> 6 #include <linux/sched/deadline.h> 7 #include <linux/binfmts.h> 8 #include <linux/mutex.h> 9 #include <linux/spinlock.h> 10 #include <linux/stop_machine.h> 11 #include <linux/irq_work.h> 12 #include <linux/tick.h> 13 #include <linux/slab.h> 14 15 #include "cpupri.h" 16 #include "cpudeadline.h" 17 #include "cpuacct.h" 18 19 #ifdef CONFIG_SCHED_DEBUG 20 #define SCHED_WARN_ON(x) WARN_ONCE(x, #x) 21 #else 22 #define SCHED_WARN_ON(x) ((void)(x)) 23 #endif 24 25 struct rq; 26 struct cpuidle_state; 27 28 /* task_struct::on_rq states: */ 29 #define TASK_ON_RQ_QUEUED 1 30 #define TASK_ON_RQ_MIGRATING 2 31 32 extern __read_mostly int scheduler_running; 33 34 extern unsigned long calc_load_update; 35 extern atomic_long_t calc_load_tasks; 36 37 extern void calc_global_load_tick(struct rq *this_rq); 38 extern long calc_load_fold_active(struct rq *this_rq, long adjust); 39 40 #ifdef CONFIG_SMP 41 extern void cpu_load_update_active(struct rq *this_rq); 42 #else 43 static inline void cpu_load_update_active(struct rq *this_rq) { } 44 #endif 45 46 /* 47 * Helpers for converting nanosecond timing to jiffy resolution 48 */ 49 #define NS_TO_JIFFIES(TIME) ((unsigned long)(TIME) / (NSEC_PER_SEC / HZ)) 50 51 /* 52 * Increase resolution of nice-level calculations for 64-bit architectures. 53 * The extra resolution improves shares distribution and load balancing of 54 * low-weight task groups (eg. nice +19 on an autogroup), deeper taskgroup 55 * hierarchies, especially on larger systems. This is not a user-visible change 56 * and does not change the user-interface for setting shares/weights. 57 * 58 * We increase resolution only if we have enough bits to allow this increased 59 * resolution (i.e. 64bit). The costs for increasing resolution when 32bit are 60 * pretty high and the returns do not justify the increased costs. 61 * 62 * Really only required when CONFIG_FAIR_GROUP_SCHED is also set, but to 63 * increase coverage and consistency always enable it on 64bit platforms. 64 */ 65 #ifdef CONFIG_64BIT 66 # define NICE_0_LOAD_SHIFT (SCHED_FIXEDPOINT_SHIFT + SCHED_FIXEDPOINT_SHIFT) 67 # define scale_load(w) ((w) << SCHED_FIXEDPOINT_SHIFT) 68 # define scale_load_down(w) ((w) >> SCHED_FIXEDPOINT_SHIFT) 69 #else 70 # define NICE_0_LOAD_SHIFT (SCHED_FIXEDPOINT_SHIFT) 71 # define scale_load(w) (w) 72 # define scale_load_down(w) (w) 73 #endif 74 75 /* 76 * Task weight (visible to users) and its load (invisible to users) have 77 * independent resolution, but they should be well calibrated. We use 78 * scale_load() and scale_load_down(w) to convert between them. The 79 * following must be true: 80 * 81 * scale_load(sched_prio_to_weight[USER_PRIO(NICE_TO_PRIO(0))]) == NICE_0_LOAD 82 * 83 */ 84 #define NICE_0_LOAD (1L << NICE_0_LOAD_SHIFT) 85 86 /* 87 * Single value that decides SCHED_DEADLINE internal math precision. 88 * 10 -> just above 1us 89 * 9 -> just above 0.5us 90 */ 91 #define DL_SCALE (10) 92 93 /* 94 * These are the 'tuning knobs' of the scheduler: 95 */ 96 97 /* 98 * single value that denotes runtime == period, ie unlimited time. 99 */ 100 #define RUNTIME_INF ((u64)~0ULL) 101 102 static inline int idle_policy(int policy) 103 { 104 return policy == SCHED_IDLE; 105 } 106 static inline int fair_policy(int policy) 107 { 108 return policy == SCHED_NORMAL || policy == SCHED_BATCH; 109 } 110 111 static inline int rt_policy(int policy) 112 { 113 return policy == SCHED_FIFO || policy == SCHED_RR; 114 } 115 116 static inline int dl_policy(int policy) 117 { 118 return policy == SCHED_DEADLINE; 119 } 120 static inline bool valid_policy(int policy) 121 { 122 return idle_policy(policy) || fair_policy(policy) || 123 rt_policy(policy) || dl_policy(policy); 124 } 125 126 static inline int task_has_rt_policy(struct task_struct *p) 127 { 128 return rt_policy(p->policy); 129 } 130 131 static inline int task_has_dl_policy(struct task_struct *p) 132 { 133 return dl_policy(p->policy); 134 } 135 136 /* 137 * Tells if entity @a should preempt entity @b. 138 */ 139 static inline bool 140 dl_entity_preempt(struct sched_dl_entity *a, struct sched_dl_entity *b) 141 { 142 return dl_time_before(a->deadline, b->deadline); 143 } 144 145 /* 146 * This is the priority-queue data structure of the RT scheduling class: 147 */ 148 struct rt_prio_array { 149 DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */ 150 struct list_head queue[MAX_RT_PRIO]; 151 }; 152 153 struct rt_bandwidth { 154 /* nests inside the rq lock: */ 155 raw_spinlock_t rt_runtime_lock; 156 ktime_t rt_period; 157 u64 rt_runtime; 158 struct hrtimer rt_period_timer; 159 unsigned int rt_period_active; 160 }; 161 162 void __dl_clear_params(struct task_struct *p); 163 164 /* 165 * To keep the bandwidth of -deadline tasks and groups under control 166 * we need some place where: 167 * - store the maximum -deadline bandwidth of the system (the group); 168 * - cache the fraction of that bandwidth that is currently allocated. 169 * 170 * This is all done in the data structure below. It is similar to the 171 * one used for RT-throttling (rt_bandwidth), with the main difference 172 * that, since here we are only interested in admission control, we 173 * do not decrease any runtime while the group "executes", neither we 174 * need a timer to replenish it. 175 * 176 * With respect to SMP, the bandwidth is given on a per-CPU basis, 177 * meaning that: 178 * - dl_bw (< 100%) is the bandwidth of the system (group) on each CPU; 179 * - dl_total_bw array contains, in the i-eth element, the currently 180 * allocated bandwidth on the i-eth CPU. 181 * Moreover, groups consume bandwidth on each CPU, while tasks only 182 * consume bandwidth on the CPU they're running on. 183 * Finally, dl_total_bw_cpu is used to cache the index of dl_total_bw 184 * that will be shown the next time the proc or cgroup controls will 185 * be red. It on its turn can be changed by writing on its own 186 * control. 187 */ 188 struct dl_bandwidth { 189 raw_spinlock_t dl_runtime_lock; 190 u64 dl_runtime; 191 u64 dl_period; 192 }; 193 194 static inline int dl_bandwidth_enabled(void) 195 { 196 return sysctl_sched_rt_runtime >= 0; 197 } 198 199 extern struct dl_bw *dl_bw_of(int i); 200 201 struct dl_bw { 202 raw_spinlock_t lock; 203 u64 bw, total_bw; 204 }; 205 206 static inline 207 void __dl_clear(struct dl_bw *dl_b, u64 tsk_bw) 208 { 209 dl_b->total_bw -= tsk_bw; 210 } 211 212 static inline 213 void __dl_add(struct dl_bw *dl_b, u64 tsk_bw) 214 { 215 dl_b->total_bw += tsk_bw; 216 } 217 218 static inline 219 bool __dl_overflow(struct dl_bw *dl_b, int cpus, u64 old_bw, u64 new_bw) 220 { 221 return dl_b->bw != -1 && 222 dl_b->bw * cpus < dl_b->total_bw - old_bw + new_bw; 223 } 224 225 extern struct mutex sched_domains_mutex; 226 227 #ifdef CONFIG_CGROUP_SCHED 228 229 #include <linux/cgroup.h> 230 231 struct cfs_rq; 232 struct rt_rq; 233 234 extern struct list_head task_groups; 235 236 struct cfs_bandwidth { 237 #ifdef CONFIG_CFS_BANDWIDTH 238 raw_spinlock_t lock; 239 ktime_t period; 240 u64 quota, runtime; 241 s64 hierarchical_quota; 242 u64 runtime_expires; 243 244 int idle, period_active; 245 struct hrtimer period_timer, slack_timer; 246 struct list_head throttled_cfs_rq; 247 248 /* statistics */ 249 int nr_periods, nr_throttled; 250 u64 throttled_time; 251 #endif 252 }; 253 254 /* task group related information */ 255 struct task_group { 256 struct cgroup_subsys_state css; 257 258 #ifdef CONFIG_FAIR_GROUP_SCHED 259 /* schedulable entities of this group on each cpu */ 260 struct sched_entity **se; 261 /* runqueue "owned" by this group on each cpu */ 262 struct cfs_rq **cfs_rq; 263 unsigned long shares; 264 265 #ifdef CONFIG_SMP 266 /* 267 * load_avg can be heavily contended at clock tick time, so put 268 * it in its own cacheline separated from the fields above which 269 * will also be accessed at each tick. 270 */ 271 atomic_long_t load_avg ____cacheline_aligned; 272 #endif 273 #endif 274 275 #ifdef CONFIG_RT_GROUP_SCHED 276 struct sched_rt_entity **rt_se; 277 struct rt_rq **rt_rq; 278 279 struct rt_bandwidth rt_bandwidth; 280 #endif 281 282 struct rcu_head rcu; 283 struct list_head list; 284 285 struct task_group *parent; 286 struct list_head siblings; 287 struct list_head children; 288 289 #ifdef CONFIG_SCHED_AUTOGROUP 290 struct autogroup *autogroup; 291 #endif 292 293 struct cfs_bandwidth cfs_bandwidth; 294 }; 295 296 #ifdef CONFIG_FAIR_GROUP_SCHED 297 #define ROOT_TASK_GROUP_LOAD NICE_0_LOAD 298 299 /* 300 * A weight of 0 or 1 can cause arithmetics problems. 301 * A weight of a cfs_rq is the sum of weights of which entities 302 * are queued on this cfs_rq, so a weight of a entity should not be 303 * too large, so as the shares value of a task group. 304 * (The default weight is 1024 - so there's no practical 305 * limitation from this.) 306 */ 307 #define MIN_SHARES (1UL << 1) 308 #define MAX_SHARES (1UL << 18) 309 #endif 310 311 typedef int (*tg_visitor)(struct task_group *, void *); 312 313 extern int walk_tg_tree_from(struct task_group *from, 314 tg_visitor down, tg_visitor up, void *data); 315 316 /* 317 * Iterate the full tree, calling @down when first entering a node and @up when 318 * leaving it for the final time. 319 * 320 * Caller must hold rcu_lock or sufficient equivalent. 321 */ 322 static inline int walk_tg_tree(tg_visitor down, tg_visitor up, void *data) 323 { 324 return walk_tg_tree_from(&root_task_group, down, up, data); 325 } 326 327 extern int tg_nop(struct task_group *tg, void *data); 328 329 extern void free_fair_sched_group(struct task_group *tg); 330 extern int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent); 331 extern void online_fair_sched_group(struct task_group *tg); 332 extern void unregister_fair_sched_group(struct task_group *tg); 333 extern void init_tg_cfs_entry(struct task_group *tg, struct cfs_rq *cfs_rq, 334 struct sched_entity *se, int cpu, 335 struct sched_entity *parent); 336 extern void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b); 337 338 extern void __refill_cfs_bandwidth_runtime(struct cfs_bandwidth *cfs_b); 339 extern void start_cfs_bandwidth(struct cfs_bandwidth *cfs_b); 340 extern void unthrottle_cfs_rq(struct cfs_rq *cfs_rq); 341 342 extern void free_rt_sched_group(struct task_group *tg); 343 extern int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent); 344 extern void init_tg_rt_entry(struct task_group *tg, struct rt_rq *rt_rq, 345 struct sched_rt_entity *rt_se, int cpu, 346 struct sched_rt_entity *parent); 347 348 extern struct task_group *sched_create_group(struct task_group *parent); 349 extern void sched_online_group(struct task_group *tg, 350 struct task_group *parent); 351 extern void sched_destroy_group(struct task_group *tg); 352 extern void sched_offline_group(struct task_group *tg); 353 354 extern void sched_move_task(struct task_struct *tsk); 355 356 #ifdef CONFIG_FAIR_GROUP_SCHED 357 extern int sched_group_set_shares(struct task_group *tg, unsigned long shares); 358 359 #ifdef CONFIG_SMP 360 extern void set_task_rq_fair(struct sched_entity *se, 361 struct cfs_rq *prev, struct cfs_rq *next); 362 #else /* !CONFIG_SMP */ 363 static inline void set_task_rq_fair(struct sched_entity *se, 364 struct cfs_rq *prev, struct cfs_rq *next) { } 365 #endif /* CONFIG_SMP */ 366 #endif /* CONFIG_FAIR_GROUP_SCHED */ 367 368 #else /* CONFIG_CGROUP_SCHED */ 369 370 struct cfs_bandwidth { }; 371 372 #endif /* CONFIG_CGROUP_SCHED */ 373 374 /* CFS-related fields in a runqueue */ 375 struct cfs_rq { 376 struct load_weight load; 377 unsigned int nr_running, h_nr_running; 378 379 u64 exec_clock; 380 u64 min_vruntime; 381 #ifndef CONFIG_64BIT 382 u64 min_vruntime_copy; 383 #endif 384 385 struct rb_root tasks_timeline; 386 struct rb_node *rb_leftmost; 387 388 /* 389 * 'curr' points to currently running entity on this cfs_rq. 390 * It is set to NULL otherwise (i.e when none are currently running). 391 */ 392 struct sched_entity *curr, *next, *last, *skip; 393 394 #ifdef CONFIG_SCHED_DEBUG 395 unsigned int nr_spread_over; 396 #endif 397 398 #ifdef CONFIG_SMP 399 /* 400 * CFS load tracking 401 */ 402 struct sched_avg avg; 403 u64 runnable_load_sum; 404 unsigned long runnable_load_avg; 405 #ifdef CONFIG_FAIR_GROUP_SCHED 406 unsigned long tg_load_avg_contrib; 407 unsigned long propagate_avg; 408 #endif 409 atomic_long_t removed_load_avg, removed_util_avg; 410 #ifndef CONFIG_64BIT 411 u64 load_last_update_time_copy; 412 #endif 413 414 #ifdef CONFIG_FAIR_GROUP_SCHED 415 /* 416 * h_load = weight * f(tg) 417 * 418 * Where f(tg) is the recursive weight fraction assigned to 419 * this group. 420 */ 421 unsigned long h_load; 422 u64 last_h_load_update; 423 struct sched_entity *h_load_next; 424 #endif /* CONFIG_FAIR_GROUP_SCHED */ 425 #endif /* CONFIG_SMP */ 426 427 #ifdef CONFIG_FAIR_GROUP_SCHED 428 struct rq *rq; /* cpu runqueue to which this cfs_rq is attached */ 429 430 /* 431 * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in 432 * a hierarchy). Non-leaf lrqs hold other higher schedulable entities 433 * (like users, containers etc.) 434 * 435 * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This 436 * list is used during load balance. 437 */ 438 int on_list; 439 struct list_head leaf_cfs_rq_list; 440 struct task_group *tg; /* group that "owns" this runqueue */ 441 442 #ifdef CONFIG_CFS_BANDWIDTH 443 int runtime_enabled; 444 u64 runtime_expires; 445 s64 runtime_remaining; 446 447 u64 throttled_clock, throttled_clock_task; 448 u64 throttled_clock_task_time; 449 int throttled, throttle_count; 450 struct list_head throttled_list; 451 #endif /* CONFIG_CFS_BANDWIDTH */ 452 #endif /* CONFIG_FAIR_GROUP_SCHED */ 453 }; 454 455 static inline int rt_bandwidth_enabled(void) 456 { 457 return sysctl_sched_rt_runtime >= 0; 458 } 459 460 /* RT IPI pull logic requires IRQ_WORK */ 461 #ifdef CONFIG_IRQ_WORK 462 # define HAVE_RT_PUSH_IPI 463 #endif 464 465 /* Real-Time classes' related field in a runqueue: */ 466 struct rt_rq { 467 struct rt_prio_array active; 468 unsigned int rt_nr_running; 469 unsigned int rr_nr_running; 470 #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED 471 struct { 472 int curr; /* highest queued rt task prio */ 473 #ifdef CONFIG_SMP 474 int next; /* next highest */ 475 #endif 476 } highest_prio; 477 #endif 478 #ifdef CONFIG_SMP 479 unsigned long rt_nr_migratory; 480 unsigned long rt_nr_total; 481 int overloaded; 482 struct plist_head pushable_tasks; 483 #ifdef HAVE_RT_PUSH_IPI 484 int push_flags; 485 int push_cpu; 486 struct irq_work push_work; 487 raw_spinlock_t push_lock; 488 #endif 489 #endif /* CONFIG_SMP */ 490 int rt_queued; 491 492 int rt_throttled; 493 u64 rt_time; 494 u64 rt_runtime; 495 /* Nests inside the rq lock: */ 496 raw_spinlock_t rt_runtime_lock; 497 498 #ifdef CONFIG_RT_GROUP_SCHED 499 unsigned long rt_nr_boosted; 500 501 struct rq *rq; 502 struct task_group *tg; 503 #endif 504 }; 505 506 /* Deadline class' related fields in a runqueue */ 507 struct dl_rq { 508 /* runqueue is an rbtree, ordered by deadline */ 509 struct rb_root rb_root; 510 struct rb_node *rb_leftmost; 511 512 unsigned long dl_nr_running; 513 514 #ifdef CONFIG_SMP 515 /* 516 * Deadline values of the currently executing and the 517 * earliest ready task on this rq. Caching these facilitates 518 * the decision wether or not a ready but not running task 519 * should migrate somewhere else. 520 */ 521 struct { 522 u64 curr; 523 u64 next; 524 } earliest_dl; 525 526 unsigned long dl_nr_migratory; 527 int overloaded; 528 529 /* 530 * Tasks on this rq that can be pushed away. They are kept in 531 * an rb-tree, ordered by tasks' deadlines, with caching 532 * of the leftmost (earliest deadline) element. 533 */ 534 struct rb_root pushable_dl_tasks_root; 535 struct rb_node *pushable_dl_tasks_leftmost; 536 #else 537 struct dl_bw dl_bw; 538 #endif 539 }; 540 541 #ifdef CONFIG_SMP 542 543 static inline bool sched_asym_prefer(int a, int b) 544 { 545 return arch_asym_cpu_priority(a) > arch_asym_cpu_priority(b); 546 } 547 548 /* 549 * We add the notion of a root-domain which will be used to define per-domain 550 * variables. Each exclusive cpuset essentially defines an island domain by 551 * fully partitioning the member cpus from any other cpuset. Whenever a new 552 * exclusive cpuset is created, we also create and attach a new root-domain 553 * object. 554 * 555 */ 556 struct root_domain { 557 atomic_t refcount; 558 atomic_t rto_count; 559 struct rcu_head rcu; 560 cpumask_var_t span; 561 cpumask_var_t online; 562 563 /* Indicate more than one runnable task for any CPU */ 564 bool overload; 565 566 /* 567 * The bit corresponding to a CPU gets set here if such CPU has more 568 * than one runnable -deadline task (as it is below for RT tasks). 569 */ 570 cpumask_var_t dlo_mask; 571 atomic_t dlo_count; 572 struct dl_bw dl_bw; 573 struct cpudl cpudl; 574 575 /* 576 * The "RT overload" flag: it gets set if a CPU has more than 577 * one runnable RT task. 578 */ 579 cpumask_var_t rto_mask; 580 struct cpupri cpupri; 581 582 unsigned long max_cpu_capacity; 583 }; 584 585 extern struct root_domain def_root_domain; 586 587 #endif /* CONFIG_SMP */ 588 589 /* 590 * This is the main, per-CPU runqueue data structure. 591 * 592 * Locking rule: those places that want to lock multiple runqueues 593 * (such as the load balancing or the thread migration code), lock 594 * acquire operations must be ordered by ascending &runqueue. 595 */ 596 struct rq { 597 /* runqueue lock: */ 598 raw_spinlock_t lock; 599 600 /* 601 * nr_running and cpu_load should be in the same cacheline because 602 * remote CPUs use both these fields when doing load calculation. 603 */ 604 unsigned int nr_running; 605 #ifdef CONFIG_NUMA_BALANCING 606 unsigned int nr_numa_running; 607 unsigned int nr_preferred_running; 608 #endif 609 #define CPU_LOAD_IDX_MAX 5 610 unsigned long cpu_load[CPU_LOAD_IDX_MAX]; 611 #ifdef CONFIG_NO_HZ_COMMON 612 #ifdef CONFIG_SMP 613 unsigned long last_load_update_tick; 614 #endif /* CONFIG_SMP */ 615 unsigned long nohz_flags; 616 #endif /* CONFIG_NO_HZ_COMMON */ 617 #ifdef CONFIG_NO_HZ_FULL 618 unsigned long last_sched_tick; 619 #endif 620 /* capture load from *all* tasks on this cpu: */ 621 struct load_weight load; 622 unsigned long nr_load_updates; 623 u64 nr_switches; 624 625 struct cfs_rq cfs; 626 struct rt_rq rt; 627 struct dl_rq dl; 628 629 #ifdef CONFIG_FAIR_GROUP_SCHED 630 /* list of leaf cfs_rq on this cpu: */ 631 struct list_head leaf_cfs_rq_list; 632 struct list_head *tmp_alone_branch; 633 #endif /* CONFIG_FAIR_GROUP_SCHED */ 634 635 /* 636 * This is part of a global counter where only the total sum 637 * over all CPUs matters. A task can increase this counter on 638 * one CPU and if it got migrated afterwards it may decrease 639 * it on another CPU. Always updated under the runqueue lock: 640 */ 641 unsigned long nr_uninterruptible; 642 643 struct task_struct *curr, *idle, *stop; 644 unsigned long next_balance; 645 struct mm_struct *prev_mm; 646 647 unsigned int clock_skip_update; 648 u64 clock; 649 u64 clock_task; 650 651 atomic_t nr_iowait; 652 653 #ifdef CONFIG_SMP 654 struct root_domain *rd; 655 struct sched_domain *sd; 656 657 unsigned long cpu_capacity; 658 unsigned long cpu_capacity_orig; 659 660 struct callback_head *balance_callback; 661 662 unsigned char idle_balance; 663 /* For active balancing */ 664 int active_balance; 665 int push_cpu; 666 struct cpu_stop_work active_balance_work; 667 /* cpu of this runqueue: */ 668 int cpu; 669 int online; 670 671 struct list_head cfs_tasks; 672 673 u64 rt_avg; 674 u64 age_stamp; 675 u64 idle_stamp; 676 u64 avg_idle; 677 678 /* This is used to determine avg_idle's max value */ 679 u64 max_idle_balance_cost; 680 #endif 681 682 #ifdef CONFIG_IRQ_TIME_ACCOUNTING 683 u64 prev_irq_time; 684 #endif 685 #ifdef CONFIG_PARAVIRT 686 u64 prev_steal_time; 687 #endif 688 #ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING 689 u64 prev_steal_time_rq; 690 #endif 691 692 /* calc_load related fields */ 693 unsigned long calc_load_update; 694 long calc_load_active; 695 696 #ifdef CONFIG_SCHED_HRTICK 697 #ifdef CONFIG_SMP 698 int hrtick_csd_pending; 699 struct call_single_data hrtick_csd; 700 #endif 701 struct hrtimer hrtick_timer; 702 #endif 703 704 #ifdef CONFIG_SCHEDSTATS 705 /* latency stats */ 706 struct sched_info rq_sched_info; 707 unsigned long long rq_cpu_time; 708 /* could above be rq->cfs_rq.exec_clock + rq->rt_rq.rt_runtime ? */ 709 710 /* sys_sched_yield() stats */ 711 unsigned int yld_count; 712 713 /* schedule() stats */ 714 unsigned int sched_count; 715 unsigned int sched_goidle; 716 717 /* try_to_wake_up() stats */ 718 unsigned int ttwu_count; 719 unsigned int ttwu_local; 720 #endif 721 722 #ifdef CONFIG_SMP 723 struct llist_head wake_list; 724 #endif 725 726 #ifdef CONFIG_CPU_IDLE 727 /* Must be inspected within a rcu lock section */ 728 struct cpuidle_state *idle_state; 729 #endif 730 }; 731 732 static inline int cpu_of(struct rq *rq) 733 { 734 #ifdef CONFIG_SMP 735 return rq->cpu; 736 #else 737 return 0; 738 #endif 739 } 740 741 742 #ifdef CONFIG_SCHED_SMT 743 744 extern struct static_key_false sched_smt_present; 745 746 extern void __update_idle_core(struct rq *rq); 747 748 static inline void update_idle_core(struct rq *rq) 749 { 750 if (static_branch_unlikely(&sched_smt_present)) 751 __update_idle_core(rq); 752 } 753 754 #else 755 static inline void update_idle_core(struct rq *rq) { } 756 #endif 757 758 DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues); 759 760 #define cpu_rq(cpu) (&per_cpu(runqueues, (cpu))) 761 #define this_rq() this_cpu_ptr(&runqueues) 762 #define task_rq(p) cpu_rq(task_cpu(p)) 763 #define cpu_curr(cpu) (cpu_rq(cpu)->curr) 764 #define raw_rq() raw_cpu_ptr(&runqueues) 765 766 static inline u64 __rq_clock_broken(struct rq *rq) 767 { 768 return READ_ONCE(rq->clock); 769 } 770 771 static inline u64 rq_clock(struct rq *rq) 772 { 773 lockdep_assert_held(&rq->lock); 774 return rq->clock; 775 } 776 777 static inline u64 rq_clock_task(struct rq *rq) 778 { 779 lockdep_assert_held(&rq->lock); 780 return rq->clock_task; 781 } 782 783 #define RQCF_REQ_SKIP 0x01 784 #define RQCF_ACT_SKIP 0x02 785 786 static inline void rq_clock_skip_update(struct rq *rq, bool skip) 787 { 788 lockdep_assert_held(&rq->lock); 789 if (skip) 790 rq->clock_skip_update |= RQCF_REQ_SKIP; 791 else 792 rq->clock_skip_update &= ~RQCF_REQ_SKIP; 793 } 794 795 #ifdef CONFIG_NUMA 796 enum numa_topology_type { 797 NUMA_DIRECT, 798 NUMA_GLUELESS_MESH, 799 NUMA_BACKPLANE, 800 }; 801 extern enum numa_topology_type sched_numa_topology_type; 802 extern int sched_max_numa_distance; 803 extern bool find_numa_distance(int distance); 804 #endif 805 806 #ifdef CONFIG_NUMA_BALANCING 807 /* The regions in numa_faults array from task_struct */ 808 enum numa_faults_stats { 809 NUMA_MEM = 0, 810 NUMA_CPU, 811 NUMA_MEMBUF, 812 NUMA_CPUBUF 813 }; 814 extern void sched_setnuma(struct task_struct *p, int node); 815 extern int migrate_task_to(struct task_struct *p, int cpu); 816 extern int migrate_swap(struct task_struct *, struct task_struct *); 817 #endif /* CONFIG_NUMA_BALANCING */ 818 819 #ifdef CONFIG_SMP 820 821 static inline void 822 queue_balance_callback(struct rq *rq, 823 struct callback_head *head, 824 void (*func)(struct rq *rq)) 825 { 826 lockdep_assert_held(&rq->lock); 827 828 if (unlikely(head->next)) 829 return; 830 831 head->func = (void (*)(struct callback_head *))func; 832 head->next = rq->balance_callback; 833 rq->balance_callback = head; 834 } 835 836 extern void sched_ttwu_pending(void); 837 838 #define rcu_dereference_check_sched_domain(p) \ 839 rcu_dereference_check((p), \ 840 lockdep_is_held(&sched_domains_mutex)) 841 842 /* 843 * The domain tree (rq->sd) is protected by RCU's quiescent state transition. 844 * See detach_destroy_domains: synchronize_sched for details. 845 * 846 * The domain tree of any CPU may only be accessed from within 847 * preempt-disabled sections. 848 */ 849 #define for_each_domain(cpu, __sd) \ 850 for (__sd = rcu_dereference_check_sched_domain(cpu_rq(cpu)->sd); \ 851 __sd; __sd = __sd->parent) 852 853 #define for_each_lower_domain(sd) for (; sd; sd = sd->child) 854 855 /** 856 * highest_flag_domain - Return highest sched_domain containing flag. 857 * @cpu: The cpu whose highest level of sched domain is to 858 * be returned. 859 * @flag: The flag to check for the highest sched_domain 860 * for the given cpu. 861 * 862 * Returns the highest sched_domain of a cpu which contains the given flag. 863 */ 864 static inline struct sched_domain *highest_flag_domain(int cpu, int flag) 865 { 866 struct sched_domain *sd, *hsd = NULL; 867 868 for_each_domain(cpu, sd) { 869 if (!(sd->flags & flag)) 870 break; 871 hsd = sd; 872 } 873 874 return hsd; 875 } 876 877 static inline struct sched_domain *lowest_flag_domain(int cpu, int flag) 878 { 879 struct sched_domain *sd; 880 881 for_each_domain(cpu, sd) { 882 if (sd->flags & flag) 883 break; 884 } 885 886 return sd; 887 } 888 889 DECLARE_PER_CPU(struct sched_domain *, sd_llc); 890 DECLARE_PER_CPU(int, sd_llc_size); 891 DECLARE_PER_CPU(int, sd_llc_id); 892 DECLARE_PER_CPU(struct sched_domain_shared *, sd_llc_shared); 893 DECLARE_PER_CPU(struct sched_domain *, sd_numa); 894 DECLARE_PER_CPU(struct sched_domain *, sd_asym); 895 896 struct sched_group_capacity { 897 atomic_t ref; 898 /* 899 * CPU capacity of this group, SCHED_CAPACITY_SCALE being max capacity 900 * for a single CPU. 901 */ 902 unsigned long capacity; 903 unsigned long min_capacity; /* Min per-CPU capacity in group */ 904 unsigned long next_update; 905 int imbalance; /* XXX unrelated to capacity but shared group state */ 906 907 unsigned long cpumask[0]; /* iteration mask */ 908 }; 909 910 struct sched_group { 911 struct sched_group *next; /* Must be a circular list */ 912 atomic_t ref; 913 914 unsigned int group_weight; 915 struct sched_group_capacity *sgc; 916 int asym_prefer_cpu; /* cpu of highest priority in group */ 917 918 /* 919 * The CPUs this group covers. 920 * 921 * NOTE: this field is variable length. (Allocated dynamically 922 * by attaching extra space to the end of the structure, 923 * depending on how many CPUs the kernel has booted up with) 924 */ 925 unsigned long cpumask[0]; 926 }; 927 928 static inline struct cpumask *sched_group_cpus(struct sched_group *sg) 929 { 930 return to_cpumask(sg->cpumask); 931 } 932 933 /* 934 * cpumask masking which cpus in the group are allowed to iterate up the domain 935 * tree. 936 */ 937 static inline struct cpumask *sched_group_mask(struct sched_group *sg) 938 { 939 return to_cpumask(sg->sgc->cpumask); 940 } 941 942 /** 943 * group_first_cpu - Returns the first cpu in the cpumask of a sched_group. 944 * @group: The group whose first cpu is to be returned. 945 */ 946 static inline unsigned int group_first_cpu(struct sched_group *group) 947 { 948 return cpumask_first(sched_group_cpus(group)); 949 } 950 951 extern int group_balance_cpu(struct sched_group *sg); 952 953 #if defined(CONFIG_SCHED_DEBUG) && defined(CONFIG_SYSCTL) 954 void register_sched_domain_sysctl(void); 955 void unregister_sched_domain_sysctl(void); 956 #else 957 static inline void register_sched_domain_sysctl(void) 958 { 959 } 960 static inline void unregister_sched_domain_sysctl(void) 961 { 962 } 963 #endif 964 965 #else 966 967 static inline void sched_ttwu_pending(void) { } 968 969 #endif /* CONFIG_SMP */ 970 971 #include "stats.h" 972 #include "auto_group.h" 973 974 #ifdef CONFIG_CGROUP_SCHED 975 976 /* 977 * Return the group to which this tasks belongs. 978 * 979 * We cannot use task_css() and friends because the cgroup subsystem 980 * changes that value before the cgroup_subsys::attach() method is called, 981 * therefore we cannot pin it and might observe the wrong value. 982 * 983 * The same is true for autogroup's p->signal->autogroup->tg, the autogroup 984 * core changes this before calling sched_move_task(). 985 * 986 * Instead we use a 'copy' which is updated from sched_move_task() while 987 * holding both task_struct::pi_lock and rq::lock. 988 */ 989 static inline struct task_group *task_group(struct task_struct *p) 990 { 991 return p->sched_task_group; 992 } 993 994 /* Change a task's cfs_rq and parent entity if it moves across CPUs/groups */ 995 static inline void set_task_rq(struct task_struct *p, unsigned int cpu) 996 { 997 #if defined(CONFIG_FAIR_GROUP_SCHED) || defined(CONFIG_RT_GROUP_SCHED) 998 struct task_group *tg = task_group(p); 999 #endif 1000 1001 #ifdef CONFIG_FAIR_GROUP_SCHED 1002 set_task_rq_fair(&p->se, p->se.cfs_rq, tg->cfs_rq[cpu]); 1003 p->se.cfs_rq = tg->cfs_rq[cpu]; 1004 p->se.parent = tg->se[cpu]; 1005 #endif 1006 1007 #ifdef CONFIG_RT_GROUP_SCHED 1008 p->rt.rt_rq = tg->rt_rq[cpu]; 1009 p->rt.parent = tg->rt_se[cpu]; 1010 #endif 1011 } 1012 1013 #else /* CONFIG_CGROUP_SCHED */ 1014 1015 static inline void set_task_rq(struct task_struct *p, unsigned int cpu) { } 1016 static inline struct task_group *task_group(struct task_struct *p) 1017 { 1018 return NULL; 1019 } 1020 1021 #endif /* CONFIG_CGROUP_SCHED */ 1022 1023 static inline void __set_task_cpu(struct task_struct *p, unsigned int cpu) 1024 { 1025 set_task_rq(p, cpu); 1026 #ifdef CONFIG_SMP 1027 /* 1028 * After ->cpu is set up to a new value, task_rq_lock(p, ...) can be 1029 * successfuly executed on another CPU. We must ensure that updates of 1030 * per-task data have been completed by this moment. 1031 */ 1032 smp_wmb(); 1033 #ifdef CONFIG_THREAD_INFO_IN_TASK 1034 p->cpu = cpu; 1035 #else 1036 task_thread_info(p)->cpu = cpu; 1037 #endif 1038 p->wake_cpu = cpu; 1039 #endif 1040 } 1041 1042 /* 1043 * Tunables that become constants when CONFIG_SCHED_DEBUG is off: 1044 */ 1045 #ifdef CONFIG_SCHED_DEBUG 1046 # include <linux/static_key.h> 1047 # define const_debug __read_mostly 1048 #else 1049 # define const_debug const 1050 #endif 1051 1052 extern const_debug unsigned int sysctl_sched_features; 1053 1054 #define SCHED_FEAT(name, enabled) \ 1055 __SCHED_FEAT_##name , 1056 1057 enum { 1058 #include "features.h" 1059 __SCHED_FEAT_NR, 1060 }; 1061 1062 #undef SCHED_FEAT 1063 1064 #if defined(CONFIG_SCHED_DEBUG) && defined(HAVE_JUMP_LABEL) 1065 #define SCHED_FEAT(name, enabled) \ 1066 static __always_inline bool static_branch_##name(struct static_key *key) \ 1067 { \ 1068 return static_key_##enabled(key); \ 1069 } 1070 1071 #include "features.h" 1072 1073 #undef SCHED_FEAT 1074 1075 extern struct static_key sched_feat_keys[__SCHED_FEAT_NR]; 1076 #define sched_feat(x) (static_branch_##x(&sched_feat_keys[__SCHED_FEAT_##x])) 1077 #else /* !(SCHED_DEBUG && HAVE_JUMP_LABEL) */ 1078 #define sched_feat(x) (sysctl_sched_features & (1UL << __SCHED_FEAT_##x)) 1079 #endif /* SCHED_DEBUG && HAVE_JUMP_LABEL */ 1080 1081 extern struct static_key_false sched_numa_balancing; 1082 extern struct static_key_false sched_schedstats; 1083 1084 static inline u64 global_rt_period(void) 1085 { 1086 return (u64)sysctl_sched_rt_period * NSEC_PER_USEC; 1087 } 1088 1089 static inline u64 global_rt_runtime(void) 1090 { 1091 if (sysctl_sched_rt_runtime < 0) 1092 return RUNTIME_INF; 1093 1094 return (u64)sysctl_sched_rt_runtime * NSEC_PER_USEC; 1095 } 1096 1097 static inline int task_current(struct rq *rq, struct task_struct *p) 1098 { 1099 return rq->curr == p; 1100 } 1101 1102 static inline int task_running(struct rq *rq, struct task_struct *p) 1103 { 1104 #ifdef CONFIG_SMP 1105 return p->on_cpu; 1106 #else 1107 return task_current(rq, p); 1108 #endif 1109 } 1110 1111 static inline int task_on_rq_queued(struct task_struct *p) 1112 { 1113 return p->on_rq == TASK_ON_RQ_QUEUED; 1114 } 1115 1116 static inline int task_on_rq_migrating(struct task_struct *p) 1117 { 1118 return p->on_rq == TASK_ON_RQ_MIGRATING; 1119 } 1120 1121 #ifndef prepare_arch_switch 1122 # define prepare_arch_switch(next) do { } while (0) 1123 #endif 1124 #ifndef finish_arch_post_lock_switch 1125 # define finish_arch_post_lock_switch() do { } while (0) 1126 #endif 1127 1128 static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next) 1129 { 1130 #ifdef CONFIG_SMP 1131 /* 1132 * We can optimise this out completely for !SMP, because the 1133 * SMP rebalancing from interrupt is the only thing that cares 1134 * here. 1135 */ 1136 next->on_cpu = 1; 1137 #endif 1138 } 1139 1140 static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev) 1141 { 1142 #ifdef CONFIG_SMP 1143 /* 1144 * After ->on_cpu is cleared, the task can be moved to a different CPU. 1145 * We must ensure this doesn't happen until the switch is completely 1146 * finished. 1147 * 1148 * In particular, the load of prev->state in finish_task_switch() must 1149 * happen before this. 1150 * 1151 * Pairs with the smp_cond_load_acquire() in try_to_wake_up(). 1152 */ 1153 smp_store_release(&prev->on_cpu, 0); 1154 #endif 1155 #ifdef CONFIG_DEBUG_SPINLOCK 1156 /* this is a valid case when another task releases the spinlock */ 1157 rq->lock.owner = current; 1158 #endif 1159 /* 1160 * If we are tracking spinlock dependencies then we have to 1161 * fix up the runqueue lock - which gets 'carried over' from 1162 * prev into current: 1163 */ 1164 spin_acquire(&rq->lock.dep_map, 0, 0, _THIS_IP_); 1165 1166 raw_spin_unlock_irq(&rq->lock); 1167 } 1168 1169 /* 1170 * wake flags 1171 */ 1172 #define WF_SYNC 0x01 /* waker goes to sleep after wakeup */ 1173 #define WF_FORK 0x02 /* child wakeup after fork */ 1174 #define WF_MIGRATED 0x4 /* internal use, task got migrated */ 1175 1176 /* 1177 * To aid in avoiding the subversion of "niceness" due to uneven distribution 1178 * of tasks with abnormal "nice" values across CPUs the contribution that 1179 * each task makes to its run queue's load is weighted according to its 1180 * scheduling class and "nice" value. For SCHED_NORMAL tasks this is just a 1181 * scaled version of the new time slice allocation that they receive on time 1182 * slice expiry etc. 1183 */ 1184 1185 #define WEIGHT_IDLEPRIO 3 1186 #define WMULT_IDLEPRIO 1431655765 1187 1188 extern const int sched_prio_to_weight[40]; 1189 extern const u32 sched_prio_to_wmult[40]; 1190 1191 /* 1192 * {de,en}queue flags: 1193 * 1194 * DEQUEUE_SLEEP - task is no longer runnable 1195 * ENQUEUE_WAKEUP - task just became runnable 1196 * 1197 * SAVE/RESTORE - an otherwise spurious dequeue/enqueue, done to ensure tasks 1198 * are in a known state which allows modification. Such pairs 1199 * should preserve as much state as possible. 1200 * 1201 * MOVE - paired with SAVE/RESTORE, explicitly does not preserve the location 1202 * in the runqueue. 1203 * 1204 * ENQUEUE_HEAD - place at front of runqueue (tail if not specified) 1205 * ENQUEUE_REPLENISH - CBS (replenish runtime and postpone deadline) 1206 * ENQUEUE_MIGRATED - the task was migrated during wakeup 1207 * 1208 */ 1209 1210 #define DEQUEUE_SLEEP 0x01 1211 #define DEQUEUE_SAVE 0x02 /* matches ENQUEUE_RESTORE */ 1212 #define DEQUEUE_MOVE 0x04 /* matches ENQUEUE_MOVE */ 1213 1214 #define ENQUEUE_WAKEUP 0x01 1215 #define ENQUEUE_RESTORE 0x02 1216 #define ENQUEUE_MOVE 0x04 1217 1218 #define ENQUEUE_HEAD 0x08 1219 #define ENQUEUE_REPLENISH 0x10 1220 #ifdef CONFIG_SMP 1221 #define ENQUEUE_MIGRATED 0x20 1222 #else 1223 #define ENQUEUE_MIGRATED 0x00 1224 #endif 1225 1226 #define RETRY_TASK ((void *)-1UL) 1227 1228 struct sched_class { 1229 const struct sched_class *next; 1230 1231 void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags); 1232 void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags); 1233 void (*yield_task) (struct rq *rq); 1234 bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt); 1235 1236 void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags); 1237 1238 /* 1239 * It is the responsibility of the pick_next_task() method that will 1240 * return the next task to call put_prev_task() on the @prev task or 1241 * something equivalent. 1242 * 1243 * May return RETRY_TASK when it finds a higher prio class has runnable 1244 * tasks. 1245 */ 1246 struct task_struct * (*pick_next_task) (struct rq *rq, 1247 struct task_struct *prev, 1248 struct pin_cookie cookie); 1249 void (*put_prev_task) (struct rq *rq, struct task_struct *p); 1250 1251 #ifdef CONFIG_SMP 1252 int (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags); 1253 void (*migrate_task_rq)(struct task_struct *p); 1254 1255 void (*task_woken) (struct rq *this_rq, struct task_struct *task); 1256 1257 void (*set_cpus_allowed)(struct task_struct *p, 1258 const struct cpumask *newmask); 1259 1260 void (*rq_online)(struct rq *rq); 1261 void (*rq_offline)(struct rq *rq); 1262 #endif 1263 1264 void (*set_curr_task) (struct rq *rq); 1265 void (*task_tick) (struct rq *rq, struct task_struct *p, int queued); 1266 void (*task_fork) (struct task_struct *p); 1267 void (*task_dead) (struct task_struct *p); 1268 1269 /* 1270 * The switched_from() call is allowed to drop rq->lock, therefore we 1271 * cannot assume the switched_from/switched_to pair is serliazed by 1272 * rq->lock. They are however serialized by p->pi_lock. 1273 */ 1274 void (*switched_from) (struct rq *this_rq, struct task_struct *task); 1275 void (*switched_to) (struct rq *this_rq, struct task_struct *task); 1276 void (*prio_changed) (struct rq *this_rq, struct task_struct *task, 1277 int oldprio); 1278 1279 unsigned int (*get_rr_interval) (struct rq *rq, 1280 struct task_struct *task); 1281 1282 void (*update_curr) (struct rq *rq); 1283 1284 #define TASK_SET_GROUP 0 1285 #define TASK_MOVE_GROUP 1 1286 1287 #ifdef CONFIG_FAIR_GROUP_SCHED 1288 void (*task_change_group) (struct task_struct *p, int type); 1289 #endif 1290 }; 1291 1292 static inline void put_prev_task(struct rq *rq, struct task_struct *prev) 1293 { 1294 prev->sched_class->put_prev_task(rq, prev); 1295 } 1296 1297 static inline void set_curr_task(struct rq *rq, struct task_struct *curr) 1298 { 1299 curr->sched_class->set_curr_task(rq); 1300 } 1301 1302 #define sched_class_highest (&stop_sched_class) 1303 #define for_each_class(class) \ 1304 for (class = sched_class_highest; class; class = class->next) 1305 1306 extern const struct sched_class stop_sched_class; 1307 extern const struct sched_class dl_sched_class; 1308 extern const struct sched_class rt_sched_class; 1309 extern const struct sched_class fair_sched_class; 1310 extern const struct sched_class idle_sched_class; 1311 1312 1313 #ifdef CONFIG_SMP 1314 1315 extern void update_group_capacity(struct sched_domain *sd, int cpu); 1316 1317 extern void trigger_load_balance(struct rq *rq); 1318 1319 extern void set_cpus_allowed_common(struct task_struct *p, const struct cpumask *new_mask); 1320 1321 #endif 1322 1323 #ifdef CONFIG_CPU_IDLE 1324 static inline void idle_set_state(struct rq *rq, 1325 struct cpuidle_state *idle_state) 1326 { 1327 rq->idle_state = idle_state; 1328 } 1329 1330 static inline struct cpuidle_state *idle_get_state(struct rq *rq) 1331 { 1332 SCHED_WARN_ON(!rcu_read_lock_held()); 1333 return rq->idle_state; 1334 } 1335 #else 1336 static inline void idle_set_state(struct rq *rq, 1337 struct cpuidle_state *idle_state) 1338 { 1339 } 1340 1341 static inline struct cpuidle_state *idle_get_state(struct rq *rq) 1342 { 1343 return NULL; 1344 } 1345 #endif 1346 1347 extern void sysrq_sched_debug_show(void); 1348 extern void sched_init_granularity(void); 1349 extern void update_max_interval(void); 1350 1351 extern void init_sched_dl_class(void); 1352 extern void init_sched_rt_class(void); 1353 extern void init_sched_fair_class(void); 1354 1355 extern void resched_curr(struct rq *rq); 1356 extern void resched_cpu(int cpu); 1357 1358 extern struct rt_bandwidth def_rt_bandwidth; 1359 extern void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime); 1360 1361 extern struct dl_bandwidth def_dl_bandwidth; 1362 extern void init_dl_bandwidth(struct dl_bandwidth *dl_b, u64 period, u64 runtime); 1363 extern void init_dl_task_timer(struct sched_dl_entity *dl_se); 1364 1365 unsigned long to_ratio(u64 period, u64 runtime); 1366 1367 extern void init_entity_runnable_average(struct sched_entity *se); 1368 extern void post_init_entity_util_avg(struct sched_entity *se); 1369 1370 #ifdef CONFIG_NO_HZ_FULL 1371 extern bool sched_can_stop_tick(struct rq *rq); 1372 1373 /* 1374 * Tick may be needed by tasks in the runqueue depending on their policy and 1375 * requirements. If tick is needed, lets send the target an IPI to kick it out of 1376 * nohz mode if necessary. 1377 */ 1378 static inline void sched_update_tick_dependency(struct rq *rq) 1379 { 1380 int cpu; 1381 1382 if (!tick_nohz_full_enabled()) 1383 return; 1384 1385 cpu = cpu_of(rq); 1386 1387 if (!tick_nohz_full_cpu(cpu)) 1388 return; 1389 1390 if (sched_can_stop_tick(rq)) 1391 tick_nohz_dep_clear_cpu(cpu, TICK_DEP_BIT_SCHED); 1392 else 1393 tick_nohz_dep_set_cpu(cpu, TICK_DEP_BIT_SCHED); 1394 } 1395 #else 1396 static inline void sched_update_tick_dependency(struct rq *rq) { } 1397 #endif 1398 1399 static inline void add_nr_running(struct rq *rq, unsigned count) 1400 { 1401 unsigned prev_nr = rq->nr_running; 1402 1403 rq->nr_running = prev_nr + count; 1404 1405 if (prev_nr < 2 && rq->nr_running >= 2) { 1406 #ifdef CONFIG_SMP 1407 if (!rq->rd->overload) 1408 rq->rd->overload = true; 1409 #endif 1410 } 1411 1412 sched_update_tick_dependency(rq); 1413 } 1414 1415 static inline void sub_nr_running(struct rq *rq, unsigned count) 1416 { 1417 rq->nr_running -= count; 1418 /* Check if we still need preemption */ 1419 sched_update_tick_dependency(rq); 1420 } 1421 1422 static inline void rq_last_tick_reset(struct rq *rq) 1423 { 1424 #ifdef CONFIG_NO_HZ_FULL 1425 rq->last_sched_tick = jiffies; 1426 #endif 1427 } 1428 1429 extern void update_rq_clock(struct rq *rq); 1430 1431 extern void activate_task(struct rq *rq, struct task_struct *p, int flags); 1432 extern void deactivate_task(struct rq *rq, struct task_struct *p, int flags); 1433 1434 extern void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags); 1435 1436 extern const_debug unsigned int sysctl_sched_time_avg; 1437 extern const_debug unsigned int sysctl_sched_nr_migrate; 1438 extern const_debug unsigned int sysctl_sched_migration_cost; 1439 1440 static inline u64 sched_avg_period(void) 1441 { 1442 return (u64)sysctl_sched_time_avg * NSEC_PER_MSEC / 2; 1443 } 1444 1445 #ifdef CONFIG_SCHED_HRTICK 1446 1447 /* 1448 * Use hrtick when: 1449 * - enabled by features 1450 * - hrtimer is actually high res 1451 */ 1452 static inline int hrtick_enabled(struct rq *rq) 1453 { 1454 if (!sched_feat(HRTICK)) 1455 return 0; 1456 if (!cpu_active(cpu_of(rq))) 1457 return 0; 1458 return hrtimer_is_hres_active(&rq->hrtick_timer); 1459 } 1460 1461 void hrtick_start(struct rq *rq, u64 delay); 1462 1463 #else 1464 1465 static inline int hrtick_enabled(struct rq *rq) 1466 { 1467 return 0; 1468 } 1469 1470 #endif /* CONFIG_SCHED_HRTICK */ 1471 1472 #ifdef CONFIG_SMP 1473 extern void sched_avg_update(struct rq *rq); 1474 1475 #ifndef arch_scale_freq_capacity 1476 static __always_inline 1477 unsigned long arch_scale_freq_capacity(struct sched_domain *sd, int cpu) 1478 { 1479 return SCHED_CAPACITY_SCALE; 1480 } 1481 #endif 1482 1483 #ifndef arch_scale_cpu_capacity 1484 static __always_inline 1485 unsigned long arch_scale_cpu_capacity(struct sched_domain *sd, int cpu) 1486 { 1487 if (sd && (sd->flags & SD_SHARE_CPUCAPACITY) && (sd->span_weight > 1)) 1488 return sd->smt_gain / sd->span_weight; 1489 1490 return SCHED_CAPACITY_SCALE; 1491 } 1492 #endif 1493 1494 static inline void sched_rt_avg_update(struct rq *rq, u64 rt_delta) 1495 { 1496 rq->rt_avg += rt_delta * arch_scale_freq_capacity(NULL, cpu_of(rq)); 1497 sched_avg_update(rq); 1498 } 1499 #else 1500 static inline void sched_rt_avg_update(struct rq *rq, u64 rt_delta) { } 1501 static inline void sched_avg_update(struct rq *rq) { } 1502 #endif 1503 1504 struct rq_flags { 1505 unsigned long flags; 1506 struct pin_cookie cookie; 1507 }; 1508 1509 struct rq *__task_rq_lock(struct task_struct *p, struct rq_flags *rf) 1510 __acquires(rq->lock); 1511 struct rq *task_rq_lock(struct task_struct *p, struct rq_flags *rf) 1512 __acquires(p->pi_lock) 1513 __acquires(rq->lock); 1514 1515 static inline void __task_rq_unlock(struct rq *rq, struct rq_flags *rf) 1516 __releases(rq->lock) 1517 { 1518 lockdep_unpin_lock(&rq->lock, rf->cookie); 1519 raw_spin_unlock(&rq->lock); 1520 } 1521 1522 static inline void 1523 task_rq_unlock(struct rq *rq, struct task_struct *p, struct rq_flags *rf) 1524 __releases(rq->lock) 1525 __releases(p->pi_lock) 1526 { 1527 lockdep_unpin_lock(&rq->lock, rf->cookie); 1528 raw_spin_unlock(&rq->lock); 1529 raw_spin_unlock_irqrestore(&p->pi_lock, rf->flags); 1530 } 1531 1532 #ifdef CONFIG_SMP 1533 #ifdef CONFIG_PREEMPT 1534 1535 static inline void double_rq_lock(struct rq *rq1, struct rq *rq2); 1536 1537 /* 1538 * fair double_lock_balance: Safely acquires both rq->locks in a fair 1539 * way at the expense of forcing extra atomic operations in all 1540 * invocations. This assures that the double_lock is acquired using the 1541 * same underlying policy as the spinlock_t on this architecture, which 1542 * reduces latency compared to the unfair variant below. However, it 1543 * also adds more overhead and therefore may reduce throughput. 1544 */ 1545 static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest) 1546 __releases(this_rq->lock) 1547 __acquires(busiest->lock) 1548 __acquires(this_rq->lock) 1549 { 1550 raw_spin_unlock(&this_rq->lock); 1551 double_rq_lock(this_rq, busiest); 1552 1553 return 1; 1554 } 1555 1556 #else 1557 /* 1558 * Unfair double_lock_balance: Optimizes throughput at the expense of 1559 * latency by eliminating extra atomic operations when the locks are 1560 * already in proper order on entry. This favors lower cpu-ids and will 1561 * grant the double lock to lower cpus over higher ids under contention, 1562 * regardless of entry order into the function. 1563 */ 1564 static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest) 1565 __releases(this_rq->lock) 1566 __acquires(busiest->lock) 1567 __acquires(this_rq->lock) 1568 { 1569 int ret = 0; 1570 1571 if (unlikely(!raw_spin_trylock(&busiest->lock))) { 1572 if (busiest < this_rq) { 1573 raw_spin_unlock(&this_rq->lock); 1574 raw_spin_lock(&busiest->lock); 1575 raw_spin_lock_nested(&this_rq->lock, 1576 SINGLE_DEPTH_NESTING); 1577 ret = 1; 1578 } else 1579 raw_spin_lock_nested(&busiest->lock, 1580 SINGLE_DEPTH_NESTING); 1581 } 1582 return ret; 1583 } 1584 1585 #endif /* CONFIG_PREEMPT */ 1586 1587 /* 1588 * double_lock_balance - lock the busiest runqueue, this_rq is locked already. 1589 */ 1590 static inline int double_lock_balance(struct rq *this_rq, struct rq *busiest) 1591 { 1592 if (unlikely(!irqs_disabled())) { 1593 /* printk() doesn't work good under rq->lock */ 1594 raw_spin_unlock(&this_rq->lock); 1595 BUG_ON(1); 1596 } 1597 1598 return _double_lock_balance(this_rq, busiest); 1599 } 1600 1601 static inline void double_unlock_balance(struct rq *this_rq, struct rq *busiest) 1602 __releases(busiest->lock) 1603 { 1604 raw_spin_unlock(&busiest->lock); 1605 lock_set_subclass(&this_rq->lock.dep_map, 0, _RET_IP_); 1606 } 1607 1608 static inline void double_lock(spinlock_t *l1, spinlock_t *l2) 1609 { 1610 if (l1 > l2) 1611 swap(l1, l2); 1612 1613 spin_lock(l1); 1614 spin_lock_nested(l2, SINGLE_DEPTH_NESTING); 1615 } 1616 1617 static inline void double_lock_irq(spinlock_t *l1, spinlock_t *l2) 1618 { 1619 if (l1 > l2) 1620 swap(l1, l2); 1621 1622 spin_lock_irq(l1); 1623 spin_lock_nested(l2, SINGLE_DEPTH_NESTING); 1624 } 1625 1626 static inline void double_raw_lock(raw_spinlock_t *l1, raw_spinlock_t *l2) 1627 { 1628 if (l1 > l2) 1629 swap(l1, l2); 1630 1631 raw_spin_lock(l1); 1632 raw_spin_lock_nested(l2, SINGLE_DEPTH_NESTING); 1633 } 1634 1635 /* 1636 * double_rq_lock - safely lock two runqueues 1637 * 1638 * Note this does not disable interrupts like task_rq_lock, 1639 * you need to do so manually before calling. 1640 */ 1641 static inline void double_rq_lock(struct rq *rq1, struct rq *rq2) 1642 __acquires(rq1->lock) 1643 __acquires(rq2->lock) 1644 { 1645 BUG_ON(!irqs_disabled()); 1646 if (rq1 == rq2) { 1647 raw_spin_lock(&rq1->lock); 1648 __acquire(rq2->lock); /* Fake it out ;) */ 1649 } else { 1650 if (rq1 < rq2) { 1651 raw_spin_lock(&rq1->lock); 1652 raw_spin_lock_nested(&rq2->lock, SINGLE_DEPTH_NESTING); 1653 } else { 1654 raw_spin_lock(&rq2->lock); 1655 raw_spin_lock_nested(&rq1->lock, SINGLE_DEPTH_NESTING); 1656 } 1657 } 1658 } 1659 1660 /* 1661 * double_rq_unlock - safely unlock two runqueues 1662 * 1663 * Note this does not restore interrupts like task_rq_unlock, 1664 * you need to do so manually after calling. 1665 */ 1666 static inline void double_rq_unlock(struct rq *rq1, struct rq *rq2) 1667 __releases(rq1->lock) 1668 __releases(rq2->lock) 1669 { 1670 raw_spin_unlock(&rq1->lock); 1671 if (rq1 != rq2) 1672 raw_spin_unlock(&rq2->lock); 1673 else 1674 __release(rq2->lock); 1675 } 1676 1677 #else /* CONFIG_SMP */ 1678 1679 /* 1680 * double_rq_lock - safely lock two runqueues 1681 * 1682 * Note this does not disable interrupts like task_rq_lock, 1683 * you need to do so manually before calling. 1684 */ 1685 static inline void double_rq_lock(struct rq *rq1, struct rq *rq2) 1686 __acquires(rq1->lock) 1687 __acquires(rq2->lock) 1688 { 1689 BUG_ON(!irqs_disabled()); 1690 BUG_ON(rq1 != rq2); 1691 raw_spin_lock(&rq1->lock); 1692 __acquire(rq2->lock); /* Fake it out ;) */ 1693 } 1694 1695 /* 1696 * double_rq_unlock - safely unlock two runqueues 1697 * 1698 * Note this does not restore interrupts like task_rq_unlock, 1699 * you need to do so manually after calling. 1700 */ 1701 static inline void double_rq_unlock(struct rq *rq1, struct rq *rq2) 1702 __releases(rq1->lock) 1703 __releases(rq2->lock) 1704 { 1705 BUG_ON(rq1 != rq2); 1706 raw_spin_unlock(&rq1->lock); 1707 __release(rq2->lock); 1708 } 1709 1710 #endif 1711 1712 extern struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq); 1713 extern struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq); 1714 1715 #ifdef CONFIG_SCHED_DEBUG 1716 extern void print_cfs_stats(struct seq_file *m, int cpu); 1717 extern void print_rt_stats(struct seq_file *m, int cpu); 1718 extern void print_dl_stats(struct seq_file *m, int cpu); 1719 extern void 1720 print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq); 1721 1722 #ifdef CONFIG_NUMA_BALANCING 1723 extern void 1724 show_numa_stats(struct task_struct *p, struct seq_file *m); 1725 extern void 1726 print_numa_stats(struct seq_file *m, int node, unsigned long tsf, 1727 unsigned long tpf, unsigned long gsf, unsigned long gpf); 1728 #endif /* CONFIG_NUMA_BALANCING */ 1729 #endif /* CONFIG_SCHED_DEBUG */ 1730 1731 extern void init_cfs_rq(struct cfs_rq *cfs_rq); 1732 extern void init_rt_rq(struct rt_rq *rt_rq); 1733 extern void init_dl_rq(struct dl_rq *dl_rq); 1734 1735 extern void cfs_bandwidth_usage_inc(void); 1736 extern void cfs_bandwidth_usage_dec(void); 1737 1738 #ifdef CONFIG_NO_HZ_COMMON 1739 enum rq_nohz_flag_bits { 1740 NOHZ_TICK_STOPPED, 1741 NOHZ_BALANCE_KICK, 1742 }; 1743 1744 #define nohz_flags(cpu) (&cpu_rq(cpu)->nohz_flags) 1745 1746 extern void nohz_balance_exit_idle(unsigned int cpu); 1747 #else 1748 static inline void nohz_balance_exit_idle(unsigned int cpu) { } 1749 #endif 1750 1751 #ifdef CONFIG_IRQ_TIME_ACCOUNTING 1752 struct irqtime { 1753 u64 hardirq_time; 1754 u64 softirq_time; 1755 u64 irq_start_time; 1756 struct u64_stats_sync sync; 1757 }; 1758 1759 DECLARE_PER_CPU(struct irqtime, cpu_irqtime); 1760 1761 static inline u64 irq_time_read(int cpu) 1762 { 1763 struct irqtime *irqtime = &per_cpu(cpu_irqtime, cpu); 1764 unsigned int seq; 1765 u64 total; 1766 1767 do { 1768 seq = __u64_stats_fetch_begin(&irqtime->sync); 1769 total = irqtime->softirq_time + irqtime->hardirq_time; 1770 } while (__u64_stats_fetch_retry(&irqtime->sync, seq)); 1771 1772 return total; 1773 } 1774 #endif /* CONFIG_IRQ_TIME_ACCOUNTING */ 1775 1776 #ifdef CONFIG_CPU_FREQ 1777 DECLARE_PER_CPU(struct update_util_data *, cpufreq_update_util_data); 1778 1779 /** 1780 * cpufreq_update_util - Take a note about CPU utilization changes. 1781 * @rq: Runqueue to carry out the update for. 1782 * @flags: Update reason flags. 1783 * 1784 * This function is called by the scheduler on the CPU whose utilization is 1785 * being updated. 1786 * 1787 * It can only be called from RCU-sched read-side critical sections. 1788 * 1789 * The way cpufreq is currently arranged requires it to evaluate the CPU 1790 * performance state (frequency/voltage) on a regular basis to prevent it from 1791 * being stuck in a completely inadequate performance level for too long. 1792 * That is not guaranteed to happen if the updates are only triggered from CFS, 1793 * though, because they may not be coming in if RT or deadline tasks are active 1794 * all the time (or there are RT and DL tasks only). 1795 * 1796 * As a workaround for that issue, this function is called by the RT and DL 1797 * sched classes to trigger extra cpufreq updates to prevent it from stalling, 1798 * but that really is a band-aid. Going forward it should be replaced with 1799 * solutions targeted more specifically at RT and DL tasks. 1800 */ 1801 static inline void cpufreq_update_util(struct rq *rq, unsigned int flags) 1802 { 1803 struct update_util_data *data; 1804 1805 data = rcu_dereference_sched(*this_cpu_ptr(&cpufreq_update_util_data)); 1806 if (data) 1807 data->func(data, rq_clock(rq), flags); 1808 } 1809 1810 static inline void cpufreq_update_this_cpu(struct rq *rq, unsigned int flags) 1811 { 1812 if (cpu_of(rq) == smp_processor_id()) 1813 cpufreq_update_util(rq, flags); 1814 } 1815 #else 1816 static inline void cpufreq_update_util(struct rq *rq, unsigned int flags) {} 1817 static inline void cpufreq_update_this_cpu(struct rq *rq, unsigned int flags) {} 1818 #endif /* CONFIG_CPU_FREQ */ 1819 1820 #ifdef arch_scale_freq_capacity 1821 #ifndef arch_scale_freq_invariant 1822 #define arch_scale_freq_invariant() (true) 1823 #endif 1824 #else /* arch_scale_freq_capacity */ 1825 #define arch_scale_freq_invariant() (false) 1826 #endif 1827