Lines Matching +full:timer +full:- +full:cannot +full:- +full:wake +full:- +full:cpu
1 // SPDX-License-Identifier: GPL-2.0
24 * guard against timer DoS.
58 return dl_se->dl_server; in dl_server()
74 struct rq *rq = dl_se->rq; in rq_of_dl_se()
84 return &rq_of_dl_se(dl_se)->dl; in dl_rq_of_se()
89 return !RB_EMPTY_NODE(&dl_se->rb_node); in on_dl_rq()
95 return dl_se->pi_se; in pi_of()
119 return &cpu_rq(i)->rd->dl_bw; in dl_bw_of()
124 struct root_domain *rd = cpu_rq(i)->rd; in dl_bw_cpus()
130 if (cpumask_subset(rd->span, cpu_active_mask)) in dl_bw_cpus()
131 return cpumask_weight(rd->span); in dl_bw_cpus()
135 for_each_cpu_and(i, rd->span, cpu_active_mask) in dl_bw_cpus()
153 * XXX Fix: If 'rq->rd == def_root_domain' perform AC against capacity
154 * of the CPU the task is running on rather rd's \Sum CPU capacity.
165 return __dl_bw_capacity(cpu_rq(i)->rd->span); in dl_bw_capacity()
169 bool dl_bw_visited(int cpu, u64 cookie) in dl_bw_visited() argument
171 struct root_domain *rd = cpu_rq(cpu)->rd; in dl_bw_visited()
173 if (rd->visit_cookie == cookie) in dl_bw_visited()
176 rd->visit_cookie = cookie; in dl_bw_visited()
188 for_each_cpu_and(i, rd->span, cpu_active_mask) { in __dl_update()
191 rq->dl.extra_bw += bw; in __dl_update()
197 return &cpu_rq(i)->dl.dl_bw; in dl_bw_of()
210 bool dl_bw_visited(int cpu, u64 cookie) in dl_bw_visited() argument
220 dl->extra_bw += bw; in __dl_update()
227 dl_b->total_bw -= tsk_bw; in __dl_sub()
234 dl_b->total_bw += tsk_bw; in __dl_add()
235 __dl_update(dl_b, -((s32)tsk_bw / cpus)); in __dl_add()
241 return dl_b->bw != -1 && in __dl_overflow()
242 cap_scale(dl_b->bw, cap) < dl_b->total_bw - old_bw + new_bw; in __dl_overflow()
248 u64 old = dl_rq->running_bw; in __add_running_bw()
251 dl_rq->running_bw += dl_bw; in __add_running_bw()
252 SCHED_WARN_ON(dl_rq->running_bw < old); /* overflow */ in __add_running_bw()
253 SCHED_WARN_ON(dl_rq->running_bw > dl_rq->this_bw); in __add_running_bw()
261 u64 old = dl_rq->running_bw; in __sub_running_bw()
264 dl_rq->running_bw -= dl_bw; in __sub_running_bw()
265 SCHED_WARN_ON(dl_rq->running_bw > old); /* underflow */ in __sub_running_bw()
266 if (dl_rq->running_bw > old) in __sub_running_bw()
267 dl_rq->running_bw = 0; in __sub_running_bw()
275 u64 old = dl_rq->this_bw; in __add_rq_bw()
278 dl_rq->this_bw += dl_bw; in __add_rq_bw()
279 SCHED_WARN_ON(dl_rq->this_bw < old); /* overflow */ in __add_rq_bw()
285 u64 old = dl_rq->this_bw; in __sub_rq_bw()
288 dl_rq->this_bw -= dl_bw; in __sub_rq_bw()
289 SCHED_WARN_ON(dl_rq->this_bw > old); /* underflow */ in __sub_rq_bw()
290 if (dl_rq->this_bw > old) in __sub_rq_bw()
291 dl_rq->this_bw = 0; in __sub_rq_bw()
292 SCHED_WARN_ON(dl_rq->running_bw > dl_rq->this_bw); in __sub_rq_bw()
299 __add_rq_bw(dl_se->dl_bw, dl_rq); in add_rq_bw()
306 __sub_rq_bw(dl_se->dl_bw, dl_rq); in sub_rq_bw()
313 __add_running_bw(dl_se->dl_bw, dl_rq); in add_running_bw()
320 __sub_running_bw(dl_se->dl_bw, dl_rq); in sub_running_bw()
325 if (dl_se->dl_non_contending) { in dl_rq_change_utilization()
326 sub_running_bw(dl_se, &rq->dl); in dl_rq_change_utilization()
327 dl_se->dl_non_contending = 0; in dl_rq_change_utilization()
330 * If the timer handler is currently running and the in dl_rq_change_utilization()
331 * timer cannot be canceled, inactive_task_timer() in dl_rq_change_utilization()
336 if (hrtimer_try_to_cancel(&dl_se->inactive_timer) == 1) { in dl_rq_change_utilization()
341 __sub_rq_bw(dl_se->dl_bw, &rq->dl); in dl_rq_change_utilization()
342 __add_rq_bw(new_bw, &rq->dl); in dl_rq_change_utilization()
346 void cancel_dl_timer(struct sched_dl_entity *dl_se, struct hrtimer *timer) in cancel_dl_timer() argument
349 * If the timer callback was running (hrtimer_try_to_cancel == -1), in cancel_dl_timer()
352 if (hrtimer_try_to_cancel(timer) == 1 && !dl_server(dl_se)) in cancel_dl_timer()
359 cancel_dl_timer(dl_se, &dl_se->dl_timer); in cancel_replenish_timer()
365 cancel_dl_timer(dl_se, &dl_se->inactive_timer); in cancel_inactive_timer()
370 WARN_ON_ONCE(p->dl.flags & SCHED_FLAG_SUGOV); in dl_change_utilization()
375 dl_rq_change_utilization(task_rq(p), &p->dl, new_bw); in dl_change_utilization()
381 * The utilization of a task cannot be immediately removed from
383 * Instead, we have to wait for the so called "0-lag time".
385 * If a task blocks before the "0-lag time", a timer (the inactive
386 * timer) is armed, and running_bw is decreased when the timer
389 * If the task wakes up again before the inactive timer fires,
390 * the timer is canceled, whereas if the task wakes up after the
391 * inactive timer fired (and running_bw has been decreased) the
394 * is used to avoid race conditions between the inactive timer handler
400 * "ACTIVE non contending" task is a blocked task for which the "0-lag time"
401 * has not passed yet. An "INACTIVE" task is a task for which the "0-lag"
403 * +------------------+
405 * +------------------>+ contending |
407 * | +----+------+------+
410 * +--------+-------+ | |
411 * | | t >= 0-lag | | wakeup
412 * | INACTIVE |<---------------+ |
414 * +--------+-------+ | |
416 * | t < 0-lag | |
419 * | +----+------+------+
421 * +-------------------+ |
422 * inactive timer | non contending |
423 * fired +------------------+
426 * blocks, and checks if the 0-lag time already passed or
428 * in the second case, it arms the inactive timer).
436 struct hrtimer *timer = &dl_se->inactive_timer; in task_non_contending() local
438 struct dl_rq *dl_rq = &rq->dl; in task_non_contending()
442 * If this is a non-deadline task that has been boosted, in task_non_contending()
445 if (dl_se->dl_runtime == 0) in task_non_contending()
451 WARN_ON(dl_se->dl_non_contending); in task_non_contending()
453 zerolag_time = dl_se->deadline - in task_non_contending()
454 div64_long((dl_se->runtime * dl_se->dl_period), in task_non_contending()
455 dl_se->dl_runtime); in task_non_contending()
458 * Using relative times instead of the absolute "0-lag time" in task_non_contending()
461 zerolag_time -= rq_clock(rq); in task_non_contending()
464 * If the "0-lag time" already passed, decrease the active in task_non_contending()
465 * utilization now, instead of starting a timer in task_non_contending()
467 if ((zerolag_time < 0) || hrtimer_active(&dl_se->inactive_timer)) { in task_non_contending()
476 if (!dl_task(p) || READ_ONCE(p->__state) == TASK_DEAD) { in task_non_contending()
479 if (READ_ONCE(p->__state) == TASK_DEAD) in task_non_contending()
480 sub_rq_bw(dl_se, &rq->dl); in task_non_contending()
481 raw_spin_lock(&dl_b->lock); in task_non_contending()
482 __dl_sub(dl_b, dl_se->dl_bw, dl_bw_cpus(task_cpu(p))); in task_non_contending()
483 raw_spin_unlock(&dl_b->lock); in task_non_contending()
491 dl_se->dl_non_contending = 1; in task_non_contending()
495 hrtimer_start(timer, ns_to_ktime(zerolag_time), HRTIMER_MODE_REL_HARD); in task_non_contending()
503 * If this is a non-deadline task that has been boosted, in task_contending()
506 if (dl_se->dl_runtime == 0) in task_contending()
512 if (dl_se->dl_non_contending) { in task_contending()
513 dl_se->dl_non_contending = 0; in task_contending()
515 * If the timer handler is currently running and the in task_contending()
516 * timer cannot be canceled, inactive_task_timer() in task_contending()
527 * when the "inactive timer" fired). in task_contending()
536 return rb_first_cached(&dl_rq->root) == &dl_se->rb_node; in is_leftmost()
543 raw_spin_lock_init(&dl_b->lock); in init_dl_bw()
545 dl_b->bw = -1; in init_dl_bw()
547 dl_b->bw = to_ratio(global_rt_period(), global_rt_runtime()); in init_dl_bw()
548 dl_b->total_bw = 0; in init_dl_bw()
553 dl_rq->root = RB_ROOT_CACHED; in init_dl_rq()
556 /* zero means no -deadline tasks */ in init_dl_rq()
557 dl_rq->earliest_dl.curr = dl_rq->earliest_dl.next = 0; in init_dl_rq()
559 dl_rq->overloaded = 0; in init_dl_rq()
560 dl_rq->pushable_dl_tasks_root = RB_ROOT_CACHED; in init_dl_rq()
562 init_dl_bw(&dl_rq->dl_bw); in init_dl_rq()
565 dl_rq->running_bw = 0; in init_dl_rq()
566 dl_rq->this_bw = 0; in init_dl_rq()
574 return atomic_read(&rq->rd->dlo_count); in dl_overloaded()
579 if (!rq->online) in dl_set_overload()
582 cpumask_set_cpu(rq->cpu, rq->rd->dlo_mask); in dl_set_overload()
590 atomic_inc(&rq->rd->dlo_count); in dl_set_overload()
595 if (!rq->online) in dl_clear_overload()
598 atomic_dec(&rq->rd->dlo_count); in dl_clear_overload()
599 cpumask_clear_cpu(rq->cpu, rq->rd->dlo_mask); in dl_clear_overload()
607 return dl_entity_preempt(&__node_2_pdl(a)->dl, &__node_2_pdl(b)->dl); in __pushable_less()
612 return !RB_EMPTY_ROOT(&rq->dl.pushable_dl_tasks_root.rb_root); in has_pushable_dl_tasks()
616 * The list of pushable -deadline task is not a plist, like in
617 * sched_rt.c, it is an rb-tree with tasks ordered by deadline.
623 WARN_ON_ONCE(!RB_EMPTY_NODE(&p->pushable_dl_tasks)); in enqueue_pushable_dl_task()
625 leftmost = rb_add_cached(&p->pushable_dl_tasks, in enqueue_pushable_dl_task()
626 &rq->dl.pushable_dl_tasks_root, in enqueue_pushable_dl_task()
629 rq->dl.earliest_dl.next = p->dl.deadline; in enqueue_pushable_dl_task()
631 if (!rq->dl.overloaded) { in enqueue_pushable_dl_task()
633 rq->dl.overloaded = 1; in enqueue_pushable_dl_task()
639 struct dl_rq *dl_rq = &rq->dl; in dequeue_pushable_dl_task()
640 struct rb_root_cached *root = &dl_rq->pushable_dl_tasks_root; in dequeue_pushable_dl_task()
643 if (RB_EMPTY_NODE(&p->pushable_dl_tasks)) in dequeue_pushable_dl_task()
646 leftmost = rb_erase_cached(&p->pushable_dl_tasks, root); in dequeue_pushable_dl_task()
648 dl_rq->earliest_dl.next = __node_2_pdl(leftmost)->dl.deadline; in dequeue_pushable_dl_task()
650 RB_CLEAR_NODE(&p->pushable_dl_tasks); in dequeue_pushable_dl_task()
652 if (!has_pushable_dl_tasks(rq) && rq->dl.overloaded) { in dequeue_pushable_dl_task()
654 rq->dl.overloaded = 0; in dequeue_pushable_dl_task()
662 return rq->online && dl_task(prev); in need_pull_dl_task()
676 queue_balance_callback(rq, &per_cpu(dl_push_head, rq->cpu), push_dl_tasks); in deadline_queue_push_tasks()
681 queue_balance_callback(rq, &per_cpu(dl_pull_head, rq->cpu), pull_dl_task); in deadline_queue_pull_task()
693 int cpu; in dl_task_offline_migration() local
696 * If we cannot preempt any rq, fall back to pick any in dl_task_offline_migration()
697 * online CPU: in dl_task_offline_migration()
699 cpu = cpumask_any_and(cpu_active_mask, p->cpus_ptr); in dl_task_offline_migration()
700 if (cpu >= nr_cpu_ids) { in dl_task_offline_migration()
702 * Failed to find any suitable CPU. in dl_task_offline_migration()
712 cpu = cpumask_any(cpu_active_mask); in dl_task_offline_migration()
714 later_rq = cpu_rq(cpu); in dl_task_offline_migration()
718 if (p->dl.dl_non_contending || p->dl.dl_throttled) { in dl_task_offline_migration()
720 * Inactive timer is armed (or callback is running, but in dl_task_offline_migration()
725 sub_running_bw(&p->dl, &rq->dl); in dl_task_offline_migration()
726 sub_rq_bw(&p->dl, &rq->dl); in dl_task_offline_migration()
728 add_rq_bw(&p->dl, &later_rq->dl); in dl_task_offline_migration()
729 add_running_bw(&p->dl, &later_rq->dl); in dl_task_offline_migration()
731 sub_rq_bw(&p->dl, &rq->dl); in dl_task_offline_migration()
732 add_rq_bw(&p->dl, &later_rq->dl); in dl_task_offline_migration()
740 dl_b = &rq->rd->dl_bw; in dl_task_offline_migration()
741 raw_spin_lock(&dl_b->lock); in dl_task_offline_migration()
742 __dl_sub(dl_b, p->dl.dl_bw, cpumask_weight(rq->rd->span)); in dl_task_offline_migration()
743 raw_spin_unlock(&dl_b->lock); in dl_task_offline_migration()
745 dl_b = &later_rq->rd->dl_bw; in dl_task_offline_migration()
746 raw_spin_lock(&dl_b->lock); in dl_task_offline_migration()
747 __dl_add(dl_b, p->dl.dl_bw, cpumask_weight(later_rq->rd->span)); in dl_task_offline_migration()
748 raw_spin_unlock(&dl_b->lock); in dl_task_offline_migration()
750 set_task_cpu(p, later_rq->cpu); in dl_task_offline_migration()
796 /* for non-boosted task, pi_of(dl_se) == dl_se */ in replenish_dl_new_period()
797 dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline; in replenish_dl_new_period()
798 dl_se->runtime = pi_of(dl_se)->dl_runtime; in replenish_dl_new_period()
804 if (dl_se->dl_defer && !dl_se->dl_defer_running) { in replenish_dl_new_period()
805 dl_se->dl_throttled = 1; in replenish_dl_new_period()
806 dl_se->dl_defer_armed = 1; in replenish_dl_new_period()
813 * - the absolute deadline of the entity has to be placed at
815 * - the runtime of the entity has to be set to the maximum value.
817 * The capability of specifying such event is useful whenever a -deadline
828 WARN_ON(dl_time_before(rq_clock(rq), dl_se->deadline)); in setup_new_dl_entity()
831 * We are racing with the deadline timer. So, do nothing because in setup_new_dl_entity()
832 * the deadline timer handler will take care of properly recharging in setup_new_dl_entity()
835 if (dl_se->dl_throttled) in setup_new_dl_entity()
872 WARN_ON_ONCE(pi_of(dl_se)->dl_runtime <= 0); in replenish_dl_entity()
875 * This could be the case for a !-dl task that is boosted. in replenish_dl_entity()
884 if (dl_se->dl_deadline == 0 || in replenish_dl_entity()
885 (dl_se->dl_defer_armed && dl_entity_overflow(dl_se, rq_clock(rq)))) { in replenish_dl_entity()
886 dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline; in replenish_dl_entity()
887 dl_se->runtime = pi_of(dl_se)->dl_runtime; in replenish_dl_entity()
890 if (dl_se->dl_yielded && dl_se->runtime > 0) in replenish_dl_entity()
891 dl_se->runtime = 0; in replenish_dl_entity()
899 while (dl_se->runtime <= 0) { in replenish_dl_entity()
900 dl_se->deadline += pi_of(dl_se)->dl_period; in replenish_dl_entity()
901 dl_se->runtime += pi_of(dl_se)->dl_runtime; in replenish_dl_entity()
906 * the future" with respect to rq->clock. If it's in replenish_dl_entity()
913 if (dl_time_before(dl_se->deadline, rq_clock(rq))) { in replenish_dl_entity()
918 if (dl_se->dl_yielded) in replenish_dl_entity()
919 dl_se->dl_yielded = 0; in replenish_dl_entity()
920 if (dl_se->dl_throttled) in replenish_dl_entity()
921 dl_se->dl_throttled = 0; in replenish_dl_entity()
927 if (dl_se->dl_defer_armed) { in replenish_dl_entity()
928 dl_se->dl_defer_armed = 0; in replenish_dl_entity()
935 * and arm the defer timer. in replenish_dl_entity()
937 if (dl_se->dl_defer && !dl_se->dl_defer_running && in replenish_dl_entity()
938 dl_time_before(rq_clock(dl_se->rq), dl_se->deadline - dl_se->runtime)) { in replenish_dl_entity()
939 if (!is_dl_boosted(dl_se) && dl_se->server_has_tasks(dl_se)) { in replenish_dl_entity()
942 * Set dl_se->dl_defer_armed and dl_throttled variables to in replenish_dl_entity()
946 dl_se->dl_defer_armed = 1; in replenish_dl_entity()
947 dl_se->dl_throttled = 1; in replenish_dl_entity()
950 * If for whatever reason (delays), a previous timer was in replenish_dl_entity()
954 hrtimer_try_to_cancel(&dl_se->dl_timer); in replenish_dl_entity()
955 dl_se->dl_defer_armed = 0; in replenish_dl_entity()
956 dl_se->dl_throttled = 0; in replenish_dl_entity()
963 * Here we check if --at time t-- an entity (which is probably being
974 * Documentation/scheduler/sched-deadline.rst for more information).
978 * runtime / (deadline - t) > dl_runtime / dl_deadline ,
999 * and (deadline - t), since t is rq->clock, is the time left in dl_entity_overflow()
1008 left = (pi_of(dl_se)->dl_deadline >> DL_SCALE) * (dl_se->runtime >> DL_SCALE); in dl_entity_overflow()
1009 right = ((dl_se->deadline - t) >> DL_SCALE) * in dl_entity_overflow()
1010 (pi_of(dl_se)->dl_runtime >> DL_SCALE); in dl_entity_overflow()
1016 * Revised wakeup rule [1]: For self-suspending tasks, rather then
1017 * re-initializing task's runtime and deadline, the revised wakeup
1022 * runtime / (deadline - t) > dl_runtime / dl_deadline
1025 * runtime = (dl_runtime / dl_deadline) * (deadline - t)
1031 * bandwidth server revisited. SIGBED Rev. 11, 4 (January 2015), 19-24.
1036 u64 laxity = dl_se->deadline - rq_clock(rq); in update_dl_revised_wakeup()
1044 WARN_ON(dl_time_before(dl_se->deadline, rq_clock(rq))); in update_dl_revised_wakeup()
1046 dl_se->runtime = (dl_se->dl_density * laxity) >> BW_SHIFT; in update_dl_revised_wakeup()
1062 return dl_se->dl_deadline == dl_se->dl_period; in dl_is_implicit()
1067 * might need to be updated. This is done by a CBS wake up rule. There are two
1099 if (dl_time_before(dl_se->deadline, rq_clock(rq)) || in update_dl_entity()
1103 !dl_time_before(dl_se->deadline, rq_clock(rq)) && in update_dl_entity()
1110 } else if (dl_server(dl_se) && dl_se->dl_defer) { in update_dl_entity()
1115 if (!dl_se->dl_defer_running) { in update_dl_entity()
1116 dl_se->dl_defer_armed = 1; in update_dl_entity()
1117 dl_se->dl_throttled = 1; in update_dl_entity()
1124 return dl_se->deadline - dl_se->dl_deadline + dl_se->dl_period; in dl_next_period()
1130 * set the bandwidth replenishment timer to the replenishment instant
1133 * Notice that it is important for the caller to know if the timer
1139 struct hrtimer *timer = &dl_se->dl_timer; in start_dl_timer() local
1148 * We want the timer to fire at the deadline, but considering in start_dl_timer()
1149 * that it is actually coming from rq->clock and not from in start_dl_timer()
1152 * The deferred reservation will have its timer set to in start_dl_timer()
1153 * (deadline - runtime). At that point, the CBS rule will decide in start_dl_timer()
1158 if (dl_se->dl_defer_armed) { in start_dl_timer()
1159 WARN_ON_ONCE(!dl_se->dl_throttled); in start_dl_timer()
1160 act = ns_to_ktime(dl_se->deadline - dl_se->runtime); in start_dl_timer()
1162 /* act = deadline - rel-deadline + period */ in start_dl_timer()
1166 now = hrtimer_cb_get_time(timer); in start_dl_timer()
1167 delta = ktime_to_ns(now) - rq_clock(rq); in start_dl_timer()
1173 * start the timer in the past! in start_dl_timer()
1183 * harmless because we're holding task_rq()->lock, therefore the timer in start_dl_timer()
1187 if (!hrtimer_is_queued(timer)) { in start_dl_timer()
1190 hrtimer_start(timer, act, HRTIMER_MODE_ABS_HARD); in start_dl_timer()
1205 * Nothing relies on rq->lock after this, so its safe to drop in __push_dl_task()
1206 * rq->lock. in __push_dl_task()
1215 /* a defer timer will not be reset if the runtime consumed was < dl_server_min_res */
1218 static enum hrtimer_restart dl_server_timer(struct hrtimer *timer, struct sched_dl_entity *dl_se) in dl_server_timer() argument
1226 if (!dl_se->dl_throttled || !dl_se->dl_runtime) in dl_server_timer()
1232 if (!dl_se->dl_runtime) in dl_server_timer()
1235 if (!dl_se->server_has_tasks(dl_se)) { in dl_server_timer()
1240 if (dl_se->dl_defer_armed) { in dl_server_timer()
1243 * If so, it is possible to push the defer timer for this amount in dl_server_timer()
1245 * forwarding the timer for a too small amount of time. in dl_server_timer()
1247 if (dl_time_before(rq_clock(dl_se->rq), in dl_server_timer()
1248 (dl_se->deadline - dl_se->runtime - dl_server_min_res))) { in dl_server_timer()
1250 /* reset the defer timer */ in dl_server_timer()
1251 fw = dl_se->deadline - rq_clock(dl_se->rq) - dl_se->runtime; in dl_server_timer()
1253 hrtimer_forward_now(timer, ns_to_ktime(fw)); in dl_server_timer()
1257 dl_se->dl_defer_running = 1; in dl_server_timer()
1262 if (!dl_task(dl_se->rq->curr) || dl_entity_preempt(dl_se, &dl_se->rq->curr->dl)) in dl_server_timer()
1272 * This is the bandwidth enforcement timer callback. If here, we know
1273 * a task is not on its dl_rq, since the fact that the timer was running
1284 static enum hrtimer_restart dl_task_timer(struct hrtimer *timer) in dl_task_timer() argument
1286 struct sched_dl_entity *dl_se = container_of(timer, in dl_task_timer()
1294 return dl_server_timer(timer, dl_se); in dl_task_timer()
1314 * Spurious timer due to start_dl_timer() race; or we already received in dl_task_timer()
1317 if (!dl_se->dl_throttled) in dl_task_timer()
1324 * If the throttle happened during sched-out; like: in dl_task_timer()
1332 * prev->on_rq = 0; in dl_task_timer()
1335 * but do not enqueue -- wait for our wakeup to do that. in dl_task_timer()
1343 if (unlikely(!rq->online)) { in dl_task_timer()
1362 if (dl_task(rq->donor)) in dl_task_timer()
1383 struct hrtimer *timer = &dl_se->dl_timer; in init_dl_task_timer() local
1385 hrtimer_init(timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL_HARD); in init_dl_task_timer()
1386 timer->function = dl_task_timer; in init_dl_task_timer()
1392 * cannot use the runtime, and so it replenishes the task. This rule
1404 * task and set the replenishing timer to the begin of the next period,
1411 if (dl_time_before(dl_se->deadline, rq_clock(rq)) && in dl_check_constrained_dl()
1415 dl_se->dl_throttled = 1; in dl_check_constrained_dl()
1416 if (dl_se->runtime > 0) in dl_check_constrained_dl()
1417 dl_se->runtime = 0; in dl_check_constrained_dl()
1424 return (dl_se->runtime <= 0); in dl_runtime_exceeded()
1429 * GRUB reclaiming algorithm, the runtime is not decreased as "dq = -dt",
1430 * but as "dq = -(max{u, (Umax - Uinact - Uextra)} / Umax) dt",
1432 * utilization, Uinact is the (per-runqueue) inactive utilization, computed
1436 * Since rq->dl.running_bw and rq->dl.this_bw contain utilizations multiplied
1438 * Since rq->dl.bw_ratio contains 1 / Umax multiplied by 2^RATIO_SHIFT, dl_bw
1439 * is multiplied by rq->dl.bw_ratio and shifted right by RATIO_SHIFT.
1441 * larger than 2^(64 - 20 - 8), which is more than 64 seconds. So, overflow is
1447 u64 u_inact = rq->dl.this_bw - rq->dl.running_bw; /* Utot - Uact */ in grub_reclaim()
1450 * Instead of computing max{u, (u_max - u_inact - u_extra)}, we in grub_reclaim()
1451 * compare u_inact + u_extra with u_max - u, because u_inact + u_extra in grub_reclaim()
1452 * can be larger than u_max. So, u_max - u_inact - u_extra would be in grub_reclaim()
1455 if (u_inact + rq->dl.extra_bw > rq->dl.max_bw - dl_se->dl_bw) in grub_reclaim()
1456 u_act = dl_se->dl_bw; in grub_reclaim()
1458 u_act = rq->dl.max_bw - u_inact - rq->dl.extra_bw; in grub_reclaim()
1460 u_act = (u_act * rq->dl.bw_ratio) >> RATIO_SHIFT; in grub_reclaim()
1469 * For tasks that participate in GRUB, we implement GRUB-PA: the in dl_scaled_delta_exec()
1473 * according to current frequency and CPU maximum capacity. in dl_scaled_delta_exec()
1475 if (unlikely(dl_se->flags & SCHED_FLAG_RECLAIM)) { in dl_scaled_delta_exec()
1478 int cpu = cpu_of(rq); in dl_scaled_delta_exec() local
1479 unsigned long scale_freq = arch_scale_freq_capacity(cpu); in dl_scaled_delta_exec()
1480 unsigned long scale_cpu = arch_scale_cpu_capacity(cpu); in dl_scaled_delta_exec()
1497 if (unlikely(dl_se->dl_yielded)) in update_curr_dl_se()
1502 if (dl_server(dl_se) && dl_se->dl_throttled && !dl_se->dl_defer) in update_curr_dl_se()
1510 dl_se->runtime -= scaled_delta_exec; in update_curr_dl_se()
1520 if (dl_se->dl_defer && dl_se->dl_throttled && dl_runtime_exceeded(dl_se)) { in update_curr_dl_se()
1522 * If the server was previously activated - the starving condition in update_curr_dl_se()
1527 dl_se->dl_defer_running = 0; in update_curr_dl_se()
1529 hrtimer_try_to_cancel(&dl_se->dl_timer); in update_curr_dl_se()
1531 replenish_dl_new_period(dl_se, dl_se->rq); in update_curr_dl_se()
1534 * Not being able to start the timer seems problematic. If it could not in update_curr_dl_se()
1545 if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) { in update_curr_dl_se()
1546 dl_se->dl_throttled = 1; in update_curr_dl_se()
1550 (dl_se->flags & SCHED_FLAG_DL_OVERRUN)) in update_curr_dl_se()
1551 dl_se->dl_overrun = 1; in update_curr_dl_se()
1555 update_stats_dequeue_dl(&rq->dl, dl_se, 0); in update_curr_dl_se()
1566 if (!is_leftmost(dl_se, &rq->dl)) in update_curr_dl_se()
1571 * The fair server (sole dl_server) does not account for real-time in update_curr_dl_se()
1574 if (dl_se == &rq->fair_server) in update_curr_dl_se()
1579 * Because -- for now -- we share the rt bandwidth, we need to in update_curr_dl_se()
1586 * using deadline servers -- however there's a few nasties to figure in update_curr_dl_se()
1590 struct rt_rq *rt_rq = &rq->rt; in update_curr_dl_se()
1592 raw_spin_lock(&rt_rq->rt_runtime_lock); in update_curr_dl_se()
1599 rt_rq->rt_time += delta_exec; in update_curr_dl_se()
1600 raw_spin_unlock(&rt_rq->rt_runtime_lock); in update_curr_dl_se()
1606 * In the non-defer mode, the idle time is not accounted, as the
1617 if (!rq->fair_server.dl_defer) in dl_server_update_idle_time()
1621 if (rq->fair_server.runtime < 0) in dl_server_update_idle_time()
1624 delta_exec = rq_clock_task(rq) - p->se.exec_start; in dl_server_update_idle_time()
1628 scaled_delta_exec = dl_scaled_delta_exec(rq, &rq->fair_server, delta_exec); in dl_server_update_idle_time()
1630 rq->fair_server.runtime -= scaled_delta_exec; in dl_server_update_idle_time()
1632 if (rq->fair_server.runtime < 0) { in dl_server_update_idle_time()
1633 rq->fair_server.dl_defer_running = 0; in dl_server_update_idle_time()
1634 rq->fair_server.runtime = 0; in dl_server_update_idle_time()
1637 p->se.exec_start = rq_clock_task(rq); in dl_server_update_idle_time()
1643 if (dl_se->dl_runtime) in dl_server_update()
1644 update_curr_dl_se(dl_se->rq, dl_se, delta_exec); in dl_server_update()
1649 struct rq *rq = dl_se->rq; in dl_server_start()
1662 dl_se->dl_server = 1; in dl_server_start()
1663 dl_se->dl_defer = 1; in dl_server_start()
1667 if (!dl_se->dl_runtime) in dl_server_start()
1670 dl_se->dl_server_active = 1; in dl_server_start()
1672 if (!dl_task(dl_se->rq->curr) || dl_entity_preempt(dl_se, &rq->curr->dl)) in dl_server_start()
1673 resched_curr(dl_se->rq); in dl_server_start()
1678 if (!dl_se->dl_runtime) in dl_server_stop()
1682 hrtimer_try_to_cancel(&dl_se->dl_timer); in dl_server_stop()
1683 dl_se->dl_defer_armed = 0; in dl_server_stop()
1684 dl_se->dl_throttled = 0; in dl_server_stop()
1685 dl_se->dl_server_active = 0; in dl_server_stop()
1692 dl_se->rq = rq; in dl_server_init()
1693 dl_se->server_has_tasks = has_tasks; in dl_server_init()
1694 dl_se->server_pick_task = pick_task; in dl_server_init()
1699 u64 new_bw = dl_se->dl_bw; in __dl_server_attach_root()
1700 int cpu = cpu_of(rq); in __dl_server_attach_root() local
1704 guard(raw_spinlock)(&dl_b->lock); in __dl_server_attach_root()
1706 if (!dl_bw_cpus(cpu)) in __dl_server_attach_root()
1709 __dl_add(dl_b, new_bw, dl_bw_cpus(cpu)); in __dl_server_attach_root()
1714 u64 old_bw = init ? 0 : to_ratio(dl_se->dl_period, dl_se->dl_runtime); in dl_server_apply_params()
1716 struct rq *rq = dl_se->rq; in dl_server_apply_params()
1717 int cpu = cpu_of(rq); in dl_server_apply_params() local
1723 dl_b = dl_bw_of(cpu); in dl_server_apply_params()
1724 guard(raw_spinlock)(&dl_b->lock); in dl_server_apply_params()
1726 cpus = dl_bw_cpus(cpu); in dl_server_apply_params()
1727 cap = dl_bw_capacity(cpu); in dl_server_apply_params()
1730 return -EBUSY; in dl_server_apply_params()
1733 __add_rq_bw(new_bw, &rq->dl); in dl_server_apply_params()
1736 __dl_sub(dl_b, dl_se->dl_bw, cpus); in dl_server_apply_params()
1742 dl_se->dl_runtime = runtime; in dl_server_apply_params()
1743 dl_se->dl_deadline = period; in dl_server_apply_params()
1744 dl_se->dl_period = period; in dl_server_apply_params()
1746 dl_se->runtime = 0; in dl_server_apply_params()
1747 dl_se->deadline = 0; in dl_server_apply_params()
1749 dl_se->dl_bw = to_ratio(dl_se->dl_period, dl_se->dl_runtime); in dl_server_apply_params()
1750 dl_se->dl_density = to_ratio(dl_se->dl_deadline, dl_se->dl_runtime); in dl_server_apply_params()
1757 * a -deadline task and has not been removed from the dl_rq).
1761 struct task_struct *donor = rq->donor; in update_curr_dl()
1762 struct sched_dl_entity *dl_se = &donor->dl; in update_curr_dl()
1780 static enum hrtimer_restart inactive_task_timer(struct hrtimer *timer) in inactive_task_timer() argument
1782 struct sched_dl_entity *dl_se = container_of(timer, in inactive_task_timer()
1793 rq = dl_se->rq; in inactive_task_timer()
1803 if (!dl_task(p) || READ_ONCE(p->__state) == TASK_DEAD) { in inactive_task_timer()
1806 if (READ_ONCE(p->__state) == TASK_DEAD && dl_se->dl_non_contending) { in inactive_task_timer()
1807 sub_running_bw(&p->dl, dl_rq_of_se(&p->dl)); in inactive_task_timer()
1808 sub_rq_bw(&p->dl, dl_rq_of_se(&p->dl)); in inactive_task_timer()
1809 dl_se->dl_non_contending = 0; in inactive_task_timer()
1812 raw_spin_lock(&dl_b->lock); in inactive_task_timer()
1813 __dl_sub(dl_b, p->dl.dl_bw, dl_bw_cpus(task_cpu(p))); in inactive_task_timer()
1814 raw_spin_unlock(&dl_b->lock); in inactive_task_timer()
1821 if (dl_se->dl_non_contending == 0) in inactive_task_timer()
1824 sub_running_bw(dl_se, &rq->dl); in inactive_task_timer()
1825 dl_se->dl_non_contending = 0; in inactive_task_timer()
1840 struct hrtimer *timer = &dl_se->inactive_timer; in init_dl_inactive_task_timer() local
1842 hrtimer_init(timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL_HARD); in init_dl_inactive_task_timer()
1843 timer->function = inactive_task_timer; in init_dl_inactive_task_timer()
1855 if (dl_rq->earliest_dl.curr == 0 || in inc_dl_deadline()
1856 dl_time_before(deadline, dl_rq->earliest_dl.curr)) { in inc_dl_deadline()
1857 if (dl_rq->earliest_dl.curr == 0) in inc_dl_deadline()
1858 cpupri_set(&rq->rd->cpupri, rq->cpu, CPUPRI_HIGHER); in inc_dl_deadline()
1859 dl_rq->earliest_dl.curr = deadline; in inc_dl_deadline()
1860 cpudl_set(&rq->rd->cpudl, rq->cpu, deadline); in inc_dl_deadline()
1872 if (!dl_rq->dl_nr_running) { in dec_dl_deadline()
1873 dl_rq->earliest_dl.curr = 0; in dec_dl_deadline()
1874 dl_rq->earliest_dl.next = 0; in dec_dl_deadline()
1875 cpudl_clear(&rq->rd->cpudl, rq->cpu); in dec_dl_deadline()
1876 cpupri_set(&rq->rd->cpupri, rq->cpu, rq->rt.highest_prio.curr); in dec_dl_deadline()
1878 struct rb_node *leftmost = rb_first_cached(&dl_rq->root); in dec_dl_deadline()
1881 dl_rq->earliest_dl.curr = entry->deadline; in dec_dl_deadline()
1882 cpudl_set(&rq->rd->cpudl, rq->cpu, entry->deadline); in dec_dl_deadline()
1896 u64 deadline = dl_se->deadline; in inc_dl_tasks()
1898 dl_rq->dl_nr_running++; in inc_dl_tasks()
1907 WARN_ON(!dl_rq->dl_nr_running); in dec_dl_tasks()
1908 dl_rq->dl_nr_running--; in dec_dl_tasks()
1911 dec_dl_deadline(dl_rq, dl_se->deadline); in dec_dl_tasks()
1916 return dl_time_before(__node_2_dle(a)->deadline, __node_2_dle(b)->deadline); in __dl_less()
1928 return &dl_task_of(dl_se)->stats; in __schedstats_from_dl_se()
1978 state = READ_ONCE(p->__state); in update_stats_dequeue_dl()
1980 __schedstat_set(p->stats.sleep_start, in update_stats_dequeue_dl()
1984 __schedstat_set(p->stats.block_start, in update_stats_dequeue_dl()
1993 WARN_ON_ONCE(!RB_EMPTY_NODE(&dl_se->rb_node)); in __enqueue_dl_entity()
1995 rb_add_cached(&dl_se->rb_node, &dl_rq->root, __dl_less); in __enqueue_dl_entity()
2004 if (RB_EMPTY_NODE(&dl_se->rb_node)) in __dequeue_dl_entity()
2007 rb_erase_cached(&dl_se->rb_node, &dl_rq->root); in __dequeue_dl_entity()
2009 RB_CLEAR_NODE(&dl_se->rb_node); in __dequeue_dl_entity()
2025 * the replenishment timer will be set to the next period. in enqueue_dl_entity()
2027 if (!dl_se->dl_throttled && !dl_is_implicit(dl_se)) in enqueue_dl_entity()
2040 * its rq, the bandwidth timer callback (which clearly has not in enqueue_dl_entity()
2044 * task's state - in GRUB parlance, "inactive" vs "active contending"). in enqueue_dl_entity()
2049 if (!dl_se->dl_defer && dl_se->dl_throttled && !(flags & ENQUEUE_REPLENISH)) { in enqueue_dl_entity()
2068 dl_time_before(dl_se->deadline, rq_clock(rq_of_dl_se(dl_se)))) { in enqueue_dl_entity()
2076 if (dl_se->dl_throttled && start_dl_timer(dl_se)) in enqueue_dl_entity()
2080 * We're about to enqueue, make sure we're not ->dl_throttled! in enqueue_dl_entity()
2081 * In case the timer was not started, say because the defer time in enqueue_dl_entity()
2085 if (dl_se->dl_throttled) { in enqueue_dl_entity()
2086 hrtimer_try_to_cancel(&dl_se->dl_timer); in enqueue_dl_entity()
2087 dl_se->dl_defer_armed = 0; in enqueue_dl_entity()
2088 dl_se->dl_throttled = 0; in enqueue_dl_entity()
2106 * This check allows to start the inactive timer (or to immediately in dequeue_dl_entity()
2109 * (p->state == TASK_DEAD). We can handle the two cases in the same in dequeue_dl_entity()
2120 if (is_dl_boosted(&p->dl)) { in enqueue_task_dl()
2133 if (p->dl.dl_throttled) { in enqueue_task_dl()
2135 * The replenish timer needs to be canceled. No in enqueue_task_dl()
2139 cancel_replenish_timer(&p->dl); in enqueue_task_dl()
2140 p->dl.dl_throttled = 0; in enqueue_task_dl()
2142 } else if (!dl_prio(p->normal_prio)) { in enqueue_task_dl()
2148 * clear the flag, otherwise the task may wake up as throttled after in enqueue_task_dl()
2152 p->dl.dl_throttled = 0; in enqueue_task_dl()
2154 printk_deferred_once("sched: DL de-boosted task PID %d: REPLENISH flag missing\n", in enqueue_task_dl()
2161 update_stats_wait_start_dl(dl_rq_of_se(&p->dl), &p->dl); in enqueue_task_dl()
2163 if (p->on_rq == TASK_ON_RQ_MIGRATING) in enqueue_task_dl()
2166 enqueue_dl_entity(&p->dl, flags); in enqueue_task_dl()
2168 if (dl_server(&p->dl)) in enqueue_task_dl()
2171 if (!task_current(rq, p) && !p->dl.dl_throttled && p->nr_cpus_allowed > 1) in enqueue_task_dl()
2179 if (p->on_rq == TASK_ON_RQ_MIGRATING) in dequeue_task_dl()
2182 dequeue_dl_entity(&p->dl, flags); in dequeue_task_dl()
2183 if (!p->dl.dl_throttled && !dl_server(&p->dl)) in dequeue_task_dl()
2190 * Yield task semantic for -deadline tasks is:
2192 * get off from the CPU until our next instance, with
2204 * it and the bandwidth timer will wake it up and will give it in yield_task_dl()
2207 rq->curr->dl.dl_yielded = 1; in yield_task_dl()
2224 return (!rq->dl.dl_nr_running || in dl_task_is_earliest_deadline()
2225 dl_time_before(p->dl.deadline, in dl_task_is_earliest_deadline()
2226 rq->dl.earliest_dl.curr)); in dl_task_is_earliest_deadline()
2232 select_task_rq_dl(struct task_struct *p, int cpu, int flags) in select_task_rq_dl() argument
2241 rq = cpu_rq(cpu); in select_task_rq_dl()
2244 curr = READ_ONCE(rq->curr); /* unlocked access */ in select_task_rq_dl()
2245 donor = READ_ONCE(rq->donor); in select_task_rq_dl()
2248 * If we are dealing with a -deadline task, we must in select_task_rq_dl()
2249 * decide where to wake it up. in select_task_rq_dl()
2257 (curr->nr_cpus_allowed < 2 || in select_task_rq_dl()
2258 !dl_entity_preempt(&p->dl, &donor->dl)) && in select_task_rq_dl()
2259 p->nr_cpus_allowed > 1; in select_task_rq_dl()
2262 * Take the capacity of the CPU into account to in select_task_rq_dl()
2266 select_rq |= !dl_task_fits_capacity(p, cpu); in select_task_rq_dl()
2271 if (target != -1 && in select_task_rq_dl()
2273 cpu = target; in select_task_rq_dl()
2278 return cpu; in select_task_rq_dl()
2286 if (READ_ONCE(p->__state) != TASK_WAKING) in migrate_task_rq_dl()
2291 * Since p->state == TASK_WAKING, set_task_cpu() has been called in migrate_task_rq_dl()
2292 * from try_to_wake_up(). Hence, p->pi_lock is locked, but in migrate_task_rq_dl()
2293 * rq->lock is not... So, lock it in migrate_task_rq_dl()
2296 if (p->dl.dl_non_contending) { in migrate_task_rq_dl()
2298 sub_running_bw(&p->dl, &rq->dl); in migrate_task_rq_dl()
2299 p->dl.dl_non_contending = 0; in migrate_task_rq_dl()
2301 * If the timer handler is currently running and the in migrate_task_rq_dl()
2302 * timer cannot be canceled, inactive_task_timer() in migrate_task_rq_dl()
2307 cancel_inactive_timer(&p->dl); in migrate_task_rq_dl()
2309 sub_rq_bw(&p->dl, &rq->dl); in migrate_task_rq_dl()
2319 if (rq->curr->nr_cpus_allowed == 1 || in check_preempt_equal_dl()
2320 !cpudl_find(&rq->rd->cpudl, rq->donor, NULL)) in check_preempt_equal_dl()
2327 if (p->nr_cpus_allowed != 1 && in check_preempt_equal_dl()
2328 cpudl_find(&rq->rd->cpudl, p, NULL)) in check_preempt_equal_dl()
2336 if (!on_dl_rq(&p->dl) && need_pull_dl_task(rq, p)) { in balance_dl()
2339 * picked for load-balance and preemption/IRQs are still in balance_dl()
2353 * Only called when both the current and waking task are -deadline
2359 if (dl_entity_preempt(&p->dl, &rq->donor->dl)) { in wakeup_preempt_dl()
2369 if ((p->dl.deadline == rq->donor->dl.deadline) && in wakeup_preempt_dl()
2370 !test_tsk_need_resched(rq->curr)) in wakeup_preempt_dl()
2378 hrtick_start(rq, dl_se->runtime); in start_hrtick_dl()
2388 struct sched_dl_entity *dl_se = &p->dl; in set_next_task_dl()
2389 struct dl_rq *dl_rq = &rq->dl; in set_next_task_dl()
2391 p->se.exec_start = rq_clock_task(rq); in set_next_task_dl()
2392 if (on_dl_rq(&p->dl)) in set_next_task_dl()
2401 if (rq->donor->sched_class != &dl_sched_class) in set_next_task_dl()
2407 start_hrtick_dl(rq, &p->dl); in set_next_task_dl()
2412 struct rb_node *left = rb_first_cached(&dl_rq->root); in pick_next_dl_entity()
2421 * __pick_next_task_dl - Helper to pick the next -deadline task to run.
2427 struct dl_rq *dl_rq = &rq->dl; in __pick_task_dl()
2438 p = dl_se->server_pick_task(dl_se); in __pick_task_dl()
2441 dl_se->dl_yielded = 1; in __pick_task_dl()
2446 rq->dl_server = dl_se; in __pick_task_dl()
2461 struct sched_dl_entity *dl_se = &p->dl; in put_prev_task_dl()
2462 struct dl_rq *dl_rq = &rq->dl; in put_prev_task_dl()
2464 if (on_dl_rq(&p->dl)) in put_prev_task_dl()
2470 if (on_dl_rq(&p->dl) && p->nr_cpus_allowed > 1) in put_prev_task_dl()
2492 if (hrtick_enabled_dl(rq) && queued && p->dl.runtime > 0 && in task_tick_dl()
2493 is_leftmost(&p->dl, &rq->dl)) in task_tick_dl()
2494 start_hrtick_dl(rq, &p->dl); in task_tick_dl()
2500 * SCHED_DEADLINE tasks cannot fork and this is achieved through in task_fork_dl()
2512 * on the CPU, NULL otherwise:
2514 static struct task_struct *pick_earliest_pushable_dl_task(struct rq *rq, int cpu) in pick_earliest_pushable_dl_task() argument
2522 next_node = rb_first_cached(&rq->dl.pushable_dl_tasks_root); in pick_earliest_pushable_dl_task()
2526 if (task_is_pushable(rq, p, cpu)) in pick_earliest_pushable_dl_task()
2542 int cpu = task_cpu(task); in find_later_rq() local
2546 return -1; in find_later_rq()
2548 if (task->nr_cpus_allowed == 1) in find_later_rq()
2549 return -1; in find_later_rq()
2553 * first, then we can look for a suitable CPU. in find_later_rq()
2555 if (!cpudl_find(&task_rq(task)->rd->cpudl, task, later_mask)) in find_later_rq()
2556 return -1; in find_later_rq()
2567 * The last CPU where the task run is our first in find_later_rq()
2568 * guess, since it is most likely cache-hot there. in find_later_rq()
2570 if (cpumask_test_cpu(cpu, later_mask)) in find_later_rq()
2571 return cpu; in find_later_rq()
2577 this_cpu = -1; in find_later_rq()
2580 for_each_domain(cpu, sd) { in find_later_rq()
2581 if (sd->flags & SD_WAKE_AFFINE) { in find_later_rq()
2588 if (this_cpu != -1 && in find_later_rq()
2597 * Last chance: if a CPU being in both later_mask in find_later_rq()
2599 * choice. Of course, the latest possible CPU is in find_later_rq()
2614 if (this_cpu != -1) in find_later_rq()
2617 cpu = cpumask_any_distribute(later_mask); in find_later_rq()
2618 if (cpu < nr_cpu_ids) in find_later_rq()
2619 return cpu; in find_later_rq()
2621 return -1; in find_later_rq()
2629 int cpu; in find_lock_later_rq() local
2632 cpu = find_later_rq(task); in find_lock_later_rq()
2634 if ((cpu == -1) || (cpu == rq->cpu)) in find_lock_later_rq()
2637 later_rq = cpu_rq(cpu); in find_lock_later_rq()
2652 !cpumask_test_cpu(later_rq->cpu, &task->cpus_mask) || in find_lock_later_rq()
2664 * If the rq we found has no -deadline task, or in find_lock_later_rq()
2686 p = __node_2_pdl(rb_first_cached(&rq->dl.pushable_dl_tasks_root)); in pick_next_pushable_dl_task()
2688 WARN_ON_ONCE(rq->cpu != task_cpu(p)); in pick_next_pushable_dl_task()
2690 WARN_ON_ONCE(p->nr_cpus_allowed <= 1); in pick_next_pushable_dl_task()
2699 * See if the non running -deadline tasks on this rq
2700 * can be sent to some other CPU where they can preempt
2715 * If next_task preempts rq->curr, and rq->curr in push_dl_task()
2719 if (dl_task(rq->donor) && in push_dl_task()
2720 dl_time_before(next_task->dl.deadline, rq->donor->dl.deadline) && in push_dl_task()
2721 rq->curr->nr_cpus_allowed > 1) { in push_dl_task()
2729 if (WARN_ON(next_task == rq->curr)) in push_dl_task()
2742 * find_lock_later_rq releases rq->lock and it is in push_dl_task()
2749 * again, some other CPU will pull it when ready. in push_dl_task()
2778 /* push_dl_task() will return true if it moved a -deadline task */ in push_dl_tasks()
2785 int this_cpu = this_rq->cpu, cpu; in pull_dl_task() local
2800 for_each_cpu(cpu, this_rq->rd->dlo_mask) { in pull_dl_task()
2801 if (this_cpu == cpu) in pull_dl_task()
2804 src_rq = cpu_rq(cpu); in pull_dl_task()
2810 if (this_rq->dl.dl_nr_running && in pull_dl_task()
2811 dl_time_before(this_rq->dl.earliest_dl.curr, in pull_dl_task()
2812 src_rq->dl.earliest_dl.next)) in pull_dl_task()
2815 /* Might drop this_rq->lock */ in pull_dl_task()
2823 if (src_rq->dl.dl_nr_running <= 1) in pull_dl_task()
2830 * - it preempts our current (if there's one), in pull_dl_task()
2831 * - it will preempt the last one we pulled (if any). in pull_dl_task()
2833 if (p && dl_time_before(p->dl.deadline, dmin) && in pull_dl_task()
2835 WARN_ON(p == src_rq->curr); in pull_dl_task()
2842 if (dl_time_before(p->dl.deadline, in pull_dl_task()
2843 src_rq->donor->dl.deadline)) in pull_dl_task()
2850 dmin = p->dl.deadline; in pull_dl_task()
2862 stop_one_cpu_nowait(src_rq->cpu, push_cpu_stop, in pull_dl_task()
2863 push_task, &src_rq->push_work); in pull_dl_task()
2880 !test_tsk_need_resched(rq->curr) && in task_woken_dl()
2881 p->nr_cpus_allowed > 1 && in task_woken_dl()
2882 dl_task(rq->donor) && in task_woken_dl()
2883 (rq->curr->nr_cpus_allowed < 2 || in task_woken_dl()
2884 !dl_entity_preempt(&p->dl, &rq->donor->dl))) { in task_woken_dl()
2898 src_rd = rq->rd; in set_cpus_allowed_dl()
2905 if (!cpumask_intersects(src_rd->span, ctx->new_mask)) { in set_cpus_allowed_dl()
2914 raw_spin_lock(&src_dl_b->lock); in set_cpus_allowed_dl()
2915 __dl_sub(src_dl_b, p->dl.dl_bw, dl_bw_cpus(task_cpu(p))); in set_cpus_allowed_dl()
2916 raw_spin_unlock(&src_dl_b->lock); in set_cpus_allowed_dl()
2922 /* Assumes rq->lock is held */
2925 if (rq->dl.overloaded) in rq_online_dl()
2928 cpudl_set_freecpu(&rq->rd->cpudl, rq->cpu); in rq_online_dl()
2929 if (rq->dl.dl_nr_running > 0) in rq_online_dl()
2930 cpudl_set(&rq->rd->cpudl, rq->cpu, rq->dl.earliest_dl.curr); in rq_online_dl()
2933 /* Assumes rq->lock is held */
2936 if (rq->dl.overloaded) in rq_offline_dl()
2939 cpudl_clear(&rq->rd->cpudl, rq->cpu); in rq_offline_dl()
2940 cpudl_clear_freecpu(&rq->rd->cpudl, rq->cpu); in rq_offline_dl()
2958 raw_spin_lock_irqsave(&p->pi_lock, rf.flags); in dl_add_task_root_domain()
2959 if (!dl_task(p) || dl_entity_is_special(&p->dl)) { in dl_add_task_root_domain()
2960 raw_spin_unlock_irqrestore(&p->pi_lock, rf.flags); in dl_add_task_root_domain()
2966 dl_b = &rq->rd->dl_bw; in dl_add_task_root_domain()
2967 raw_spin_lock(&dl_b->lock); in dl_add_task_root_domain()
2969 __dl_add(dl_b, p->dl.dl_bw, cpumask_weight(rq->rd->span)); in dl_add_task_root_domain()
2971 raw_spin_unlock(&dl_b->lock); in dl_add_task_root_domain()
2980 guard(raw_spinlock_irqsave)(&rd->dl_bw.lock); in dl_clear_root_domain()
2981 rd->dl_bw.total_bw = 0; in dl_clear_root_domain()
2987 for_each_cpu(i, rd->span) { in dl_clear_root_domain()
2988 struct sched_dl_entity *dl_se = &cpu_rq(i)->fair_server; in dl_clear_root_domain()
2991 __dl_add(&rd->dl_bw, dl_se->dl_bw, dl_bw_cpus(i)); in dl_clear_root_domain()
2995 void dl_clear_root_domain_cpu(int cpu) in dl_clear_root_domain_cpu() argument
2997 dl_clear_root_domain(cpu_rq(cpu)->rd); in dl_clear_root_domain_cpu()
3005 * task_non_contending() can start the "inactive timer" (if the 0-lag in switched_from_dl()
3007 * the "inactive timer" fires, it can continue to consume its current in switched_from_dl()
3009 * SCHED_DEADLINE until the 0-lag time passes, inactive_task_timer() in switched_from_dl()
3012 if (task_on_rq_queued(p) && p->dl.dl_runtime) in switched_from_dl()
3013 task_non_contending(&p->dl); in switched_from_dl()
3023 * Inactive timer is armed. However, p is leaving DEADLINE and in switched_from_dl()
3028 if (p->dl.dl_non_contending) in switched_from_dl()
3029 sub_running_bw(&p->dl, &rq->dl); in switched_from_dl()
3030 sub_rq_bw(&p->dl, &rq->dl); in switched_from_dl()
3034 * We cannot use inactive_task_timer() to invoke sub_running_bw() in switched_from_dl()
3035 * at the 0-lag time, because the task could have been migrated in switched_from_dl()
3038 if (p->dl.dl_non_contending) in switched_from_dl()
3039 p->dl.dl_non_contending = 0; in switched_from_dl()
3042 * Since this might be the only -deadline task on the rq, in switched_from_dl()
3044 * from an overloaded CPU, if any. in switched_from_dl()
3046 if (!task_on_rq_queued(p) || rq->dl.dl_nr_running) in switched_from_dl()
3053 * When switching to -deadline, we may overload the rq, then
3058 cancel_inactive_timer(&p->dl); in switched_to_dl()
3068 add_rq_bw(&p->dl, &rq->dl); in switched_to_dl()
3073 if (rq->donor != p) { in switched_to_dl()
3075 if (p->nr_cpus_allowed > 1 && rq->dl.overloaded) in switched_to_dl()
3078 if (dl_task(rq->donor)) in switched_to_dl()
3088 * If the scheduling parameters of a -deadline task changed,
3104 if (!rq->dl.overloaded) in prio_changed_dl()
3113 if (dl_time_before(rq->dl.earliest_dl.curr, p->dl.deadline)) in prio_changed_dl()
3122 if (!dl_task(rq->curr) || in prio_changed_dl()
3123 dl_time_before(p->dl.deadline, rq->curr->dl.deadline)) in prio_changed_dl()
3136 static int task_is_throttled_dl(struct task_struct *p, int cpu) in task_is_throttled_dl() argument
3138 return p->dl.dl_throttled; in task_is_throttled_dl()
3191 int cpu, cpus, ret = 0; in sched_dl_global_validate() local
3199 for_each_online_cpu(cpu) { in sched_dl_global_validate()
3202 if (dl_bw_visited(cpu, cookie)) in sched_dl_global_validate()
3205 dl_b = dl_bw_of(cpu); in sched_dl_global_validate()
3206 cpus = dl_bw_cpus(cpu); in sched_dl_global_validate()
3208 raw_spin_lock_irqsave(&dl_b->lock, flags); in sched_dl_global_validate()
3209 if (new_bw * cpus < dl_b->total_bw) in sched_dl_global_validate()
3210 ret = -EBUSY; in sched_dl_global_validate()
3211 raw_spin_unlock_irqrestore(&dl_b->lock, flags); in sched_dl_global_validate()
3226 dl_rq->bw_ratio = 1 << RATIO_SHIFT; in init_dl_rq_bw_ratio()
3227 dl_rq->max_bw = dl_rq->extra_bw = 1 << BW_SHIFT; in init_dl_rq_bw_ratio()
3229 dl_rq->bw_ratio = to_ratio(global_rt_runtime(), in init_dl_rq_bw_ratio()
3230 global_rt_period()) >> (BW_SHIFT - RATIO_SHIFT); in init_dl_rq_bw_ratio()
3231 dl_rq->max_bw = dl_rq->extra_bw = in init_dl_rq_bw_ratio()
3238 u64 new_bw = -1; in sched_dl_do_global()
3241 int cpu; in sched_dl_do_global() local
3247 for_each_possible_cpu(cpu) { in sched_dl_do_global()
3250 if (dl_bw_visited(cpu, cookie)) { in sched_dl_do_global()
3255 dl_b = dl_bw_of(cpu); in sched_dl_do_global()
3257 raw_spin_lock_irqsave(&dl_b->lock, flags); in sched_dl_do_global()
3258 dl_b->bw = new_bw; in sched_dl_do_global()
3259 raw_spin_unlock_irqrestore(&dl_b->lock, flags); in sched_dl_do_global()
3262 init_dl_rq_bw_ratio(&cpu_rq(cpu)->dl); in sched_dl_do_global()
3272 * This function is called while holding p's rq->lock.
3277 u64 period = attr->sched_period ?: attr->sched_deadline; in sched_dl_overflow()
3278 u64 runtime = attr->sched_runtime; in sched_dl_overflow()
3280 int cpus, err = -1, cpu = task_cpu(p); in sched_dl_overflow() local
3281 struct dl_bw *dl_b = dl_bw_of(cpu); in sched_dl_overflow()
3284 if (attr->sched_flags & SCHED_FLAG_SUGOV) in sched_dl_overflow()
3288 if (new_bw == p->dl.dl_bw && task_has_dl_policy(p)) in sched_dl_overflow()
3292 * Either if a task, enters, leave, or stays -deadline but changes in sched_dl_overflow()
3296 raw_spin_lock(&dl_b->lock); in sched_dl_overflow()
3297 cpus = dl_bw_cpus(cpu); in sched_dl_overflow()
3298 cap = dl_bw_capacity(cpu); in sched_dl_overflow()
3302 if (hrtimer_active(&p->dl.inactive_timer)) in sched_dl_overflow()
3303 __dl_sub(dl_b, p->dl.dl_bw, cpus); in sched_dl_overflow()
3307 !__dl_overflow(dl_b, cap, p->dl.dl_bw, new_bw)) { in sched_dl_overflow()
3311 * utilization change until the task's 0-lag point. in sched_dl_overflow()
3313 * timer" when the task is not inactive. in sched_dl_overflow()
3315 __dl_sub(dl_b, p->dl.dl_bw, cpus); in sched_dl_overflow()
3323 * (0-lag) time. in sched_dl_overflow()
3327 raw_spin_unlock(&dl_b->lock); in sched_dl_overflow()
3342 struct sched_dl_entity *dl_se = &p->dl; in __setparam_dl()
3344 dl_se->dl_runtime = attr->sched_runtime; in __setparam_dl()
3345 dl_se->dl_deadline = attr->sched_deadline; in __setparam_dl()
3346 dl_se->dl_period = attr->sched_period ?: dl_se->dl_deadline; in __setparam_dl()
3347 dl_se->flags = attr->sched_flags & SCHED_DL_FLAGS; in __setparam_dl()
3348 dl_se->dl_bw = to_ratio(dl_se->dl_period, dl_se->dl_runtime); in __setparam_dl()
3349 dl_se->dl_density = to_ratio(dl_se->dl_deadline, dl_se->dl_runtime); in __setparam_dl()
3354 struct sched_dl_entity *dl_se = &p->dl; in __getparam_dl()
3356 attr->sched_priority = p->rt_priority; in __getparam_dl()
3357 attr->sched_runtime = dl_se->dl_runtime; in __getparam_dl()
3358 attr->sched_deadline = dl_se->dl_deadline; in __getparam_dl()
3359 attr->sched_period = dl_se->dl_period; in __getparam_dl()
3360 attr->sched_flags &= ~SCHED_DL_FLAGS; in __getparam_dl()
3361 attr->sched_flags |= dl_se->flags; in __getparam_dl()
3365 * This function validates the new parameters of a -deadline task.
3379 if (attr->sched_flags & SCHED_FLAG_SUGOV) in __checkparam_dl()
3383 if (attr->sched_deadline == 0) in __checkparam_dl()
3390 if (attr->sched_runtime < (1ULL << DL_SCALE)) in __checkparam_dl()
3394 * Since we use the MSB for wrap-around and sign issues, make in __checkparam_dl()
3397 if (attr->sched_deadline & (1ULL << 63) || in __checkparam_dl()
3398 attr->sched_period & (1ULL << 63)) in __checkparam_dl()
3401 period = attr->sched_period; in __checkparam_dl()
3403 period = attr->sched_deadline; in __checkparam_dl()
3406 if (period < attr->sched_deadline || in __checkparam_dl()
3407 attr->sched_deadline < attr->sched_runtime) in __checkparam_dl()
3424 dl_se->dl_runtime = 0; in __dl_clear_params()
3425 dl_se->dl_deadline = 0; in __dl_clear_params()
3426 dl_se->dl_period = 0; in __dl_clear_params()
3427 dl_se->flags = 0; in __dl_clear_params()
3428 dl_se->dl_bw = 0; in __dl_clear_params()
3429 dl_se->dl_density = 0; in __dl_clear_params()
3431 dl_se->dl_throttled = 0; in __dl_clear_params()
3432 dl_se->dl_yielded = 0; in __dl_clear_params()
3433 dl_se->dl_non_contending = 0; in __dl_clear_params()
3434 dl_se->dl_overrun = 0; in __dl_clear_params()
3435 dl_se->dl_server = 0; in __dl_clear_params()
3438 dl_se->pi_se = dl_se; in __dl_clear_params()
3444 RB_CLEAR_NODE(&dl_se->rb_node); in init_dl_entity()
3452 struct sched_dl_entity *dl_se = &p->dl; in dl_param_changed()
3454 if (dl_se->dl_runtime != attr->sched_runtime || in dl_param_changed()
3455 dl_se->dl_deadline != attr->sched_deadline || in dl_param_changed()
3456 dl_se->dl_period != attr->sched_period || in dl_param_changed()
3457 dl_se->flags != (attr->sched_flags & SCHED_DL_FLAGS)) in dl_param_changed()
3474 raw_spin_lock_irqsave(&cur_dl_b->lock, flags); in dl_cpuset_cpumask_can_shrink()
3477 raw_spin_unlock_irqrestore(&cur_dl_b->lock, flags); in dl_cpuset_cpumask_can_shrink()
3489 static int dl_bw_manage(enum dl_bw_request req, int cpu, u64 dl_bw) in dl_bw_manage() argument
3497 dl_b = dl_bw_of(cpu); in dl_bw_manage()
3498 raw_spin_lock_irqsave(&dl_b->lock, flags); in dl_bw_manage()
3500 cap = dl_bw_capacity(cpu); in dl_bw_manage()
3503 __dl_sub(dl_b, dl_bw, dl_bw_cpus(cpu)); in dl_bw_manage()
3515 __dl_add(dl_b, dl_bw, dl_bw_cpus(cpu)); in dl_bw_manage()
3520 * cpu is not off yet, but we need to do the math by in dl_bw_manage()
3522 * turn cpu off?). in dl_bw_manage()
3524 cap -= arch_scale_cpu_capacity(cpu); in dl_bw_manage()
3527 * cpu is going offline and NORMAL tasks will be moved away in dl_bw_manage()
3530 * the cpu is off. in dl_bw_manage()
3532 if (cpu_rq(cpu)->fair_server.dl_server) in dl_bw_manage()
3533 fair_server_bw = cpu_rq(cpu)->fair_server.dl_bw; in dl_bw_manage()
3540 if (dl_b->total_bw - fair_server_bw > 0) { in dl_bw_manage()
3542 * Leaving at least one CPU for DEADLINE tasks seems a in dl_bw_manage()
3543 * wise thing to do. As said above, cpu is not offline in dl_bw_manage()
3546 if (dl_bw_cpus(cpu) - 1) in dl_bw_manage()
3555 raw_spin_unlock_irqrestore(&dl_b->lock, flags); in dl_bw_manage()
3558 return overflow ? -EBUSY : 0; in dl_bw_manage()
3561 int dl_bw_deactivate(int cpu) in dl_bw_deactivate() argument
3563 return dl_bw_manage(dl_bw_req_deactivate, cpu, 0); in dl_bw_deactivate()
3566 int dl_bw_alloc(int cpu, u64 dl_bw) in dl_bw_alloc() argument
3568 return dl_bw_manage(dl_bw_req_alloc, cpu, dl_bw); in dl_bw_alloc()
3571 void dl_bw_free(int cpu, u64 dl_bw) in dl_bw_free() argument
3573 dl_bw_manage(dl_bw_req_free, cpu, dl_bw); in dl_bw_free()
3578 void print_dl_stats(struct seq_file *m, int cpu) in print_dl_stats() argument
3580 print_dl_rq(m, cpu, &cpu_rq(cpu)->dl); in print_dl_stats()