linux-kernel - Re: [PATCH RFC] select_idle

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: <20160406004412.GB57524@clm-mbp.masoncoding.com>
Date:	Tue, 5 Apr 2016 20:44:12 -0400
From:	Chris Mason <clm@...com>
To:	Matt Fleming <matt@...eblueprint.co.uk>
CC:	Peter Zijlstra <peterz@...radead.org>,
	Ingo Molnar <mingo@...nel.org>,
	Mike Galbraith <mgalbraith@...e.de>,
	<linux-kernel@...r.kernel.org>,
	Mel Gorman <mgorman@...hsingularity.net>
Subject: Re: [PATCH RFC] select_idle_sibling experiments

On Tue, Apr 05, 2016 at 09:03:02PM +0100, Matt Fleming wrote:
> On Tue, 05 Apr, at 02:08:22PM, Chris Mason wrote:
> > 
> > I started with a small-ish program to benchmark wakeup latencies.  The
> > basic idea is a bunch of worker threads who sit around and burn CPU.
> > Every once and a while they send a message to a message thread.
>  
> This reminds me of something I've been looking at recently; a similar
> workload in Mel's mmtests based on pgbench with 1-client that also has
> this problem of cpu_idle() being false at an inconvenient time in
> select_idle_sibling(), so we move the task off the cpu and the cpu
> then immediately goes idle.
> 
> This leads to tasks bouncing around the socket as we search for idle
> cpus.

It might be worth making a way to claim the idle cpu.  If there are lots
of them, we'll fan out properly instead of piling up into the first one.
If there are very few of them, we'll figure it out much faster.

> 
> > It has knobs for cpu think time, and for how long the messenger thread
> > waits before replying.  Here's how I'm running it with my patch:
>  
> [...]
> 
> Cool, I'll go have a play with this.

I'm more than open to ways to improve it, and I'll send to Mel or put in
a git tree if people find it useful.

> 
> > Now, on to the patch.  I pushed some code around and narrowed the
> > problem down to select_idle_sibling()   We have cores going into and out
> > of idle fast enough that even this cut our latencies in half:
> > 
> > static int select_idle_sibling(struct task_struct *p, int target)
> >                                 goto next;
> >  
> >                         for_each_cpu(i, sched_group_cpus(sg)) {
> > -                               if (i == target || !idle_cpu(i))
> > +                               if (!idle_cpu(i))
> >                                         goto next;
> >                         }
> >  
> > IOW, by the time we get down to for_each_cpu(), the idle_cpu() check
> > done at the top of the function is no longer valid.
>  
> Yeah. The problem is that because we're racing with the cpu going in
> and out of idle, and since you're exploiting that race condition, this
> is highly tuned to your specific workload.
> 
> Which is a roundabout way of saying, this is probably going to
> negatively impact other workloads.
> 
> > I tried a few variations on select_idle_sibling() that preserved the
> > underlying goal of returning idle cores before idle SMT threads.  They
> > were all horrible in different ways, and none of them were fast.
>  
> I toyed with ignoring cpu_idle() in select_idle_sibling() for my
> workload. That actually was faster ;)
> 
> > The patch below just makes select_idle_sibling pick the first idle
> > thread it can find.  When I ran it through production workloads here, it
> > was faster than the patch we've been carrying around for the last few
> > years.
> 
> It would be really nice if we had a lightweight way to gauge the
> "idleness" of a cpu, and whether we expect it to be idle again soon.
> 
> Failing that, could we just force the task onto 'target' when it makes
> sense and skip the idle search (and the race) altogether?

To me it feels like the search for a full free core is impossible.  The boxes
are intentionally loaded to the point where a full core is never going
to be free.  So we need this loop to quickly pick a good candidate and
move on.

The benchmark is using ~30ms of CPU time in each worker thread, so
picking a CPU with a busy worker thread is going to have a pretty big
penalty.  Just grabbing any CPU and hoping it'll be idle soon isn't
likely to work well, and if it does that's probably a bug in my
benchmark ;)

You can see this in action by adding one (or at most two) more threads
to the command line.  The p99 jumps quickly to 2ms or more.

-chris