1 2 #include <linux/sched.h> 3 #include <linux/sched/sysctl.h> 4 #include <linux/sched/rt.h> 5 #include <linux/mutex.h> 6 #include <linux/spinlock.h> 7 #include <linux/stop_machine.h> 8 9 #include "cpupri.h" 10 #include "cpuacct.h" 11 12 extern __read_mostly int scheduler_running; 13 14 /* 15 * Convert user-nice values [ -20 ... 0 ... 19 ] 16 * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ], 17 * and back. 18 */ 19 #define NICE_TO_PRIO(nice) (MAX_RT_PRIO + (nice) + 20) 20 #define PRIO_TO_NICE(prio) ((prio) - MAX_RT_PRIO - 20) 21 #define TASK_NICE(p) PRIO_TO_NICE((p)->static_prio) 22 23 /* 24 * 'User priority' is the nice value converted to something we 25 * can work with better when scaling various scheduler parameters, 26 * it's a [ 0 ... 39 ] range. 27 */ 28 #define USER_PRIO(p) ((p)-MAX_RT_PRIO) 29 #define TASK_USER_PRIO(p) USER_PRIO((p)->static_prio) 30 #define MAX_USER_PRIO (USER_PRIO(MAX_PRIO)) 31 32 /* 33 * Helpers for converting nanosecond timing to jiffy resolution 34 */ 35 #define NS_TO_JIFFIES(TIME) ((unsigned long)(TIME) / (NSEC_PER_SEC / HZ)) 36 37 /* 38 * Increase resolution of nice-level calculations for 64-bit architectures. 39 * The extra resolution improves shares distribution and load balancing of 40 * low-weight task groups (eg. nice +19 on an autogroup), deeper taskgroup 41 * hierarchies, especially on larger systems. This is not a user-visible change 42 * and does not change the user-interface for setting shares/weights. 43 * 44 * We increase resolution only if we have enough bits to allow this increased 45 * resolution (i.e. BITS_PER_LONG > 32). The costs for increasing resolution 46 * when BITS_PER_LONG <= 32 are pretty high and the returns do not justify the 47 * increased costs. 48 */ 49 #if 0 /* BITS_PER_LONG > 32 -- currently broken: it increases power usage under light load */ 50 # define SCHED_LOAD_RESOLUTION 10 51 # define scale_load(w) ((w) << SCHED_LOAD_RESOLUTION) 52 # define scale_load_down(w) ((w) >> SCHED_LOAD_RESOLUTION) 53 #else 54 # define SCHED_LOAD_RESOLUTION 0 55 # define scale_load(w) (w) 56 # define scale_load_down(w) (w) 57 #endif 58 59 #define SCHED_LOAD_SHIFT (10 + SCHED_LOAD_RESOLUTION) 60 #define SCHED_LOAD_SCALE (1L << SCHED_LOAD_SHIFT) 61 62 #define NICE_0_LOAD SCHED_LOAD_SCALE 63 #define NICE_0_SHIFT SCHED_LOAD_SHIFT 64 65 /* 66 * These are the 'tuning knobs' of the scheduler: 67 */ 68 69 /* 70 * single value that denotes runtime == period, ie unlimited time. 71 */ 72 #define RUNTIME_INF ((u64)~0ULL) 73 74 static inline int rt_policy(int policy) 75 { 76 if (policy == SCHED_FIFO || policy == SCHED_RR) 77 return 1; 78 return 0; 79 } 80 81 static inline int task_has_rt_policy(struct task_struct *p) 82 { 83 return rt_policy(p->policy); 84 } 85 86 /* 87 * This is the priority-queue data structure of the RT scheduling class: 88 */ 89 struct rt_prio_array { 90 DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */ 91 struct list_head queue[MAX_RT_PRIO]; 92 }; 93 94 struct rt_bandwidth { 95 /* nests inside the rq lock: */ 96 raw_spinlock_t rt_runtime_lock; 97 ktime_t rt_period; 98 u64 rt_runtime; 99 struct hrtimer rt_period_timer; 100 }; 101 102 extern struct mutex sched_domains_mutex; 103 104 #ifdef CONFIG_CGROUP_SCHED 105 106 #include <linux/cgroup.h> 107 108 struct cfs_rq; 109 struct rt_rq; 110 111 extern struct list_head task_groups; 112 113 struct cfs_bandwidth { 114 #ifdef CONFIG_CFS_BANDWIDTH 115 raw_spinlock_t lock; 116 ktime_t period; 117 u64 quota, runtime; 118 s64 hierarchal_quota; 119 u64 runtime_expires; 120 121 int idle, timer_active; 122 struct hrtimer period_timer, slack_timer; 123 struct list_head throttled_cfs_rq; 124 125 /* statistics */ 126 int nr_periods, nr_throttled; 127 u64 throttled_time; 128 #endif 129 }; 130 131 /* task group related information */ 132 struct task_group { 133 struct cgroup_subsys_state css; 134 135 #ifdef CONFIG_FAIR_GROUP_SCHED 136 /* schedulable entities of this group on each cpu */ 137 struct sched_entity **se; 138 /* runqueue "owned" by this group on each cpu */ 139 struct cfs_rq **cfs_rq; 140 unsigned long shares; 141 142 atomic_t load_weight; 143 atomic64_t load_avg; 144 atomic_t runnable_avg; 145 #endif 146 147 #ifdef CONFIG_RT_GROUP_SCHED 148 struct sched_rt_entity **rt_se; 149 struct rt_rq **rt_rq; 150 151 struct rt_bandwidth rt_bandwidth; 152 #endif 153 154 struct rcu_head rcu; 155 struct list_head list; 156 157 struct task_group *parent; 158 struct list_head siblings; 159 struct list_head children; 160 161 #ifdef CONFIG_SCHED_AUTOGROUP 162 struct autogroup *autogroup; 163 #endif 164 165 struct cfs_bandwidth cfs_bandwidth; 166 }; 167 168 #ifdef CONFIG_FAIR_GROUP_SCHED 169 #define ROOT_TASK_GROUP_LOAD NICE_0_LOAD 170 171 /* 172 * A weight of 0 or 1 can cause arithmetics problems. 173 * A weight of a cfs_rq is the sum of weights of which entities 174 * are queued on this cfs_rq, so a weight of a entity should not be 175 * too large, so as the shares value of a task group. 176 * (The default weight is 1024 - so there's no practical 177 * limitation from this.) 178 */ 179 #define MIN_SHARES (1UL << 1) 180 #define MAX_SHARES (1UL << 18) 181 #endif 182 183 typedef int (*tg_visitor)(struct task_group *, void *); 184 185 extern int walk_tg_tree_from(struct task_group *from, 186 tg_visitor down, tg_visitor up, void *data); 187 188 /* 189 * Iterate the full tree, calling @down when first entering a node and @up when 190 * leaving it for the final time. 191 * 192 * Caller must hold rcu_lock or sufficient equivalent. 193 */ 194 static inline int walk_tg_tree(tg_visitor down, tg_visitor up, void *data) 195 { 196 return walk_tg_tree_from(&root_task_group, down, up, data); 197 } 198 199 extern int tg_nop(struct task_group *tg, void *data); 200 201 extern void free_fair_sched_group(struct task_group *tg); 202 extern int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent); 203 extern void unregister_fair_sched_group(struct task_group *tg, int cpu); 204 extern void init_tg_cfs_entry(struct task_group *tg, struct cfs_rq *cfs_rq, 205 struct sched_entity *se, int cpu, 206 struct sched_entity *parent); 207 extern void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b); 208 extern int sched_group_set_shares(struct task_group *tg, unsigned long shares); 209 210 extern void __refill_cfs_bandwidth_runtime(struct cfs_bandwidth *cfs_b); 211 extern void __start_cfs_bandwidth(struct cfs_bandwidth *cfs_b); 212 extern void unthrottle_cfs_rq(struct cfs_rq *cfs_rq); 213 214 extern void free_rt_sched_group(struct task_group *tg); 215 extern int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent); 216 extern void init_tg_rt_entry(struct task_group *tg, struct rt_rq *rt_rq, 217 struct sched_rt_entity *rt_se, int cpu, 218 struct sched_rt_entity *parent); 219 220 extern struct task_group *sched_create_group(struct task_group *parent); 221 extern void sched_online_group(struct task_group *tg, 222 struct task_group *parent); 223 extern void sched_destroy_group(struct task_group *tg); 224 extern void sched_offline_group(struct task_group *tg); 225 226 extern void sched_move_task(struct task_struct *tsk); 227 228 #ifdef CONFIG_FAIR_GROUP_SCHED 229 extern int sched_group_set_shares(struct task_group *tg, unsigned long shares); 230 #endif 231 232 #else /* CONFIG_CGROUP_SCHED */ 233 234 struct cfs_bandwidth { }; 235 236 #endif /* CONFIG_CGROUP_SCHED */ 237 238 /* CFS-related fields in a runqueue */ 239 struct cfs_rq { 240 struct load_weight load; 241 unsigned int nr_running, h_nr_running; 242 243 u64 exec_clock; 244 u64 min_vruntime; 245 #ifndef CONFIG_64BIT 246 u64 min_vruntime_copy; 247 #endif 248 249 struct rb_root tasks_timeline; 250 struct rb_node *rb_leftmost; 251 252 /* 253 * 'curr' points to currently running entity on this cfs_rq. 254 * It is set to NULL otherwise (i.e when none are currently running). 255 */ 256 struct sched_entity *curr, *next, *last, *skip; 257 258 #ifdef CONFIG_SCHED_DEBUG 259 unsigned int nr_spread_over; 260 #endif 261 262 #ifdef CONFIG_SMP 263 /* 264 * Load-tracking only depends on SMP, FAIR_GROUP_SCHED dependency below may be 265 * removed when useful for applications beyond shares distribution (e.g. 266 * load-balance). 267 */ 268 #ifdef CONFIG_FAIR_GROUP_SCHED 269 /* 270 * CFS Load tracking 271 * Under CFS, load is tracked on a per-entity basis and aggregated up. 272 * This allows for the description of both thread and group usage (in 273 * the FAIR_GROUP_SCHED case). 274 */ 275 u64 runnable_load_avg, blocked_load_avg; 276 atomic64_t decay_counter, removed_load; 277 u64 last_decay; 278 #endif /* CONFIG_FAIR_GROUP_SCHED */ 279 /* These always depend on CONFIG_FAIR_GROUP_SCHED */ 280 #ifdef CONFIG_FAIR_GROUP_SCHED 281 u32 tg_runnable_contrib; 282 u64 tg_load_contrib; 283 #endif /* CONFIG_FAIR_GROUP_SCHED */ 284 285 /* 286 * h_load = weight * f(tg) 287 * 288 * Where f(tg) is the recursive weight fraction assigned to 289 * this group. 290 */ 291 unsigned long h_load; 292 #endif /* CONFIG_SMP */ 293 294 #ifdef CONFIG_FAIR_GROUP_SCHED 295 struct rq *rq; /* cpu runqueue to which this cfs_rq is attached */ 296 297 /* 298 * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in 299 * a hierarchy). Non-leaf lrqs hold other higher schedulable entities 300 * (like users, containers etc.) 301 * 302 * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This 303 * list is used during load balance. 304 */ 305 int on_list; 306 struct list_head leaf_cfs_rq_list; 307 struct task_group *tg; /* group that "owns" this runqueue */ 308 309 #ifdef CONFIG_CFS_BANDWIDTH 310 int runtime_enabled; 311 u64 runtime_expires; 312 s64 runtime_remaining; 313 314 u64 throttled_clock, throttled_clock_task; 315 u64 throttled_clock_task_time; 316 int throttled, throttle_count; 317 struct list_head throttled_list; 318 #endif /* CONFIG_CFS_BANDWIDTH */ 319 #endif /* CONFIG_FAIR_GROUP_SCHED */ 320 }; 321 322 static inline int rt_bandwidth_enabled(void) 323 { 324 return sysctl_sched_rt_runtime >= 0; 325 } 326 327 /* Real-Time classes' related field in a runqueue: */ 328 struct rt_rq { 329 struct rt_prio_array active; 330 unsigned int rt_nr_running; 331 #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED 332 struct { 333 int curr; /* highest queued rt task prio */ 334 #ifdef CONFIG_SMP 335 int next; /* next highest */ 336 #endif 337 } highest_prio; 338 #endif 339 #ifdef CONFIG_SMP 340 unsigned long rt_nr_migratory; 341 unsigned long rt_nr_total; 342 int overloaded; 343 struct plist_head pushable_tasks; 344 #endif 345 int rt_throttled; 346 u64 rt_time; 347 u64 rt_runtime; 348 /* Nests inside the rq lock: */ 349 raw_spinlock_t rt_runtime_lock; 350 351 #ifdef CONFIG_RT_GROUP_SCHED 352 unsigned long rt_nr_boosted; 353 354 struct rq *rq; 355 struct list_head leaf_rt_rq_list; 356 struct task_group *tg; 357 #endif 358 }; 359 360 #ifdef CONFIG_SMP 361 362 /* 363 * We add the notion of a root-domain which will be used to define per-domain 364 * variables. Each exclusive cpuset essentially defines an island domain by 365 * fully partitioning the member cpus from any other cpuset. Whenever a new 366 * exclusive cpuset is created, we also create and attach a new root-domain 367 * object. 368 * 369 */ 370 struct root_domain { 371 atomic_t refcount; 372 atomic_t rto_count; 373 struct rcu_head rcu; 374 cpumask_var_t span; 375 cpumask_var_t online; 376 377 /* 378 * The "RT overload" flag: it gets set if a CPU has more than 379 * one runnable RT task. 380 */ 381 cpumask_var_t rto_mask; 382 struct cpupri cpupri; 383 }; 384 385 extern struct root_domain def_root_domain; 386 387 #endif /* CONFIG_SMP */ 388 389 /* 390 * This is the main, per-CPU runqueue data structure. 391 * 392 * Locking rule: those places that want to lock multiple runqueues 393 * (such as the load balancing or the thread migration code), lock 394 * acquire operations must be ordered by ascending &runqueue. 395 */ 396 struct rq { 397 /* runqueue lock: */ 398 raw_spinlock_t lock; 399 400 /* 401 * nr_running and cpu_load should be in the same cacheline because 402 * remote CPUs use both these fields when doing load calculation. 403 */ 404 unsigned int nr_running; 405 #define CPU_LOAD_IDX_MAX 5 406 unsigned long cpu_load[CPU_LOAD_IDX_MAX]; 407 unsigned long last_load_update_tick; 408 #ifdef CONFIG_NO_HZ 409 u64 nohz_stamp; 410 unsigned long nohz_flags; 411 #endif 412 int skip_clock_update; 413 414 /* capture load from *all* tasks on this cpu: */ 415 struct load_weight load; 416 unsigned long nr_load_updates; 417 u64 nr_switches; 418 419 struct cfs_rq cfs; 420 struct rt_rq rt; 421 422 #ifdef CONFIG_FAIR_GROUP_SCHED 423 /* list of leaf cfs_rq on this cpu: */ 424 struct list_head leaf_cfs_rq_list; 425 #ifdef CONFIG_SMP 426 unsigned long h_load_throttle; 427 #endif /* CONFIG_SMP */ 428 #endif /* CONFIG_FAIR_GROUP_SCHED */ 429 430 #ifdef CONFIG_RT_GROUP_SCHED 431 struct list_head leaf_rt_rq_list; 432 #endif 433 434 /* 435 * This is part of a global counter where only the total sum 436 * over all CPUs matters. A task can increase this counter on 437 * one CPU and if it got migrated afterwards it may decrease 438 * it on another CPU. Always updated under the runqueue lock: 439 */ 440 unsigned long nr_uninterruptible; 441 442 struct task_struct *curr, *idle, *stop; 443 unsigned long next_balance; 444 struct mm_struct *prev_mm; 445 446 u64 clock; 447 u64 clock_task; 448 449 atomic_t nr_iowait; 450 451 #ifdef CONFIG_SMP 452 struct root_domain *rd; 453 struct sched_domain *sd; 454 455 unsigned long cpu_power; 456 457 unsigned char idle_balance; 458 /* For active balancing */ 459 int post_schedule; 460 int active_balance; 461 int push_cpu; 462 struct cpu_stop_work active_balance_work; 463 /* cpu of this runqueue: */ 464 int cpu; 465 int online; 466 467 struct list_head cfs_tasks; 468 469 u64 rt_avg; 470 u64 age_stamp; 471 u64 idle_stamp; 472 u64 avg_idle; 473 #endif 474 475 #ifdef CONFIG_IRQ_TIME_ACCOUNTING 476 u64 prev_irq_time; 477 #endif 478 #ifdef CONFIG_PARAVIRT 479 u64 prev_steal_time; 480 #endif 481 #ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING 482 u64 prev_steal_time_rq; 483 #endif 484 485 /* calc_load related fields */ 486 unsigned long calc_load_update; 487 long calc_load_active; 488 489 #ifdef CONFIG_SCHED_HRTICK 490 #ifdef CONFIG_SMP 491 int hrtick_csd_pending; 492 struct call_single_data hrtick_csd; 493 #endif 494 struct hrtimer hrtick_timer; 495 #endif 496 497 #ifdef CONFIG_SCHEDSTATS 498 /* latency stats */ 499 struct sched_info rq_sched_info; 500 unsigned long long rq_cpu_time; 501 /* could above be rq->cfs_rq.exec_clock + rq->rt_rq.rt_runtime ? */ 502 503 /* sys_sched_yield() stats */ 504 unsigned int yld_count; 505 506 /* schedule() stats */ 507 unsigned int sched_count; 508 unsigned int sched_goidle; 509 510 /* try_to_wake_up() stats */ 511 unsigned int ttwu_count; 512 unsigned int ttwu_local; 513 #endif 514 515 #ifdef CONFIG_SMP 516 struct llist_head wake_list; 517 #endif 518 519 struct sched_avg avg; 520 }; 521 522 static inline int cpu_of(struct rq *rq) 523 { 524 #ifdef CONFIG_SMP 525 return rq->cpu; 526 #else 527 return 0; 528 #endif 529 } 530 531 DECLARE_PER_CPU(struct rq, runqueues); 532 533 #define cpu_rq(cpu) (&per_cpu(runqueues, (cpu))) 534 #define this_rq() (&__get_cpu_var(runqueues)) 535 #define task_rq(p) cpu_rq(task_cpu(p)) 536 #define cpu_curr(cpu) (cpu_rq(cpu)->curr) 537 #define raw_rq() (&__raw_get_cpu_var(runqueues)) 538 539 #ifdef CONFIG_SMP 540 541 #define rcu_dereference_check_sched_domain(p) \ 542 rcu_dereference_check((p), \ 543 lockdep_is_held(&sched_domains_mutex)) 544 545 /* 546 * The domain tree (rq->sd) is protected by RCU's quiescent state transition. 547 * See detach_destroy_domains: synchronize_sched for details. 548 * 549 * The domain tree of any CPU may only be accessed from within 550 * preempt-disabled sections. 551 */ 552 #define for_each_domain(cpu, __sd) \ 553 for (__sd = rcu_dereference_check_sched_domain(cpu_rq(cpu)->sd); \ 554 __sd; __sd = __sd->parent) 555 556 #define for_each_lower_domain(sd) for (; sd; sd = sd->child) 557 558 /** 559 * highest_flag_domain - Return highest sched_domain containing flag. 560 * @cpu: The cpu whose highest level of sched domain is to 561 * be returned. 562 * @flag: The flag to check for the highest sched_domain 563 * for the given cpu. 564 * 565 * Returns the highest sched_domain of a cpu which contains the given flag. 566 */ 567 static inline struct sched_domain *highest_flag_domain(int cpu, int flag) 568 { 569 struct sched_domain *sd, *hsd = NULL; 570 571 for_each_domain(cpu, sd) { 572 if (!(sd->flags & flag)) 573 break; 574 hsd = sd; 575 } 576 577 return hsd; 578 } 579 580 DECLARE_PER_CPU(struct sched_domain *, sd_llc); 581 DECLARE_PER_CPU(int, sd_llc_id); 582 583 struct sched_group_power { 584 atomic_t ref; 585 /* 586 * CPU power of this group, SCHED_LOAD_SCALE being max power for a 587 * single CPU. 588 */ 589 unsigned int power, power_orig; 590 unsigned long next_update; 591 /* 592 * Number of busy cpus in this group. 593 */ 594 atomic_t nr_busy_cpus; 595 596 unsigned long cpumask[0]; /* iteration mask */ 597 }; 598 599 struct sched_group { 600 struct sched_group *next; /* Must be a circular list */ 601 atomic_t ref; 602 603 unsigned int group_weight; 604 struct sched_group_power *sgp; 605 606 /* 607 * The CPUs this group covers. 608 * 609 * NOTE: this field is variable length. (Allocated dynamically 610 * by attaching extra space to the end of the structure, 611 * depending on how many CPUs the kernel has booted up with) 612 */ 613 unsigned long cpumask[0]; 614 }; 615 616 static inline struct cpumask *sched_group_cpus(struct sched_group *sg) 617 { 618 return to_cpumask(sg->cpumask); 619 } 620 621 /* 622 * cpumask masking which cpus in the group are allowed to iterate up the domain 623 * tree. 624 */ 625 static inline struct cpumask *sched_group_mask(struct sched_group *sg) 626 { 627 return to_cpumask(sg->sgp->cpumask); 628 } 629 630 /** 631 * group_first_cpu - Returns the first cpu in the cpumask of a sched_group. 632 * @group: The group whose first cpu is to be returned. 633 */ 634 static inline unsigned int group_first_cpu(struct sched_group *group) 635 { 636 return cpumask_first(sched_group_cpus(group)); 637 } 638 639 extern int group_balance_cpu(struct sched_group *sg); 640 641 #endif /* CONFIG_SMP */ 642 643 #include "stats.h" 644 #include "auto_group.h" 645 646 #ifdef CONFIG_CGROUP_SCHED 647 648 /* 649 * Return the group to which this tasks belongs. 650 * 651 * We cannot use task_subsys_state() and friends because the cgroup 652 * subsystem changes that value before the cgroup_subsys::attach() method 653 * is called, therefore we cannot pin it and might observe the wrong value. 654 * 655 * The same is true for autogroup's p->signal->autogroup->tg, the autogroup 656 * core changes this before calling sched_move_task(). 657 * 658 * Instead we use a 'copy' which is updated from sched_move_task() while 659 * holding both task_struct::pi_lock and rq::lock. 660 */ 661 static inline struct task_group *task_group(struct task_struct *p) 662 { 663 return p->sched_task_group; 664 } 665 666 /* Change a task's cfs_rq and parent entity if it moves across CPUs/groups */ 667 static inline void set_task_rq(struct task_struct *p, unsigned int cpu) 668 { 669 #if defined(CONFIG_FAIR_GROUP_SCHED) || defined(CONFIG_RT_GROUP_SCHED) 670 struct task_group *tg = task_group(p); 671 #endif 672 673 #ifdef CONFIG_FAIR_GROUP_SCHED 674 p->se.cfs_rq = tg->cfs_rq[cpu]; 675 p->se.parent = tg->se[cpu]; 676 #endif 677 678 #ifdef CONFIG_RT_GROUP_SCHED 679 p->rt.rt_rq = tg->rt_rq[cpu]; 680 p->rt.parent = tg->rt_se[cpu]; 681 #endif 682 } 683 684 #else /* CONFIG_CGROUP_SCHED */ 685 686 static inline void set_task_rq(struct task_struct *p, unsigned int cpu) { } 687 static inline struct task_group *task_group(struct task_struct *p) 688 { 689 return NULL; 690 } 691 692 #endif /* CONFIG_CGROUP_SCHED */ 693 694 static inline void __set_task_cpu(struct task_struct *p, unsigned int cpu) 695 { 696 set_task_rq(p, cpu); 697 #ifdef CONFIG_SMP 698 /* 699 * After ->cpu is set up to a new value, task_rq_lock(p, ...) can be 700 * successfuly executed on another CPU. We must ensure that updates of 701 * per-task data have been completed by this moment. 702 */ 703 smp_wmb(); 704 task_thread_info(p)->cpu = cpu; 705 #endif 706 } 707 708 /* 709 * Tunables that become constants when CONFIG_SCHED_DEBUG is off: 710 */ 711 #ifdef CONFIG_SCHED_DEBUG 712 # include <linux/static_key.h> 713 # define const_debug __read_mostly 714 #else 715 # define const_debug const 716 #endif 717 718 extern const_debug unsigned int sysctl_sched_features; 719 720 #define SCHED_FEAT(name, enabled) \ 721 __SCHED_FEAT_##name , 722 723 enum { 724 #include "features.h" 725 __SCHED_FEAT_NR, 726 }; 727 728 #undef SCHED_FEAT 729 730 #if defined(CONFIG_SCHED_DEBUG) && defined(HAVE_JUMP_LABEL) 731 static __always_inline bool static_branch__true(struct static_key *key) 732 { 733 return static_key_true(key); /* Not out of line branch. */ 734 } 735 736 static __always_inline bool static_branch__false(struct static_key *key) 737 { 738 return static_key_false(key); /* Out of line branch. */ 739 } 740 741 #define SCHED_FEAT(name, enabled) \ 742 static __always_inline bool static_branch_##name(struct static_key *key) \ 743 { \ 744 return static_branch__##enabled(key); \ 745 } 746 747 #include "features.h" 748 749 #undef SCHED_FEAT 750 751 extern struct static_key sched_feat_keys[__SCHED_FEAT_NR]; 752 #define sched_feat(x) (static_branch_##x(&sched_feat_keys[__SCHED_FEAT_##x])) 753 #else /* !(SCHED_DEBUG && HAVE_JUMP_LABEL) */ 754 #define sched_feat(x) (sysctl_sched_features & (1UL << __SCHED_FEAT_##x)) 755 #endif /* SCHED_DEBUG && HAVE_JUMP_LABEL */ 756 757 #ifdef CONFIG_NUMA_BALANCING 758 #define sched_feat_numa(x) sched_feat(x) 759 #ifdef CONFIG_SCHED_DEBUG 760 #define numabalancing_enabled sched_feat_numa(NUMA) 761 #else 762 extern bool numabalancing_enabled; 763 #endif /* CONFIG_SCHED_DEBUG */ 764 #else 765 #define sched_feat_numa(x) (0) 766 #define numabalancing_enabled (0) 767 #endif /* CONFIG_NUMA_BALANCING */ 768 769 static inline u64 global_rt_period(void) 770 { 771 return (u64)sysctl_sched_rt_period * NSEC_PER_USEC; 772 } 773 774 static inline u64 global_rt_runtime(void) 775 { 776 if (sysctl_sched_rt_runtime < 0) 777 return RUNTIME_INF; 778 779 return (u64)sysctl_sched_rt_runtime * NSEC_PER_USEC; 780 } 781 782 783 784 static inline int task_current(struct rq *rq, struct task_struct *p) 785 { 786 return rq->curr == p; 787 } 788 789 static inline int task_running(struct rq *rq, struct task_struct *p) 790 { 791 #ifdef CONFIG_SMP 792 return p->on_cpu; 793 #else 794 return task_current(rq, p); 795 #endif 796 } 797 798 799 #ifndef prepare_arch_switch 800 # define prepare_arch_switch(next) do { } while (0) 801 #endif 802 #ifndef finish_arch_switch 803 # define finish_arch_switch(prev) do { } while (0) 804 #endif 805 #ifndef finish_arch_post_lock_switch 806 # define finish_arch_post_lock_switch() do { } while (0) 807 #endif 808 809 #ifndef __ARCH_WANT_UNLOCKED_CTXSW 810 static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next) 811 { 812 #ifdef CONFIG_SMP 813 /* 814 * We can optimise this out completely for !SMP, because the 815 * SMP rebalancing from interrupt is the only thing that cares 816 * here. 817 */ 818 next->on_cpu = 1; 819 #endif 820 } 821 822 static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev) 823 { 824 #ifdef CONFIG_SMP 825 /* 826 * After ->on_cpu is cleared, the task can be moved to a different CPU. 827 * We must ensure this doesn't happen until the switch is completely 828 * finished. 829 */ 830 smp_wmb(); 831 prev->on_cpu = 0; 832 #endif 833 #ifdef CONFIG_DEBUG_SPINLOCK 834 /* this is a valid case when another task releases the spinlock */ 835 rq->lock.owner = current; 836 #endif 837 /* 838 * If we are tracking spinlock dependencies then we have to 839 * fix up the runqueue lock - which gets 'carried over' from 840 * prev into current: 841 */ 842 spin_acquire(&rq->lock.dep_map, 0, 0, _THIS_IP_); 843 844 raw_spin_unlock_irq(&rq->lock); 845 } 846 847 #else /* __ARCH_WANT_UNLOCKED_CTXSW */ 848 static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next) 849 { 850 #ifdef CONFIG_SMP 851 /* 852 * We can optimise this out completely for !SMP, because the 853 * SMP rebalancing from interrupt is the only thing that cares 854 * here. 855 */ 856 next->on_cpu = 1; 857 #endif 858 raw_spin_unlock(&rq->lock); 859 } 860 861 static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev) 862 { 863 #ifdef CONFIG_SMP 864 /* 865 * After ->on_cpu is cleared, the task can be moved to a different CPU. 866 * We must ensure this doesn't happen until the switch is completely 867 * finished. 868 */ 869 smp_wmb(); 870 prev->on_cpu = 0; 871 #endif 872 local_irq_enable(); 873 } 874 #endif /* __ARCH_WANT_UNLOCKED_CTXSW */ 875 876 /* 877 * wake flags 878 */ 879 #define WF_SYNC 0x01 /* waker goes to sleep after wakeup */ 880 #define WF_FORK 0x02 /* child wakeup after fork */ 881 #define WF_MIGRATED 0x4 /* internal use, task got migrated */ 882 883 static inline void update_load_add(struct load_weight *lw, unsigned long inc) 884 { 885 lw->weight += inc; 886 lw->inv_weight = 0; 887 } 888 889 static inline void update_load_sub(struct load_weight *lw, unsigned long dec) 890 { 891 lw->weight -= dec; 892 lw->inv_weight = 0; 893 } 894 895 static inline void update_load_set(struct load_weight *lw, unsigned long w) 896 { 897 lw->weight = w; 898 lw->inv_weight = 0; 899 } 900 901 /* 902 * To aid in avoiding the subversion of "niceness" due to uneven distribution 903 * of tasks with abnormal "nice" values across CPUs the contribution that 904 * each task makes to its run queue's load is weighted according to its 905 * scheduling class and "nice" value. For SCHED_NORMAL tasks this is just a 906 * scaled version of the new time slice allocation that they receive on time 907 * slice expiry etc. 908 */ 909 910 #define WEIGHT_IDLEPRIO 3 911 #define WMULT_IDLEPRIO 1431655765 912 913 /* 914 * Nice levels are multiplicative, with a gentle 10% change for every 915 * nice level changed. I.e. when a CPU-bound task goes from nice 0 to 916 * nice 1, it will get ~10% less CPU time than another CPU-bound task 917 * that remained on nice 0. 918 * 919 * The "10% effect" is relative and cumulative: from _any_ nice level, 920 * if you go up 1 level, it's -10% CPU usage, if you go down 1 level 921 * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25. 922 * If a task goes up by ~10% and another task goes down by ~10% then 923 * the relative distance between them is ~25%.) 924 */ 925 static const int prio_to_weight[40] = { 926 /* -20 */ 88761, 71755, 56483, 46273, 36291, 927 /* -15 */ 29154, 23254, 18705, 14949, 11916, 928 /* -10 */ 9548, 7620, 6100, 4904, 3906, 929 /* -5 */ 3121, 2501, 1991, 1586, 1277, 930 /* 0 */ 1024, 820, 655, 526, 423, 931 /* 5 */ 335, 272, 215, 172, 137, 932 /* 10 */ 110, 87, 70, 56, 45, 933 /* 15 */ 36, 29, 23, 18, 15, 934 }; 935 936 /* 937 * Inverse (2^32/x) values of the prio_to_weight[] array, precalculated. 938 * 939 * In cases where the weight does not change often, we can use the 940 * precalculated inverse to speed up arithmetics by turning divisions 941 * into multiplications: 942 */ 943 static const u32 prio_to_wmult[40] = { 944 /* -20 */ 48388, 59856, 76040, 92818, 118348, 945 /* -15 */ 147320, 184698, 229616, 287308, 360437, 946 /* -10 */ 449829, 563644, 704093, 875809, 1099582, 947 /* -5 */ 1376151, 1717300, 2157191, 2708050, 3363326, 948 /* 0 */ 4194304, 5237765, 6557202, 8165337, 10153587, 949 /* 5 */ 12820798, 15790321, 19976592, 24970740, 31350126, 950 /* 10 */ 39045157, 49367440, 61356676, 76695844, 95443717, 951 /* 15 */ 119304647, 148102320, 186737708, 238609294, 286331153, 952 }; 953 954 #define ENQUEUE_WAKEUP 1 955 #define ENQUEUE_HEAD 2 956 #ifdef CONFIG_SMP 957 #define ENQUEUE_WAKING 4 /* sched_class::task_waking was called */ 958 #else 959 #define ENQUEUE_WAKING 0 960 #endif 961 962 #define DEQUEUE_SLEEP 1 963 964 struct sched_class { 965 const struct sched_class *next; 966 967 void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags); 968 void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags); 969 void (*yield_task) (struct rq *rq); 970 bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt); 971 972 void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags); 973 974 struct task_struct * (*pick_next_task) (struct rq *rq); 975 void (*put_prev_task) (struct rq *rq, struct task_struct *p); 976 977 #ifdef CONFIG_SMP 978 int (*select_task_rq)(struct task_struct *p, int sd_flag, int flags); 979 void (*migrate_task_rq)(struct task_struct *p, int next_cpu); 980 981 void (*pre_schedule) (struct rq *this_rq, struct task_struct *task); 982 void (*post_schedule) (struct rq *this_rq); 983 void (*task_waking) (struct task_struct *task); 984 void (*task_woken) (struct rq *this_rq, struct task_struct *task); 985 986 void (*set_cpus_allowed)(struct task_struct *p, 987 const struct cpumask *newmask); 988 989 void (*rq_online)(struct rq *rq); 990 void (*rq_offline)(struct rq *rq); 991 #endif 992 993 void (*set_curr_task) (struct rq *rq); 994 void (*task_tick) (struct rq *rq, struct task_struct *p, int queued); 995 void (*task_fork) (struct task_struct *p); 996 997 void (*switched_from) (struct rq *this_rq, struct task_struct *task); 998 void (*switched_to) (struct rq *this_rq, struct task_struct *task); 999 void (*prio_changed) (struct rq *this_rq, struct task_struct *task, 1000 int oldprio); 1001 1002 unsigned int (*get_rr_interval) (struct rq *rq, 1003 struct task_struct *task); 1004 1005 #ifdef CONFIG_FAIR_GROUP_SCHED 1006 void (*task_move_group) (struct task_struct *p, int on_rq); 1007 #endif 1008 }; 1009 1010 #define sched_class_highest (&stop_sched_class) 1011 #define for_each_class(class) \ 1012 for (class = sched_class_highest; class; class = class->next) 1013 1014 extern const struct sched_class stop_sched_class; 1015 extern const struct sched_class rt_sched_class; 1016 extern const struct sched_class fair_sched_class; 1017 extern const struct sched_class idle_sched_class; 1018 1019 1020 #ifdef CONFIG_SMP 1021 1022 extern void update_group_power(struct sched_domain *sd, int cpu); 1023 1024 extern void trigger_load_balance(struct rq *rq, int cpu); 1025 extern void idle_balance(int this_cpu, struct rq *this_rq); 1026 1027 /* 1028 * Only depends on SMP, FAIR_GROUP_SCHED may be removed when runnable_avg 1029 * becomes useful in lb 1030 */ 1031 #if defined(CONFIG_FAIR_GROUP_SCHED) 1032 extern void idle_enter_fair(struct rq *this_rq); 1033 extern void idle_exit_fair(struct rq *this_rq); 1034 #else 1035 static inline void idle_enter_fair(struct rq *this_rq) {} 1036 static inline void idle_exit_fair(struct rq *this_rq) {} 1037 #endif 1038 1039 #else /* CONFIG_SMP */ 1040 1041 static inline void idle_balance(int cpu, struct rq *rq) 1042 { 1043 } 1044 1045 #endif 1046 1047 extern void sysrq_sched_debug_show(void); 1048 extern void sched_init_granularity(void); 1049 extern void update_max_interval(void); 1050 extern int update_runtime(struct notifier_block *nfb, unsigned long action, void *hcpu); 1051 extern void init_sched_rt_class(void); 1052 extern void init_sched_fair_class(void); 1053 1054 extern void resched_task(struct task_struct *p); 1055 extern void resched_cpu(int cpu); 1056 1057 extern struct rt_bandwidth def_rt_bandwidth; 1058 extern void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime); 1059 1060 extern void update_idle_cpu_load(struct rq *this_rq); 1061 1062 #ifdef CONFIG_PARAVIRT 1063 static inline u64 steal_ticks(u64 steal) 1064 { 1065 if (unlikely(steal > NSEC_PER_SEC)) 1066 return div_u64(steal, TICK_NSEC); 1067 1068 return __iter_div_u64_rem(steal, TICK_NSEC, &steal); 1069 } 1070 #endif 1071 1072 static inline void inc_nr_running(struct rq *rq) 1073 { 1074 rq->nr_running++; 1075 } 1076 1077 static inline void dec_nr_running(struct rq *rq) 1078 { 1079 rq->nr_running--; 1080 } 1081 1082 extern void update_rq_clock(struct rq *rq); 1083 1084 extern void activate_task(struct rq *rq, struct task_struct *p, int flags); 1085 extern void deactivate_task(struct rq *rq, struct task_struct *p, int flags); 1086 1087 extern void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags); 1088 1089 extern const_debug unsigned int sysctl_sched_time_avg; 1090 extern const_debug unsigned int sysctl_sched_nr_migrate; 1091 extern const_debug unsigned int sysctl_sched_migration_cost; 1092 1093 static inline u64 sched_avg_period(void) 1094 { 1095 return (u64)sysctl_sched_time_avg * NSEC_PER_MSEC / 2; 1096 } 1097 1098 #ifdef CONFIG_SCHED_HRTICK 1099 1100 /* 1101 * Use hrtick when: 1102 * - enabled by features 1103 * - hrtimer is actually high res 1104 */ 1105 static inline int hrtick_enabled(struct rq *rq) 1106 { 1107 if (!sched_feat(HRTICK)) 1108 return 0; 1109 if (!cpu_active(cpu_of(rq))) 1110 return 0; 1111 return hrtimer_is_hres_active(&rq->hrtick_timer); 1112 } 1113 1114 void hrtick_start(struct rq *rq, u64 delay); 1115 1116 #else 1117 1118 static inline int hrtick_enabled(struct rq *rq) 1119 { 1120 return 0; 1121 } 1122 1123 #endif /* CONFIG_SCHED_HRTICK */ 1124 1125 #ifdef CONFIG_SMP 1126 extern void sched_avg_update(struct rq *rq); 1127 static inline void sched_rt_avg_update(struct rq *rq, u64 rt_delta) 1128 { 1129 rq->rt_avg += rt_delta; 1130 sched_avg_update(rq); 1131 } 1132 #else 1133 static inline void sched_rt_avg_update(struct rq *rq, u64 rt_delta) { } 1134 static inline void sched_avg_update(struct rq *rq) { } 1135 #endif 1136 1137 extern void start_bandwidth_timer(struct hrtimer *period_timer, ktime_t period); 1138 1139 #ifdef CONFIG_SMP 1140 #ifdef CONFIG_PREEMPT 1141 1142 static inline void double_rq_lock(struct rq *rq1, struct rq *rq2); 1143 1144 /* 1145 * fair double_lock_balance: Safely acquires both rq->locks in a fair 1146 * way at the expense of forcing extra atomic operations in all 1147 * invocations. This assures that the double_lock is acquired using the 1148 * same underlying policy as the spinlock_t on this architecture, which 1149 * reduces latency compared to the unfair variant below. However, it 1150 * also adds more overhead and therefore may reduce throughput. 1151 */ 1152 static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest) 1153 __releases(this_rq->lock) 1154 __acquires(busiest->lock) 1155 __acquires(this_rq->lock) 1156 { 1157 raw_spin_unlock(&this_rq->lock); 1158 double_rq_lock(this_rq, busiest); 1159 1160 return 1; 1161 } 1162 1163 #else 1164 /* 1165 * Unfair double_lock_balance: Optimizes throughput at the expense of 1166 * latency by eliminating extra atomic operations when the locks are 1167 * already in proper order on entry. This favors lower cpu-ids and will 1168 * grant the double lock to lower cpus over higher ids under contention, 1169 * regardless of entry order into the function. 1170 */ 1171 static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest) 1172 __releases(this_rq->lock) 1173 __acquires(busiest->lock) 1174 __acquires(this_rq->lock) 1175 { 1176 int ret = 0; 1177 1178 if (unlikely(!raw_spin_trylock(&busiest->lock))) { 1179 if (busiest < this_rq) { 1180 raw_spin_unlock(&this_rq->lock); 1181 raw_spin_lock(&busiest->lock); 1182 raw_spin_lock_nested(&this_rq->lock, 1183 SINGLE_DEPTH_NESTING); 1184 ret = 1; 1185 } else 1186 raw_spin_lock_nested(&busiest->lock, 1187 SINGLE_DEPTH_NESTING); 1188 } 1189 return ret; 1190 } 1191 1192 #endif /* CONFIG_PREEMPT */ 1193 1194 /* 1195 * double_lock_balance - lock the busiest runqueue, this_rq is locked already. 1196 */ 1197 static inline int double_lock_balance(struct rq *this_rq, struct rq *busiest) 1198 { 1199 if (unlikely(!irqs_disabled())) { 1200 /* printk() doesn't work good under rq->lock */ 1201 raw_spin_unlock(&this_rq->lock); 1202 BUG_ON(1); 1203 } 1204 1205 return _double_lock_balance(this_rq, busiest); 1206 } 1207 1208 static inline void double_unlock_balance(struct rq *this_rq, struct rq *busiest) 1209 __releases(busiest->lock) 1210 { 1211 raw_spin_unlock(&busiest->lock); 1212 lock_set_subclass(&this_rq->lock.dep_map, 0, _RET_IP_); 1213 } 1214 1215 /* 1216 * double_rq_lock - safely lock two runqueues 1217 * 1218 * Note this does not disable interrupts like task_rq_lock, 1219 * you need to do so manually before calling. 1220 */ 1221 static inline void double_rq_lock(struct rq *rq1, struct rq *rq2) 1222 __acquires(rq1->lock) 1223 __acquires(rq2->lock) 1224 { 1225 BUG_ON(!irqs_disabled()); 1226 if (rq1 == rq2) { 1227 raw_spin_lock(&rq1->lock); 1228 __acquire(rq2->lock); /* Fake it out ;) */ 1229 } else { 1230 if (rq1 < rq2) { 1231 raw_spin_lock(&rq1->lock); 1232 raw_spin_lock_nested(&rq2->lock, SINGLE_DEPTH_NESTING); 1233 } else { 1234 raw_spin_lock(&rq2->lock); 1235 raw_spin_lock_nested(&rq1->lock, SINGLE_DEPTH_NESTING); 1236 } 1237 } 1238 } 1239 1240 /* 1241 * double_rq_unlock - safely unlock two runqueues 1242 * 1243 * Note this does not restore interrupts like task_rq_unlock, 1244 * you need to do so manually after calling. 1245 */ 1246 static inline void double_rq_unlock(struct rq *rq1, struct rq *rq2) 1247 __releases(rq1->lock) 1248 __releases(rq2->lock) 1249 { 1250 raw_spin_unlock(&rq1->lock); 1251 if (rq1 != rq2) 1252 raw_spin_unlock(&rq2->lock); 1253 else 1254 __release(rq2->lock); 1255 } 1256 1257 #else /* CONFIG_SMP */ 1258 1259 /* 1260 * double_rq_lock - safely lock two runqueues 1261 * 1262 * Note this does not disable interrupts like task_rq_lock, 1263 * you need to do so manually before calling. 1264 */ 1265 static inline void double_rq_lock(struct rq *rq1, struct rq *rq2) 1266 __acquires(rq1->lock) 1267 __acquires(rq2->lock) 1268 { 1269 BUG_ON(!irqs_disabled()); 1270 BUG_ON(rq1 != rq2); 1271 raw_spin_lock(&rq1->lock); 1272 __acquire(rq2->lock); /* Fake it out ;) */ 1273 } 1274 1275 /* 1276 * double_rq_unlock - safely unlock two runqueues 1277 * 1278 * Note this does not restore interrupts like task_rq_unlock, 1279 * you need to do so manually after calling. 1280 */ 1281 static inline void double_rq_unlock(struct rq *rq1, struct rq *rq2) 1282 __releases(rq1->lock) 1283 __releases(rq2->lock) 1284 { 1285 BUG_ON(rq1 != rq2); 1286 raw_spin_unlock(&rq1->lock); 1287 __release(rq2->lock); 1288 } 1289 1290 #endif 1291 1292 extern struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq); 1293 extern struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq); 1294 extern void print_cfs_stats(struct seq_file *m, int cpu); 1295 extern void print_rt_stats(struct seq_file *m, int cpu); 1296 1297 extern void init_cfs_rq(struct cfs_rq *cfs_rq); 1298 extern void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq); 1299 1300 extern void account_cfs_bandwidth_used(int enabled, int was_enabled); 1301 1302 #ifdef CONFIG_NO_HZ 1303 enum rq_nohz_flag_bits { 1304 NOHZ_TICK_STOPPED, 1305 NOHZ_BALANCE_KICK, 1306 }; 1307 1308 #define nohz_flags(cpu) (&cpu_rq(cpu)->nohz_flags) 1309 #endif 1310 1311 #ifdef CONFIG_IRQ_TIME_ACCOUNTING 1312 1313 DECLARE_PER_CPU(u64, cpu_hardirq_time); 1314 DECLARE_PER_CPU(u64, cpu_softirq_time); 1315 1316 #ifndef CONFIG_64BIT 1317 DECLARE_PER_CPU(seqcount_t, irq_time_seq); 1318 1319 static inline void irq_time_write_begin(void) 1320 { 1321 __this_cpu_inc(irq_time_seq.sequence); 1322 smp_wmb(); 1323 } 1324 1325 static inline void irq_time_write_end(void) 1326 { 1327 smp_wmb(); 1328 __this_cpu_inc(irq_time_seq.sequence); 1329 } 1330 1331 static inline u64 irq_time_read(int cpu) 1332 { 1333 u64 irq_time; 1334 unsigned seq; 1335 1336 do { 1337 seq = read_seqcount_begin(&per_cpu(irq_time_seq, cpu)); 1338 irq_time = per_cpu(cpu_softirq_time, cpu) + 1339 per_cpu(cpu_hardirq_time, cpu); 1340 } while (read_seqcount_retry(&per_cpu(irq_time_seq, cpu), seq)); 1341 1342 return irq_time; 1343 } 1344 #else /* CONFIG_64BIT */ 1345 static inline void irq_time_write_begin(void) 1346 { 1347 } 1348 1349 static inline void irq_time_write_end(void) 1350 { 1351 } 1352 1353 static inline u64 irq_time_read(int cpu) 1354 { 1355 return per_cpu(cpu_softirq_time, cpu) + per_cpu(cpu_hardirq_time, cpu); 1356 } 1357 #endif /* CONFIG_64BIT */ 1358 #endif /* CONFIG_IRQ_TIME_ACCOUNTING */ 1359