linux-kernel - [PATCH v4] sched/deadline: Change the time to replenish runtime for sleep tasks

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Date:   Tue, 30 May 2017 14:09:52 +0900
From:   Byungchul Park <byungchul.park@....com>
To:     peterz@...radead.org, mingo@...nel.org
Cc:     linux-kernel@...r.kernel.org, juri.lelli@...il.com,
        rostedt@...dmis.org, kernel-team@....com
Subject: [PATCH v4] sched/deadline: Change the time to replenish runtime for sleep tasks

Hi Juri, Peterz,

I checked if this case actually happens practically but it has not
happened. As expected, it's too rare to happen, though it can save
unnecessary interrupts if all the timings are satisfied as the example
in the commit log.

So I don't think it's that worth as much as I initially thought, but
I'm just curious about your opinions. Could you give me your opinions?
It would be appriciated if you do.

Thanks,
Byungchul

----->8-----
>From c94ba55ddd6e67fe3f6a0a34e79f884b91b747ab Mon Sep 17 00:00:00 2001
From: Byungchul Park <byungchul.park@....com>
Date: Tue, 30 May 2017 11:29:45 +0900
Subject: [PATCH v4] sched/deadline: Change the time to replenish runtime for
 sleep tasks

Let's consider the following example.

                                  (N+1)th tick
                  (N)th tick                 |
                           |                 |
timeline : o...............o...o.........o...o...o..o
           ^                   ^         ^       ^  ^
           |                   |         |       |  |
       start                   |         |       |  |
                original runtime         |       |  |
                     sleep with (-)runtime       |  |
                                 original deadline  |
                                              wake up

When this task is woken up, a negative runtime should be considered,
which means that the task should get penalized when assigning runtime,
becasue it already spent more than expected. Current code handles this
by replenishing a runtime in hrtimer callback for deadline. But this
approach has room for improvement:

   We can avoid setting a deadline timer and save an interrupt if the
   task sleeps for long time so that the deadline passes, since that
   can be handled on wake-up.

So does not set a deadline timer in that case and force to replenish it
when waking it up.

Signed-off-by: Byungchul Park <byungchul.park@....com>
---
 kernel/sched/deadline.c | 36 +++++++++++++++++++++++++++++-------
 1 file changed, 29 insertions(+), 7 deletions(-)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 27737f3..e7a7209 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -498,13 +498,23 @@ static void update_dl_entity(struct sched_dl_entity *dl_se,
 	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
 	struct rq *rq = rq_of_dl_rq(dl_rq);
 
-	if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
-	    dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
+	if (dl_time_before(dl_se->deadline, rq_clock(rq)))
+		replenish_dl_entity(dl_se, pi_se);
+
+	if (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;
 	}
 }
 
+static inline void stop_dl_timer(struct task_struct *p)
+{
+	struct sched_dl_entity *dl_se = &p->dl;
+	struct hrtimer *timer = &dl_se->dl_timer;
+
+	hrtimer_try_to_cancel(timer);
+}
+
 /*
  * 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
@@ -621,13 +631,11 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
 	 *         __dequeue_task_dl()
 	 *     prev->on_rq = 0;
 	 *
-	 * We can be both throttled and !queued. Replenish the counter
-	 * but do not enqueue -- wait for our wakeup to do that.
+	 * We can be both throttled and !queued. Wait for our wakeup to
+	 * replenish runtime and enqueue p.
 	 */
-	if (!task_on_rq_queued(p)) {
-		replenish_dl_entity(dl_se, dl_se);
+	if (!task_on_rq_queued(p))
 		goto unlock;
-	}
 
 #ifdef CONFIG_SMP
 	if (unlikely(!rq->online)) {
@@ -956,6 +964,13 @@ static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
 	if (p->dl.dl_throttled && !(flags & ENQUEUE_REPLENISH))
 		return;
 
+	/*
+	 * start_dl_timer() would do nothing if already deadline < now.
+	 * The case will be handled in update_dl_entity().
+	 */
+	if (p->dl.dl_throttled && (flags & ENQUEUE_WAKEUP))
+		start_dl_timer(p);
+
 	enqueue_dl_entity(&p->dl, pi_se, flags);
 
 	if (!task_current(rq, p) && tsk_nr_cpus_allowed(p) > 1)
@@ -964,6 +979,13 @@ static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
 
 static void __dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags)
 {
+	/*
+	 * Runtime will be replenished on wake-up. We can avoid
+	 * unnecessary timer interrupt in this case.
+	 */
+	if (p->dl.dl_throttled && (flags & DEQUEUE_SLEEP))
+		stop_dl_timer(p);
+
 	dequeue_dl_entity(&p->dl);
 	dequeue_pushable_dl_task(rq, p);
 }
-- 
1.9.1