DMARC-Filter: OpenDMARC Filter v1.3.2 mx1.redhat.com C0DD23D94F
From: Xunlei Pang <xlpang@redhat.com>
To: linux-kernel@vger.kernel.org
Cc: Peter Zijlstra <peterz@infradead.org>, Juri Lelli <juri.lelli@arm.com>,
        Ingo Molnar <mingo@redhat.com>,
        Luca Abeni <luca.abeni@santannapisa.it>,
        Xunlei Pang <xlpang@redhat.com>,
        Daniel Bristot de Oliveira <bristot@redhat.com>,
        Steven Rostedt <rostedt@goodmis.org>
Subject: [PATCH] sched/deadline: Throttle a constrained task activated if overflow
Date: Mon, 10 Apr 2017 17:22:11 +0800
Message-Id: <1491816131-20268-1-git-send-email-xlpang@redhat.com>
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 4513
Lines: 112

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.

Cc: Daniel Bristot de Oliveira <bristot@redhat.com>
Cc: Steven Rostedt <rostedt@goodmis.org>
Signed-off-by: Xunlei Pang <xlpang@redhat.com>
---
 kernel/sched/deadline.c | 47 +++++++++++++++++++++++++++--------------------
 1 file changed, 27 insertions(+), 20 deletions(-)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index a2ce590..e7be3b4 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -702,28 +702,33 @@ void init_dl_task_timer(struct sched_dl_entity *dl_se)
  * 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.
+ * deadline before the next period, or before the deadline but bandwidth
+ * of the current period was used up. In these cases, replenishing the
+ * task would allow it to run for more than 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.
+ * To avoid these problems, in the activation of a constrained deadline
+ * task, throttle the task as needed and set the replenishing timer to
+ * the begin of the next period.
  */
 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;
-	}
+	if (dl_time_before(dl_next_period(dl_se), rq_clock(rq)))
+		return;
+
+	/* Still have available bandwidth in the current period. */
+	if (dl_time_before(rq_clock(rq), dl_se->deadline) &&
+	    !dl_entity_overflow(dl_se, dl_se, rq_clock(rq)))
+		return;
+
+	if (!start_dl_timer(p))
+		return;
+
+	dl_se->dl_throttled = 1;
 }
 
 static
@@ -990,12 +995,14 @@ 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.
+	 * Check if a constrained deadline task is allowed to be
+	 * activated in the current period. If not, the task will
+	 * be throttled and the replenishment timer will be set to
+	 * the next period. Skip boosted and throttled tasks.
 	 */
-	if (!p->dl.dl_throttled && dl_is_constrained(&p->dl))
+	if (!p->dl.dl_boosted &&
+	    !p->dl.dl_throttled &&
+	    dl_is_constrained(&p->dl))
 		dl_check_constrained_dl(&p->dl);
 
 	/*
-- 
1.8.3.1