sched/deadline: Fixes for constrained deadline tasks

While reading sched deadline code, I find out that a constrained deadline task could be replenished before the next period if activated after the deadline, opening the window to run for more than Q/P. The patch [2] explains and fixes this problem.

Furthermore, while fixing this issue, I found that the replenishment timer was being fired at the deadline of the task. This works fine for implicit deadline tasks (deadline == period) because the deadline is at the same point in time of the next period. But that is not true for constrained deadline tasks (deadline < period). This problem is not as visible as the first because the runtime leakage takes place only in the second activation. Next activations receive the correct bandwidth. However, after the 2nd activation, tasks are activated in the (period - dl_deadline) instant, which is before the expected activation. This problem is explained in the fix description as well.

While testing these fixes, Rostedt tweaked the test case a little. Instead of having the runtime equal to the deadline, he increased the deadline ten fold. Then, the task started using much more than .1% of the CPU. More like 20%. Looking into this he found that it was due to the dl_entity_overflow() constantly returning true. That's because it uses the relative period against relative runtime vs the absolute deadline against absolute runtime. As we care about if the runtime can make its deadline, not its period, we need to use the task's density in the check, not the task's utilization. After correcting this, now when the task gets enqueued, it can throttle correctly.

Changes from V3:
- Fixes grammar errors in the patch 2/3. (Steven Rostedt)
- I was checking if the pi_se was constrained, not the task being awakened.
This was not causing problems in the test case because pi_se = &p->dl, but this would be a problem if we were activating the task in a PI case:
It would check the pi-waiter, not the task being awakened (p).
Changes from V2:
- Fixes dl_entity_overflow(): (Steven Rostedt)
Patch 3/3 fixes the dl_entity_overflow() for constrained deadline tasks by using the density, not the utilization.
(as deadline <= period, deadline is always == min(deadline, period))
Changes from V1:
- Fix a broken comment style. (Peter Zijlstra)
- Fixes dl_is_constrained(). (Steven Rostedt)
A constrained deadline task has dl_deadline < dl_period; so
"dl_runtime < dl_period"; s/runtime/deadline/

Daniel Bristot de Oliveira (2):
sched/deadline: Replenishment timer should fire in the next period sched/deadline: Throttle a constrained deadline task activated after
the deadline

Steven Rostedt (VMware) (1):
sched/deadline: Use deadline instead of period when calculating
overflow

 kernel/sched/deadline.c | 62 ++++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 56 insertions(+), 6 deletions(-)

2.9.3