runtime/monitor.cc

   1 /*
   2  * Copyright (C) 2008 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include "monitor.h"
  18
  19 #include <vector>
  20
  21 #include "art_method-inl.h"
  22 #include "base/mutex.h"
  23 #include "base/stl_util.h"
  24 #include "base/systrace.h"
  25 #include "base/time_utils.h"
  26 #include "class_linker.h"
  27 #include "dex_file-inl.h"
  28 #include "dex_instruction-inl.h"
  29 #include "lock_word-inl.h"
  30 #include "mirror/class-inl.h"
  31 #include "mirror/object-inl.h"
  32 #include "mirror/object_array-inl.h"
  33 #include "scoped_thread_state_change.h"
  34 #include "thread.h"
  35 #include "thread_list.h"
  36 #include "verifier/method_verifier.h"
  37 #include "well_known_classes.h"
  38
  39 namespace art {
  40
  41 static constexpr uint64_t kLongWaitMs = 100;
  42
  43 /*
  44  * Every Object has a monitor associated with it, but not every Object is actually locked.  Even
  45  * the ones that are locked do not need a full-fledged monitor until a) there is actual contention
  46  * or b) wait() is called on the Object.
  47  *
  48  * For Android, we have implemented a scheme similar to the one described in Bacon et al.'s
  49  * "Thin locks: featherweight synchronization for Java" (ACM 1998).  Things are even easier for us,
  50  * though, because we have a full 32 bits to work with.
  51  *
  52  * The two states of an Object's lock are referred to as "thin" and "fat".  A lock may transition
  53  * from the "thin" state to the "fat" state and this transition is referred to as inflation. Once
  54  * a lock has been inflated it remains in the "fat" state indefinitely.
  55  *
  56  * The lock value itself is stored in mirror::Object::monitor_ and the representation is described
  57  * in the LockWord value type.
  58  *
  59  * Monitors provide:
  60  *  - mutually exclusive access to resources
  61  *  - a way for multiple threads to wait for notification
  62  *
  63  * In effect, they fill the role of both mutexes and condition variables.
  64  *
  65  * Only one thread can own the monitor at any time.  There may be several threads waiting on it
  66  * (the wait call unlocks it).  One or more waiting threads may be getting interrupted or notified
  67  * at any given time.
  68  */
  69
  70 uint32_t Monitor::lock_profiling_threshold_ = 0;
  71
  72 void Monitor::Init(uint32_t lock_profiling_threshold) {
  73   lock_profiling_threshold_ = lock_profiling_threshold;
  74 }
  75
  76 Monitor::Monitor(Thread* self, Thread* owner, mirror::Object* obj, int32_t hash_code)
  77     : monitor_lock_("a monitor lock", kMonitorLock),
  78       monitor_contenders_("monitor contenders", monitor_lock_),
  79       num_waiters_(0),
  80       owner_(owner),
  81       lock_count_(0),
  82       obj_(GcRoot<mirror::Object>(obj)),
  83       wait_set_(nullptr),
  84       hash_code_(hash_code),
  85       locking_method_(nullptr),
  86       locking_dex_pc_(0),
  87       monitor_id_(MonitorPool::ComputeMonitorId(this, self)) {
  88 #ifdef __LP64__
  89   DCHECK(false) << "Should not be reached in 64b";
  90   next_free_ = nullptr;
  91 #endif
  92   // We should only inflate a lock if the owner is ourselves or suspended. This avoids a race
  93   // with the owner unlocking the thin-lock.
  94   CHECK(owner == nullptr || owner == self || owner->IsSuspended());
  95   // The identity hash code is set for the life time of the monitor.
  96 }
  97
  98 Monitor::Monitor(Thread* self, Thread* owner, mirror::Object* obj, int32_t hash_code,
  99                  MonitorId id)
 100     : monitor_lock_("a monitor lock", kMonitorLock),
 101       monitor_contenders_("monitor contenders", monitor_lock_),
 102       num_waiters_(0),
 103       owner_(owner),
 104       lock_count_(0),
 105       obj_(GcRoot<mirror::Object>(obj)),
 106       wait_set_(nullptr),
 107       hash_code_(hash_code),
 108       locking_method_(nullptr),
 109       locking_dex_pc_(0),
 110       monitor_id_(id) {
 111 #ifdef __LP64__
 112   next_free_ = nullptr;
 113 #endif
 114   // We should only inflate a lock if the owner is ourselves or suspended. This avoids a race
 115   // with the owner unlocking the thin-lock.
 116   CHECK(owner == nullptr || owner == self || owner->IsSuspended());
 117   // The identity hash code is set for the life time of the monitor.
 118 }
 119
 120 int32_t Monitor::GetHashCode() {
 121   while (!HasHashCode()) {
 122     if (hash_code_.CompareExchangeWeakRelaxed(0, mirror::Object::GenerateIdentityHashCode())) {
 123       break;
 124     }
 125   }
 126   DCHECK(HasHashCode());
 127   return hash_code_.LoadRelaxed();
 128 }
 129
 130 bool Monitor::Install(Thread* self) {
 131   MutexLock mu(self, monitor_lock_);  // Uncontended mutex acquisition as monitor isn't yet public.
 132   CHECK(owner_ == nullptr || owner_ == self || owner_->IsSuspended());
 133   // Propagate the lock state.
 134   LockWord lw(GetObject()->GetLockWord(false));
 135   switch (lw.GetState()) {
 136     case LockWord::kThinLocked: {
 137       CHECK_EQ(owner_->GetThreadId(), lw.ThinLockOwner());
 138       lock_count_ = lw.ThinLockCount();
 139       break;
 140     }
 141     case LockWord::kHashCode: {
 142       CHECK_EQ(hash_code_.LoadRelaxed(), static_cast<int32_t>(lw.GetHashCode()));
 143       break;
 144     }
 145     case LockWord::kFatLocked: {
 146       // The owner_ is suspended but another thread beat us to install a monitor.
 147       return false;
 148     }
 149     case LockWord::kUnlocked: {
 150       LOG(FATAL) << "Inflating unlocked lock word";
 151       break;
 152     }
 153     default: {
 154       LOG(FATAL) << "Invalid monitor state " << lw.GetState();
 155       return false;
 156     }
 157   }
 158   LockWord fat(this, lw.ReadBarrierState());
 159   // Publish the updated lock word, which may race with other threads.
 160   bool success = GetObject()->CasLockWordWeakSequentiallyConsistent(lw, fat);
 161   // Lock profiling.
 162   if (success && owner_ != nullptr && lock_profiling_threshold_ != 0) {
 163     // Do not abort on dex pc errors. This can easily happen when we want to dump a stack trace on
 164     // abort.
 165     locking_method_ = owner_->GetCurrentMethod(&locking_dex_pc_, false);
 166   }
 167   return success;
 168 }
 169
 170 Monitor::~Monitor() {
 171   // Deflated monitors have a null object.
 172 }
 173
 174 void Monitor::AppendToWaitSet(Thread* thread) {
 175   DCHECK(owner_ == Thread::Current());
 176   DCHECK(thread != nullptr);
 177   DCHECK(thread->GetWaitNext() == nullptr) << thread->GetWaitNext();
 178   if (wait_set_ == nullptr) {
 179     wait_set_ = thread;
 180     return;
 181   }
 182
 183   // push_back.
 184   Thread* t = wait_set_;
 185   while (t->GetWaitNext() != nullptr) {
 186     t = t->GetWaitNext();
 187   }
 188   t->SetWaitNext(thread);
 189 }
 190
 191 void Monitor::RemoveFromWaitSet(Thread *thread) {
 192   DCHECK(owner_ == Thread::Current());
 193   DCHECK(thread != nullptr);
 194   if (wait_set_ == nullptr) {
 195     return;
 196   }
 197   if (wait_set_ == thread) {
 198     wait_set_ = thread->GetWaitNext();
 199     thread->SetWaitNext(nullptr);
 200     return;
 201   }
 202
 203   Thread* t = wait_set_;
 204   while (t->GetWaitNext() != nullptr) {
 205     if (t->GetWaitNext() == thread) {
 206       t->SetWaitNext(thread->GetWaitNext());
 207       thread->SetWaitNext(nullptr);
 208       return;
 209     }
 210     t = t->GetWaitNext();
 211   }
 212 }
 213
 214 void Monitor::SetObject(mirror::Object* object) {
 215   obj_ = GcRoot<mirror::Object>(object);
 216 }
 217
 218 // Note: Adapted from CurrentMethodVisitor in thread.cc. We must not resolve here.
 219
 220 struct NthCallerWithDexPcVisitor FINAL : public StackVisitor {
 221   explicit NthCallerWithDexPcVisitor(Thread* thread, size_t frame)
 222       SHARED_REQUIRES(Locks::mutator_lock_)
 223       : StackVisitor(thread, nullptr, StackVisitor::StackWalkKind::kIncludeInlinedFramesNoResolve),
 224         method_(nullptr),
 225         dex_pc_(0),
 226         current_frame_number_(0),
 227         wanted_frame_number_(frame) {}
 228   bool VisitFrame() OVERRIDE SHARED_REQUIRES(Locks::mutator_lock_) {
 229     ArtMethod* m = GetMethod();
 230     if (m == nullptr || m->IsRuntimeMethod()) {
 231       // Runtime method, upcall, or resolution issue. Skip.
 232       return true;
 233     }
 234
 235     // Is this the requested frame?
 236     if (current_frame_number_ == wanted_frame_number_) {
 237       method_ = m;
 238       dex_pc_ = GetDexPc(false /* abort_on_error*/);
 239       return false;
 240     }
 241
 242     // Look for more.
 243     current_frame_number_++;
 244     return true;
 245   }
 246
 247   ArtMethod* method_;
 248   uint32_t dex_pc_;
 249
 250  private:
 251   size_t current_frame_number_;
 252   const size_t wanted_frame_number_;
 253 };
 254
 255 // This function is inlined and just helps to not have the VLOG and ATRACE check at all the
 256 // potential tracing points.
 257 void Monitor::AtraceMonitorLock(Thread* self, mirror::Object* obj, bool is_wait) {
 258   if (UNLIKELY(VLOG_IS_ON(systrace_lock_logging) && ATRACE_ENABLED())) {
 259     AtraceMonitorLockImpl(self, obj, is_wait);
 260   }
 261 }
 262
 263 void Monitor::AtraceMonitorLockImpl(Thread* self, mirror::Object* obj, bool is_wait) {
 264   // Wait() requires a deeper call stack to be useful. Otherwise you'll see "Waiting at
 265   // Object.java". Assume that we'll wait a nontrivial amount, so it's OK to do a longer
 266   // stack walk than if !is_wait.
 267   NthCallerWithDexPcVisitor visitor(self, is_wait ? 1U : 0U);
 268   visitor.WalkStack(false);
 269   const char* prefix = is_wait ? "Waiting on " : "Locking ";
 270
 271   const char* filename;
 272   int32_t line_number;
 273   TranslateLocation(visitor.method_, visitor.dex_pc_, &filename, &line_number);
 274
 275   // It would be nice to have a stable "ID" for the object here. However, the only stable thing
 276   // would be the identity hashcode. But we cannot use IdentityHashcode here: For one, there are
 277   // times when it is unsafe to make that call (see stack dumping for an explanation). More
 278   // importantly, we would have to give up on thin-locking when adding systrace locks, as the
 279   // identity hashcode is stored in the lockword normally (so can't be used with thin-locks).
 280   //
 281   // Because of thin-locks we also cannot use the monitor id (as there is no monitor). Monitor ids
 282   // also do not have to be stable, as the monitor may be deflated.
 283   std::string tmp = StringPrintf("%s %d at %s:%d",
 284       prefix,
 285       (obj == nullptr ? -1 : static_cast<int32_t>(reinterpret_cast<uintptr_t>(obj))),
 286       (filename != nullptr ? filename : "null"),
 287       line_number);
 288   ATRACE_BEGIN(tmp.c_str());
 289 }
 290
 291 void Monitor::AtraceMonitorUnlock() {
 292   if (UNLIKELY(VLOG_IS_ON(systrace_lock_logging))) {
 293     ATRACE_END();
 294   }
 295 }
 296
 297 std::string Monitor::PrettyContentionInfo(const std::string& owner_name,
 298                                           pid_t owner_tid,
 299                                           ArtMethod* owners_method,
 300                                           uint32_t owners_dex_pc,
 301                                           size_t num_waiters) {
 302   const char* owners_filename;
 303   int32_t owners_line_number;
 304   if (owners_method != nullptr) {
 305     TranslateLocation(owners_method, owners_dex_pc, &owners_filename, &owners_line_number);
 306   }
 307   std::ostringstream oss;
 308   oss << "monitor contention with owner " << owner_name << " (" << owner_tid << ")";
 309   if (owners_method != nullptr) {
 310     oss << " at " << PrettyMethod(owners_method);
 311     oss << "(" << owners_filename << ":" << owners_line_number << ")";
 312   }
 313   oss << " waiters=" << num_waiters;
 314   return oss.str();
 315 }
 316
 317 bool Monitor::TryLockLocked(Thread* self) {
 318   if (owner_ == nullptr) {  // Unowned.
 319     owner_ = self;
 320     CHECK_EQ(lock_count_, 0);
 321     // When debugging, save the current monitor holder for future
 322     // acquisition failures to use in sampled logging.
 323     if (lock_profiling_threshold_ != 0) {
 324       locking_method_ = self->GetCurrentMethod(&locking_dex_pc_);
 325     }
 326   } else if (owner_ == self) {  // Recursive.
 327     lock_count_++;
 328   } else {
 329     return false;
 330   }
 331   AtraceMonitorLock(self, GetObject(), false /* is_wait */);
 332   return true;
 333 }
 334
 335 bool Monitor::TryLock(Thread* self) {
 336   MutexLock mu(self, monitor_lock_);
 337   return TryLockLocked(self);
 338 }
 339
 340 void Monitor::Lock(Thread* self) {
 341   MutexLock mu(self, monitor_lock_);
 342   while (true) {
 343     if (TryLockLocked(self)) {
 344       return;
 345     }
 346     // Contended.
 347     const bool log_contention = (lock_profiling_threshold_ != 0);
 348     uint64_t wait_start_ms = log_contention ? MilliTime() : 0;
 349     ArtMethod* owners_method = locking_method_;
 350     uint32_t owners_dex_pc = locking_dex_pc_;
 351     // Do this before releasing the lock so that we don't get deflated.
 352     size_t num_waiters = num_waiters_;
 353     ++num_waiters_;
 354     monitor_lock_.Unlock(self);  // Let go of locks in order.
 355     self->SetMonitorEnterObject(GetObject());
 356     {
 357       uint32_t original_owner_thread_id = 0u;
 358       ScopedThreadStateChange tsc(self, kBlocked);  // Change to blocked and give up mutator_lock_.
 359       {
 360         // Reacquire monitor_lock_ without mutator_lock_ for Wait.
 361         MutexLock mu2(self, monitor_lock_);
 362         if (owner_ != nullptr) {  // Did the owner_ give the lock up?
 363           original_owner_thread_id = owner_->GetThreadId();
 364           if (ATRACE_ENABLED()) {
 365             std::ostringstream oss;
 366             std::string name;
 367             owner_->GetThreadName(name);
 368             oss << PrettyContentionInfo(name,
 369                                         owner_->GetTid(),
 370                                         owners_method,
 371                                         owners_dex_pc,
 372                                         num_waiters);
 373             // Add info for contending thread.
 374             uint32_t pc;
 375             ArtMethod* m = self->GetCurrentMethod(&pc);
 376             const char* filename;
 377             int32_t line_number;
 378             TranslateLocation(m, pc, &filename, &line_number);
 379             oss << " blocking from "
 380                 << PrettyMethod(m) << "(" << (filename != nullptr ? filename : "null") << ":"
 381                 << line_number << ")";
 382             ATRACE_BEGIN(oss.str().c_str());
 383           }
 384           monitor_contenders_.Wait(self);  // Still contended so wait.
 385         }
 386       }
 387       if (original_owner_thread_id != 0u) {
 388         // Woken from contention.
 389         if (log_contention) {
 390           uint32_t original_owner_tid = 0;
 391           std::string original_owner_name;
 392           {
 393             MutexLock mu2(Thread::Current(), *Locks::thread_list_lock_);
 394             // Re-find the owner in case the thread got killed.
 395             Thread* original_owner = Runtime::Current()->GetThreadList()->FindThreadByThreadId(
 396                 original_owner_thread_id);
 397             // Do not do any work that requires the mutator lock.
 398             if (original_owner != nullptr) {
 399               original_owner_tid = original_owner->GetTid();
 400               original_owner->GetThreadName(original_owner_name);
 401             }
 402           }
 403
 404           if (original_owner_tid != 0u) {
 405             uint64_t wait_ms = MilliTime() - wait_start_ms;
 406             uint32_t sample_percent;
 407             if (wait_ms >= lock_profiling_threshold_) {
 408               sample_percent = 100;
 409             } else {
 410               sample_percent = 100 * wait_ms / lock_profiling_threshold_;
 411             }
 412             if (sample_percent != 0 && (static_cast<uint32_t>(rand() % 100) < sample_percent)) {
 413               if (wait_ms > kLongWaitMs && owners_method != nullptr) {
 414                 uint32_t pc;
 415                 ArtMethod* m = self->GetCurrentMethod(&pc);
 416                 // TODO: We should maybe check that original_owner is still a live thread.
 417                 LOG(WARNING) << "Long "
 418                     << PrettyContentionInfo(original_owner_name,
 419                                             original_owner_tid,
 420                                             owners_method,
 421                                             owners_dex_pc,
 422                                             num_waiters)
 423                     << " in " << PrettyMethod(m) << " for " << PrettyDuration(MsToNs(wait_ms));
 424               }
 425               const char* owners_filename;
 426               int32_t owners_line_number;
 427               TranslateLocation(owners_method,
 428                                 owners_dex_pc,
 429                                 &owners_filename,
 430                                 &owners_line_number);
 431               LogContentionEvent(self,
 432                                  wait_ms,
 433                                  sample_percent,
 434                                  owners_filename,
 435                                  owners_line_number);
 436             }
 437           }
 438         }
 439         ATRACE_END();
 440       }
 441     }
 442     self->SetMonitorEnterObject(nullptr);
 443     monitor_lock_.Lock(self);  // Reacquire locks in order.
 444     --num_waiters_;
 445   }
 446 }
 447
 448 static void ThrowIllegalMonitorStateExceptionF(const char* fmt, ...)
 449                                               __attribute__((format(printf, 1, 2)));
 450
 451 static void ThrowIllegalMonitorStateExceptionF(const char* fmt, ...)
 452     SHARED_REQUIRES(Locks::mutator_lock_) {
 453   va_list args;
 454   va_start(args, fmt);
 455   Thread* self = Thread::Current();
 456   self->ThrowNewExceptionV("Ljava/lang/IllegalMonitorStateException;", fmt, args);
 457   if (!Runtime::Current()->IsStarted() || VLOG_IS_ON(monitor)) {
 458     std::ostringstream ss;
 459     self->Dump(ss);
 460     LOG(Runtime::Current()->IsStarted() ? INFO : ERROR)
 461         << self->GetException()->Dump() << "\n" << ss.str();
 462   }
 463   va_end(args);
 464 }
 465
 466 static std::string ThreadToString(Thread* thread) {
 467   if (thread == nullptr) {
 468     return "nullptr";
 469   }
 470   std::ostringstream oss;
 471   // TODO: alternatively, we could just return the thread's name.
 472   oss << *thread;
 473   return oss.str();
 474 }
 475
 476 void Monitor::FailedUnlock(mirror::Object* o,
 477                            uint32_t expected_owner_thread_id,
 478                            uint32_t found_owner_thread_id,
 479                            Monitor* monitor) {
 480   // Acquire thread list lock so threads won't disappear from under us.
 481   std::string current_owner_string;
 482   std::string expected_owner_string;
 483   std::string found_owner_string;
 484   uint32_t current_owner_thread_id = 0u;
 485   {
 486     MutexLock mu(Thread::Current(), *Locks::thread_list_lock_);
 487     ThreadList* const thread_list = Runtime::Current()->GetThreadList();
 488     Thread* expected_owner = thread_list->FindThreadByThreadId(expected_owner_thread_id);
 489     Thread* found_owner = thread_list->FindThreadByThreadId(found_owner_thread_id);
 490
 491     // Re-read owner now that we hold lock.
 492     Thread* current_owner = (monitor != nullptr) ? monitor->GetOwner() : nullptr;
 493     if (current_owner != nullptr) {
 494       current_owner_thread_id = current_owner->GetThreadId();
 495     }
 496     // Get short descriptions of the threads involved.
 497     current_owner_string = ThreadToString(current_owner);
 498     expected_owner_string = expected_owner != nullptr ? ThreadToString(expected_owner) : "unnamed";
 499     found_owner_string = found_owner != nullptr ? ThreadToString(found_owner) : "unnamed";
 500   }
 501
 502   if (current_owner_thread_id == 0u) {
 503     if (found_owner_thread_id == 0u) {
 504       ThrowIllegalMonitorStateExceptionF("unlock of unowned monitor on object of type '%s'"
 505                                          " on thread '%s'",
 506                                          PrettyTypeOf(o).c_str(),
 507                                          expected_owner_string.c_str());
 508     } else {
 509       // Race: the original read found an owner but now there is none
 510       ThrowIllegalMonitorStateExceptionF("unlock of monitor owned by '%s' on object of type '%s'"
 511                                          " (where now the monitor appears unowned) on thread '%s'",
 512                                          found_owner_string.c_str(),
 513                                          PrettyTypeOf(o).c_str(),
 514                                          expected_owner_string.c_str());
 515     }
 516   } else {
 517     if (found_owner_thread_id == 0u) {
 518       // Race: originally there was no owner, there is now
 519       ThrowIllegalMonitorStateExceptionF("unlock of monitor owned by '%s' on object of type '%s'"
 520                                          " (originally believed to be unowned) on thread '%s'",
 521                                          current_owner_string.c_str(),
 522                                          PrettyTypeOf(o).c_str(),
 523                                          expected_owner_string.c_str());
 524     } else {
 525       if (found_owner_thread_id != current_owner_thread_id) {
 526         // Race: originally found and current owner have changed
 527         ThrowIllegalMonitorStateExceptionF("unlock of monitor originally owned by '%s' (now"
 528                                            " owned by '%s') on object of type '%s' on thread '%s'",
 529                                            found_owner_string.c_str(),
 530                                            current_owner_string.c_str(),
 531                                            PrettyTypeOf(o).c_str(),
 532                                            expected_owner_string.c_str());
 533       } else {
 534         ThrowIllegalMonitorStateExceptionF("unlock of monitor owned by '%s' on object of type '%s'"
 535                                            " on thread '%s",
 536                                            current_owner_string.c_str(),
 537                                            PrettyTypeOf(o).c_str(),
 538                                            expected_owner_string.c_str());
 539       }
 540     }
 541   }
 542 }
 543
 544 bool Monitor::Unlock(Thread* self) {
 545   DCHECK(self != nullptr);
 546   uint32_t owner_thread_id = 0u;
 547   {
 548     MutexLock mu(self, monitor_lock_);
 549     Thread* owner = owner_;
 550     if (owner != nullptr) {
 551       owner_thread_id = owner->GetThreadId();
 552     }
 553     if (owner == self) {
 554       // We own the monitor, so nobody else can be in here.
 555       AtraceMonitorUnlock();
 556       if (lock_count_ == 0) {
 557         owner_ = nullptr;
 558         locking_method_ = nullptr;
 559         locking_dex_pc_ = 0;
 560         // Wake a contender.
 561         monitor_contenders_.Signal(self);
 562       } else {
 563         --lock_count_;
 564       }
 565       return true;
 566     }
 567   }
 568   // We don't own this, so we're not allowed to unlock it.
 569   // The JNI spec says that we should throw IllegalMonitorStateException in this case.
 570   FailedUnlock(GetObject(), self->GetThreadId(), owner_thread_id, this);
 571   return false;
 572 }
 573
 574 void Monitor::Wait(Thread* self, int64_t ms, int32_t ns,
 575                    bool interruptShouldThrow, ThreadState why) {
 576   DCHECK(self != nullptr);
 577   DCHECK(why == kTimedWaiting || why == kWaiting || why == kSleeping);
 578
 579   monitor_lock_.Lock(self);
 580
 581   // Make sure that we hold the lock.
 582   if (owner_ != self) {
 583     monitor_lock_.Unlock(self);
 584     ThrowIllegalMonitorStateExceptionF("object not locked by thread before wait()");
 585     return;
 586   }
 587
 588   // We need to turn a zero-length timed wait into a regular wait because
 589   // Object.wait(0, 0) is defined as Object.wait(0), which is defined as Object.wait().
 590   if (why == kTimedWaiting && (ms == 0 && ns == 0)) {
 591     why = kWaiting;
 592   }
 593
 594   // Enforce the timeout range.
 595   if (ms < 0 || ns < 0 || ns > 999999) {
 596     monitor_lock_.Unlock(self);
 597     self->ThrowNewExceptionF("Ljava/lang/IllegalArgumentException;",
 598                              "timeout arguments out of range: ms=%" PRId64 " ns=%d", ms, ns);
 599     return;
 600   }
 601
 602   /*
 603    * Add ourselves to the set of threads waiting on this monitor, and
 604    * release our hold.  We need to let it go even if we're a few levels
 605    * deep in a recursive lock, and we need to restore that later.
 606    *
 607    * We append to the wait set ahead of clearing the count and owner
 608    * fields so the subroutine can check that the calling thread owns
 609    * the monitor.  Aside from that, the order of member updates is
 610    * not order sensitive as we hold the pthread mutex.
 611    */
 612   AppendToWaitSet(self);
 613   ++num_waiters_;
 614   int prev_lock_count = lock_count_;
 615   lock_count_ = 0;
 616   owner_ = nullptr;
 617   ArtMethod* saved_method = locking_method_;
 618   locking_method_ = nullptr;
 619   uintptr_t saved_dex_pc = locking_dex_pc_;
 620   locking_dex_pc_ = 0;
 621
 622   AtraceMonitorUnlock();  // For the implict Unlock() just above. This will only end the deepest
 623                           // nesting, but that is enough for the visualization, and corresponds to
 624                           // the single Lock() we do afterwards.
 625   AtraceMonitorLock(self, GetObject(), true /* is_wait */);
 626
 627   bool was_interrupted = false;
 628   {
 629     // Update thread state. If the GC wakes up, it'll ignore us, knowing
 630     // that we won't touch any references in this state, and we'll check
 631     // our suspend mode before we transition out.
 632     ScopedThreadSuspension sts(self, why);
 633
 634     // Pseudo-atomically wait on self's wait_cond_ and release the monitor lock.
 635     MutexLock mu(self, *self->GetWaitMutex());
 636
 637     // Set wait_monitor_ to the monitor object we will be waiting on. When wait_monitor_ is
 638     // non-null a notifying or interrupting thread must signal the thread's wait_cond_ to wake it
 639     // up.
 640     DCHECK(self->GetWaitMonitor() == nullptr);
 641     self->SetWaitMonitor(this);
 642
 643     // Release the monitor lock.
 644     monitor_contenders_.Signal(self);
 645     monitor_lock_.Unlock(self);
 646
 647     // Handle the case where the thread was interrupted before we called wait().
 648     if (self->IsInterruptedLocked()) {
 649       was_interrupted = true;
 650     } else {
 651       // Wait for a notification or a timeout to occur.
 652       if (why == kWaiting) {
 653         self->GetWaitConditionVariable()->Wait(self);
 654       } else {
 655         DCHECK(why == kTimedWaiting || why == kSleeping) << why;
 656         self->GetWaitConditionVariable()->TimedWait(self, ms, ns);
 657       }
 658       was_interrupted = self->IsInterruptedLocked();
 659     }
 660   }
 661
 662   {
 663     // We reset the thread's wait_monitor_ field after transitioning back to runnable so
 664     // that a thread in a waiting/sleeping state has a non-null wait_monitor_ for debugging
 665     // and diagnostic purposes. (If you reset this earlier, stack dumps will claim that threads
 666     // are waiting on "null".)
 667     MutexLock mu(self, *self->GetWaitMutex());
 668     DCHECK(self->GetWaitMonitor() != nullptr);
 669     self->SetWaitMonitor(nullptr);
 670   }
 671
 672   // Allocate the interrupted exception not holding the monitor lock since it may cause a GC.
 673   // If the GC requires acquiring the monitor for enqueuing cleared references, this would
 674   // cause a deadlock if the monitor is held.
 675   if (was_interrupted && interruptShouldThrow) {
 676     /*
 677      * We were interrupted while waiting, or somebody interrupted an
 678      * un-interruptible thread earlier and we're bailing out immediately.
 679      *
 680      * The doc sayeth: "The interrupted status of the current thread is
 681      * cleared when this exception is thrown."
 682      */
 683     {
 684       MutexLock mu(self, *self->GetWaitMutex());
 685       self->SetInterruptedLocked(false);
 686     }
 687     self->ThrowNewException("Ljava/lang/InterruptedException;", nullptr);
 688   }
 689
 690   AtraceMonitorUnlock();  // End Wait().
 691
 692   // Re-acquire the monitor and lock.
 693   Lock(self);
 694   monitor_lock_.Lock(self);
 695   self->GetWaitMutex()->AssertNotHeld(self);
 696
 697   /*
 698    * We remove our thread from wait set after restoring the count
 699    * and owner fields so the subroutine can check that the calling
 700    * thread owns the monitor. Aside from that, the order of member
 701    * updates is not order sensitive as we hold the pthread mutex.
 702    */
 703   owner_ = self;
 704   lock_count_ = prev_lock_count;
 705   locking_method_ = saved_method;
 706   locking_dex_pc_ = saved_dex_pc;
 707   --num_waiters_;
 708   RemoveFromWaitSet(self);
 709
 710   monitor_lock_.Unlock(self);
 711 }
 712
 713 void Monitor::Notify(Thread* self) {
 714   DCHECK(self != nullptr);
 715   MutexLock mu(self, monitor_lock_);
 716   // Make sure that we hold the lock.
 717   if (owner_ != self) {
 718     ThrowIllegalMonitorStateExceptionF("object not locked by thread before notify()");
 719     return;
 720   }
 721   // Signal the first waiting thread in the wait set.
 722   while (wait_set_ != nullptr) {
 723     Thread* thread = wait_set_;
 724     wait_set_ = thread->GetWaitNext();
 725     thread->SetWaitNext(nullptr);
 726
 727     // Check to see if the thread is still waiting.
 728     MutexLock wait_mu(self, *thread->GetWaitMutex());
 729     if (thread->GetWaitMonitor() != nullptr) {
 730       thread->GetWaitConditionVariable()->Signal(self);
 731       return;
 732     }
 733   }
 734 }
 735
 736 void Monitor::NotifyAll(Thread* self) {
 737   DCHECK(self != nullptr);
 738   MutexLock mu(self, monitor_lock_);
 739   // Make sure that we hold the lock.
 740   if (owner_ != self) {
 741     ThrowIllegalMonitorStateExceptionF("object not locked by thread before notifyAll()");
 742     return;
 743   }
 744   // Signal all threads in the wait set.
 745   while (wait_set_ != nullptr) {
 746     Thread* thread = wait_set_;
 747     wait_set_ = thread->GetWaitNext();
 748     thread->SetWaitNext(nullptr);
 749     thread->Notify();
 750   }
 751 }
 752
 753 bool Monitor::Deflate(Thread* self, mirror::Object* obj) {
 754   DCHECK(obj != nullptr);
 755   // Don't need volatile since we only deflate with mutators suspended.
 756   LockWord lw(obj->GetLockWord(false));
 757   // If the lock isn't an inflated monitor, then we don't need to deflate anything.
 758   if (lw.GetState() == LockWord::kFatLocked) {
 759     Monitor* monitor = lw.FatLockMonitor();
 760     DCHECK(monitor != nullptr);
 761     MutexLock mu(self, monitor->monitor_lock_);
 762     // Can't deflate if we have anybody waiting on the CV.
 763     if (monitor->num_waiters_ > 0) {
 764       return false;
 765     }
 766     Thread* owner = monitor->owner_;
 767     if (owner != nullptr) {
 768       // Can't deflate if we are locked and have a hash code.
 769       if (monitor->HasHashCode()) {
 770         return false;
 771       }
 772       // Can't deflate if our lock count is too high.
 773       if (monitor->lock_count_ > LockWord::kThinLockMaxCount) {
 774         return false;
 775       }
 776       // Deflate to a thin lock.
 777       LockWord new_lw = LockWord::FromThinLockId(owner->GetThreadId(), monitor->lock_count_,
 778                                                  lw.ReadBarrierState());
 779       // Assume no concurrent read barrier state changes as mutators are suspended.
 780       obj->SetLockWord(new_lw, false);
 781       VLOG(monitor) << "Deflated " << obj << " to thin lock " << owner->GetTid() << " / "
 782           << monitor->lock_count_;
 783     } else if (monitor->HasHashCode()) {
 784       LockWord new_lw = LockWord::FromHashCode(monitor->GetHashCode(), lw.ReadBarrierState());
 785       // Assume no concurrent read barrier state changes as mutators are suspended.
 786       obj->SetLockWord(new_lw, false);
 787       VLOG(monitor) << "Deflated " << obj << " to hash monitor " << monitor->GetHashCode();
 788     } else {
 789       // No lock and no hash, just put an empty lock word inside the object.
 790       LockWord new_lw = LockWord::FromDefault(lw.ReadBarrierState());
 791       // Assume no concurrent read barrier state changes as mutators are suspended.
 792       obj->SetLockWord(new_lw, false);
 793       VLOG(monitor) << "Deflated" << obj << " to empty lock word";
 794     }
 795     // The monitor is deflated, mark the object as null so that we know to delete it during the
 796     // next GC.
 797     monitor->obj_ = GcRoot<mirror::Object>(nullptr);
 798   }
 799   return true;
 800 }
 801
 802 void Monitor::Inflate(Thread* self, Thread* owner, mirror::Object* obj, int32_t hash_code) {
 803   DCHECK(self != nullptr);
 804   DCHECK(obj != nullptr);
 805   // Allocate and acquire a new monitor.
 806   Monitor* m = MonitorPool::CreateMonitor(self, owner, obj, hash_code);
 807   DCHECK(m != nullptr);
 808   if (m->Install(self)) {
 809     if (owner != nullptr) {
 810       VLOG(monitor) << "monitor: thread" << owner->GetThreadId()
 811           << " created monitor " << m << " for object " << obj;
 812     } else {
 813       VLOG(monitor) << "monitor: Inflate with hashcode " << hash_code
 814           << " created monitor " << m << " for object " << obj;
 815     }
 816     Runtime::Current()->GetMonitorList()->Add(m);
 817     CHECK_EQ(obj->GetLockWord(true).GetState(), LockWord::kFatLocked);
 818   } else {
 819     MonitorPool::ReleaseMonitor(self, m);
 820   }
 821 }
 822
 823 void Monitor::InflateThinLocked(Thread* self, Handle<mirror::Object> obj, LockWord lock_word,
 824                                 uint32_t hash_code) {
 825   DCHECK_EQ(lock_word.GetState(), LockWord::kThinLocked);
 826   uint32_t owner_thread_id = lock_word.ThinLockOwner();
 827   if (owner_thread_id == self->GetThreadId()) {
 828     // We own the monitor, we can easily inflate it.
 829     Inflate(self, self, obj.Get(), hash_code);
 830   } else {
 831     ThreadList* thread_list = Runtime::Current()->GetThreadList();
 832     // Suspend the owner, inflate. First change to blocked and give up mutator_lock_.
 833     self->SetMonitorEnterObject(obj.Get());
 834     bool timed_out;
 835     Thread* owner;
 836     {
 837       ScopedThreadSuspension sts(self, kBlocked);
 838       owner = thread_list->SuspendThreadByThreadId(owner_thread_id, false, &timed_out);
 839     }
 840     if (owner != nullptr) {
 841       // We succeeded in suspending the thread, check the lock's status didn't change.
 842       lock_word = obj->GetLockWord(true);
 843       if (lock_word.GetState() == LockWord::kThinLocked &&
 844           lock_word.ThinLockOwner() == owner_thread_id) {
 845         // Go ahead and inflate the lock.
 846         Inflate(self, owner, obj.Get(), hash_code);
 847       }
 848       thread_list->Resume(owner, false);
 849     }
 850     self->SetMonitorEnterObject(nullptr);
 851   }
 852 }
 853
 854 // Fool annotalysis into thinking that the lock on obj is acquired.
 855 static mirror::Object* FakeLock(mirror::Object* obj)
 856     EXCLUSIVE_LOCK_FUNCTION(obj) NO_THREAD_SAFETY_ANALYSIS {
 857   return obj;
 858 }
 859
 860 // Fool annotalysis into thinking that the lock on obj is release.
 861 static mirror::Object* FakeUnlock(mirror::Object* obj)
 862     UNLOCK_FUNCTION(obj) NO_THREAD_SAFETY_ANALYSIS {
 863   return obj;
 864 }
 865
 866 mirror::Object* Monitor::MonitorEnter(Thread* self, mirror::Object* obj, bool trylock) {
 867   DCHECK(self != nullptr);
 868   DCHECK(obj != nullptr);
 869   self->AssertThreadSuspensionIsAllowable();
 870   obj = FakeLock(obj);
 871   uint32_t thread_id = self->GetThreadId();
 872   size_t contention_count = 0;
 873   StackHandleScope<1> hs(self);
 874   Handle<mirror::Object> h_obj(hs.NewHandle(obj));
 875   while (true) {
 876     LockWord lock_word = h_obj->GetLockWord(true);
 877     switch (lock_word.GetState()) {
 878       case LockWord::kUnlocked: {
 879         LockWord thin_locked(LockWord::FromThinLockId(thread_id, 0, lock_word.ReadBarrierState()));
 880         if (h_obj->CasLockWordWeakSequentiallyConsistent(lock_word, thin_locked)) {
 881           AtraceMonitorLock(self, h_obj.Get(), false /* is_wait */);
 882           // CasLockWord enforces more than the acquire ordering we need here.
 883           return h_obj.Get();  // Success!
 884         }
 885         continue;  // Go again.
 886       }
 887       case LockWord::kThinLocked: {
 888         uint32_t owner_thread_id = lock_word.ThinLockOwner();
 889         if (owner_thread_id == thread_id) {
 890           // We own the lock, increase the recursion count.
 891           uint32_t new_count = lock_word.ThinLockCount() + 1;
 892           if (LIKELY(new_count <= LockWord::kThinLockMaxCount)) {
 893             LockWord thin_locked(LockWord::FromThinLockId(thread_id, new_count,
 894                                                           lock_word.ReadBarrierState()));
 895             if (!kUseReadBarrier) {
 896               h_obj->SetLockWord(thin_locked, true);
 897               AtraceMonitorLock(self, h_obj.Get(), false /* is_wait */);
 898               return h_obj.Get();  // Success!
 899             } else {
 900               // Use CAS to preserve the read barrier state.
 901               if (h_obj->CasLockWordWeakSequentiallyConsistent(lock_word, thin_locked)) {
 902                 AtraceMonitorLock(self, h_obj.Get(), false /* is_wait */);
 903                 return h_obj.Get();  // Success!
 904               }
 905             }
 906             continue;  // Go again.
 907           } else {
 908             // We'd overflow the recursion count, so inflate the monitor.
 909             InflateThinLocked(self, h_obj, lock_word, 0);
 910           }
 911         } else {
 912           if (trylock) {
 913             return nullptr;
 914           }
 915           // Contention.
 916           contention_count++;
 917           Runtime* runtime = Runtime::Current();
 918           if (contention_count <= runtime->GetMaxSpinsBeforeThinkLockInflation()) {
 919             // TODO: Consider switching the thread state to kBlocked when we are yielding.
 920             // Use sched_yield instead of NanoSleep since NanoSleep can wait much longer than the
 921             // parameter you pass in. This can cause thread suspension to take excessively long
 922             // and make long pauses. See b/16307460.
 923             sched_yield();
 924           } else {
 925             contention_count = 0;
 926             InflateThinLocked(self, h_obj, lock_word, 0);
 927           }
 928         }
 929         continue;  // Start from the beginning.
 930       }
 931       case LockWord::kFatLocked: {
 932         Monitor* mon = lock_word.FatLockMonitor();
 933         if (trylock) {
 934           return mon->TryLock(self) ? h_obj.Get() : nullptr;
 935         } else {
 936           mon->Lock(self);
 937           return h_obj.Get();  // Success!
 938         }
 939       }
 940       case LockWord::kHashCode:
 941         // Inflate with the existing hashcode.
 942         Inflate(self, nullptr, h_obj.Get(), lock_word.GetHashCode());
 943         continue;  // Start from the beginning.
 944       default: {
 945         LOG(FATAL) << "Invalid monitor state " << lock_word.GetState();
 946         UNREACHABLE();
 947       }
 948     }
 949   }
 950 }
 951
 952 bool Monitor::MonitorExit(Thread* self, mirror::Object* obj) {
 953   DCHECK(self != nullptr);
 954   DCHECK(obj != nullptr);
 955   self->AssertThreadSuspensionIsAllowable();
 956   obj = FakeUnlock(obj);
 957   StackHandleScope<1> hs(self);
 958   Handle<mirror::Object> h_obj(hs.NewHandle(obj));
 959   while (true) {
 960     LockWord lock_word = obj->GetLockWord(true);
 961     switch (lock_word.GetState()) {
 962       case LockWord::kHashCode:
 963         // Fall-through.
 964       case LockWord::kUnlocked:
 965         FailedUnlock(h_obj.Get(), self->GetThreadId(), 0u, nullptr);
 966         return false;  // Failure.
 967       case LockWord::kThinLocked: {
 968         uint32_t thread_id = self->GetThreadId();
 969         uint32_t owner_thread_id = lock_word.ThinLockOwner();
 970         if (owner_thread_id != thread_id) {
 971           FailedUnlock(h_obj.Get(), thread_id, owner_thread_id, nullptr);
 972           return false;  // Failure.
 973         } else {
 974           // We own the lock, decrease the recursion count.
 975           LockWord new_lw = LockWord::Default();
 976           if (lock_word.ThinLockCount() != 0) {
 977             uint32_t new_count = lock_word.ThinLockCount() - 1;
 978             new_lw = LockWord::FromThinLockId(thread_id, new_count, lock_word.ReadBarrierState());
 979           } else {
 980             new_lw = LockWord::FromDefault(lock_word.ReadBarrierState());
 981           }
 982           if (!kUseReadBarrier) {
 983             DCHECK_EQ(new_lw.ReadBarrierState(), 0U);
 984             h_obj->SetLockWord(new_lw, true);
 985             AtraceMonitorUnlock();
 986             // Success!
 987             return true;
 988           } else {
 989             // Use CAS to preserve the read barrier state.
 990             if (h_obj->CasLockWordWeakSequentiallyConsistent(lock_word, new_lw)) {
 991               AtraceMonitorUnlock();
 992               // Success!
 993               return true;
 994             }
 995           }
 996           continue;  // Go again.
 997         }
 998       }
 999       case LockWord::kFatLocked: {
1000         Monitor* mon = lock_word.FatLockMonitor();
1001         return mon->Unlock(self);
1002       }
1003       default: {
1004         LOG(FATAL) << "Invalid monitor state " << lock_word.GetState();
1005         return false;
1006       }
1007     }
1008   }
1009 }
1010
1011 void Monitor::Wait(Thread* self, mirror::Object *obj, int64_t ms, int32_t ns,
1012                    bool interruptShouldThrow, ThreadState why) {
1013   DCHECK(self != nullptr);
1014   DCHECK(obj != nullptr);
1015   LockWord lock_word = obj->GetLockWord(true);
1016   while (lock_word.GetState() != LockWord::kFatLocked) {
1017     switch (lock_word.GetState()) {
1018       case LockWord::kHashCode:
1019         // Fall-through.
1020       case LockWord::kUnlocked:
1021         ThrowIllegalMonitorStateExceptionF("object not locked by thread before wait()");
1022         return;  // Failure.
1023       case LockWord::kThinLocked: {
1024         uint32_t thread_id = self->GetThreadId();
1025         uint32_t owner_thread_id = lock_word.ThinLockOwner();
1026         if (owner_thread_id != thread_id) {
1027           ThrowIllegalMonitorStateExceptionF("object not locked by thread before wait()");
1028           return;  // Failure.
1029         } else {
1030           // We own the lock, inflate to enqueue ourself on the Monitor. May fail spuriously so
1031           // re-load.
1032           Inflate(self, self, obj, 0);
1033           lock_word = obj->GetLockWord(true);
1034         }
1035         break;
1036       }
1037       case LockWord::kFatLocked:  // Unreachable given the loop condition above. Fall-through.
1038       default: {
1039         LOG(FATAL) << "Invalid monitor state " << lock_word.GetState();
1040         return;
1041       }
1042     }
1043   }
1044   Monitor* mon = lock_word.FatLockMonitor();
1045   mon->Wait(self, ms, ns, interruptShouldThrow, why);
1046 }
1047
1048 void Monitor::DoNotify(Thread* self, mirror::Object* obj, bool notify_all) {
1049   DCHECK(self != nullptr);
1050   DCHECK(obj != nullptr);
1051   LockWord lock_word = obj->GetLockWord(true);
1052   switch (lock_word.GetState()) {
1053     case LockWord::kHashCode:
1054       // Fall-through.
1055     case LockWord::kUnlocked:
1056       ThrowIllegalMonitorStateExceptionF("object not locked by thread before notify()");
1057       return;  // Failure.
1058     case LockWord::kThinLocked: {
1059       uint32_t thread_id = self->GetThreadId();
1060       uint32_t owner_thread_id = lock_word.ThinLockOwner();
1061       if (owner_thread_id != thread_id) {
1062         ThrowIllegalMonitorStateExceptionF("object not locked by thread before notify()");
1063         return;  // Failure.
1064       } else {
1065         // We own the lock but there's no Monitor and therefore no waiters.
1066         return;  // Success.
1067       }
1068     }
1069     case LockWord::kFatLocked: {
1070       Monitor* mon = lock_word.FatLockMonitor();
1071       if (notify_all) {
1072         mon->NotifyAll(self);
1073       } else {
1074         mon->Notify(self);
1075       }
1076       return;  // Success.
1077     }
1078     default: {
1079       LOG(FATAL) << "Invalid monitor state " << lock_word.GetState();
1080       return;
1081     }
1082   }
1083 }
1084
1085 uint32_t Monitor::GetLockOwnerThreadId(mirror::Object* obj) {
1086   DCHECK(obj != nullptr);
1087   LockWord lock_word = obj->GetLockWord(true);
1088   switch (lock_word.GetState()) {
1089     case LockWord::kHashCode:
1090       // Fall-through.
1091     case LockWord::kUnlocked:
1092       return ThreadList::kInvalidThreadId;
1093     case LockWord::kThinLocked:
1094       return lock_word.ThinLockOwner();
1095     case LockWord::kFatLocked: {
1096       Monitor* mon = lock_word.FatLockMonitor();
1097       return mon->GetOwnerThreadId();
1098     }
1099     default: {
1100       LOG(FATAL) << "Unreachable";
1101       UNREACHABLE();
1102     }
1103   }
1104 }
1105
1106 void Monitor::DescribeWait(std::ostream& os, const Thread* thread) {
1107   // Determine the wait message and object we're waiting or blocked upon.
1108   mirror::Object* pretty_object = nullptr;
1109   const char* wait_message = nullptr;
1110   uint32_t lock_owner = ThreadList::kInvalidThreadId;
1111   ThreadState state = thread->GetState();
1112   if (state == kWaiting || state == kTimedWaiting || state == kSleeping) {
1113     wait_message = (state == kSleeping) ? "  - sleeping on " : "  - waiting on ";
1114     Thread* self = Thread::Current();
1115     MutexLock mu(self, *thread->GetWaitMutex());
1116     Monitor* monitor = thread->GetWaitMonitor();
1117     if (monitor != nullptr) {
1118       pretty_object = monitor->GetObject();
1119     }
1120   } else if (state == kBlocked) {
1121     wait_message = "  - waiting to lock ";
1122     pretty_object = thread->GetMonitorEnterObject();
1123     if (pretty_object != nullptr) {
1124       lock_owner = pretty_object->GetLockOwnerThreadId();
1125     }
1126   }
1127
1128   if (wait_message != nullptr) {
1129     if (pretty_object == nullptr) {
1130       os << wait_message << "an unknown object";
1131     } else {
1132       if ((pretty_object->GetLockWord(true).GetState() == LockWord::kThinLocked) &&
1133           Locks::mutator_lock_->IsExclusiveHeld(Thread::Current())) {
1134         // Getting the identity hashcode here would result in lock inflation and suspension of the
1135         // current thread, which isn't safe if this is the only runnable thread.
1136         os << wait_message << StringPrintf("<@addr=0x%" PRIxPTR "> (a %s)",
1137                                            reinterpret_cast<intptr_t>(pretty_object),
1138                                            PrettyTypeOf(pretty_object).c_str());
1139       } else {
1140         // - waiting on <0x6008c468> (a java.lang.Class<java.lang.ref.ReferenceQueue>)
1141         // Call PrettyTypeOf before IdentityHashCode since IdentityHashCode can cause thread
1142         // suspension and move pretty_object.
1143         const std::string pretty_type(PrettyTypeOf(pretty_object));
1144         os << wait_message << StringPrintf("<0x%08x> (a %s)", pretty_object->IdentityHashCode(),
1145                                            pretty_type.c_str());
1146       }
1147     }
1148     // - waiting to lock <0x613f83d8> (a java.lang.Object) held by thread 5
1149     if (lock_owner != ThreadList::kInvalidThreadId) {
1150       os << " held by thread " << lock_owner;
1151     }
1152     os << "\n";
1153   }
1154 }
1155
1156 mirror::Object* Monitor::GetContendedMonitor(Thread* thread) {
1157   // This is used to implement JDWP's ThreadReference.CurrentContendedMonitor, and has a bizarre
1158   // definition of contended that includes a monitor a thread is trying to enter...
1159   mirror::Object* result = thread->GetMonitorEnterObject();
1160   if (result == nullptr) {
1161     // ...but also a monitor that the thread is waiting on.
1162     MutexLock mu(Thread::Current(), *thread->GetWaitMutex());
1163     Monitor* monitor = thread->GetWaitMonitor();
1164     if (monitor != nullptr) {
1165       result = monitor->GetObject();
1166     }
1167   }
1168   return result;
1169 }
1170
1171 void Monitor::VisitLocks(StackVisitor* stack_visitor, void (*callback)(mirror::Object*, void*),
1172                          void* callback_context, bool abort_on_failure) {
1173   ArtMethod* m = stack_visitor->GetMethod();
1174   CHECK(m != nullptr);
1175
1176   // Native methods are an easy special case.
1177   // TODO: use the JNI implementation's table of explicit MonitorEnter calls and dump those too.
1178   if (m->IsNative()) {
1179     if (m->IsSynchronized()) {
1180       mirror::Object* jni_this =
1181           stack_visitor->GetCurrentHandleScope(sizeof(void*))->GetReference(0);
1182       callback(jni_this, callback_context);
1183     }
1184     return;
1185   }
1186
1187   // Proxy methods should not be synchronized.
1188   if (m->IsProxyMethod()) {
1189     CHECK(!m->IsSynchronized());
1190     return;
1191   }
1192
1193   // Is there any reason to believe there's any synchronization in this method?
1194   const DexFile::CodeItem* code_item = m->GetCodeItem();
1195   CHECK(code_item != nullptr) << PrettyMethod(m);
1196   if (code_item->tries_size_ == 0) {
1197     return;  // No "tries" implies no synchronization, so no held locks to report.
1198   }
1199
1200   // Get the dex pc. If abort_on_failure is false, GetDexPc will not abort in the case it cannot
1201   // find the dex pc, and instead return kDexNoIndex. Then bail out, as it indicates we have an
1202   // inconsistent stack anyways.
1203   uint32_t dex_pc = stack_visitor->GetDexPc(abort_on_failure);
1204   if (!abort_on_failure && dex_pc == DexFile::kDexNoIndex) {
1205     LOG(ERROR) << "Could not find dex_pc for " << PrettyMethod(m);
1206     return;
1207   }
1208
1209   // Ask the verifier for the dex pcs of all the monitor-enter instructions corresponding to
1210   // the locks held in this stack frame.
1211   std::vector<uint32_t> monitor_enter_dex_pcs;
1212   verifier::MethodVerifier::FindLocksAtDexPc(m, dex_pc, &monitor_enter_dex_pcs);
1213   for (uint32_t monitor_dex_pc : monitor_enter_dex_pcs) {
1214     // The verifier works in terms of the dex pcs of the monitor-enter instructions.
1215     // We want the registers used by those instructions (so we can read the values out of them).
1216     const Instruction* monitor_enter_instruction =
1217         Instruction::At(&code_item->insns_[monitor_dex_pc]);
1218
1219     // Quick sanity check.
1220     CHECK_EQ(monitor_enter_instruction->Opcode(), Instruction::MONITOR_ENTER)
1221       << "expected monitor-enter @" << monitor_dex_pc << "; was "
1222       << reinterpret_cast<const void*>(monitor_enter_instruction);
1223
1224     uint16_t monitor_register = monitor_enter_instruction->VRegA();
1225     uint32_t value;
1226     bool success = stack_visitor->GetVReg(m, monitor_register, kReferenceVReg, &value);
1227     CHECK(success) << "Failed to read v" << monitor_register << " of kind "
1228                    << kReferenceVReg << " in method " << PrettyMethod(m);
1229     mirror::Object* o = reinterpret_cast<mirror::Object*>(value);
1230     callback(o, callback_context);
1231   }
1232 }
1233
1234 bool Monitor::IsValidLockWord(LockWord lock_word) {
1235   switch (lock_word.GetState()) {
1236     case LockWord::kUnlocked:
1237       // Nothing to check.
1238       return true;
1239     case LockWord::kThinLocked:
1240       // Basic sanity check of owner.
1241       return lock_word.ThinLockOwner() != ThreadList::kInvalidThreadId;
1242     case LockWord::kFatLocked: {
1243       // Check the  monitor appears in the monitor list.
1244       Monitor* mon = lock_word.FatLockMonitor();
1245       MonitorList* list = Runtime::Current()->GetMonitorList();
1246       MutexLock mu(Thread::Current(), list->monitor_list_lock_);
1247       for (Monitor* list_mon : list->list_) {
1248         if (mon == list_mon) {
1249           return true;  // Found our monitor.
1250         }
1251       }
1252       return false;  // Fail - unowned monitor in an object.
1253     }
1254     case LockWord::kHashCode:
1255       return true;
1256     default:
1257       LOG(FATAL) << "Unreachable";
1258       UNREACHABLE();
1259   }
1260 }
1261
1262 bool Monitor::IsLocked() SHARED_REQUIRES(Locks::mutator_lock_) {
1263   MutexLock mu(Thread::Current(), monitor_lock_);
1264   return owner_ != nullptr;
1265 }
1266
1267 void Monitor::TranslateLocation(ArtMethod* method,
1268                                 uint32_t dex_pc,
1269                                 const char** source_file,
1270                                 int32_t* line_number) {
1271   // If method is null, location is unknown
1272   if (method == nullptr) {
1273     *source_file = "";
1274     *line_number = 0;
1275     return;
1276   }
1277   *source_file = method->GetDeclaringClassSourceFile();
1278   if (*source_file == nullptr) {
1279     *source_file = "";
1280   }
1281   *line_number = method->GetLineNumFromDexPC(dex_pc);
1282 }
1283
1284 uint32_t Monitor::GetOwnerThreadId() {
1285   MutexLock mu(Thread::Current(), monitor_lock_);
1286   Thread* owner = owner_;
1287   if (owner != nullptr) {
1288     return owner->GetThreadId();
1289   } else {
1290     return ThreadList::kInvalidThreadId;
1291   }
1292 }
1293
1294 MonitorList::MonitorList()
1295     : allow_new_monitors_(true), monitor_list_lock_("MonitorList lock", kMonitorListLock),
1296       monitor_add_condition_("MonitorList disallow condition", monitor_list_lock_) {
1297 }
1298
1299 MonitorList::~MonitorList() {
1300   Thread* self = Thread::Current();
1301   MutexLock mu(self, monitor_list_lock_);
1302   // Release all monitors to the pool.
1303   // TODO: Is it an invariant that *all* open monitors are in the list? Then we could
1304   // clear faster in the pool.
1305   MonitorPool::ReleaseMonitors(self, &list_);
1306 }
1307
1308 void MonitorList::DisallowNewMonitors() {
1309   CHECK(!kUseReadBarrier);
1310   MutexLock mu(Thread::Current(), monitor_list_lock_);
1311   allow_new_monitors_ = false;
1312 }
1313
1314 void MonitorList::AllowNewMonitors() {
1315   CHECK(!kUseReadBarrier);
1316   Thread* self = Thread::Current();
1317   MutexLock mu(self, monitor_list_lock_);
1318   allow_new_monitors_ = true;
1319   monitor_add_condition_.Broadcast(self);
1320 }
1321
1322 void MonitorList::BroadcastForNewMonitors() {
1323   CHECK(kUseReadBarrier);
1324   Thread* self = Thread::Current();
1325   MutexLock mu(self, monitor_list_lock_);
1326   monitor_add_condition_.Broadcast(self);
1327 }
1328
1329 void MonitorList::Add(Monitor* m) {
1330   Thread* self = Thread::Current();
1331   MutexLock mu(self, monitor_list_lock_);
1332   while (UNLIKELY((!kUseReadBarrier && !allow_new_monitors_) ||
1333                   (kUseReadBarrier && !self->GetWeakRefAccessEnabled()))) {
1334     monitor_add_condition_.WaitHoldingLocks(self);
1335   }
1336   list_.push_front(m);
1337 }
1338
1339 void MonitorList::SweepMonitorList(IsMarkedVisitor* visitor) {
1340   Thread* self = Thread::Current();
1341   MutexLock mu(self, monitor_list_lock_);
1342   for (auto it = list_.begin(); it != list_.end(); ) {
1343     Monitor* m = *it;
1344     // Disable the read barrier in GetObject() as this is called by GC.
1345     mirror::Object* obj = m->GetObject<kWithoutReadBarrier>();
1346     // The object of a monitor can be null if we have deflated it.
1347     mirror::Object* new_obj = obj != nullptr ? visitor->IsMarked(obj) : nullptr;
1348     if (new_obj == nullptr) {
1349       VLOG(monitor) << "freeing monitor " << m << " belonging to unmarked object "
1350                     << obj;
1351       MonitorPool::ReleaseMonitor(self, m);
1352       it = list_.erase(it);
1353     } else {
1354       m->SetObject(new_obj);
1355       ++it;
1356     }
1357   }
1358 }
1359
1360 class MonitorDeflateVisitor : public IsMarkedVisitor {
1361  public:
1362   MonitorDeflateVisitor() : self_(Thread::Current()), deflate_count_(0) {}
1363
1364   virtual mirror::Object* IsMarked(mirror::Object* object) OVERRIDE
1365       SHARED_REQUIRES(Locks::mutator_lock_) {
1366     if (Monitor::Deflate(self_, object)) {
1367       DCHECK_NE(object->GetLockWord(true).GetState(), LockWord::kFatLocked);
1368       ++deflate_count_;
1369       // If we deflated, return null so that the monitor gets removed from the array.
1370       return nullptr;
1371     }
1372     return object;  // Monitor was not deflated.
1373   }
1374
1375   Thread* const self_;
1376   size_t deflate_count_;
1377 };
1378
1379 size_t MonitorList::DeflateMonitors() {
1380   MonitorDeflateVisitor visitor;
1381   Locks::mutator_lock_->AssertExclusiveHeld(visitor.self_);
1382   SweepMonitorList(&visitor);
1383   return visitor.deflate_count_;
1384 }
1385
1386 MonitorInfo::MonitorInfo(mirror::Object* obj) : owner_(nullptr), entry_count_(0) {
1387   DCHECK(obj != nullptr);
1388   LockWord lock_word = obj->GetLockWord(true);
1389   switch (lock_word.GetState()) {
1390     case LockWord::kUnlocked:
1391       // Fall-through.
1392     case LockWord::kForwardingAddress:
1393       // Fall-through.
1394     case LockWord::kHashCode:
1395       break;
1396     case LockWord::kThinLocked:
1397       owner_ = Runtime::Current()->GetThreadList()->FindThreadByThreadId(lock_word.ThinLockOwner());
1398       entry_count_ = 1 + lock_word.ThinLockCount();
1399       // Thin locks have no waiters.
1400       break;
1401     case LockWord::kFatLocked: {
1402       Monitor* mon = lock_word.FatLockMonitor();
1403       owner_ = mon->owner_;
1404       entry_count_ = 1 + mon->lock_count_;
1405       for (Thread* waiter = mon->wait_set_; waiter != nullptr; waiter = waiter->GetWaitNext()) {
1406         waiters_.push_back(waiter);
1407       }
1408       break;
1409     }
1410   }
1411 }
1412
1413 }  // namespace art