[PATCH] sched/core: add unlikely in group_has_capacity()

[PATCH] sched/core: add unlikely in group_has_capacity()

[Qi Zheng]

1. The group_has_capacity() function is only called in
   group_classify().
2. Before calling the group_has_capacity() function,
   group_is_overloaded() will first judge the following
   formula, if it holds, the group_classify() will directly
   return the group_overloaded.

	(sgs->group_capacity * imbalance_pct) <
                        (sgs->group_runnable * 100)

Therefore, when the group_has_capacity() is called, the
probability that the above formalu holds is very small. Hint
compilers about that.

Signed-off-by: Qi Zheng <arch0.zheng@gmail.com>
---
 kernel/sched/fair.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 2ba8f230feb9..9074fd5e23b2 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -8234,8 +8234,8 @@ group_has_capacity(unsigned int imbalance_pct, struct sg_lb_stats *sgs)
 	if (sgs->sum_nr_running < sgs->group_weight)
 		return true;
 
-	if ((sgs->group_capacity * imbalance_pct) <
-			(sgs->group_runnable * 100))
+	if (unlikely((sgs->group_capacity * imbalance_pct) <
+			(sgs->group_runnable * 100)))
 		return false;
 
 	if ((sgs->group_capacity * 100) >
-- 
2.25.1

Re: [PATCH] sched/core: add unlikely in group_has_capacity()

[Ingo Molnar]

* Qi Zheng <arch0.zheng@gmail.com> wrote:

> 1. The group_has_capacity() function is only called in
>    group_classify().
> 2. Before calling the group_has_capacity() function,
>    group_is_overloaded() will first judge the following
>    formula, if it holds, the group_classify() will directly
>    return the group_overloaded.
> 
> 	(sgs->group_capacity * imbalance_pct) <
>                         (sgs->group_runnable * 100)
> 
> Therefore, when the group_has_capacity() is called, the
> probability that the above formalu holds is very small. Hint
> compilers about that.
> 
> Signed-off-by: Qi Zheng <arch0.zheng@gmail.com>
> ---
>  kernel/sched/fair.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 2ba8f230feb9..9074fd5e23b2 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -8234,8 +8234,8 @@ group_has_capacity(unsigned int imbalance_pct, struct sg_lb_stats *sgs)
>  	if (sgs->sum_nr_running < sgs->group_weight)
>  		return true;
>  
> -	if ((sgs->group_capacity * imbalance_pct) <
> -			(sgs->group_runnable * 100))
> +	if (unlikely((sgs->group_capacity * imbalance_pct) <
> +			(sgs->group_runnable * 100)))
>  		return false;

Isn't the probability that this second check will match around 0%?

I.e. wouldn't the right fix be to remove the duplicate check from 
group_has_capacity(), because it's already been checked in 
group_classify()? Maybe while leaving a comment in place?

Thanks,

	Ingo

Re: [PATCH] sched/core: add unlikely in group_has_capacity()

[Qi Zheng]

Yeah, because of the following two points, I also think
the probability is 0%:
a) the sd is protected by rcu lock, and load_balance()
    func is between rcu_read_lock() and rcu_read_unlock().
b) the sgs is a local variable.
	
So in the group_classify(), the env->sd->imbalance_pct and
the sgs will not be changed. May I remove the duplicate check
from group_has_capacity() and resubmit a patch?

Yours,
Qi Zheng

On 2020/8/6 下午10:45, Ingo Molnar wrote:
> 
> * Qi Zheng <arch0.zheng@gmail.com> wrote:
> 
>> 1. The group_has_capacity() function is only called in
>>     group_classify().
>> 2. Before calling the group_has_capacity() function,
>>     group_is_overloaded() will first judge the following
>>     formula, if it holds, the group_classify() will directly
>>     return the group_overloaded.
>>
>> 	(sgs->group_capacity * imbalance_pct) <
>>                          (sgs->group_runnable * 100)
>>
>> Therefore, when the group_has_capacity() is called, the
>> probability that the above formalu holds is very small. Hint
>> compilers about that.
>>
>> Signed-off-by: Qi Zheng <arch0.zheng@gmail.com>
>> ---
>>   kernel/sched/fair.c | 4 ++--
>>   1 file changed, 2 insertions(+), 2 deletions(-)
>>
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index 2ba8f230feb9..9074fd5e23b2 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -8234,8 +8234,8 @@ group_has_capacity(unsigned int imbalance_pct, struct sg_lb_stats *sgs)
>>   	if (sgs->sum_nr_running < sgs->group_weight)
>>   		return true;
>>   
>> -	if ((sgs->group_capacity * imbalance_pct) <
>> -			(sgs->group_runnable * 100))
>> +	if (unlikely((sgs->group_capacity * imbalance_pct) <
>> +			(sgs->group_runnable * 100)))
>>   		return false;
> 
> Isn't the probability that this second check will match around 0%?
> 
> I.e. wouldn't the right fix be to remove the duplicate check from
> group_has_capacity(), because it's already been checked in
> group_classify()? Maybe while leaving a comment in place?
> 
> Thanks,
> 
> 	Ingo
> 

Re: [PATCH] sched/core: add unlikely in group_has_capacity()

[Qi Zheng]

On 2020/8/7 上午10:47, Qi Zheng wrote:
> Yeah, because of the following two points, I also think
> the probability is 0%:
> a) the sd is protected by rcu lock, and load_balance()
>     func is between rcu_read_lock() and rcu_read_unlock().
> b) the sgs is a local variable.
> 
> So in the group_classify(), the env->sd->imbalance_pct and
> the sgs will not be changed. May I remove the duplicate check
> from group_has_capacity() and resubmit a patch?
> 
> Yours,
> Qi Zheng
> 
> On 2020/8/6 下午10:45, Ingo Molnar wrote:
>>
>> * Qi Zheng <arch0.zheng@gmail.com> wrote:
>>
>>> 1. The group_has_capacity() function is only called in
>>>     group_classify().
>>> 2. Before calling the group_has_capacity() function,
>>>     group_is_overloaded() will first judge the following
>>>     formula, if it holds, the group_classify() will directly
>>>     return the group_overloaded.
>>>
>>>     (sgs->group_capacity * imbalance_pct) <
>>>                          (sgs->group_runnable * 100)
>>>
>>> Therefore, when the group_has_capacity() is called, the
>>> probability that the above formalu holds is very small. Hint
>>> compilers about that.
>>>
>>> Signed-off-by: Qi Zheng <arch0.zheng@gmail.com>
>>> ---
>>>   kernel/sched/fair.c | 4 ++--
>>>   1 file changed, 2 insertions(+), 2 deletions(-)
>>>
>>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>>> index 2ba8f230feb9..9074fd5e23b2 100644
>>> --- a/kernel/sched/fair.c
>>> +++ b/kernel/sched/fair.c
>>> @@ -8234,8 +8234,8 @@ group_has_capacity(unsigned int imbalance_pct, 
>>> struct sg_lb_stats *sgs)
>>>       if (sgs->sum_nr_running < sgs->group_weight)
>>>           return true;
>>> -    if ((sgs->group_capacity * imbalance_pct) <
>>> -            (sgs->group_runnable * 100))
>>> +    if (unlikely((sgs->group_capacity * imbalance_pct) <
>>> +            (sgs->group_runnable * 100)))
>>>           return false;
>>
>> Isn't the probability that this second check will match around 0%?
>>
>> I.e. wouldn't the right fix be to remove the duplicate check from
>> group_has_capacity(), because it's already been checked in
>> group_classify()? Maybe while leaving a comment in place?
>>
>> Thanks,
>>
>>     Ingo
>>

Hi,

As Valentin and I discussed in the patch below, simply removing the
check may not be completely harmless.

	[PATCH]sched/fair: Remove the duplicate check from
					group_has_capacity() :
	-	if ((sgs->group_capacity * imbalance_pct) <
	-			(sgs->group_runnable * 100))
	-		return false;


If sum_nr_running < group_weight, we won't evaluate it.
If sum_nr_running > group_weight, we either won't call into
   group_has_capacity() or we'll have checked it already in
   group_overloaded().
But in the case of sum_nr_running == group_weight, we can
run to this check.

Although I also think it is unlikely to cause the significant
capacity pressure at the == case, but I'm not sure whether there
are some special scenarios. such as some cpus in sg->cpumask are
no longer active, or other scenarios?

So adding the unlikely() in group_has_capacity() may be the safest
way.

Add Valentin Schneider <valentin.schneider@arm.com>.

Yours,
Qi Zheng

Re: [PATCH] sched/core: add unlikely in group_has_capacity()

[Vincent Guittot]

On Wed, 12 Aug 2020 at 03:49, Qi Zheng <arch0.zheng@gmail.com> wrote:
>
> On 2020/8/7 上午10:47, Qi Zheng wrote:
> > Yeah, because of the following two points, I also think
> > the probability is 0%:
> > a) the sd is protected by rcu lock, and load_balance()
> >     func is between rcu_read_lock() and rcu_read_unlock().
> > b) the sgs is a local variable.
> >
> > So in the group_classify(), the env->sd->imbalance_pct and
> > the sgs will not be changed. May I remove the duplicate check
> > from group_has_capacity() and resubmit a patch?
> >
> > Yours,
> > Qi Zheng
> >
> > On 2020/8/6 下午10:45, Ingo Molnar wrote:
> >>
> >> * Qi Zheng <arch0.zheng@gmail.com> wrote:
> >>
> >>> 1. The group_has_capacity() function is only called in
> >>>     group_classify().
> >>> 2. Before calling the group_has_capacity() function,
> >>>     group_is_overloaded() will first judge the following
> >>>     formula, if it holds, the group_classify() will directly
> >>>     return the group_overloaded.
> >>>
> >>>     (sgs->group_capacity * imbalance_pct) <
> >>>                          (sgs->group_runnable * 100)
> >>>
> >>> Therefore, when the group_has_capacity() is called, the
> >>> probability that the above formalu holds is very small. Hint
> >>> compilers about that.
> >>>
> >>> Signed-off-by: Qi Zheng <arch0.zheng@gmail.com>
> >>> ---
> >>>   kernel/sched/fair.c | 4 ++--
> >>>   1 file changed, 2 insertions(+), 2 deletions(-)
> >>>
> >>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> >>> index 2ba8f230feb9..9074fd5e23b2 100644
> >>> --- a/kernel/sched/fair.c
> >>> +++ b/kernel/sched/fair.c
> >>> @@ -8234,8 +8234,8 @@ group_has_capacity(unsigned int imbalance_pct,
> >>> struct sg_lb_stats *sgs)
> >>>       if (sgs->sum_nr_running < sgs->group_weight)
> >>>           return true;
> >>> -    if ((sgs->group_capacity * imbalance_pct) <
> >>> -            (sgs->group_runnable * 100))
> >>> +    if (unlikely((sgs->group_capacity * imbalance_pct) <
> >>> +            (sgs->group_runnable * 100)))
> >>>           return false;
> >>
> >> Isn't the probability that this second check will match around 0%?
> >>
> >> I.e. wouldn't the right fix be to remove the duplicate check from
> >> group_has_capacity(), because it's already been checked in
> >> group_classify()? Maybe while leaving a comment in place?
> >>
> >> Thanks,
> >>
> >>     Ingo
> >>
>
> Hi,
>
> As Valentin and I discussed in the patch below, simply removing the
> check may not be completely harmless.
>
>         [PATCH]sched/fair: Remove the duplicate check from
>                                         group_has_capacity() :
>         -       if ((sgs->group_capacity * imbalance_pct) <
>         -                       (sgs->group_runnable * 100))
>         -               return false;
>
>
> If sum_nr_running < group_weight, we won't evaluate it.
> If sum_nr_running > group_weight, we either won't call into
>    group_has_capacity() or we'll have checked it already in
>    group_overloaded().
> But in the case of sum_nr_running == group_weight, we can
> run to this check.

The case "sum_nr_running == group_weight" should not be considered as
a corner case because that's the final state that we are trying to
reach with load balance: 1 task per CPU
And because of task migrations involved to reach this state, we easily
have a temporarly low group_utilization (because of the migration) but
a high group_runnable. This state highlights the fact that some tasks
were competing for CPU cycles before the migration done by the load
balance and the task that remains on the CPU, should fill the spare
capacity. So the test prevents the load balance to immediately put
back another task on the CPU

Removing the condition should not be considered

>
> Although I also think it is unlikely to cause the significant
> capacity pressure at the == case, but I'm not sure whether there
> are some special scenarios. such as some cpus in sg->cpumask are
> no longer active, or other scenarios?
>
> So adding the unlikely() in group_has_capacity() may be the safest
> way.

Adding unlikely() is safe and I'm fine to add it but I'd like some
figures that show improvements

Regards,
Vincent

>
> Add Valentin Schneider <valentin.schneider@arm.com>.
>
> Yours,
> Qi Zheng