linux-kernel - Re: [RFC PATCH 3/7] sched/fair: Remove magic margin in fits

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <20230906214535.y4m5rtmi6zz24wvx@airbuntu>
Date:   Wed, 6 Sep 2023 22:45:35 +0100
From:   Qais Yousef <qyousef@...alina.io>
To:     Dietmar Eggemann <dietmar.eggemann@....com>
Cc:     Ingo Molnar <mingo@...nel.org>,
        Peter Zijlstra <peterz@...radead.org>,
        "Rafael J. Wysocki" <rafael@...nel.org>,
        Viresh Kumar <viresh.kumar@...aro.org>,
        Vincent Guittot <vincent.guittot@...aro.org>,
        linux-kernel@...r.kernel.org, linux-pm@...r.kernel.org,
        Lukasz Luba <lukasz.luba@....com>
Subject: Re: [RFC PATCH 3/7] sched/fair: Remove magic margin in
 fits_capacity()

On 09/06/23 16:38, Dietmar Eggemann wrote:
> On 28/08/2023 01:31, Qais Yousef wrote:
> > 80% margin is a magic value that has served its purpose for now, but it
> > no longer fits the variety of systems exist today. If a system is over
> > powered specifically, this 80% will mean we leave a lot of capacity
> > unused before we decide to upmigrate on HMP system.
> > 
> > The upmigration behavior should rely on the fact that a bad decision
> > made will need load balance to kick in to perform misfit migration. And
> > I think this is an adequate definition for what to consider as enough
> > headroom to consider whether a util fits capacity or not.
> > 
> > Use the new approximate_util_avg() function to predict the util if the
> > task continues to run for TICK_US. If the value is not strictly less
> > than the capacity, then it must not be placed there, ie considered
> > misfit.
> > 
> > Signed-off-by: Qais Yousef (Google) <qyousef@...alina.io>
> > ---
> >  kernel/sched/fair.c | 21 ++++++++++++++++++---
> >  1 file changed, 18 insertions(+), 3 deletions(-)
> > 
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index 0b7445cd5af9..facbf3eb7141 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -109,16 +109,31 @@ int __weak arch_asym_cpu_priority(int cpu)
> >  }
> >  
> >  /*
> > - * The margin used when comparing utilization with CPU capacity.
> > + * The util will fit the capacity if it has enough headroom to grow within the
> > + * next tick - which is when any load balancing activity happens to do the
> > + * correction.
> >   *
> > - * (default: ~20%)
> > + * If util stays within the capacity before tick has elapsed, then it should be
> > + * fine. If not, then a correction action must happen shortly after it starts
> > + * running, hence we treat it as !fit.
> > + *
> > + * TODO: TICK is not actually accurate enough. balance_interval is the correct
> > + * one to use as the next load balance doesn't not happen religiously at tick.
> > + * Accessing balance_interval might be tricky and will require some refactoring
> > + * first.
> >   */
> 
> I understand that you want to have a more intelligent margin (depending
> on the util value) but why you want to use the time value of TICK_USEC
> (or the balance_interval)?
> 
> We call fits_capacity() e.g. in wakeup and the next lb can just happen
> immediately after it.

If it happens immediately, then current values we're considering without margin
are enough to make a correct decision. But worst case scenario if the task
doesn't go to sleep shortly after and continues to run, then we'll have to wait
for TICK_USEC for lb to kick off again and handle a misfit lb.

So we only need to add margin (or headroom which I think is a better word) to
account for the fact that a worst case scenario is that the task will run for
a full tick on this CPU. And what I'm trying to say/do here is that as long as
the task doesn't grow beyond the capacity of the CPU within tick, then it's
fine for it to run there as it won't cause misfit or require misfit lb to run.

If the value goes beyond capacity of the CPU before the end of the tick, then
this means the task had to run at lower capacity for sometime. Which is what
we're trying to avoid IIUC.


Thanks!

--
Qais Yousef

> 
> > -#define fits_capacity(cap, max)	((cap) * 1280 < (max) * 1024)
> > +static inline bool fits_capacity(unsigned long util, unsigned long capacity)
> > +{
> > +	return approximate_util_avg(util, TICK_USEC) < capacity;
> > +}
> 
> [...]
>