Date: Fri, 30 Jun 2017 10:28:17 -0400
From: Josef Bacik <josef@toxicpanda.com>
To: Joel Fernandes <joelaf@google.com>
Cc: Josef Bacik <josef@toxicpanda.com>,
        Mike Galbraith <umgwanakikbuti@gmail.com>,
        Peter Zijlstra <peterz@infradead.org>,
        LKML <linux-kernel@vger.kernel.org>, Juri Lelli <Juri.Lelli@arm.com>,
        Dietmar Eggemann <dietmar.eggemann@arm.com>,
        Patrick Bellasi <patrick.bellasi@arm.com>,
        Brendan Jackman <brendan.jackman@arm.com>,
        Chris Redpath <Chris.Redpath@arm.com>
Subject: Re: wake_wide mechanism clarification
Message-ID: <20170630142815.GA9743@destiny>
References: <CAJWu+oo0_zAWLjObRZp-r3VH5kKKb4aFVnRevtbYh+uH_tCNag@mail.gmail.com>
 <20170630004912.GA2457@destiny>
 <CAJWu+opFTvnGnYyRo9eYZJUxiHdoMCMoadUvnX3p=6ypwWX_Jw@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <CAJWu+opFTvnGnYyRo9eYZJUxiHdoMCMoadUvnX3p=6ypwWX_Jw@mail.gmail.com>
User-Agent: Mutt/1.8.0 (2017-02-23)
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 3927
Lines: 77

On Thu, Jun 29, 2017 at 08:04:59PM -0700, Joel Fernandes wrote:
> Hi Josef,
> 
> Thanks a lot for your reply, :-)
> 
> On Thu, Jun 29, 2017 at 5:49 PM, Josef Bacik <josef@toxicpanda.com> wrote:
> > Because we are trying to detect the case that the master is waking many
> > different processes, and the 'slave' processes are only waking up the
> > master/some other specific processes to determine if we don't care about cache
> > locality.
> >
> >>
> >> The code here is written as:
> >>
> >> if (slave < factor || master < slave * factor)
> >>    return 0;
> >>
> >> However I think we should just do (with my current and probably wrong
> >> understanding):
> >>
> >> if (slave < factor || master < factor)
> >>     return 0;
> >>
> >
> > Actually I think both are wrong, but I need Mike to weigh in.  In my example
> > above we'd return 0, because the 'producer' will definitely have a wakee_flip of
> > ridiculous values, but the 'consumer' could essentially have a wakee_flip of 1,
> > just the master to tell it that it's done.  I _suppose_ in practice you have a
> > lock or something so the wakee_flip isn't going to be strictly 1, but some
> > significantly lower value than master.  I'm skeptical of the slave < factor
> > test, I think it's too high of a bar in the case where cache locality doesn't
> > really matter, but the master < slave * factor makes sense, as slave is going to
> > be orders of magnitude lower than master.
> 
> That makes sense that we multiply slave's flips by a factor because
> its low, but I still didn't get why the factor is chosen to be
> llc_size instead of something else for the multiplication with slave
> (slave * factor). I know slave's flips are probably low and need to be
> higher, but why its multiplied with llc_size than some other number
> (in other words - why we are tying the size of a NUMA node or a
> cluster size with the number of wake-ups that the slave made)? Is this
> because of an assumption that a master is expected to evenly
> distribute work amongs CPUs within its node or something like that?
> 

Yeah I don't know why llc_size was chosen, but I've been thinking about this on
and off since last night and I don't really know what the right thing to use
would be.  We need some arbitrary number, and any arbitrary number is going to
be wrong for one workload when its fine for another workload.

What we really want is to know how many different tasks we could potentially
wake up to compare against, and that's kind of impossible.  If we did it based
soley on actual wakee_flips values we could end up with the case that 1 tasks
that has 2 worker tasks always being wake_wide, and that may not be as helpful.
With processes that are threaded then sure we have a readily available number to
use, but for things that are discrete processes that talk over say a pipe or
shared memory that's going to be unpossible to tease out.  I haven't had my Mt.
Dew this morning so if you have a better idea for a factor I'm all ears.

> More over, this case is only for when slave wakeups are far lower than
> the master. But, what about the case where slave wakes up are greater
> than the factor but approximately equal or around the same as the
> masters'. Then, it sounds like (master < slave * factor) can return
> true. In that case wake_wide() will be = 0. That sounds like a bad
> thing to do I think - pull a busy slave onto a busy master.
> 

This I think is a flaw in our load balancing assumptions.  I've been drowning in
this code recently because of a cgroups imbalance problem.  We don't really
propagate load well for processes that are on the rq but haven't run yet, so I
feel this plays into this problem where we think the cpu we're pulling to has
plenty of capacity when in reality it doesnt.

I'm going to tool around with this logic some this morning and see if I can make
it a little bit smarter, I'll let you know how it goes.  Thanks,

Josef