linux-kernel - Re: [PATCH] sched/core: add unlikely in group_has

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <CAKfTPtBGA8d5zKcTkotxD+NmSmfXNt6yUOG_q8FN0g-rdor8bw@mail.gmail.com>
Date:   Mon, 17 Aug 2020 10:18:59 +0200
From:   Vincent Guittot <vincent.guittot@...aro.org>
To:     Qi Zheng <arch0.zheng@...il.com>
Cc:     Ingo Molnar <mingo@...nel.org>,
        Valentin Schneider <valentin.schneider@....com>,
        Ingo Molnar <mingo@...hat.com>,
        Peter Zijlstra <peterz@...radead.org>,
        Juri Lelli <juri.lelli@...hat.com>,
        Dietmar Eggemann <dietmar.eggemann@....com>,
        Steven Rostedt <rostedt@...dmis.org>,
        Ben Segall <bsegall@...gle.com>, Mel Gorman <mgorman@...e.de>,
        linux-kernel <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH] sched/core: add unlikely in group_has_capacity()

On Wed, 12 Aug 2020 at 03:49, Qi Zheng <arch0.zheng@...il.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@...il.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@...il.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@....com>.
>
> Yours,
> Qi Zheng