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 for Android: free password hash cracker in your pocket
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20231022002805.GA3219395@google.com>
Date:   Sun, 22 Oct 2023 00:28:05 +0000
From:   Joel Fernandes <joel@...lfernandes.org>
To:     Vincent Guittot <vincent.guittot@...aro.org>
Cc:     linux-kernel@...r.kernel.org, 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>,
        Daniel Bristot de Oliveira <bristot@...hat.com>,
        Valentin Schneider <vschneid@...hat.com>,
        "Vineeth Pillai (Google)" <vineeth@...byteword.org>,
        Suleiman Souhlal <suleiman@...gle.com>,
        Frederic Weisbecker <frederic@...nel.org>,
        "Paul E . McKenney" <paulmck@...nel.org>
Subject: Re: [PATCH 3/3] sched: Update ->next_balance correctly during
 newidle balance

On Fri, Oct 20, 2023 at 03:40:14PM +0200, Vincent Guittot wrote:
> On Fri, 20 Oct 2023 at 03:40, Joel Fernandes (Google)
> <joel@...lfernandes.org> wrote:
> >
> > From: "Vineeth Pillai (Google)" <vineeth@...byteword.org>
> >
> > When newidle balancing triggers, we see that it constantly clobbers
> > rq->next_balance even when there is no newidle balance happening due to
> > the cost estimates.  Due to this, we see that periodic load balance
> > (rebalance_domains) may trigger way more often when the CPU is going in
> > and out of idle at a high rate but is no really idle. Repeatedly
> > triggering load balance there is a bad idea as it is a heavy operation.
> > It also causes increases in softirq.
> 
> we have 2 balance intervals:
> - one when idle based on the sd->balance_interval = sd_weight
> - one when busy which increases the period by multiplying it with
> busy_factor = 16

On my production system I see load balance triggering every 4 jiffies! In a
Qemu system (which I use for traces below), I see every 8 jiffies. I'll go
look into that more as well, it could be something going on in
get_sd_balance_interval().

> When becoming idle, the rq->next_balance can have been set using the
> 16*sd_weight period so load_balance can wait for a long time before
> running idle load balance for this cpu.

Got it.

> As a typical example, instead of waiting at most 8ms, we will wait
> 128ms before we try to pull a task on the idle CPU.
> 
> That's the reason for updating rq->next_balance in newidle_balance()

Got it, makes sense. But I still feel the mechanism is too aggressive, see
below.

> > Another issue is ->last_balance is not updated after newidle balance
> > causing mistakes in the ->next_balance calculations.
> 
> newly idle load balance is not equal to idle load balance. It's a
> light load balance trying to pull one  task and you can't really
> consider it to the normal load balance

True. However the point is that it is coupled with the other load balance
mechanism and the two are not independent. As you can see below, modifying
rq->next_balance in newidle also causes the periodic balance to happen more
aggressively as well if there is a high transition from busy to idle and
viceversa.

> > Fix by updating last_balance when a newidle load balance actually
> > happens and then updating next_balance. This is also how it is done in
> > other load balance paths.
> >
> > Testing shows a significant drop in softirqs when running:
> > cyclictest -i 100 -d 100 --latency=1000 -D 5 -t -m  -q
> >
> > Goes from ~6k to ~800.
> 
> Even if your figures look interesting, your patch adds regression in
> the load balance and the fairness.

Yes I see that now. However it does illustrate the problem IMO.

> We can probably do improve the current behavior for decreasing number
> of ILB but your proposal is not the right solution IMO

One of the problems is if you have task goes idle a lot, then the
newidle_balance mechanism triggers the periodic balance every jiffie (once
per millisecond on HZ=1000).

Following are some traces I collected.

cyclictest-123   [003]   522.650574  newidle_balance: this_rq[cpu=3]->next_balance: 221,264 -> 221,145 (jiffies=221,157)
   <idle>-0      [003]   522.651443  trigger_load_balance: time_after_eq(jiffies=221,158, rq->next_balance=221,145) = 1
   <idle>-0      [003]   522.651461  rebalance_domains: rq[cpu=3]->next_balance: 221,145 -> 221,264 (jiffies=221,158)
cyclictest-123   [003]   522.651494  newidle_balance: this_rq[cpu=3]->next_balance: 221,264 -> 221,145 (jiffies=221,158)
   <idle>-0      [003]   522.652522  trigger_load_balance: time_after_eq(jiffies=221,159, rq->next_balance=221,145) = 1
   <idle>-0      [003]   522.652560  rebalance_domains: rq[cpu=3]->next_balance: 221,145 -> 221,264 (jiffies=221,159)
cyclictest-124   [003]   522.652586  newidle_balance: this_rq[cpu=3]->next_balance: 221,264 -> 221,145 (jiffies=221,159)
   <idle>-0      [003]   522.654492  trigger_load_balance: time_after_eq(jiffies=221,161, rq->next_balance=221,145) = 1
   <idle>-0      [003]   522.654534  rebalance_domains: rq[cpu=3]->next_balance: 221,145 -> 221,264 (jiffies=221,161)

Triggering it so aggressively likely that is useless, it increases softirq
count and hurts power when no real work is done IMHO. And it probably makes
things worse for power on ARM where you have uclamp stuff happening in the
load balance paths which is quite heavy when I last traced that..

Further, we have observed in our tracing on real device that the update of
rq->next_balance from the newidle path is itself buggy... we observed that
because newidle balance may not update rq->last_balance, it is possible that
rq->next_balance when updated by update_next_balance() will be updated to a
value that is in the past and it will be stuck there for a long time! Perhaps
we should investigate more and fix that bug separately. Vineeth could provide
more details on the "getting stuck in the past" behavior as well.

I hope these patches highlight some of the issues we find and can trigger any
improvements by us or others. From our side we'll continue to work on it and
thank you for explaining some of the load balance code!

thanks,

 - Joel & Vineeth


> 
> >
> > Cc: Suleiman Souhlal <suleiman@...gle.com>
> > Cc: Steven Rostedt <rostedt@...dmis.org>
> > Cc: Frederic Weisbecker <frederic@...nel.org>
> > Cc: Paul E. McKenney <paulmck@...nel.org>
> > Signed-off-by: Vineeth Pillai (Google) <vineeth@...byteword.org>
> > Co-developed-by: Joel Fernandes (Google) <joel@...lfernandes.org>
> > Signed-off-by: Joel Fernandes (Google) <joel@...lfernandes.org>
> > ---
> >  kernel/sched/fair.c | 8 ++------
> >  1 file changed, 2 insertions(+), 6 deletions(-)
> >
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index 8e276d12c3cb..b147ad09126a 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -12076,11 +12076,7 @@ static int newidle_balance(struct rq *this_rq, struct rq_flags *rf)
> >
> >         if (!READ_ONCE(this_rq->rd->overload) ||
> >             (sd && this_rq->avg_idle < sd->max_newidle_lb_cost)) {
> > -
> > -               if (sd)
> > -                       update_next_balance(sd, &next_balance);
> >                 rcu_read_unlock();
> > -
> >                 goto out;
> >         }
> >         rcu_read_unlock();
> > @@ -12095,8 +12091,6 @@ static int newidle_balance(struct rq *this_rq, struct rq_flags *rf)
> >                 int continue_balancing = 1;
> >                 u64 domain_cost;
> >
> > -               update_next_balance(sd, &next_balance);
> > -
> >                 if (this_rq->avg_idle < curr_cost + sd->max_newidle_lb_cost)
> >                         break;
> >
> > @@ -12109,6 +12103,8 @@ static int newidle_balance(struct rq *this_rq, struct rq_flags *rf)
> >                         t1 = sched_clock_cpu(this_cpu);
> >                         domain_cost = t1 - t0;
> >                         update_newidle_cost(sd, domain_cost);
> > +                       sd->last_balance = jiffies;
> > +                       update_next_balance(sd, &next_balance);
> >
> >                         curr_cost += domain_cost;
> >                         t0 = t1;
> > --
> > 2.42.0.655.g421f12c284-goog
> >

Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux Powered by OpenVZ