3  * Deadline Scheduling Class (SCHED_DEADLINE)
5  * Earliest Deadline First (EDF) + Constant Bandwidth Server (CBS).
393  * A flag in the deadline scheduling entity (dl_non_contending)
442 	 * If this is a non-deadline task that has been boosted,  in task_non_contending()
453 	zerolag_time = dl_se->deadline -  in task_non_contending()
503 	 * If this is a non-deadline task that has been boosted,  in task_contending()
556 	/* zero means no -deadline tasks */  in init_dl_rq()
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.
629 		rq->dl.earliest_dl.next = p->dl.deadline;  in enqueue_pushable_dl_task()
648 		dl_rq->earliest_dl.next = __node_2_pdl(leftmost)->dl.deadline;  in dequeue_pushable_dl_task()
797 	dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline;  in replenish_dl_new_period()
813  *  - the absolute deadline of the entity has to be placed at
814  *    current time + relative deadline;
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()
833 	 * the runtime and postponing the deadline  in setup_new_dl_entity()
850  * Pure Earliest Deadline First (EDF) scheduling does not deal with the
861  * of a entity is replenished, its deadline is also postponed. That ensures
886 		dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline;  in replenish_dl_entity()
894 	 * We keep moving the deadline away until we get some  in replenish_dl_entity()
900 		dl_se->deadline += pi_of(dl_se)->dl_period;  in replenish_dl_entity()
905 	 * At this point, the deadline really should be "in  in replenish_dl_entity()
910 	 * resetting the deadline and the budget of the  in replenish_dl_entity()
913 	if (dl_time_before(dl_se->deadline, rq_clock(rq))) {  in replenish_dl_entity()
933 	 * A this point, if the deferred server is not armed, and the deadline  in replenish_dl_entity()
938 	    dl_time_before(rq_clock(dl_se->rq), dl_se->deadline - dl_se->runtime)) {  in replenish_dl_entity()
965  * and its current deadline _without_ exceeding the bandwidth it is
968  * over residual deadline fits within the allocated bandwidth, then we
969  * can keep the current (absolute) deadline and residual budget without
971  * refill the runtime and set the deadline a period in the future,
972  * because keeping the current (absolute) deadline of the task would
974  * Documentation/scheduler/sched-deadline.rst for more information).
978  *   runtime / (deadline - t) > dl_runtime / dl_deadline ,
982  * Notice that the bandwidth check is done against the deadline. For
983  * task with deadline equal to period this is the same of using
997 	 * are the relative deadline and the maximum runtime of each  in dl_entity_overflow()
999 	 * and (deadline - t), since t is rq->clock, is the time left  in dl_entity_overflow()
1000 	 * to the (absolute) deadline. Even if overflowing the u64 type  in dl_entity_overflow()
1009 	right = ((dl_se->deadline - t) >> DL_SCALE) *  in dl_entity_overflow()
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)
1036 	u64 laxity = dl_se->deadline - rq_clock(rq);  in update_dl_revised_wakeup()
1039 	 * If the task has deadline < period, and the deadline is in the past,  in update_dl_revised_wakeup()
1044 	WARN_ON(dl_time_before(dl_se->deadline, rq_clock(rq)));  in update_dl_revised_wakeup()
1050  * Regarding the deadline, a task with implicit deadline has a relative
1051  * deadline == relative period. A task with constrained deadline has a
1052  * relative deadline <= relative period.
1054  * We support constrained deadline tasks. However, there are some restrictions
1055  * applied only for tasks which do not have an implicit deadline. See
1058  * The dl_is_implicit() returns true if the task has an implicit deadline.
1066  * When a deadline entity is placed in the runqueue, its runtime and deadline
1071  * case, the runtime is replenished and a new absolute deadline is set.
1074  * remaining runtime and deadline could make the entity to overflow, see
1076  * is detected, the runtime and deadline need to be updated.
1078  * If the task has an implicit deadline, i.e., deadline == period, the Original
1079  * CBS is applied. The runtime is replenished and a new absolute deadline is
1083  * deadline < period, which are said to have a constrained deadline. By
1084  * applying the Original CBS, a constrained deadline task would be able to run
1085  * runtime/deadline in a period. With deadline < period, the task would
1089  * constrained deadline tasks when a runtime overflow is detected. In the
1090  * Revisited CBS, rather than replenishing & setting a new absolute deadline,
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()
1112 		 * The server can still use its previous deadline, so check if  in update_dl_entity()
1124 	return dl_se->deadline - dl_se->dl_deadline + dl_se->dl_period;  in dl_next_period()
1148 	 * We want the timer to fire at the deadline, but considering  in start_dl_timer()
1153 	 * (deadline - runtime). At that point, the CBS rule will decide  in start_dl_timer()
1154 	 * if the current deadline can be used, or if a replenishment is  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()
1172 	 * chosen as the deadline is too small, don't even try to  in start_dl_timer()
1248 					   (dl_se->deadline - dl_se->runtime - dl_server_min_res))) {  in dl_server_timer()
1251 				fw = dl_se->deadline - rq_clock(dl_se->rq) - dl_se->runtime;  in dl_server_timer()
1280  * do nothing but clearing dl_throttled, so that runtime and deadline
1391  * runtime and period. If the deadline of the task is in the past, CBS
1393  * works fine for implicit deadline tasks (deadline == period), and the
1394  * CBS was designed for implicit deadline tasks. However, a task with
1395  * constrained deadline (deadline < period) might be awakened after the
1396  * deadline, but before the next period. In this case, replenishing the
1397  * task would allow it to run for runtime / deadline. As in this case
1398  * deadline < period, CBS enables a task to run for more than the
1402  * To avoid this problem, in the activation of a constrained deadline
1403  * task after the deadline but before the next period, throttle the
1411 	if (dl_time_before(dl_se->deadline, rq_clock(rq)) &&  in dl_check_constrained_dl()
1586 	 * using deadline servers -- however there's a few nasties to figure  in update_curr_dl_se()
1747 	dl_se->deadline = 0;  in dl_server_apply_params()
1757  * a -deadline task and has not been removed from the dl_rq).
1851 static void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline)  in inc_dl_deadline()  argument
1856 	    dl_time_before(deadline, dl_rq->earliest_dl.curr)) {  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()
1864 static void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline)  in dec_dl_deadline()  argument
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()
1888 static inline void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline) {}  in inc_dl_deadline()  argument
1889 static inline void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline) {}  in dec_dl_deadline()  argument
1896 	u64 deadline = dl_se->deadline;  in inc_dl_tasks()  local
1901 	inc_dl_deadline(dl_rq, deadline);  in inc_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()
2022 	 * Check if a constrained deadline task was activated  in enqueue_dl_entity()
2023 	 * after the deadline but before the next period.  in enqueue_dl_entity()
2068 		   dl_time_before(dl_se->deadline, rq_clock(rq_of_dl_se(dl_se)))) {  in enqueue_dl_entity()
2190  * Yield task semantic for -deadline tasks is:
2202 	 * We make the task go to sleep until its current deadline by  in yield_task_dl()
2225 		dl_time_before(p->dl.deadline,  in dl_task_is_earliest_deadline()
2248 	 * If we are dealing with a -deadline task, we must  in select_task_rq_dl()
2250 	 * If it has a later deadline and the current task  in select_task_rq_dl()
2253 	 * other hand, if it has a shorter deadline, we  in select_task_rq_dl()
2353  * Only called when both the current and waking task are -deadline
2366 	 * In the unlikely case current and p have the same deadline  in wakeup_preempt_dl()
2369 	if ((p->dl.deadline == rq->donor->dl.deadline) &&  in wakeup_preempt_dl()
2421  * __pick_next_task_dl - Helper to pick the next -deadline task to run.
2641 			 * Target rq has tasks of equal or earlier deadline,  in find_lock_later_rq()
2664 		 * If the rq we found has no -deadline task, or  in find_lock_later_rq()
2665 		 * its earliest one has a later deadline than our  in find_lock_later_rq()
2699  * See if the non running -deadline tasks on this rq
2720 	    dl_time_before(next_task->dl.deadline, rq->donor->dl.deadline) &&  in push_dl_task()
2778 	/* push_dl_task() will return true if it moved a -deadline task */  in push_dl_tasks()
2833 		if (p && dl_time_before(p->dl.deadline, dmin) &&  in pull_dl_task()
2840 			 * deadline than the current task of its runqueue.  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()
3008 	 * runtime using its current deadline. If it stays outside of  in switched_from_dl()
3023 		 * Inactive timer is armed. However, p is leaving DEADLINE and  in switched_from_dl()
3042 	 * Since this might be the only -deadline task on the rq,  in switched_from_dl()
3053  * When switching to -deadline, we may overload the rq, then
3088  * If the scheduling parameters of a -deadline task changed,
3100 	 * we don't have the old deadline value, and  in prio_changed_dl()
3109 		 * If we now have a earlier deadline task than p,  in prio_changed_dl()
3113 		if (dl_time_before(rq->dl.earliest_dl.curr, p->dl.deadline))  in prio_changed_dl()
3117 		 * Current may not be deadline in case p was throttled but we  in prio_changed_dl()
3120 		 * Otherwise, if p was given an earlier deadline, reschedule.  in prio_changed_dl()
3123 		    dl_time_before(p->dl.deadline, rq->curr->dl.deadline))  in prio_changed_dl()
3128 	 * We don't know if p has a earlier or later deadline, so let's blindly  in prio_changed_dl()
3287 	/* !deadline task may carry old deadline bandwidth */  in sched_dl_overflow()
3292 	 * Either if a task, enters, leave, or stays -deadline but changes  in sched_dl_overflow()
3321 		 * Do not decrease the total deadline utilization here,  in sched_dl_overflow()
3337  * absolute deadline will be properly calculated when the task is enqueued
3365  * This function validates the new parameters of a -deadline task.
3366  * We ask for the deadline not being zero, and greater or equal
3368  * greater than deadline. Furthermore, we have to be sure that
3382 	/* deadline != 0 */  in __checkparam_dl()
3405 	/* runtime <= deadline <= period (if period != 0) */  in __checkparam_dl()
3536 		 * Not much to check if no DEADLINE bandwidth is present.  in dl_bw_manage()
3542 			 * Leaving at least one CPU for DEADLINE tasks seems a  in dl_bw_manage()