1 /* 2 * Real-Time Scheduling Class (mapped to the SCHED_FIFO and SCHED_RR 3 * policies) 4 */ 5 6 #include "sched.h" 7 8 #include <linux/slab.h> 9 10 int sched_rr_timeslice = RR_TIMESLICE; 11 12 static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun); 13 14 struct rt_bandwidth def_rt_bandwidth; 15 16 static enum hrtimer_restart sched_rt_period_timer(struct hrtimer *timer) 17 { 18 struct rt_bandwidth *rt_b = 19 container_of(timer, struct rt_bandwidth, rt_period_timer); 20 ktime_t now; 21 int overrun; 22 int idle = 0; 23 24 for (;;) { 25 now = hrtimer_cb_get_time(timer); 26 overrun = hrtimer_forward(timer, now, rt_b->rt_period); 27 28 if (!overrun) 29 break; 30 31 idle = do_sched_rt_period_timer(rt_b, overrun); 32 } 33 34 return idle ? HRTIMER_NORESTART : HRTIMER_RESTART; 35 } 36 37 void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime) 38 { 39 rt_b->rt_period = ns_to_ktime(period); 40 rt_b->rt_runtime = runtime; 41 42 raw_spin_lock_init(&rt_b->rt_runtime_lock); 43 44 hrtimer_init(&rt_b->rt_period_timer, 45 CLOCK_MONOTONIC, HRTIMER_MODE_REL); 46 rt_b->rt_period_timer.function = sched_rt_period_timer; 47 } 48 49 static void start_rt_bandwidth(struct rt_bandwidth *rt_b) 50 { 51 if (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF) 52 return; 53 54 if (hrtimer_active(&rt_b->rt_period_timer)) 55 return; 56 57 raw_spin_lock(&rt_b->rt_runtime_lock); 58 start_bandwidth_timer(&rt_b->rt_period_timer, rt_b->rt_period); 59 raw_spin_unlock(&rt_b->rt_runtime_lock); 60 } 61 62 void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq) 63 { 64 struct rt_prio_array *array; 65 int i; 66 67 array = &rt_rq->active; 68 for (i = 0; i < MAX_RT_PRIO; i++) { 69 INIT_LIST_HEAD(array->queue + i); 70 __clear_bit(i, array->bitmap); 71 } 72 /* delimiter for bitsearch: */ 73 __set_bit(MAX_RT_PRIO, array->bitmap); 74 75 #if defined CONFIG_SMP 76 rt_rq->highest_prio.curr = MAX_RT_PRIO; 77 rt_rq->highest_prio.next = MAX_RT_PRIO; 78 rt_rq->rt_nr_migratory = 0; 79 rt_rq->overloaded = 0; 80 plist_head_init(&rt_rq->pushable_tasks); 81 #endif 82 83 rt_rq->rt_time = 0; 84 rt_rq->rt_throttled = 0; 85 rt_rq->rt_runtime = 0; 86 raw_spin_lock_init(&rt_rq->rt_runtime_lock); 87 } 88 89 #ifdef CONFIG_RT_GROUP_SCHED 90 static void destroy_rt_bandwidth(struct rt_bandwidth *rt_b) 91 { 92 hrtimer_cancel(&rt_b->rt_period_timer); 93 } 94 95 #define rt_entity_is_task(rt_se) (!(rt_se)->my_q) 96 97 static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se) 98 { 99 #ifdef CONFIG_SCHED_DEBUG 100 WARN_ON_ONCE(!rt_entity_is_task(rt_se)); 101 #endif 102 return container_of(rt_se, struct task_struct, rt); 103 } 104 105 static inline struct rq *rq_of_rt_rq(struct rt_rq *rt_rq) 106 { 107 return rt_rq->rq; 108 } 109 110 static inline struct rt_rq *rt_rq_of_se(struct sched_rt_entity *rt_se) 111 { 112 return rt_se->rt_rq; 113 } 114 115 void free_rt_sched_group(struct task_group *tg) 116 { 117 int i; 118 119 if (tg->rt_se) 120 destroy_rt_bandwidth(&tg->rt_bandwidth); 121 122 for_each_possible_cpu(i) { 123 if (tg->rt_rq) 124 kfree(tg->rt_rq[i]); 125 if (tg->rt_se) 126 kfree(tg->rt_se[i]); 127 } 128 129 kfree(tg->rt_rq); 130 kfree(tg->rt_se); 131 } 132 133 void init_tg_rt_entry(struct task_group *tg, struct rt_rq *rt_rq, 134 struct sched_rt_entity *rt_se, int cpu, 135 struct sched_rt_entity *parent) 136 { 137 struct rq *rq = cpu_rq(cpu); 138 139 rt_rq->highest_prio.curr = MAX_RT_PRIO; 140 rt_rq->rt_nr_boosted = 0; 141 rt_rq->rq = rq; 142 rt_rq->tg = tg; 143 144 tg->rt_rq[cpu] = rt_rq; 145 tg->rt_se[cpu] = rt_se; 146 147 if (!rt_se) 148 return; 149 150 if (!parent) 151 rt_se->rt_rq = &rq->rt; 152 else 153 rt_se->rt_rq = parent->my_q; 154 155 rt_se->my_q = rt_rq; 156 rt_se->parent = parent; 157 INIT_LIST_HEAD(&rt_se->run_list); 158 } 159 160 int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent) 161 { 162 struct rt_rq *rt_rq; 163 struct sched_rt_entity *rt_se; 164 int i; 165 166 tg->rt_rq = kzalloc(sizeof(rt_rq) * nr_cpu_ids, GFP_KERNEL); 167 if (!tg->rt_rq) 168 goto err; 169 tg->rt_se = kzalloc(sizeof(rt_se) * nr_cpu_ids, GFP_KERNEL); 170 if (!tg->rt_se) 171 goto err; 172 173 init_rt_bandwidth(&tg->rt_bandwidth, 174 ktime_to_ns(def_rt_bandwidth.rt_period), 0); 175 176 for_each_possible_cpu(i) { 177 rt_rq = kzalloc_node(sizeof(struct rt_rq), 178 GFP_KERNEL, cpu_to_node(i)); 179 if (!rt_rq) 180 goto err; 181 182 rt_se = kzalloc_node(sizeof(struct sched_rt_entity), 183 GFP_KERNEL, cpu_to_node(i)); 184 if (!rt_se) 185 goto err_free_rq; 186 187 init_rt_rq(rt_rq, cpu_rq(i)); 188 rt_rq->rt_runtime = tg->rt_bandwidth.rt_runtime; 189 init_tg_rt_entry(tg, rt_rq, rt_se, i, parent->rt_se[i]); 190 } 191 192 return 1; 193 194 err_free_rq: 195 kfree(rt_rq); 196 err: 197 return 0; 198 } 199 200 #else /* CONFIG_RT_GROUP_SCHED */ 201 202 #define rt_entity_is_task(rt_se) (1) 203 204 static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se) 205 { 206 return container_of(rt_se, struct task_struct, rt); 207 } 208 209 static inline struct rq *rq_of_rt_rq(struct rt_rq *rt_rq) 210 { 211 return container_of(rt_rq, struct rq, rt); 212 } 213 214 static inline struct rt_rq *rt_rq_of_se(struct sched_rt_entity *rt_se) 215 { 216 struct task_struct *p = rt_task_of(rt_se); 217 struct rq *rq = task_rq(p); 218 219 return &rq->rt; 220 } 221 222 void free_rt_sched_group(struct task_group *tg) { } 223 224 int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent) 225 { 226 return 1; 227 } 228 #endif /* CONFIG_RT_GROUP_SCHED */ 229 230 #ifdef CONFIG_SMP 231 232 static int pull_rt_task(struct rq *this_rq); 233 234 static inline bool need_pull_rt_task(struct rq *rq, struct task_struct *prev) 235 { 236 /* Try to pull RT tasks here if we lower this rq's prio */ 237 return rq->rt.highest_prio.curr > prev->prio; 238 } 239 240 static inline int rt_overloaded(struct rq *rq) 241 { 242 return atomic_read(&rq->rd->rto_count); 243 } 244 245 static inline void rt_set_overload(struct rq *rq) 246 { 247 if (!rq->online) 248 return; 249 250 cpumask_set_cpu(rq->cpu, rq->rd->rto_mask); 251 /* 252 * Make sure the mask is visible before we set 253 * the overload count. That is checked to determine 254 * if we should look at the mask. It would be a shame 255 * if we looked at the mask, but the mask was not 256 * updated yet. 257 * 258 * Matched by the barrier in pull_rt_task(). 259 */ 260 smp_wmb(); 261 atomic_inc(&rq->rd->rto_count); 262 } 263 264 static inline void rt_clear_overload(struct rq *rq) 265 { 266 if (!rq->online) 267 return; 268 269 /* the order here really doesn't matter */ 270 atomic_dec(&rq->rd->rto_count); 271 cpumask_clear_cpu(rq->cpu, rq->rd->rto_mask); 272 } 273 274 static void update_rt_migration(struct rt_rq *rt_rq) 275 { 276 if (rt_rq->rt_nr_migratory && rt_rq->rt_nr_total > 1) { 277 if (!rt_rq->overloaded) { 278 rt_set_overload(rq_of_rt_rq(rt_rq)); 279 rt_rq->overloaded = 1; 280 } 281 } else if (rt_rq->overloaded) { 282 rt_clear_overload(rq_of_rt_rq(rt_rq)); 283 rt_rq->overloaded = 0; 284 } 285 } 286 287 static void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) 288 { 289 struct task_struct *p; 290 291 if (!rt_entity_is_task(rt_se)) 292 return; 293 294 p = rt_task_of(rt_se); 295 rt_rq = &rq_of_rt_rq(rt_rq)->rt; 296 297 rt_rq->rt_nr_total++; 298 if (p->nr_cpus_allowed > 1) 299 rt_rq->rt_nr_migratory++; 300 301 update_rt_migration(rt_rq); 302 } 303 304 static void dec_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) 305 { 306 struct task_struct *p; 307 308 if (!rt_entity_is_task(rt_se)) 309 return; 310 311 p = rt_task_of(rt_se); 312 rt_rq = &rq_of_rt_rq(rt_rq)->rt; 313 314 rt_rq->rt_nr_total--; 315 if (p->nr_cpus_allowed > 1) 316 rt_rq->rt_nr_migratory--; 317 318 update_rt_migration(rt_rq); 319 } 320 321 static inline int has_pushable_tasks(struct rq *rq) 322 { 323 return !plist_head_empty(&rq->rt.pushable_tasks); 324 } 325 326 static inline void set_post_schedule(struct rq *rq) 327 { 328 /* 329 * We detect this state here so that we can avoid taking the RQ 330 * lock again later if there is no need to push 331 */ 332 rq->post_schedule = has_pushable_tasks(rq); 333 } 334 335 static void enqueue_pushable_task(struct rq *rq, struct task_struct *p) 336 { 337 plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks); 338 plist_node_init(&p->pushable_tasks, p->prio); 339 plist_add(&p->pushable_tasks, &rq->rt.pushable_tasks); 340 341 /* Update the highest prio pushable task */ 342 if (p->prio < rq->rt.highest_prio.next) 343 rq->rt.highest_prio.next = p->prio; 344 } 345 346 static void dequeue_pushable_task(struct rq *rq, struct task_struct *p) 347 { 348 plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks); 349 350 /* Update the new highest prio pushable task */ 351 if (has_pushable_tasks(rq)) { 352 p = plist_first_entry(&rq->rt.pushable_tasks, 353 struct task_struct, pushable_tasks); 354 rq->rt.highest_prio.next = p->prio; 355 } else 356 rq->rt.highest_prio.next = MAX_RT_PRIO; 357 } 358 359 #else 360 361 static inline void enqueue_pushable_task(struct rq *rq, struct task_struct *p) 362 { 363 } 364 365 static inline void dequeue_pushable_task(struct rq *rq, struct task_struct *p) 366 { 367 } 368 369 static inline 370 void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) 371 { 372 } 373 374 static inline 375 void dec_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) 376 { 377 } 378 379 static inline bool need_pull_rt_task(struct rq *rq, struct task_struct *prev) 380 { 381 return false; 382 } 383 384 static inline int pull_rt_task(struct rq *this_rq) 385 { 386 return 0; 387 } 388 389 static inline void set_post_schedule(struct rq *rq) 390 { 391 } 392 #endif /* CONFIG_SMP */ 393 394 static inline int on_rt_rq(struct sched_rt_entity *rt_se) 395 { 396 return !list_empty(&rt_se->run_list); 397 } 398 399 #ifdef CONFIG_RT_GROUP_SCHED 400 401 static inline u64 sched_rt_runtime(struct rt_rq *rt_rq) 402 { 403 if (!rt_rq->tg) 404 return RUNTIME_INF; 405 406 return rt_rq->rt_runtime; 407 } 408 409 static inline u64 sched_rt_period(struct rt_rq *rt_rq) 410 { 411 return ktime_to_ns(rt_rq->tg->rt_bandwidth.rt_period); 412 } 413 414 typedef struct task_group *rt_rq_iter_t; 415 416 static inline struct task_group *next_task_group(struct task_group *tg) 417 { 418 do { 419 tg = list_entry_rcu(tg->list.next, 420 typeof(struct task_group), list); 421 } while (&tg->list != &task_groups && task_group_is_autogroup(tg)); 422 423 if (&tg->list == &task_groups) 424 tg = NULL; 425 426 return tg; 427 } 428 429 #define for_each_rt_rq(rt_rq, iter, rq) \ 430 for (iter = container_of(&task_groups, typeof(*iter), list); \ 431 (iter = next_task_group(iter)) && \ 432 (rt_rq = iter->rt_rq[cpu_of(rq)]);) 433 434 #define for_each_sched_rt_entity(rt_se) \ 435 for (; rt_se; rt_se = rt_se->parent) 436 437 static inline struct rt_rq *group_rt_rq(struct sched_rt_entity *rt_se) 438 { 439 return rt_se->my_q; 440 } 441 442 static void enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head); 443 static void dequeue_rt_entity(struct sched_rt_entity *rt_se); 444 445 static void sched_rt_rq_enqueue(struct rt_rq *rt_rq) 446 { 447 struct task_struct *curr = rq_of_rt_rq(rt_rq)->curr; 448 struct sched_rt_entity *rt_se; 449 450 int cpu = cpu_of(rq_of_rt_rq(rt_rq)); 451 452 rt_se = rt_rq->tg->rt_se[cpu]; 453 454 if (rt_rq->rt_nr_running) { 455 if (rt_se && !on_rt_rq(rt_se)) 456 enqueue_rt_entity(rt_se, false); 457 if (rt_rq->highest_prio.curr < curr->prio) 458 resched_task(curr); 459 } 460 } 461 462 static void sched_rt_rq_dequeue(struct rt_rq *rt_rq) 463 { 464 struct sched_rt_entity *rt_se; 465 int cpu = cpu_of(rq_of_rt_rq(rt_rq)); 466 467 rt_se = rt_rq->tg->rt_se[cpu]; 468 469 if (rt_se && on_rt_rq(rt_se)) 470 dequeue_rt_entity(rt_se); 471 } 472 473 static int rt_se_boosted(struct sched_rt_entity *rt_se) 474 { 475 struct rt_rq *rt_rq = group_rt_rq(rt_se); 476 struct task_struct *p; 477 478 if (rt_rq) 479 return !!rt_rq->rt_nr_boosted; 480 481 p = rt_task_of(rt_se); 482 return p->prio != p->normal_prio; 483 } 484 485 #ifdef CONFIG_SMP 486 static inline const struct cpumask *sched_rt_period_mask(void) 487 { 488 return this_rq()->rd->span; 489 } 490 #else 491 static inline const struct cpumask *sched_rt_period_mask(void) 492 { 493 return cpu_online_mask; 494 } 495 #endif 496 497 static inline 498 struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu) 499 { 500 return container_of(rt_b, struct task_group, rt_bandwidth)->rt_rq[cpu]; 501 } 502 503 static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq) 504 { 505 return &rt_rq->tg->rt_bandwidth; 506 } 507 508 #else /* !CONFIG_RT_GROUP_SCHED */ 509 510 static inline u64 sched_rt_runtime(struct rt_rq *rt_rq) 511 { 512 return rt_rq->rt_runtime; 513 } 514 515 static inline u64 sched_rt_period(struct rt_rq *rt_rq) 516 { 517 return ktime_to_ns(def_rt_bandwidth.rt_period); 518 } 519 520 typedef struct rt_rq *rt_rq_iter_t; 521 522 #define for_each_rt_rq(rt_rq, iter, rq) \ 523 for ((void) iter, rt_rq = &rq->rt; rt_rq; rt_rq = NULL) 524 525 #define for_each_sched_rt_entity(rt_se) \ 526 for (; rt_se; rt_se = NULL) 527 528 static inline struct rt_rq *group_rt_rq(struct sched_rt_entity *rt_se) 529 { 530 return NULL; 531 } 532 533 static inline void sched_rt_rq_enqueue(struct rt_rq *rt_rq) 534 { 535 if (rt_rq->rt_nr_running) 536 resched_task(rq_of_rt_rq(rt_rq)->curr); 537 } 538 539 static inline void sched_rt_rq_dequeue(struct rt_rq *rt_rq) 540 { 541 } 542 543 static inline const struct cpumask *sched_rt_period_mask(void) 544 { 545 return cpu_online_mask; 546 } 547 548 static inline 549 struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu) 550 { 551 return &cpu_rq(cpu)->rt; 552 } 553 554 static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq) 555 { 556 return &def_rt_bandwidth; 557 } 558 559 #endif /* CONFIG_RT_GROUP_SCHED */ 560 561 bool sched_rt_bandwidth_account(struct rt_rq *rt_rq) 562 { 563 struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq); 564 565 return (hrtimer_active(&rt_b->rt_period_timer) || 566 rt_rq->rt_time < rt_b->rt_runtime); 567 } 568 569 #ifdef CONFIG_SMP 570 /* 571 * We ran out of runtime, see if we can borrow some from our neighbours. 572 */ 573 static int do_balance_runtime(struct rt_rq *rt_rq) 574 { 575 struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq); 576 struct root_domain *rd = rq_of_rt_rq(rt_rq)->rd; 577 int i, weight, more = 0; 578 u64 rt_period; 579 580 weight = cpumask_weight(rd->span); 581 582 raw_spin_lock(&rt_b->rt_runtime_lock); 583 rt_period = ktime_to_ns(rt_b->rt_period); 584 for_each_cpu(i, rd->span) { 585 struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i); 586 s64 diff; 587 588 if (iter == rt_rq) 589 continue; 590 591 raw_spin_lock(&iter->rt_runtime_lock); 592 /* 593 * Either all rqs have inf runtime and there's nothing to steal 594 * or __disable_runtime() below sets a specific rq to inf to 595 * indicate its been disabled and disalow stealing. 596 */ 597 if (iter->rt_runtime == RUNTIME_INF) 598 goto next; 599 600 /* 601 * From runqueues with spare time, take 1/n part of their 602 * spare time, but no more than our period. 603 */ 604 diff = iter->rt_runtime - iter->rt_time; 605 if (diff > 0) { 606 diff = div_u64((u64)diff, weight); 607 if (rt_rq->rt_runtime + diff > rt_period) 608 diff = rt_period - rt_rq->rt_runtime; 609 iter->rt_runtime -= diff; 610 rt_rq->rt_runtime += diff; 611 more = 1; 612 if (rt_rq->rt_runtime == rt_period) { 613 raw_spin_unlock(&iter->rt_runtime_lock); 614 break; 615 } 616 } 617 next: 618 raw_spin_unlock(&iter->rt_runtime_lock); 619 } 620 raw_spin_unlock(&rt_b->rt_runtime_lock); 621 622 return more; 623 } 624 625 /* 626 * Ensure this RQ takes back all the runtime it lend to its neighbours. 627 */ 628 static void __disable_runtime(struct rq *rq) 629 { 630 struct root_domain *rd = rq->rd; 631 rt_rq_iter_t iter; 632 struct rt_rq *rt_rq; 633 634 if (unlikely(!scheduler_running)) 635 return; 636 637 for_each_rt_rq(rt_rq, iter, rq) { 638 struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq); 639 s64 want; 640 int i; 641 642 raw_spin_lock(&rt_b->rt_runtime_lock); 643 raw_spin_lock(&rt_rq->rt_runtime_lock); 644 /* 645 * Either we're all inf and nobody needs to borrow, or we're 646 * already disabled and thus have nothing to do, or we have 647 * exactly the right amount of runtime to take out. 648 */ 649 if (rt_rq->rt_runtime == RUNTIME_INF || 650 rt_rq->rt_runtime == rt_b->rt_runtime) 651 goto balanced; 652 raw_spin_unlock(&rt_rq->rt_runtime_lock); 653 654 /* 655 * Calculate the difference between what we started out with 656 * and what we current have, that's the amount of runtime 657 * we lend and now have to reclaim. 658 */ 659 want = rt_b->rt_runtime - rt_rq->rt_runtime; 660 661 /* 662 * Greedy reclaim, take back as much as we can. 663 */ 664 for_each_cpu(i, rd->span) { 665 struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i); 666 s64 diff; 667 668 /* 669 * Can't reclaim from ourselves or disabled runqueues. 670 */ 671 if (iter == rt_rq || iter->rt_runtime == RUNTIME_INF) 672 continue; 673 674 raw_spin_lock(&iter->rt_runtime_lock); 675 if (want > 0) { 676 diff = min_t(s64, iter->rt_runtime, want); 677 iter->rt_runtime -= diff; 678 want -= diff; 679 } else { 680 iter->rt_runtime -= want; 681 want -= want; 682 } 683 raw_spin_unlock(&iter->rt_runtime_lock); 684 685 if (!want) 686 break; 687 } 688 689 raw_spin_lock(&rt_rq->rt_runtime_lock); 690 /* 691 * We cannot be left wanting - that would mean some runtime 692 * leaked out of the system. 693 */ 694 BUG_ON(want); 695 balanced: 696 /* 697 * Disable all the borrow logic by pretending we have inf 698 * runtime - in which case borrowing doesn't make sense. 699 */ 700 rt_rq->rt_runtime = RUNTIME_INF; 701 rt_rq->rt_throttled = 0; 702 raw_spin_unlock(&rt_rq->rt_runtime_lock); 703 raw_spin_unlock(&rt_b->rt_runtime_lock); 704 } 705 } 706 707 static void __enable_runtime(struct rq *rq) 708 { 709 rt_rq_iter_t iter; 710 struct rt_rq *rt_rq; 711 712 if (unlikely(!scheduler_running)) 713 return; 714 715 /* 716 * Reset each runqueue's bandwidth settings 717 */ 718 for_each_rt_rq(rt_rq, iter, rq) { 719 struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq); 720 721 raw_spin_lock(&rt_b->rt_runtime_lock); 722 raw_spin_lock(&rt_rq->rt_runtime_lock); 723 rt_rq->rt_runtime = rt_b->rt_runtime; 724 rt_rq->rt_time = 0; 725 rt_rq->rt_throttled = 0; 726 raw_spin_unlock(&rt_rq->rt_runtime_lock); 727 raw_spin_unlock(&rt_b->rt_runtime_lock); 728 } 729 } 730 731 static int balance_runtime(struct rt_rq *rt_rq) 732 { 733 int more = 0; 734 735 if (!sched_feat(RT_RUNTIME_SHARE)) 736 return more; 737 738 if (rt_rq->rt_time > rt_rq->rt_runtime) { 739 raw_spin_unlock(&rt_rq->rt_runtime_lock); 740 more = do_balance_runtime(rt_rq); 741 raw_spin_lock(&rt_rq->rt_runtime_lock); 742 } 743 744 return more; 745 } 746 #else /* !CONFIG_SMP */ 747 static inline int balance_runtime(struct rt_rq *rt_rq) 748 { 749 return 0; 750 } 751 #endif /* CONFIG_SMP */ 752 753 static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun) 754 { 755 int i, idle = 1, throttled = 0; 756 const struct cpumask *span; 757 758 span = sched_rt_period_mask(); 759 #ifdef CONFIG_RT_GROUP_SCHED 760 /* 761 * FIXME: isolated CPUs should really leave the root task group, 762 * whether they are isolcpus or were isolated via cpusets, lest 763 * the timer run on a CPU which does not service all runqueues, 764 * potentially leaving other CPUs indefinitely throttled. If 765 * isolation is really required, the user will turn the throttle 766 * off to kill the perturbations it causes anyway. Meanwhile, 767 * this maintains functionality for boot and/or troubleshooting. 768 */ 769 if (rt_b == &root_task_group.rt_bandwidth) 770 span = cpu_online_mask; 771 #endif 772 for_each_cpu(i, span) { 773 int enqueue = 0; 774 struct rt_rq *rt_rq = sched_rt_period_rt_rq(rt_b, i); 775 struct rq *rq = rq_of_rt_rq(rt_rq); 776 777 raw_spin_lock(&rq->lock); 778 if (rt_rq->rt_time) { 779 u64 runtime; 780 781 raw_spin_lock(&rt_rq->rt_runtime_lock); 782 if (rt_rq->rt_throttled) 783 balance_runtime(rt_rq); 784 runtime = rt_rq->rt_runtime; 785 rt_rq->rt_time -= min(rt_rq->rt_time, overrun*runtime); 786 if (rt_rq->rt_throttled && rt_rq->rt_time < runtime) { 787 rt_rq->rt_throttled = 0; 788 enqueue = 1; 789 790 /* 791 * Force a clock update if the CPU was idle, 792 * lest wakeup -> unthrottle time accumulate. 793 */ 794 if (rt_rq->rt_nr_running && rq->curr == rq->idle) 795 rq->skip_clock_update = -1; 796 } 797 if (rt_rq->rt_time || rt_rq->rt_nr_running) 798 idle = 0; 799 raw_spin_unlock(&rt_rq->rt_runtime_lock); 800 } else if (rt_rq->rt_nr_running) { 801 idle = 0; 802 if (!rt_rq_throttled(rt_rq)) 803 enqueue = 1; 804 } 805 if (rt_rq->rt_throttled) 806 throttled = 1; 807 808 if (enqueue) 809 sched_rt_rq_enqueue(rt_rq); 810 raw_spin_unlock(&rq->lock); 811 } 812 813 if (!throttled && (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF)) 814 return 1; 815 816 return idle; 817 } 818 819 static inline int rt_se_prio(struct sched_rt_entity *rt_se) 820 { 821 #ifdef CONFIG_RT_GROUP_SCHED 822 struct rt_rq *rt_rq = group_rt_rq(rt_se); 823 824 if (rt_rq) 825 return rt_rq->highest_prio.curr; 826 #endif 827 828 return rt_task_of(rt_se)->prio; 829 } 830 831 static int sched_rt_runtime_exceeded(struct rt_rq *rt_rq) 832 { 833 u64 runtime = sched_rt_runtime(rt_rq); 834 835 if (rt_rq->rt_throttled) 836 return rt_rq_throttled(rt_rq); 837 838 if (runtime >= sched_rt_period(rt_rq)) 839 return 0; 840 841 balance_runtime(rt_rq); 842 runtime = sched_rt_runtime(rt_rq); 843 if (runtime == RUNTIME_INF) 844 return 0; 845 846 if (rt_rq->rt_time > runtime) { 847 struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq); 848 849 /* 850 * Don't actually throttle groups that have no runtime assigned 851 * but accrue some time due to boosting. 852 */ 853 if (likely(rt_b->rt_runtime)) { 854 static bool once = false; 855 856 rt_rq->rt_throttled = 1; 857 858 if (!once) { 859 once = true; 860 printk_sched("sched: RT throttling activated\n"); 861 } 862 } else { 863 /* 864 * In case we did anyway, make it go away, 865 * replenishment is a joke, since it will replenish us 866 * with exactly 0 ns. 867 */ 868 rt_rq->rt_time = 0; 869 } 870 871 if (rt_rq_throttled(rt_rq)) { 872 sched_rt_rq_dequeue(rt_rq); 873 return 1; 874 } 875 } 876 877 return 0; 878 } 879 880 /* 881 * Update the current task's runtime statistics. Skip current tasks that 882 * are not in our scheduling class. 883 */ 884 static void update_curr_rt(struct rq *rq) 885 { 886 struct task_struct *curr = rq->curr; 887 struct sched_rt_entity *rt_se = &curr->rt; 888 struct rt_rq *rt_rq = rt_rq_of_se(rt_se); 889 u64 delta_exec; 890 891 if (curr->sched_class != &rt_sched_class) 892 return; 893 894 delta_exec = rq_clock_task(rq) - curr->se.exec_start; 895 if (unlikely((s64)delta_exec <= 0)) 896 return; 897 898 schedstat_set(curr->se.statistics.exec_max, 899 max(curr->se.statistics.exec_max, delta_exec)); 900 901 curr->se.sum_exec_runtime += delta_exec; 902 account_group_exec_runtime(curr, delta_exec); 903 904 curr->se.exec_start = rq_clock_task(rq); 905 cpuacct_charge(curr, delta_exec); 906 907 sched_rt_avg_update(rq, delta_exec); 908 909 if (!rt_bandwidth_enabled()) 910 return; 911 912 for_each_sched_rt_entity(rt_se) { 913 rt_rq = rt_rq_of_se(rt_se); 914 915 if (sched_rt_runtime(rt_rq) != RUNTIME_INF) { 916 raw_spin_lock(&rt_rq->rt_runtime_lock); 917 rt_rq->rt_time += delta_exec; 918 if (sched_rt_runtime_exceeded(rt_rq)) 919 resched_task(curr); 920 raw_spin_unlock(&rt_rq->rt_runtime_lock); 921 } 922 } 923 } 924 925 #if defined CONFIG_SMP 926 927 static void 928 inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio) 929 { 930 struct rq *rq = rq_of_rt_rq(rt_rq); 931 932 #ifdef CONFIG_RT_GROUP_SCHED 933 /* 934 * Change rq's cpupri only if rt_rq is the top queue. 935 */ 936 if (&rq->rt != rt_rq) 937 return; 938 #endif 939 if (rq->online && prio < prev_prio) 940 cpupri_set(&rq->rd->cpupri, rq->cpu, prio); 941 } 942 943 static void 944 dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio) 945 { 946 struct rq *rq = rq_of_rt_rq(rt_rq); 947 948 #ifdef CONFIG_RT_GROUP_SCHED 949 /* 950 * Change rq's cpupri only if rt_rq is the top queue. 951 */ 952 if (&rq->rt != rt_rq) 953 return; 954 #endif 955 if (rq->online && rt_rq->highest_prio.curr != prev_prio) 956 cpupri_set(&rq->rd->cpupri, rq->cpu, rt_rq->highest_prio.curr); 957 } 958 959 #else /* CONFIG_SMP */ 960 961 static inline 962 void inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio) {} 963 static inline 964 void dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio) {} 965 966 #endif /* CONFIG_SMP */ 967 968 #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED 969 static void 970 inc_rt_prio(struct rt_rq *rt_rq, int prio) 971 { 972 int prev_prio = rt_rq->highest_prio.curr; 973 974 if (prio < prev_prio) 975 rt_rq->highest_prio.curr = prio; 976 977 inc_rt_prio_smp(rt_rq, prio, prev_prio); 978 } 979 980 static void 981 dec_rt_prio(struct rt_rq *rt_rq, int prio) 982 { 983 int prev_prio = rt_rq->highest_prio.curr; 984 985 if (rt_rq->rt_nr_running) { 986 987 WARN_ON(prio < prev_prio); 988 989 /* 990 * This may have been our highest task, and therefore 991 * we may have some recomputation to do 992 */ 993 if (prio == prev_prio) { 994 struct rt_prio_array *array = &rt_rq->active; 995 996 rt_rq->highest_prio.curr = 997 sched_find_first_bit(array->bitmap); 998 } 999 1000 } else 1001 rt_rq->highest_prio.curr = MAX_RT_PRIO; 1002 1003 dec_rt_prio_smp(rt_rq, prio, prev_prio); 1004 } 1005 1006 #else 1007 1008 static inline void inc_rt_prio(struct rt_rq *rt_rq, int prio) {} 1009 static inline void dec_rt_prio(struct rt_rq *rt_rq, int prio) {} 1010 1011 #endif /* CONFIG_SMP || CONFIG_RT_GROUP_SCHED */ 1012 1013 #ifdef CONFIG_RT_GROUP_SCHED 1014 1015 static void 1016 inc_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) 1017 { 1018 if (rt_se_boosted(rt_se)) 1019 rt_rq->rt_nr_boosted++; 1020 1021 if (rt_rq->tg) 1022 start_rt_bandwidth(&rt_rq->tg->rt_bandwidth); 1023 } 1024 1025 static void 1026 dec_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) 1027 { 1028 if (rt_se_boosted(rt_se)) 1029 rt_rq->rt_nr_boosted--; 1030 1031 WARN_ON(!rt_rq->rt_nr_running && rt_rq->rt_nr_boosted); 1032 } 1033 1034 #else /* CONFIG_RT_GROUP_SCHED */ 1035 1036 static void 1037 inc_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) 1038 { 1039 start_rt_bandwidth(&def_rt_bandwidth); 1040 } 1041 1042 static inline 1043 void dec_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) {} 1044 1045 #endif /* CONFIG_RT_GROUP_SCHED */ 1046 1047 static inline 1048 void inc_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) 1049 { 1050 int prio = rt_se_prio(rt_se); 1051 1052 WARN_ON(!rt_prio(prio)); 1053 rt_rq->rt_nr_running++; 1054 1055 inc_rt_prio(rt_rq, prio); 1056 inc_rt_migration(rt_se, rt_rq); 1057 inc_rt_group(rt_se, rt_rq); 1058 } 1059 1060 static inline 1061 void dec_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) 1062 { 1063 WARN_ON(!rt_prio(rt_se_prio(rt_se))); 1064 WARN_ON(!rt_rq->rt_nr_running); 1065 rt_rq->rt_nr_running--; 1066 1067 dec_rt_prio(rt_rq, rt_se_prio(rt_se)); 1068 dec_rt_migration(rt_se, rt_rq); 1069 dec_rt_group(rt_se, rt_rq); 1070 } 1071 1072 static void __enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head) 1073 { 1074 struct rt_rq *rt_rq = rt_rq_of_se(rt_se); 1075 struct rt_prio_array *array = &rt_rq->active; 1076 struct rt_rq *group_rq = group_rt_rq(rt_se); 1077 struct list_head *queue = array->queue + rt_se_prio(rt_se); 1078 1079 /* 1080 * Don't enqueue the group if its throttled, or when empty. 1081 * The latter is a consequence of the former when a child group 1082 * get throttled and the current group doesn't have any other 1083 * active members. 1084 */ 1085 if (group_rq && (rt_rq_throttled(group_rq) || !group_rq->rt_nr_running)) 1086 return; 1087 1088 if (head) 1089 list_add(&rt_se->run_list, queue); 1090 else 1091 list_add_tail(&rt_se->run_list, queue); 1092 __set_bit(rt_se_prio(rt_se), array->bitmap); 1093 1094 inc_rt_tasks(rt_se, rt_rq); 1095 } 1096 1097 static void __dequeue_rt_entity(struct sched_rt_entity *rt_se) 1098 { 1099 struct rt_rq *rt_rq = rt_rq_of_se(rt_se); 1100 struct rt_prio_array *array = &rt_rq->active; 1101 1102 list_del_init(&rt_se->run_list); 1103 if (list_empty(array->queue + rt_se_prio(rt_se))) 1104 __clear_bit(rt_se_prio(rt_se), array->bitmap); 1105 1106 dec_rt_tasks(rt_se, rt_rq); 1107 } 1108 1109 /* 1110 * Because the prio of an upper entry depends on the lower 1111 * entries, we must remove entries top - down. 1112 */ 1113 static void dequeue_rt_stack(struct sched_rt_entity *rt_se) 1114 { 1115 struct sched_rt_entity *back = NULL; 1116 1117 for_each_sched_rt_entity(rt_se) { 1118 rt_se->back = back; 1119 back = rt_se; 1120 } 1121 1122 for (rt_se = back; rt_se; rt_se = rt_se->back) { 1123 if (on_rt_rq(rt_se)) 1124 __dequeue_rt_entity(rt_se); 1125 } 1126 } 1127 1128 static void enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head) 1129 { 1130 dequeue_rt_stack(rt_se); 1131 for_each_sched_rt_entity(rt_se) 1132 __enqueue_rt_entity(rt_se, head); 1133 } 1134 1135 static void dequeue_rt_entity(struct sched_rt_entity *rt_se) 1136 { 1137 dequeue_rt_stack(rt_se); 1138 1139 for_each_sched_rt_entity(rt_se) { 1140 struct rt_rq *rt_rq = group_rt_rq(rt_se); 1141 1142 if (rt_rq && rt_rq->rt_nr_running) 1143 __enqueue_rt_entity(rt_se, false); 1144 } 1145 } 1146 1147 /* 1148 * Adding/removing a task to/from a priority array: 1149 */ 1150 static void 1151 enqueue_task_rt(struct rq *rq, struct task_struct *p, int flags) 1152 { 1153 struct sched_rt_entity *rt_se = &p->rt; 1154 1155 if (flags & ENQUEUE_WAKEUP) 1156 rt_se->timeout = 0; 1157 1158 enqueue_rt_entity(rt_se, flags & ENQUEUE_HEAD); 1159 1160 if (!task_current(rq, p) && p->nr_cpus_allowed > 1) 1161 enqueue_pushable_task(rq, p); 1162 1163 inc_nr_running(rq); 1164 } 1165 1166 static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int flags) 1167 { 1168 struct sched_rt_entity *rt_se = &p->rt; 1169 1170 update_curr_rt(rq); 1171 dequeue_rt_entity(rt_se); 1172 1173 dequeue_pushable_task(rq, p); 1174 1175 dec_nr_running(rq); 1176 } 1177 1178 /* 1179 * Put task to the head or the end of the run list without the overhead of 1180 * dequeue followed by enqueue. 1181 */ 1182 static void 1183 requeue_rt_entity(struct rt_rq *rt_rq, struct sched_rt_entity *rt_se, int head) 1184 { 1185 if (on_rt_rq(rt_se)) { 1186 struct rt_prio_array *array = &rt_rq->active; 1187 struct list_head *queue = array->queue + rt_se_prio(rt_se); 1188 1189 if (head) 1190 list_move(&rt_se->run_list, queue); 1191 else 1192 list_move_tail(&rt_se->run_list, queue); 1193 } 1194 } 1195 1196 static void requeue_task_rt(struct rq *rq, struct task_struct *p, int head) 1197 { 1198 struct sched_rt_entity *rt_se = &p->rt; 1199 struct rt_rq *rt_rq; 1200 1201 for_each_sched_rt_entity(rt_se) { 1202 rt_rq = rt_rq_of_se(rt_se); 1203 requeue_rt_entity(rt_rq, rt_se, head); 1204 } 1205 } 1206 1207 static void yield_task_rt(struct rq *rq) 1208 { 1209 requeue_task_rt(rq, rq->curr, 0); 1210 } 1211 1212 #ifdef CONFIG_SMP 1213 static int find_lowest_rq(struct task_struct *task); 1214 1215 static int 1216 select_task_rq_rt(struct task_struct *p, int cpu, int sd_flag, int flags) 1217 { 1218 struct task_struct *curr; 1219 struct rq *rq; 1220 1221 if (p->nr_cpus_allowed == 1) 1222 goto out; 1223 1224 /* For anything but wake ups, just return the task_cpu */ 1225 if (sd_flag != SD_BALANCE_WAKE && sd_flag != SD_BALANCE_FORK) 1226 goto out; 1227 1228 rq = cpu_rq(cpu); 1229 1230 rcu_read_lock(); 1231 curr = ACCESS_ONCE(rq->curr); /* unlocked access */ 1232 1233 /* 1234 * If the current task on @p's runqueue is an RT task, then 1235 * try to see if we can wake this RT task up on another 1236 * runqueue. Otherwise simply start this RT task 1237 * on its current runqueue. 1238 * 1239 * We want to avoid overloading runqueues. If the woken 1240 * task is a higher priority, then it will stay on this CPU 1241 * and the lower prio task should be moved to another CPU. 1242 * Even though this will probably make the lower prio task 1243 * lose its cache, we do not want to bounce a higher task 1244 * around just because it gave up its CPU, perhaps for a 1245 * lock? 1246 * 1247 * For equal prio tasks, we just let the scheduler sort it out. 1248 * 1249 * Otherwise, just let it ride on the affined RQ and the 1250 * post-schedule router will push the preempted task away 1251 * 1252 * This test is optimistic, if we get it wrong the load-balancer 1253 * will have to sort it out. 1254 */ 1255 if (curr && unlikely(rt_task(curr)) && 1256 (curr->nr_cpus_allowed < 2 || 1257 curr->prio <= p->prio)) { 1258 int target = find_lowest_rq(p); 1259 1260 if (target != -1) 1261 cpu = target; 1262 } 1263 rcu_read_unlock(); 1264 1265 out: 1266 return cpu; 1267 } 1268 1269 static void check_preempt_equal_prio(struct rq *rq, struct task_struct *p) 1270 { 1271 if (rq->curr->nr_cpus_allowed == 1) 1272 return; 1273 1274 if (p->nr_cpus_allowed != 1 1275 && cpupri_find(&rq->rd->cpupri, p, NULL)) 1276 return; 1277 1278 if (!cpupri_find(&rq->rd->cpupri, rq->curr, NULL)) 1279 return; 1280 1281 /* 1282 * There appears to be other cpus that can accept 1283 * current and none to run 'p', so lets reschedule 1284 * to try and push current away: 1285 */ 1286 requeue_task_rt(rq, p, 1); 1287 resched_task(rq->curr); 1288 } 1289 1290 #endif /* CONFIG_SMP */ 1291 1292 /* 1293 * Preempt the current task with a newly woken task if needed: 1294 */ 1295 static void check_preempt_curr_rt(struct rq *rq, struct task_struct *p, int flags) 1296 { 1297 if (p->prio < rq->curr->prio) { 1298 resched_task(rq->curr); 1299 return; 1300 } 1301 1302 #ifdef CONFIG_SMP 1303 /* 1304 * If: 1305 * 1306 * - the newly woken task is of equal priority to the current task 1307 * - the newly woken task is non-migratable while current is migratable 1308 * - current will be preempted on the next reschedule 1309 * 1310 * we should check to see if current can readily move to a different 1311 * cpu. If so, we will reschedule to allow the push logic to try 1312 * to move current somewhere else, making room for our non-migratable 1313 * task. 1314 */ 1315 if (p->prio == rq->curr->prio && !test_tsk_need_resched(rq->curr)) 1316 check_preempt_equal_prio(rq, p); 1317 #endif 1318 } 1319 1320 static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq, 1321 struct rt_rq *rt_rq) 1322 { 1323 struct rt_prio_array *array = &rt_rq->active; 1324 struct sched_rt_entity *next = NULL; 1325 struct list_head *queue; 1326 int idx; 1327 1328 idx = sched_find_first_bit(array->bitmap); 1329 BUG_ON(idx >= MAX_RT_PRIO); 1330 1331 queue = array->queue + idx; 1332 next = list_entry(queue->next, struct sched_rt_entity, run_list); 1333 1334 return next; 1335 } 1336 1337 static struct task_struct *_pick_next_task_rt(struct rq *rq) 1338 { 1339 struct sched_rt_entity *rt_se; 1340 struct task_struct *p; 1341 struct rt_rq *rt_rq = &rq->rt; 1342 1343 do { 1344 rt_se = pick_next_rt_entity(rq, rt_rq); 1345 BUG_ON(!rt_se); 1346 rt_rq = group_rt_rq(rt_se); 1347 } while (rt_rq); 1348 1349 p = rt_task_of(rt_se); 1350 p->se.exec_start = rq_clock_task(rq); 1351 1352 return p; 1353 } 1354 1355 static struct task_struct * 1356 pick_next_task_rt(struct rq *rq, struct task_struct *prev) 1357 { 1358 struct task_struct *p; 1359 struct rt_rq *rt_rq = &rq->rt; 1360 1361 if (need_pull_rt_task(rq, prev)) { 1362 pull_rt_task(rq); 1363 /* 1364 * pull_rt_task() can drop (and re-acquire) rq->lock; this 1365 * means a dl or stop task can slip in, in which case we need 1366 * to re-start task selection. 1367 */ 1368 if (unlikely((rq->stop && rq->stop->on_rq) || 1369 rq->dl.dl_nr_running)) 1370 return RETRY_TASK; 1371 } 1372 1373 /* 1374 * We may dequeue prev's rt_rq in put_prev_task(). 1375 * So, we update time before rt_nr_running check. 1376 */ 1377 if (prev->sched_class == &rt_sched_class) 1378 update_curr_rt(rq); 1379 1380 if (!rt_rq->rt_nr_running) 1381 return NULL; 1382 1383 if (rt_rq_throttled(rt_rq)) 1384 return NULL; 1385 1386 put_prev_task(rq, prev); 1387 1388 p = _pick_next_task_rt(rq); 1389 1390 /* The running task is never eligible for pushing */ 1391 if (p) 1392 dequeue_pushable_task(rq, p); 1393 1394 set_post_schedule(rq); 1395 1396 return p; 1397 } 1398 1399 static void put_prev_task_rt(struct rq *rq, struct task_struct *p) 1400 { 1401 update_curr_rt(rq); 1402 1403 /* 1404 * The previous task needs to be made eligible for pushing 1405 * if it is still active 1406 */ 1407 if (on_rt_rq(&p->rt) && p->nr_cpus_allowed > 1) 1408 enqueue_pushable_task(rq, p); 1409 } 1410 1411 #ifdef CONFIG_SMP 1412 1413 /* Only try algorithms three times */ 1414 #define RT_MAX_TRIES 3 1415 1416 static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu) 1417 { 1418 if (!task_running(rq, p) && 1419 cpumask_test_cpu(cpu, tsk_cpus_allowed(p))) 1420 return 1; 1421 return 0; 1422 } 1423 1424 /* 1425 * Return the highest pushable rq's task, which is suitable to be executed 1426 * on the cpu, NULL otherwise 1427 */ 1428 static struct task_struct *pick_highest_pushable_task(struct rq *rq, int cpu) 1429 { 1430 struct plist_head *head = &rq->rt.pushable_tasks; 1431 struct task_struct *p; 1432 1433 if (!has_pushable_tasks(rq)) 1434 return NULL; 1435 1436 plist_for_each_entry(p, head, pushable_tasks) { 1437 if (pick_rt_task(rq, p, cpu)) 1438 return p; 1439 } 1440 1441 return NULL; 1442 } 1443 1444 static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask); 1445 1446 static int find_lowest_rq(struct task_struct *task) 1447 { 1448 struct sched_domain *sd; 1449 struct cpumask *lowest_mask = __get_cpu_var(local_cpu_mask); 1450 int this_cpu = smp_processor_id(); 1451 int cpu = task_cpu(task); 1452 1453 /* Make sure the mask is initialized first */ 1454 if (unlikely(!lowest_mask)) 1455 return -1; 1456 1457 if (task->nr_cpus_allowed == 1) 1458 return -1; /* No other targets possible */ 1459 1460 if (!cpupri_find(&task_rq(task)->rd->cpupri, task, lowest_mask)) 1461 return -1; /* No targets found */ 1462 1463 /* 1464 * At this point we have built a mask of cpus representing the 1465 * lowest priority tasks in the system. Now we want to elect 1466 * the best one based on our affinity and topology. 1467 * 1468 * We prioritize the last cpu that the task executed on since 1469 * it is most likely cache-hot in that location. 1470 */ 1471 if (cpumask_test_cpu(cpu, lowest_mask)) 1472 return cpu; 1473 1474 /* 1475 * Otherwise, we consult the sched_domains span maps to figure 1476 * out which cpu is logically closest to our hot cache data. 1477 */ 1478 if (!cpumask_test_cpu(this_cpu, lowest_mask)) 1479 this_cpu = -1; /* Skip this_cpu opt if not among lowest */ 1480 1481 rcu_read_lock(); 1482 for_each_domain(cpu, sd) { 1483 if (sd->flags & SD_WAKE_AFFINE) { 1484 int best_cpu; 1485 1486 /* 1487 * "this_cpu" is cheaper to preempt than a 1488 * remote processor. 1489 */ 1490 if (this_cpu != -1 && 1491 cpumask_test_cpu(this_cpu, sched_domain_span(sd))) { 1492 rcu_read_unlock(); 1493 return this_cpu; 1494 } 1495 1496 best_cpu = cpumask_first_and(lowest_mask, 1497 sched_domain_span(sd)); 1498 if (best_cpu < nr_cpu_ids) { 1499 rcu_read_unlock(); 1500 return best_cpu; 1501 } 1502 } 1503 } 1504 rcu_read_unlock(); 1505 1506 /* 1507 * And finally, if there were no matches within the domains 1508 * just give the caller *something* to work with from the compatible 1509 * locations. 1510 */ 1511 if (this_cpu != -1) 1512 return this_cpu; 1513 1514 cpu = cpumask_any(lowest_mask); 1515 if (cpu < nr_cpu_ids) 1516 return cpu; 1517 return -1; 1518 } 1519 1520 /* Will lock the rq it finds */ 1521 static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq) 1522 { 1523 struct rq *lowest_rq = NULL; 1524 int tries; 1525 int cpu; 1526 1527 for (tries = 0; tries < RT_MAX_TRIES; tries++) { 1528 cpu = find_lowest_rq(task); 1529 1530 if ((cpu == -1) || (cpu == rq->cpu)) 1531 break; 1532 1533 lowest_rq = cpu_rq(cpu); 1534 1535 /* if the prio of this runqueue changed, try again */ 1536 if (double_lock_balance(rq, lowest_rq)) { 1537 /* 1538 * We had to unlock the run queue. In 1539 * the mean time, task could have 1540 * migrated already or had its affinity changed. 1541 * Also make sure that it wasn't scheduled on its rq. 1542 */ 1543 if (unlikely(task_rq(task) != rq || 1544 !cpumask_test_cpu(lowest_rq->cpu, 1545 tsk_cpus_allowed(task)) || 1546 task_running(rq, task) || 1547 !task->on_rq)) { 1548 1549 double_unlock_balance(rq, lowest_rq); 1550 lowest_rq = NULL; 1551 break; 1552 } 1553 } 1554 1555 /* If this rq is still suitable use it. */ 1556 if (lowest_rq->rt.highest_prio.curr > task->prio) 1557 break; 1558 1559 /* try again */ 1560 double_unlock_balance(rq, lowest_rq); 1561 lowest_rq = NULL; 1562 } 1563 1564 return lowest_rq; 1565 } 1566 1567 static struct task_struct *pick_next_pushable_task(struct rq *rq) 1568 { 1569 struct task_struct *p; 1570 1571 if (!has_pushable_tasks(rq)) 1572 return NULL; 1573 1574 p = plist_first_entry(&rq->rt.pushable_tasks, 1575 struct task_struct, pushable_tasks); 1576 1577 BUG_ON(rq->cpu != task_cpu(p)); 1578 BUG_ON(task_current(rq, p)); 1579 BUG_ON(p->nr_cpus_allowed <= 1); 1580 1581 BUG_ON(!p->on_rq); 1582 BUG_ON(!rt_task(p)); 1583 1584 return p; 1585 } 1586 1587 /* 1588 * If the current CPU has more than one RT task, see if the non 1589 * running task can migrate over to a CPU that is running a task 1590 * of lesser priority. 1591 */ 1592 static int push_rt_task(struct rq *rq) 1593 { 1594 struct task_struct *next_task; 1595 struct rq *lowest_rq; 1596 int ret = 0; 1597 1598 if (!rq->rt.overloaded) 1599 return 0; 1600 1601 next_task = pick_next_pushable_task(rq); 1602 if (!next_task) 1603 return 0; 1604 1605 retry: 1606 if (unlikely(next_task == rq->curr)) { 1607 WARN_ON(1); 1608 return 0; 1609 } 1610 1611 /* 1612 * It's possible that the next_task slipped in of 1613 * higher priority than current. If that's the case 1614 * just reschedule current. 1615 */ 1616 if (unlikely(next_task->prio < rq->curr->prio)) { 1617 resched_task(rq->curr); 1618 return 0; 1619 } 1620 1621 /* We might release rq lock */ 1622 get_task_struct(next_task); 1623 1624 /* find_lock_lowest_rq locks the rq if found */ 1625 lowest_rq = find_lock_lowest_rq(next_task, rq); 1626 if (!lowest_rq) { 1627 struct task_struct *task; 1628 /* 1629 * find_lock_lowest_rq releases rq->lock 1630 * so it is possible that next_task has migrated. 1631 * 1632 * We need to make sure that the task is still on the same 1633 * run-queue and is also still the next task eligible for 1634 * pushing. 1635 */ 1636 task = pick_next_pushable_task(rq); 1637 if (task_cpu(next_task) == rq->cpu && task == next_task) { 1638 /* 1639 * The task hasn't migrated, and is still the next 1640 * eligible task, but we failed to find a run-queue 1641 * to push it to. Do not retry in this case, since 1642 * other cpus will pull from us when ready. 1643 */ 1644 goto out; 1645 } 1646 1647 if (!task) 1648 /* No more tasks, just exit */ 1649 goto out; 1650 1651 /* 1652 * Something has shifted, try again. 1653 */ 1654 put_task_struct(next_task); 1655 next_task = task; 1656 goto retry; 1657 } 1658 1659 deactivate_task(rq, next_task, 0); 1660 set_task_cpu(next_task, lowest_rq->cpu); 1661 activate_task(lowest_rq, next_task, 0); 1662 ret = 1; 1663 1664 resched_task(lowest_rq->curr); 1665 1666 double_unlock_balance(rq, lowest_rq); 1667 1668 out: 1669 put_task_struct(next_task); 1670 1671 return ret; 1672 } 1673 1674 static void push_rt_tasks(struct rq *rq) 1675 { 1676 /* push_rt_task will return true if it moved an RT */ 1677 while (push_rt_task(rq)) 1678 ; 1679 } 1680 1681 static int pull_rt_task(struct rq *this_rq) 1682 { 1683 int this_cpu = this_rq->cpu, ret = 0, cpu; 1684 struct task_struct *p; 1685 struct rq *src_rq; 1686 1687 if (likely(!rt_overloaded(this_rq))) 1688 return 0; 1689 1690 /* 1691 * Match the barrier from rt_set_overloaded; this guarantees that if we 1692 * see overloaded we must also see the rto_mask bit. 1693 */ 1694 smp_rmb(); 1695 1696 for_each_cpu(cpu, this_rq->rd->rto_mask) { 1697 if (this_cpu == cpu) 1698 continue; 1699 1700 src_rq = cpu_rq(cpu); 1701 1702 /* 1703 * Don't bother taking the src_rq->lock if the next highest 1704 * task is known to be lower-priority than our current task. 1705 * This may look racy, but if this value is about to go 1706 * logically higher, the src_rq will push this task away. 1707 * And if its going logically lower, we do not care 1708 */ 1709 if (src_rq->rt.highest_prio.next >= 1710 this_rq->rt.highest_prio.curr) 1711 continue; 1712 1713 /* 1714 * We can potentially drop this_rq's lock in 1715 * double_lock_balance, and another CPU could 1716 * alter this_rq 1717 */ 1718 double_lock_balance(this_rq, src_rq); 1719 1720 /* 1721 * We can pull only a task, which is pushable 1722 * on its rq, and no others. 1723 */ 1724 p = pick_highest_pushable_task(src_rq, this_cpu); 1725 1726 /* 1727 * Do we have an RT task that preempts 1728 * the to-be-scheduled task? 1729 */ 1730 if (p && (p->prio < this_rq->rt.highest_prio.curr)) { 1731 WARN_ON(p == src_rq->curr); 1732 WARN_ON(!p->on_rq); 1733 1734 /* 1735 * There's a chance that p is higher in priority 1736 * than what's currently running on its cpu. 1737 * This is just that p is wakeing up and hasn't 1738 * had a chance to schedule. We only pull 1739 * p if it is lower in priority than the 1740 * current task on the run queue 1741 */ 1742 if (p->prio < src_rq->curr->prio) 1743 goto skip; 1744 1745 ret = 1; 1746 1747 deactivate_task(src_rq, p, 0); 1748 set_task_cpu(p, this_cpu); 1749 activate_task(this_rq, p, 0); 1750 /* 1751 * We continue with the search, just in 1752 * case there's an even higher prio task 1753 * in another runqueue. (low likelihood 1754 * but possible) 1755 */ 1756 } 1757 skip: 1758 double_unlock_balance(this_rq, src_rq); 1759 } 1760 1761 return ret; 1762 } 1763 1764 static void post_schedule_rt(struct rq *rq) 1765 { 1766 push_rt_tasks(rq); 1767 } 1768 1769 /* 1770 * If we are not running and we are not going to reschedule soon, we should 1771 * try to push tasks away now 1772 */ 1773 static void task_woken_rt(struct rq *rq, struct task_struct *p) 1774 { 1775 if (!task_running(rq, p) && 1776 !test_tsk_need_resched(rq->curr) && 1777 has_pushable_tasks(rq) && 1778 p->nr_cpus_allowed > 1 && 1779 (dl_task(rq->curr) || rt_task(rq->curr)) && 1780 (rq->curr->nr_cpus_allowed < 2 || 1781 rq->curr->prio <= p->prio)) 1782 push_rt_tasks(rq); 1783 } 1784 1785 static void set_cpus_allowed_rt(struct task_struct *p, 1786 const struct cpumask *new_mask) 1787 { 1788 struct rq *rq; 1789 int weight; 1790 1791 BUG_ON(!rt_task(p)); 1792 1793 if (!p->on_rq) 1794 return; 1795 1796 weight = cpumask_weight(new_mask); 1797 1798 /* 1799 * Only update if the process changes its state from whether it 1800 * can migrate or not. 1801 */ 1802 if ((p->nr_cpus_allowed > 1) == (weight > 1)) 1803 return; 1804 1805 rq = task_rq(p); 1806 1807 /* 1808 * The process used to be able to migrate OR it can now migrate 1809 */ 1810 if (weight <= 1) { 1811 if (!task_current(rq, p)) 1812 dequeue_pushable_task(rq, p); 1813 BUG_ON(!rq->rt.rt_nr_migratory); 1814 rq->rt.rt_nr_migratory--; 1815 } else { 1816 if (!task_current(rq, p)) 1817 enqueue_pushable_task(rq, p); 1818 rq->rt.rt_nr_migratory++; 1819 } 1820 1821 update_rt_migration(&rq->rt); 1822 } 1823 1824 /* Assumes rq->lock is held */ 1825 static void rq_online_rt(struct rq *rq) 1826 { 1827 if (rq->rt.overloaded) 1828 rt_set_overload(rq); 1829 1830 __enable_runtime(rq); 1831 1832 cpupri_set(&rq->rd->cpupri, rq->cpu, rq->rt.highest_prio.curr); 1833 } 1834 1835 /* Assumes rq->lock is held */ 1836 static void rq_offline_rt(struct rq *rq) 1837 { 1838 if (rq->rt.overloaded) 1839 rt_clear_overload(rq); 1840 1841 __disable_runtime(rq); 1842 1843 cpupri_set(&rq->rd->cpupri, rq->cpu, CPUPRI_INVALID); 1844 } 1845 1846 /* 1847 * When switch from the rt queue, we bring ourselves to a position 1848 * that we might want to pull RT tasks from other runqueues. 1849 */ 1850 static void switched_from_rt(struct rq *rq, struct task_struct *p) 1851 { 1852 /* 1853 * If there are other RT tasks then we will reschedule 1854 * and the scheduling of the other RT tasks will handle 1855 * the balancing. But if we are the last RT task 1856 * we may need to handle the pulling of RT tasks 1857 * now. 1858 */ 1859 if (!p->on_rq || rq->rt.rt_nr_running) 1860 return; 1861 1862 if (pull_rt_task(rq)) 1863 resched_task(rq->curr); 1864 } 1865 1866 void __init init_sched_rt_class(void) 1867 { 1868 unsigned int i; 1869 1870 for_each_possible_cpu(i) { 1871 zalloc_cpumask_var_node(&per_cpu(local_cpu_mask, i), 1872 GFP_KERNEL, cpu_to_node(i)); 1873 } 1874 } 1875 #endif /* CONFIG_SMP */ 1876 1877 /* 1878 * When switching a task to RT, we may overload the runqueue 1879 * with RT tasks. In this case we try to push them off to 1880 * other runqueues. 1881 */ 1882 static void switched_to_rt(struct rq *rq, struct task_struct *p) 1883 { 1884 int check_resched = 1; 1885 1886 /* 1887 * If we are already running, then there's nothing 1888 * that needs to be done. But if we are not running 1889 * we may need to preempt the current running task. 1890 * If that current running task is also an RT task 1891 * then see if we can move to another run queue. 1892 */ 1893 if (p->on_rq && rq->curr != p) { 1894 #ifdef CONFIG_SMP 1895 if (rq->rt.overloaded && push_rt_task(rq) && 1896 /* Don't resched if we changed runqueues */ 1897 rq != task_rq(p)) 1898 check_resched = 0; 1899 #endif /* CONFIG_SMP */ 1900 if (check_resched && p->prio < rq->curr->prio) 1901 resched_task(rq->curr); 1902 } 1903 } 1904 1905 /* 1906 * Priority of the task has changed. This may cause 1907 * us to initiate a push or pull. 1908 */ 1909 static void 1910 prio_changed_rt(struct rq *rq, struct task_struct *p, int oldprio) 1911 { 1912 if (!p->on_rq) 1913 return; 1914 1915 if (rq->curr == p) { 1916 #ifdef CONFIG_SMP 1917 /* 1918 * If our priority decreases while running, we 1919 * may need to pull tasks to this runqueue. 1920 */ 1921 if (oldprio < p->prio) 1922 pull_rt_task(rq); 1923 /* 1924 * If there's a higher priority task waiting to run 1925 * then reschedule. Note, the above pull_rt_task 1926 * can release the rq lock and p could migrate. 1927 * Only reschedule if p is still on the same runqueue. 1928 */ 1929 if (p->prio > rq->rt.highest_prio.curr && rq->curr == p) 1930 resched_task(p); 1931 #else 1932 /* For UP simply resched on drop of prio */ 1933 if (oldprio < p->prio) 1934 resched_task(p); 1935 #endif /* CONFIG_SMP */ 1936 } else { 1937 /* 1938 * This task is not running, but if it is 1939 * greater than the current running task 1940 * then reschedule. 1941 */ 1942 if (p->prio < rq->curr->prio) 1943 resched_task(rq->curr); 1944 } 1945 } 1946 1947 static void watchdog(struct rq *rq, struct task_struct *p) 1948 { 1949 unsigned long soft, hard; 1950 1951 /* max may change after cur was read, this will be fixed next tick */ 1952 soft = task_rlimit(p, RLIMIT_RTTIME); 1953 hard = task_rlimit_max(p, RLIMIT_RTTIME); 1954 1955 if (soft != RLIM_INFINITY) { 1956 unsigned long next; 1957 1958 if (p->rt.watchdog_stamp != jiffies) { 1959 p->rt.timeout++; 1960 p->rt.watchdog_stamp = jiffies; 1961 } 1962 1963 next = DIV_ROUND_UP(min(soft, hard), USEC_PER_SEC/HZ); 1964 if (p->rt.timeout > next) 1965 p->cputime_expires.sched_exp = p->se.sum_exec_runtime; 1966 } 1967 } 1968 1969 static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued) 1970 { 1971 struct sched_rt_entity *rt_se = &p->rt; 1972 1973 update_curr_rt(rq); 1974 1975 watchdog(rq, p); 1976 1977 /* 1978 * RR tasks need a special form of timeslice management. 1979 * FIFO tasks have no timeslices. 1980 */ 1981 if (p->policy != SCHED_RR) 1982 return; 1983 1984 if (--p->rt.time_slice) 1985 return; 1986 1987 p->rt.time_slice = sched_rr_timeslice; 1988 1989 /* 1990 * Requeue to the end of queue if we (and all of our ancestors) are not 1991 * the only element on the queue 1992 */ 1993 for_each_sched_rt_entity(rt_se) { 1994 if (rt_se->run_list.prev != rt_se->run_list.next) { 1995 requeue_task_rt(rq, p, 0); 1996 set_tsk_need_resched(p); 1997 return; 1998 } 1999 } 2000 } 2001 2002 static void set_curr_task_rt(struct rq *rq) 2003 { 2004 struct task_struct *p = rq->curr; 2005 2006 p->se.exec_start = rq_clock_task(rq); 2007 2008 /* The running task is never eligible for pushing */ 2009 dequeue_pushable_task(rq, p); 2010 } 2011 2012 static unsigned int get_rr_interval_rt(struct rq *rq, struct task_struct *task) 2013 { 2014 /* 2015 * Time slice is 0 for SCHED_FIFO tasks 2016 */ 2017 if (task->policy == SCHED_RR) 2018 return sched_rr_timeslice; 2019 else 2020 return 0; 2021 } 2022 2023 const struct sched_class rt_sched_class = { 2024 .next = &fair_sched_class, 2025 .enqueue_task = enqueue_task_rt, 2026 .dequeue_task = dequeue_task_rt, 2027 .yield_task = yield_task_rt, 2028 2029 .check_preempt_curr = check_preempt_curr_rt, 2030 2031 .pick_next_task = pick_next_task_rt, 2032 .put_prev_task = put_prev_task_rt, 2033 2034 #ifdef CONFIG_SMP 2035 .select_task_rq = select_task_rq_rt, 2036 2037 .set_cpus_allowed = set_cpus_allowed_rt, 2038 .rq_online = rq_online_rt, 2039 .rq_offline = rq_offline_rt, 2040 .post_schedule = post_schedule_rt, 2041 .task_woken = task_woken_rt, 2042 .switched_from = switched_from_rt, 2043 #endif 2044 2045 .set_curr_task = set_curr_task_rt, 2046 .task_tick = task_tick_rt, 2047 2048 .get_rr_interval = get_rr_interval_rt, 2049 2050 .prio_changed = prio_changed_rt, 2051 .switched_to = switched_to_rt, 2052 }; 2053 2054 #ifdef CONFIG_SCHED_DEBUG 2055 extern void print_rt_rq(struct seq_file *m, int cpu, struct rt_rq *rt_rq); 2056 2057 void print_rt_stats(struct seq_file *m, int cpu) 2058 { 2059 rt_rq_iter_t iter; 2060 struct rt_rq *rt_rq; 2061 2062 rcu_read_lock(); 2063 for_each_rt_rq(rt_rq, iter, cpu_rq(cpu)) 2064 print_rt_rq(m, cpu, rt_rq); 2065 rcu_read_unlock(); 2066 } 2067 #endif /* CONFIG_SCHED_DEBUG */ 2068