linux-kernel - Re: wake_wide mechanism clarification

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: <CAJWu+opFTvnGnYyRo9eYZJUxiHdoMCMoadUvnX3p=6ypwWX_Jw@mail.gmail.com>
Date:   Thu, 29 Jun 2017 20:04:59 -0700
From:   Joel Fernandes <joelaf@...gle.com>
To:     Josef Bacik <josef@...icpanda.com>
Cc:     Mike Galbraith <umgwanakikbuti@...il.com>,
        Peter Zijlstra <peterz@...radead.org>,
        LKML <linux-kernel@...r.kernel.org>,
        Juri Lelli <Juri.Lelli@....com>,
        Dietmar Eggemann <dietmar.eggemann@....com>,
        Patrick Bellasi <patrick.bellasi@....com>,
        Brendan Jackman <brendan.jackman@....com>,
        Chris Redpath <Chris.Redpath@....com>
Subject: Re: wake_wide mechanism clarification

Hi Josef,

Thanks a lot for your reply, :-)

On Thu, Jun 29, 2017 at 5:49 PM, Josef Bacik <josef@...icpanda.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?

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.

>> Basically, I didn't follow why we multiply the slave's flips with
>> llc_size. That makes it sound like the master has to have way more
>> flips than the slave to return 0 from wake_wide. Could you maybe give
>> an example to clarify? Thanks a lot for your help,
>>
>
> It may be worth to try with schedbench and trace it to see how this turns out in
> practice, as that's the workload that generated all this discussion before.  I
> imagine generally speaking this works out properly.  The small regression I

I see. I will try to find some time to play with this tool. Thanks for
the pointer.

> reported before was at low RPS, so we wouldn't be waking up as many tasks as
> often, so we would be returning 0 from wake_wide() and we'd get screwed.  This
> is where I think possibly dropping the slave < factor part of the test would
> address that, but I'd have to trace it to say for sure.

Ah, I see your problem. I guess its a conflicting case/requirement? I
guess somehow to handle your case, it has to be embedded into this
condition that cache locality doesn't matter as that seems to be the
assumption of slave < factor as you pointed.

Thanks,
Joel