Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1507223 > unrolled thread

[RFC v3 0/6] CPU reclaiming for SCHED_DEADLINE

Back to article view | Back to linux.kernel

Contents

  [RFC v3 0/6] CPU reclaiming for SCHED_DEADLINE  Luca Abeni <luca.abeni@unitn.it> - 2016-10-24 16:10 +0200
    [RFC v3 5/6] Do not reclaim the whole CPU bandwidth Luca Abeni <luca.abeni@unitn.it> - 2016-10-24 16:10 +0200
    [RFC v3 1/6] Track the active utilisation Luca Abeni <luca.abeni@unitn.it> - 2016-10-24 16:10 +0200
      Re: [RFC v3 1/6] Track the active utilisation Daniel Bristot de Oliveira <bristot@redhat.com> - 2016-10-25 11:20 +0200
        Re: [RFC v3 1/6] Track the active utilisation luca abeni <luca.abeni@unitn.it> - 2016-10-25 11:30 +0200
          Re: [RFC v3 1/6] Track the active utilisation Steven Rostedt <rostedt@goodmis.org> - 2016-10-25 16:00 +0200
            Re: [RFC v3 1/6] Track the active utilisation Luca Abeni <luca.abeni@unitn.it> - 2016-10-25 20:10 +0200
    [RFC v3 2/6] Improve the tracking of active utilisation Luca Abeni <luca.abeni@unitn.it> - 2016-10-24 16:10 +0200
    [RFC v3 3/6] Fix the update of the total -deadline utilization Luca Abeni <luca.abeni@unitn.it> - 2016-10-24 16:10 +0200
    [RFC v3 4/6] GRUB accounting Luca Abeni <luca.abeni@unitn.it> - 2016-10-24 16:10 +0200

#1507223 — [RFC v3 0/6] CPU reclaiming for SCHED_DEADLINE

Hi all,

this patchset implements CPU reclaiming (using the GRUB algorithm[1])
for SCHED_DEADLINE: basically, this feature allows SCHED_DEADLINE tasks
to consume more than their reserved runtime, up to a maximum fraction
of the CPU time (so that other tasks are left some spare CPU time to
execute), if this does not break the guarantees of other SCHED_DEADLINE
tasks.
The patchset applies on top of tip/master.


The implemented CPU reclaiming algorithm is based on tracking the
utilization U_act of active tasks (first 2 patches), and modifying the
runtime accounting rule (see patch 0004). The original GRUB algorithm is
modified as described in [2] to support multiple CPUs (the original
algorithm only considered one single CPU, this one tracks U_act per
runqueue) and to leave an "unreclaimable" fraction of CPU time to non
SCHED_DEADLINE tasks (see patch 0005: the original algorithm can consume
100% of the CPU time, starving all the other tasks).
Patch 0003 uses the newly introduced "inactive timer" (introduced in
patch 0002) to fix dl_overflow() and __setparam_dl().
Patch 0006 allows to enable CPU reclaiming only on selected tasks.


Changes since v2:
in general, I tried to address all the comments I received, and to add
some more comments in "critical" parts of the code. In particular, I:
- Updated to latest tip/master. This required some changes (for example,
  using "struct rq_flags" instead of "unsigned long" for task_rq_lock())
- Merged patches 0001 and 0002, as suggested by Juri
- Added some comments about GRUB in the changelog of the patch adding
  GRUB accounting
- Exchanged the order of two patches ("Make GRUB a task's flag" and
  "Do not reclaim the whole CPU bandwidth"), as suggested by Juri
- Removed unused code ("if (task_on_rq_queued(p))" in task_dead_dl(),
  noticed by Peter) from patch 0001
- Properly consider the migrations of queued dl tasks when updating
  the active utilization. This should address Peter's concern from
  http://lkml.iu.edu/hypermail/linux/kernel/1604.0/02612.html
- Simplified the code for setting up the inactive timer, as suggested
  by Peter: http://lkml.iu.edu/hypermail/linux/kernel/1604.0/02620.html
- Use hrtimer_is_queued() instead of "(hrtimer_active() &&
  !hrtimer_callback_running())", as pointed out by Peter:
  http://lkml.iu.edu/hypermail/linux/kernel/1604.0/02805.html
- Fix select_task_rq_dl() (using "task_cpu(p) != cpu" instead
  of "rq != cpu_rq(cpu)"), as pointed out by Peter:
  http://lkml.iu.edu/hypermail/linux/kernel/1604.0/02822.html
  I also changed the logic used in select_task_rq_dl()
  (that now does not increase the active utilization in the selected
  runqueue)
- Because of the changes in the code, I am not sure if the race condition
  pointed out by Peter can still happen. I tried to trigger it in many ways,
  but I failed... If it turns out that the race is still possible, I'll fix
  it in the next round of patches, by introducing a new "is_contending" field
  (protected by pi_mutex) in the dl scheduling entity.


[1] Lipari, G., & Baruah, S. (2000). Greedy reclamation of unused bandwidth in constant-bandwidth servers. In Real-Time Systems, 2000. Euromicro RTS 2000. 12th Euromicro Conference on (pp. 193-200). IEEE.
[2] Abeni, L., Lelli, J., Scordino, C., & Palopoli, L. (2014, October). Greedy CPU reclaiming for SCHED DEADLINE. In Proceedings of the Real-Time Linux Workshop (RTLWS), Dusseldorf, Germany. 



Luca Abeni (6):
  Track the active utilisation
  Improve the tracking of active utilisation
  Fix the update of the total -deadline utilization
  GRUB accounting
  Do not reclaim the whole CPU bandwidth
  Make GRUB a task's flag

 include/linux/sched.h      |   1 +
 include/uapi/linux/sched.h |   1 +
 kernel/sched/core.c        |  44 ++++-----
 kernel/sched/deadline.c    | 220 ++++++++++++++++++++++++++++++++++++++++-----
 kernel/sched/sched.h       |  13 +++
 5 files changed, 234 insertions(+), 45 deletions(-)

-- 
2.7.4

[toc] | [next] | [standalone]

#1507224 — [RFC v3 5/6] Do not reclaim the whole CPU bandwidth

Original GRUB tends to reclaim 100% of the CPU time... And this allows a
CPU hot to starve non-deadline tasks.
To address this issue, allow the scheduler to reclaim only a specified
fraction of CPU time.

Signed-off-by: Luca Abeni <luca.abeni@unitn.it>
---
 kernel/sched/core.c     | 4 ++++
 kernel/sched/deadline.c | 7 ++++++-
 kernel/sched/sched.h    | 6 ++++++
 3 files changed, 16 insertions(+), 1 deletion(-)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 337a5f0..6706b5f 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -8256,6 +8256,10 @@ static void sched_dl_do_global(void)
 		raw_spin_unlock_irqrestore(&dl_b->lock, flags);
 
 		rcu_read_unlock_sched();
+		if (dl_b->bw == -1)
+			cpu_rq(cpu)->dl.non_deadline_bw = 0;
+		else
+			cpu_rq(cpu)->dl.non_deadline_bw = (1 << 20) - new_bw;
 	}
 }
 
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index fa10fcd..cab76e8 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -147,6 +147,11 @@ void init_dl_rq(struct dl_rq *dl_rq)
 #else
 	init_dl_bw(&dl_rq->dl_bw);
 #endif
+	if (global_rt_runtime() == RUNTIME_INF)
+		dl_rq->non_deadline_bw = 0;
+	else
+		dl_rq->non_deadline_bw = (1 << 20) -
+			to_ratio(global_rt_period(), global_rt_runtime());
 }
 
 #ifdef CONFIG_SMP
@@ -780,7 +785,7 @@ extern bool sched_rt_bandwidth_account(struct rt_rq *rt_rq);
  */
 u64 grub_reclaim(u64 delta, struct rq *rq)
 {
-	return (delta * rq->dl.running_bw) >> 20;
+	return (delta * (rq->dl.non_deadline_bw + rq->dl.running_bw)) >> 20;
 }
 
 /*
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index e82c419..2748431 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -541,6 +541,12 @@ struct dl_rq {
 	 * task blocks
 	 */
 	s64 running_bw;
+
+	/*
+	 * Fraction of the CPU utilization that cannot be reclaimed
+	 * by the GRUB algorithm.
+	 */
+	s64 non_deadline_bw;
 };
 
 #ifdef CONFIG_SMP
-- 
2.7.4

[toc] | [prev] | [next] | [standalone]

#1507225 — [RFC v3 1/6] Track the active utilisation

The active utilisation here is defined as the total utilisation of the
active (TASK_RUNNING) tasks queued on a runqueue. Hence, it is increased
when a task wakes up and is decreased when a task blocks.

When a task is migrated from CPUi to CPUj, immediately subtract the task's
utilisation from CPUi and add it to CPUj. This mechanism is implemented by
modifying the pull and push functions.
Note: this is not fully correct from the theoretical point of view
(the utilisation should be removed from CPUi only at the 0 lag time),
but doing the right thing would be _MUCH_ more complex (leaving the
timer armed when the task is on a different CPU... Inactive timers should
be moved from per-task timers to per-runqueue lists of timers! Bah...)

The utilisation tracking mechanism implemented in this commit can be
fixed / improved by decreasing the active utilisation at the so-called
"0-lag time" instead of when the task blocks.

Signed-off-by: Juri Lelli <juri.lelli@arm.com>
Signed-off-by: Luca Abeni <luca.abeni@unitn.it>
---
 kernel/sched/deadline.c | 39 ++++++++++++++++++++++++++++++++++++++-
 kernel/sched/sched.h    |  6 ++++++
 2 files changed, 44 insertions(+), 1 deletion(-)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 37e2449..3d95c1d 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -43,6 +43,22 @@ static inline int on_dl_rq(struct sched_dl_entity *dl_se)
 	return !RB_EMPTY_NODE(&dl_se->rb_node);
 }
 
+static void add_running_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
+{
+	u64 se_bw = dl_se->dl_bw;
+
+	dl_rq->running_bw += se_bw;
+}
+
+static void sub_running_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
+{
+	u64 se_bw = dl_se->dl_bw;
+
+	dl_rq->running_bw -= se_bw;
+	if (WARN_ON(dl_rq->running_bw < 0))
+		dl_rq->running_bw = 0;
+}
+
 static inline int is_leftmost(struct task_struct *p, struct dl_rq *dl_rq)
 {
 	struct sched_dl_entity *dl_se = &p->dl;
@@ -498,6 +514,8 @@ 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);
 
+	add_running_bw(dl_se, dl_rq);
+
 	if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
 	    dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
 		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
@@ -947,14 +965,19 @@ static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
 		return;
 	}
 
+	if (p->on_rq == TASK_ON_RQ_MIGRATING)
+		add_running_bw(&p->dl, &rq->dl);
+
 	/*
 	 * If p is throttled, we do nothing. In fact, if it exhausted
 	 * its budget it needs a replenishment and, since it now is on
 	 * its rq, the bandwidth timer callback (which clearly has not
 	 * run yet) will take care of this.
 	 */
-	if (p->dl.dl_throttled && !(flags & ENQUEUE_REPLENISH))
+	if (p->dl.dl_throttled && !(flags & ENQUEUE_REPLENISH)) {
+		add_running_bw(&p->dl, &rq->dl);
 		return;
+	}
 
 	enqueue_dl_entity(&p->dl, pi_se, flags);
 
@@ -972,6 +995,12 @@ 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 (p->on_rq == TASK_ON_RQ_MIGRATING)
+		sub_running_bw(&p->dl, &rq->dl);
+
+	if (flags & DEQUEUE_SLEEP)
+		sub_running_bw(&p->dl, &rq->dl);
 }
 
 /*
@@ -1501,7 +1530,9 @@ static int push_dl_task(struct rq *rq)
 	}
 
 	deactivate_task(rq, next_task, 0);
+	sub_running_bw(&next_task->dl, &rq->dl);
 	set_task_cpu(next_task, later_rq->cpu);
+	add_running_bw(&next_task->dl, &later_rq->dl);
 	activate_task(later_rq, next_task, 0);
 	ret = 1;
 
@@ -1589,7 +1620,9 @@ static void pull_dl_task(struct rq *this_rq)
 			resched = true;
 
 			deactivate_task(src_rq, p, 0);
+			sub_running_bw(&p->dl, &src_rq->dl);
 			set_task_cpu(p, this_cpu);
+			add_running_bw(&p->dl, &this_rq->dl);
 			activate_task(this_rq, p, 0);
 			dmin = p->dl.deadline;
 
@@ -1695,6 +1728,9 @@ static void switched_from_dl(struct rq *rq, struct task_struct *p)
 	if (!start_dl_timer(p))
 		__dl_clear_params(p);
 
+	if (task_on_rq_queued(p))
+		sub_running_bw(&p->dl, &rq->dl);
+
 	/*
 	 * Since this might be the only -deadline task on the rq,
 	 * this is the right place to try to pull some other one
@@ -1712,6 +1748,7 @@ static void switched_from_dl(struct rq *rq, struct task_struct *p)
  */
 static void switched_to_dl(struct rq *rq, struct task_struct *p)
 {
+	add_running_bw(&p->dl, &rq->dl);
 
 	/* If p is not queued we will update its parameters at next wakeup. */
 	if (!task_on_rq_queued(p))
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 055f935..3a36c74 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -535,6 +535,12 @@ struct dl_rq {
 #else
 	struct dl_bw dl_bw;
 #endif
+	/*
+	 * "Active utilization" for this runqueue: increased when a
+	 * task wakes up (becomes TASK_RUNNING) and decreased when a
+	 * task blocks
+	 */
+	s64 running_bw;
 };
 
 #ifdef CONFIG_SMP
-- 
2.7.4

[toc] | [prev] | [next] | [standalone]

#1508101 — Re: [RFC v3 1/6] Track the active utilisation

Il 24/10/2016 16:06, Luca Abeni ha scritto:
> The active utilisation here is defined as the total utilisation of the
> active (TASK_RUNNING) tasks queued on a runqueue. Hence, it is increased
> when a task wakes up and is decreased when a task blocks.
> 
> When a task is migrated from CPUi to CPUj, immediately subtract the task's
> utilisation from CPUi and add it to CPUj. This mechanism is implemented by
> modifying the pull and push functions.
> Note: this is not fully correct from the theoretical point of view
> (the utilisation should be removed from CPUi only at the 0 lag time),
> but doing the right thing would be _MUCH_ more complex (leaving the
> timer armed when the task is on a different CPU... Inactive timers should
> be moved from per-task timers to per-runqueue lists of timers! Bah...)
> 
> The utilisation tracking mechanism implemented in this commit can be
> fixed / improved by decreasing the active utilisation at the so-called
> "0-lag time" instead of when the task blocks.
> 
> Signed-off-by: Juri Lelli <juri.lelli@arm.com>
> Signed-off-by: Luca Abeni <luca.abeni@unitn.it>
> ---
>  kernel/sched/deadline.c | 39 ++++++++++++++++++++++++++++++++++++++-
>  kernel/sched/sched.h    |  6 ++++++
>  2 files changed, 44 insertions(+), 1 deletion(-)
> 
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index 37e2449..3d95c1d 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -43,6 +43,22 @@ static inline int on_dl_rq(struct sched_dl_entity *dl_se)
>  	return !RB_EMPTY_NODE(&dl_se->rb_node);
>  }
>  
> +static void add_running_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
> +{
> +	u64 se_bw = dl_se->dl_bw;
> +
> +	dl_rq->running_bw += se_bw;
> +}

why not...

static *inline*
void add_running_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
{
	dl_rq->running_bw += dl_se->dl_bw;
}

am I missing something?

> +static void sub_running_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
> +{
> +	u64 se_bw = dl_se->dl_bw;
> +
> +	dl_rq->running_bw -= se_bw;
> +	if (WARN_ON(dl_rq->running_bw < 0))
> +		dl_rq->running_bw = 0;
> +}

(if I am not missing anything...)

the same in the above function: use inline and remove the se_bw variable.

-- Daniel

[toc] | [prev] | [next] | [standalone]

#1508112 — Re: [RFC v3 1/6] Track the active utilisation

Hi Daniel,

On Tue, 25 Oct 2016 11:09:52 +0200
Daniel Bristot de Oliveira <bristot@redhat.com> wrote:
[...]
> > +static void add_running_bw(struct sched_dl_entity *dl_se, struct
> > dl_rq *dl_rq) +{
> > +	u64 se_bw = dl_se->dl_bw;
> > +
> > +	dl_rq->running_bw += se_bw;
> > +}  
> 
> why not...
> 
> static *inline*
> void add_running_bw(struct sched_dl_entity *dl_se, struct dl_rq
> *dl_rq) {
> 	dl_rq->running_bw += dl_se->dl_bw;
> }
> 
> am I missing something?

I do not know... Maybe I am the one missing something :)
I assumed that the compiler is smart enough to inline the function (and
to avoid creating a local variable on the stack), but if there is
agreement I can change the function in this way.



			Thanks,
				Luca


> 
> > +static void sub_running_bw(struct sched_dl_entity *dl_se, struct
> > dl_rq *dl_rq) +{
> > +	u64 se_bw = dl_se->dl_bw;
> > +
> > +	dl_rq->running_bw -= se_bw;
> > +	if (WARN_ON(dl_rq->running_bw < 0))
> > +		dl_rq->running_bw = 0;
> > +}  
> 
> (if I am not missing anything...)
> 
> the same in the above function: use inline and remove the se_bw
> variable.
> 
> -- Daniel

[toc] | [prev] | [next] | [standalone]

#1508309 — Re: [RFC v3 1/6] Track the active utilisation

On Tue, 25 Oct 2016 11:29:16 +0200
luca abeni <luca.abeni@unitn.it> wrote:

> Hi Daniel,
> 
> On Tue, 25 Oct 2016 11:09:52 +0200
> Daniel Bristot de Oliveira <bristot@redhat.com> wrote:
> [...]
> > > +static void add_running_bw(struct sched_dl_entity *dl_se, struct
> > > dl_rq *dl_rq) +{
> > > +	u64 se_bw = dl_se->dl_bw;
> > > +
> > > +	dl_rq->running_bw += se_bw;
> > > +}    
> > 
> > why not...
> > 
> > static *inline*
> > void add_running_bw(struct sched_dl_entity *dl_se, struct dl_rq
> > *dl_rq) {
> > 	dl_rq->running_bw += dl_se->dl_bw;
> > }
> > 
> > am I missing something?  
> 
> I do not know... Maybe I am the one missing something :)
> I assumed that the compiler is smart enough to inline the function (and
> to avoid creating a local variable on the stack), but if there is
> agreement I can change the function in this way.
> 
> 

I agree with Daniel, especially since I don't usually trust the
compiler. And the added variable is more of a distraction as it doesn't
seem to have any real purpose.

-- Steve

[toc] | [prev] | [next] | [standalone]

#1508529 — Re: [RFC v3 1/6] Track the active utilisation

On Tue, 25 Oct 2016 09:58:11 -0400
Steven Rostedt <rostedt@goodmis.org> wrote:

> On Tue, 25 Oct 2016 11:29:16 +0200
> luca abeni <luca.abeni@unitn.it> wrote:
> 
> > Hi Daniel,
> > 
> > On Tue, 25 Oct 2016 11:09:52 +0200
> > Daniel Bristot de Oliveira <bristot@redhat.com> wrote:
> > [...]
> > > > +static void add_running_bw(struct sched_dl_entity *dl_se,
> > > > struct dl_rq *dl_rq) +{
> > > > +	u64 se_bw = dl_se->dl_bw;
> > > > +
> > > > +	dl_rq->running_bw += se_bw;
> > > > +}    
> > > 
> > > why not...
> > > 
> > > static *inline*
> > > void add_running_bw(struct sched_dl_entity *dl_se, struct dl_rq
> > > *dl_rq) {
> > > 	dl_rq->running_bw += dl_se->dl_bw;
> > > }
> > > 
> > > am I missing something?  
> > 
> > I do not know... Maybe I am the one missing something :)
> > I assumed that the compiler is smart enough to inline the function
> > (and to avoid creating a local variable on the stack), but if there
> > is agreement I can change the function in this way.
> > 
> > 
> 
> I agree with Daniel, especially since I don't usually trust the
> compiler. And the added variable is more of a distraction as it
> doesn't seem to have any real purpose.

Ok, then; I'll fix this in the next round of patches.


		Thanks,
			Luca

[toc] | [prev] | [next] | [standalone]

#1507229 — [RFC v3 2/6] Improve the tracking of active utilisation

This patch implements a more theoretically sound algorithm for
thracking the active utilisation: instead of decreasing it when a
task blocks, use a timer (the "inactive timer", named after the
"Inactive" task state of the GRUB algorithm) to decrease the
active utilisaation at the so called "0-lag time".

Signed-off-by: Luca Abeni <luca.abeni@unitn.it>
---
 include/linux/sched.h   |   1 +
 kernel/sched/core.c     |   1 +
 kernel/sched/deadline.c | 139 ++++++++++++++++++++++++++++++++++++++++++------
 kernel/sched/sched.h    |   1 +
 4 files changed, 126 insertions(+), 16 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 348f51b..22543c6 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1433,6 +1433,7 @@ struct sched_dl_entity {
 	 * own bandwidth to be enforced, thus we need one timer per task.
 	 */
 	struct hrtimer dl_timer;
+	struct hrtimer inactive_timer;
 };
 
 union rcu_special {
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 94732d1..664c618 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -2217,6 +2217,7 @@ static void __sched_fork(unsigned long clone_flags, struct task_struct *p)
 
 	RB_CLEAR_NODE(&p->dl.rb_node);
 	init_dl_task_timer(&p->dl);
+	init_inactive_task_timer(&p->dl);
 	__dl_clear_params(p);
 
 	INIT_LIST_HEAD(&p->rt.run_list);
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 3d95c1d..80d1541 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -47,6 +47,7 @@ static void add_running_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
 {
 	u64 se_bw = dl_se->dl_bw;
 
+	lockdep_assert_held(&(rq_of_dl_rq(dl_rq))->lock);
 	dl_rq->running_bw += se_bw;
 }
 
@@ -54,11 +55,52 @@ static void sub_running_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
 {
 	u64 se_bw = dl_se->dl_bw;
 
+	lockdep_assert_held(&(rq_of_dl_rq(dl_rq))->lock);
 	dl_rq->running_bw -= se_bw;
 	if (WARN_ON(dl_rq->running_bw < 0))
 		dl_rq->running_bw = 0;
 }
 
+static void task_go_inactive(struct task_struct *p)
+{
+	struct sched_dl_entity *dl_se = &p->dl;
+	struct hrtimer *timer = &dl_se->inactive_timer;
+	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
+	struct rq *rq = rq_of_dl_rq(dl_rq);
+	s64 zerolag_time;
+
+	WARN_ON(dl_se->dl_runtime == 0);
+
+	/* If the inactive timer is already armed, return immediately */
+	if (hrtimer_active(&dl_se->inactive_timer))
+		return;
+
+	zerolag_time = dl_se->deadline -
+		 div64_long((dl_se->runtime * dl_se->dl_period),
+			dl_se->dl_runtime);
+
+	/*
+	 * Using relative times instead of the absolute "0-lag time"
+	 * allows to simplify the code
+	 */
+	zerolag_time -= rq_clock(rq);
+
+	/*
+	 * If the "0-lag time" already passed, decrease the active
+	 * utilization now, instead of starting a timer
+	 */
+	if (zerolag_time < 0) {
+		sub_running_bw(dl_se, dl_rq);
+		if (!dl_task(p))
+			__dl_clear_params(p);
+
+		return;
+	}
+
+	get_task_struct(p);
+	hrtimer_start(timer, ns_to_ktime(zerolag_time), HRTIMER_MODE_REL);
+}
+
 static inline int is_leftmost(struct task_struct *p, struct dl_rq *dl_rq)
 {
 	struct sched_dl_entity *dl_se = &p->dl;
@@ -514,7 +556,20 @@ 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);
 
-	add_running_bw(dl_se, dl_rq);
+	if (hrtimer_is_queued(&dl_se->inactive_timer)) {
+		hrtimer_try_to_cancel(&dl_se->inactive_timer);
+		WARN_ON(dl_task_of(dl_se)->nr_cpus_allowed > 1);
+	} else {
+		/*
+		 * The "inactive timer" has been cancelled in
+		 * select_task_rq_dl() (and the acvive utilisation has
+		 * been decreased). So, increase the active utilisation.
+		 * If select_task_rq_dl() could not cancel the timer,
+		 * inactive_task_timer() will * find the task state as
+		 * TASK_RUNNING, and will do nothing, so we are still safe.
+		 */
+		add_running_bw(dl_se, dl_rq);
+	}
 
 	if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
 	    dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
@@ -602,14 +657,8 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
 
 	rq = task_rq_lock(p, &rf);
 
-	/*
-	 * The task might have changed its scheduling policy to something
-	 * different than SCHED_DEADLINE (through switched_fromd_dl()).
-	 */
-	if (!dl_task(p)) {
-		__dl_clear_params(p);
+	if (!dl_task(p))
 		goto unlock;
-	}
 
 	/*
 	 * The task might have been boosted by someone else and might be in the
@@ -796,6 +845,44 @@ static void update_curr_dl(struct rq *rq)
 	}
 }
 
+static enum hrtimer_restart inactive_task_timer(struct hrtimer *timer)
+{
+	struct sched_dl_entity *dl_se = container_of(timer,
+						     struct sched_dl_entity,
+						     inactive_timer);
+	struct task_struct *p = dl_task_of(dl_se);
+	struct rq_flags rf;
+	struct rq *rq;
+
+	rq = task_rq_lock(p, &rf);
+
+	if (!dl_task(p)) {
+		__dl_clear_params(p);
+
+		goto unlock;
+	}
+	if (p->state == TASK_RUNNING)
+		goto unlock;
+
+	sched_clock_tick();
+	update_rq_clock(rq);
+
+	sub_running_bw(dl_se, &rq->dl);
+unlock:
+	task_rq_unlock(rq, p, &rf);
+	put_task_struct(p);
+
+	return HRTIMER_NORESTART;
+}
+
+void init_inactive_task_timer(struct sched_dl_entity *dl_se)
+{
+	struct hrtimer *timer = &dl_se->inactive_timer;
+
+	hrtimer_init(timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
+	timer->function = inactive_task_timer;
+}
+
 #ifdef CONFIG_SMP
 
 static void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline)
@@ -1000,7 +1087,7 @@ static void dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags)
 		sub_running_bw(&p->dl, &rq->dl);
 
 	if (flags & DEQUEUE_SLEEP)
-		sub_running_bw(&p->dl, &rq->dl);
+		task_go_inactive(p);
 }
 
 /*
@@ -1074,6 +1161,14 @@ select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags)
 	}
 	rcu_read_unlock();
 
+	rq = task_rq(p);
+	raw_spin_lock(&rq->lock);
+	if (hrtimer_active(&p->dl.inactive_timer)) {
+		sub_running_bw(&p->dl, &rq->dl);
+		hrtimer_try_to_cancel(&p->dl.inactive_timer);
+	}
+	raw_spin_unlock(&rq->lock);
+
 out:
 	return cpu;
 }
@@ -1244,6 +1339,11 @@ static void task_dead_dl(struct task_struct *p)
 	/* XXX we should retain the bw until 0-lag */
 	dl_b->total_bw -= p->dl.dl_bw;
 	raw_spin_unlock_irq(&dl_b->lock);
+	if (hrtimer_active(&p->dl.inactive_timer)) {
+		raw_spin_lock_irq(&task_rq(p)->lock);
+		sub_running_bw(&p->dl, dl_rq_of_se(&p->dl));
+		raw_spin_unlock_irq(&task_rq(p)->lock);
+	}
 }
 
 static void set_curr_task_dl(struct rq *rq)
@@ -1720,15 +1820,22 @@ void __init init_sched_dl_class(void)
 static void switched_from_dl(struct rq *rq, struct task_struct *p)
 {
 	/*
-	 * Start the deadline timer; if we switch back to dl before this we'll
-	 * continue consuming our current CBS slice. If we stay outside of
-	 * SCHED_DEADLINE until the deadline passes, the timer will reset the
-	 * task.
+	 * task_go_inactive() can start the "inactive timer" (if the 0-lag
+	 * time is in the future). If the task switches back to dl before
+	 * the "inactive timer" fires, it can continue to consume its current
+	 * runtime using its current deadline. If it stays outside of
+	 * SCHED_DEADLINE until the 0-lag time passes, inactive_task_timer()
+	 * will reset the task parameters.
 	 */
-	if (!start_dl_timer(p))
-		__dl_clear_params(p);
+	if (task_on_rq_queued(p) && p->dl.dl_runtime)
+		task_go_inactive(p);
 
-	if (task_on_rq_queued(p))
+	/*
+	 * We cannot use inactive_task_timer() to invoke sub_running_bw()
+	 * at the 0-lag time, because the task could have been migrated
+	 * while SCHED_OTHER in the meanwhile.
+	 */
+	if (hrtimer_is_queued(&p->dl.inactive_timer))
 		sub_running_bw(&p->dl, &rq->dl);
 
 	/*
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 3a36c74..e82c419 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -1358,6 +1358,7 @@ extern void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime
 extern struct dl_bandwidth def_dl_bandwidth;
 extern void init_dl_bandwidth(struct dl_bandwidth *dl_b, u64 period, u64 runtime);
 extern void init_dl_task_timer(struct sched_dl_entity *dl_se);
+extern void init_inactive_task_timer(struct sched_dl_entity *dl_se);
 
 unsigned long to_ratio(u64 period, u64 runtime);
 
-- 
2.7.4

[toc] | [prev] | [next] | [standalone]

#1507230 — [RFC v3 3/6] Fix the update of the total -deadline utilization

Now that the inactive timer can be armed to fire at the 0-lag time,
it is possible to use inactive_task_timer() to update the total
-deadline utilization (dl_b->total_bw) at the correct time, fixing
dl_overflow() and __setparam_dl().

Signed-off-by: Luca Abeni <luca.abeni@unitn.it>
---
 kernel/sched/core.c     | 36 ++++++++++++------------------------
 kernel/sched/deadline.c | 34 +++++++++++++++++++++++++---------
 2 files changed, 37 insertions(+), 33 deletions(-)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 664c618..337a5f0 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -2507,9 +2507,6 @@ static inline int dl_bw_cpus(int i)
  * allocated bandwidth to reflect the new situation.
  *
  * This function is called while holding p's rq->lock.
- *
- * XXX we should delay bw change until the task's 0-lag point, see
- * __setparam_dl().
  */
 static int dl_overflow(struct task_struct *p, int policy,
 		       const struct sched_attr *attr)
@@ -2538,11 +2535,22 @@ static int dl_overflow(struct task_struct *p, int policy,
 		err = 0;
 	} else if (dl_policy(policy) && task_has_dl_policy(p) &&
 		   !__dl_overflow(dl_b, cpus, p->dl.dl_bw, new_bw)) {
+		/*
+		 * XXX this is slightly incorrect: when the task
+		 * utilization decreases, we should delay the total
+		 * utilization change until the task's 0-lag point.
+		 * But this would require to set the task's "inactive
+		 * timer" when the task is not inactive.
+		 */
 		__dl_clear(dl_b, p->dl.dl_bw);
 		__dl_add(dl_b, new_bw);
 		err = 0;
 	} else if (!dl_policy(policy) && task_has_dl_policy(p)) {
-		__dl_clear(dl_b, p->dl.dl_bw);
+		/*
+		 * Do not decrease the total deadline utilization here,
+		 * switched_from_dl() will take care to do it at the correct
+		 * (0-lag) time.
+		 */
 		err = 0;
 	}
 	raw_spin_unlock(&dl_b->lock);
@@ -3912,26 +3920,6 @@ __setparam_dl(struct task_struct *p, const struct sched_attr *attr)
 	dl_se->dl_period = attr->sched_period ?: dl_se->dl_deadline;
 	dl_se->flags = attr->sched_flags;
 	dl_se->dl_bw = to_ratio(dl_se->dl_period, dl_se->dl_runtime);
-
-	/*
-	 * Changing the parameters of a task is 'tricky' and we're not doing
-	 * the correct thing -- also see task_dead_dl() and switched_from_dl().
-	 *
-	 * What we SHOULD do is delay the bandwidth release until the 0-lag
-	 * point. This would include retaining the task_struct until that time
-	 * and change dl_overflow() to not immediately decrement the current
-	 * amount.
-	 *
-	 * Instead we retain the current runtime/deadline and let the new
-	 * parameters take effect after the current reservation period lapses.
-	 * This is safe (albeit pessimistic) because the 0-lag point is always
-	 * before the current scheduling deadline.
-	 *
-	 * We can still have temporary overloads because we do not delay the
-	 * change in bandwidth until that time; so admission control is
-	 * not on the safe side. It does however guarantee tasks will never
-	 * consume more than promised.
-	 */
 }
 
 /*
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 80d1541..4d3545b 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -91,8 +91,14 @@ static void task_go_inactive(struct task_struct *p)
 	 */
 	if (zerolag_time < 0) {
 		sub_running_bw(dl_se, dl_rq);
-		if (!dl_task(p))
+		if (!dl_task(p)) {
+			struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
+
+			raw_spin_lock(&dl_b->lock);
+			__dl_clear(dl_b, p->dl.dl_bw);
 			__dl_clear_params(p);
+			raw_spin_unlock(&dl_b->lock);
+		}
 
 		return;
 	}
@@ -856,8 +862,13 @@ static enum hrtimer_restart inactive_task_timer(struct hrtimer *timer)
 
 	rq = task_rq_lock(p, &rf);
 
-	if (!dl_task(p)) {
+	if (!dl_task(p) || p->state == TASK_DEAD) {
+		struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
+
+		raw_spin_lock(&dl_b->lock);
+		__dl_clear(dl_b, p->dl.dl_bw);
 		__dl_clear_params(p);
+		raw_spin_unlock(&dl_b->lock);
 
 		goto unlock;
 	}
@@ -1330,16 +1341,21 @@ static void task_fork_dl(struct task_struct *p)
 
 static void task_dead_dl(struct task_struct *p)
 {
-	struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
-
 	/*
 	 * Since we are TASK_DEAD we won't slip out of the domain!
 	 */
-	raw_spin_lock_irq(&dl_b->lock);
-	/* XXX we should retain the bw until 0-lag */
-	dl_b->total_bw -= p->dl.dl_bw;
-	raw_spin_unlock_irq(&dl_b->lock);
-	if (hrtimer_active(&p->dl.inactive_timer)) {
+	if (!hrtimer_active(&p->dl.inactive_timer)) {
+		struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
+
+		/*
+		 * If the "inactive timer is not active, the 0-lag time
+		 * is already passed, so we immediately decrease the
+		 * total deadline utilization
+		 */
+		raw_spin_lock_irq(&dl_b->lock);
+		__dl_clear(dl_b, p->dl.dl_bw);
+		raw_spin_unlock_irq(&dl_b->lock);
+	} else {
 		raw_spin_lock_irq(&task_rq(p)->lock);
 		sub_running_bw(&p->dl, dl_rq_of_se(&p->dl));
 		raw_spin_unlock_irq(&task_rq(p)->lock);
-- 
2.7.4

[toc] | [prev] | [next] | [standalone]

#1507231 — [RFC v3 4/6] GRUB accounting

According to the GRUB (Greedy Reclaimation of Unused Bandwidth) reclaiming
algorithm, the runtime is not decreased as "dq = -dt", but as
"dq = -Uact dt" (where Uact is the per-runqueue active utilization).
Hence, this commit modifies the runtime accounting rule in update_curr_dl()
to implement the GRUB rule.

Signed-off-by: Luca Abeni <luca.abeni@unitn.it>
---
 kernel/sched/deadline.c | 14 ++++++++++++++
 1 file changed, 14 insertions(+)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 4d3545b..fa10fcd 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -771,6 +771,19 @@ int dl_runtime_exceeded(struct sched_dl_entity *dl_se)
 extern bool sched_rt_bandwidth_account(struct rt_rq *rt_rq);
 
 /*
+ * This function implements the GRUB accounting rule:
+ * according to the GRUB reclaiming algorithm, the runtime is
+ * not decreased as "dq = -dt", but as "dq = -Uact dt", where
+ * Uact is the (per-runqueue) active utilization.
+ * Since rq->dl.running_bw contains Uact * 2^20, the result
+ * has to be shifted right by 20.
+ */
+u64 grub_reclaim(u64 delta, struct rq *rq)
+{
+	return (delta * rq->dl.running_bw) >> 20;
+}
+
+/*
  * Update the current task's runtime statistics (provided it is still
  * a -deadline task and has not been removed from the dl_rq).
  */
@@ -812,6 +825,7 @@ static void update_curr_dl(struct rq *rq)
 
 	sched_rt_avg_update(rq, delta_exec);
 
+	delta_exec = grub_reclaim(delta_exec, rq);
 	dl_se->runtime -= delta_exec;
 
 throttle:
-- 
2.7.4

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web