1 files changed, 145 insertions, 63 deletions

diff --git a/runtime/monitor.cc b/runtime/monitor.cc
index 0f0a378142..0353efdfbc 100644
--- a/runtime/monitor.cc
+++ b/runtime/monitor.cc
@@ -97,6 +97,7 @@ Monitor::Monitor(Thread* self, Thread* owner, mirror::Object* obj, int32_t hash_
       lock_count_(0),
       obj_(GcRoot<mirror::Object>(obj)),
       wait_set_(nullptr),
+      wake_set_(nullptr),
       hash_code_(hash_code),
       locking_method_(nullptr),
       locking_dex_pc_(0),
@@ -120,6 +121,7 @@ Monitor::Monitor(Thread* self, Thread* owner, mirror::Object* obj, int32_t hash_
       lock_count_(0),
       obj_(GcRoot<mirror::Object>(obj)),
       wait_set_(nullptr),
+      wake_set_(nullptr),
       hash_code_(hash_code),
       locking_method_(nullptr),
       locking_dex_pc_(0),
@@ -226,7 +228,8 @@ Monitor::~Monitor() {
 }
 
 void Monitor::AppendToWaitSet(Thread* thread) {
-  DCHECK(owner_ == Thread::Current());
+  // Not checking that the owner is equal to this thread, since we've released
+  // the monitor by the time this method is called.
   DCHECK(thread != nullptr);
   DCHECK(thread->GetWaitNext() == nullptr) << thread->GetWaitNext();
   if (wait_set_ == nullptr) {
@@ -245,24 +248,29 @@ void Monitor::AppendToWaitSet(Thread* thread) {
 void Monitor::RemoveFromWaitSet(Thread *thread) {
   DCHECK(owner_ == Thread::Current());
   DCHECK(thread != nullptr);
-  if (wait_set_ == nullptr) {
-    return;
-  }
-  if (wait_set_ == thread) {
-    wait_set_ = thread->GetWaitNext();
-    thread->SetWaitNext(nullptr);
-    return;
-  }
-
-  Thread* t = wait_set_;
-  while (t->GetWaitNext() != nullptr) {
-    if (t->GetWaitNext() == thread) {
-      t->SetWaitNext(thread->GetWaitNext());
-      thread->SetWaitNext(nullptr);
-      return;
+  auto remove = [&](Thread*& set){
+    if (set != nullptr) {
+      if (set == thread) {
+        set = thread->GetWaitNext();
+        thread->SetWaitNext(nullptr);
+        return true;
+      }
+      Thread* t = set;
+      while (t->GetWaitNext() != nullptr) {
+        if (t->GetWaitNext() == thread) {
+          t->SetWaitNext(thread->GetWaitNext());
+          thread->SetWaitNext(nullptr);
+          return true;
+        }
+        t = t->GetWaitNext();
+      }
     }
-    t = t->GetWaitNext();
+    return false;
+  };
+  if (remove(wait_set_)) {
+    return;
   }
+  remove(wake_set_);
 }
 
 void Monitor::SetObject(mirror::Object* object) {
@@ -699,33 +707,102 @@ void Monitor::FailedUnlock(mirror::Object* o,
 bool Monitor::Unlock(Thread* self) {
   DCHECK(self != nullptr);
   uint32_t owner_thread_id = 0u;
-  {
-    MutexLock mu(self, monitor_lock_);
-    Thread* owner = owner_;
-    if (owner != nullptr) {
-      owner_thread_id = owner->GetThreadId();
-    }
-    if (owner == self) {
-      // We own the monitor, so nobody else can be in here.
-      AtraceMonitorUnlock();
-      if (lock_count_ == 0) {
-        owner_ = nullptr;
-        locking_method_ = nullptr;
-        locking_dex_pc_ = 0;
-        // Wake a contender.
-        monitor_contenders_.Signal(self);
-      } else {
-        --lock_count_;
-      }
+  DCHECK(!monitor_lock_.IsExclusiveHeld(self));
+  monitor_lock_.Lock(self);
+  Thread* owner = owner_;
+  if (owner != nullptr) {
+    owner_thread_id = owner->GetThreadId();
+  }
+  if (owner == self) {
+    // We own the monitor, so nobody else can be in here.
+    AtraceMonitorUnlock();
+    if (lock_count_ == 0) {
+      owner_ = nullptr;
+      locking_method_ = nullptr;
+      locking_dex_pc_ = 0;
+      SignalContendersAndReleaseMonitorLock(self);
+      return true;
+    } else {
+      --lock_count_;
+      monitor_lock_.Unlock(self);
       return true;
     }
   }
   // We don't own this, so we're not allowed to unlock it.
   // The JNI spec says that we should throw IllegalMonitorStateException in this case.
   FailedUnlock(GetObject(), self->GetThreadId(), owner_thread_id, this);
+  monitor_lock_.Unlock(self);
   return false;
 }
 
+void Monitor::SignalContendersAndReleaseMonitorLock(Thread* self) {
+  // We want to signal one thread to wake up, to acquire the monitor that
+  // we are releasing. This could either be a Thread waiting on its own
+  // ConditionVariable, or a thread waiting on monitor_contenders_.
+  while (true) {
+    Thread* thread = wake_set_;
+    if (thread == nullptr) {
+      break;
+    } else if (thread == self) {
+      // In the case of wait(), this will be invoked with self's GetWaitMutex held.
+      // On a second run through this while loop, we will have released and reacquired
+      // monitor_lock_, so it is possible that self has moved into wake_set. Since we
+      // don't want to signal ourselves before waiting or recursively acquire GetWaitMutex,
+      // skip ourself if we encounter it while traversing the wake set.
+      thread = self->GetWaitNext();
+      if (thread == nullptr) {
+        break;
+      }
+      self->SetWaitNext(thread->GetWaitNext());
+    } else {
+      wake_set_ = thread->GetWaitNext();
+    }
+    thread->SetWaitNext(nullptr);
+
+    // Release the lock, so that a potentially awakened thread will not
+    // immediately contend on it.
+    monitor_lock_.Unlock(self);
+    // Check to see if the thread is still waiting.
+    {
+      // In the case of wait(), we'll be acquiring another thread's GetWaitMutex with
+      // self's GetWaitMutex held. This does not risk deadlock, because we only acquire this lock
+      // for threads in the wake_set_. A thread can only enter wake_set_ from Notify or NotifyAll,
+      // and those acquire each thread's GetWaitMutex before moving them. Thus, the threads whose
+      // wait mutexes we acquire here must have already been released from wait(), so there is no
+      // risk of the following lock ordering leading to deadlock:
+      // Thread 1 waits
+      // Thread 2 waits
+      // While threads 1 and 2 have released both the monitor and the monitor_lock_, thread 3 calls
+      // notify() to wake them both up.
+      // Thread 1 enters this block, and attempts to acquire Thread 2's GetWaitMutex to wake it
+      // Thread 2 enters this block, and attempts to acquire Thread 1's GetWaitMutex to wake it
+      //
+      // Thanks to the lock checking in Notify and NotifyAll, no thread is observable in wake_set_
+      // unless that thread has actually started waiting (and therefore will not subsequently
+      // acquire another thread's GetWaitMutex while holding its own).
+      MutexLock wait_mu(self, *thread->GetWaitMutex());
+      if (thread->GetWaitMonitor() != nullptr) {
+        thread->GetWaitConditionVariable()->Signal(self);
+        return;
+      }
+    }
+    // Reacquire the lock for the next iteration
+    monitor_lock_.Lock(self);
+    // We had to reacquire the lock so that we can wake a contender, or look
+    // for another notified waiter thread, but if someone else has already acquired our
+    // monitor, there's no need to wake anybody else as they'll just contend
+    // with the current owner.
+    if (owner_ != nullptr) {
+      monitor_lock_.Unlock(self);
+      return;
+    }
+  }
+  // If we didn't wake any threads that were originally waiting on us,
+  // wake a contender.
+  monitor_contenders_.Signal(self);
+  monitor_lock_.Unlock(self);
+}
+
 void Monitor::Wait(Thread* self, int64_t ms, int32_t ns,
                    bool interruptShouldThrow, ThreadState why) {
   DCHECK(self != nullptr);
@@ -755,17 +832,9 @@ void Monitor::Wait(Thread* self, int64_t ms, int32_t ns,
   }
 
   /*
-   * Add ourselves to the set of threads waiting on this monitor, and
-   * release our hold.  We need to let it go even if we're a few levels
+   * Release our hold - we need to let it go even if we're a few levels
    * deep in a recursive lock, and we need to restore that later.
-   *
-   * We append to the wait set ahead of clearing the count and owner
-   * fields so the subroutine can check that the calling thread owns
-   * the monitor.  Aside from that, the order of member updates is
-   * not order sensitive as we hold the pthread mutex.
    */
-  AppendToWaitSet(self);
-  ++num_waiters_;
   int prev_lock_count = lock_count_;
   lock_count_ = 0;
   owner_ = nullptr;
@@ -790,6 +859,17 @@ void Monitor::Wait(Thread* self, int64_t ms, int32_t ns,
     // Pseudo-atomically wait on self's wait_cond_ and release the monitor lock.
     MutexLock mu(self, *self->GetWaitMutex());
 
+    /*
+     * Add ourselves to the set of threads waiting on this monitor.
+     * It's important that we are only added to the wait set after
+     * acquiring our GetWaitMutex, so that calls to Notify() that occur after we
+     * have released monitor_lock_ will not move us from wait_set_ to wake_set_
+     * until we've signalled contenders on this monitor.
+     */
+    AppendToWaitSet(self);
+    ++num_waiters_;
+
+
     // Set wait_monitor_ to the monitor object we will be waiting on. When wait_monitor_ is
     // non-null a notifying or interrupting thread must signal the thread's wait_cond_ to wake it
     // up.
@@ -797,8 +877,7 @@ void Monitor::Wait(Thread* self, int64_t ms, int32_t ns,
     self->SetWaitMonitor(this);
 
     // Release the monitor lock.
-    monitor_contenders_.Signal(self);
-    monitor_lock_.Unlock(self);
+    SignalContendersAndReleaseMonitorLock(self);
 
     // Handle the case where the thread was interrupted before we called wait().
     if (self->IsInterrupted()) {
@@ -874,18 +953,16 @@ void Monitor::Notify(Thread* self) {
     ThrowIllegalMonitorStateExceptionF("object not locked by thread before notify()");
     return;
   }
-  // Signal the first waiting thread in the wait set.
-  while (wait_set_ != nullptr) {
-    Thread* thread = wait_set_;
-    wait_set_ = thread->GetWaitNext();
-    thread->SetWaitNext(nullptr);
-
-    // Check to see if the thread is still waiting.
-    MutexLock wait_mu(self, *thread->GetWaitMutex());
-    if (thread->GetWaitMonitor() != nullptr) {
-      thread->GetWaitConditionVariable()->Signal(self);
-      return;
-    }
+  // Move one thread from waiters to wake set
+  Thread* to_move = wait_set_;
+  if (to_move != nullptr) {
+    // Acquiring the thread's wait mutex before moving it prevents us from moving a thread that
+    // has released monitor_lock_ in wait() but not yet tried to wake an entry in wake_set_. See
+    // comments in SignalContendersAndReleaseMonitorLock.
+    MutexLock wait(self, *to_move->GetWaitMutex());
+    wait_set_ = to_move->GetWaitNext();
+    to_move->SetWaitNext(wake_set_);
+    wake_set_ = to_move;
   }
 }
 
@@ -897,12 +974,17 @@ void Monitor::NotifyAll(Thread* self) {
     ThrowIllegalMonitorStateExceptionF("object not locked by thread before notifyAll()");
     return;
   }
-  // Signal all threads in the wait set.
+
+  // Move all threads from waiters to wake set
   while (wait_set_ != nullptr) {
-    Thread* thread = wait_set_;
-    wait_set_ = thread->GetWaitNext();
-    thread->SetWaitNext(nullptr);
-    thread->Notify();
+    Thread* to_move = wait_set_;
+    // Acquiring the thread's wait mutex before moving it prevents us from moving a thread that
+    // has released monitor_lock_ in wait() but not yet tried to wake an entry in wake_set_. See
+    // comments in SignalContendersAndReleaseMonitorLock.
+    MutexLock wait(self, *to_move->GetWaitMutex());
+    wait_set_ = to_move->GetWaitNext();
+    to_move->SetWaitNext(wake_set_);
+    wake_set_ = to_move;
   }
 }