Signal a blocked futex if the isolate is interrupted; don't busy-wait

Signal a blocked futex if the isolate is interrupted; don't busy-wait

FutexEmulation::Wait can potentially block forever on a condition variable. We
want to allow this to be interrupted (for a debugger, or to terminate the
thread, for example).

The previous implementation would periodically wake up the waiter to check for
interrupts. This CL modifies the StackGuard so it wakes the blocked futex if
the thread should be interrupted.

BUG=chromium:497295
R=jarin@chromium.org
LOG=n

Committed: https://crrev.com/b7cf73271d2bbabfd4c19b6b1158c476c364c747
Cr-Commit-Position: refs/heads/master@{#30311}

[Jarin, 2015-07-23 13:01:05]

I thought it looked good to me, but the bots disagree. Could you take a look?
(It would be great if you could describe what went wrong.)

[Jarin, 2015-08-11 08:21:49]

One question below. 

Still, could you explain why it deadlocked?

https://codereview.chromium.org/1230303005/diff/80001/src/futex-emulation.cc
File src/futex-emulation.cc (right):

https://codereview.chromium.org/1230303005/diff/80001/src/futex-emulation.cc#...
src/futex-emulation.cc:138: if (node->CheckInterruptedAndClear()) {
Why can't you read and clear the interrupt flag while still holding the lock?
That way, you would not have to resort to the CASing, no? (You could also use
lexically scoped guards.)

[binji, 2015-08-11 14:51:17]

There were multiple deadlocks. I described them briefly in the comments, but
I'll go into more detail here.

1) Originally I didn't lock in NotifyWake. That is mostly OK on POSIX, but fails
on Windows because the CondVar implementation expects it (there is a DCHECK in
ConditionVariable::Wait() that can fire -- I believe it is because SetEvent
could cause a thread switch before notified is set to true).

It turns out that the lock is useful anyway (for preventing lost wakeups), so I
added it in. This causes a lock inversion with the execution lock when
requesting an interrupt. The fix here is to release the execution lock before
calling NotifyWake.

2) The second deadlock was much more rare (~2 times out of 10000), and looked
like it was Windows-only. This inversion occurs when the futex lock is held
while calling HandleInterrupts. This can occasionally coincide with the
OptimizingCompilerDispatcher being run on both threads. This object has a mutex
"output_queue_mutex_" that is acquired in CompileNext and in
InstallOptimizedFunctions. The inversion occurs between this lock and the futex
lock. The thread requesting the interrupt locks output_queue_mutex_, then calls
NotifyWake which locks the futex lock. The futexwait thread locks the futex
lock, then tries to lock the output_queue_mutex_ when calling HandleInterrupts.

Now that I look at it, these are the same deadlock; so I can remove the
unlock/lock pair around the execution lock.

The other thing that was throwing me off was the Time vs. TimeTicks bug, which
would cause occasional flakes on Windows -- it was hard to tell if those were
related or not.

https://codereview.chromium.org/1230303005/diff/80001/src/futex-emulation.cc
File src/futex-emulation.cc (right):

https://codereview.chromium.org/1230303005/diff/80001/src/futex-emulation.cc#...
src/futex-emulation.cc:138: if (node->CheckInterruptedAndClear()) {
On 2015/08/11 at 08:21:49, Jarin wrote:
> Why can't you read and clear the interrupt flag while still holding the lock?
That way, you would not have to resort to the CASing, no? (You could also use
lexically scoped guards.)

Good point, I'll change this.

[binji, 2015-08-18 21:58:41]

Updated to HEAD, PTAL

[Jarin, 2015-08-19 05:26:05]

lgtm with a question.

https://codereview.chromium.org/1230303005/diff/120001/src/execution.cc
File src/execution.cc (right):

https://codereview.chromium.org/1230303005/diff/120001/src/execution.cc#newco...
src/execution.cc:418: if (isolate_->futex_wait_list_node()->waiting()) {
Could we perhaps pull the waiting() check into NotifyWake?

Then the waiting accessors could be private (and perhaps we could even pull the
waiting_ flag into the critical section and make it non-atomic).

https://codereview.chromium.org/1230303005/diff/120001/src/futex-emulation.h
File src/futex-emulation.h (right):

https://codereview.chromium.org/1230303005/diff/120001/src/futex-emulation.h#...
src/futex-emulation.h:44: waiting_(false),
waiting_(0)

[binji, 2015-08-19 17:36:23]

https://codereview.chromium.org/1230303005/diff/120001/src/execution.cc
File src/execution.cc (right):

https://codereview.chromium.org/1230303005/diff/120001/src/execution.cc#newco...
src/execution.cc:418: if (isolate_->futex_wait_list_node()->waiting()) {
On 2015/08/19 at 05:26:05, Jarin wrote:
> Could we perhaps pull the waiting() check into NotifyWake?
> 
> Then the waiting accessors could be private (and perhaps we could even pull
the waiting_ flag into the critical section and make it non-atomic).

My thought here was to do a quick check to avoid taking a lock if there is no
futex waiting (which is the common case). What do you think?

https://codereview.chromium.org/1230303005/diff/120001/src/futex-emulation.h
File src/futex-emulation.h (right):

https://codereview.chromium.org/1230303005/diff/120001/src/futex-emulation.h#...
src/futex-emulation.h:44: waiting_(false),
On 2015/08/19 at 05:26:05, Jarin wrote:
> waiting_(0)

Done.

[Jarin, 2015-08-20 05:19:58]

On 2015/08/19 17:36:23, binji wrote:
> https://codereview.chromium.org/1230303005/diff/120001/src/execution.cc
> File src/execution.cc (right):
> 
>
https://codereview.chromium.org/1230303005/diff/120001/src/execution.cc#newco...
> src/execution.cc:418: if (isolate_->futex_wait_list_node()->waiting()) {
> On 2015/08/19 at 05:26:05, Jarin wrote:
> > Could we perhaps pull the waiting() check into NotifyWake?
> > 
> > Then the waiting accessors could be private (and perhaps we could even pull
> the waiting_ flag into the critical section and make it non-atomic).
> 
> My thought here was to do a quick check to avoid taking a lock if there is no
> futex waiting (which is the common case). What do you think?

Yeah, that's what I thought. However, locks are cheap, interrupts are rare and
atomics are scary. Up to you.

[binji, 2015-08-20 23:16:13]

On 2015/08/20 at 05:19:58, jarin wrote:
> On 2015/08/19 17:36:23, binji wrote:
> > https://codereview.chromium.org/1230303005/diff/120001/src/execution.cc
> > File src/execution.cc (right):
> > 
> >
https://codereview.chromium.org/1230303005/diff/120001/src/execution.cc#newco...
> > src/execution.cc:418: if (isolate_->futex_wait_list_node()->waiting()) {
> > On 2015/08/19 at 05:26:05, Jarin wrote:
> > > Could we perhaps pull the waiting() check into NotifyWake?
> > > 
> > > Then the waiting accessors could be private (and perhaps we could even
pull
> > the waiting_ flag into the critical section and make it non-atomic).
> > 
> > My thought here was to do a quick check to avoid taking a lock if there is
no
> > futex waiting (which is the common case). What do you think?
> 
> Yeah, that's what I thought. However, locks are cheap, interrupts are rare and
atomics are scary. Up to you.

Ah, good call. I was mistakenly thinking this was a lock grabbed in
HandleInterrupts, not RequestInterrupt.

[Jarin, 2015-08-21 07:12:41]

On 2015/08/20 23:16:13, binji wrote:
> On 2015/08/20 at 05:19:58, jarin wrote:
> > On 2015/08/19 17:36:23, binji wrote:
> > > https://codereview.chromium.org/1230303005/diff/120001/src/execution.cc
> > > File src/execution.cc (right):
> > > 
> > >
>
https://codereview.chromium.org/1230303005/diff/120001/src/execution.cc#newco...
> > > src/execution.cc:418: if (isolate_->futex_wait_list_node()->waiting()) {
> > > On 2015/08/19 at 05:26:05, Jarin wrote:
> > > > Could we perhaps pull the waiting() check into NotifyWake?
> > > > 
> > > > Then the waiting accessors could be private (and perhaps we could even
> pull
> > > the waiting_ flag into the critical section and make it non-atomic).
> > > 
> > > My thought here was to do a quick check to avoid taking a lock if there is
> no
> > > futex waiting (which is the common case). What do you think?
> > 
> > Yeah, that's what I thought. However, locks are cheap, interrupts are rare
and
> atomics are scary. Up to you.
> 
> Ah, good call. I was mistakenly thinking this was a lock grabbed in
> HandleInterrupts, not RequestInterrupt.

Thanks! lgtm.

Let's see what the fuzzer thinks :-)

[binji, 2015-08-21 16:03:32]

The CQ bit was checked by binji@chromium.org

[binji, 2015-08-21 16:03:36]

The CQ bit was unchecked by binji@chromium.org

[binji, 2015-08-21 16:04:03]

The CQ bit was checked by binji@chromium.org

[commit-bot: I haz the power, 2015-08-21 16:04:13]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1230303005/160001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1230303005/160001

[commit-bot: I haz the power, 2015-08-21 16:41:50]

Committed patchset #9 (id:160001)

[commit-bot: I haz the power, 2015-08-21 16:42:12]

Patchset 9 (id:??) landed as
https://crrev.com/b7cf73271d2bbabfd4c19b6b1158c476c364c747
Cr-Commit-Position: refs/heads/master@{#30311}