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

Groups > linux.kernel > #1513370 > unrolled thread

Re: [RFC v3 2/6] Improve the tracking of active utilisation

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [RFC v3 2/6] Improve the tracking of active utilisation Juri Lelli <juri.lelli@arm.com> - 2016-11-01 17:50 +0100
    Re: [RFC v3 2/6] Improve the tracking of active utilisation luca abeni <luca.abeni@unitn.it> - 2016-11-01 22:50 +0100
      Re: [RFC v3 2/6] Improve the tracking of active utilisation luca abeni <luca.abeni@unitn.it> - 2016-11-02 03:40 +0100
        Re: [RFC v3 2/6] Improve the tracking of active utilisation Juri Lelli <juri.lelli@arm.com> - 2016-11-10 11:10 +0100
          Re: [RFC v3 2/6] Improve the tracking of active utilisation Juri Lelli <juri.lelli@arm.com> - 2016-11-10 13:00 +0100
            Re: [RFC v3 2/6] Improve the tracking of active utilisation luca abeni <luca.abeni@unitn.it> - 2016-11-10 13:20 +0100
              Re: [RFC v3 2/6] Improve the tracking of active utilisation Juri Lelli <juri.lelli@arm.com> - 2016-11-10 13:40 +0100
                Re: [RFC v3 2/6] Improve the tracking of active utilisation luca abeni <luca.abeni@unitn.it> - 2016-11-10 13:50 +0100

#1513370 — Re: [RFC v3 2/6] Improve the tracking of active utilisation

Hi,

On 24/10/16 16:06, Luca Abeni wrote:
> This patch implements a more theoretically sound algorithm for
> thracking the active utilisation: instead of decreasing it when a

s/thracking/tracking/
s/the//

> 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".

s/utilisaation/utilisation/

> 
> 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);

This and the one below go in 1/6.

>  	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);

Why we are OK with just trying to cancel the inactive timer?

> +		WARN_ON(dl_task_of(dl_se)->nr_cpus_allowed > 1);

What's wrong with nr_cpus_allowed > 1 tasks?

> +	} 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);

Can't we subtract twice if it happens that after we grabbed rq_lock the timer
fired, so it's now waiting for that lock and it goes ahead and sub_running_bw
again after we release the lock?

> +	}
> +	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));

Don't we still need to wait for the 0-lag? Or maybe since the task is dying we
can release it's bw instantaneously? In this case I'd add a comment about it.

> +		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.

But, from a theoretical pow, we very much should, right?
Is this taken care of in next patch?

> +	 */
> +	if (hrtimer_is_queued(&p->dl.inactive_timer))
>  		sub_running_bw(&p->dl, &rq->dl);
>  

Thanks,

- Juri

[toc] | [next] | [standalone]

#1513534

Hi Juri,

On Tue, 1 Nov 2016 16:46:04 +0000
Juri Lelli <juri.lelli@arm.com> wrote:
[...]
> > 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);  
> 
> This and the one below go in 1/6.
Ok; I'll move it there


> 
> >  	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);  
> 
> Why we are OK with just trying to cancel the inactive timer?
This is my understanding of the things: if the timer cannot be
cancelled, it either:
1) Already decreased the active utilisation (and the timer handler is
   just finishing its execution). In this case, cancelling it or not
   cancelling it does not make any difference
2) Still have to decrease the active utilisation (and is probably
   waiting for the runqueue lock). In this case, the timer handler
   will find the task RUNNING, and will not decrease the active
   utilisation

> 
> > +		WARN_ON(dl_task_of(dl_se)->nr_cpus_allowed > 1);  
> 
> What's wrong with nr_cpus_allowed > 1 tasks?
If nr_cpus_allowed > 1, then select_task_rq_dl() executed before
enqueueing the task, and it already took care of cancelling the
inactive timer. I added this WARN_ON() to check for possible races
between the timer handler and select_task_rq / enqueue_task_dl...
I tried hard to trigger such a race, but the WARN_ON() never
happened (it only happened when I had tasks bound to one single
CPU - I tried this combination for testing purposes).

[...]
> > @@ -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);  
> 
> Can't we subtract twice if it happens that after we grabbed rq_lock the timer
> fired, so it's now waiting for that lock and it goes ahead and sub_running_bw
> again after we release the lock?
Uhm... I somehow convinced myself that this could not happen, but I do not
remember the details, sorry :(
I'll check again in the next days (BTW, wouldn't this trigger the WARN_ON you
mentioned above?)


> 
> > +	}
> > +	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));  
> 
> Don't we still need to wait for the 0-lag? Or maybe since the task is dying we
> can release it's bw instantaneously? In this case I'd add a comment about it.
Uhmm... I think you are right; I'll double-check this.


> >  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.  
> 
> But, from a theoretical pow, we very much should, right?
Yes, we should.

> Is this taken care of in next patch?
No, I left this small divergence between theory and practice. The problem is
that the inactive timer handler looks at the task's runqueue, and decreases
the active utilization of such a runqueue. If the task is a SCHED_DEADLINE
task, this is not an issue, because the inactive timer is armed when the
task is not on a runqueue... When the task is inserted in a runqueue again,
the timer is cancelled. But when the task becomes SCHED_NORMAL, it can go
on a runqueue (and migrate to different runqueues) without cancelling the
inactive timer... So, when the inactive timer fires we have no guarantee
that the task's runqueue is still the one from which we need to subtract
the utilisation (I've actually seen this bug in action, before changing the
code in the way it is now).

If this is not acceptable, I'll try to find another solution to this issue.




			Thanks,
				Luca

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

#1513624

On Tue, 1 Nov 2016 22:46:33 +0100
luca abeni <luca.abeni@unitn.it> wrote:
[...]
> > > @@ -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);    
> > 
> > Can't we subtract twice if it happens that after we grabbed rq_lock the timer
> > fired, so it's now waiting for that lock and it goes ahead and sub_running_bw
> > again after we release the lock?  
> Uhm... I somehow convinced myself that this could not happen, but I do not
> remember the details, sorry :(
I think I remember the answer now: pi_lock is acquired before invoking select_task_rq
and is released after invoking enqueue_task... So, if there is a pending inactive
timer, its handler will be executed after the task is enqueued... It will see the task
as RUNNING, and will not decrease the active utilisation.

Does this make sense?



				Luca

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

#1518824

On 02/11/16 03:35, Luca Abeni wrote:
> On Tue, 1 Nov 2016 22:46:33 +0100
> luca abeni <luca.abeni@unitn.it> wrote:
> [...]
> > > > @@ -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);    
> > > 
> > > Can't we subtract twice if it happens that after we grabbed rq_lock the timer
> > > fired, so it's now waiting for that lock and it goes ahead and sub_running_bw
> > > again after we release the lock?  
> > Uhm... I somehow convinced myself that this could not happen, but I do not
> > remember the details, sorry :(
> I think I remember the answer now: pi_lock is acquired before invoking select_task_rq
> and is released after invoking enqueue_task... So, if there is a pending inactive
> timer, its handler will be executed after the task is enqueued... It will see the task
> as RUNNING, and will not decrease the active utilisation.
> 

Oh, because we do task_rq_lock() inactive_task_timer(). So, that should
save us from the double subtract. Would you mind adding something along
the line of what you said above as a comment for next version?

Thanks,

- Juri

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

#1518917

On 10/11/16 10:04, Juri Lelli wrote:
> On 02/11/16 03:35, Luca Abeni wrote:
> > On Tue, 1 Nov 2016 22:46:33 +0100
> > luca abeni <luca.abeni@unitn.it> wrote:
> > [...]
> > > > > @@ -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);    
> > > > 
> > > > Can't we subtract twice if it happens that after we grabbed rq_lock the timer
> > > > fired, so it's now waiting for that lock and it goes ahead and sub_running_bw
> > > > again after we release the lock?  
> > > Uhm... I somehow convinced myself that this could not happen, but I do not
> > > remember the details, sorry :(
> > I think I remember the answer now: pi_lock is acquired before invoking select_task_rq
> > and is released after invoking enqueue_task... So, if there is a pending inactive
> > timer, its handler will be executed after the task is enqueued... It will see the task
> > as RUNNING, and will not decrease the active utilisation.
> > 
> 
> Oh, because we do task_rq_lock() inactive_task_timer(). So, that should
> save us from the double subtract. Would you mind adding something along
> the line of what you said above as a comment for next version?
> 

Mmm, wait again.

Cannot the following happen?

 - inactive_timer fires and does sub_running_bw (as the task is not
   RUNNING)
 - another cpu does try_to_wake_up and blocks on pi_lock
 - inactive timer releases both pi and rq locks (but is still executing,
   let's say it is doing put_task_struct())
 - try_to_wake_up goes ahead and calls select_task_rq_dl
   + it finds inactive_timer active
   + sub_running_bw again :(

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

#1518933

On Thu, 10 Nov 2016 11:56:10 +0000
Juri Lelli <juri.lelli@arm.com> wrote:

> On 10/11/16 10:04, Juri Lelli wrote:
> > On 02/11/16 03:35, Luca Abeni wrote:  
> > > On Tue, 1 Nov 2016 22:46:33 +0100
> > > luca abeni <luca.abeni@unitn.it> wrote:
> > > [...]  
> > > > > > @@ -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);      
> > > > > 
> > > > > Can't we subtract twice if it happens that after we grabbed
> > > > > rq_lock the timer fired, so it's now waiting for that lock
> > > > > and it goes ahead and sub_running_bw again after we release
> > > > > the lock?    
> > > > Uhm... I somehow convinced myself that this could not happen,
> > > > but I do not remember the details, sorry :(  
> > > I think I remember the answer now: pi_lock is acquired before
> > > invoking select_task_rq and is released after invoking
> > > enqueue_task... So, if there is a pending inactive timer, its
> > > handler will be executed after the task is enqueued... It will
> > > see the task as RUNNING, and will not decrease the active
> > > utilisation. 
> > 
> > Oh, because we do task_rq_lock() inactive_task_timer(). So, that
> > should save us from the double subtract. Would you mind adding
> > something along the line of what you said above as a comment for
> > next version? 
> 
> Mmm, wait again.
> 
> Cannot the following happen?
> 
>  - inactive_timer fires and does sub_running_bw (as the task is not
>    RUNNING)
>  - another cpu does try_to_wake_up and blocks on pi_lock
>  - inactive timer releases both pi and rq locks (but is still
> executing, let's say it is doing put_task_struct())
>  - try_to_wake_up goes ahead and calls select_task_rq_dl
>    + it finds inactive_timer active
>    + sub_running_bw again :(
Uhm... Right; this can happen :(

Ok; I'll think about some possible solution for this race... If I do
not find any simple way to solve it, I'll add a "contending" flag,
which allows to know if the inactive timer handler already executed or
not.

BTW, talking about sched_dl_entity flags: I see there are three
different int fields "dl_throttled, "dl_boosted" and "dl_yielded"; any
reason for doing this instead of having a "dl_flags" field and setting
its different bits when the entity is throttled, boosted or yielded? In
other words: if I need this "contending" flag, should I add a new
"dl_contending" field?



			Thanks,
				Luca

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

#1518951

On 10/11/16 13:15, Luca Abeni wrote:
> On Thu, 10 Nov 2016 11:56:10 +0000
> Juri Lelli <juri.lelli@arm.com> wrote:
> 
> > On 10/11/16 10:04, Juri Lelli wrote:
> > > On 02/11/16 03:35, Luca Abeni wrote:  
> > > > On Tue, 1 Nov 2016 22:46:33 +0100
> > > > luca abeni <luca.abeni@unitn.it> wrote:
> > > > [...]  
> > > > > > > @@ -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);      
> > > > > > 
> > > > > > Can't we subtract twice if it happens that after we grabbed
> > > > > > rq_lock the timer fired, so it's now waiting for that lock
> > > > > > and it goes ahead and sub_running_bw again after we release
> > > > > > the lock?    
> > > > > Uhm... I somehow convinced myself that this could not happen,
> > > > > but I do not remember the details, sorry :(  
> > > > I think I remember the answer now: pi_lock is acquired before
> > > > invoking select_task_rq and is released after invoking
> > > > enqueue_task... So, if there is a pending inactive timer, its
> > > > handler will be executed after the task is enqueued... It will
> > > > see the task as RUNNING, and will not decrease the active
> > > > utilisation. 
> > > 
> > > Oh, because we do task_rq_lock() inactive_task_timer(). So, that
> > > should save us from the double subtract. Would you mind adding
> > > something along the line of what you said above as a comment for
> > > next version? 
> > 
> > Mmm, wait again.
> > 
> > Cannot the following happen?
> > 
> >  - inactive_timer fires and does sub_running_bw (as the task is not
> >    RUNNING)
> >  - another cpu does try_to_wake_up and blocks on pi_lock
> >  - inactive timer releases both pi and rq locks (but is still
> > executing, let's say it is doing put_task_struct())
> >  - try_to_wake_up goes ahead and calls select_task_rq_dl
> >    + it finds inactive_timer active
> >    + sub_running_bw again :(
> Uhm... Right; this can happen :(
> 

:(

> Ok; I'll think about some possible solution for this race... If I do
> not find any simple way to solve it, I'll add a "contending" flag,
> which allows to know if the inactive timer handler already executed or
> not.
> 

Right, this might help.

Another thing that I was thinking of is whether we can use the return
value of hrtimer_try_to_cancel() to decide what to do:

 - if it returns 0 it means that the callback exectuted or the timer was
   never set, so nothing to do (as in nothing to sub_running_bw from)
 - if it returns 1 we succedeed, so we need to actively sub_running_bw
 - if -1 we can assume that it will eventually do sub_running_bw() so we
   don't need to care explicitly

Now I guess the problem is that the task can be migrated while his
inactive_timer is set (by select_task_rq_dl or by other classes load
balacing if setscheduled to a different class). Can't we store a back
reference to the rq from which the inactive_timer was queued and use
that to sub_running_bw() from? It seems that we might end up with some
"shadow" bandwidth, say when we do a wakeup migration, but maybe this is
something we can tolerate? Just thinking aloud. :)

> BTW, talking about sched_dl_entity flags: I see there are three
> different int fields "dl_throttled, "dl_boosted" and "dl_yielded"; any
> reason for doing this instead of having a "dl_flags" field and setting
> its different bits when the entity is throttled, boosted or yielded? In
> other words: if I need this "contending" flag, should I add a new
> "dl_contending" field?
> 

I think you might want to add a clean-up patch to your series (or a
separate one) fixing the current situation, and the build on to adding
the new flag if needed.

Thanks,

- Juri

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

#1518955

On Thu, 10 Nov 2016 12:34:15 +0000
Juri Lelli <juri.lelli@arm.com> wrote:
[...]
> > Ok; I'll think about some possible solution for this race... If I do
> > not find any simple way to solve it, I'll add a "contending" flag,
> > which allows to know if the inactive timer handler already executed
> > or not.
> >   
> 
> Right, this might help.
> 
> Another thing that I was thinking of is whether we can use the return
> value of hrtimer_try_to_cancel() to decide what to do:
> 
>  - if it returns 0 it means that the callback exectuted or the timer
> was never set, so nothing to do (as in nothing to sub_running_bw from)
>  - if it returns 1 we succedeed, so we need to actively sub_running_bw
>  - if -1 we can assume that it will eventually do sub_running_bw() so
> we don't need to care explicitly
This is about what I did in the initial version of the patch, but I
found some problems... I'll try to have another look at this approach.


> Now I guess the problem is that the task can be migrated while his
> inactive_timer is set (by select_task_rq_dl or by other classes load
> balacing if setscheduled to a different class). Can't we store a back
> reference to the rq from which the inactive_timer was queued and use
> that to sub_running_bw() from? It seems that we might end up with some
> "shadow" bandwidth, say when we do a wakeup migration, but maybe this
> is something we can tolerate? Just thinking aloud. :)
I'll think about this...


> > BTW, talking about sched_dl_entity flags: I see there are three
> > different int fields "dl_throttled, "dl_boosted" and "dl_yielded";
> > any reason for doing this instead of having a "dl_flags" field and
> > setting its different bits when the entity is throttled, boosted or
> > yielded? In other words: if I need this "contending" flag, should I
> > add a new "dl_contending" field?
> >   
> 
> I think you might want to add a clean-up patch to your series (or a
> separate one) fixing the current situation, and the build on to adding
> the new flag if needed.
Ok, can do this. I just wanted to know if there is a reason for having
different "dl_*" fields instead of a "flags" field (I do not know,
maybe performance?) or if it is just an historical accident and this
can be changed.



			Thanks,
				Luca

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web