[PATCH v2 0/3] Update blocked load

[PATCH v2 0/3] Update blocked load

[Vincent Guittot]

This patchset applies on top of Peter's sched/esting branch minus the last 2 commit:
56eb46798b33 ("sched: Clean up nohz enter/exit")

v2:
- minor naming updates

Vincent Guittot (3):
  sched: Stop nohz stats when decayed
  sched: reduce the periodic update duration
  sched: update blocked load when newly idle

 kernel/sched/fair.c  | 203 ++++++++++++++++++++++++++++++++++++++++++---------
 kernel/sched/sched.h |   1 +
 2 files changed, 169 insertions(+), 35 deletions(-)

-- 
2.7.4

[PATCH v2 1/3] sched: Stop nohz stats when decayed

[Vincent Guittot]

Stopped the periodic update of blocked load when all idle CPUs have fully
decayed. We introduce a new nohz.has_blocked that reflect if some idle
CPUs has blocked load that have to be periodiccally updated. nohz.has_blocked
is set everytime that a Idle CPU can have blocked load and it is then clear
when no more blocked load has been detected during an update. We don't need
atomic operation but only to make cure of the right ordering when updating
nohz.idle_cpus_mask and nohz.has_blocked.

Suggested-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
---
 kernel/sched/fair.c  | 94 +++++++++++++++++++++++++++++++++++++++++-----------
 kernel/sched/sched.h |  1 +
 2 files changed, 75 insertions(+), 20 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 7af1fa9..b9660b5 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -5383,8 +5383,9 @@ decay_load_missed(unsigned long load, unsigned long missed_updates, int idx)
 static struct {
 	cpumask_var_t idle_cpus_mask;
 	atomic_t nr_cpus;
+	int has_blocked;		/* Idle CPUS has blocked load */
 	unsigned long next_balance;     /* in jiffy units */
-	unsigned long next_stats;
+	unsigned long next_blocked;	/* Next update of blocked load in jiffies */
 } nohz ____cacheline_aligned;
 
 #endif /* CONFIG_NO_HZ_COMMON */
@@ -6951,6 +6952,7 @@ enum fbq_type { regular, remote, all };
 #define LBF_DST_PINNED  0x04
 #define LBF_SOME_PINNED	0x08
 #define LBF_NOHZ_STATS	0x10
+#define LBF_NOHZ_AGAIN	0x20
 
 struct lb_env {
 	struct sched_domain	*sd;
@@ -7335,8 +7337,6 @@ static void attach_tasks(struct lb_env *env)
 	rq_unlock(env->dst_rq, &rf);
 }
 
-#ifdef CONFIG_FAIR_GROUP_SCHED
-
 static inline bool cfs_rq_is_decayed(struct cfs_rq *cfs_rq)
 {
 	if (cfs_rq->load.weight)
@@ -7354,11 +7354,14 @@ static inline bool cfs_rq_is_decayed(struct cfs_rq *cfs_rq)
 	return true;
 }
 
+#ifdef CONFIG_FAIR_GROUP_SCHED
+
 static void update_blocked_averages(int cpu)
 {
 	struct rq *rq = cpu_rq(cpu);
 	struct cfs_rq *cfs_rq, *pos;
 	struct rq_flags rf;
+	bool done = true;
 
 	rq_lock_irqsave(rq, &rf);
 	update_rq_clock(rq);
@@ -7388,10 +7391,14 @@ static void update_blocked_averages(int cpu)
 		 */
 		if (cfs_rq_is_decayed(cfs_rq))
 			list_del_leaf_cfs_rq(cfs_rq);
+		else
+			done = false;
 	}
 
 #ifdef CONFIG_NO_HZ_COMMON
 	rq->last_blocked_load_update_tick = jiffies;
+	if (done)
+		rq->has_blocked_load = 0;
 #endif
 	rq_unlock_irqrestore(rq, &rf);
 }
@@ -7454,6 +7461,8 @@ static inline void update_blocked_averages(int cpu)
 	update_cfs_rq_load_avg(cfs_rq_clock_task(cfs_rq), cfs_rq);
 #ifdef CONFIG_NO_HZ_COMMON
 	rq->last_blocked_load_update_tick = jiffies;
+	if (cfs_rq_is_decayed(cfs_rq))
+		rq->has_blocked_load = 0;
 #endif
 	rq_unlock_irqrestore(rq, &rf);
 }
@@ -7789,18 +7798,25 @@ group_type group_classify(struct sched_group *group,
 	return group_other;
 }
 
-static void update_nohz_stats(struct rq *rq)
+static bool update_nohz_stats(struct rq *rq)
 {
 #ifdef CONFIG_NO_HZ_COMMON
 	unsigned int cpu = rq->cpu;
 
+	if (!rq->has_blocked_load)
+		return false;
+
 	if (!cpumask_test_cpu(cpu, nohz.idle_cpus_mask))
-		return;
+		return false;
 
 	if (!time_after(jiffies, rq->last_blocked_load_update_tick))
-		return;
+		return true;
 
 	update_blocked_averages(cpu);
+
+	return rq->has_blocked_load;
+#else
+	return false;
 #endif
 }
 
@@ -7826,8 +7842,8 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 	for_each_cpu_and(i, sched_group_span(group), env->cpus) {
 		struct rq *rq = cpu_rq(i);
 
-		if (env->flags & LBF_NOHZ_STATS)
-			update_nohz_stats(rq);
+		if ((env->flags & LBF_NOHZ_STATS) && update_nohz_stats(rq))
+			env->flags |= LBF_NOHZ_AGAIN;
 
 		/* Bias balancing toward cpus of our domain */
 		if (local_group)
@@ -7979,18 +7995,15 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
 	struct sg_lb_stats *local = &sds->local_stat;
 	struct sg_lb_stats tmp_sgs;
 	int load_idx, prefer_sibling = 0;
+	int has_blocked = READ_ONCE(nohz.has_blocked);
 	bool overload = false;
 
 	if (child && child->flags & SD_PREFER_SIBLING)
 		prefer_sibling = 1;
 
 #ifdef CONFIG_NO_HZ_COMMON
-	if (env->idle == CPU_NEWLY_IDLE) {
+	if (env->idle == CPU_NEWLY_IDLE && has_blocked)
 		env->flags |= LBF_NOHZ_STATS;
-
-		if (cpumask_subset(nohz.idle_cpus_mask, sched_domain_span(env->sd)))
-			nohz.next_stats = jiffies + msecs_to_jiffies(LOAD_AVG_PERIOD);
-	}
 #endif
 
 	load_idx = get_sd_load_idx(env->sd, env->idle);
@@ -8046,6 +8059,15 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
 		sg = sg->next;
 	} while (sg != env->sd->groups);
 
+#ifdef CONFIG_NO_HZ_COMMON
+	if ((env->flags & LBF_NOHZ_AGAIN) &&
+	    cpumask_subset(nohz.idle_cpus_mask, sched_domain_span(env->sd))) {
+
+		WRITE_ONCE(nohz.next_blocked,
+				jiffies + msecs_to_jiffies(LOAD_AVG_PERIOD));
+	}
+#endif
+
 	if (env->sd->flags & SD_NUMA)
 		env->fbq_type = fbq_classify_group(&sds->busiest_stat);
 
@@ -9069,6 +9091,8 @@ static void nohz_balancer_kick(struct rq *rq)
 	struct sched_domain *sd;
 	int nr_busy, i, cpu = rq->cpu;
 	unsigned int flags = 0;
+	unsigned long has_blocked = READ_ONCE(nohz.has_blocked);
+	unsigned long next_blocked = READ_ONCE(nohz.next_blocked);
 
 	if (unlikely(rq->idle_balance))
 		return;
@@ -9086,7 +9110,7 @@ static void nohz_balancer_kick(struct rq *rq)
 	if (likely(!atomic_read(&nohz.nr_cpus)))
 		return;
 
-	if (time_after(now, nohz.next_stats))
+	if (time_after(now, next_blocked) && has_blocked)
 		flags = NOHZ_STATS_KICK;
 
 	if (time_before(now, nohz.next_balance))
@@ -9207,13 +9231,15 @@ void nohz_balance_enter_idle(int cpu)
 	if (!housekeeping_cpu(cpu, HK_FLAG_SCHED))
 		return;
 
+	rq->has_blocked_load = 1;
+
 	if (rq->nohz_tick_stopped)
-		return;
+		goto out;
 
 	/*
 	 * If we're a completely isolated CPU, we don't play.
 	 */
-	if (on_null_domain(cpu_rq(cpu)))
+	if (on_null_domain(rq))
 		return;
 
 	rq->nohz_tick_stopped = 1;
@@ -9222,6 +9248,13 @@ void nohz_balance_enter_idle(int cpu)
 	atomic_inc(&nohz.nr_cpus);
 
 	set_cpu_sd_state_idle(cpu);
+
+out:
+	/*
+	 * Each time a cpu enter idle, we assume that it has blocked load and
+	 * enable the periodic update of the load of idle cpus
+	 */
+	WRITE_ONCE(nohz.has_blocked, 1);
 }
 #else
 static inline void nohz_balancer_kick(struct rq *rq) { }
@@ -9374,6 +9407,16 @@ static bool nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 
 	SCHED_WARN_ON((flags & NOHZ_KICK_MASK) == NOHZ_BALANCE_KICK);
 
+	/*
+	 * We assume there will be no idle load after this update and clear
+	 * the has_blocked flag. If a cpu enters idle in the mean time, it will
+	 * set the has_blocked flag and trig another update of idle load.
+	 * Because a cpu that becomes idle, is added to idle_cpus_mask before
+	 * setting the flag, we are sure to not clear the state and not
+	 * check the load of an idle cpu.
+	 */
+	WRITE_ONCE(nohz.has_blocked, 0);
+
 	for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
 		if (balance_cpu == this_cpu || !idle_cpu(balance_cpu))
 			continue;
@@ -9383,11 +9426,16 @@ static bool nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 		 * work being done for other cpus. Next load
 		 * balancing owner will pick it up.
 		 */
-		if (need_resched())
-			break;
+		if (need_resched()) {
+			has_blocked_load = true;
+			goto abort;
+		}
 
 		rq = cpu_rq(balance_cpu);
 
+		update_blocked_averages(rq->cpu);
+		has_blocked_load |= rq->has_blocked_load;
+
 		/*
 		 * If time for next balance is due,
 		 * do the balance.
@@ -9400,7 +9448,6 @@ static bool nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 			cpu_load_update_idle(rq);
 			rq_unlock_irq(rq, &rf);
 
-			update_blocked_averages(rq->cpu);
 			if (flags & NOHZ_BALANCE_KICK)
 				rebalance_domains(rq, CPU_IDLE);
 		}
@@ -9415,7 +9462,13 @@ static bool nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 	if (flags & NOHZ_BALANCE_KICK)
 		rebalance_domains(this_rq, CPU_IDLE);
 
-	nohz.next_stats = next_stats;
+	WRITE_ONCE(nohz.next_blocked,
+		now + msecs_to_jiffies(LOAD_AVG_PERIOD));
+
+abort:
+	/* There is still blocked load, enable periodic update */
+	if (has_blocked_load)
+		WRITE_ONCE(nohz.has_blocked, 1);
 
 	/*
 	 * next_balance will be updated only when there is a need.
@@ -10046,6 +10099,7 @@ __init void init_sched_fair_class(void)
 
 #ifdef CONFIG_NO_HZ_COMMON
 	nohz.next_balance = jiffies;
+	nohz.next_blocked = jiffies;
 	zalloc_cpumask_var(&nohz.idle_cpus_mask, GFP_NOWAIT);
 #endif
 #endif /* SMP */
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index e200045..ad9b929 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -723,6 +723,7 @@ struct rq {
 #ifdef CONFIG_SMP
 	unsigned long last_load_update_tick;
 	unsigned long last_blocked_load_update_tick;
+	unsigned int has_blocked_load;
 #endif /* CONFIG_SMP */
 	unsigned int nohz_tick_stopped;
 	atomic_t nohz_flags;
-- 
2.7.4

Re: [PATCH v2 1/3] sched: Stop nohz stats when decayed

[Valentin Schneider]

On 02/06/2018 07:23 PM, Vincent Guittot wrote:
> [...]
> @@ -7826,8 +7842,8 @@ static inline void update_sg_lb_stats(struct lb_env *env,
>  	for_each_cpu_and(i, sched_group_span(group), env->cpus) {
>  		struct rq *rq = cpu_rq(i);
>  
> -		if (env->flags & LBF_NOHZ_STATS)
> -			update_nohz_stats(rq);
> +		if ((env->flags & LBF_NOHZ_STATS) && update_nohz_stats(rq))
> +			env->flags |= LBF_NOHZ_AGAIN;
>  
>  		/* Bias balancing toward cpus of our domain */
>  		if (local_group)
> @@ -7979,18 +7995,15 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
>  	struct sg_lb_stats *local = &sds->local_stat;
>  	struct sg_lb_stats tmp_sgs;
>  	int load_idx, prefer_sibling = 0;
> +	int has_blocked = READ_ONCE(nohz.has_blocked);
>  	bool overload = false;
>  
>  	if (child && child->flags & SD_PREFER_SIBLING)
>  		prefer_sibling = 1;
>  
>  #ifdef CONFIG_NO_HZ_COMMON
> -	if (env->idle == CPU_NEWLY_IDLE) {
> +	if (env->idle == CPU_NEWLY_IDLE && has_blocked)
>  		env->flags |= LBF_NOHZ_STATS;
> -
> -		if (cpumask_subset(nohz.idle_cpus_mask, sched_domain_span(env->sd)))
> -			nohz.next_stats = jiffies + msecs_to_jiffies(LOAD_AVG_PERIOD);
> -	}
>  #endif
>  
>  	load_idx = get_sd_load_idx(env->sd, env->idle);
> @@ -8046,6 +8059,15 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
>  		sg = sg->next;
>  	} while (sg != env->sd->groups);
>  
> +#ifdef CONFIG_NO_HZ_COMMON
> +	if ((env->flags & LBF_NOHZ_AGAIN) &&
> +	    cpumask_subset(nohz.idle_cpus_mask, sched_domain_span(env->sd))) {
> +
> +		WRITE_ONCE(nohz.next_blocked,
> +				jiffies + msecs_to_jiffies(LOAD_AVG_PERIOD));

Here we push the stats update forward if we visited all the nohz CPUs but they
still have blocked load. IMO we should also clear the nohz.has_blocked flag
if we visited all the nohz CPUs and none had blocked load left.

If we don't do that, we could very well have cleared all of the nohz blocked
load in idle_balance and successfully pulled a task, but the flag isn't
cleared so we'll end up doing a _nohz_idle_balance() later on for nothing.


As I said in a previous comment, we also have this problem with periodic
load balance: if a CPU goes nohz (nohz.has_blocked is raised) but wakes up,
e.g. before the next nohz.next_blocked, we should stop kicking ILBs

Now I'd need to test this, but I think it can actually get worse: if that 
CPU keeps generating blocked load after this short idle period, no matter 
how many _nohz_idle_balance() we go through we will never reach a point 
where nohz.has_blocked gets cleared, and we'll keep kicking those ILBs to
update blocked load that already gets updated in the periodic balance.

I think that's where a nohz blocked load cpumask can also help: on top of
skipping nohz CPUs that don't need an update, we can stop the whole remote
update machinery when the last nohz cpu with blocked load wakes up, or say
when it goes through its first periodic balance.

> +	}
> +#endif
> +

Re: [PATCH v2 1/3] sched: Stop nohz stats when decayed

[Peter Zijlstra]

On Thu, Feb 08, 2018 at 12:46:53PM +0000, Valentin Schneider wrote:
> On 02/06/2018 07:23 PM, Vincent Guittot wrote:
> > [...]
> > @@ -7826,8 +7842,8 @@ static inline void update_sg_lb_stats(struct lb_env *env,
> >  	for_each_cpu_and(i, sched_group_span(group), env->cpus) {
> >  		struct rq *rq = cpu_rq(i);
> >  
> > -		if (env->flags & LBF_NOHZ_STATS)
> > -			update_nohz_stats(rq);
> > +		if ((env->flags & LBF_NOHZ_STATS) && update_nohz_stats(rq))
> > +			env->flags |= LBF_NOHZ_AGAIN;
> >  
> >  		/* Bias balancing toward cpus of our domain */
> >  		if (local_group)
> > @@ -7979,18 +7995,15 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
> >  	struct sg_lb_stats *local = &sds->local_stat;
> >  	struct sg_lb_stats tmp_sgs;
> >  	int load_idx, prefer_sibling = 0;
> > +	int has_blocked = READ_ONCE(nohz.has_blocked);
> >  	bool overload = false;
> >  
> >  	if (child && child->flags & SD_PREFER_SIBLING)
> >  		prefer_sibling = 1;
> >  
> >  #ifdef CONFIG_NO_HZ_COMMON
> > -	if (env->idle == CPU_NEWLY_IDLE) {
> > +	if (env->idle == CPU_NEWLY_IDLE && has_blocked)
> >  		env->flags |= LBF_NOHZ_STATS;
> > -
> > -		if (cpumask_subset(nohz.idle_cpus_mask, sched_domain_span(env->sd)))
> > -			nohz.next_stats = jiffies + msecs_to_jiffies(LOAD_AVG_PERIOD);
> > -	}
> >  #endif
> >  
> >  	load_idx = get_sd_load_idx(env->sd, env->idle);
> > @@ -8046,6 +8059,15 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
> >  		sg = sg->next;
> >  	} while (sg != env->sd->groups);
> >  
> > +#ifdef CONFIG_NO_HZ_COMMON
> > +	if ((env->flags & LBF_NOHZ_AGAIN) &&
> > +	    cpumask_subset(nohz.idle_cpus_mask, sched_domain_span(env->sd))) {
> > +
> > +		WRITE_ONCE(nohz.next_blocked,
> > +				jiffies + msecs_to_jiffies(LOAD_AVG_PERIOD));
> 
> Here we push the stats update forward if we visited all the nohz CPUs but they
> still have blocked load. IMO we should also clear the nohz.has_blocked flag
> if we visited all the nohz CPUs and none had blocked load left.

You can't, new cpu's can have joined the set. I used to detect that, but
that requires atomic ops.

Re: [PATCH v2 1/3] sched: Stop nohz stats when decayed

[Vincent Guittot]

On 8 February 2018 at 13:46, Valentin Schneider
<valentin.schneider@arm.com> wrote:
> On 02/06/2018 07:23 PM, Vincent Guittot wrote:
>> [...]
>> @@ -7826,8 +7842,8 @@ static inline void update_sg_lb_stats(struct lb_env *env,
>>       for_each_cpu_and(i, sched_group_span(group), env->cpus) {
>>               struct rq *rq = cpu_rq(i);
>>
>> -             if (env->flags & LBF_NOHZ_STATS)
>> -                     update_nohz_stats(rq);
>> +             if ((env->flags & LBF_NOHZ_STATS) && update_nohz_stats(rq))
>> +                     env->flags |= LBF_NOHZ_AGAIN;
>>
>>               /* Bias balancing toward cpus of our domain */
>>               if (local_group)
>> @@ -7979,18 +7995,15 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
>>       struct sg_lb_stats *local = &sds->local_stat;
>>       struct sg_lb_stats tmp_sgs;
>>       int load_idx, prefer_sibling = 0;
>> +     int has_blocked = READ_ONCE(nohz.has_blocked);
>>       bool overload = false;
>>
>>       if (child && child->flags & SD_PREFER_SIBLING)
>>               prefer_sibling = 1;
>>
>>  #ifdef CONFIG_NO_HZ_COMMON
>> -     if (env->idle == CPU_NEWLY_IDLE) {
>> +     if (env->idle == CPU_NEWLY_IDLE && has_blocked)
>>               env->flags |= LBF_NOHZ_STATS;
>> -
>> -             if (cpumask_subset(nohz.idle_cpus_mask, sched_domain_span(env->sd)))
>> -                     nohz.next_stats = jiffies + msecs_to_jiffies(LOAD_AVG_PERIOD);
>> -     }
>>  #endif
>>
>>       load_idx = get_sd_load_idx(env->sd, env->idle);
>> @@ -8046,6 +8059,15 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
>>               sg = sg->next;
>>       } while (sg != env->sd->groups);
>>
>> +#ifdef CONFIG_NO_HZ_COMMON
>> +     if ((env->flags & LBF_NOHZ_AGAIN) &&
>> +         cpumask_subset(nohz.idle_cpus_mask, sched_domain_span(env->sd))) {
>> +
>> +             WRITE_ONCE(nohz.next_blocked,
>> +                             jiffies + msecs_to_jiffies(LOAD_AVG_PERIOD));
>
> Here we push the stats update forward if we visited all the nohz CPUs but they
> still have blocked load. IMO we should also clear the nohz.has_blocked flag
> if we visited all the nohz CPUs and none had blocked load left.
>
> If we don't do that, we could very well have cleared all of the nohz blocked
> load in idle_balance and successfully pulled a task, but the flag isn't
> cleared so we'll end up doing a _nohz_idle_balance() later on for nothing.
>
>
> As I said in a previous comment, we also have this problem with periodic
> load balance: if a CPU goes nohz (nohz.has_blocked is raised) but wakes up,
> e.g. before the next nohz.next_blocked, we should stop kicking ILBs
>
> Now I'd need to test this, but I think it can actually get worse: if that
> CPU keeps generating blocked load after this short idle period, no matter
> how many _nohz_idle_balance() we go through we will never reach a point
> where nohz.has_blocked gets cleared, and we'll keep kicking those ILBs to
> update blocked load that already gets updated in the periodic balance.
>
> I think that's where a nohz blocked load cpumask can also help: on top of
> skipping nohz CPUs that don't need an update, we can stop the whole remote
> update machinery when the last nohz cpu with blocked load wakes up, or say
> when it goes through its first periodic balance.

The main question is : Do we want to remove all useless kicks to ilb
or useless calls to _nohz_idle_balance at the cost of adding more
latency in the idle/wakeup path because of the additional atomic
operations to keep track of which CPUs are idle, tickless with blocked
load or do we accept to kick ilb or call _nohz_idle_balance uselessly
from time to time for some use cases

I agree with you that there are some useless calls with the proposal
which can be removed with additional checks, variables and cpumask
manipulation. Which use case will benefits from these additional
checks and does it worth ?

Vincent

>
>> +     }
>> +#endif
>> +
>

Re: [PATCH v2 1/3] sched: Stop nohz stats when decayed

[Valentin Schneider]

On 02/08/2018 01:36 PM, Vincent Guittot wrote:
> On 8 February 2018 at 13:46, Valentin Schneider
> <valentin.schneider@arm.com> wrote:
>> On 02/06/2018 07:23 PM, Vincent Guittot wrote:
>>> [...]
>>> @@ -7826,8 +7842,8 @@ static inline void update_sg_lb_stats(struct lb_env *env,
>>>       for_each_cpu_and(i, sched_group_span(group), env->cpus) {
>>>               struct rq *rq = cpu_rq(i);
>>>
>>> -             if (env->flags & LBF_NOHZ_STATS)
>>> -                     update_nohz_stats(rq);
>>> +             if ((env->flags & LBF_NOHZ_STATS) && update_nohz_stats(rq))
>>> +                     env->flags |= LBF_NOHZ_AGAIN;
>>>
>>>               /* Bias balancing toward cpus of our domain */
>>>               if (local_group)
>>> @@ -7979,18 +7995,15 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
>>>       struct sg_lb_stats *local = &sds->local_stat;
>>>       struct sg_lb_stats tmp_sgs;
>>>       int load_idx, prefer_sibling = 0;
>>> +     int has_blocked = READ_ONCE(nohz.has_blocked);
>>>       bool overload = false;
>>>
>>>       if (child && child->flags & SD_PREFER_SIBLING)
>>>               prefer_sibling = 1;
>>>
>>>  #ifdef CONFIG_NO_HZ_COMMON
>>> -     if (env->idle == CPU_NEWLY_IDLE) {
>>> +     if (env->idle == CPU_NEWLY_IDLE && has_blocked)
>>>               env->flags |= LBF_NOHZ_STATS;
>>> -
>>> -             if (cpumask_subset(nohz.idle_cpus_mask, sched_domain_span(env->sd)))
>>> -                     nohz.next_stats = jiffies + msecs_to_jiffies(LOAD_AVG_PERIOD);
>>> -     }
>>>  #endif
>>>
>>>       load_idx = get_sd_load_idx(env->sd, env->idle);
>>> @@ -8046,6 +8059,15 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
>>>               sg = sg->next;
>>>       } while (sg != env->sd->groups);
>>>
>>> +#ifdef CONFIG_NO_HZ_COMMON
>>> +     if ((env->flags & LBF_NOHZ_AGAIN) &&
>>> +         cpumask_subset(nohz.idle_cpus_mask, sched_domain_span(env->sd))) {
>>> +
>>> +             WRITE_ONCE(nohz.next_blocked,
>>> +                             jiffies + msecs_to_jiffies(LOAD_AVG_PERIOD));
>>
>> Here we push the stats update forward if we visited all the nohz CPUs but they
>> still have blocked load. IMO we should also clear the nohz.has_blocked flag
>> if we visited all the nohz CPUs and none had blocked load left.
>>
>> If we don't do that, we could very well have cleared all of the nohz blocked
>> load in idle_balance and successfully pulled a task, but the flag isn't
>> cleared so we'll end up doing a _nohz_idle_balance() later on for nothing.
>>
>>
>> As I said in a previous comment, we also have this problem with periodic
>> load balance: if a CPU goes nohz (nohz.has_blocked is raised) but wakes up,
>> e.g. before the next nohz.next_blocked, we should stop kicking ILBs
>>
>> Now I'd need to test this, but I think it can actually get worse: if that
>> CPU keeps generating blocked load after this short idle period, no matter
>> how many _nohz_idle_balance() we go through we will never reach a point
>> where nohz.has_blocked gets cleared, and we'll keep kicking those ILBs to
>> update blocked load that already gets updated in the periodic balance.
>>
>> I think that's where a nohz blocked load cpumask can also help: on top of
>> skipping nohz CPUs that don't need an update, we can stop the whole remote
>> update machinery when the last nohz cpu with blocked load wakes up, or say
>> when it goes through its first periodic balance.
> 
> The main question is : Do we want to remove all useless kicks to ilb
> or useless calls to _nohz_idle_balance at the cost of adding more
> latency in the idle/wakeup path because of the additional atomic
> operations to keep track of which CPUs are idle, tickless with blocked
> load or do we accept to kick ilb or call _nohz_idle_balance uselessly
> from time to time for some use cases
> 
> I agree with you that there are some useless calls with the proposal
> which can be removed with additional checks, variables and cpumask
> manipulation. Which use case will benefits from these additional
> checks and does it worth ?
> 
> Vincent

For now I've been using those made-up rt-app workloads to stress specific
bits of code, but I agree it would be really nice to have a "real" workload
to see how both power (additional kick_ilb()'s) and performance (additional
atomic ops) are affected. As Vincent suggested offline, it could be worth
giving it a shot on Android...


In the meantime I've done some more accurate profiling with cpumasks on my
Juno r2 (patch at the bottom). As a sidenote, I realised I don't have a test
case for the load update through load_balance() in idle_balance() - I only
test the !overload segment. Will think about that.

In summary:

20 iterations per test case
All non-mentioned CPUs are idling

---------------------
kick_ilb() test case:
---------------------

a, b = 100% rt-app tasks
- = idling

Accumulating load before sleeping
        ^
        ^
CPU1| a a a - - - a
CPU2| - - b b b b b
              v
              v > Periodically kicking ILBs to update nohz blocked load
	
Baseline:
    _nohz_idle_balance() takes 39µs in average
    nohz_balance_enter_idle() takes 233ns in average

W/ cpumask:
    _nohz_idle_balance() takes 33µs in average
    nohz_balance_enter_idle() takes 283ns in average

Diff:
    _nohz_idle_balance() -6µs in average (-16%)
    nohz_balance_enter_idle() +50ns in average (+21%)


---------------------------------------------------
Local _nohz_idle_balance() for NEWLY_IDLE test case:
---------------------------------------------------

a = 100% rt-app task
b = periodic rt-app task
- = idling

Accumulating load before sleeping
        ^
        ^
CPU1| a a a - - - - - a
CPU2| - - b - b - b - b
               v
               v > Periodically updating nohz blocked load through local
                   _nohz_idle_balance() in idle_balance()


(execution times are x2 as fast as previous test case because CPU2 is a
big CPU, whereas CPU0 - the ILB 99% of the time in the previous test - is a
LITTLE CPU ~ half as powerful).

Baseline:
    _nohz_idle_balance() takes 20µs in average
    nohz_balance_enter_idle() takes 183ns in average

W/ cpumask:
    _nohz_idle_balance() takes 13µs in average
    nohz_balance_enter_idle() takes 217ns in average

Diff:
    _nohz_idle_balance() -7µs in average (-38%)
    nohz_balance_enter_idle() +34ns in average (+18%)



For more details: https://gist.github.com/valschneider/78099acee87a18057d56cc6cc03978b1

---
 kernel/sched/fair.c | 82 +++++++++++++++++++++++++----------------------------
 1 file changed, 39 insertions(+), 43 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 3abb3bc..4042025 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -5404,8 +5404,8 @@ decay_load_missed(unsigned long load, unsigned long missed_updates, int idx)
 
 static struct {
 	cpumask_var_t idle_cpus_mask;
+	cpumask_var_t stale_cpus_mask; /* Idle CPUs with blocked load */
 	atomic_t nr_cpus;
-	int has_blocked;		/* Idle CPUS has blocked load */
 	unsigned long next_balance;     /* in jiffy units */
 	unsigned long next_blocked;	/* Next update of blocked load in jiffies */
 } nohz ____cacheline_aligned;
@@ -6968,7 +6968,6 @@ enum fbq_type { regular, remote, all };
 #define LBF_DST_PINNED  0x04
 #define LBF_SOME_PINNED	0x08
 #define LBF_NOHZ_STATS	0x10
-#define LBF_NOHZ_AGAIN	0x20
 
 struct lb_env {
 	struct sched_domain	*sd;
@@ -7827,25 +7826,24 @@ group_type group_classify(struct sched_group *group,
 	return group_other;
 }
 
-static bool update_nohz_stats(struct rq *rq)
+static void update_nohz_stats(struct rq *rq)
 {
 #ifdef CONFIG_NO_HZ_COMMON
 	unsigned int cpu = rq->cpu;
 
-	if (!rq->has_blocked_load)
-		return false;
 
-	if (!cpumask_test_cpu(cpu, nohz.idle_cpus_mask))
-		return false;
+	if (!cpumask_test_cpu(cpu, nohz.stale_cpus_mask))
+		return;
 
 	if (!time_after(jiffies, rq->last_blocked_load_update_tick))
-		return true;
+		return;
 
 	update_blocked_averages(cpu);
 
-	return rq->has_blocked_load;
+	if (!rq->has_blocked_load)
+		cpumask_clear_cpu(cpu, nohz.stale_cpus_mask);
 #else
-	return false;
+	return;
 #endif
 }
 
@@ -7871,8 +7869,8 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 	for_each_cpu_and(i, sched_group_span(group), env->cpus) {
 		struct rq *rq = cpu_rq(i);
 
-		if ((env->flags & LBF_NOHZ_STATS) && update_nohz_stats(rq))
-			env->flags |= LBF_NOHZ_AGAIN;
+		if (env->flags & LBF_NOHZ_STATS)
+			update_nohz_stats(rq);
 
 		/* Bias balancing toward cpus of our domain */
 		if (local_group)
@@ -8024,7 +8022,8 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
 	struct sg_lb_stats *local = &sds->local_stat;
 	struct sg_lb_stats tmp_sgs;
 	int load_idx, prefer_sibling = 0;
-	int has_blocked = READ_ONCE(nohz.has_blocked);
+	int has_blocked = cpumask_intersects(sched_domain_span(env->sd),
+					     nohz.stale_cpus_mask);
 	bool overload = false;
 
 	if (child && child->flags & SD_PREFER_SIBLING)
@@ -8089,8 +8088,13 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
 	} while (sg != env->sd->groups);
 
 #ifdef CONFIG_NO_HZ_COMMON
-	if ((env->flags & LBF_NOHZ_AGAIN) &&
-	    cpumask_subset(nohz.idle_cpus_mask, sched_domain_span(env->sd))) {
+	/*
+	 * All nohz CPUs with blocked load were visited but some haven't fully
+	 * decayed. Visit them again later.
+	 */
+	if ((env->flags & LBF_NOHZ_STATS) &&
+	    cpumask_subset(nohz.idle_cpus_mask, sched_domain_span(env->sd)) &&
+	    !cpumask_empty(nohz.stale_cpus_mask)) {
 
 		WRITE_ONCE(nohz.next_blocked,
 				jiffies + msecs_to_jiffies(LOAD_AVG_PERIOD));
@@ -8882,7 +8886,7 @@ static int idle_balance(struct rq *this_rq, struct rq_flags *rf)
 
 	if (this_rq->avg_idle < sysctl_sched_migration_cost ||
 	    !this_rq->rd->overload) {
-		unsigned long has_blocked = READ_ONCE(nohz.has_blocked);
+		unsigned long has_blocked = !cpumask_empty(nohz.stale_cpus_mask);
 		unsigned long next_blocked = READ_ONCE(nohz.next_blocked);
 
 		rcu_read_lock();
@@ -9137,7 +9141,7 @@ static void nohz_balancer_kick(struct rq *rq)
 	struct sched_domain *sd;
 	int nr_busy, i, cpu = rq->cpu;
 	unsigned int flags = 0;
-	unsigned long has_blocked = READ_ONCE(nohz.has_blocked);
+	unsigned long has_blocked = !cpumask_empty(nohz.stale_cpus_mask);
 	unsigned long next_blocked = READ_ONCE(nohz.next_blocked);
 
 	if (unlikely(rq->idle_balance))
@@ -9297,10 +9301,10 @@ void nohz_balance_enter_idle(int cpu)
 
 out:
 	/*
-	 * Each time a cpu enter idle, we assume that it has blocked load and
-	 * enable the periodic update of the load of idle cpus
+	 * Each time a cpu enters idle, we assume that it has blocked load and
+	 * enable the periodic update of its blocked load
 	 */
-	WRITE_ONCE(nohz.has_blocked, 1);
+	cpumask_set_cpu(cpu, nohz.stale_cpus_mask);
 }
 #else
 static inline void nohz_balancer_kick(struct rq *rq) { }
@@ -9437,7 +9441,6 @@ static bool _nohz_idle_balance(struct rq *this_rq, unsigned int flags, enum cpu_
 	/* Earliest time when we have to do rebalance again */
 	unsigned long now = jiffies;
 	unsigned long next_balance = now + 60*HZ;
-	bool has_blocked_load = false;
 	int update_next_balance = 0;
 	int this_cpu = this_rq->cpu;
 	int balance_cpu;
@@ -9447,16 +9450,6 @@ static bool _nohz_idle_balance(struct rq *this_rq, unsigned int flags, enum cpu_
 
 	SCHED_WARN_ON((flags & NOHZ_KICK_MASK) == NOHZ_BALANCE_KICK);
 
-	/*
-	 * We assume there will be no idle load after this update and clear
-	 * the has_blocked flag. If a cpu enters idle in the mean time, it will
-	 * set the has_blocked flag and trig another update of idle load.
-	 * Because a cpu that becomes idle, is added to idle_cpus_mask before
-	 * setting the flag, we are sure to not clear the state and not
-	 * check the load of an idle cpu.
-	 */
-	WRITE_ONCE(nohz.has_blocked, 0);
-
 	for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
 		u64 t0, domain_cost;
 
@@ -9466,29 +9459,34 @@ static bool _nohz_idle_balance(struct rq *this_rq, unsigned int flags, enum cpu_
 			continue;
 
 		/*
+		 * When using the nohz balance to only update blocked load,
+		 * we can skip nohz CPUs which no longer have blocked load.
+		 */
+		if ((flags & NOHZ_KICK_MASK) == NOHZ_STATS_KICK &&
+		    !cpumask_test_cpu(balance_cpu, nohz.stale_cpus_mask))
+			continue;
+
+		/*
 		 * If this cpu gets work to do, stop the load balancing
 		 * work being done for other cpus. Next load
 		 * balancing owner will pick it up.
 		 */
-		if (need_resched()) {
-			has_blocked_load = true;
+		if (need_resched())
 			goto abort;
-		}
 
 		/*
 		 * If the update is done while CPU becomes idle, we abort
 		 * the update when its cost is higher than the average idle
 		 * time in orde to not delay a possible wake up.
 		 */
-		if (idle == CPU_NEWLY_IDLE && this_rq->avg_idle < curr_cost) {
-			has_blocked_load = true;
+		if (idle == CPU_NEWLY_IDLE && this_rq->avg_idle < curr_cost)
 			goto abort;
-		}
 
 		rq = cpu_rq(balance_cpu);
 
 		update_blocked_averages(rq->cpu);
-		has_blocked_load |= rq->has_blocked_load;
+		if (!rq->has_blocked_load)
+			cpumask_clear_cpu(balance_cpu, nohz.stale_cpus_mask);
 
 		/*
 		 * If time for next balance is due,
@@ -9519,7 +9517,8 @@ static bool _nohz_idle_balance(struct rq *this_rq, unsigned int flags, enum cpu_
 	/* Newly idle CPU doesn't need an update */
 	if (idle != CPU_NEWLY_IDLE) {
 		update_blocked_averages(this_cpu);
-		has_blocked_load |= this_rq->has_blocked_load;
+		if (!this_rq->has_blocked_load)
+			cpumask_clear_cpu(this_cpu, nohz.stale_cpus_mask);
 	}
 
 	if (flags & NOHZ_BALANCE_KICK)
@@ -9532,10 +9531,6 @@ static bool _nohz_idle_balance(struct rq *this_rq, unsigned int flags, enum cpu_
 	ret = true;
 
 abort:
-	/* There is still blocked load, enable periodic update */
-	if (has_blocked_load)
-		WRITE_ONCE(nohz.has_blocked, 1);
-
 	/*
 	 * next_balance will be updated only when there is a need.
 	 * When the CPU is attached to null domain for ex, it will not be
@@ -10196,6 +10191,7 @@ __init void init_sched_fair_class(void)
 	nohz.next_balance = jiffies;
 	nohz.next_blocked = jiffies;
 	zalloc_cpumask_var(&nohz.idle_cpus_mask, GFP_NOWAIT);
+	zalloc_cpumask_var(&nohz.stale_cpus_mask, GFP_NOWAIT);
 #endif
 #endif /* SMP */
 
-- 
2.7.4

Re: [PATCH v2 1/3] sched: Stop nohz stats when decayed

[Vincent Guittot]

On 8 February 2018 at 20:21, Valentin Schneider
<valentin.schneider@arm.com> wrote:
> On 02/08/2018 01:36 PM, Vincent Guittot wrote:
>> On 8 February 2018 at 13:46, Valentin Schneider
>> <valentin.schneider@arm.com> wrote:
>>> On 02/06/2018 07:23 PM, Vincent Guittot wrote:
>>>> [...]

>
> For now I've been using those made-up rt-app workloads to stress specific
> bits of code, but I agree it would be really nice to have a "real" workload
> to see how both power (additional kick_ilb()'s) and performance (additional
> atomic ops) are affected. As Vincent suggested offline, it could be worth
> giving it a shot on Android...
>
>
> In the meantime I've done some more accurate profiling with cpumasks on my
> Juno r2 (patch at the bottom). As a sidenote, I realised I don't have a test
> case for the load update through load_balance() in idle_balance() - I only
> test the !overload segment. Will think about that.
>
> In summary:
>
> 20 iterations per test case
> All non-mentioned CPUs are idling
>
> ---------------------
> kick_ilb() test case:
> ---------------------
>
> a, b = 100% rt-app tasks
> - = idling
>
> Accumulating load before sleeping
>         ^
>         ^
> CPU1| a a a - - - a
> CPU2| - - b b b b b
>               v
>               v > Periodically kicking ILBs to update nohz blocked load
>
> Baseline:
>     _nohz_idle_balance() takes 39µs in average
>     nohz_balance_enter_idle() takes 233ns in average
>
> W/ cpumask:
>     _nohz_idle_balance() takes 33µs in average
>     nohz_balance_enter_idle() takes 283ns in average
>
> Diff:
>     _nohz_idle_balance() -6µs in average (-16%)
>     nohz_balance_enter_idle() +50ns in average (+21%)

In your use case, there is no contention when accessing the cpumask.
Have you tried a use case with tasks that wake ups and go back to idle
simultaneously on several/all cpus so they will fight to update the
atomic resources ?
That would be interesting to see the impact on the runtime of the
nohz_balance_enter_idle function

>
>
> ---------------------------------------------------
> Local _nohz_idle_balance() for NEWLY_IDLE test case:
> ---------------------------------------------------
>
> a = 100% rt-app task
> b = periodic rt-app task
> - = idling
>
> Accumulating load before sleeping
>         ^
>         ^
> CPU1| a a a - - - - - a
> CPU2| - - b - b - b - b
>                v
>                v > Periodically updating nohz blocked load through local
>                    _nohz_idle_balance() in idle_balance()
>
>
> (execution times are x2 as fast as previous test case because CPU2 is a
> big CPU, whereas CPU0 - the ILB 99% of the time in the previous test - is a
> LITTLE CPU ~ half as powerful).
>
> Baseline:
>     _nohz_idle_balance() takes 20µs in average
>     nohz_balance_enter_idle() takes 183ns in average
>
> W/ cpumask:
>     _nohz_idle_balance() takes 13µs in average
>     nohz_balance_enter_idle() takes 217ns in average
>
> Diff:
>     _nohz_idle_balance() -7µs in average (-38%)
>     nohz_balance_enter_idle() +34ns in average (+18%)
>
>
>
> For more details: https://gist.github.com/valschneider/78099acee87a18057d56cc6cc03978b1
>
> ---
>  kernel/sched/fair.c | 82 +++++++++++++++++++++++++----------------------------
>  1 file changed, 39 insertions(+), 43 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 3abb3bc..4042025 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -5404,8 +5404,8 @@ decay_load_missed(unsigned long load, unsigned long missed_updates, int idx)
>
>  static struct {
>         cpumask_var_t idle_cpus_mask;
> +       cpumask_var_t stale_cpus_mask; /* Idle CPUs with blocked load */
>         atomic_t nr_cpus;
> -       int has_blocked;                /* Idle CPUS has blocked load */
>         unsigned long next_balance;     /* in jiffy units */
>         unsigned long next_blocked;     /* Next update of blocked load in jiffies */
>  } nohz ____cacheline_aligned;
> @@ -6968,7 +6968,6 @@ enum fbq_type { regular, remote, all };
>  #define LBF_DST_PINNED  0x04
>  #define LBF_SOME_PINNED        0x08
>  #define LBF_NOHZ_STATS 0x10
> -#define LBF_NOHZ_AGAIN 0x20
>
>  struct lb_env {
>         struct sched_domain     *sd;
> @@ -7827,25 +7826,24 @@ group_type group_classify(struct sched_group *group,
>         return group_other;
>  }
>
> -static bool update_nohz_stats(struct rq *rq)
> +static void update_nohz_stats(struct rq *rq)
>  {
>  #ifdef CONFIG_NO_HZ_COMMON
>         unsigned int cpu = rq->cpu;
>
> -       if (!rq->has_blocked_load)
> -               return false;
>
> -       if (!cpumask_test_cpu(cpu, nohz.idle_cpus_mask))
> -               return false;
> +       if (!cpumask_test_cpu(cpu, nohz.stale_cpus_mask))
> +               return;
>
>         if (!time_after(jiffies, rq->last_blocked_load_update_tick))
> -               return true;
> +               return;
>
>         update_blocked_averages(cpu);
>
> -       return rq->has_blocked_load;
> +       if (!rq->has_blocked_load)
> +               cpumask_clear_cpu(cpu, nohz.stale_cpus_mask);
>  #else
> -       return false;
> +       return;
>  #endif
>  }
>
> @@ -7871,8 +7869,8 @@ static inline void update_sg_lb_stats(struct lb_env *env,
>         for_each_cpu_and(i, sched_group_span(group), env->cpus) {
>                 struct rq *rq = cpu_rq(i);
>
> -               if ((env->flags & LBF_NOHZ_STATS) && update_nohz_stats(rq))
> -                       env->flags |= LBF_NOHZ_AGAIN;
> +               if (env->flags & LBF_NOHZ_STATS)
> +                       update_nohz_stats(rq);
>
>                 /* Bias balancing toward cpus of our domain */
>                 if (local_group)
> @@ -8024,7 +8022,8 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
>         struct sg_lb_stats *local = &sds->local_stat;
>         struct sg_lb_stats tmp_sgs;
>         int load_idx, prefer_sibling = 0;
> -       int has_blocked = READ_ONCE(nohz.has_blocked);
> +       int has_blocked = cpumask_intersects(sched_domain_span(env->sd),
> +                                            nohz.stale_cpus_mask);
>         bool overload = false;
>
>         if (child && child->flags & SD_PREFER_SIBLING)
> @@ -8089,8 +8088,13 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
>         } while (sg != env->sd->groups);
>
>  #ifdef CONFIG_NO_HZ_COMMON
> -       if ((env->flags & LBF_NOHZ_AGAIN) &&
> -           cpumask_subset(nohz.idle_cpus_mask, sched_domain_span(env->sd))) {
> +       /*
> +        * All nohz CPUs with blocked load were visited but some haven't fully
> +        * decayed. Visit them again later.
> +        */
> +       if ((env->flags & LBF_NOHZ_STATS) &&
> +           cpumask_subset(nohz.idle_cpus_mask, sched_domain_span(env->sd)) &&
> +           !cpumask_empty(nohz.stale_cpus_mask)) {
>
>                 WRITE_ONCE(nohz.next_blocked,
>                                 jiffies + msecs_to_jiffies(LOAD_AVG_PERIOD));
> @@ -8882,7 +8886,7 @@ static int idle_balance(struct rq *this_rq, struct rq_flags *rf)
>
>         if (this_rq->avg_idle < sysctl_sched_migration_cost ||
>             !this_rq->rd->overload) {
> -               unsigned long has_blocked = READ_ONCE(nohz.has_blocked);
> +               unsigned long has_blocked = !cpumask_empty(nohz.stale_cpus_mask);
>                 unsigned long next_blocked = READ_ONCE(nohz.next_blocked);
>
>                 rcu_read_lock();
> @@ -9137,7 +9141,7 @@ static void nohz_balancer_kick(struct rq *rq)
>         struct sched_domain *sd;
>         int nr_busy, i, cpu = rq->cpu;
>         unsigned int flags = 0;
> -       unsigned long has_blocked = READ_ONCE(nohz.has_blocked);
> +       unsigned long has_blocked = !cpumask_empty(nohz.stale_cpus_mask);
>         unsigned long next_blocked = READ_ONCE(nohz.next_blocked);
>
>         if (unlikely(rq->idle_balance))
> @@ -9297,10 +9301,10 @@ void nohz_balance_enter_idle(int cpu)
>
>  out:
>         /*
> -        * Each time a cpu enter idle, we assume that it has blocked load and
> -        * enable the periodic update of the load of idle cpus
> +        * Each time a cpu enters idle, we assume that it has blocked load and
> +        * enable the periodic update of its blocked load
>          */
> -       WRITE_ONCE(nohz.has_blocked, 1);
> +       cpumask_set_cpu(cpu, nohz.stale_cpus_mask);
>  }
>  #else
>  static inline void nohz_balancer_kick(struct rq *rq) { }
> @@ -9437,7 +9441,6 @@ static bool _nohz_idle_balance(struct rq *this_rq, unsigned int flags, enum cpu_
>         /* Earliest time when we have to do rebalance again */
>         unsigned long now = jiffies;
>         unsigned long next_balance = now + 60*HZ;
> -       bool has_blocked_load = false;
>         int update_next_balance = 0;
>         int this_cpu = this_rq->cpu;
>         int balance_cpu;
> @@ -9447,16 +9450,6 @@ static bool _nohz_idle_balance(struct rq *this_rq, unsigned int flags, enum cpu_
>
>         SCHED_WARN_ON((flags & NOHZ_KICK_MASK) == NOHZ_BALANCE_KICK);
>
> -       /*
> -        * We assume there will be no idle load after this update and clear
> -        * the has_blocked flag. If a cpu enters idle in the mean time, it will
> -        * set the has_blocked flag and trig another update of idle load.
> -        * Because a cpu that becomes idle, is added to idle_cpus_mask before
> -        * setting the flag, we are sure to not clear the state and not
> -        * check the load of an idle cpu.
> -        */
> -       WRITE_ONCE(nohz.has_blocked, 0);
> -
>         for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
>                 u64 t0, domain_cost;
>
> @@ -9466,29 +9459,34 @@ static bool _nohz_idle_balance(struct rq *this_rq, unsigned int flags, enum cpu_
>                         continue;
>
>                 /*
> +                * When using the nohz balance to only update blocked load,
> +                * we can skip nohz CPUs which no longer have blocked load.
> +                */
> +               if ((flags & NOHZ_KICK_MASK) == NOHZ_STATS_KICK &&
> +                   !cpumask_test_cpu(balance_cpu, nohz.stale_cpus_mask))
> +                       continue;
> +
> +               /*
>                  * If this cpu gets work to do, stop the load balancing
>                  * work being done for other cpus. Next load
>                  * balancing owner will pick it up.
>                  */
> -               if (need_resched()) {
> -                       has_blocked_load = true;
> +               if (need_resched())
>                         goto abort;
> -               }
>
>                 /*
>                  * If the update is done while CPU becomes idle, we abort
>                  * the update when its cost is higher than the average idle
>                  * time in orde to not delay a possible wake up.
>                  */
> -               if (idle == CPU_NEWLY_IDLE && this_rq->avg_idle < curr_cost) {
> -                       has_blocked_load = true;
> +               if (idle == CPU_NEWLY_IDLE && this_rq->avg_idle < curr_cost)
>                         goto abort;
> -               }
>
>                 rq = cpu_rq(balance_cpu);
>
>                 update_blocked_averages(rq->cpu);
> -               has_blocked_load |= rq->has_blocked_load;
> +               if (!rq->has_blocked_load)
> +                       cpumask_clear_cpu(balance_cpu, nohz.stale_cpus_mask);
>
>                 /*
>                  * If time for next balance is due,
> @@ -9519,7 +9517,8 @@ static bool _nohz_idle_balance(struct rq *this_rq, unsigned int flags, enum cpu_
>         /* Newly idle CPU doesn't need an update */
>         if (idle != CPU_NEWLY_IDLE) {
>                 update_blocked_averages(this_cpu);
> -               has_blocked_load |= this_rq->has_blocked_load;
> +               if (!this_rq->has_blocked_load)
> +                       cpumask_clear_cpu(this_cpu, nohz.stale_cpus_mask);
>         }
>
>         if (flags & NOHZ_BALANCE_KICK)
> @@ -9532,10 +9531,6 @@ static bool _nohz_idle_balance(struct rq *this_rq, unsigned int flags, enum cpu_
>         ret = true;
>
>  abort:
> -       /* There is still blocked load, enable periodic update */
> -       if (has_blocked_load)
> -               WRITE_ONCE(nohz.has_blocked, 1);
> -
>         /*
>          * next_balance will be updated only when there is a need.
>          * When the CPU is attached to null domain for ex, it will not be
> @@ -10196,6 +10191,7 @@ __init void init_sched_fair_class(void)
>         nohz.next_balance = jiffies;
>         nohz.next_blocked = jiffies;
>         zalloc_cpumask_var(&nohz.idle_cpus_mask, GFP_NOWAIT);
> +       zalloc_cpumask_var(&nohz.stale_cpus_mask, GFP_NOWAIT);
>  #endif
>  #endif /* SMP */
>
> --
> 2.7.4
>
>

Re: [PATCH v2 1/3] sched: Stop nohz stats when decayed

[Valentin Schneider]

On 02/09/2018 11:41 AM, Vincent Guittot wrote:
> On 8 February 2018 at 20:21, Valentin Schneider
> <valentin.schneider@arm.com> wrote:
>> On 02/08/2018 01:36 PM, Vincent Guittot wrote:
>>> On 8 February 2018 at 13:46, Valentin Schneider
>>> <valentin.schneider@arm.com> wrote:
>>>> On 02/06/2018 07:23 PM, Vincent Guittot wrote:
>>>>> [...]
> 
>>
>> In summary:
>>
>> 20 iterations per test case
>> All non-mentioned CPUs are idling
>>
>> ---------------------
>> kick_ilb() test case:
>> ---------------------
>>
>> a, b = 100% rt-app tasks
>> - = idling
>>
>> Accumulating load before sleeping
>>         ^
>>         ^
>> CPU1| a a a - - - a
>> CPU2| - - b b b b b
>>               v
>>               v > Periodically kicking ILBs to update nohz blocked load
>>
>> Baseline:
>>     _nohz_idle_balance() takes 39µs in average
>>     nohz_balance_enter_idle() takes 233ns in average
>>
>> W/ cpumask:
>>     _nohz_idle_balance() takes 33µs in average
>>     nohz_balance_enter_idle() takes 283ns in average
>>
>> Diff:
>>     _nohz_idle_balance() -6µs in average (-16%)
>>     nohz_balance_enter_idle() +50ns in average (+21%)
> 
> In your use case, there is no contention when accessing the cpumask.
> Have you tried a use case with tasks that wake ups and go back to idle
> simultaneously on several/all cpus so they will fight to update the
> atomic resources ?
> That would be interesting to see the impact on the runtime of the
> nohz_balance_enter_idle function

No, I haven't tried that yet. For now these tests picture the "best case" 
scenario since all but one CPU is idle. I've been meaning to test busier
scenarios - I'll give your idle/sleep storm a try, thanks for the suggestion.

I also need to work on a test case for the load_balance() call in
idle_balance(). As Peter mentioned, the clearing of has_blocked in 
update_sd_lb_stats() can only be done with atomic ops, so that's another 
thing to profile against the baseline.

Re: [PATCH v2 1/3] sched: Stop nohz stats when decayed

[Peter Zijlstra]

On Tue, Feb 06, 2018 at 08:23:05PM +0100, Vincent Guittot wrote:

> @@ -9207,13 +9231,15 @@ void nohz_balance_enter_idle(int cpu)
>  	if (!housekeeping_cpu(cpu, HK_FLAG_SCHED))
>  		return;
>  
> +	rq->has_blocked_load = 1;
> +
>  	if (rq->nohz_tick_stopped)
> -		return;

this case is difficult... needs thinking

> +		goto out;
>  
>  	/*
>  	 * If we're a completely isolated CPU, we don't play.
>  	 */
> -	if (on_null_domain(cpu_rq(cpu)))
> +	if (on_null_domain(rq))
>  		return;
>  
>  	rq->nohz_tick_stopped = 1;
> @@ -9222,6 +9248,13 @@ void nohz_balance_enter_idle(int cpu)
>  	atomic_inc(&nohz.nr_cpus);
>  
>  	set_cpu_sd_state_idle(cpu);

	/*
	 * Ensures that if nohz_idle_balance() fails to observe our
	 * @idle_cpus_mask store, it must observe the @has_blocked
	 * store.
	 */
	smp_mb__after_atomic();

> +
> +out:
> +	/*
> +	 * Each time a cpu enter idle, we assume that it has blocked load and
> +	 * enable the periodic update of the load of idle cpus
> +	 */
> +	WRITE_ONCE(nohz.has_blocked, 1);
>  }



> @@ -9374,6 +9407,16 @@ static bool nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
>  
>  	SCHED_WARN_ON((flags & NOHZ_KICK_MASK) == NOHZ_BALANCE_KICK);
>  
> +	/*
> +	 * We assume there will be no idle load after this update and clear
> +	 * the has_blocked flag. If a cpu enters idle in the mean time, it will
> +	 * set the has_blocked flag and trig another update of idle load.
> +	 * Because a cpu that becomes idle, is added to idle_cpus_mask before
> +	 * setting the flag, we are sure to not clear the state and not
> +	 * check the load of an idle cpu.
> +	 */
> +	WRITE_ONCE(nohz.has_blocked, 0);

	/*
	 * Ensures that if we miss the CPU, we must see the has_blocked
	 * store from nohz_balance_enter_idle().
	 */
	smp_mb();

>  	for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
>  		if (balance_cpu == this_cpu || !idle_cpu(balance_cpu))
>  			continue;


I _think_, but my brain isn't quite willing to turn on today.

Without this ordering I think it would be possible to loose has_blocked
and not observe the CPU either.

Re: [PATCH v2 1/3] sched: Stop nohz stats when decayed

[Peter Zijlstra]

On Thu, Feb 08, 2018 at 03:00:05PM +0100, Peter Zijlstra wrote:
> On Tue, Feb 06, 2018 at 08:23:05PM +0100, Vincent Guittot wrote:
> 
> > @@ -9207,13 +9231,15 @@ void nohz_balance_enter_idle(int cpu)
> >  	if (!housekeeping_cpu(cpu, HK_FLAG_SCHED))
> >  		return;
> >  
> > +	rq->has_blocked_load = 1;
> > +
> >  	if (rq->nohz_tick_stopped)
> > -		return;
> 
> this case is difficult... needs thinking
> 
> > +		goto out;
> >  
> >  	/*
> >  	 * If we're a completely isolated CPU, we don't play.
> >  	 */
> > -	if (on_null_domain(cpu_rq(cpu)))
> > +	if (on_null_domain(rq))
> >  		return;
> >  
> >  	rq->nohz_tick_stopped = 1;
> > @@ -9222,6 +9248,13 @@ void nohz_balance_enter_idle(int cpu)
> >  	atomic_inc(&nohz.nr_cpus);
> >  
> >  	set_cpu_sd_state_idle(cpu);
> 
> 	/*
> 	 * Ensures that if nohz_idle_balance() fails to observe our
> 	 * @idle_cpus_mask store, it must observe the @has_blocked
> 	 * store.
> 	 */
> 	smp_mb__after_atomic();
> 
> > +
> > +out:
> > +	/*
> > +	 * Each time a cpu enter idle, we assume that it has blocked load and
> > +	 * enable the periodic update of the load of idle cpus
> > +	 */
> > +	WRITE_ONCE(nohz.has_blocked, 1);
> >  }
> 
> 
> 
> > @@ -9374,6 +9407,16 @@ static bool nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
> >  
> >  	SCHED_WARN_ON((flags & NOHZ_KICK_MASK) == NOHZ_BALANCE_KICK);
> >  
> > +	/*
> > +	 * We assume there will be no idle load after this update and clear
> > +	 * the has_blocked flag. If a cpu enters idle in the mean time, it will
> > +	 * set the has_blocked flag and trig another update of idle load.
> > +	 * Because a cpu that becomes idle, is added to idle_cpus_mask before
> > +	 * setting the flag, we are sure to not clear the state and not
> > +	 * check the load of an idle cpu.
> > +	 */
> > +	WRITE_ONCE(nohz.has_blocked, 0);
> 
> 	/*
> 	 * Ensures that if we miss the CPU, we must see the has_blocked
> 	 * store from nohz_balance_enter_idle().
> 	 */
> 	smp_mb();
> 
> >  	for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
> >  		if (balance_cpu == this_cpu || !idle_cpu(balance_cpu))
> >  			continue;
> 
> 
> I _think_, but my brain isn't quite willing to turn on today.
> 
> Without this ordering I think it would be possible to loose has_blocked
> and not observe the CPU either.
> 
> 

might be the exact case from litmus-tests/R+mbonceonces.litmus but I
can't seem to get herd7 working today.

Re: [PATCH v2 1/3] sched: Stop nohz stats when decayed

[Vincent Guittot]

On 8 February 2018 at 15:00, Peter Zijlstra <peterz@infradead.org> wrote:
> On Tue, Feb 06, 2018 at 08:23:05PM +0100, Vincent Guittot wrote:
>
>> @@ -9207,13 +9231,15 @@ void nohz_balance_enter_idle(int cpu)
>>       if (!housekeeping_cpu(cpu, HK_FLAG_SCHED))
>>               return;
>>
>> +     rq->has_blocked_load = 1;
>> +
>>       if (rq->nohz_tick_stopped)
>> -             return;
>
> this case is difficult... needs thinking

The use case happens when a CPU wakes up and goes back to idle before
the tick fires and clears nohz_tick_stopped.

>
>> +             goto out;
>>
>>       /*
>>        * If we're a completely isolated CPU, we don't play.
>>        */
>> -     if (on_null_domain(cpu_rq(cpu)))
>> +     if (on_null_domain(rq))
>>               return;
>>
>>       rq->nohz_tick_stopped = 1;
>> @@ -9222,6 +9248,13 @@ void nohz_balance_enter_idle(int cpu)
>>       atomic_inc(&nohz.nr_cpus);
>>
>>       set_cpu_sd_state_idle(cpu);
>
>         /*
>          * Ensures that if nohz_idle_balance() fails to observe our
>          * @idle_cpus_mask store, it must observe the @has_blocked
>          * store.
>          */
>         smp_mb__after_atomic();
>
>> +
>> +out:
>> +     /*
>> +      * Each time a cpu enter idle, we assume that it has blocked load and
>> +      * enable the periodic update of the load of idle cpus
>> +      */
>> +     WRITE_ONCE(nohz.has_blocked, 1);
>>  }
>
>
>
>> @@ -9374,6 +9407,16 @@ static bool nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
>>
>>       SCHED_WARN_ON((flags & NOHZ_KICK_MASK) == NOHZ_BALANCE_KICK);
>>
>> +     /*
>> +      * We assume there will be no idle load after this update and clear
>> +      * the has_blocked flag. If a cpu enters idle in the mean time, it will
>> +      * set the has_blocked flag and trig another update of idle load.
>> +      * Because a cpu that becomes idle, is added to idle_cpus_mask before
>> +      * setting the flag, we are sure to not clear the state and not
>> +      * check the load of an idle cpu.
>> +      */
>> +     WRITE_ONCE(nohz.has_blocked, 0);
>
>         /*
>          * Ensures that if we miss the CPU, we must see the has_blocked
>          * store from nohz_balance_enter_idle().
>          */
>         smp_mb();
>
>>       for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
>>               if (balance_cpu == this_cpu || !idle_cpu(balance_cpu))
>>                       continue;
>
>
> I _think_, but my brain isn't quite willing to turn on today.
>
> Without this ordering I think it would be possible to loose has_blocked
> and not observe the CPU either.

I think that you are right.
I also wondered if some barriers were necessary but wrongly concluded
that set operation on nohz.idle_cpus_mask and WRITE_ONCE with volatile
would be enough to ensure the right ordering

>
>

Re: [PATCH v2 1/3] sched: Stop nohz stats when decayed

[Peter Zijlstra]

On Thu, Feb 08, 2018 at 04:05:58PM +0100, Vincent Guittot wrote:
> On 8 February 2018 at 15:00, Peter Zijlstra <peterz@infradead.org> wrote:
> > On Tue, Feb 06, 2018 at 08:23:05PM +0100, Vincent Guittot wrote:
> >
> >> @@ -9207,13 +9231,15 @@ void nohz_balance_enter_idle(int cpu)
> >>       if (!housekeeping_cpu(cpu, HK_FLAG_SCHED))
> >>               return;
> >>
> >> +     rq->has_blocked_load = 1;

Should we not set that with rq->lock held? We already clear it while
holding rq->lock.

> >> +
> >>       if (rq->nohz_tick_stopped)
> >> -             return;
> >
> > this case is difficult... needs thinking
> 
> The use case happens when a CPU wakes up and goes back to idle before
> the tick fires and clears nohz_tick_stopped.

Yes, and so we could have accrued blocked load. Now in this case the CPU
must already be set in the cpumask, but we could've already cleared
has_blocked.

My question is mostly about needing that "goto out" to set the flag,
because I think we can loose it on a store collision vs clearing it. But
in that case I suppose the iteration must already be in progress, which
in turn will observe rq->has_blocked_load and re-set nohz.has_blocked.

So yes, this is good, but could use a comment.

> > Without this ordering I think it would be possible to loose has_blocked
> > and not observe the CPU either.
> 
> I think that you are right.
> I also wondered if some barriers were necessary but wrongly concluded
> that set operation on nohz.idle_cpus_mask and WRITE_ONCE with volatile
> would be enough to ensure the right ordering

Yeah, so I forgot to write the comment in my patch, but it had the
barriers implied by cmpxchg.

Re: [PATCH v2 1/3] sched: Stop nohz stats when decayed

[Vincent Guittot]

On 8 February 2018 at 16:44, Peter Zijlstra <peterz@infradead.org> wrote:
> On Thu, Feb 08, 2018 at 04:05:58PM +0100, Vincent Guittot wrote:
>> On 8 February 2018 at 15:00, Peter Zijlstra <peterz@infradead.org> wrote:
>> > On Tue, Feb 06, 2018 at 08:23:05PM +0100, Vincent Guittot wrote:
>> >
>> >> @@ -9207,13 +9231,15 @@ void nohz_balance_enter_idle(int cpu)
>> >>       if (!housekeeping_cpu(cpu, HK_FLAG_SCHED))
>> >>               return;
>> >>
>> >> +     rq->has_blocked_load = 1;
>
> Should we not set that with rq->lock held? We already clear it while
> holding rq->lock.

I think it's safe because it is used to re-enable the periodic decay
unconditionally.
It is cleared with  rq->lock held to prevents any update of the cfs_rq
*_avg  while deciding if we can clear has_blocked_load

>
>> >> +
>> >>       if (rq->nohz_tick_stopped)
>> >> -             return;
>> >
>> > this case is difficult... needs thinking
>>
>> The use case happens when a CPU wakes up and goes back to idle before
>> the tick fires and clears nohz_tick_stopped.
>
> Yes, and so we could have accrued blocked load. Now in this case the CPU
> must already be set in the cpumask, but we could've already cleared
> has_blocked.
>
> My question is mostly about needing that "goto out" to set the flag,
> because I think we can loose it on a store collision vs clearing it. But
> in that case I suppose the iteration must already be in progress, which
> in turn will observe rq->has_blocked_load and re-set nohz.has_blocked.
>
> So yes, this is good, but could use a comment.
>
>> > Without this ordering I think it would be possible to loose has_blocked
>> > and not observe the CPU either.
>>
>> I think that you are right.
>> I also wondered if some barriers were necessary but wrongly concluded
>> that set operation on nohz.idle_cpus_mask and WRITE_ONCE with volatile
>> would be enough to ensure the right ordering
>
> Yeah, so I forgot to write the comment in my patch, but it had the
> barriers implied by cmpxchg.

Re: [PATCH v2 1/3] sched: Stop nohz stats when decayed

[Peter Zijlstra]

On Thu, Feb 08, 2018 at 05:52:00PM +0100, Vincent Guittot wrote:
> On 8 February 2018 at 16:44, Peter Zijlstra <peterz@infradead.org> wrote:
> > On Thu, Feb 08, 2018 at 04:05:58PM +0100, Vincent Guittot wrote:
> >> On 8 February 2018 at 15:00, Peter Zijlstra <peterz@infradead.org> wrote:
> >> > On Tue, Feb 06, 2018 at 08:23:05PM +0100, Vincent Guittot wrote:
> >> >
> >> >> @@ -9207,13 +9231,15 @@ void nohz_balance_enter_idle(int cpu)
> >> >>       if (!housekeeping_cpu(cpu, HK_FLAG_SCHED))
> >> >>               return;
> >> >>
> >> >> +     rq->has_blocked_load = 1;
> >
> > Should we not set that with rq->lock held? We already clear it while
> > holding rq->lock.
> 
> I think it's safe because it is used to re-enable the periodic decay
> unconditionally.
> It is cleared with  rq->lock held to prevents any update of the cfs_rq
> *_avg  while deciding if we can clear has_blocked_load

Yes, and that clearing must then have observed the new addition. But
please put so in a comment.

Re: [PATCH v2 1/3] sched: Stop nohz stats when decayed

[Will Deacon]

On Thu, Feb 08, 2018 at 03:00:05PM +0100, Peter Zijlstra wrote:
> On Tue, Feb 06, 2018 at 08:23:05PM +0100, Vincent Guittot wrote:
> > @@ -9222,6 +9248,13 @@ void nohz_balance_enter_idle(int cpu)
> >  	atomic_inc(&nohz.nr_cpus);
> >  
> >  	set_cpu_sd_state_idle(cpu);
> 
> 	/*
> 	 * Ensures that if nohz_idle_balance() fails to observe our
> 	 * @idle_cpus_mask store, it must observe the @has_blocked
> 	 * store.
> 	 */
> 	smp_mb__after_atomic();
> 
> > +
> > +out:
> > +	/*
> > +	 * Each time a cpu enter idle, we assume that it has blocked load and
> > +	 * enable the periodic update of the load of idle cpus
> > +	 */
> > +	WRITE_ONCE(nohz.has_blocked, 1);
> >  }
> 
> 
> 
> > @@ -9374,6 +9407,16 @@ static bool nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
> >  
> >  	SCHED_WARN_ON((flags & NOHZ_KICK_MASK) == NOHZ_BALANCE_KICK);
> >  
> > +	/*
> > +	 * We assume there will be no idle load after this update and clear
> > +	 * the has_blocked flag. If a cpu enters idle in the mean time, it will
> > +	 * set the has_blocked flag and trig another update of idle load.
> > +	 * Because a cpu that becomes idle, is added to idle_cpus_mask before
> > +	 * setting the flag, we are sure to not clear the state and not
> > +	 * check the load of an idle cpu.
> > +	 */
> > +	WRITE_ONCE(nohz.has_blocked, 0);
> 
> 	/*
> 	 * Ensures that if we miss the CPU, we must see the has_blocked
> 	 * store from nohz_balance_enter_idle().
> 	 */
> 	smp_mb();
> 
> >  	for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
> >  		if (balance_cpu == this_cpu || !idle_cpu(balance_cpu))
> >  			continue;
> 
> 
> I _think_, but my brain isn't quite willing to turn on today.
> 
> Without this ordering I think it would be possible to loose has_blocked
> and not observe the CPU either.

I had a quick look at this, and I think you're right. This looks very much
like an 'R'-shaped test, which means it's smp_mb() all round otherwise Power
will go wrong. That also means the smp_mb__after_atomic() in
nohz_balance_enter_idle *cannot* be an smp_wmb(), so you might want a
comment stating that explicitly.

On arm64, release/acquire would work, but that's basically not the case for
anybody else including x86, so let's not go there.

Will

Re: [PATCH v2 1/3] sched: Stop nohz stats when decayed

[Peter Zijlstra]

On Thu, Feb 08, 2018 at 03:30:31PM +0000, Will Deacon wrote:
> On Thu, Feb 08, 2018 at 03:00:05PM +0100, Peter Zijlstra wrote:

> > Without this ordering I think it would be possible to loose has_blocked
> > and not observe the CPU either.
> 
> I had a quick look at this, and I think you're right. This looks very much
> like an 'R'-shaped test, which means it's smp_mb() all round otherwise Power
> will go wrong. That also means the smp_mb__after_atomic() in
> nohz_balance_enter_idle *cannot* be an smp_wmb(), so you might want a
> comment stating that explicitly.

Thanks Will. BTW, where does that 'R' shape nomenclature come from?
This is the first I've heard of it.

Re: [PATCH v2 1/3] sched: Stop nohz stats when decayed

[Will Deacon]

On Thu, Feb 08, 2018 at 04:46:43PM +0100, Peter Zijlstra wrote:
> On Thu, Feb 08, 2018 at 03:30:31PM +0000, Will Deacon wrote:
> > On Thu, Feb 08, 2018 at 03:00:05PM +0100, Peter Zijlstra wrote:
> 
> > > Without this ordering I think it would be possible to loose has_blocked
> > > and not observe the CPU either.
> > 
> > I had a quick look at this, and I think you're right. This looks very much
> > like an 'R'-shaped test, which means it's smp_mb() all round otherwise Power
> > will go wrong. That also means the smp_mb__after_atomic() in
> > nohz_balance_enter_idle *cannot* be an smp_wmb(), so you might want a
> > comment stating that explicitly.
> 
> Thanks Will. BTW, where does that 'R' shape nomenclature come from?
> This is the first I've heard of it.

I don't know where it originates from, but the imfamous "test6.pdf" has it:

https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf

half way down the first page on the left. It says "needs sync+sync" which
is about as bad as it gets for Power (compare with "2+2w", which gets away
with lwsync+lwsync). See also:

http://materials.dagstuhl.de/files/16/16471/16471.DerekWilliams.Slides.pdf

for a light-hearted, yet technically accurate story about the latter.

Will

Re: [PATCH v2 1/3] sched: Stop nohz stats when decayed

[Andrea Parri]

On Thu, Feb 08, 2018 at 04:03:41PM +0000, Will Deacon wrote:
> On Thu, Feb 08, 2018 at 04:46:43PM +0100, Peter Zijlstra wrote:
> > On Thu, Feb 08, 2018 at 03:30:31PM +0000, Will Deacon wrote:
> > > On Thu, Feb 08, 2018 at 03:00:05PM +0100, Peter Zijlstra wrote:
> > 
> > > > Without this ordering I think it would be possible to loose has_blocked
> > > > and not observe the CPU either.
> > > 
> > > I had a quick look at this, and I think you're right. This looks very much
> > > like an 'R'-shaped test, which means it's smp_mb() all round otherwise Power
> > > will go wrong. That also means the smp_mb__after_atomic() in
> > > nohz_balance_enter_idle *cannot* be an smp_wmb(), so you might want a
> > > comment stating that explicitly.
> > 
> > Thanks Will. BTW, where does that 'R' shape nomenclature come from?
> > This is the first I've heard of it.
> 
> I don't know where it originates from, but the imfamous "test6.pdf" has it:
> 
> https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf
> 
> half way down the first page on the left. It says "needs sync+sync" which

Indeed.  As a curiosity: I've never _observed_ R+lwsync+sync (the lwsync
separating the two writes), and other people who tried found the same

  http://moscova.inria.fr/~maranget/cats7/linux/hard.html#unseen
  http://www.cl.cam.ac.uk/~pes20/ppc-supplemental/ppc051.html#toc8 .

It would be interesting to hear about different results ... ;-)

  Andrea


> is about as bad as it gets for Power (compare with "2+2w", which gets away
> with lwsync+lwsync). See also:
> 
> http://materials.dagstuhl.de/files/16/16471/16471.DerekWilliams.Slides.pdf
> 
> for a light-hearted, yet technically accurate story about the latter.
> 
> Will

[PATCH v2 2/3] sched: reduce the periodic update duration

[Vincent Guittot]

Instead of using the cfs_rq_is_decayed() which monitors all *_avg
and *_sum, we create a cfs_rq_has_blocked() which only takes care of
util_avg and load_avg. We are only interested by these 2 values which are
decaying faster than the *_sum so we can stop the periodic update earlier.

Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
---
 kernel/sched/fair.c | 21 +++++++++++++++++----
 1 file changed, 17 insertions(+), 4 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index b9660b5..e203297 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -7337,6 +7337,19 @@ static void attach_tasks(struct lb_env *env)
 	rq_unlock(env->dst_rq, &rf);
 }
 
+static inline bool cfs_rq_has_blocked(struct cfs_rq *cfs_rq)
+{
+	if (cfs_rq->avg.load_avg)
+		return true;
+
+	if (cfs_rq->avg.util_avg)
+		return true;
+
+	return false;
+}
+
+#ifdef CONFIG_FAIR_GROUP_SCHED
+
 static inline bool cfs_rq_is_decayed(struct cfs_rq *cfs_rq)
 {
 	if (cfs_rq->load.weight)
@@ -7354,8 +7367,6 @@ static inline bool cfs_rq_is_decayed(struct cfs_rq *cfs_rq)
 	return true;
 }
 
-#ifdef CONFIG_FAIR_GROUP_SCHED
-
 static void update_blocked_averages(int cpu)
 {
 	struct rq *rq = cpu_rq(cpu);
@@ -7391,7 +7402,9 @@ static void update_blocked_averages(int cpu)
 		 */
 		if (cfs_rq_is_decayed(cfs_rq))
 			list_del_leaf_cfs_rq(cfs_rq);
-		else
+
+		/* Don't need periodic decay once load/util_avg are null */
+		if (cfs_rq_has_blocked(cfs_rq))
 			done = false;
 	}
 
@@ -7461,7 +7474,7 @@ static inline void update_blocked_averages(int cpu)
 	update_cfs_rq_load_avg(cfs_rq_clock_task(cfs_rq), cfs_rq);
 #ifdef CONFIG_NO_HZ_COMMON
 	rq->last_blocked_load_update_tick = jiffies;
-	if (cfs_rq_is_decayed(cfs_rq))
+	if (!cfs_rq_has_blocked(cfs_rq))
 		rq->has_blocked_load = 0;
 #endif
 	rq_unlock_irqrestore(rq, &rf);
-- 
2.7.4

[PATCH v2 3/3] sched: update blocked load when newly idle

[Vincent Guittot]

When NEWLY_IDLE load balance is not triggered, we might need to update the
blocked load anyway. We can kick an ilb so an idle CPU will take care of
updating blocked load or we can try to update them locally before entering
idle. In the latter case, we reuse part of the nohz_idle_balance.

Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
---
 kernel/sched/fair.c | 102 ++++++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 84 insertions(+), 18 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index e203297..dcac728 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -8829,6 +8829,9 @@ update_next_balance(struct sched_domain *sd, unsigned long *next_balance)
 		*next_balance = next;
 }
 
+static bool _nohz_idle_balance(struct rq *this_rq, unsigned int flags, enum cpu_idle_type idle);
+static void kick_ilb(unsigned int flags);
+
 /*
  * idle_balance is called by schedule() if this_cpu is about to become
  * idle. Attempts to pull tasks from other CPUs.
@@ -8863,12 +8866,26 @@ static int idle_balance(struct rq *this_rq, struct rq_flags *rf)
 
 	if (this_rq->avg_idle < sysctl_sched_migration_cost ||
 	    !this_rq->rd->overload) {
+		unsigned long has_blocked = READ_ONCE(nohz.has_blocked);
+		unsigned long next_blocked = READ_ONCE(nohz.next_blocked);
+
 		rcu_read_lock();
 		sd = rcu_dereference_check_sched_domain(this_rq->sd);
 		if (sd)
 			update_next_balance(sd, &next_balance);
 		rcu_read_unlock();
 
+		/*
+		 * Update blocked idle load if it has not been done for a
+		 * while. Try to do it locally before entering idle but kick a
+		 * ilb if it takes too much time and/or might delay next local
+		 * wake up
+		 */
+		if (has_blocked && time_after_eq(jiffies, next_blocked) &&
+				(this_rq->avg_idle < sysctl_sched_migration_cost ||
+				!_nohz_idle_balance(this_rq, NOHZ_STATS_KICK, CPU_NEWLY_IDLE)))
+			kick_ilb(NOHZ_STATS_KICK);
+
 		goto out;
 	}
 
@@ -9393,30 +9410,24 @@ static void rebalance_domains(struct rq *rq, enum cpu_idle_type idle)
 
 #ifdef CONFIG_NO_HZ_COMMON
 /*
- * In CONFIG_NO_HZ_COMMON case, the idle balance kickee will do the
- * rebalancing for all the cpus for whom scheduler ticks are stopped.
+ * Internal function that runs load balance for all idle cpus. The load balance
+ * can be a simple update of blocked load or a complete load balance with
+ * tasks movement depending of flags.
+ * For newly idle mode, we abort the loop if it takes too much time and return
+ * false to notify that the loop has not be completed and a ilb should be kick.
  */
-static bool nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
+static bool _nohz_idle_balance(struct rq *this_rq, unsigned int flags, enum cpu_idle_type idle)
 {
 	/* Earliest time when we have to do rebalance again */
 	unsigned long now = jiffies;
 	unsigned long next_balance = now + 60*HZ;
-	unsigned long next_stats = now + msecs_to_jiffies(LOAD_AVG_PERIOD);
+	bool has_blocked_load = false;
 	int update_next_balance = 0;
 	int this_cpu = this_rq->cpu;
-	unsigned int flags;
 	int balance_cpu;
+	int ret = false;
 	struct rq *rq;
-
-	if (!(atomic_read(nohz_flags(this_cpu)) & NOHZ_KICK_MASK))
-		return false;
-
-	if (idle != CPU_IDLE) {
-		atomic_andnot(NOHZ_KICK_MASK, nohz_flags(this_cpu));
-		return false;
-	}
-
-	flags = atomic_fetch_andnot(NOHZ_KICK_MASK, nohz_flags(this_cpu));
+	u64 curr_cost = 0;
 
 	SCHED_WARN_ON((flags & NOHZ_KICK_MASK) == NOHZ_BALANCE_KICK);
 
@@ -9431,6 +9442,10 @@ static bool nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 	WRITE_ONCE(nohz.has_blocked, 0);
 
 	for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
+		u64 t0, domain_cost;
+
+		t0 = sched_clock_cpu(this_cpu);
+
 		if (balance_cpu == this_cpu || !idle_cpu(balance_cpu))
 			continue;
 
@@ -9444,6 +9459,16 @@ static bool nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 			goto abort;
 		}
 
+		/*
+		 * If the update is done while CPU becomes idle, we abort
+		 * the update when its cost is higher than the average idle
+		 * time in orde to not delay a possible wake up.
+		 */
+		if (idle == CPU_NEWLY_IDLE && this_rq->avg_idle < curr_cost) {
+			has_blocked_load = true;
+			goto abort;
+		}
+
 		rq = cpu_rq(balance_cpu);
 
 		update_blocked_averages(rq->cpu);
@@ -9456,10 +9481,10 @@ static bool nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 		if (time_after_eq(jiffies, rq->next_balance)) {
 			struct rq_flags rf;
 
-			rq_lock_irq(rq, &rf);
+			rq_lock_irqsave(rq, &rf);
 			update_rq_clock(rq);
 			cpu_load_update_idle(rq);
-			rq_unlock_irq(rq, &rf);
+			rq_unlock_irqrestore(rq, &rf);
 
 			if (flags & NOHZ_BALANCE_KICK)
 				rebalance_domains(rq, CPU_IDLE);
@@ -9469,15 +9494,27 @@ static bool nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 			next_balance = rq->next_balance;
 			update_next_balance = 1;
 		}
+
+		domain_cost = sched_clock_cpu(this_cpu) - t0;
+		curr_cost += domain_cost;
+
+	}
+
+	/* Newly idle CPU doesn't need an update */
+	if (idle != CPU_NEWLY_IDLE) {
+		update_blocked_averages(this_cpu);
+		has_blocked_load |= this_rq->has_blocked_load;
 	}
 
-	update_blocked_averages(this_cpu);
 	if (flags & NOHZ_BALANCE_KICK)
 		rebalance_domains(this_rq, CPU_IDLE);
 
 	WRITE_ONCE(nohz.next_blocked,
 		now + msecs_to_jiffies(LOAD_AVG_PERIOD));
 
+	/* The full idle balance loop has been done */
+	ret = true;
+
 abort:
 	/* There is still blocked load, enable periodic update */
 	if (has_blocked_load)
@@ -9491,6 +9528,35 @@ static bool nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
 	if (likely(update_next_balance))
 		nohz.next_balance = next_balance;
 
+	return ret;
+}
+
+/*
+ * In CONFIG_NO_HZ_COMMON case, the idle balance kickee will do the
+ * rebalancing for all the cpus for whom scheduler ticks are stopped.
+ */
+static bool nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
+{
+	int this_cpu = this_rq->cpu;
+	unsigned int flags;
+
+	if (!(atomic_read(nohz_flags(this_cpu)) & NOHZ_KICK_MASK))
+		return false;
+
+	if (idle != CPU_IDLE) {
+		atomic_andnot(NOHZ_KICK_MASK, nohz_flags(this_cpu));
+		return false;
+	}
+
+	/*
+	 * barrier, pairs with nohz_balance_enter_idle(), ensures ...
+	 */
+	flags = atomic_fetch_andnot(NOHZ_KICK_MASK, nohz_flags(this_cpu));
+	if (!(flags & NOHZ_KICK_MASK))
+		return false;
+
+	_nohz_idle_balance(this_rq, flags, idle);
+
 	return true;
 }
 #else
-- 
2.7.4

Re: [PATCH v2 0/3] Update blocked load

[Peter Zijlstra]

On Tue, Feb 06, 2018 at 08:23:04PM +0100, Vincent Guittot wrote:
> This patchset applies on top of Peter's sched/esting branch minus the last 2 commit:
> 56eb46798b33 ("sched: Clean up nohz enter/exit")

So what will update the blocked load after we wake from a total idle?

I don't see anything here that would do that (yet?).

Re: [PATCH v2 0/3] Update blocked load

[Vincent Guittot]

On 6 February 2018 at 22:25, Peter Zijlstra <peterz@infradead.org> wrote:
> On Tue, Feb 06, 2018 at 08:23:04PM +0100, Vincent Guittot wrote:
>> This patchset applies on top of Peter's sched/esting branch minus the last 2 commit:
>> 56eb46798b33 ("sched: Clean up nohz enter/exit")
>
> So what will update the blocked load after we wake from a total idle?
>
> I don't see anything here that would do that (yet?).

The fast wake up path uses only idle state and runnable load average.
The later is normally up to date and null ( thanks to the propagation
of runnable) because of the fact that we were totally idle.
For the other "slow" path, we need to update the utilization of the
CPUs when we use them (and the load as well even if we don't use it).
This will be part of another patch as the overhead need to be
evaluated

That should be enough to take the right decision at wake up from a
long total idle state

Then for a complete update of the load metric, we can either wait for
the next tick or kick an ilb at wake up (what you don't like).