[PATCH v2 1/2] sched/deadline: Factor out the actual work replenishing runtime

[PATCH v2 1/2] sched/deadline: Factor out the actual work replenishing runtime

[Byungchul Park]

The actual work replenishing runtime can also be used by other than
replenish_dl_entiry(). So factor this out into a separate function so
that others can use it.

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

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 27737f3..69e3fbb 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -359,6 +359,39 @@ static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se)
 	dl_se->runtime = dl_se->dl_runtime;
 }
 
+static void __replenish_dl_entity(struct sched_dl_entity *dl_se,
+				  struct sched_dl_entity *pi_se)
+{
+	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
+	struct rq *rq = rq_of_dl_rq(dl_rq);
+
+	/*
+	 * We keep moving the deadline away until we get some
+	 * available runtime for the entity. This ensures correct
+	 * handling of situations where the runtime overrun is
+	 * arbitrary large.
+	 */
+	while (dl_se->runtime <= 0) {
+		dl_se->deadline += pi_se->dl_period;
+		dl_se->runtime += pi_se->dl_runtime;
+	}
+
+	/*
+	 * At this point, the deadline really should be "in
+	 * the future" with respect to rq->clock. If it's
+	 * not, we are, for some reason, lagging too much!
+	 * Anyway, after having warn userspace abut that,
+	 * we still try to keep the things running by
+	 * resetting the deadline and the budget of the
+	 * entity.
+	 */
+	if (dl_time_before(dl_se->deadline, rq_clock(rq))) {
+		printk_deferred_once("sched: DL replenish lagged too much\n");
+		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
+		dl_se->runtime = pi_se->dl_runtime;
+	}
+}
+
 /*
  * Pure Earliest Deadline First (EDF) scheduling does not deal with the
  * possibility of a entity lasting more than what it declared, and thus
@@ -397,31 +430,7 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se,
 	if (dl_se->dl_yielded && dl_se->runtime > 0)
 		dl_se->runtime = 0;
 
-	/*
-	 * We keep moving the deadline away until we get some
-	 * available runtime for the entity. This ensures correct
-	 * handling of situations where the runtime overrun is
-	 * arbitrary large.
-	 */
-	while (dl_se->runtime <= 0) {
-		dl_se->deadline += pi_se->dl_period;
-		dl_se->runtime += pi_se->dl_runtime;
-	}
-
-	/*
-	 * At this point, the deadline really should be "in
-	 * the future" with respect to rq->clock. If it's
-	 * not, we are, for some reason, lagging too much!
-	 * Anyway, after having warn userspace abut that,
-	 * we still try to keep the things running by
-	 * resetting the deadline and the budget of the
-	 * entity.
-	 */
-	if (dl_time_before(dl_se->deadline, rq_clock(rq))) {
-		printk_deferred_once("sched: DL replenish lagged too much\n");
-		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
-		dl_se->runtime = pi_se->dl_runtime;
-	}
+	__replenish_dl_entity(dl_se, pi_se);
 
 	if (dl_se->dl_yielded)
 		dl_se->dl_yielded = 0;
-- 
1.9.1

[PATCH v2 2/2] sched/deadline: Change the way to replenish runtime for sleep tasks

[Byungchul Park]

Let's consider the following example.

timeline : 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 in two ways:

   1. No need to keep the hrtimer for a sleep task because it can be
      handled when waking it up.

   2. It will be replenished twice unnecessarily if the task sleeps for
      long time so that the deadline, assigned in the hrtimer callback,
      also passed. In other words, one happens in the callback and the
      other happens in update_dl_entiry() when waking it up.

So try to cancel the hrtimer for a sleep task and make all these things
handled when waking it up.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 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 69e3fbb..b59ee7b 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -507,8 +507,10 @@ 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;
 	}
@@ -981,6 +983,9 @@ static void dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags)
 {
 	update_curr_dl(rq);
 	__dequeue_task_dl(rq, p, flags);
+
+	if (flags & DEQUEUE_SLEEP)
+		hrtimer_try_to_cancel(&p->dl.dl_timer);
 }
 
 /*
-- 
1.9.1

RE: [PATCH v2 2/2] sched/deadline: Change the way to replenish runtime for sleep tasks

[byungchul.park]

> -----Original Message-----
> From: Byungchul Park [mailto:byungchul.park@lge.com]
> Sent: Thursday, February 23, 2017 12:11 PM
> To: peterz@infradead.org; mingo@kernel.org
> Cc: linux-kernel@vger.kernel.org; juri.lelli@gmail.com;
> rostedt@goodmis.org; kernel-team@lge.com
> Subject: [PATCH v2 2/2] sched/deadline: Change the way to replenish
> runtime for sleep tasks
> 
> Let's consider the following example.
> 
> timeline : 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 in two ways:
> 
>    1. No need to keep the hrtimer for a sleep task because it can be
>       handled when waking it up.
> 
>    2. It will be replenished twice unnecessarily if the task sleeps for
>       long time so that the deadline, assigned in the hrtimer callback,
>       also passed. In other words, one happens in the callback and the
>       other happens in update_dl_entiry() when waking it up.
> 
> So try to cancel the hrtimer for a sleep task and make all these things
> handled when waking it up.
> 
> Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> ---
>  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 69e3fbb..b59ee7b 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -507,8 +507,10 @@ 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;
>  	}
> @@ -981,6 +983,9 @@ static void dequeue_task_dl(struct rq *rq, struct
> task_struct *p, int flags)
>  {
>  	update_curr_dl(rq);
>  	__dequeue_task_dl(rq, p, flags);
> +
> +	if (flags & DEQUEUE_SLEEP)
> +		hrtimer_try_to_cancel(&p->dl.dl_timer);

Sorry. I found I might have made a mistake. I might have to re-start the
timer when waking it up if necessary. Let me think more.

>  }
> 
>  /*
> --
> 1.9.1

Re: [PATCH v2 2/2] sched/deadline: Change the way to replenish runtime for sleep tasks

[Byungchul Park]

On Thu, Feb 23, 2017 at 12:18:48PM +0900, byungchul.park wrote:
> > Current code handles this by replenishing a runtime in hrtimer callback
> > for deadline. But this approach has room for improvement in two ways:
> > 
> >    1. No need to keep the hrtimer for a sleep task because it can be
> >       handled when waking it up.
> > 
> >    2. It will be replenished twice unnecessarily if the task sleeps for
> >       long time so that the deadline, assigned in the hrtimer callback,
> >       also passed. In other words, one happens in the callback and the
> >       other happens in update_dl_entiry() when waking it up.

I wanted to enhance not only the second but also the first, so remove
the unnecessary timer overhead for sleep tasks. It's possible but it
makes code too complecated and I won't do that.

I will resend a patch doing only the second one at the next spin.

Thank you,
Byungchul

> > @@ -981,6 +983,9 @@ static void dequeue_task_dl(struct rq *rq, struct
> > task_struct *p, int flags)
> >  {
> >  	update_curr_dl(rq);
> >  	__dequeue_task_dl(rq, p, flags);
> > +
> > +	if (flags & DEQUEUE_SLEEP)
> > +		hrtimer_try_to_cancel(&p->dl.dl_timer);
> 
> Sorry. I found I might have made a mistake. I might have to re-start the
> timer when waking it up if necessary. Let me think more.