[PATCH V2 0/2] sched/deadline: Fixes for constrained deadline tasks

[PATCH V2 0/2] sched/deadline: Fixes for constrained deadline tasks

[Daniel Bristot de Oliveira]

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.

Changes from V1:
 - Fix a broken comment style.
 - Fixes dl_is_constrained():
    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

 kernel/sched/deadline.c | 54 +++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 52 insertions(+), 2 deletions(-)

-- 
2.9.3

[PATCH V2 1/2] sched/deadline: Replenishment timer should fire in the next period

[Daniel Bristot de Oliveira]

Currently, the replenishment timer is set to fire at the deadline
of a task. Although that works for implicit deadline tasks because the
deadline is equals to the begin of the next period, that is not correct
for constrained deadline tasks (deadline < period).

For instance:

f.c:
 --------------- %< ---------------
int main (void)
{
	for(;;);
}
 --------------- >% ---------------

  # gcc -o f f.c

  # trace-cmd record -e sched:sched_switch                              \
   				   -e syscalls:sys_exit_sched_setattr   \
   chrt -d --sched-runtime  490000000 					\
           --sched-deadline 500000000 					\
	   --sched-period  1000000000 0 ./f

  # trace-cmd report | grep "{pid of ./f}"

After setting parameters, the task is replenished and continue running
until being throttled.
         f-11295 [003] 13322.113776: sys_exit_sched_setattr: 0x0

The task is throttled after running 492318 ms, as expected.
         f-11295 [003] 13322.606094: sched_switch:   f:11295 [-1] R ==> \
						   watchdog/3:32 [0]

But then, the task is replenished 500719 ms after the first
replenishment:
    <idle>-0     [003] 13322.614495: sched_switch:   swapper/3:0 [120] R \
						   ==> f:11295 [-1]

Running for 490277 ms:
         f-11295 [003] 13323.104772: sched_switch:   f:11295 [-1] R ==>  \
						   swapper/3:0 [120]

Hence, in the first period, the task runs 2 * runtime, and that is a bug.

During the first replenishment, the next deadline is set one period away.
So the runtime / period starts to be respected. However, as the second
replenishment took place in the wrong instant, the next replenishment
will also be held in a wrong instant of time. Rather than occurring in
the nth period away from the first activation, it is taking place
in the (nth period - relative deadline).

Signed-off-by: Daniel Bristot de Oliveira <bristot@redhat.com>
Reviewed-by: Luca Abeni <luca.abeni@santannapisa.it>
Reviewed-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
Reviewed-by: Juri Lelli <juri.lelli@arm.com>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Juri Lelli <juri.lelli@arm.com>
Cc: Tommaso Cucinotta <tommaso.cucinotta@sssup.it>
Cc: Luca Abeni <luca.abeni@santannapisa.it>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Mike Galbraith <efault@gmx.de>
Cc: Romulo Silva de Oliveira <romulo.deoliveira@ufsc.br>
Cc: linux-kernel@vger.kernel.org
---
 kernel/sched/deadline.c | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 70ef2b1..3c94d85 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -505,10 +505,15 @@ static void update_dl_entity(struct sched_dl_entity *dl_se,
 	}
 }
 
+static inline u64 dl_next_period(struct sched_dl_entity *dl_se)
+{
+	return dl_se->deadline - dl_se->dl_deadline + dl_se->dl_period;
+}
+
 /*
  * If the entity depleted all its runtime, and if we want it to sleep
  * while waiting for some new execution time to become available, we
- * set the bandwidth enforcement timer to the replenishment instant
+ * set the bandwidth replenishment timer to the replenishment instant
  * and try to activate it.
  *
  * Notice that it is important for the caller to know if the timer
@@ -530,7 +535,7 @@ static int start_dl_timer(struct task_struct *p)
 	 * that it is actually coming from rq->clock and not from
 	 * hrtimer's time base reading.
 	 */
-	act = ns_to_ktime(dl_se->deadline);
+	act = ns_to_ktime(dl_next_period(dl_se));
 	now = hrtimer_cb_get_time(timer);
 	delta = ktime_to_ns(now) - rq_clock(rq);
 	act = ktime_add_ns(act, delta);
-- 
2.9.3

[PATCH V2 2/2] sched/deadline: Throttle a constrained deadline task activated after the deadline

[Daniel Bristot de Oliveira]

During the activation, CBS checks if it can reuse the current task's
runtime and period. If the deadline of the task is in the past, CBS
cannot use the runtime, and so it replenishes the task. This rule
works fine for implicit deadline tasks (deadline == period), and the
CBS was designed for implicit deadline tasks. However, a task with
constrained deadline (deadine < period) might be awakened after the
deadline, but before the next period. In this case, replenishing the
task would allow it to run for runtime / deadline. As in this case
deadline < period, CBS enables a task to run for more than the
runtime / period. In a very load system, this can cause the domino
effect, making other tasks to miss their deadlines.

To avoid this problem, in the activation of a constrained deadline
task after the deadline but before the next period, throttle the
task and set the replenishing timer to the begin of the next period,
unless it is boosted.

Reproducer:

 --------------- %< ---------------
  int main (int argc, char **argv)
  {
	int ret;
	int flags = 0;
	unsigned long l = 0;
	struct timespec ts;
	struct sched_attr attr;

	memset(&attr, 0, sizeof(attr));
	attr.size = sizeof(attr);

	attr.sched_policy   = SCHED_DEADLINE;
	attr.sched_runtime  = 2 * 1000 * 1000;		/* 2 ms */
	attr.sched_deadline = 2 * 1000 * 1000;		/* 2 ms */
	attr.sched_period   = 2 * 1000 * 1000 * 1000;	/* 2 s */

	ts.tv_sec = 0;
	ts.tv_nsec = 2000 * 1000;			/* 2 ms */

	ret = sched_setattr(0, &attr, flags);

	if (ret < 0) {
		perror("sched_setattr");
		exit(-1);
	}

	for(;;) {
		/* XXX: you may need to adjust the loop */
		for (l = 0; l < 150000; l++);
		/*
		 * The ideia is to go to sleep right before the deadline
		 * and then wake up before the next period to receive
		 * a new replenishment.
		 */
		nanosleep(&ts, NULL);
	}

	exit(0);
  }
  --------------- >% ---------------

On my box, this reproducer uses almost 50% of the CPU time, which is
obviously wrong for a task with 2/2000 reservation.

Signed-off-by: Daniel Bristot de Oliveira <bristot@redhat.com>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Juri Lelli <juri.lelli@arm.com>
Cc: Tommaso Cucinotta <tommaso.cucinotta@sssup.it>
Cc: Luca Abeni <luca.abeni@santannapisa.it>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Mike Galbraith <efault@gmx.de>
Cc: Romulo Silva de Oliveira <romulo.deoliveira@ufsc.br>
Cc: linux-kernel@vger.kernel.org
---
 kernel/sched/deadline.c | 45 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 45 insertions(+)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 3c94d85..3a88def 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -694,6 +694,37 @@ void init_dl_task_timer(struct sched_dl_entity *dl_se)
 	timer->function = dl_task_timer;
 }
 
+/*
+ * During the activation, CBS checks if it can reuse the current task's
+ * runtime and period. If the deadline of the task is in the past, CBS
+ * cannot use the runtime, and so it replenishes the task. This rule
+ * works fine for implicit deadline tasks (deadline == period), and the
+ * CBS was designed for implicit deadline tasks. However, a task with
+ * constrained deadline (deadine < period) might be awakened after the
+ * deadline, but before the next period. In this case, replenishing the
+ * task would allow it to run for runtime / deadline. As in this case
+ * deadline < period, CBS enables a task to run for more than the
+ * runtime / period. In a very load system, this can cause the domino
+ * effect, making other tasks to miss their deadlines.
+ *
+ * To avoid this problem, in the activation of a constrained deadline
+ * task after the deadline but before the next period, throttle the
+ * task and set the replenishing timer to the begin of the next period,
+ * unless it is boosted.
+ */
+static inline void dl_check_constrained_dl(struct sched_dl_entity *dl_se)
+{
+	struct task_struct *p = dl_task_of(dl_se);
+	struct rq *rq = rq_of_dl_rq(dl_rq_of_se(dl_se));
+
+	if (dl_time_before(dl_se->deadline, rq_clock(rq)) &&
+	    dl_time_before(rq_clock(rq), dl_next_period(dl_se))) {
+		if (unlikely(dl_se->dl_boosted || !start_dl_timer(p)))
+			return;
+		dl_se->dl_throttled = 1;
+	}
+}
+
 static
 int dl_runtime_exceeded(struct sched_dl_entity *dl_se)
 {
@@ -927,6 +958,11 @@ static void dequeue_dl_entity(struct sched_dl_entity *dl_se)
 	__dequeue_dl_entity(dl_se);
 }
 
+static inline bool dl_is_constrained(struct sched_dl_entity *dl_se)
+{
+	return dl_se->dl_deadline < dl_se->dl_period;
+}
+
 static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
 {
 	struct task_struct *pi_task = rt_mutex_get_top_task(p);
@@ -953,6 +989,15 @@ static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
 	}
 
 	/*
+	 * Check if a constrained deadline task was activated
+	 * after the deadline but before the next period.
+	 * If that is the case, the task will be throttled and
+	 * the replenishment timer will be set to the next period.
+	 */
+	if (!pi_se->dl_throttled && dl_is_constrained(pi_se))
+		dl_check_constrained_dl(pi_se);
+
+	/*
 	 * If p is throttled, we do nothing. In fact, if it exhausted
 	 * its budget it needs a replenishment and, since it now is on
 	 * its rq, the bandwidth timer callback (which clearly has not
-- 
2.9.3

Re: [PATCH V2 2/2] sched/deadline: Throttle a constrained deadline task activated after the deadline

[Tommaso Cucinotta]

On 13/02/2017 20:05, Daniel Bristot de Oliveira wrote:
> To avoid this problem, in the activation of a constrained deadline
> task after the deadline but before the next period, throttle the
> task and set the replenishing timer to the begin of the next period,
> unless it is boosted.

my only comment is that, by throttling on (dl < wakeuptime < period), we force the app to sync its activation time with the kernel, and the cbs doesn't self-sync anymore with the app own periodicity, which is what normally happens with dl=period. With dl=period, we loose the cbs self-sync and we force the app to sync with the kernel periodic timer only if we use explicitly yield(), but now this becomes also implicit just if we set dl<period.

> 	attr.sched_policy   = SCHED_DEADLINE;
> 	attr.sched_runtime  = 2 * 1000 * 1000;		/* 2 ms */
> 	attr.sched_deadline = 2 * 1000 * 1000;		/* 2 ms */
> 	attr.sched_period   = 2 * 1000 * 1000 * 1000;	/* 2 s */
...
> On my box, this reproducer uses almost 50% of the CPU time, which is
> obviously wrong for a task with 2/2000 reservation.

just a note here: in this example of runtime=deadline=2ms, shall we rely
on a utilization-based test, then we should assume the task is taking 100%.
More precise tests for EDF with deadline<period would properly count the
1998ms/2000ms free space, instead.

my2c,

	T.
-- 
Tommaso Cucinotta, Computer Engineering PhD
Associate Professor at the Real-Time Systems Laboratory (ReTiS)
Scuola Superiore Sant'Anna, Pisa, Italy
http://retis.sssup.it/people/tommaso

Re: [PATCH V2 2/2] sched/deadline: Throttle a constrained deadline task activated after the deadline

[Daniel Bristot de Oliveira]

On 02/14/2017 04:54 PM, Tommaso Cucinotta wrote:
> On 13/02/2017 20:05, Daniel Bristot de Oliveira wrote:
>> To avoid this problem, in the activation of a constrained deadline
>> task after the deadline but before the next period, throttle the
>> task and set the replenishing timer to the begin of the next period,
>> unless it is boosted.
> 
> my only comment is that, by throttling on (dl < wakeuptime < period), we
> force the app to sync its activation time with the kernel, and the cbs
> doesn't self-sync anymore with the app own periodicity, which is what
> normally happens with dl=period. With dl=period, we loose the cbs
> self-sync and we force the app to sync with the kernel periodic timer
> only if we use explicitly yield(), but now this becomes also implicit
> just if we set dl<period.

I see your point. However, that will happen only if, for some external
fact or imprecision, the task wakes up with a minimum inter-arrival time
smaller than the dl_period. In such case, IMHO the user must be aware of
the miss behavior or imprecision of the task/method which activates the
task and set an appropriate/safer smaller dl_period.

Furthermore, (correct me if I am wrong...) CBS will self-sync implicit
deadline tasks which did not consume all its previous runtime. Because,
if the runtime was consumed, the wake-up will fall in the same case I am
making constrained tasks to fall - the task will be throttled until the
next replenishment, after the next period.

The idea is to simulate sched_yield(). By suspending itself further than
the deadline, the task either has timing problems, or it wants to
suspend itself until the next activation, like calling sched_yeild(),
but allowing itself to be sporadic (to be activated after the minimum
inter-arrival time).

> 
>>     attr.sched_policy   = SCHED_DEADLINE;
>>     attr.sched_runtime  = 2 * 1000 * 1000;        /* 2 ms */
>>     attr.sched_deadline = 2 * 1000 * 1000;        /* 2 ms */
>>     attr.sched_period   = 2 * 1000 * 1000 * 1000;    /* 2 s */
> ...
>> On my box, this reproducer uses almost 50% of the CPU time, which is
>> obviously wrong for a task with 2/2000 reservation.
> 
> just a note here: in this example of runtime=deadline=2ms, shall we rely
> on a utilization-based test, then we should assume the task is taking 100%.
> More precise tests for EDF with deadline<period would properly count the
> 1998ms/2000ms free space, instead.

Yeah, it is taking 100% for runtime/deadline. But the admission is
runtime/period, so it will pass. The idea of runtime=deadline is to
avoid the task being throttled. If the task is throttle we would not be
able to demonstrate this bug. Anyway, we can set runtime = (0.95 *
deadline), it will also reproduce the problem, as long as the task is
put to sleep before being throttled.

Thanks!
-- Daniel

Re: [PATCH V2 2/2] sched/deadline: Throttle a constrained deadline task activated after the deadline

[Steven Rostedt]

On Mon, 13 Feb 2017 20:05:58 +0100
Daniel Bristot de Oliveira <bristot@redhat.com> wrote:

> During the activation, CBS checks if it can reuse the current task's
> runtime and period. If the deadline of the task is in the past, CBS
> cannot use the runtime, and so it replenishes the task. This rule
> works fine for implicit deadline tasks (deadline == period), and the
> CBS was designed for implicit deadline tasks. However, a task with
> constrained deadline (deadine < period) might be awakened after the
> deadline, but before the next period. In this case, replenishing the
> task would allow it to run for runtime / deadline. As in this case
> deadline < period, CBS enables a task to run for more than the
> runtime / period. In a very load system, this can cause the domino
> effect, making other tasks to miss their deadlines.
> 
> To avoid this problem, in the activation of a constrained deadline
> task after the deadline but before the next period, throttle the
> task and set the replenishing timer to the begin of the next period,
> unless it is boosted.
> 
> Reproducer:
> 
>  --------------- %< ---------------
>   int main (int argc, char **argv)
>   {
> 	int ret;
> 	int flags = 0;
> 	unsigned long l = 0;
> 	struct timespec ts;
> 	struct sched_attr attr;
> 
> 	memset(&attr, 0, sizeof(attr));
> 	attr.size = sizeof(attr);
> 
> 	attr.sched_policy   = SCHED_DEADLINE;
> 	attr.sched_runtime  = 2 * 1000 * 1000;		/* 2 ms */
> 	attr.sched_deadline = 2 * 1000 * 1000;		/* 2 ms */
> 	attr.sched_period   = 2 * 1000 * 1000 * 1000;	/* 2 s */
> 
> 	ts.tv_sec = 0;
> 	ts.tv_nsec = 2000 * 1000;			/* 2 ms */
> 
> 	ret = sched_setattr(0, &attr, flags);
> 
> 	if (ret < 0) {
> 		perror("sched_setattr");
> 		exit(-1);
> 	}
> 
> 	for(;;) {
> 		/* XXX: you may need to adjust the loop */
> 		for (l = 0; l < 150000; l++);
> 		/*
> 		 * The ideia is to go to sleep right before the deadline
> 		 * and then wake up before the next period to receive
> 		 * a new replenishment.
> 		 */
> 		nanosleep(&ts, NULL);
> 	}
> 
> 	exit(0);
>   }
>   --------------- >% ---------------  
> 
> On my box, this reproducer uses almost 50% of the CPU time, which is
> obviously wrong for a task with 2/2000 reservation.
> 
> Signed-off-by: Daniel Bristot de Oliveira <bristot@redhat.com>
> Cc: Ingo Molnar <mingo@redhat.com>
> Cc: Peter Zijlstra <peterz@infradead.org>
> Cc: Juri Lelli <juri.lelli@arm.com>
> Cc: Tommaso Cucinotta <tommaso.cucinotta@sssup.it>
> Cc: Luca Abeni <luca.abeni@santannapisa.it>
> Cc: Steven Rostedt <rostedt@goodmis.org>
> Cc: Mike Galbraith <efault@gmx.de>
> Cc: Romulo Silva de Oliveira <romulo.deoliveira@ufsc.br>
> Cc: linux-kernel@vger.kernel.org
> 

Reviewed-by: Steven Rostedt (VMware) <rostedt@goodmis.org>

-- Steve

[PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow

[Steven Rostedt (VMware)]

I was testing Daniel's changes with his test case, and tweaked it a
little. Instead of having the runtime equal to the deadline, I
increased the deadline ten fold.

Daniel's test case had:

	attr.sched_runtime  = 2 * 1000 * 1000;		/* 2 ms */
	attr.sched_deadline = 2 * 1000 * 1000;		/* 2 ms */
	attr.sched_period   = 2 * 1000 * 1000 * 1000;	/* 2 s */

To make it more interesting, I changed it to:

	attr.sched_runtime  =  2 * 1000 * 1000;		/* 2 ms */
	attr.sched_deadline = 20 * 1000 * 1000;		/* 20 ms */
	attr.sched_period   =  2 * 1000 * 1000 * 1000;	/* 2 s */


The results were rather surprising. The behavior that Daniel's patch
was fixing came back. The task started using much more than .1% of the
CPU. More like 20%.

Looking into this I 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.

  runtime / (deadline - t) > dl_runtime / dl_period

There's even a comment mentioning this, and saying that when relative
deadline equals relative period, that the equation is the same as using
deadline instead of period. That comment is backwards! What we really
want is:

  runtime / (deadline - t) > dl_runtime / dl_deadline

We care about if the runtime can make its deadline, not its period. And
then we can say "when the deadline equals the period, the equation is
the same as using dl_period instead of dl_deadline".

After correcting this, now when the task gets enqueued, it can throttle
correctly, and Daniel's fix to the throttling of sleeping deadline
tasks works even when the runtime and deadline are not the same.

Signed-off-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
---
Index: linux-trace.git/kernel/sched/deadline.c
===================================================================
--- linux-trace.git.orig/kernel/sched/deadline.c
+++ linux-trace.git/kernel/sched/deadline.c
@@ -445,13 +445,13 @@ static void replenish_dl_entity(struct s
  *
  * This function returns true if:
  *
- *   runtime / (deadline - t) > dl_runtime / dl_period ,
+ *   runtime / (deadline - t) > dl_runtime / dl_deadline ,
  *
  * IOW we can't recycle current parameters.
  *
- * Notice that the bandwidth check is done against the period. For
+ * Notice that the bandwidth check is done against the deadline. For
  * task with deadline equal to period this is the same of using
- * dl_deadline instead of dl_period in the equation above.
+ * dl_period instead of dl_deadline in the equation above.
  */
 static bool dl_entity_overflow(struct sched_dl_entity *dl_se,
 			       struct sched_dl_entity *pi_se, u64 t)
@@ -476,7 +476,7 @@ static bool dl_entity_overflow(struct sc
 	 * of anything below microseconds resolution is actually fiction
 	 * (but still we want to give the user that illusion >;).
 	 */
-	left = (pi_se->dl_period >> DL_SCALE) * (dl_se->runtime >> DL_SCALE);
+	left = (pi_se->dl_deadline >> DL_SCALE) * (dl_se->runtime >> DL_SCALE);
 	right = ((dl_se->deadline - t) >> DL_SCALE) *
 		(pi_se->dl_runtime >> DL_SCALE);
 

Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow

[luca abeni]

Hi Steven,

On Tue, 14 Feb 2017 14:28:48 -0500
"Steven Rostedt (VMware)" <rostedt@goodmis.org> wrote:

> I was testing Daniel's changes with his test case, and tweaked it a
> little. Instead of having the runtime equal to the deadline, I
> increased the deadline ten fold.
> 
> Daniel's test case had:
> 
> 	attr.sched_runtime  = 2 * 1000 * 1000;		/* 2 ms
> */ attr.sched_deadline = 2 * 1000 * 1000;		/* 2 ms */
> 	attr.sched_period   = 2 * 1000 * 1000 * 1000;	/* 2 s */
> 
> To make it more interesting, I changed it to:
> 
> 	attr.sched_runtime  =  2 * 1000 * 1000;		/* 2
> ms */ attr.sched_deadline = 20 * 1000 * 1000;		/* 20 ms
> */ attr.sched_period   =  2 * 1000 * 1000 * 1000;	/* 2 s */
> 
> 
> The results were rather surprising. The behavior that Daniel's patch
> was fixing came back. The task started using much more than .1% of the
> CPU. More like 20%.
> 
> Looking into this I 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.
> 
>   runtime / (deadline - t) > dl_runtime / dl_period

I agree that there is an inconsistency here (again, using equations
from the "period=deadline" case with a relative deadline different from
period).

I am not sure about the correct fix (wouldn't
"runtime / (deadline - t) > dl_runtime / dl_deadline" allow the task to
use a fraction of CPU time equal to dl_runtime / dl_deadline?)

The current code is clearly wrong (as shown by Daniel), but I do not
understand how the current check can allow the task to consume more
than dl_runtime / dl_period... I need some more time to think about
this issue. 


				Luca
> 
> There's even a comment mentioning this, and saying that when relative
> deadline equals relative period, that the equation is the same as
> using deadline instead of period. That comment is backwards! What we
> really want is:
> 
>   runtime / (deadline - t) > dl_runtime / dl_deadline
> 
> We care about if the runtime can make its deadline, not its period.
> And then we can say "when the deadline equals the period, the
> equation is the same as using dl_period instead of dl_deadline".
> 
> After correcting this, now when the task gets enqueued, it can
> throttle correctly, and Daniel's fix to the throttling of sleeping
> deadline tasks works even when the runtime and deadline are not the
> same.
> 
> Signed-off-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
> ---
> Index: linux-trace.git/kernel/sched/deadline.c
> ===================================================================
> --- linux-trace.git.orig/kernel/sched/deadline.c
> +++ linux-trace.git/kernel/sched/deadline.c
> @@ -445,13 +445,13 @@ static void replenish_dl_entity(struct s
>   *
>   * This function returns true if:
>   *
> - *   runtime / (deadline - t) > dl_runtime / dl_period ,
> + *   runtime / (deadline - t) > dl_runtime / dl_deadline ,
>   *
>   * IOW we can't recycle current parameters.
>   *
> - * Notice that the bandwidth check is done against the period. For
> + * Notice that the bandwidth check is done against the deadline. For
>   * task with deadline equal to period this is the same of using
> - * dl_deadline instead of dl_period in the equation above.
> + * dl_period instead of dl_deadline in the equation above.
>   */
>  static bool dl_entity_overflow(struct sched_dl_entity *dl_se,
>  			       struct sched_dl_entity *pi_se, u64 t)
> @@ -476,7 +476,7 @@ static bool dl_entity_overflow(struct sc
>  	 * of anything below microseconds resolution is actually
> fiction
>  	 * (but still we want to give the user that illusion >;).
>  	 */
> -	left = (pi_se->dl_period >> DL_SCALE) * (dl_se->runtime >>
> DL_SCALE);
> +	left = (pi_se->dl_deadline >> DL_SCALE) * (dl_se->runtime >>
> DL_SCALE); right = ((dl_se->deadline - t) >> DL_SCALE) *
>  		(pi_se->dl_runtime >> DL_SCALE);
>  

Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow

[Steven Rostedt]

On Tue, 14 Feb 2017 23:49:26 +0100
luca abeni <luca.abeni@santannapisa.it> wrote:

> Hi Steven,
> 
> On Tue, 14 Feb 2017 14:28:48 -0500
> "Steven Rostedt (VMware)" <rostedt@goodmis.org> wrote:
> 
> > I was testing Daniel's changes with his test case, and tweaked it a
> > little. Instead of having the runtime equal to the deadline, I
> > increased the deadline ten fold.
> > 
> > Daniel's test case had:
> > 
> > 	attr.sched_runtime  = 2 * 1000 * 1000;		/* 2 ms
> > */ attr.sched_deadline = 2 * 1000 * 1000;		/* 2 ms */
> > 	attr.sched_period   = 2 * 1000 * 1000 * 1000;	/* 2 s */
> > 
> > To make it more interesting, I changed it to:
> > 
> > 	attr.sched_runtime  =  2 * 1000 * 1000;		/* 2
> > ms */ attr.sched_deadline = 20 * 1000 * 1000;		/* 20 ms
> > */ attr.sched_period   =  2 * 1000 * 1000 * 1000;	/* 2 s */
> > 
> > 
> > The results were rather surprising. The behavior that Daniel's patch
> > was fixing came back. The task started using much more than .1% of the
> > CPU. More like 20%.
> > 
> > Looking into this I 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.
> > 
> >   runtime / (deadline - t) > dl_runtime / dl_period  
> 
> I agree that there is an inconsistency here (again, using equations
> from the "period=deadline" case with a relative deadline different from
> period).
> 
> I am not sure about the correct fix (wouldn't
> "runtime / (deadline - t) > dl_runtime / dl_deadline" allow the task to
> use a fraction of CPU time equal to dl_runtime / dl_deadline?)
> 
> The current code is clearly wrong (as shown by Daniel), but I do not
> understand how the current check can allow the task to consume more
> than dl_runtime / dl_period... I need some more time to think about
> this issue. 
> 

This is in dl_entity_overflow() which is called by update_dl_entity()
which has this:

	if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
	    dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
		dl_se->runtime = pi_se->dl_runtime;
	}


The comments in this code state:

 * The policy here is that we update the deadline of the entity only if:
 *  - the current deadline is in the past,
 *  - using the remaining runtime with the current deadline would make
 *    the entity exceed its bandwidth.

That second comment is saying that when this task woke up, if the
percentage left to run will exceed its bandwidth with the rest of the
system then reset its deadline and its runtime.

What happens in the current logic, is that overflow() check says, when
the deadline is much smaller than the period, "yeah, we're going to
exceed our percentage!" so give us more, even though it wont exceed its
percentage if we compared runtime with deadline.

The relative-runtime / relative-period is a tiny percentage, which does
not reflect the percentage that the task is allowed to have before the
deadline is hit. The tasks bandwidth should be calculated by the
relative-runtime / relative-deadline, as runtime <= deadline <= period,
and the runtime should happen within the deadline.

When the task wakes up, it currently looks at how much time is left
absolute-deadline - t, and compares it to the amount of runtime left.
The percentage allowed should still be compared with the percentage
between relative-runtime and relative-deadline. The relative-period or
even absolute-period, should have no influence in this decision.

-- Steve

Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow

[Luca Abeni]

Hi Steven,

On Tue, 14 Feb 2017 19:14:17 -0500
Steven Rostedt <rostedt@goodmis.org> wrote:
[...]
> > I am not sure about the correct fix (wouldn't
> > "runtime / (deadline - t) > dl_runtime / dl_deadline" allow the
> > task to use a fraction of CPU time equal to dl_runtime /
> > dl_deadline?)
> > 
> > The current code is clearly wrong (as shown by Daniel), but I do not
> > understand how the current check can allow the task to consume more
> > than dl_runtime / dl_period... I need some more time to think about
> > this issue. 
> >   
> 
> This is in dl_entity_overflow() which is called by update_dl_entity()
> which has this:
> 
> 	if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
> 	    dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
> 		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
> 		dl_se->runtime = pi_se->dl_runtime;
> 	}
> 
> 
> The comments in this code state:
> 
>  * The policy here is that we update the deadline of the entity only
> if:
>  *  - the current deadline is in the past,
>  *  - using the remaining runtime with the current deadline would make
>  *    the entity exceed its bandwidth.
> 
> That second comment is saying that when this task woke up, if the
> percentage left to run will exceed its bandwidth with the rest of the
> system then reset its deadline and its runtime.

Right; this is the problem. When the relative deadline is different
from the period, the term "bandwidth" is ambiguous... We can consider
the utilisation (maximum runtime / period), or the density (maximum
runtime / relative deadline). In some sense, the two approaches are
both correct (if we use density, we are more pessimistic but we try to
respect deadlines in a hard way; if we use utilisation, we allow more
tasks to be admitted but we can only provide bounded tardiness).

What the current code is doing is to mix the two approaches (resulting
in a wrong runtime/deadline assignment).

> What happens in the current logic, is that overflow() check says, when
> the deadline is much smaller than the period, "yeah, we're going to
> exceed our percentage!" so give us more, even though it wont exceed
> its percentage if we compared runtime with deadline.
> 
> The relative-runtime / relative-period is a tiny percentage, which
> does not reflect the percentage that the task is allowed to have
> before the deadline is hit. The tasks bandwidth should be calculated
> by the relative-runtime / relative-deadline, as runtime <= deadline
> <= period, and the runtime should happen within the deadline.
> 
> When the task wakes up, it currently looks at how much time is left
> absolute-deadline - t, and compares it to the amount of runtime left.
> The percentage allowed should still be compared with the percentage
> between relative-runtime and relative-deadline. The relative-period or
> even absolute-period, should have no influence in this decision.

Ok, thanks; I think I can now see why this can result in a task
consuming more than the reserved utilisation. I still need some time to
convince me that "runtime / (deadline - t) > dl_runtime / dl_deadline"
is the correct check to use (in this case, shouldn't we also change the
admission test to use densities instead of utilisations?)



			Thanks,
				Luca

Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow

[Juri Lelli]

Hi,

On 15/02/17 08:40, Luca Abeni wrote:
> Hi Steven,
> 
> On Tue, 14 Feb 2017 19:14:17 -0500
> Steven Rostedt <rostedt@goodmis.org> wrote:
> [...]
> > > I am not sure about the correct fix (wouldn't
> > > "runtime / (deadline - t) > dl_runtime / dl_deadline" allow the
> > > task to use a fraction of CPU time equal to dl_runtime /
> > > dl_deadline?)
> > > 
> > > The current code is clearly wrong (as shown by Daniel), but I do not
> > > understand how the current check can allow the task to consume more
> > > than dl_runtime / dl_period... I need some more time to think about
> > > this issue. 
> > >   
> > 
> > This is in dl_entity_overflow() which is called by update_dl_entity()
> > which has this:
> > 
> > 	if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
> > 	    dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
> > 		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
> > 		dl_se->runtime = pi_se->dl_runtime;
> > 	}
> > 
> > 
> > The comments in this code state:
> > 
> >  * The policy here is that we update the deadline of the entity only
> > if:
> >  *  - the current deadline is in the past,
> >  *  - using the remaining runtime with the current deadline would make
> >  *    the entity exceed its bandwidth.
> > 
> > That second comment is saying that when this task woke up, if the
> > percentage left to run will exceed its bandwidth with the rest of the
> > system then reset its deadline and its runtime.
> 
> Right; this is the problem. When the relative deadline is different
> from the period, the term "bandwidth" is ambiguous... We can consider
> the utilisation (maximum runtime / period), or the density (maximum
> runtime / relative deadline). In some sense, the two approaches are
> both correct (if we use density, we are more pessimistic but we try to
> respect deadlines in a hard way; if we use utilisation, we allow more
> tasks to be admitted but we can only provide bounded tardiness).
> 
> What the current code is doing is to mix the two approaches (resulting
> in a wrong runtime/deadline assignment).
> 
> > What happens in the current logic, is that overflow() check says, when
> > the deadline is much smaller than the period, "yeah, we're going to
> > exceed our percentage!" so give us more, even though it wont exceed
> > its percentage if we compared runtime with deadline.
> > 
> > The relative-runtime / relative-period is a tiny percentage, which
> > does not reflect the percentage that the task is allowed to have
> > before the deadline is hit. The tasks bandwidth should be calculated
> > by the relative-runtime / relative-deadline, as runtime <= deadline
> > <= period, and the runtime should happen within the deadline.
> > 
> > When the task wakes up, it currently looks at how much time is left
> > absolute-deadline - t, and compares it to the amount of runtime left.
> > The percentage allowed should still be compared with the percentage
> > between relative-runtime and relative-deadline. The relative-period or
> > even absolute-period, should have no influence in this decision.
> 
> Ok, thanks; I think I can now see why this can result in a task
> consuming more than the reserved utilisation. I still need some time to
> convince me that "runtime / (deadline - t) > dl_runtime / dl_deadline"
> is the correct check to use (in this case, shouldn't we also change the
> admission test to use densities instead of utilisations?)
> 

Right, this is what I was wondering as well, as dl_overflow() currently
looks at the period. And I also have some recollection of this
discussion happening already in the past, unfortunately it was not on
the list.

That discussion started with the following patch

--->8---
>From 6cd9b6f3c2b9f144828aa09ad2a355b00a153348 Mon Sep 17 00:00:00 2001
From: Juri Lelli <juri.lelli@arm.com>
Date: Fri, 4 Sep 2015 15:41:42 +0100
Subject: [PATCH] sched/core: fix SCHED_DEADLINE admission control

As Documentation/sched/sched-deadline.txt says, a new task can pass
through admission control if sum(WCET_i / min{D_i, P_i}) <= 1.
However, if the user specifies both sched_period and sched_deadline,
we actually check that sum(WCET_i / P_i) <= 1; and this is a less
restrictive check w.r.t. the former.

Fix this by always using sched_deadline parameter to compute new_bw,
as we also impose that runtime <= deadline <= period (if period != 0)
and deadline != 0.

Fixes: 4df1638cfaf9 ("sched/deadline: Fix overflow to handle period==0 and deadline!=0")
Signed-off-by: Juri Lelli <juri.lelli@arm.com>
---
 kernel/sched/core.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 096b73b..56bc449 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -2302,9 +2302,9 @@ static int dl_overflow(struct task_struct *p, int policy,
 {
 
 	struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
-	u64 period = attr->sched_period ?: attr->sched_deadline;
+	u64 deadline = attr->sched_deadline;
 	u64 runtime = attr->sched_runtime;
-	u64 new_bw = dl_policy(policy) ? to_ratio(period, runtime) : 0;
+	u64 new_bw = dl_policy(policy) ? to_ratio(deadline, runtime) : 0;
 	int cpus, err = -1;
 
 	if (new_bw == p->dl.dl_bw)
--->8---

that we then dediced not to propose since (note that these are just my
memories of the dicussion, so everything it's up for further discussion,
also in light of the problem highlighted by Daniel)

 - SCHED_DEADLINE, as the documentation says, does AC using utilization
 - it is however true that a sufficient (but not necessary) test on UP for
   D_i != P_i cases is the one of my patch above
 - we have agreed in the past that the kernel should only check that we
   don't cause "overload" in the system (which is still the case if we
   consider utilizations), not "hard schedulability"
 - also because on SMP systems "sum(WCET_i / min{D_i, P_i}) <= M"
   doesn't guarantee much more than the test base on P_i only (there not
   seem to be many/any papers around considering the D_i != P_i case on
   SMP actually)
 - basically the patch above would only matter for the UP/partitioned
   cases

Thoughts?

Thanks,

- Juri

Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow

[Peter Zijlstra]

On Wed, Feb 15, 2017 at 10:29:19AM +0000, Juri Lelli wrote:

> that we then dediced not to propose since (note that these are just my
> memories of the dicussion, so everything it's up for further discussion,
> also in light of the problem highlighted by Daniel)
> 
>  - SCHED_DEADLINE, as the documentation says, does AC using utilization
>  - it is however true that a sufficient (but not necessary) test on UP for
>    D_i != P_i cases is the one of my patch above
>  - we have agreed in the past that the kernel should only check that we
>    don't cause "overload" in the system (which is still the case if we
>    consider utilizations), not "hard schedulability"
>  - also because on SMP systems "sum(WCET_i / min{D_i, P_i}) <= M"
>    doesn't guarantee much more than the test base on P_i only (there not
>    seem to be many/any papers around considering the D_i != P_i case on
>    SMP actually)
>  - basically the patch above would only matter for the UP/partitioned
>    cases
> 
> Thoughts?

I think that this makes sense. Keep the kernel AC such that the working
set is 'recoverable' was I think the word Tommaso used last time.

I've been meaning to play with his suggested AC for arbitrary affinities
but haven't managed to find time yet. My biggest attraction to that is
that it would allow de-coupling it from the root_domain thingy and
side-step the problems we currently have with that.

Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow

[Luca Abeni]

Hi Juri,

On Wed, 15 Feb 2017 10:29:19 +0000
Juri Lelli <juri.lelli@arm.com> wrote:
[...]
> > Ok, thanks; I think I can now see why this can result in a task
> > consuming more than the reserved utilisation. I still need some
> > time to convince me that "runtime / (deadline - t) > dl_runtime /
> > dl_deadline" is the correct check to use (in this case, shouldn't
> > we also change the admission test to use densities instead of
> > utilisations?) 
> 
> Right, this is what I was wondering as well, as dl_overflow()
> currently looks at the period. And I also have some recollection of
> this discussion happening already in the past, unfortunately it was
> not on the list.
> 
> That discussion started with the following patch
[...]
> that we then dediced not to propose since (note that these are just my
> memories of the dicussion, so everything it's up for further
> discussion, also in light of the problem highlighted by Daniel)
> 
>  - SCHED_DEADLINE, as the documentation says, does AC using
> utilization
>  - it is however true that a sufficient (but not necessary) test on
> UP for D_i != P_i cases is the one of my patch above
>  - we have agreed in the past that the kernel should only check that
> we don't cause "overload" in the system (which is still the case if we
>    consider utilizations), not "hard schedulability"
I remember a similar discussion; I think the decision about what to do
depends on what are the requirements: hard deadline guarantees (but in
this case global EDF is just a bad choice) or tardines no overload
guarantees?

My understanding was that the kernel guarantees that deadline tasks
will not starve non-deadline tasks, and that there is an upper bound
for the tardiness experienced by deadline tasks. If this understanding
is correct, then the current admission test is ok. But if I
misunderstood the purpose of the kernel admission test, then maybe your
patch is ok.

Then, it is important to keep the admission test consistent with the
checks performed in dl_entity_overflow() (but whatever we decide to do,
dl_entity_overflow() should be fixed).


				Luca

>  - also because on SMP systems "sum(WCET_i / min{D_i, P_i}) <= M"
>    doesn't guarantee much more than the test base on P_i only (there
> not seem to be many/any papers around considering the D_i != P_i case
> on SMP actually)
>  - basically the patch above would only matter for the UP/partitioned
>    cases
> 
> Thoughts?
> 
> Thanks,
> 
> - Juri

Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow

[Juri Lelli]

On 15/02/17 13:31, Luca Abeni wrote:
> Hi Juri,
> 
> On Wed, 15 Feb 2017 10:29:19 +0000
> Juri Lelli <juri.lelli@arm.com> wrote:
> [...]
> > > Ok, thanks; I think I can now see why this can result in a task
> > > consuming more than the reserved utilisation. I still need some
> > > time to convince me that "runtime / (deadline - t) > dl_runtime /
> > > dl_deadline" is the correct check to use (in this case, shouldn't
> > > we also change the admission test to use densities instead of
> > > utilisations?) 
> > 
> > Right, this is what I was wondering as well, as dl_overflow()
> > currently looks at the period. And I also have some recollection of
> > this discussion happening already in the past, unfortunately it was
> > not on the list.
> > 
> > That discussion started with the following patch
> [...]
> > that we then dediced not to propose since (note that these are just my
> > memories of the dicussion, so everything it's up for further
> > discussion, also in light of the problem highlighted by Daniel)
> > 
> >  - SCHED_DEADLINE, as the documentation says, does AC using
> > utilization
> >  - it is however true that a sufficient (but not necessary) test on
> > UP for D_i != P_i cases is the one of my patch above
> >  - we have agreed in the past that the kernel should only check that
> > we don't cause "overload" in the system (which is still the case if we
> >    consider utilizations), not "hard schedulability"
> I remember a similar discussion; I think the decision about what to do
> depends on what are the requirements: hard deadline guarantees (but in
> this case global EDF is just a bad choice) or tardines no overload
> guarantees?
> 
> My understanding was that the kernel guarantees that deadline tasks
> will not starve non-deadline tasks, and that there is an upper bound
> for the tardiness experienced by deadline tasks. If this understanding
> is correct, then the current admission test is ok. But if I
> misunderstood the purpose of the kernel admission test, then maybe your
> patch is ok.
> 
> Then, it is important to keep the admission test consistent with the
> checks performed in dl_entity_overflow() (but whatever we decide to do,
> dl_entity_overflow() should be fixed).
> 

I'm sorry, but I'm a bit lost. :(

Why do you say 'whatever we decide to do'?

In my understanding:

 - if we decide AC shouldn't change (as we care about not-starving
   others and having bounded tardiness), then I'd say dl_entity_overflow
   shouldn't change as well, since it's using dl_runtime/dl_period as
   'static bandwidth' (as AC does)
 
 - if we instead move to use densities when doing AC (dl_runtime/dl_
   deadline), I think we should also change the check in dl_entity_
   overflow, as Steve is proposing

 - in both cases Daniel's fixes look sensible to have

Where am I wrong? :)

Actually, another thing that we noticed, talking on IRC with Peter, is
that we seem to be replenishing differently on different occasions:

 - on wakeup (if overflowing) we do

   dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
   dl_se->runtime = pi_se->dl_runtime;

 - when the replenishment timer fires (un-thottle and with runtime < 0)

   dl_se->deadline += pi_se->dl_period;
   dl_se->runtime += pi_se->dl_runtime;

Isn't this problematic as well?

Thanks,

- Juri

Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow

[Luca Abeni]

On Wed, 15 Feb 2017 12:59:25 +0000
Juri Lelli <juri.lelli@arm.com> wrote:

> On 15/02/17 13:31, Luca Abeni wrote:
> > Hi Juri,
> > 
> > On Wed, 15 Feb 2017 10:29:19 +0000
> > Juri Lelli <juri.lelli@arm.com> wrote:
> > [...]  
> > > > Ok, thanks; I think I can now see why this can result in a task
> > > > consuming more than the reserved utilisation. I still need some
> > > > time to convince me that "runtime / (deadline - t) >
> > > > dl_runtime / dl_deadline" is the correct check to use (in this
> > > > case, shouldn't we also change the admission test to use
> > > > densities instead of utilisations?)   
> > > 
> > > Right, this is what I was wondering as well, as dl_overflow()
> > > currently looks at the period. And I also have some recollection
> > > of this discussion happening already in the past, unfortunately
> > > it was not on the list.
> > > 
> > > That discussion started with the following patch  
> > [...]  
> > > that we then dediced not to propose since (note that these are
> > > just my memories of the dicussion, so everything it's up for
> > > further discussion, also in light of the problem highlighted by
> > > Daniel)
> > > 
> > >  - SCHED_DEADLINE, as the documentation says, does AC using
> > > utilization
> > >  - it is however true that a sufficient (but not necessary) test
> > > on UP for D_i != P_i cases is the one of my patch above
> > >  - we have agreed in the past that the kernel should only check
> > > that we don't cause "overload" in the system (which is still the
> > > case if we consider utilizations), not "hard schedulability"  
> > I remember a similar discussion; I think the decision about what to
> > do depends on what are the requirements: hard deadline guarantees
> > (but in this case global EDF is just a bad choice) or tardines no
> > overload guarantees?
> > 
> > My understanding was that the kernel guarantees that deadline tasks
> > will not starve non-deadline tasks, and that there is an upper bound
> > for the tardiness experienced by deadline tasks. If this
> > understanding is correct, then the current admission test is ok.
> > But if I misunderstood the purpose of the kernel admission test,
> > then maybe your patch is ok.
> > 
> > Then, it is important to keep the admission test consistent with the
> > checks performed in dl_entity_overflow() (but whatever we decide to
> > do, dl_entity_overflow() should be fixed).
> >   
> 
> I'm sorry, but I'm a bit lost. :(
> 
> Why do you say 'whatever we decide to do'?
> 
> In my understanding:
> 
>  - if we decide AC shouldn't change (as we care about not-starving
>    others and having bounded tardiness), then I'd say
> dl_entity_overflow shouldn't change as well, since it's using
> dl_runtime/dl_period as 'static bandwidth' (as AC does)

Yes, but it is comparing dl_runtime/dl_period with
runtime/(deadline-t), mixing different things. I still need to think
more about this, but I think it should either compare
runtime/(deadline-t) with dl_runtime/dl_deadline or
runtime/(end_of_reservation_period-t) with dl_runtime/dl_period...
Otherwise we risk to have issues as shown by Daniel and Steven.


>  - if we instead move to use densities when doing AC (dl_runtime/dl_
>    deadline), I think we should also change the check in dl_entity_
>    overflow, as Steve is proposing
> 
>  - in both cases Daniel's fixes look sensible to have
Yes, Daniel's fixes fix a possible DoS, so they should go in... Then,
we can decide how to improve the situation.

> 
> Where am I wrong? :)
> 
> Actually, another thing that we noticed, talking on IRC with Peter, is
> that we seem to be replenishing differently on different occasions:
> 
>  - on wakeup (if overflowing) we do
> 
>    dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
>    dl_se->runtime = pi_se->dl_runtime;
> 
>  - when the replenishment timer fires (un-thottle and with runtime <
> 0)
> 
>    dl_se->deadline += pi_se->dl_period;
>    dl_se->runtime += pi_se->dl_runtime;
> 
> Isn't this problematic as well?
I _think_ this is correct, because they are two different things: in
the first case, we generate a new scheduling deadline starting from
current time (so, the deadline must be computed based on the relative
deadline); in the second case, we postpone an existing scheduling
deadline (so, it must be postponed by one period)[*]... No? Or am I
misunderstanding the issue you saw?


				Thanks,
					Luca

[*] Notice that with Daniel's fix the replenishment timer fires at the
end of the reservation period (or, at the beginning of a new
reservation period). So, "current time + dl_deadline" is about equal to
"deadline + period" (but using "current time + dl_deadline" would
generate larger deadlines if the timer fires later than expected).

Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow

[Juri Lelli]

On 15/02/17 14:13, Luca Abeni wrote:
> On Wed, 15 Feb 2017 12:59:25 +0000
> Juri Lelli <juri.lelli@arm.com> wrote:
> 
> > On 15/02/17 13:31, Luca Abeni wrote:
> > > Hi Juri,
> > > 
> > > On Wed, 15 Feb 2017 10:29:19 +0000
> > > Juri Lelli <juri.lelli@arm.com> wrote:
> > > [...]  
> > > > > Ok, thanks; I think I can now see why this can result in a task
> > > > > consuming more than the reserved utilisation. I still need some
> > > > > time to convince me that "runtime / (deadline - t) >
> > > > > dl_runtime / dl_deadline" is the correct check to use (in this
> > > > > case, shouldn't we also change the admission test to use
> > > > > densities instead of utilisations?)   
> > > > 
> > > > Right, this is what I was wondering as well, as dl_overflow()
> > > > currently looks at the period. And I also have some recollection
> > > > of this discussion happening already in the past, unfortunately
> > > > it was not on the list.
> > > > 
> > > > That discussion started with the following patch  
> > > [...]  
> > > > that we then dediced not to propose since (note that these are
> > > > just my memories of the dicussion, so everything it's up for
> > > > further discussion, also in light of the problem highlighted by
> > > > Daniel)
> > > > 
> > > >  - SCHED_DEADLINE, as the documentation says, does AC using
> > > > utilization
> > > >  - it is however true that a sufficient (but not necessary) test
> > > > on UP for D_i != P_i cases is the one of my patch above
> > > >  - we have agreed in the past that the kernel should only check
> > > > that we don't cause "overload" in the system (which is still the
> > > > case if we consider utilizations), not "hard schedulability"  
> > > I remember a similar discussion; I think the decision about what to
> > > do depends on what are the requirements: hard deadline guarantees
> > > (but in this case global EDF is just a bad choice) or tardines no
> > > overload guarantees?
> > > 
> > > My understanding was that the kernel guarantees that deadline tasks
> > > will not starve non-deadline tasks, and that there is an upper bound
> > > for the tardiness experienced by deadline tasks. If this
> > > understanding is correct, then the current admission test is ok.
> > > But if I misunderstood the purpose of the kernel admission test,
> > > then maybe your patch is ok.
> > > 
> > > Then, it is important to keep the admission test consistent with the
> > > checks performed in dl_entity_overflow() (but whatever we decide to
> > > do, dl_entity_overflow() should be fixed).
> > >   
> > 
> > I'm sorry, but I'm a bit lost. :(
> > 
> > Why do you say 'whatever we decide to do'?
> > 
> > In my understanding:
> > 
> >  - if we decide AC shouldn't change (as we care about not-starving
> >    others and having bounded tardiness), then I'd say
> > dl_entity_overflow shouldn't change as well, since it's using
> > dl_runtime/dl_period as 'static bandwidth' (as AC does)
> 
> Yes, but it is comparing dl_runtime/dl_period with
> runtime/(deadline-t), mixing different things. I still need to think
> more about this, but I think it should either compare
> runtime/(deadline-t) with dl_runtime/dl_deadline or
> runtime/(end_of_reservation_period-t) with dl_runtime/dl_period...
> Otherwise we risk to have issues as shown by Daniel and Steven.

OK.

> 
> 
> >  - if we instead move to use densities when doing AC (dl_runtime/dl_
> >    deadline), I think we should also change the check in dl_entity_
> >    overflow, as Steve is proposing
> > 
> >  - in both cases Daniel's fixes look sensible to have
> Yes, Daniel's fixes fix a possible DoS, so they should go in... Then,
> we can decide how to improve the situation.
> 
> > 
> > Where am I wrong? :)
> > 
> > Actually, another thing that we noticed, talking on IRC with Peter, is
> > that we seem to be replenishing differently on different occasions:
> > 
> >  - on wakeup (if overflowing) we do
> > 
> >    dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
> >    dl_se->runtime = pi_se->dl_runtime;
> > 
> >  - when the replenishment timer fires (un-thottle and with runtime <
> > 0)
> > 
> >    dl_se->deadline += pi_se->dl_period;
> >    dl_se->runtime += pi_se->dl_runtime;
> > 
> > Isn't this problematic as well?
> I _think_ this is correct, because they are two different things: in
> the first case, we generate a new scheduling deadline starting from
> current time (so, the deadline must be computed based on the relative
> deadline); in the second case, we postpone an existing scheduling
> deadline (so, it must be postponed by one period)[*]... No? Or am I
> misunderstanding the issue you saw?
> 

No, what you are saying makes sense, we don't actually have a problem.

Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow

[Daniel Bristot de Oliveira]

On 02/15/2017 01:59 PM, Juri Lelli wrote:
> Actually, another thing that we noticed, talking on IRC with Peter, is
> that we seem to be replenishing differently on different occasions:

When a task is awakened (not by the replenishment timer), it is not
possible to know if the absolute deadline var stores the absolute
deadline of activation which took place in the instant
(current time) - dl_period.

Therefore, assuming the next deadline is one dl_deadline away from now
is correct.

IOW: that is a sporadic activation - the task is activated after at
least minimum inter-arrival time between activation/replenishment:

>  - on wakeup (if overflowing) we do
> 
>    dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
>    dl_se->runtime = pi_se->dl_runtime;


In the replenishment timer, it is known that the absolute deadline
instant of the previous activation is in the deadline var. So
putting the absolute deadline one dl_period away is correct [1].

Another point is that this case avoids creating time drift due
to latencies. For instance, in the case of a 1 ms delay of the timer
(interrupts disabled?), the wakeup replenishment would push the
absolute a relative deadline + 1 ms away from the previous deadline.

IOW: the replenishment timer makes the periodic case - a fixed time
offset from the previous activation/replenishment.

>  - when the replenishment timer fires (un-thottle and with runtime < 0)
> 
>    dl_se->deadline += pi_se->dl_period;
>    dl_se->runtime += pi_se->dl_runtime;

So I think it is correct. Am I missing something?

[1] For the sake of completeness:

- dl_se->deadline = Absolute deadline
- dl_se->dl_deadline = Relative deadline

the next absolute deadline is at:

dl_se->deadline = dl_next_period(dl_se) + dl_se->dl_deadline;

as dl_next_period(dl_se) is:

dl_se->deadline - dl_se->dl_deadline + dl_se->dl_period;

the next deadline is at:

dl_se->deadline = dl_se->deadline - dl_se->dl_deadline +
dl_se->dl_period + dl_se->dl_deadline

Which can be simplified to:

dl_se->deadline = dl_se->deadline += pi_se->dl_period;

because we have (- dl_se->dl_deadline) + dl_se->dl_deadline.

-- Daniel

Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow

[Daniel Bristot de Oliveira]

On 02/15/2017 02:33 PM, Daniel Bristot de Oliveira wrote:
> dl_se->deadline = dl_se->deadline += pi_se->dl_period;

ops, it should be:

dl_se->deadline = dl_se->deadline + pi_se->dl_period;

Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow

[Steven Rostedt]

On Wed, 15 Feb 2017 14:42:42 +0100
Daniel Bristot de Oliveira <bristot@redhat.com> wrote:

> On 02/15/2017 02:33 PM, Daniel Bristot de Oliveira wrote:
> > dl_se->deadline = dl_se->deadline += pi_se->dl_period;  
> 
> ops, it should be:
> 
> dl_se->deadline = dl_se->deadline + pi_se->dl_period;

or

 dl_se->deadline += pi_se->dl_period;

;-)

-- Steve

Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow

[Juri Lelli]

On 15/02/17 14:33, Daniel Bristot de Oliveira wrote:
> On 02/15/2017 01:59 PM, Juri Lelli wrote:
> > Actually, another thing that we noticed, talking on IRC with Peter, is
> > that we seem to be replenishing differently on different occasions:
> 
> When a task is awakened (not by the replenishment timer), it is not
> possible to know if the absolute deadline var stores the absolute
> deadline of activation which took place in the instant
> (current time) - dl_period.
> 
> Therefore, assuming the next deadline is one dl_deadline away from now
> is correct.
> 
> IOW: that is a sporadic activation - the task is activated after at
> least minimum inter-arrival time between activation/replenishment:
> 
> >  - on wakeup (if overflowing) we do
> > 
> >    dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
> >    dl_se->runtime = pi_se->dl_runtime;
> 
> 
> In the replenishment timer, it is known that the absolute deadline
> instant of the previous activation is in the deadline var. So
> putting the absolute deadline one dl_period away is correct [1].
> 
> Another point is that this case avoids creating time drift due
> to latencies. For instance, in the case of a 1 ms delay of the timer
> (interrupts disabled?), the wakeup replenishment would push the
> absolute a relative deadline + 1 ms away from the previous deadline.
> 
> IOW: the replenishment timer makes the periodic case - a fixed time
> offset from the previous activation/replenishment.
> 
> >  - when the replenishment timer fires (un-thottle and with runtime < 0)
> > 
> >    dl_se->deadline += pi_se->dl_period;
> >    dl_se->runtime += pi_se->dl_runtime;
> 
> So I think it is correct. Am I missing something?
> 

Nope, you are right, no problems here.

Thanks,

- Juri

Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow

[Tommaso Cucinotta]

On 15/02/2017 14:33, Daniel Bristot de Oliveira wrote:
> [1] For the sake of completeness:
> - dl_se->deadline = Absolute deadline
> - dl_se->dl_deadline = Relative deadline
Daniel's note [1] reminds me that, would it be worth a rename of these, for the sake of clarity, e.g.:
-) abs_deadline vs rel_deadline
-) runtime_left vs runtime_tot
or similar :-) ?

     T.

Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow

[Steven Rostedt]

On Thu, 16 Feb 2017 17:36:07 +0100
Tommaso Cucinotta <tommaso.cucinotta@santannapisa.it> wrote:

> On 15/02/2017 14:33, Daniel Bristot de Oliveira wrote:
> > [1] For the sake of completeness:
> > - dl_se->deadline = Absolute deadline
> > - dl_se->dl_deadline = Relative deadline  
> Daniel's note [1] reminds me that, would it be worth a rename of these, for the sake of clarity, e.g.:
> -) abs_deadline vs rel_deadline
> -) runtime_left vs runtime_tot
> or similar :-) ?

+1 as I seem to get confused by it too.

-- Steve