Lines Matching +full:throttle +full:- +full:period +full:- +full:us
1 // SPDX-License-Identifier: GPL-2.0
22 * Default limits for DL period; on the top end we guard against small util
27 static unsigned int sysctl_sched_dl_period_min = 100; /* 100 us */
72 return &rq->dl; in dl_rq_of_se()
77 return !RB_EMPTY_NODE(&dl_se->rb_node); in on_dl_rq()
83 return dl_se->pi_se; in pi_of()
107 return &cpu_rq(i)->rd->dl_bw; in dl_bw_of()
112 struct root_domain *rd = cpu_rq(i)->rd; in dl_bw_cpus()
118 if (cpumask_subset(rd->span, cpu_active_mask)) in dl_bw_cpus()
119 return cpumask_weight(rd->span); in dl_bw_cpus()
123 for_each_cpu_and(i, rd->span, cpu_active_mask) in dl_bw_cpus()
141 * XXX Fix: If 'rq->rd == def_root_domain' perform AC against capacity
153 return __dl_bw_capacity(cpu_rq(i)->rd->span); in dl_bw_capacity()
159 struct root_domain *rd = cpu_rq(cpu)->rd; in dl_bw_visited()
161 if (rd->visit_gen == gen) in dl_bw_visited()
164 rd->visit_gen = gen; in dl_bw_visited()
176 for_each_cpu_and(i, rd->span, cpu_active_mask) { in __dl_update()
179 rq->dl.extra_bw += bw; in __dl_update()
185 return &cpu_rq(i)->dl.dl_bw; in dl_bw_of()
208 dl->extra_bw += bw; in __dl_update()
215 dl_b->total_bw -= tsk_bw; in __dl_sub()
222 dl_b->total_bw += tsk_bw; in __dl_add()
223 __dl_update(dl_b, -((s32)tsk_bw / cpus)); in __dl_add()
229 return dl_b->bw != -1 && in __dl_overflow()
230 cap_scale(dl_b->bw, cap) < dl_b->total_bw - old_bw + new_bw; in __dl_overflow()
236 u64 old = dl_rq->running_bw; in __add_running_bw()
239 dl_rq->running_bw += dl_bw; in __add_running_bw()
240 SCHED_WARN_ON(dl_rq->running_bw < old); /* overflow */ in __add_running_bw()
241 SCHED_WARN_ON(dl_rq->running_bw > dl_rq->this_bw); in __add_running_bw()
249 u64 old = dl_rq->running_bw; in __sub_running_bw()
252 dl_rq->running_bw -= dl_bw; in __sub_running_bw()
253 SCHED_WARN_ON(dl_rq->running_bw > old); /* underflow */ in __sub_running_bw()
254 if (dl_rq->running_bw > old) in __sub_running_bw()
255 dl_rq->running_bw = 0; in __sub_running_bw()
263 u64 old = dl_rq->this_bw; in __add_rq_bw()
266 dl_rq->this_bw += dl_bw; in __add_rq_bw()
267 SCHED_WARN_ON(dl_rq->this_bw < old); /* overflow */ in __add_rq_bw()
273 u64 old = dl_rq->this_bw; in __sub_rq_bw()
276 dl_rq->this_bw -= dl_bw; in __sub_rq_bw()
277 SCHED_WARN_ON(dl_rq->this_bw > old); /* underflow */ in __sub_rq_bw()
278 if (dl_rq->this_bw > old) in __sub_rq_bw()
279 dl_rq->this_bw = 0; in __sub_rq_bw()
280 SCHED_WARN_ON(dl_rq->running_bw > dl_rq->this_bw); in __sub_rq_bw()
287 __add_rq_bw(dl_se->dl_bw, dl_rq); in add_rq_bw()
294 __sub_rq_bw(dl_se->dl_bw, dl_rq); in sub_rq_bw()
301 __add_running_bw(dl_se->dl_bw, dl_rq); in add_running_bw()
308 __sub_running_bw(dl_se->dl_bw, dl_rq); in sub_running_bw()
315 WARN_ON_ONCE(p->dl.flags & SCHED_FLAG_SUGOV); in dl_change_utilization()
321 if (p->dl.dl_non_contending) { in dl_change_utilization()
322 sub_running_bw(&p->dl, &rq->dl); in dl_change_utilization()
323 p->dl.dl_non_contending = 0; in dl_change_utilization()
331 if (hrtimer_try_to_cancel(&p->dl.inactive_timer) == 1) in dl_change_utilization()
334 __sub_rq_bw(p->dl.dl_bw, &rq->dl); in dl_change_utilization()
335 __add_rq_bw(new_bw, &rq->dl); in dl_change_utilization()
343 * Instead, we have to wait for the so called "0-lag time".
345 * If a task blocks before the "0-lag time", a timer (the inactive
360 * "ACTIVE non contending" task is a blocked task for which the "0-lag time"
361 * has not passed yet. An "INACTIVE" task is a task for which the "0-lag"
363 * +------------------+
365 * +------------------>+ contending |
367 * | +----+------+------+
370 * +--------+-------+ | |
371 * | | t >= 0-lag | | wakeup
372 * | INACTIVE |<---------------+ |
374 * +--------+-------+ | |
376 * | t < 0-lag | |
379 * | +----+------+------+
381 * +-------------------+ |
383 * fired +------------------+
386 * blocks, and checks if the 0-lag time already passed or
396 struct hrtimer *timer = &dl_se->inactive_timer; in task_non_contending()
403 * If this is a non-deadline task that has been boosted, in task_non_contending()
406 if (dl_se->dl_runtime == 0) in task_non_contending()
412 WARN_ON(dl_se->dl_non_contending); in task_non_contending()
414 zerolag_time = dl_se->deadline - in task_non_contending()
415 div64_long((dl_se->runtime * dl_se->dl_period), in task_non_contending()
416 dl_se->dl_runtime); in task_non_contending()
419 * Using relative times instead of the absolute "0-lag time" in task_non_contending()
422 zerolag_time -= rq_clock(rq); in task_non_contending()
425 * If the "0-lag time" already passed, decrease the active in task_non_contending()
428 if ((zerolag_time < 0) || hrtimer_active(&dl_se->inactive_timer)) { in task_non_contending()
432 if (!dl_task(p) || READ_ONCE(p->__state) == TASK_DEAD) { in task_non_contending()
435 if (READ_ONCE(p->__state) == TASK_DEAD) in task_non_contending()
436 sub_rq_bw(dl_se, &rq->dl); in task_non_contending()
437 raw_spin_lock(&dl_b->lock); in task_non_contending()
438 __dl_sub(dl_b, dl_se->dl_bw, dl_bw_cpus(task_cpu(p))); in task_non_contending()
439 raw_spin_unlock(&dl_b->lock); in task_non_contending()
446 dl_se->dl_non_contending = 1; in task_non_contending()
456 * If this is a non-deadline task that has been boosted, in task_contending()
459 if (dl_se->dl_runtime == 0) in task_contending()
465 if (dl_se->dl_non_contending) { in task_contending()
466 dl_se->dl_non_contending = 0; in task_contending()
474 if (hrtimer_try_to_cancel(&dl_se->inactive_timer) == 1) in task_contending()
490 struct sched_dl_entity *dl_se = &p->dl; in is_leftmost()
492 return rb_first_cached(&dl_rq->root) == &dl_se->rb_node; in is_leftmost()
499 raw_spin_lock_init(&dl_b->lock); in init_dl_bw()
501 dl_b->bw = -1; in init_dl_bw()
503 dl_b->bw = to_ratio(global_rt_period(), global_rt_runtime()); in init_dl_bw()
504 dl_b->total_bw = 0; in init_dl_bw()
509 dl_rq->root = RB_ROOT_CACHED; in init_dl_rq()
512 /* zero means no -deadline tasks */ in init_dl_rq()
513 dl_rq->earliest_dl.curr = dl_rq->earliest_dl.next = 0; in init_dl_rq()
515 dl_rq->dl_nr_migratory = 0; in init_dl_rq()
516 dl_rq->overloaded = 0; in init_dl_rq()
517 dl_rq->pushable_dl_tasks_root = RB_ROOT_CACHED; in init_dl_rq()
519 init_dl_bw(&dl_rq->dl_bw); in init_dl_rq()
522 dl_rq->running_bw = 0; in init_dl_rq()
523 dl_rq->this_bw = 0; in init_dl_rq()
531 return atomic_read(&rq->rd->dlo_count); in dl_overloaded()
536 if (!rq->online) in dl_set_overload()
539 cpumask_set_cpu(rq->cpu, rq->rd->dlo_mask); in dl_set_overload()
547 atomic_inc(&rq->rd->dlo_count); in dl_set_overload()
552 if (!rq->online) in dl_clear_overload()
555 atomic_dec(&rq->rd->dlo_count); in dl_clear_overload()
556 cpumask_clear_cpu(rq->cpu, rq->rd->dlo_mask); in dl_clear_overload()
561 if (dl_rq->dl_nr_migratory && dl_rq->dl_nr_running > 1) { in update_dl_migration()
562 if (!dl_rq->overloaded) { in update_dl_migration()
564 dl_rq->overloaded = 1; in update_dl_migration()
566 } else if (dl_rq->overloaded) { in update_dl_migration()
568 dl_rq->overloaded = 0; in update_dl_migration()
576 if (p->nr_cpus_allowed > 1) in inc_dl_migration()
577 dl_rq->dl_nr_migratory++; in inc_dl_migration()
586 if (p->nr_cpus_allowed > 1) in dec_dl_migration()
587 dl_rq->dl_nr_migratory--; in dec_dl_migration()
597 return dl_entity_preempt(&__node_2_pdl(a)->dl, &__node_2_pdl(b)->dl); in __pushable_less()
601 * The list of pushable -deadline task is not a plist, like in
602 * sched_rt.c, it is an rb-tree with tasks ordered by deadline.
608 WARN_ON_ONCE(!RB_EMPTY_NODE(&p->pushable_dl_tasks)); in enqueue_pushable_dl_task()
610 leftmost = rb_add_cached(&p->pushable_dl_tasks, in enqueue_pushable_dl_task()
611 &rq->dl.pushable_dl_tasks_root, in enqueue_pushable_dl_task()
614 rq->dl.earliest_dl.next = p->dl.deadline; in enqueue_pushable_dl_task()
619 struct dl_rq *dl_rq = &rq->dl; in dequeue_pushable_dl_task()
620 struct rb_root_cached *root = &dl_rq->pushable_dl_tasks_root; in dequeue_pushable_dl_task()
623 if (RB_EMPTY_NODE(&p->pushable_dl_tasks)) in dequeue_pushable_dl_task()
626 leftmost = rb_erase_cached(&p->pushable_dl_tasks, root); in dequeue_pushable_dl_task()
628 dl_rq->earliest_dl.next = __node_2_pdl(leftmost)->dl.deadline; in dequeue_pushable_dl_task()
630 RB_CLEAR_NODE(&p->pushable_dl_tasks); in dequeue_pushable_dl_task()
635 return !RB_EMPTY_ROOT(&rq->dl.pushable_dl_tasks_root.rb_root); in has_pushable_dl_tasks()
642 return rq->online && dl_task(prev); in need_pull_dl_task()
656 queue_balance_callback(rq, &per_cpu(dl_push_head, rq->cpu), push_dl_tasks); in deadline_queue_push_tasks()
661 queue_balance_callback(rq, &per_cpu(dl_pull_head, rq->cpu), pull_dl_task); in deadline_queue_pull_task()
679 cpu = cpumask_any_and(cpu_active_mask, p->cpus_ptr); in dl_task_offline_migration()
698 if (p->dl.dl_non_contending || p->dl.dl_throttled) { in dl_task_offline_migration()
701 * waiting for us to release rq locks). In any case, when it in dl_task_offline_migration()
705 sub_running_bw(&p->dl, &rq->dl); in dl_task_offline_migration()
706 sub_rq_bw(&p->dl, &rq->dl); in dl_task_offline_migration()
708 add_rq_bw(&p->dl, &later_rq->dl); in dl_task_offline_migration()
709 add_running_bw(&p->dl, &later_rq->dl); in dl_task_offline_migration()
711 sub_rq_bw(&p->dl, &rq->dl); in dl_task_offline_migration()
712 add_rq_bw(&p->dl, &later_rq->dl); in dl_task_offline_migration()
720 dl_b = &rq->rd->dl_bw; in dl_task_offline_migration()
721 raw_spin_lock(&dl_b->lock); in dl_task_offline_migration()
722 __dl_sub(dl_b, p->dl.dl_bw, cpumask_weight(rq->rd->span)); in dl_task_offline_migration()
723 raw_spin_unlock(&dl_b->lock); in dl_task_offline_migration()
725 dl_b = &later_rq->rd->dl_bw; in dl_task_offline_migration()
726 raw_spin_lock(&dl_b->lock); in dl_task_offline_migration()
727 __dl_add(dl_b, p->dl.dl_bw, cpumask_weight(later_rq->rd->span)); in dl_task_offline_migration()
728 raw_spin_unlock(&dl_b->lock); in dl_task_offline_migration()
730 set_task_cpu(p, later_rq->cpu); in dl_task_offline_migration()
774 /* for non-boosted task, pi_of(dl_se) == dl_se */ in replenish_dl_new_period()
775 dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline; in replenish_dl_new_period()
776 dl_se->runtime = pi_of(dl_se)->dl_runtime; in replenish_dl_new_period()
782 * - the absolute deadline of the entity has to be placed at
784 * - the runtime of the entity has to be set to the maximum value.
786 * The capability of specifying such event is useful whenever a -deadline
797 WARN_ON(dl_time_before(rq_clock(rq), dl_se->deadline)); in setup_new_dl_entity()
804 if (dl_se->dl_throttled) in setup_new_dl_entity()
838 WARN_ON_ONCE(pi_of(dl_se)->dl_runtime <= 0); in replenish_dl_entity()
841 * This could be the case for a !-dl task that is boosted. in replenish_dl_entity()
844 if (dl_se->dl_deadline == 0) in replenish_dl_entity()
847 if (dl_se->dl_yielded && dl_se->runtime > 0) in replenish_dl_entity()
848 dl_se->runtime = 0; in replenish_dl_entity()
856 while (dl_se->runtime <= 0) { in replenish_dl_entity()
857 dl_se->deadline += pi_of(dl_se)->dl_period; in replenish_dl_entity()
858 dl_se->runtime += pi_of(dl_se)->dl_runtime; in replenish_dl_entity()
863 * the future" with respect to rq->clock. If it's in replenish_dl_entity()
870 if (dl_time_before(dl_se->deadline, rq_clock(rq))) { in replenish_dl_entity()
875 if (dl_se->dl_yielded) in replenish_dl_entity()
876 dl_se->dl_yielded = 0; in replenish_dl_entity()
877 if (dl_se->dl_throttled) in replenish_dl_entity()
878 dl_se->dl_throttled = 0; in replenish_dl_entity()
882 * Here we check if --at time t-- an entity (which is probably being
890 * refill the runtime and set the deadline a period in the future,
893 * Documentation/scheduler/sched-deadline.rst for more information).
897 * runtime / (deadline - t) > dl_runtime / dl_deadline ,
902 * task with deadline equal to period this is the same of using
918 * and (deadline - t), since t is rq->clock, is the time left in dl_entity_overflow()
922 * means that we reduce granularity to 1us. We are fine with it, in dl_entity_overflow()
927 left = (pi_of(dl_se)->dl_deadline >> DL_SCALE) * (dl_se->runtime >> DL_SCALE); in dl_entity_overflow()
928 right = ((dl_se->deadline - t) >> DL_SCALE) * in dl_entity_overflow()
929 (pi_of(dl_se)->dl_runtime >> DL_SCALE); in dl_entity_overflow()
935 * Revised wakeup rule [1]: For self-suspending tasks, rather then
936 * re-initializing task's runtime and deadline, the revised wakeup
941 * runtime / (deadline - t) > dl_runtime / dl_deadline
944 * runtime = (dl_runtime / dl_deadline) * (deadline - t)
950 * bandwidth server revisited. SIGBED Rev. 11, 4 (January 2015), 19-24.
955 u64 laxity = dl_se->deadline - rq_clock(rq); in update_dl_revised_wakeup()
958 * If the task has deadline < period, and the deadline is in the past, in update_dl_revised_wakeup()
963 WARN_ON(dl_time_before(dl_se->deadline, rq_clock(rq))); in update_dl_revised_wakeup()
965 dl_se->runtime = (dl_se->dl_density * laxity) >> BW_SHIFT; in update_dl_revised_wakeup()
970 * deadline == relative period. A task with constrained deadline has a
971 * relative deadline <= relative period.
981 return dl_se->dl_deadline == dl_se->dl_period; in dl_is_implicit()
989 * When the task is starting a new period, the Original CBS is used. In this
992 * When a task is queued before the begin of the next period, using the
997 * If the task has an implicit deadline, i.e., deadline == period, the Original
1002 * deadline < period, which are said to have a constrained deadline. By
1004 * runtime/deadline in a period. With deadline < period, the task would
1005 * overrun the runtime/period allowed bandwidth, breaking the admission test.
1019 if (dl_time_before(dl_se->deadline, rq_clock(rq)) || in update_dl_entity()
1023 !dl_time_before(dl_se->deadline, rq_clock(rq)) && in update_dl_entity()
1035 return dl_se->deadline - dl_se->dl_deadline + dl_se->dl_period; in dl_next_period()
1050 struct sched_dl_entity *dl_se = &p->dl; in start_dl_timer()
1051 struct hrtimer *timer = &dl_se->dl_timer; in start_dl_timer()
1060 * that it is actually coming from rq->clock and not from in start_dl_timer()
1065 delta = ktime_to_ns(now) - rq_clock(rq); in start_dl_timer()
1081 * harmless because we're holding task_rq()->lock, therefore the timer in start_dl_timer()
1135 if (!dl_se->dl_throttled) in dl_task_timer()
1142 * If the throttle happened during sched-out; like: in dl_task_timer()
1150 * prev->on_rq = 0; in dl_task_timer()
1153 * but do not enqueue -- wait for our wakeup to do that. in dl_task_timer()
1161 if (unlikely(!rq->online)) { in dl_task_timer()
1180 if (dl_task(rq->curr)) in dl_task_timer()
1192 * Nothing relies on rq->lock after this, so its safe to drop in dl_task_timer()
1193 * rq->lock. in dl_task_timer()
1215 struct hrtimer *timer = &dl_se->dl_timer; in init_dl_task_timer()
1218 timer->function = dl_task_timer; in init_dl_task_timer()
1223 * runtime and period. If the deadline of the task is in the past, CBS
1225 * works fine for implicit deadline tasks (deadline == period), and the
1227 * constrained deadline (deadline < period) might be awakened after the
1228 * deadline, but before the next period. In this case, replenishing the
1230 * deadline < period, CBS enables a task to run for more than the
1231 * runtime / period. In a very loaded system, this can cause a domino
1235 * task after the deadline but before the next period, throttle the
1236 * task and set the replenishing timer to the begin of the next period,
1244 if (dl_time_before(dl_se->deadline, rq_clock(rq)) && in dl_check_constrained_dl()
1248 dl_se->dl_throttled = 1; in dl_check_constrained_dl()
1249 if (dl_se->runtime > 0) in dl_check_constrained_dl()
1250 dl_se->runtime = 0; in dl_check_constrained_dl()
1257 return (dl_se->runtime <= 0); in dl_runtime_exceeded()
1262 * GRUB reclaiming algorithm, the runtime is not decreased as "dq = -dt",
1263 * but as "dq = -(max{u, (Umax - Uinact - Uextra)} / Umax) dt",
1265 * utilization, Uinact is the (per-runqueue) inactive utilization, computed
1269 * Since rq->dl.running_bw and rq->dl.this_bw contain utilizations multiplied
1271 * Since rq->dl.bw_ratio contains 1 / Umax multiplied by 2^RATIO_SHIFT, dl_bw
1272 * is multiped by rq->dl.bw_ratio and shifted right by RATIO_SHIFT.
1274 * larger than 2^(64 - 20 - 8), which is more than 64 seconds. So, overflow is
1280 u64 u_inact = rq->dl.this_bw - rq->dl.running_bw; /* Utot - Uact */ in grub_reclaim()
1283 * Instead of computing max{u, (u_max - u_inact - u_extra)}, we in grub_reclaim()
1284 * compare u_inact + u_extra with u_max - u, because u_inact + u_extra in grub_reclaim()
1285 * can be larger than u_max. So, u_max - u_inact - u_extra would be in grub_reclaim()
1288 if (u_inact + rq->dl.extra_bw > rq->dl.max_bw - dl_se->dl_bw) in grub_reclaim()
1289 u_act = dl_se->dl_bw; in grub_reclaim()
1291 u_act = rq->dl.max_bw - u_inact - rq->dl.extra_bw; in grub_reclaim()
1293 u_act = (u_act * rq->dl.bw_ratio) >> RATIO_SHIFT; in grub_reclaim()
1299 * a -deadline task and has not been removed from the dl_rq).
1303 struct task_struct *curr = rq->curr; in update_curr_dl()
1304 struct sched_dl_entity *dl_se = &curr->dl; in update_curr_dl()
1321 if (unlikely(dl_se->dl_yielded)) in update_curr_dl()
1322 goto throttle; in update_curr_dl()
1330 * For tasks that participate in GRUB, we implement GRUB-PA: the in update_curr_dl()
1336 if (unlikely(dl_se->flags & SCHED_FLAG_RECLAIM)) { in update_curr_dl()
1339 &curr->dl); in update_curr_dl()
1348 dl_se->runtime -= scaled_delta_exec; in update_curr_dl()
1350 throttle: in update_curr_dl()
1351 if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) { in update_curr_dl()
1352 dl_se->dl_throttled = 1; in update_curr_dl()
1356 (dl_se->flags & SCHED_FLAG_DL_OVERRUN)) in update_curr_dl()
1357 dl_se->dl_overrun = 1; in update_curr_dl()
1363 if (!is_leftmost(curr, &rq->dl)) in update_curr_dl()
1368 * Because -- for now -- we share the rt bandwidth, we need to in update_curr_dl()
1375 * using deadline servers -- however there's a few nasties to figure in update_curr_dl()
1379 struct rt_rq *rt_rq = &rq->rt; in update_curr_dl()
1381 raw_spin_lock(&rt_rq->rt_runtime_lock); in update_curr_dl()
1384 * have our own CBS to keep us inline; only account when RT in update_curr_dl()
1388 rt_rq->rt_time += delta_exec; in update_curr_dl()
1389 raw_spin_unlock(&rt_rq->rt_runtime_lock); in update_curr_dl()
1407 if (!dl_task(p) || READ_ONCE(p->__state) == TASK_DEAD) { in inactive_task_timer()
1410 if (READ_ONCE(p->__state) == TASK_DEAD && dl_se->dl_non_contending) { in inactive_task_timer()
1411 sub_running_bw(&p->dl, dl_rq_of_se(&p->dl)); in inactive_task_timer()
1412 sub_rq_bw(&p->dl, dl_rq_of_se(&p->dl)); in inactive_task_timer()
1413 dl_se->dl_non_contending = 0; in inactive_task_timer()
1416 raw_spin_lock(&dl_b->lock); in inactive_task_timer()
1417 __dl_sub(dl_b, p->dl.dl_bw, dl_bw_cpus(task_cpu(p))); in inactive_task_timer()
1418 raw_spin_unlock(&dl_b->lock); in inactive_task_timer()
1423 if (dl_se->dl_non_contending == 0) in inactive_task_timer()
1426 sub_running_bw(dl_se, &rq->dl); in inactive_task_timer()
1427 dl_se->dl_non_contending = 0; in inactive_task_timer()
1437 struct hrtimer *timer = &dl_se->inactive_timer; in init_dl_inactive_task_timer()
1440 timer->function = inactive_task_timer; in init_dl_inactive_task_timer()
1452 if (dl_rq->earliest_dl.curr == 0 || in inc_dl_deadline()
1453 dl_time_before(deadline, dl_rq->earliest_dl.curr)) { in inc_dl_deadline()
1454 if (dl_rq->earliest_dl.curr == 0) in inc_dl_deadline()
1455 cpupri_set(&rq->rd->cpupri, rq->cpu, CPUPRI_HIGHER); in inc_dl_deadline()
1456 dl_rq->earliest_dl.curr = deadline; in inc_dl_deadline()
1457 cpudl_set(&rq->rd->cpudl, rq->cpu, deadline); in inc_dl_deadline()
1469 if (!dl_rq->dl_nr_running) { in dec_dl_deadline()
1470 dl_rq->earliest_dl.curr = 0; in dec_dl_deadline()
1471 dl_rq->earliest_dl.next = 0; in dec_dl_deadline()
1472 cpudl_clear(&rq->rd->cpudl, rq->cpu); in dec_dl_deadline()
1473 cpupri_set(&rq->rd->cpupri, rq->cpu, rq->rt.highest_prio.curr); in dec_dl_deadline()
1475 struct rb_node *leftmost = rb_first_cached(&dl_rq->root); in dec_dl_deadline()
1478 dl_rq->earliest_dl.curr = entry->deadline; in dec_dl_deadline()
1479 cpudl_set(&rq->rd->cpudl, rq->cpu, entry->deadline); in dec_dl_deadline()
1493 int prio = dl_task_of(dl_se)->prio; in inc_dl_tasks()
1494 u64 deadline = dl_se->deadline; in inc_dl_tasks()
1497 dl_rq->dl_nr_running++; in inc_dl_tasks()
1507 int prio = dl_task_of(dl_se)->prio; in dec_dl_tasks()
1510 WARN_ON(!dl_rq->dl_nr_running); in dec_dl_tasks()
1511 dl_rq->dl_nr_running--; in dec_dl_tasks()
1514 dec_dl_deadline(dl_rq, dl_se->deadline); in dec_dl_tasks()
1520 return dl_time_before(__node_2_dle(a)->deadline, __node_2_dle(b)->deadline); in __dl_less()
1526 return &dl_task_of(dl_se)->stats; in __schedstats_from_dl_se()
1588 state = READ_ONCE(p->__state); in update_stats_dequeue_dl()
1590 __schedstat_set(p->stats.sleep_start, in update_stats_dequeue_dl()
1594 __schedstat_set(p->stats.block_start, in update_stats_dequeue_dl()
1603 WARN_ON_ONCE(!RB_EMPTY_NODE(&dl_se->rb_node)); in __enqueue_dl_entity()
1605 rb_add_cached(&dl_se->rb_node, &dl_rq->root, __dl_less); in __enqueue_dl_entity()
1614 if (RB_EMPTY_NODE(&dl_se->rb_node)) in __dequeue_dl_entity()
1617 rb_erase_cached(&dl_se->rb_node, &dl_rq->root); in __dequeue_dl_entity()
1619 RB_CLEAR_NODE(&dl_se->rb_node); in __dequeue_dl_entity()
1633 * after the deadline but before the next period. in enqueue_dl_entity()
1635 * the replenishment timer will be set to the next period. in enqueue_dl_entity()
1637 if (!dl_se->dl_throttled && !dl_is_implicit(dl_se)) in enqueue_dl_entity()
1654 * task's state - in GRUB parlance, "inactive" vs "active contending"). in enqueue_dl_entity()
1659 if (dl_se->dl_throttled && !(flags & ENQUEUE_REPLENISH)) { in enqueue_dl_entity()
1678 dl_time_before(dl_se->deadline, in enqueue_dl_entity()
1701 * (p->state == TASK_DEAD). We can handle the two cases in the same in dequeue_dl_entity()
1712 if (is_dl_boosted(&p->dl)) { in enqueue_task_dl()
1723 * In this case, the boost overrides the throttle. in enqueue_task_dl()
1725 if (p->dl.dl_throttled) { in enqueue_task_dl()
1731 hrtimer_try_to_cancel(&p->dl.dl_timer); in enqueue_task_dl()
1732 p->dl.dl_throttled = 0; in enqueue_task_dl()
1734 } else if (!dl_prio(p->normal_prio)) { in enqueue_task_dl()
1742 * the throttle. in enqueue_task_dl()
1744 p->dl.dl_throttled = 0; in enqueue_task_dl()
1746 printk_deferred_once("sched: DL de-boosted task PID %d: REPLENISH flag missing\n", in enqueue_task_dl()
1753 update_stats_wait_start_dl(dl_rq_of_se(&p->dl), &p->dl); in enqueue_task_dl()
1755 if (p->on_rq == TASK_ON_RQ_MIGRATING) in enqueue_task_dl()
1758 enqueue_dl_entity(&p->dl, flags); in enqueue_task_dl()
1760 if (!task_current(rq, p) && !p->dl.dl_throttled && p->nr_cpus_allowed > 1) in enqueue_task_dl()
1766 update_stats_dequeue_dl(&rq->dl, &p->dl, flags); in __dequeue_task_dl()
1767 dequeue_dl_entity(&p->dl, flags); in __dequeue_task_dl()
1769 if (!p->dl.dl_throttled) in __dequeue_task_dl()
1777 if (p->on_rq == TASK_ON_RQ_MIGRATING) in dequeue_task_dl()
1784 * Yield task semantic for -deadline tasks is:
1801 rq->curr->dl.dl_yielded = 1; in yield_task_dl()
1818 return (!rq->dl.dl_nr_running || in dl_task_is_earliest_deadline()
1819 dl_time_before(p->dl.deadline, in dl_task_is_earliest_deadline()
1820 rq->dl.earliest_dl.curr)); in dl_task_is_earliest_deadline()
1838 curr = READ_ONCE(rq->curr); /* unlocked access */ in select_task_rq_dl()
1841 * If we are dealing with a -deadline task, we must in select_task_rq_dl()
1850 (curr->nr_cpus_allowed < 2 || in select_task_rq_dl()
1851 !dl_entity_preempt(&p->dl, &curr->dl)) && in select_task_rq_dl()
1852 p->nr_cpus_allowed > 1; in select_task_rq_dl()
1864 if (target != -1 && in select_task_rq_dl()
1879 if (READ_ONCE(p->__state) != TASK_WAKING) in migrate_task_rq_dl()
1884 * Since p->state == TASK_WAKING, set_task_cpu() has been called in migrate_task_rq_dl()
1885 * from try_to_wake_up(). Hence, p->pi_lock is locked, but in migrate_task_rq_dl()
1886 * rq->lock is not... So, lock it in migrate_task_rq_dl()
1889 if (p->dl.dl_non_contending) { in migrate_task_rq_dl()
1891 sub_running_bw(&p->dl, &rq->dl); in migrate_task_rq_dl()
1892 p->dl.dl_non_contending = 0; in migrate_task_rq_dl()
1900 if (hrtimer_try_to_cancel(&p->dl.inactive_timer) == 1) in migrate_task_rq_dl()
1903 sub_rq_bw(&p->dl, &rq->dl); in migrate_task_rq_dl()
1913 if (rq->curr->nr_cpus_allowed == 1 || in check_preempt_equal_dl()
1914 !cpudl_find(&rq->rd->cpudl, rq->curr, NULL)) in check_preempt_equal_dl()
1921 if (p->nr_cpus_allowed != 1 && in check_preempt_equal_dl()
1922 cpudl_find(&rq->rd->cpudl, p, NULL)) in check_preempt_equal_dl()
1930 if (!on_dl_rq(&p->dl) && need_pull_dl_task(rq, p)) { in balance_dl()
1933 * picked for load-balance and preemption/IRQs are still in balance_dl()
1947 * Only called when both the current and waking task are -deadline
1953 if (dl_entity_preempt(&p->dl, &rq->curr->dl)) { in wakeup_preempt_dl()
1961 * let us try to decide what's the best thing to do... in wakeup_preempt_dl()
1963 if ((p->dl.deadline == rq->curr->dl.deadline) && in wakeup_preempt_dl()
1964 !test_tsk_need_resched(rq->curr)) in wakeup_preempt_dl()
1972 hrtick_start(rq, p->dl.runtime); in start_hrtick_dl()
1982 struct sched_dl_entity *dl_se = &p->dl; in set_next_task_dl()
1983 struct dl_rq *dl_rq = &rq->dl; in set_next_task_dl()
1985 p->se.exec_start = rq_clock_task(rq); in set_next_task_dl()
1986 if (on_dl_rq(&p->dl)) in set_next_task_dl()
1998 if (rq->curr->sched_class != &dl_sched_class) in set_next_task_dl()
2006 struct rb_node *left = rb_first_cached(&dl_rq->root); in pick_next_dl_entity()
2017 struct dl_rq *dl_rq = &rq->dl; in pick_task_dl()
2043 struct sched_dl_entity *dl_se = &p->dl; in put_prev_task_dl()
2044 struct dl_rq *dl_rq = &rq->dl; in put_prev_task_dl()
2046 if (on_dl_rq(&p->dl)) in put_prev_task_dl()
2052 if (on_dl_rq(&p->dl) && p->nr_cpus_allowed > 1) in put_prev_task_dl()
2070 * Even when we have runtime, update_curr_dl() might have resulted in us in task_tick_dl()
2074 if (hrtick_enabled_dl(rq) && queued && p->dl.runtime > 0 && in task_tick_dl()
2075 is_leftmost(p, &rq->dl)) in task_tick_dl()
2095 cpumask_test_cpu(cpu, &p->cpus_mask)) in pick_dl_task()
2112 next_node = rb_first_cached(&rq->dl.pushable_dl_tasks_root); in pick_earliest_pushable_dl_task()
2139 return -1; in find_later_rq()
2141 if (task->nr_cpus_allowed == 1) in find_later_rq()
2142 return -1; in find_later_rq()
2148 if (!cpudl_find(&task_rq(task)->rd->cpudl, task, later_mask)) in find_later_rq()
2149 return -1; in find_later_rq()
2161 * guess, since it is most likely cache-hot there. in find_later_rq()
2170 this_cpu = -1; in find_later_rq()
2174 if (sd->flags & SD_WAKE_AFFINE) { in find_later_rq()
2181 if (this_cpu != -1 && in find_later_rq()
2207 if (this_cpu != -1) in find_later_rq()
2214 return -1; in find_later_rq()
2227 if ((cpu == -1) || (cpu == rq->cpu)) in find_lock_later_rq()
2245 !cpumask_test_cpu(later_rq->cpu, &task->cpus_mask) || in find_lock_later_rq()
2257 * If the rq we found has no -deadline task, or in find_lock_later_rq()
2279 p = __node_2_pdl(rb_first_cached(&rq->dl.pushable_dl_tasks_root)); in pick_next_pushable_dl_task()
2281 WARN_ON_ONCE(rq->cpu != task_cpu(p)); in pick_next_pushable_dl_task()
2283 WARN_ON_ONCE(p->nr_cpus_allowed <= 1); in pick_next_pushable_dl_task()
2292 * See if the non running -deadline tasks on this rq
2302 if (!rq->dl.overloaded) in push_dl_task()
2311 * If next_task preempts rq->curr, and rq->curr in push_dl_task()
2315 if (dl_task(rq->curr) && in push_dl_task()
2316 dl_time_before(next_task->dl.deadline, rq->curr->dl.deadline) && in push_dl_task()
2317 rq->curr->nr_cpus_allowed > 1) { in push_dl_task()
2325 if (WARN_ON(next_task == rq->curr)) in push_dl_task()
2338 * find_lock_later_rq releases rq->lock and it is in push_dl_task()
2360 set_task_cpu(next_task, later_rq->cpu); in push_dl_task()
2376 /* push_dl_task() will return true if it moved a -deadline task */ in push_dl_tasks()
2383 int this_cpu = this_rq->cpu, cpu; in pull_dl_task()
2398 for_each_cpu(cpu, this_rq->rd->dlo_mask) { in pull_dl_task()
2408 if (this_rq->dl.dl_nr_running && in pull_dl_task()
2409 dl_time_before(this_rq->dl.earliest_dl.curr, in pull_dl_task()
2410 src_rq->dl.earliest_dl.next)) in pull_dl_task()
2413 /* Might drop this_rq->lock */ in pull_dl_task()
2421 if (src_rq->dl.dl_nr_running <= 1) in pull_dl_task()
2428 * - it preempts our current (if there's one), in pull_dl_task()
2429 * - it will preempt the last one we pulled (if any). in pull_dl_task()
2431 if (p && dl_time_before(p->dl.deadline, dmin) && in pull_dl_task()
2433 WARN_ON(p == src_rq->curr); in pull_dl_task()
2440 if (dl_time_before(p->dl.deadline, in pull_dl_task()
2441 src_rq->curr->dl.deadline)) in pull_dl_task()
2450 dmin = p->dl.deadline; in pull_dl_task()
2462 stop_one_cpu_nowait(src_rq->cpu, push_cpu_stop, in pull_dl_task()
2463 push_task, &src_rq->push_work); in pull_dl_task()
2480 !test_tsk_need_resched(rq->curr) && in task_woken_dl()
2481 p->nr_cpus_allowed > 1 && in task_woken_dl()
2482 dl_task(rq->curr) && in task_woken_dl()
2483 (rq->curr->nr_cpus_allowed < 2 || in task_woken_dl()
2484 !dl_entity_preempt(&p->dl, &rq->curr->dl))) { in task_woken_dl()
2498 src_rd = rq->rd; in set_cpus_allowed_dl()
2502 * update. We already made space for us in the destination in set_cpus_allowed_dl()
2505 if (!cpumask_intersects(src_rd->span, ctx->new_mask)) { in set_cpus_allowed_dl()
2514 raw_spin_lock(&src_dl_b->lock); in set_cpus_allowed_dl()
2515 __dl_sub(src_dl_b, p->dl.dl_bw, dl_bw_cpus(task_cpu(p))); in set_cpus_allowed_dl()
2516 raw_spin_unlock(&src_dl_b->lock); in set_cpus_allowed_dl()
2522 /* Assumes rq->lock is held */
2525 if (rq->dl.overloaded) in rq_online_dl()
2528 cpudl_set_freecpu(&rq->rd->cpudl, rq->cpu); in rq_online_dl()
2529 if (rq->dl.dl_nr_running > 0) in rq_online_dl()
2530 cpudl_set(&rq->rd->cpudl, rq->cpu, rq->dl.earliest_dl.curr); in rq_online_dl()
2533 /* Assumes rq->lock is held */
2536 if (rq->dl.overloaded) in rq_offline_dl()
2539 cpudl_clear(&rq->rd->cpudl, rq->cpu); in rq_offline_dl()
2540 cpudl_clear_freecpu(&rq->rd->cpudl, rq->cpu); in rq_offline_dl()
2558 raw_spin_lock_irqsave(&p->pi_lock, rf.flags); in dl_add_task_root_domain()
2560 raw_spin_unlock_irqrestore(&p->pi_lock, rf.flags); in dl_add_task_root_domain()
2566 dl_b = &rq->rd->dl_bw; in dl_add_task_root_domain()
2567 raw_spin_lock(&dl_b->lock); in dl_add_task_root_domain()
2569 __dl_add(dl_b, p->dl.dl_bw, cpumask_weight(rq->rd->span)); in dl_add_task_root_domain()
2571 raw_spin_unlock(&dl_b->lock); in dl_add_task_root_domain()
2580 raw_spin_lock_irqsave(&rd->dl_bw.lock, flags); in dl_clear_root_domain()
2581 rd->dl_bw.total_bw = 0; in dl_clear_root_domain()
2582 raw_spin_unlock_irqrestore(&rd->dl_bw.lock, flags); in dl_clear_root_domain()
2590 * task_non_contending() can start the "inactive timer" (if the 0-lag in switched_from_dl()
2594 * SCHED_DEADLINE until the 0-lag time passes, inactive_task_timer() in switched_from_dl()
2597 if (task_on_rq_queued(p) && p->dl.dl_runtime) in switched_from_dl()
2598 task_non_contending(&p->dl); in switched_from_dl()
2613 if (p->dl.dl_non_contending) in switched_from_dl()
2614 sub_running_bw(&p->dl, &rq->dl); in switched_from_dl()
2615 sub_rq_bw(&p->dl, &rq->dl); in switched_from_dl()
2620 * at the 0-lag time, because the task could have been migrated in switched_from_dl()
2623 if (p->dl.dl_non_contending) in switched_from_dl()
2624 p->dl.dl_non_contending = 0; in switched_from_dl()
2627 * Since this might be the only -deadline task on the rq, in switched_from_dl()
2631 if (!task_on_rq_queued(p) || rq->dl.dl_nr_running) in switched_from_dl()
2638 * When switching to -deadline, we may overload the rq, then
2643 if (hrtimer_try_to_cancel(&p->dl.inactive_timer) == 1) in switched_to_dl()
2654 add_rq_bw(&p->dl, &rq->dl); in switched_to_dl()
2659 if (rq->curr != p) { in switched_to_dl()
2661 if (p->nr_cpus_allowed > 1 && rq->dl.overloaded) in switched_to_dl()
2664 if (dl_task(rq->curr)) in switched_to_dl()
2674 * If the scheduling parameters of a -deadline task changed,
2690 if (!rq->dl.overloaded) in prio_changed_dl()
2699 if (dl_time_before(rq->dl.earliest_dl.curr, p->dl.deadline)) in prio_changed_dl()
2708 if (!dl_task(rq->curr) || in prio_changed_dl()
2709 dl_time_before(p->dl.deadline, rq->curr->dl.deadline)) in prio_changed_dl()
2724 return p->dl.dl_throttled; in task_is_throttled_dl()
2771 u64 period = global_rt_period(); in sched_dl_global_validate() local
2772 u64 new_bw = to_ratio(period, runtime); in sched_dl_global_validate()
2792 raw_spin_lock_irqsave(&dl_b->lock, flags); in sched_dl_global_validate()
2793 if (new_bw * cpus < dl_b->total_bw) in sched_dl_global_validate()
2794 ret = -EBUSY; in sched_dl_global_validate()
2795 raw_spin_unlock_irqrestore(&dl_b->lock, flags); in sched_dl_global_validate()
2810 dl_rq->bw_ratio = 1 << RATIO_SHIFT; in init_dl_rq_bw_ratio()
2811 dl_rq->max_bw = dl_rq->extra_bw = 1 << BW_SHIFT; in init_dl_rq_bw_ratio()
2813 dl_rq->bw_ratio = to_ratio(global_rt_runtime(), in init_dl_rq_bw_ratio()
2814 global_rt_period()) >> (BW_SHIFT - RATIO_SHIFT); in init_dl_rq_bw_ratio()
2815 dl_rq->max_bw = dl_rq->extra_bw = in init_dl_rq_bw_ratio()
2822 u64 new_bw = -1; in sched_dl_do_global()
2841 raw_spin_lock_irqsave(&dl_b->lock, flags); in sched_dl_do_global()
2842 dl_b->bw = new_bw; in sched_dl_do_global()
2843 raw_spin_unlock_irqrestore(&dl_b->lock, flags); in sched_dl_do_global()
2846 init_dl_rq_bw_ratio(&cpu_rq(cpu)->dl); in sched_dl_do_global()
2856 * This function is called while holding p's rq->lock.
2861 u64 period = attr->sched_period ?: attr->sched_deadline; in sched_dl_overflow() local
2862 u64 runtime = attr->sched_runtime; in sched_dl_overflow()
2863 u64 new_bw = dl_policy(policy) ? to_ratio(period, runtime) : 0; in sched_dl_overflow()
2864 int cpus, err = -1, cpu = task_cpu(p); in sched_dl_overflow()
2868 if (attr->sched_flags & SCHED_FLAG_SUGOV) in sched_dl_overflow()
2872 if (new_bw == p->dl.dl_bw && task_has_dl_policy(p)) in sched_dl_overflow()
2876 * Either if a task, enters, leave, or stays -deadline but changes in sched_dl_overflow()
2880 raw_spin_lock(&dl_b->lock); in sched_dl_overflow()
2886 if (hrtimer_active(&p->dl.inactive_timer)) in sched_dl_overflow()
2887 __dl_sub(dl_b, p->dl.dl_bw, cpus); in sched_dl_overflow()
2891 !__dl_overflow(dl_b, cap, p->dl.dl_bw, new_bw)) { in sched_dl_overflow()
2895 * utilization change until the task's 0-lag point. in sched_dl_overflow()
2899 __dl_sub(dl_b, p->dl.dl_bw, cpus); in sched_dl_overflow()
2907 * (0-lag) time. in sched_dl_overflow()
2911 raw_spin_unlock(&dl_b->lock); in sched_dl_overflow()
2926 struct sched_dl_entity *dl_se = &p->dl; in __setparam_dl()
2928 dl_se->dl_runtime = attr->sched_runtime; in __setparam_dl()
2929 dl_se->dl_deadline = attr->sched_deadline; in __setparam_dl()
2930 dl_se->dl_period = attr->sched_period ?: dl_se->dl_deadline; in __setparam_dl()
2931 dl_se->flags = attr->sched_flags & SCHED_DL_FLAGS; in __setparam_dl()
2932 dl_se->dl_bw = to_ratio(dl_se->dl_period, dl_se->dl_runtime); in __setparam_dl()
2933 dl_se->dl_density = to_ratio(dl_se->dl_deadline, dl_se->dl_runtime); in __setparam_dl()
2938 struct sched_dl_entity *dl_se = &p->dl; in __getparam_dl()
2940 attr->sched_priority = p->rt_priority; in __getparam_dl()
2941 attr->sched_runtime = dl_se->dl_runtime; in __getparam_dl()
2942 attr->sched_deadline = dl_se->dl_deadline; in __getparam_dl()
2943 attr->sched_period = dl_se->dl_period; in __getparam_dl()
2944 attr->sched_flags &= ~SCHED_DL_FLAGS; in __getparam_dl()
2945 attr->sched_flags |= dl_se->flags; in __getparam_dl()
2949 * This function validates the new parameters of a -deadline task.
2951 * than the runtime, as well as the period of being zero or
2953 * user parameters are above the internal resolution of 1us (we
2960 u64 period, max, min; in __checkparam_dl() local
2963 if (attr->sched_flags & SCHED_FLAG_SUGOV) in __checkparam_dl()
2967 if (attr->sched_deadline == 0) in __checkparam_dl()
2974 if (attr->sched_runtime < (1ULL << DL_SCALE)) in __checkparam_dl()
2978 * Since we use the MSB for wrap-around and sign issues, make in __checkparam_dl()
2979 * sure it's not set (mind that period can be equal to zero). in __checkparam_dl()
2981 if (attr->sched_deadline & (1ULL << 63) || in __checkparam_dl()
2982 attr->sched_period & (1ULL << 63)) in __checkparam_dl()
2985 period = attr->sched_period; in __checkparam_dl()
2986 if (!period) in __checkparam_dl()
2987 period = attr->sched_deadline; in __checkparam_dl()
2989 /* runtime <= deadline <= period (if period != 0) */ in __checkparam_dl()
2990 if (period < attr->sched_deadline || in __checkparam_dl()
2991 attr->sched_deadline < attr->sched_runtime) in __checkparam_dl()
2997 if (period < min || period > max) in __checkparam_dl()
3008 dl_se->dl_runtime = 0; in __dl_clear_params()
3009 dl_se->dl_deadline = 0; in __dl_clear_params()
3010 dl_se->dl_period = 0; in __dl_clear_params()
3011 dl_se->flags = 0; in __dl_clear_params()
3012 dl_se->dl_bw = 0; in __dl_clear_params()
3013 dl_se->dl_density = 0; in __dl_clear_params()
3015 dl_se->dl_throttled = 0; in __dl_clear_params()
3016 dl_se->dl_yielded = 0; in __dl_clear_params()
3017 dl_se->dl_non_contending = 0; in __dl_clear_params()
3018 dl_se->dl_overrun = 0; in __dl_clear_params()
3021 dl_se->pi_se = dl_se; in __dl_clear_params()
3027 RB_CLEAR_NODE(&dl_se->rb_node); in init_dl_entity()
3035 struct sched_dl_entity *dl_se = &p->dl; in dl_param_changed()
3037 if (dl_se->dl_runtime != attr->sched_runtime || in dl_param_changed()
3038 dl_se->dl_deadline != attr->sched_deadline || in dl_param_changed()
3039 dl_se->dl_period != attr->sched_period || in dl_param_changed()
3040 dl_se->flags != (attr->sched_flags & SCHED_DL_FLAGS)) in dl_param_changed()
3057 raw_spin_lock_irqsave(&cur_dl_b->lock, flags); in dl_cpuset_cpumask_can_shrink()
3060 raw_spin_unlock_irqrestore(&cur_dl_b->lock, flags); in dl_cpuset_cpumask_can_shrink()
3080 raw_spin_lock_irqsave(&dl_b->lock, flags); in dl_bw_manage()
3100 raw_spin_unlock_irqrestore(&dl_b->lock, flags); in dl_bw_manage()
3103 return overflow ? -EBUSY : 0; in dl_bw_manage()
3125 print_dl_rq(m, cpu, &cpu_rq(cpu)->dl); in print_dl_stats()