3  * Deadline Scheduling Class (SCHED_DEADLINE)
5  * Earliest Deadline First (EDF) + Constant Bandwidth Server (CBS).
273  * A flag in the deadline scheduling entity (dl_non_contending)
323 	 * If this is a non-deadline task that has been boosted,  in task_non_contending()
334 	zerolag_time = dl_se->deadline -  in task_non_contending()
375 	 * If this is a non-deadline task that has been boosted,  in task_contending()
440 	/* zero means no -deadline tasks */  in init_dl_rq()
529  * The list of pushable -deadline task is not a plist, like in
530  * sched_rt.c, it is an rb-tree with tasks ordered by deadline.
542 		rq->dl.earliest_dl.next = p->dl.deadline;  in enqueue_pushable_dl_task()
556 		dl_rq->earliest_dl.next = __node_2_pdl(leftmost)->dl.deadline;  in dequeue_pushable_dl_task()
711  *  - the absolute deadline of the entity has to be placed at
712  *    current time + relative deadline;
715  * The capability of specifying such event is useful whenever a -deadline
726 	WARN_ON(dl_time_before(rq_clock(rq), dl_se->deadline));  in setup_new_dl_entity()
729 	 * We are racing with the deadline timer. So, do nothing because  in setup_new_dl_entity()
730 	 * the deadline timer handler will take care of properly recharging  in setup_new_dl_entity()
731 	 * the runtime and postponing the deadline  in setup_new_dl_entity()
741 	dl_se->deadline = rq_clock(rq) + dl_se->dl_deadline;  in setup_new_dl_entity()
746  * Pure Earliest Deadline First (EDF) scheduling does not deal with the
757  * of a entity is replenished, its deadline is also postponed. That ensures
775 		dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline;  in replenish_dl_entity()
783 	 * We keep moving the deadline away until we get some  in replenish_dl_entity()
789 		dl_se->deadline += pi_of(dl_se)->dl_period;  in replenish_dl_entity()
794 	 * At this point, the deadline really should be "in  in replenish_dl_entity()
799 	 * resetting the deadline and the budget of the  in replenish_dl_entity()
802 	if (dl_time_before(dl_se->deadline, rq_clock(rq))) {  in replenish_dl_entity()
804 		dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline;  in replenish_dl_entity()
817  * and its current deadline _without_ exceeding the bandwidth it is
820  * over residual deadline fits within the allocated bandwidth, then we
821  * can keep the current (absolute) deadline and residual budget without
823  * refill the runtime and set the deadline a period in the future,
824  * because keeping the current (absolute) deadline of the task would
826  * Documentation/scheduler/sched-deadline.rst for more information).
830  *   runtime / (deadline - t) > dl_runtime / dl_deadline ,
834  * Notice that the bandwidth check is done against the deadline. For
835  * task with deadline equal to period this is the same of using
849 	 * are the relative deadline and the maximum runtime of each  in dl_entity_overflow()
851 	 * and (deadline - t), since t is rq->clock, is the time left  in dl_entity_overflow()
852 	 * to the (absolute) deadline. Even if overflowing the u64 type  in dl_entity_overflow()
861 	right = ((dl_se->deadline - t) >> DL_SCALE) *  in dl_entity_overflow()
869  * re-initializing task's runtime and deadline, the revised wakeup
874  *    runtime / (deadline - t) > dl_runtime / dl_deadline
877  *     runtime = (dl_runtime / dl_deadline) * (deadline - t)
888 	u64 laxity = dl_se->deadline - rq_clock(rq);  in update_dl_revised_wakeup()
891 	 * If the task has deadline < period, and the deadline is in the past,  in update_dl_revised_wakeup()
896 	WARN_ON(dl_time_before(dl_se->deadline, rq_clock(rq)));  in update_dl_revised_wakeup()
902  * Regarding the deadline, a task with implicit deadline has a relative
903  * deadline == relative period. A task with constrained deadline has a
904  * relative deadline <= relative period.
906  * We support constrained deadline tasks. However, there are some restrictions
907  * applied only for tasks which do not have an implicit deadline. See
910  * The dl_is_implicit() returns true if the task has an implicit deadline.
918  * When a deadline entity is placed in the runqueue, its runtime and deadline
923  * case, the runtime is replenished and a new absolute deadline is set.
926  * remaining runtime and deadline could make the entity to overflow, see
928  * is detected, the runtime and deadline need to be updated.
930  * If the task has an implicit deadline, i.e., deadline == period, the Original
931  * CBS is applied. the runtime is replenished and a new absolute deadline is
935  * deadline < period, which are said to have a constrained deadline. By
936  * applying the Original CBS, a constrained deadline task would be able to run
937  * runtime/deadline in a period. With deadline < period, the task would
941  * constrained deadline tasks when a runtime overflow is detected. In the
942  * Revisited CBS, rather than replenishing & setting a new absolute deadline,
952 	if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||  in update_dl_entity()
956 			     !dl_time_before(dl_se->deadline, rq_clock(rq)) &&  in update_dl_entity()
962 		dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline;  in update_dl_entity()
969 	return dl_se->deadline - dl_se->dl_deadline + dl_se->dl_period;  in dl_next_period()
993 	 * We want the timer to fire at the deadline, but considering  in start_dl_timer()
1004 	 * chosen as the deadline is too small, don't even try to  in start_dl_timer()
1036  * do nothing but clearing dl_throttled, so that runtime and deadline
1157  * runtime and period. If the deadline of the task is in the past, CBS
1159  * works fine for implicit deadline tasks (deadline == period), and the
1160  * CBS was designed for implicit deadline tasks. However, a task with
1161  * constrained deadline (deadline < period) might be awakened after the
1162  * deadline, but before the next period. In this case, replenishing the
1163  * task would allow it to run for runtime / deadline. As in this case
1164  * deadline < period, CBS enables a task to run for more than the
1168  * To avoid this problem, in the activation of a constrained deadline
1169  * task after the deadline but before the next period, throttle the
1178 	if (dl_time_before(dl_se->deadline, rq_clock(rq)) &&  in dl_check_constrained_dl()
1239  * a -deadline task and has not been removed from the dl_rq).
1326 	 * using deadline servers -- however there's a few nasties to figure  in update_curr_dl()
1396 static void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline)  in inc_dl_deadline()  argument
1401 	    dl_time_before(deadline, dl_rq->earliest_dl.curr)) {  in inc_dl_deadline()
1404 		dl_rq->earliest_dl.curr = deadline;  in inc_dl_deadline()
1405 		cpudl_set(&rq->rd->cpudl, rq->cpu, deadline);  in inc_dl_deadline()
1409 static void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline)  in dec_dl_deadline()  argument
1427 		dl_rq->earliest_dl.curr = entry->deadline;  in dec_dl_deadline()
1428 		cpudl_set(&rq->rd->cpudl, rq->cpu, entry->deadline);  in dec_dl_deadline()
1434 static inline void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline) {}  in inc_dl_deadline()  argument
1435 static inline void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline) {}  in dec_dl_deadline()  argument
1443 	u64 deadline = dl_se->deadline;  in inc_dl_tasks()  local
1449 	inc_dl_deadline(dl_rq, deadline);  in inc_dl_tasks()
1463 	dec_dl_deadline(dl_rq, dl_se->deadline);  in dec_dl_tasks()
1472 	return dl_time_before(__node_2_dle(a)->deadline, __node_2_dle(b)->deadline);  in __dl_less()
1516 		  dl_time_before(dl_se->deadline,  in enqueue_dl_entity()
1569 	 * Check if a constrained deadline task was activated  in enqueue_task_dl()
1570 	 * after the deadline but before the next period.  in enqueue_task_dl()
1637  * Yield task semantic for -deadline tasks is:
1649 	 * We make the task go to sleep until its current deadline by  in yield_task_dl()
1686 	 * If we are dealing with a -deadline task, we must  in select_task_rq_dl()
1688 	 * If it has a later deadline and the current task  in select_task_rq_dl()
1691 	 * other hand, if it has a shorter deadline, we  in select_task_rq_dl()
1710 				(dl_time_before(p->dl.deadline,  in select_task_rq_dl()
1793  * Only called when both the current and waking task are -deadline
1806 	 * In the unlikely case current and p have the same deadline  in check_preempt_curr_dl()
1809 	if ((p->dl.deadline == rq->curr->dl.deadline) &&  in check_preempt_curr_dl()
2067 		    !dl_time_before(task->dl.deadline,  in find_lock_later_rq()
2070 			 * Target rq has tasks of equal or earlier deadline,  in find_lock_later_rq()
2092 		 * If the rq we found has no -deadline task, or  in find_lock_later_rq()
2093 		 * its earliest one has a later deadline than our  in find_lock_later_rq()
2097 		    dl_time_before(task->dl.deadline,  in find_lock_later_rq()
2130  * See if the non running -deadline tasks on this rq
2160 	    dl_time_before(next_task->dl.deadline, rq->curr->dl.deadline) &&  in push_dl_task()
2220 	/* push_dl_task() will return true if it moved a -deadline task */  in push_dl_tasks()
2275 		if (p && dl_time_before(p->dl.deadline, dmin) &&  in pull_dl_task()
2277 		     dl_time_before(p->dl.deadline,  in pull_dl_task()
2284 			 * deadline than the current task of its runqueue.  in pull_dl_task()
2286 			if (dl_time_before(p->dl.deadline,  in pull_dl_task()
2287 					   src_rq->curr->dl.deadline))  in pull_dl_task()
2296 				dmin = p->dl.deadline;  in pull_dl_task()
2438 	 * runtime using its current deadline. If it stays outside of  in switched_from_dl()
2447 		 * Inactive timer is armed. However, p is leaving DEADLINE and  in switched_from_dl()
2466 	 * Since this might be the only -deadline task on the rq,  in switched_from_dl()
2477  * When switching to -deadline, we may overload the rq, then
2507  * If the scheduling parameters of a -deadline task changed,
2517 		 * we don't have the old deadline value, and  in prio_changed_dl()
2525 		 * If we now have a earlier deadline task than p,  in prio_changed_dl()
2529 		if (dl_time_before(rq->dl.earliest_dl.curr, p->dl.deadline))  in prio_changed_dl()
2534 		 * or later deadline, so let's blindly set a  in prio_changed_dl()
2685 	/* !deadline task may carry old deadline bandwidth */  in sched_dl_overflow()
2690 	 * Either if a task, enters, leave, or stays -deadline but changes  in sched_dl_overflow()
2719 		 * Do not decrease the total deadline utilization here,  in sched_dl_overflow()
2735  * absolute deadline will be properly calculated when the task is enqueued
2771  * This function validates the new parameters of a -deadline task.
2772  * We ask for the deadline not being zero, and greater or equal
2774  * greater than deadline. Furthermore, we have to be sure that
2788 	/* deadline != 0 */  in __checkparam_dl()
2811 	/* runtime <= deadline <= period (if period != 0) */  in __checkparam_dl()