[PATCH RFC] sched/deadline: Use the revised wakeup rule for suspending constrained dl tasks

[PATCH RFC] sched/deadline: Use the revised wakeup rule for suspending constrained dl tasks

[Daniel Bristot de Oliveira]

We have been facing some problems with self-suspending constrained
deadline tasks. The main reason is that the original CBS was not
designed for such sort of tasks.

One problem reported by Xunlei Pang takes place when a task
suspends, and then is awakened before the deadline, but so close
to the deadline that its remaining runtime can cause the task
to have an absolute density higher than allowed. In such situation,
the original CBS assumes that the task is facing an early activation,
and so it replenishes the task and set another deadline, one deadline
in the future. This rule works fine for implicit deadline tasks.
Moreover, it allows the system to adapt the period of a task in which
the external event source suffered from a clock drift.

However, this opens the window for bandwidth leakage for constrained
deadline tasks. For instance, a task with the following parameters:

  runtime   = 5 ms
  deadline  = 7 ms
  [density] = 5 / 7 = 0.71
  period    = 1000 ms

If the task runs for 1 ms, and then suspends for another 1ms,
it will be awakened with the following parameters:

  remaining runtime = 4
  laxity = 5

presenting a absolute density of 4 / 5 = 0.80.

In this case, the original CBS would assume the task had an early
wakeup. Then, CBS will reset the runtime, and the absolute deadline will
be postponed by one relative deadline, allowing the task to run.

The problem is that, if the task runs this pattern forever, it will keep
receiving bandwidth, being able to run 1ms every 2ms. Following this
behavior, the task would be able to run 500 ms in 1 sec. Thus running
more than the 5 ms / 1 sec the admission control allowed it to run.

Trying to address the self-suspending case, Luca Abeni, Giuseppe
Lipari, and Juri Lelli [1] revisited the CBS in order to deal with
self-suspending tasks. In the new approach, rather than
replenishing/postponing the absolute deadline, the revised wakeup rule
adjusts the remaining runtime, reducing it to fit into the allowed
density.

A resumed version of the idea is:

At a given time t, the maximum absolute density of a task cannot be
higher than its relative density, that is:

  runtime / (deadline - t) <= dl_runtime / dl_deadline

Knowing the laxity of a task (deadline - t), it is possible to move
it to the other side of the equality, thus enabling to define max
remaining runtime a task can use within the absolute deadline, without
over-running the allowed density:

  runtime = (dl_runtime / dl_deadline) * (deadline - t)

For instance, in our previous example, the task could still run:

  runtime = ( 5 / 7 ) * 4
  runtime = 2.85 ms

Without causing damage for other deadline tasks. It is note worth that
the laxity cannot be negative because that would cause a negative
runtime. Thus, this patch depends on the patch:

  edf5835 sched/deadline: Throttle a constrained deadline task activated
          after the deadline

Which throttles a constrained deadline task activated after the
deadline.

Finally, it is also possible to use the revised wakeup rule for
all other tasks, but that would require some more discussions
about pros and cons.

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

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index a2ce590..71e5bcf 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -484,13 +484,63 @@ static bool dl_entity_overflow(struct sched_dl_entity *dl_se,
 }
 
 /*
+ * Revised wakeup rule [1]: For self-suspending tasks, rather then
+ * re-initializing task's runtime and deadline, the revised wakeup
+ * rule adjusts the task's runtime to avoid the task to overrun its
+ * density.
+ *
+ * Reasoning: a task may overrun the density if:
+ *    runtime / (deadline - t) > dl_runtime / dl_deadline
+ *
+ * Therefore, runtime can be adjusted to:
+ *     runtime = (dl_runtime / dl_deadline) * (deadline - t)
+ *
+ * In such way that runtime will be equals to the maximum density
+ * the task can use without breaking any rule.
+ *
+ * [1] Luca Abeni, Giuseppe Lipari, and Juri Lelli. 2015. Constant
+ * bandwidth server revisited. SIGBED Rev. 11, 4 (January 2015), 19-24.
+ */
+static void
+update_dl_revised_wakeup(struct sched_dl_entity *dl_se, struct rq *rq)
+{
+	u64 density = div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline);
+	u64 laxity = dl_se->deadline - rq_clock(rq);
+
+	BUG_ON(laxity < 0);
+
+	dl_se->runtime = density * laxity >> 20;
+}
+
+static inline bool dl_is_constrained(struct sched_dl_entity *dl_se)
+{
+	return dl_se->dl_deadline < dl_se->dl_period;
+}
+
+/*
  * When a -deadline entity is queued back on the runqueue, its runtime and
  * deadline might need updating.
  *
- * The policy here is that we update the deadline of the entity only if:
- *  - the current deadline is in the past,
+ * Currently, we are using two different CBS rules, 1) the original CBS
+ * for implicit deadline tasks; 2) the revisited CBS for constrained
+ * deadline ones. The reason is that the original CBS can cause a constrained
+ * deadline task to be replenished deadline/period times in a period, in
+ * the worst case, hence allowing it to run more than runtime/period.
+ * In order to prevent this misbehave, the revisited CBS is used for
+ * constrained deadline tasks. In the revisited CBS, in the case of an
+ * overload, rather than replenishing & postponing the deadline, the
+ * remaining runtime of a task is reduced to avoid runtime overflow.
+ *
+ * So, for implicit deadline tasks, the policy here is that the runtime &
+ * deadline of an entity are update if and only if., either:
+ *  - the current deadline is in the past, or
  *  - using the remaining runtime with the current deadline would make
  *    the entity exceed its bandwidth.
+ *
+ * For constrained deadline tasks, the policy here is that the runtime
+ * is reduced to avoid exceeding its bandwidth if:
+ *   - using the remaining runtime with the current deadline would make
+ *     the entity exceed its bandwidth.
  */
 static void update_dl_entity(struct sched_dl_entity *dl_se,
 			     struct sched_dl_entity *pi_se)
@@ -500,6 +550,14 @@ static void update_dl_entity(struct sched_dl_entity *dl_se,
 
 	if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
 	    dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
+
+		if (unlikely(dl_is_constrained(dl_se) &&
+		    !dl_time_before(dl_se->deadline, rq_clock(rq)) &&
+		    !dl_se->dl_boosted)){
+			update_dl_revised_wakeup(dl_se, rq);
+			return;
+		}
+
 		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
 		dl_se->runtime = pi_se->dl_runtime;
 	}
@@ -959,11 +1017,6 @@ 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);
-- 
2.9.3

Re: [PATCH RFC] sched/deadline: Use the revised wakeup rule for suspending constrained dl tasks

[Steven Rostedt]

On Mon, 24 Apr 2017 17:18:35 +0200
Daniel Bristot de Oliveira <bristot@redhat.com> wrote:

> We have been facing some problems with self-suspending constrained
> deadline tasks. The main reason is that the original CBS was not
> designed for such sort of tasks.
> 
> One problem reported by Xunlei Pang takes place when a task
> suspends, and then is awakened before the deadline, but so close
> to the deadline that its remaining runtime can cause the task
> to have an absolute density higher than allowed. In such situation,
> the original CBS assumes that the task is facing an early activation,
> and so it replenishes the task and set another deadline, one deadline
> in the future. This rule works fine for implicit deadline tasks.
> Moreover, it allows the system to adapt the period of a task in which
> the external event source suffered from a clock drift.
> 
> However, this opens the window for bandwidth leakage for constrained
> deadline tasks. For instance, a task with the following parameters:
> 
>   runtime   = 5 ms
>   deadline  = 7 ms
>   [density] = 5 / 7 = 0.71
>   period    = 1000 ms
> 
> If the task runs for 1 ms, and then suspends for another 1ms,
> it will be awakened with the following parameters:
> 
>   remaining runtime = 4
>   laxity = 5
> 
> presenting a absolute density of 4 / 5 = 0.80.
> 
> In this case, the original CBS would assume the task had an early
> wakeup. Then, CBS will reset the runtime, and the absolute deadline will
> be postponed by one relative deadline, allowing the task to run.
> 
> The problem is that, if the task runs this pattern forever, it will keep
> receiving bandwidth, being able to run 1ms every 2ms. Following this
> behavior, the task would be able to run 500 ms in 1 sec. Thus running
> more than the 5 ms / 1 sec the admission control allowed it to run.
> 
> Trying to address the self-suspending case, Luca Abeni, Giuseppe
> Lipari, and Juri Lelli [1] revisited the CBS in order to deal with
> self-suspending tasks. In the new approach, rather than
> replenishing/postponing the absolute deadline, the revised wakeup rule
> adjusts the remaining runtime, reducing it to fit into the allowed
> density.
> 
> A resumed version of the idea is:
> 
> At a given time t, the maximum absolute density of a task cannot be
> higher than its relative density, that is:
> 
>   runtime / (deadline - t) <= dl_runtime / dl_deadline
> 
> Knowing the laxity of a task (deadline - t), it is possible to move
> it to the other side of the equality, thus enabling to define max
> remaining runtime a task can use within the absolute deadline, without
> over-running the allowed density:
> 
>   runtime = (dl_runtime / dl_deadline) * (deadline - t)
> 
> For instance, in our previous example, the task could still run:
> 
>   runtime = ( 5 / 7 ) * 4
>   runtime = 2.85 ms

Nice.

> 
> Without causing damage for other deadline tasks. It is note worth that
> the laxity cannot be negative because that would cause a negative
> runtime. Thus, this patch depends on the patch:
> 
>   edf5835 sched/deadline: Throttle a constrained deadline task activated
>           after the deadline
> 
> Which throttles a constrained deadline task activated after the
> deadline.
> 
> Finally, it is also possible to use the revised wakeup rule for
> all other tasks, but that would require some more discussions
> about pros and cons.
> 
> Reported-by: Xunlei Pang <xpang@redhat.com>
> Signed-off-by: Daniel Bristot de Oliveira <bristot@redhat.com>
> Cc: Xunlei Pang <xpang@redhat.com>
> Cc: Ingo Molnar <mingo@redhat.com>
> Cc: Peter Zijlstra <peterz@infradead.org>
> Cc: Juri Lelli <juri.lelli@arm.com>
> Cc: Steven Rostedt <rostedt@goodmis.org>
> Cc: Luca Abeni <luca.abeni@santannapisa.it>
> Cc: Tommaso Cucinotta <tommaso.cucinotta@sssup.it>
> Cc: Romulo Silva de Oliveira <romulo.deoliveira@ufsc.br>
> Cc: linux-kernel@vger.kernel.org
> ---
>  kernel/sched/deadline.c | 67 +++++++++++++++++++++++++++++++++++++++++++------
>  1 file changed, 60 insertions(+), 7 deletions(-)
> 
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index a2ce590..71e5bcf 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -484,13 +484,63 @@ static bool dl_entity_overflow(struct sched_dl_entity *dl_se,
>  }
>  
>  /*
> + * Revised wakeup rule [1]: For self-suspending tasks, rather then
> + * re-initializing task's runtime and deadline, the revised wakeup
> + * rule adjusts the task's runtime to avoid the task to overrun its
> + * density.
> + *
> + * Reasoning: a task may overrun the density if:
> + *    runtime / (deadline - t) > dl_runtime / dl_deadline
> + *
> + * Therefore, runtime can be adjusted to:
> + *     runtime = (dl_runtime / dl_deadline) * (deadline - t)
> + *
> + * In such way that runtime will be equals to the maximum density
> + * the task can use without breaking any rule.
> + *
> + * [1] Luca Abeni, Giuseppe Lipari, and Juri Lelli. 2015. Constant
> + * bandwidth server revisited. SIGBED Rev. 11, 4 (January 2015), 19-24.
> + */
> +static void
> +update_dl_revised_wakeup(struct sched_dl_entity *dl_se, struct rq *rq)
> +{
> +	u64 density = div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline);

Hmm, dl_runtime and dl_deadline don't get updated that often. Can't we
simply keep a static dl_se->dl_density, and update it when dl_runtime
or dl_deadline get updated? That would get rid of the divide in the
middle of a wake up call.

-- Steve

> +	u64 laxity = dl_se->deadline - rq_clock(rq);
> +
> +	BUG_ON(laxity < 0);
> +
> +	dl_se->runtime = density * laxity >> 20;
> +}
> +
> +static inline bool dl_is_constrained(struct sched_dl_entity *dl_se)
> +{
> +	return dl_se->dl_deadline < dl_se->dl_period;
> +}
> +

Re: [PATCH RFC] sched/deadline: Use the revised wakeup rule for suspending constrained dl tasks

[Daniel Bristot de Oliveira]

On 04/24/2017 07:00 PM, Steven Rostedt wrote:
>> +static void
>> +update_dl_revised_wakeup(struct sched_dl_entity *dl_se, struct rq *rq)
>> +{
>> +	u64 density = div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline);
> Hmm, dl_runtime and dl_deadline don't get updated that often. Can't we
> simply keep a static dl_se->dl_density, and update it when dl_runtime
> or dl_deadline get updated? That would get rid of the divide in the
> middle of a wake up call.

Yeah, I agree! Juri also pointed in the same direction, I will add it in
the possible next version ;-).

Thanks for the feedback!

-- Daniel

Re: [PATCH RFC] sched/deadline: Use the revised wakeup rule for suspending constrained dl tasks

[Daniel Bristot de Oliveira]

On 04/24/2017 05:18 PM, Daniel Bristot de Oliveira wrote:
>   remaining runtime = 4
>   laxity = 5
Oops! The laxity is 5... so...

> Knowing the laxity of a task (deadline - t), it is possible to move
> it to the other side of the equality, thus enabling to define max
> remaining runtime a task can use within the absolute deadline, without
> over-running the allowed density:
> 
>   runtime = (dl_runtime / dl_deadline) * (deadline - t)
> 
> For instance, in our previous example, the task could still run:
> 
>   runtime = ( 5 / 7 ) * 4
>   runtime = 2.85 ms

This should be:
    runtime = ( 5 / 7 ) * 5
    runtime = 3.57 ms

even better :-)

-- Daniel

Re: [PATCH RFC] sched/deadline: Use the revised wakeup rule for suspending constrained dl tasks

[Peter Zijlstra]

On Mon, Apr 24, 2017 at 05:18:35PM +0200, Daniel Bristot de Oliveira wrote:
> We have been facing some problems with self-suspending constrained
> deadline tasks. The main reason is that the original CBS was not
> designed for such sort of tasks.
> 
> One problem reported by Xunlei Pang takes place when a task
> suspends, and then is awakened before the deadline, but so close
> to the deadline that its remaining runtime can cause the task
> to have an absolute density higher than allowed. In such situation,
> the original CBS assumes that the task is facing an early activation,
> and so it replenishes the task and set another deadline, one deadline
> in the future. This rule works fine for implicit deadline tasks.
> Moreover, it allows the system to adapt the period of a task in which
> the external event source suffered from a clock drift.
> 
> However, this opens the window for bandwidth leakage for constrained
> deadline tasks. For instance, a task with the following parameters:
> 
>   runtime   = 5 ms
>   deadline  = 7 ms
>   [density] = 5 / 7 = 0.71
>   period    = 1000 ms
> 
> If the task runs for 1 ms, and then suspends for another 1ms,
> it will be awakened with the following parameters:
> 
>   remaining runtime = 4
>   laxity = 5
> 
> presenting a absolute density of 4 / 5 = 0.80.
> 
> In this case, the original CBS would assume the task had an early
> wakeup. Then, CBS will reset the runtime, and the absolute deadline will
> be postponed by one relative deadline, allowing the task to run.
> 
> The problem is that, if the task runs this pattern forever, it will keep
> receiving bandwidth, being able to run 1ms every 2ms. Following this
> behavior, the task would be able to run 500 ms in 1 sec. Thus running
> more than the 5 ms / 1 sec the admission control allowed it to run.
> 
> Trying to address the self-suspending case, Luca Abeni, Giuseppe
> Lipari, and Juri Lelli [1] revisited the CBS in order to deal with
> self-suspending tasks. In the new approach, rather than
> replenishing/postponing the absolute deadline, the revised wakeup rule
> adjusts the remaining runtime, reducing it to fit into the allowed
> density.
> 
> A resumed version of the idea is:
> 
> At a given time t, the maximum absolute density of a task cannot be
> higher than its relative density, that is:
> 
>   runtime / (deadline - t) <= dl_runtime / dl_deadline
> 
> Knowing the laxity of a task (deadline - t), it is possible to move
> it to the other side of the equality, thus enabling to define max
> remaining runtime a task can use within the absolute deadline, without
> over-running the allowed density:
> 
>   runtime = (dl_runtime / dl_deadline) * (deadline - t)
> 
> For instance, in our previous example, the task could still run:
> 
>   runtime = ( 5 / 7 ) * 4
>   runtime = 2.85 ms
> 
> Without causing damage for other deadline tasks. It is note worth that
> the laxity cannot be negative because that would cause a negative
> runtime. Thus, this patch depends on the patch:
> 
>   edf5835 sched/deadline: Throttle a constrained deadline task activated
>           after the deadline

My git tree says that is:

df8eac8cafce ("sched/deadline: Throttle a constrained deadline task activated after the deadline")

> Which throttles a constrained deadline task activated after the
> deadline.
> 
> Finally, it is also possible to use the revised wakeup rule for
> all other tasks, but that would require some more discussions
> about pros and cons.
> 
> Reported-by: Xunlei Pang <xpang@redhat.com>
> Signed-off-by: Daniel Bristot de Oliveira <bristot@redhat.com>
> Cc: Xunlei Pang <xpang@redhat.com>
> Cc: Ingo Molnar <mingo@redhat.com>
> Cc: Peter Zijlstra <peterz@infradead.org>
> Cc: Juri Lelli <juri.lelli@arm.com>
> Cc: Steven Rostedt <rostedt@goodmis.org>
> Cc: Luca Abeni <luca.abeni@santannapisa.it>
> Cc: Tommaso Cucinotta <tommaso.cucinotta@sssup.it>
> Cc: Romulo Silva de Oliveira <romulo.deoliveira@ufsc.br>
> Cc: linux-kernel@vger.kernel.org
> ---
>  kernel/sched/deadline.c | 67 +++++++++++++++++++++++++++++++++++++++++++------
>  1 file changed, 60 insertions(+), 7 deletions(-)
> 
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index a2ce590..71e5bcf 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -484,13 +484,63 @@ static bool dl_entity_overflow(struct sched_dl_entity *dl_se,
>  }
>  
>  /*
> + * Revised wakeup rule [1]: For self-suspending tasks, rather then
> + * re-initializing task's runtime and deadline, the revised wakeup
> + * rule adjusts the task's runtime to avoid the task to overrun its
> + * density.
> + *
> + * Reasoning: a task may overrun the density if:
> + *    runtime / (deadline - t) > dl_runtime / dl_deadline

When reading that, I have the instant question: "why / how ?" I suspect
the blurb below (at update_dl_entity) has the answer, if so this can use
a reference thereto.

> + *
> + * Therefore, runtime can be adjusted to:
> + *     runtime = (dl_runtime / dl_deadline) * (deadline - t)
> + *
> + * In such way that runtime will be equals to the maximum density
> + * the task can use without breaking any rule.
> + *
> + * [1] Luca Abeni, Giuseppe Lipari, and Juri Lelli. 2015. Constant
> + * bandwidth server revisited. SIGBED Rev. 11, 4 (January 2015), 19-24.
> + */
> +static void
> +update_dl_revised_wakeup(struct sched_dl_entity *dl_se, struct rq *rq)
> +{
> +	u64 density = div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline);
> +	u64 laxity = dl_se->deadline - rq_clock(rq);
> +
> +	BUG_ON(laxity < 0);

Compiler will make that go away, by virtue of laxity being unsigned.

> +
> +	dl_se->runtime = density * laxity >> 20;
> +}
> +
/*
 * XXX comment that explains what constrained is ? per the definition
 * below that is any task where deadline != period?
 */
> +static inline bool dl_is_constrained(struct sched_dl_entity *dl_se)
> +{
> +	return dl_se->dl_deadline < dl_se->dl_period;
> +}
> +
> +/*
>   * When a -deadline entity is queued back on the runqueue, its runtime and
>   * deadline might need updating.
>   *
> + * Currently, we are using two different CBS rules, 1) the original CBS
> + * for implicit deadline tasks; 2) the revisited CBS for constrained
> + * deadline ones. The reason is that the original CBS can cause a constrained
> + * deadline task to be replenished deadline/period times in a period, in
> + * the worst case, hence allowing it to run more than runtime/period.
> + * In order to prevent this misbehave, the revisited CBS is used for
> + * constrained deadline tasks. In the revisited CBS, in the case of an
> + * overload, rather than replenishing & postponing the deadline, the
> + * remaining runtime of a task is reduced to avoid runtime overflow.

We use two difference CBS rules:

 1) the original CBS rule for implicit deadline tasks;
 2) the revised CBS rule for constrained deadline tasks.

( and here I have the question, wth is implicit / constrained )

The reason is that the original CBS rul can cause a constrained deadline
task to be replenished deadline/period times in a period (worst case),
hence allowing it to run more than runtime/period.

( the deadline/period thing could use a few words extra; in the example
  above that divides to: 7/1000 = .007 which does not have an integer
  component. You cannot replenish fractional times etc.. )

In order to prevent this, the revised CBS rule reduces the remaining
runtime (by limiting the max density).

> + *
> + * So, for implicit deadline tasks, the policy here is that the runtime &
> + * deadline of an entity are update if and only if., either:

updated ? IFF

> + *  - the current deadline is in the past, or
>   *  - using the remaining runtime with the current deadline would make
>   *    the entity exceed its bandwidth.
> + *
> + * For constrained deadline tasks, the policy here is that the runtime
> + * is reduced to avoid exceeding its bandwidth if:

> + *   - using the remaining runtime with the current deadline would make
> + *     the entity exceed its bandwidth.
>   */

In general the comment on comments is to add whitespace. That greatly
increases readability.

>  static void update_dl_entity(struct sched_dl_entity *dl_se,
>  			     struct sched_dl_entity *pi_se)
> @@ -500,6 +550,14 @@ static void update_dl_entity(struct sched_dl_entity *dl_se,
>  
>  	if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
>  	    dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
> +
> +		if (unlikely(dl_is_constrained(dl_se) &&
> +		    !dl_time_before(dl_se->deadline, rq_clock(rq)) &&

alignment is misleading, this is still inside the unlikely(.

> +		    !dl_se->dl_boosted)){
> +			update_dl_revised_wakeup(dl_se, rq);
> +			return;
> +		}
> +
>  		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
>  		dl_se->runtime = pi_se->dl_runtime;
>  	}

Re: [PATCH RFC] sched/deadline: Use the revised wakeup rule for suspending constrained dl tasks

[Peter Zijlstra]

On Thu, May 04, 2017 at 04:17:21PM +0200, Peter Zijlstra wrote:
> On Mon, Apr 24, 2017 at 05:18:35PM +0200, Daniel Bristot de Oliveira wrote:
> > +static void
> > +update_dl_revised_wakeup(struct sched_dl_entity *dl_se, struct rq *rq)
> > +{
> > +	u64 density = div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline);
> > +	u64 laxity = dl_se->deadline - rq_clock(rq);
> > +
> > +	BUG_ON(laxity < 0);
> 
> Compiler will make that go away, by virtue of laxity being unsigned.

Also, so we want that to BUG (or even WARN) in a soft RT setting.
Remember, GEDF does not guarantee we make our deadlines.


> We use two difference CBS rules:

_different_, clearly I cannot type anymore either ;-)

Re: [PATCH RFC] sched/deadline: Use the revised wakeup rule for suspending constrained dl tasks

[Peter Zijlstra]

On Thu, May 04, 2017 at 04:17:21PM +0200, Peter Zijlstra wrote:
> We use two difference CBS rules:
> 
>  1) the original CBS rule for implicit deadline tasks;
>  2) the revised CBS rule for constrained deadline tasks.

> > @@ -500,6 +550,14 @@ static void update_dl_entity(struct sched_dl_entity *dl_se,
> >  
> >  	if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
> >  	    dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
> > +
> > +		if (unlikely(dl_is_constrained(dl_se) &&
> > +		    !dl_time_before(dl_se->deadline, rq_clock(rq)) &&
> > +		    !dl_se->dl_boosted)){
> > +			update_dl_revised_wakeup(dl_se, rq);
> > +			return;
> > +		}
> > +
> >  		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
> >  		dl_se->runtime = pi_se->dl_runtime;
> >  	}

That comment above does not match the code. We can still use the
original CBS rule for constrained tasks.

We only use the revised CBS rule when the constrained task hasn't missed
its deadline yet.

Re: [PATCH RFC] sched/deadline: Use the revised wakeup rule for suspending constrained dl tasks

[Daniel Bristot de Oliveira]

On 05/04/2017 04:17 PM, Peter Zijlstra wrote:
> On Mon, Apr 24, 2017 at 05:18:35PM +0200, Daniel Bristot de Oliveira wrote:
>> We have been facing some problems with self-suspending constrained
>> deadline tasks. The main reason is that the original CBS was not
>> designed for such sort of tasks.
>>
>> One problem reported by Xunlei Pang takes place when a task
>> suspends, and then is awakened before the deadline, but so close
>> to the deadline that its remaining runtime can cause the task
>> to have an absolute density higher than allowed. In such situation,
>> the original CBS assumes that the task is facing an early activation,
>> and so it replenishes the task and set another deadline, one deadline
>> in the future. This rule works fine for implicit deadline tasks.
>> Moreover, it allows the system to adapt the period of a task in which
>> the external event source suffered from a clock drift.
>>
>> However, this opens the window for bandwidth leakage for constrained
>> deadline tasks. For instance, a task with the following parameters:
>>
>>   runtime   = 5 ms
>>   deadline  = 7 ms
>>   [density] = 5 / 7 = 0.71
>>   period    = 1000 ms
>>
>> If the task runs for 1 ms, and then suspends for another 1ms,
>> it will be awakened with the following parameters:
>>
>>   remaining runtime = 4
>>   laxity = 5
>>
>> presenting a absolute density of 4 / 5 = 0.80.
>>
>> In this case, the original CBS would assume the task had an early
>> wakeup. Then, CBS will reset the runtime, and the absolute deadline will
>> be postponed by one relative deadline, allowing the task to run.
>>
>> The problem is that, if the task runs this pattern forever, it will keep
>> receiving bandwidth, being able to run 1ms every 2ms. Following this
>> behavior, the task would be able to run 500 ms in 1 sec. Thus running
>> more than the 5 ms / 1 sec the admission control allowed it to run.
>>
>> Trying to address the self-suspending case, Luca Abeni, Giuseppe
>> Lipari, and Juri Lelli [1] revisited the CBS in order to deal with
>> self-suspending tasks. In the new approach, rather than
>> replenishing/postponing the absolute deadline, the revised wakeup rule
>> adjusts the remaining runtime, reducing it to fit into the allowed
>> density.
>>
>> A resumed version of the idea is:
>>
>> At a given time t, the maximum absolute density of a task cannot be
>> higher than its relative density, that is:
>>
>>   runtime / (deadline - t) <= dl_runtime / dl_deadline
>>
>> Knowing the laxity of a task (deadline - t), it is possible to move
>> it to the other side of the equality, thus enabling to define max
>> remaining runtime a task can use within the absolute deadline, without
>> over-running the allowed density:
>>
>>   runtime = (dl_runtime / dl_deadline) * (deadline - t)
>>
>> For instance, in our previous example, the task could still run:
>>
>>   runtime = ( 5 / 7 ) * 4
>>   runtime = 2.85 ms
>>
>> Without causing damage for other deadline tasks. It is note worth that
>> the laxity cannot be negative because that would cause a negative
>> runtime. Thus, this patch depends on the patch:
>>
>>   edf5835 sched/deadline: Throttle a constrained deadline task activated
>>           after the deadline
> 
> My git tree says that is:
> 
> df8eac8cafce ("sched/deadline: Throttle a constrained deadline task activated after the deadline")

Ops, you are right, I was using my own tree, sorry.

>> Which throttles a constrained deadline task activated after the
>> deadline.
>>
>> Finally, it is also possible to use the revised wakeup rule for
>> all other tasks, but that would require some more discussions
>> about pros and cons.
>>
>> Reported-by: Xunlei Pang <xpang@redhat.com>
>> Signed-off-by: Daniel Bristot de Oliveira <bristot@redhat.com>
>> Cc: Xunlei Pang <xpang@redhat.com>
>> Cc: Ingo Molnar <mingo@redhat.com>
>> Cc: Peter Zijlstra <peterz@infradead.org>
>> Cc: Juri Lelli <juri.lelli@arm.com>
>> Cc: Steven Rostedt <rostedt@goodmis.org>
>> Cc: Luca Abeni <luca.abeni@santannapisa.it>
>> Cc: Tommaso Cucinotta <tommaso.cucinotta@sssup.it>
>> Cc: Romulo Silva de Oliveira <romulo.deoliveira@ufsc.br>
>> Cc: linux-kernel@vger.kernel.org
>> ---
>>  kernel/sched/deadline.c | 67 +++++++++++++++++++++++++++++++++++++++++++------
>>  1 file changed, 60 insertions(+), 7 deletions(-)
>>
>> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
>> index a2ce590..71e5bcf 100644
>> --- a/kernel/sched/deadline.c
>> +++ b/kernel/sched/deadline.c
>> @@ -484,13 +484,63 @@ static bool dl_entity_overflow(struct sched_dl_entity *dl_se,
>>  }
>>  
>>  /*
>> + * Revised wakeup rule [1]: For self-suspending tasks, rather then
>> + * re-initializing task's runtime and deadline, the revised wakeup
>> + * rule adjusts the task's runtime to avoid the task to overrun its
>> + * density.
>> + *
>> + * Reasoning: a task may overrun the density if:
>> + *    runtime / (deadline - t) > dl_runtime / dl_deadline
> 
> When reading that, I have the instant question: "why / how ?" I suspect
> the blurb below (at update_dl_entity) has the answer, if so this can use
> a reference thereto.

Yeah, I will connect the two comments.

>> + *
>> + * Therefore, runtime can be adjusted to:
>> + *     runtime = (dl_runtime / dl_deadline) * (deadline - t)
>> + *
>> + * In such way that runtime will be equals to the maximum density
>> + * the task can use without breaking any rule.
>> + *
>> + * [1] Luca Abeni, Giuseppe Lipari, and Juri Lelli. 2015. Constant
>> + * bandwidth server revisited. SIGBED Rev. 11, 4 (January 2015), 19-24.
>> + */
>> +static void
>> +update_dl_revised_wakeup(struct sched_dl_entity *dl_se, struct rq *rq)
>> +{
>> +	u64 density = div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline);
>> +	u64 laxity = dl_se->deadline - rq_clock(rq);
>> +
>> +	BUG_ON(laxity < 0);
> 
> Compiler will make that go away, by virtue of laxity being unsigned.
> 
>> +
>> +	dl_se->runtime = density * laxity >> 20;
>> +}
>> +
> /*
>  * XXX comment that explains what constrained is ? per the definition
>  * below that is any task where deadline != period?
>  */

Per definition, constrained deadline tasks are those with deadline <=
period.

So, to be strictly correct, I should even rename this function to
something like: dl_is_not_implicit. (implicit deadline means deadline =
period).

(Well, we also have arbitrary deadline, with deadline less than, equals
to or higher than the period... so the name should be something like
dl_neither_implicit_nor_arbitrary but we do not support it...).

So, although slight imprecise, the current name is the more intuitive
one. Any suggestions?

I will write a comment explaining the terms.

>> +static inline bool dl_is_constrained(struct sched_dl_entity *dl_se)
>> +{
>> +	return dl_se->dl_deadline < dl_se->dl_period;
>> +}
>> +
>> +/*
>>   * When a -deadline entity is queued back on the runqueue, its runtime and
>>   * deadline might need updating.
>>   *
>> + * Currently, we are using two different CBS rules, 1) the original CBS
>> + * for implicit deadline tasks; 2) the revisited CBS for constrained
>> + * deadline ones. The reason is that the original CBS can cause a constrained
>> + * deadline task to be replenished deadline/period times in a period, in
>> + * the worst case, hence allowing it to run more than runtime/period.
>> + * In order to prevent this misbehave, the revisited CBS is used for
>> + * constrained deadline tasks. In the revisited CBS, in the case of an
>> + * overload, rather than replenishing & postponing the deadline, the
>> + * remaining runtime of a task is reduced to avoid runtime overflow.
> 
> We use two difference CBS rules:
> 
>  1) the original CBS rule for implicit deadline tasks;
>  2) the revised CBS rule for constrained deadline tasks.
> 
> ( and here I have the question, wth is implicit / constrained )
> 
> The reason is that the original CBS rul can cause a constrained deadline
> task to be replenished deadline/period times in a period (worst case),
> hence allowing it to run more than runtime/period.
> 
> ( the deadline/period thing could use a few words extra; in the example
>   above that divides to: 7/1000 = .007 which does not have an integer
>   component. You cannot replenish fractional times etc.. )

Actually, the sched deadline uses that 'runtime << 20' to avoid such
imprecision. For example, runtime of 7 ms of a 1000 ms period would
result in:

7 << 20 / 1000
7340032 / 1000 = 7340.032 = 7340

Btw, we are currently using the density in the overflow rule, so it is
using runtime / deadline, which is more pessimistic.

> In order to prevent this, the revised CBS rule reduces the remaining
> runtime (by limiting the max density).

correct!

> 
>> + *
>> + * So, for implicit deadline tasks, the policy here is that the runtime &
>> + * deadline of an entity are update if and only if., either:
> 
> updated ? IFF
> 
>> + *  - the current deadline is in the past, or
>>   *  - using the remaining runtime with the current deadline would make
>>   *    the entity exceed its bandwidth.
>> + *
>> + * For constrained deadline tasks, the policy here is that the runtime
>> + * is reduced to avoid exceeding its bandwidth if:
> 
>> + *   - using the remaining runtime with the current deadline would make
>> + *     the entity exceed its bandwidth.
>>   */
> 
> In general the comment on comments is to add whitespace. That greatly
> increases readability.

ack o>
> 
>>  static void update_dl_entity(struct sched_dl_entity *dl_se,
>>  			     struct sched_dl_entity *pi_se)
>> @@ -500,6 +550,14 @@ static void update_dl_entity(struct sched_dl_entity *dl_se,
>>  
>>  	if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
>>  	    dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
>> +
>> +		if (unlikely(dl_is_constrained(dl_se) &&
>> +		    !dl_time_before(dl_se->deadline, rq_clock(rq)) &&
> 
> alignment is misleading, this is still inside the unlikely(.

ack

>> +		    !dl_se->dl_boosted)){
>> +			update_dl_revised_wakeup(dl_se, rq);
>> +			return;
>> +		}
>> +
>>  		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
>>  		dl_se->runtime = pi_se->dl_runtime;
>>  	}

Re: [PATCH RFC] sched/deadline: Use the revised wakeup rule for suspending constrained dl tasks

[Daniel Bristot de Oliveira]

On 05/04/2017 04:23 PM, Peter Zijlstra wrote:
> On Thu, May 04, 2017 at 04:17:21PM +0200, Peter Zijlstra wrote:
>> On Mon, Apr 24, 2017 at 05:18:35PM +0200, Daniel Bristot de Oliveira wrote:
>>> +static void
>>> +update_dl_revised_wakeup(struct sched_dl_entity *dl_se, struct rq *rq)
>>> +{
>>> +	u64 density = div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline);
>>> +	u64 laxity = dl_se->deadline - rq_clock(rq);
>>> +
>>> +	BUG_ON(laxity < 0);
>> Compiler will make that go away, by virtue of laxity being unsigned.
> Also, so we want that to BUG (or even WARN) in a soft RT setting.
> Remember, GEDF does not guarantee we make our deadlines.

The point is that, a task with laxity < 0 should be throttled before
this point by:

df8eac8cafce ("sched/deadline: Throttle a constrained deadline task
activated after the deadline")

Arrive here with (laxity < 0) meas that we skipped that check.

>> We use two difference CBS rules:
> _different_, clearly I cannot type anymore either ;-)

ops... :-)

-- Daniel

Re: [PATCH RFC] sched/deadline: Use the revised wakeup rule for suspending constrained dl tasks

[Daniel Bristot de Oliveira]

On 05/04/2017 04:26 PM, Peter Zijlstra wrote:
> On Thu, May 04, 2017 at 04:17:21PM +0200, Peter Zijlstra wrote:
>> We use two difference CBS rules:
>>
>>  1) the original CBS rule for implicit deadline tasks;
>>  2) the revised CBS rule for constrained deadline tasks.
>>> @@ -500,6 +550,14 @@ static void update_dl_entity(struct sched_dl_entity *dl_se,
>>>  
>>>  	if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
>>>  	    dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
>>> +
>>> +		if (unlikely(dl_is_constrained(dl_se) &&
>>> +		    !dl_time_before(dl_se->deadline, rq_clock(rq)) &&
>>> +		    !dl_se->dl_boosted)){
>>> +			update_dl_revised_wakeup(dl_se, rq);
>>> +			return;
>>> +		}
>>> +
>>>  		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
>>>  		dl_se->runtime = pi_se->dl_runtime;
>>>  	}
> That comment above does not match the code. We can still use the
> original CBS rule for constrained tasks.
> 
> We only use the revised CBS rule when the constrained task hasn't missed
> its deadline yet.

Correct. I will improve the explanation.

Thank you very much for all comments :-)

-- Daniel