Return-Path: <linux-kernel-owner@vger.kernel.org>
Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand
        id S1752211AbdDJUrT (ORCPT <rfc822;w@1wt.eu>);
        Mon, 10 Apr 2017 16:47:19 -0400
Received: from mail-wr0-f179.google.com ([209.85.128.179]:36300 "EHLO
        mail-wr0-f179.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org
        with ESMTP id S1751888AbdDJUrR (ORCPT
        <rfc822;linux-kernel@vger.kernel.org>);
        Mon, 10 Apr 2017 16:47:17 -0400
Subject: Re: [PATCH] sched/deadline: Throttle a constrained task activated if
 overflow
To: Xunlei Pang <xlpang@redhat.com>, linux-kernel@vger.kernel.org
References: <1491816131-20268-1-git-send-email-xlpang@redhat.com>
Cc: Peter Zijlstra <peterz@infradead.org>, Juri Lelli <juri.lelli@arm.com>,
        Ingo Molnar <mingo@redhat.com>,
        Luca Abeni <luca.abeni@santannapisa.it>,
        Steven Rostedt <rostedt@goodmis.org>,
        Tommaso Cucinotta <tommaso.cucinotta@sssup.it>,
        =?UTF-8?Q?R=c3=b4mulo_Silva_de_Oliveira?= 
        <romulo.deoliveira@ufsc.br>,
        Mathieu Poirier <mathieu.poirier@linaro.org>
From: Daniel Bristot de Oliveira <bristot@redhat.com>
Message-ID: <4d24b94c-1e57-b82c-ff0f-099157ba5526@redhat.com>
Date: Mon, 10 Apr 2017 22:47:14 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
 Thunderbird/45.8.0
MIME-Version: 1.0
In-Reply-To: <1491816131-20268-1-git-send-email-xlpang@redhat.com>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Sender: linux-kernel-owner@vger.kernel.org
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org
Content-Length: 7408
Lines: 190

On 04/10/2017 11:22 AM, Xunlei Pang wrote:
> I was testing Daniel's changes with his test case in the commit
> df8eac8cafce ("sched/deadline: Throttle a constrained deadline
> task activated after the deadline"), and tweaked it a little.
> 
> Instead of having the runtime equal to the deadline, I tweaked
> runtime, deadline and sleep value to ensure every time it calls
> dl_check_constrained_dl() with "dl_se->deadline > rq_clock(rq)"
> as well as true dl_entity_overflow(), so it does replenishing
> every wake up in update_dl_entity(), and break its bandwidth.
> 
> 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 */
> ts.tv_sec = 0;
> ts.tv_nsec = 2000 * 1000; /* 2 ms */
> 
> I changed it to:
> attr.sched_runtime = 5 * 1000 * 1000; /* 5 ms */
> attr.sched_deadline = 7 * 1000 * 1000; /* 7 ms */
> attr.sched_period = 1 * 1000 * 1000 * 1000; /* 1 s */
> ts.tv_sec = 0;
> ts.tv_nsec = 1000 * 1000; /* 1 ms */
> 
> The change above can result in over 25% of the CPU on my machine.
> 
> In order to avoid the beakage, we improve dl_check_constrained_dl()
> to prevent dl tasks from being activated until the next period if it
> runs out of bandwidth of the current period.

The problem now is that, with your patch, we will throttle the task
with some possible runtime. Moreover, the task did not brake any
rule, like being awakened after the deadline - the user-space is not
misbehaving.

That is +- what the reproducer is doing when using your patch,
(I put some trace_printk when noticing the overflow in the wakeup).

          <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: my current runtime is 3657361 and the deadline is 4613027 from now 
          <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: 	my dl_runtime is 5000000

and so the task will be throttled with 3657361 ns runtime available.

As we can see, it is really breaking the density:

5ms / 7ms (.714285) < 3657361 / 4613027 (.792833)

Well, it is not breaking that much. Trying to be less pessimist, we can
compute a new runtime with following equation:

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

That is, a runtime which fits in the task's density.

In code:

dl_se->runtime = (div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline) * (dl_se->deadline - rq_clock(rq))) >> 20;

For example (a trace_printk) showing the adjusted runtime for the
previous task:
          <idle>-0     [007] d.h.  1505.066440: enqueue_task_dl: 	I can still run for 3294208 (it is not that bad)

With the adjusted runtime, we have the following density:

3294208 / 4613027 = .714109

as .714109  < .714285

Voilà. We can still use 3.2 ms of runtime! Not bad at all.

However, even this result is, somehow, controversial. Because we are
reducing the task's reservation (Q/P). But that is very close to the
implicit deadline behavior: when it "overflows", the runtime is truncated
(a replenishment...) and the deadline is postponed. In this case, we do
not need to postpone the deadline, just to "truncate" the runtime to fit
in the density... it is not that bad.

Another possibility is not to replenish a constrained deadline
task twice in a period. In this case, the task would run further
the deadline, potentially causing problems for implicit deadline tasks.
But! even implicit deadline would do it in a overloaded system. The
problem is that, by using the density the system easily becomes
overloaded (too pessimistic).

Resuming (so far):

1) We can be pessimistic to the constrained deadline task,
   with Xunlei's patch;
2) Compute a new runtime to fit in the density - somehow pessimistic.
3) Avoid replenishing a constrained deadline before the next period.
   but the system will become overload very easily (density).

I think the option 2 is the mid-term.
I am showing a _proof of concept_ patch bellow. I is based in the
Xunlei's changes in the verification. I need to polish it... but...
you guys can read the idea in C.

I have the 3) too, but I am not sure if it is as good as 2.

We still need to think more about the solution.... test more... I will
continue working on this tomorrow, discussing with luca and tommaso
as well.

Thoughts? Am I missing something (probably, I am tired :-) )?

---
 kernel/sched/deadline.c | 53 ++++++++++++++++++++++++++++---------------------
 1 file changed, 30 insertions(+), 23 deletions(-)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 7508129..6fa4887 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -696,34 +696,38 @@ void init_dl_task_timer(struct sched_dl_entity *dl_se)
 }
 
 /*
- * 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 loaded system, this can cause a domino
- * effect, making other tasks 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.
+ * XXX: Daniel will document it better in a clean patch, this is
+ * a proof of concept.
  */
 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));
+	u64 clock = rq_clock(rq);
 
-	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;
+	/* we are in a new period */
+	if (dl_time_before(dl_next_period(dl_se), rq_clock(rq)))
+		return;
+
+	/* are we ok with the deadline and density? */
+	if (dl_time_before(rq_clock(rq), dl_se->deadline) &&
+	    !dl_entity_overflow(dl_se, dl_se, rq_clock(rq)))
+		return;
+
+	/* is the density the problem? */
+	if (dl_entity_overflow(dl_se, dl_se, clock)) {
+		/* reduces the runtime so it fits in the density */
+		dl_se->runtime =
+		  (div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline) *
+		  (dl_se->deadline - clock)) >> 20;
+		WARN_ON(dl_se->runtime < 0);
+		return;
 	}
+
+	if (!start_dl_timer(p))
+		return;
+
+	dl_se->dl_throttled = 1;
 }
 
 static
@@ -996,8 +1000,11 @@ static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
 	 * If that is the case, the task will be throttled and
 	 * the replenishment timer will be set to the next period.
 	 */
-	if (!dl_se->dl_throttled && dl_is_constrained(dl_se))
-		dl_check_constrained_dl(dl_se);
+	if (!p->dl.dl_boosted &&
+	    !p->dl.dl_throttled &&
+	    dl_is_constrained(&p->dl))
+		dl_check_constrained_dl(&p->dl);
+
 
 	/*
 	 * If p is throttled, we do nothing. In fact, if it exhausted
-- 
2.5.0