[PATCH] sched/fair: Remove the duplicate check from group_has_capacity()

[PATCH] sched/fair: Remove the duplicate check from group_has_capacity()

[Qi Zheng]

1. The group_has_capacity() function is only called in
   group_classify().
2. The following inequality has already been checked in
   group_is_overloaded() which was also called in
   group_classify().

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

So just remove the duplicate check from group_has_capacity().

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

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 2ba8f230feb9..a41903fb327a 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -8234,10 +8234,6 @@ 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))
-		return false;
-
 	if ((sgs->group_capacity * 100) >
 			(sgs->group_util * imbalance_pct))
 		return true;
-- 
2.25.1

Re: [PATCH] sched/fair: Remove the duplicate check from group_has_capacity()

[Valentin Schneider]

On 10/08/20 02:00, Qi Zheng wrote:
> 1. The group_has_capacity() function is only called in
>    group_classify().
> 2. The following inequality has already been checked in
>    group_is_overloaded() which was also called in
>    group_classify().
>
>       (sgs->group_capacity * imbalance_pct) <
>                         (sgs->group_runnable * 100)
>

Consider group_is_overloaded() returns false because of the first
condition:

        if (sgs->sum_nr_running <= sgs->group_weight)
                return false;

then group_has_capacity() would be the first place where the group_runnable
vs group_capacity comparison would be done.

Now in that specific case we'll actually only check it if

  sgs->sum_nr_running == sgs->group_weight

and the only case where the runnable vs capacity check can fail here is if
there's significant capacity pressure going on. TBH this capacity pressure
could be happening even when there are fewer tasks than CPUs, so I'm not
sure how intentional that corner case is.


For the

    sgs->sum_nr_running > sgs->group_weight

case I agree with your patch, there just is that oddity at the == case.

> So just remove the duplicate check from group_has_capacity().
>
> Signed-off-by: Qi Zheng <arch0.zheng@gmail.com>
> ---
>  kernel/sched/fair.c | 4 ----
>  1 file changed, 4 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 2ba8f230feb9..a41903fb327a 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -8234,10 +8234,6 @@ 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))
> -		return false;
> -
>       if ((sgs->group_capacity * 100) >
>                       (sgs->group_util * imbalance_pct))
>               return true;

Re: [PATCH] sched/fair: Remove the duplicate check from group_has_capacity()

[Qi Zheng]

On 2020/8/11 上午2:33, Valentin Schneider wrote:
> 
> On 10/08/20 02:00, Qi Zheng wrote:
>> 1. The group_has_capacity() function is only called in
>>     group_classify().
>> 2. The following inequality has already been checked in
>>     group_is_overloaded() which was also called in
>>     group_classify().
>>
>>        (sgs->group_capacity * imbalance_pct) <
>>                          (sgs->group_runnable * 100)
>>
> 
> Consider group_is_overloaded() returns false because of the first
> condition:
> 
>          if (sgs->sum_nr_running <= sgs->group_weight)
>                  return false;
> 
> then group_has_capacity() would be the first place where the group_runnable
> vs group_capacity comparison would be done.
> 
> Now in that specific case we'll actually only check it if
> 
>    sgs->sum_nr_running == sgs->group_weight
> 
> and the only case where the runnable vs capacity check can fail here is if
> there's significant capacity pressure going on. TBH this capacity pressure
> could be happening even when there are fewer tasks than CPUs, so I'm not
> sure how intentional that corner case is.

Maybe some cpus in sg->cpumask are no longer active at the == case,
which causes the significant capacity pressure?

> 
> 
> For the
> 
>      sgs->sum_nr_running > sgs->group_weight
> 
> case I agree with your patch, there just is that oddity at the == case.
> 
>> So just remove the duplicate check from group_has_capacity().
>>
>> Signed-off-by: Qi Zheng <arch0.zheng@gmail.com>
>> ---
>>   kernel/sched/fair.c | 4 ----
>>   1 file changed, 4 deletions(-)
>>
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index 2ba8f230feb9..a41903fb327a 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -8234,10 +8234,6 @@ 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))
>> -		return false;
>> -
>>        if ((sgs->group_capacity * 100) >
>>                        (sgs->group_util * imbalance_pct))
>>                return true;

Re: [PATCH] sched/fair: Remove the duplicate check from group_has_capacity()

[Valentin Schneider]

On 11/08/20 04:39, Qi Zheng wrote:
> On 2020/8/11 上午2:33, Valentin Schneider wrote:
>>
>> On 10/08/20 02:00, Qi Zheng wrote:
>>> 1. The group_has_capacity() function is only called in
>>>     group_classify().
>>> 2. The following inequality has already been checked in
>>>     group_is_overloaded() which was also called in
>>>     group_classify().
>>>
>>>        (sgs->group_capacity * imbalance_pct) <
>>>                          (sgs->group_runnable * 100)
>>>
>>
>> Consider group_is_overloaded() returns false because of the first
>> condition:
>>
>>          if (sgs->sum_nr_running <= sgs->group_weight)
>>                  return false;
>>
>> then group_has_capacity() would be the first place where the group_runnable
>> vs group_capacity comparison would be done.
>>
>> Now in that specific case we'll actually only check it if
>>
>>    sgs->sum_nr_running == sgs->group_weight
>>
>> and the only case where the runnable vs capacity check can fail here is if
>> there's significant capacity pressure going on. TBH this capacity pressure
>> could be happening even when there are fewer tasks than CPUs, so I'm not
>> sure how intentional that corner case is.
>
> Maybe some cpus in sg->cpumask are no longer active at the == case,
> which causes the significant capacity pressure?
>

That can only happen in that short window between deactivating a CPU and
not having rebuilt the sched_domains yet, which sounds quite elusive.

Re: [PATCH] sched/fair: Remove the duplicate check from group_has_capacity()

[Qi Zheng]

On 2020/8/11 下午6:38, Valentin Schneider wrote:
> 
> On 11/08/20 04:39, Qi Zheng wrote:
>> On 2020/8/11 上午2:33, Valentin Schneider wrote:
>>>
>>> On 10/08/20 02:00, Qi Zheng wrote:
>>>> 1. The group_has_capacity() function is only called in
>>>>      group_classify().
>>>> 2. The following inequality has already been checked in
>>>>      group_is_overloaded() which was also called in
>>>>      group_classify().
>>>>
>>>>         (sgs->group_capacity * imbalance_pct) <
>>>>                           (sgs->group_runnable * 100)
>>>>
>>>
>>> Consider group_is_overloaded() returns false because of the first
>>> condition:
>>>
>>>           if (sgs->sum_nr_running <= sgs->group_weight)
>>>                   return false;
>>>
>>> then group_has_capacity() would be the first place where the group_runnable
>>> vs group_capacity comparison would be done.
>>>
>>> Now in that specific case we'll actually only check it if
>>>
>>>     sgs->sum_nr_running == sgs->group_weight
>>>
>>> and the only case where the runnable vs capacity check can fail here is if
>>> there's significant capacity pressure going on. TBH this capacity pressure
>>> could be happening even when there are fewer tasks than CPUs, so I'm not
>>> sure how intentional that corner case is.
>>
>> Maybe some cpus in sg->cpumask are no longer active at the == case,
>> which causes the significant capacity pressure?
>>
> 
> That can only happen in that short window between deactivating a CPU and
> not having rebuilt the sched_domains yet, which sounds quite elusive.
> 

In fact, at the beginning, I added unlikely() here to hint the compiler:

-	if ((sgs->group_capacity * imbalance_pct) <
-			(sgs->group_runnable * 100))
+	if (unlikely((sgs->group_capacity * imbalance_pct) <
+			(sgs->group_runnable * 100)))

The corresponding patch is as follows:

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

Do you think it is necessary?

Re: [PATCH] sched/fair: Remove the duplicate check from group_has_capacity()

[Valentin Schneider]

On 11/08/20 12:44, Qi Zheng wrote:
> On 2020/8/11 下午6:38, Valentin Schneider wrote:
>>
>> On 11/08/20 04:39, Qi Zheng wrote:
>>> On 2020/8/11 上午2:33, Valentin Schneider wrote:
>>>>
>>>> On 10/08/20 02:00, Qi Zheng wrote:
>>>>> 1. The group_has_capacity() function is only called in
>>>>>      group_classify().
>>>>> 2. The following inequality has already been checked in
>>>>>      group_is_overloaded() which was also called in
>>>>>      group_classify().
>>>>>
>>>>>         (sgs->group_capacity * imbalance_pct) <
>>>>>                           (sgs->group_runnable * 100)
>>>>>
>>>>
>>>> Consider group_is_overloaded() returns false because of the first
>>>> condition:
>>>>
>>>>           if (sgs->sum_nr_running <= sgs->group_weight)
>>>>                   return false;
>>>>
>>>> then group_has_capacity() would be the first place where the group_runnable
>>>> vs group_capacity comparison would be done.
>>>>
>>>> Now in that specific case we'll actually only check it if
>>>>
>>>>     sgs->sum_nr_running == sgs->group_weight
>>>>
>>>> and the only case where the runnable vs capacity check can fail here is if
>>>> there's significant capacity pressure going on. TBH this capacity pressure
>>>> could be happening even when there are fewer tasks than CPUs, so I'm not
>>>> sure how intentional that corner case is.
>>>
>>> Maybe some cpus in sg->cpumask are no longer active at the == case,
>>> which causes the significant capacity pressure?
>>>
>>
>> That can only happen in that short window between deactivating a CPU and
>> not having rebuilt the sched_domains yet, which sounds quite elusive.
>>
>
> In fact, at the beginning, I added unlikely() here to hint the compiler:
>
> -	if ((sgs->group_capacity * imbalance_pct) <
> -			(sgs->group_runnable * 100))
> +	if (unlikely((sgs->group_capacity * imbalance_pct) <
> +			(sgs->group_runnable * 100)))
>
> The corresponding patch is as follows:
>
>       [PATCH]sched/core: add unlikely in group_has_capacity()
>
> Do you think it is necessary?

The "unlikely" approach has the benefit of keeping all corner cases in
place. I was tempted to say it could still make sense to get rid of the
extra check entirely, given that it has an impact only when:

- sum_nr_running == group_weight
- group capacity has been noticeably reduced

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().

That said, it does make very much sense to check it in that ==
case. Vincent might have a different take on this, but right now I'd say
the unlikely approach is the safest one of the two.

Re: [PATCH] sched/fair: Remove the duplicate check from group_has_capacity()

[Qi Zheng]

On 2020/8/11 下午8:48, Valentin Schneider wrote:
> 
> On 11/08/20 12:44, Qi Zheng wrote:
>> On 2020/8/11 下午6:38, Valentin Schneider wrote:
>>>
>>> On 11/08/20 04:39, Qi Zheng wrote:
>>>> On 2020/8/11 上午2:33, Valentin Schneider wrote:
>>>>>
>>>>> On 10/08/20 02:00, Qi Zheng wrote:
>>>>>> 1. The group_has_capacity() function is only called in
>>>>>>       group_classify().
>>>>>> 2. The following inequality has already been checked in
>>>>>>       group_is_overloaded() which was also called in
>>>>>>       group_classify().
>>>>>>
>>>>>>          (sgs->group_capacity * imbalance_pct) <
>>>>>>                            (sgs->group_runnable * 100)
>>>>>>
>>>>>
>>>>> Consider group_is_overloaded() returns false because of the first
>>>>> condition:
>>>>>
>>>>>            if (sgs->sum_nr_running <= sgs->group_weight)
>>>>>                    return false;
>>>>>
>>>>> then group_has_capacity() would be the first place where the group_runnable
>>>>> vs group_capacity comparison would be done.
>>>>>
>>>>> Now in that specific case we'll actually only check it if
>>>>>
>>>>>      sgs->sum_nr_running == sgs->group_weight
>>>>>
>>>>> and the only case where the runnable vs capacity check can fail here is if
>>>>> there's significant capacity pressure going on. TBH this capacity pressure
>>>>> could be happening even when there are fewer tasks than CPUs, so I'm not
>>>>> sure how intentional that corner case is.
>>>>
>>>> Maybe some cpus in sg->cpumask are no longer active at the == case,
>>>> which causes the significant capacity pressure?
>>>>
>>>
>>> That can only happen in that short window between deactivating a CPU and
>>> not having rebuilt the sched_domains yet, which sounds quite elusive.
>>>
>>
>> In fact, at the beginning, I added unlikely() here to hint the compiler:
>>
>> -	if ((sgs->group_capacity * imbalance_pct) <
>> -			(sgs->group_runnable * 100))
>> +	if (unlikely((sgs->group_capacity * imbalance_pct) <
>> +			(sgs->group_runnable * 100)))
>>
>> The corresponding patch is as follows:
>>
>>        [PATCH]sched/core: add unlikely in group_has_capacity()
>>
>> Do you think it is necessary?
> 
> The "unlikely" approach has the benefit of keeping all corner cases in
> place. I was tempted to say it could still make sense to get rid of the
> extra check entirely, given that it has an impact only when:
> 
> - sum_nr_running == group_weight
> - group capacity has been noticeably reduced
> 
> 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().
> 
> That said, it does make very much sense to check it in that ==
> case. Vincent might have a different take on this, but right now I'd say
> the unlikely approach is the safest one of the two.
> 

So what should I do next? Do I resubmit a patch with unlikely() or
add your email to the old patch([PATCH]sched/core: add unlikely in
group_has_capacity())? Or continue to wait for suggestions from
other maintainers?

Re: [PATCH] sched/fair: Remove the duplicate check from group_has_capacity()

[Valentin Schneider]

On 11/08/20 14:12, Qi Zheng wrote:
> On 2020/8/11 下午8:48, Valentin Schneider wrote:
>> On 11/08/20 12:44, Qi Zheng wrote:
>>> In fact, at the beginning, I added unlikely() here to hint the compiler:
>>>
>>> -	if ((sgs->group_capacity * imbalance_pct) <
>>> -			(sgs->group_runnable * 100))
>>> +	if (unlikely((sgs->group_capacity * imbalance_pct) <
>>> +			(sgs->group_runnable * 100)))
>>>
>>> The corresponding patch is as follows:
>>>
>>>        [PATCH]sched/core: add unlikely in group_has_capacity()
>>>
>>> Do you think it is necessary?
>>
>> The "unlikely" approach has the benefit of keeping all corner cases in
>> place. I was tempted to say it could still make sense to get rid of the
>> extra check entirely, given that it has an impact only when:
>>
>> - sum_nr_running == group_weight
>> - group capacity has been noticeably reduced
>>
>> 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().
>>
>> That said, it does make very much sense to check it in that ==
>> case. Vincent might have a different take on this, but right now I'd say
>> the unlikely approach is the safest one of the two.
>>
>
> So what should I do next? Do I resubmit a patch with unlikely() or
> add your email to the old patch([PATCH]sched/core: add unlikely in
> group_has_capacity())? Or continue to wait for suggestions from
> other maintainers?

I guess you can add a reply to the original thread where you had the
unlikely() to point out *removing* the check isn't 100% harmless.

Vincent might want to have a look at it, but AFAIA he's on holidays ATM.

Re: [PATCH] sched/fair: Remove the duplicate check from group_has_capacity()

[Qi Zheng]

On 2020/8/12 上午4:16, Valentin Schneider wrote:
> 
> On 11/08/20 14:12, Qi Zheng wrote:
>> On 2020/8/11 下午8:48, Valentin Schneider wrote:
>>> On 11/08/20 12:44, Qi Zheng wrote:
>>>> In fact, at the beginning, I added unlikely() here to hint the compiler:
>>>>
>>>> -	if ((sgs->group_capacity * imbalance_pct) <
>>>> -			(sgs->group_runnable * 100))
>>>> +	if (unlikely((sgs->group_capacity * imbalance_pct) <
>>>> +			(sgs->group_runnable * 100)))
>>>>
>>>> The corresponding patch is as follows:
>>>>
>>>>         [PATCH]sched/core: add unlikely in group_has_capacity()
>>>>
>>>> Do you think it is necessary?
>>>
>>> The "unlikely" approach has the benefit of keeping all corner cases in
>>> place. I was tempted to say it could still make sense to get rid of the
>>> extra check entirely, given that it has an impact only when:
>>>
>>> - sum_nr_running == group_weight
>>> - group capacity has been noticeably reduced
>>>
>>> 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().
>>>
>>> That said, it does make very much sense to check it in that ==
>>> case. Vincent might have a different take on this, but right now I'd say
>>> the unlikely approach is the safest one of the two.
>>>
>>
>> So what should I do next? Do I resubmit a patch with unlikely() or
>> add your email to the old patch([PATCH]sched/core: add unlikely in
>> group_has_capacity())? Or continue to wait for suggestions from
>> other maintainers?
> 
> I guess you can add a reply to the original thread where you had the
> unlikely() to point out *removing* the check isn't 100% harmless.
> 
> Vincent might want to have a look at it, but AFAIA he's on holidays ATM.
> 

Okay, I will reply to the old patch and add your email to it.
Thanks for your comments.

Yours,
Qi Zheng