runtime/base/mutex.cc

   1 /*
   2  * Copyright (C) 2011 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 "mutex.h"
  18
  19 #include <errno.h>
  20 #include <sys/time.h>
  21
  22 #include "atomic.h"
  23 #include "base/logging.h"
  24 #include "mutex-inl.h"
  25 #include "runtime.h"
  26 #include "scoped_thread_state_change.h"
  27 #include "thread-inl.h"
  28 #include "utils.h"
  29
  30 namespace art {
  31
  32 Mutex* Locks::abort_lock_ = nullptr;
  33 Mutex* Locks::allocated_thread_ids_lock_ = nullptr;
  34 Mutex* Locks::breakpoint_lock_ = nullptr;
  35 ReaderWriterMutex* Locks::classlinker_classes_lock_ = nullptr;
  36 ReaderWriterMutex* Locks::heap_bitmap_lock_ = nullptr;
  37 Mutex* Locks::logging_lock_ = nullptr;
  38 Mutex* Locks::mem_maps_lock_ = nullptr;
  39 Mutex* Locks::modify_ldt_lock_ = nullptr;
  40 ReaderWriterMutex* Locks::mutator_lock_ = nullptr;
  41 Mutex* Locks::runtime_shutdown_lock_ = nullptr;
  42 Mutex* Locks::thread_list_lock_ = nullptr;
  43 Mutex* Locks::thread_suspend_count_lock_ = nullptr;
  44 Mutex* Locks::trace_lock_ = nullptr;
  45 Mutex* Locks::profiler_lock_ = nullptr;
  46 Mutex* Locks::unexpected_signal_lock_ = nullptr;
  47 Mutex* Locks::intern_table_lock_ = nullptr;
  48
  49 struct AllMutexData {
  50   // A guard for all_mutexes_ that's not a mutex (Mutexes must CAS to acquire and busy wait).
  51   Atomic<const BaseMutex*> all_mutexes_guard;
  52   // All created mutexes guarded by all_mutexes_guard_.
  53   std::set<BaseMutex*>* all_mutexes;
  54   AllMutexData() : all_mutexes(NULL) {}
  55 };
  56 static struct AllMutexData gAllMutexData[kAllMutexDataSize];
  57
  58 #if ART_USE_FUTEXES
  59 static bool ComputeRelativeTimeSpec(timespec* result_ts, const timespec& lhs, const timespec& rhs) {
  60   const int32_t one_sec = 1000 * 1000 * 1000;  // one second in nanoseconds.
  61   result_ts->tv_sec = lhs.tv_sec - rhs.tv_sec;
  62   result_ts->tv_nsec = lhs.tv_nsec - rhs.tv_nsec;
  63   if (result_ts->tv_nsec < 0) {
  64     result_ts->tv_sec--;
  65     result_ts->tv_nsec += one_sec;
  66   } else if (result_ts->tv_nsec > one_sec) {
  67     result_ts->tv_sec++;
  68     result_ts->tv_nsec -= one_sec;
  69   }
  70   return result_ts->tv_sec < 0;
  71 }
  72 #endif
  73
  74 class ScopedAllMutexesLock {
  75  public:
  76   explicit ScopedAllMutexesLock(const BaseMutex* mutex) : mutex_(mutex) {
  77     while (!gAllMutexData->all_mutexes_guard.CompareExchangeWeakAcquire(0, mutex)) {
  78       NanoSleep(100);
  79     }
  80   }
  81   ~ScopedAllMutexesLock() {
  82     while (!gAllMutexData->all_mutexes_guard.CompareExchangeWeakRelease(mutex_, 0)) {
  83       NanoSleep(100);
  84     }
  85   }
  86  private:
  87   const BaseMutex* const mutex_;
  88 };
  89
  90 BaseMutex::BaseMutex(const char* name, LockLevel level) : level_(level), name_(name) {
  91   if (kLogLockContentions) {
  92     ScopedAllMutexesLock mu(this);
  93     std::set<BaseMutex*>** all_mutexes_ptr = &gAllMutexData->all_mutexes;
  94     if (*all_mutexes_ptr == NULL) {
  95       // We leak the global set of all mutexes to avoid ordering issues in global variable
  96       // construction/destruction.
  97       *all_mutexes_ptr = new std::set<BaseMutex*>();
  98     }
  99     (*all_mutexes_ptr)->insert(this);
 100   }
 101 }
 102
 103 BaseMutex::~BaseMutex() {
 104   if (kLogLockContentions) {
 105     ScopedAllMutexesLock mu(this);
 106     gAllMutexData->all_mutexes->erase(this);
 107   }
 108 }
 109
 110 void BaseMutex::DumpAll(std::ostream& os) {
 111   if (kLogLockContentions) {
 112     os << "Mutex logging:\n";
 113     ScopedAllMutexesLock mu(reinterpret_cast<const BaseMutex*>(-1));
 114     std::set<BaseMutex*>* all_mutexes = gAllMutexData->all_mutexes;
 115     if (all_mutexes == NULL) {
 116       // No mutexes have been created yet during at startup.
 117       return;
 118     }
 119     typedef std::set<BaseMutex*>::const_iterator It;
 120     os << "(Contended)\n";
 121     for (It it = all_mutexes->begin(); it != all_mutexes->end(); ++it) {
 122       BaseMutex* mutex = *it;
 123       if (mutex->HasEverContended()) {
 124         mutex->Dump(os);
 125         os << "\n";
 126       }
 127     }
 128     os << "(Never contented)\n";
 129     for (It it = all_mutexes->begin(); it != all_mutexes->end(); ++it) {
 130       BaseMutex* mutex = *it;
 131       if (!mutex->HasEverContended()) {
 132         mutex->Dump(os);
 133         os << "\n";
 134       }
 135     }
 136   }
 137 }
 138
 139 void BaseMutex::CheckSafeToWait(Thread* self) {
 140   if (self == NULL) {
 141     CheckUnattachedThread(level_);
 142     return;
 143   }
 144   if (kDebugLocking) {
 145     CHECK(self->GetHeldMutex(level_) == this || level_ == kMonitorLock)
 146         << "Waiting on unacquired mutex: " << name_;
 147     bool bad_mutexes_held = false;
 148     for (int i = kLockLevelCount - 1; i >= 0; --i) {
 149       if (i != level_) {
 150         BaseMutex* held_mutex = self->GetHeldMutex(static_cast<LockLevel>(i));
 151         if (held_mutex != NULL) {
 152           LOG(ERROR) << "Holding \"" << held_mutex->name_ << "\" "
 153                      << "(level " << LockLevel(i) << ") while performing wait on "
 154                      << "\"" << name_ << "\" (level " << level_ << ")";
 155           bad_mutexes_held = true;
 156         }
 157       }
 158     }
 159     CHECK(!bad_mutexes_held);
 160   }
 161 }
 162
 163 inline void BaseMutex::ContentionLogData::AddToWaitTime(uint64_t value) {
 164   if (kLogLockContentions) {
 165     // Atomically add value to wait_time.
 166     uint64_t new_val, old_val;
 167     volatile int64_t* addr = reinterpret_cast<volatile int64_t*>(&wait_time);
 168     volatile const int64_t* caddr = const_cast<volatile const int64_t*>(addr);
 169     do {
 170       old_val = static_cast<uint64_t>(QuasiAtomic::Read64(caddr));
 171       new_val = old_val + value;
 172     } while (!QuasiAtomic::Cas64(static_cast<int64_t>(old_val), static_cast<int64_t>(new_val), addr));
 173   }
 174 }
 175
 176 void BaseMutex::RecordContention(uint64_t blocked_tid,
 177                                  uint64_t owner_tid,
 178                                  uint64_t nano_time_blocked) {
 179   if (kLogLockContentions) {
 180     ContentionLogData* data = contention_log_data_;
 181     ++(data->contention_count);
 182     data->AddToWaitTime(nano_time_blocked);
 183     ContentionLogEntry* log = data->contention_log;
 184     // This code is intentionally racy as it is only used for diagnostics.
 185     uint32_t slot = data->cur_content_log_entry.LoadRelaxed();
 186     if (log[slot].blocked_tid == blocked_tid &&
 187         log[slot].owner_tid == blocked_tid) {
 188       ++log[slot].count;
 189     } else {
 190       uint32_t new_slot;
 191       do {
 192         slot = data->cur_content_log_entry.LoadRelaxed();
 193         new_slot = (slot + 1) % kContentionLogSize;
 194       } while (!data->cur_content_log_entry.CompareExchangeWeakRelaxed(slot, new_slot));
 195       log[new_slot].blocked_tid = blocked_tid;
 196       log[new_slot].owner_tid = owner_tid;
 197       log[new_slot].count.StoreRelaxed(1);
 198     }
 199   }
 200 }
 201
 202 void BaseMutex::DumpContention(std::ostream& os) const {
 203   if (kLogLockContentions) {
 204     const ContentionLogData* data = contention_log_data_;
 205     const ContentionLogEntry* log = data->contention_log;
 206     uint64_t wait_time = data->wait_time;
 207     uint32_t contention_count = data->contention_count.LoadRelaxed();
 208     if (contention_count == 0) {
 209       os << "never contended";
 210     } else {
 211       os << "contended " << contention_count
 212          << " total wait of contender " << PrettyDuration(wait_time)
 213          << " average " << PrettyDuration(wait_time / contention_count);
 214       SafeMap<uint64_t, size_t> most_common_blocker;
 215       SafeMap<uint64_t, size_t> most_common_blocked;
 216       for (size_t i = 0; i < kContentionLogSize; ++i) {
 217         uint64_t blocked_tid = log[i].blocked_tid;
 218         uint64_t owner_tid = log[i].owner_tid;
 219         uint32_t count = log[i].count.LoadRelaxed();
 220         if (count > 0) {
 221           auto it = most_common_blocked.find(blocked_tid);
 222           if (it != most_common_blocked.end()) {
 223             most_common_blocked.Overwrite(blocked_tid, it->second + count);
 224           } else {
 225             most_common_blocked.Put(blocked_tid, count);
 226           }
 227           it = most_common_blocker.find(owner_tid);
 228           if (it != most_common_blocker.end()) {
 229             most_common_blocker.Overwrite(owner_tid, it->second + count);
 230           } else {
 231             most_common_blocker.Put(owner_tid, count);
 232           }
 233         }
 234       }
 235       uint64_t max_tid = 0;
 236       size_t max_tid_count = 0;
 237       for (const auto& pair : most_common_blocked) {
 238         if (pair.second > max_tid_count) {
 239           max_tid = pair.first;
 240           max_tid_count = pair.second;
 241         }
 242       }
 243       if (max_tid != 0) {
 244         os << " sample shows most blocked tid=" << max_tid;
 245       }
 246       max_tid = 0;
 247       max_tid_count = 0;
 248       for (const auto& pair : most_common_blocker) {
 249         if (pair.second > max_tid_count) {
 250           max_tid = pair.first;
 251           max_tid_count = pair.second;
 252         }
 253       }
 254       if (max_tid != 0) {
 255         os << " sample shows tid=" << max_tid << " owning during this time";
 256       }
 257     }
 258   }
 259 }
 260
 261
 262 Mutex::Mutex(const char* name, LockLevel level, bool recursive)
 263     : BaseMutex(name, level), recursive_(recursive), recursion_count_(0) {
 264 #if ART_USE_FUTEXES
 265   DCHECK_EQ(0, state_.LoadRelaxed());
 266   DCHECK_EQ(0, num_contenders_.LoadRelaxed());
 267 #else
 268   CHECK_MUTEX_CALL(pthread_mutex_init, (&mutex_, nullptr));
 269 #endif
 270   exclusive_owner_ = 0;
 271 }
 272
 273 Mutex::~Mutex() {
 274 #if ART_USE_FUTEXES
 275   if (state_.LoadRelaxed() != 0) {
 276     Runtime* runtime = Runtime::Current();
 277     bool shutting_down = runtime == nullptr || runtime->IsShuttingDown(Thread::Current());
 278     LOG(shutting_down ? WARNING : FATAL) << "destroying mutex with owner: " << exclusive_owner_;
 279   } else {
 280     CHECK_EQ(exclusive_owner_, 0U)  << "unexpectedly found an owner on unlocked mutex " << name_;
 281     CHECK_EQ(num_contenders_.LoadSequentiallyConsistent(), 0)
 282         << "unexpectedly found a contender on mutex " << name_;
 283   }
 284 #else
 285   // We can't use CHECK_MUTEX_CALL here because on shutdown a suspended daemon thread
 286   // may still be using locks.
 287   int rc = pthread_mutex_destroy(&mutex_);
 288   if (rc != 0) {
 289     errno = rc;
 290     // TODO: should we just not log at all if shutting down? this could be the logging mutex!
 291     MutexLock mu(Thread::Current(), *Locks::runtime_shutdown_lock_);
 292     Runtime* runtime = Runtime::Current();
 293     bool shutting_down = (runtime == NULL) || runtime->IsShuttingDownLocked();
 294     PLOG(shutting_down ? WARNING : FATAL) << "pthread_mutex_destroy failed for " << name_;
 295   }
 296 #endif
 297 }
 298
 299 void Mutex::ExclusiveLock(Thread* self) {
 300   DCHECK(self == NULL || self == Thread::Current());
 301   if (kDebugLocking && !recursive_) {
 302     AssertNotHeld(self);
 303   }
 304   if (!recursive_ || !IsExclusiveHeld(self)) {
 305 #if ART_USE_FUTEXES
 306     bool done = false;
 307     do {
 308       int32_t cur_state = state_.LoadRelaxed();
 309       if (LIKELY(cur_state == 0)) {
 310         // Change state from 0 to 1 and impose load/store ordering appropriate for lock acquisition.
 311         done = state_.CompareExchangeWeakAcquire(0 /* cur_state */, 1 /* new state */);
 312       } else {
 313         // Failed to acquire, hang up.
 314         ScopedContentionRecorder scr(this, SafeGetTid(self), GetExclusiveOwnerTid());
 315         num_contenders_++;
 316         if (futex(state_.Address(), FUTEX_WAIT, 1, NULL, NULL, 0) != 0) {
 317           // EAGAIN and EINTR both indicate a spurious failure, try again from the beginning.
 318           // We don't use TEMP_FAILURE_RETRY so we can intentionally retry to acquire the lock.
 319           if ((errno != EAGAIN) && (errno != EINTR)) {
 320             PLOG(FATAL) << "futex wait failed for " << name_;
 321           }
 322         }
 323         num_contenders_--;
 324       }
 325     } while (!done);
 326     DCHECK_EQ(state_.LoadRelaxed(), 1);
 327 #else
 328     CHECK_MUTEX_CALL(pthread_mutex_lock, (&mutex_));
 329 #endif
 330     DCHECK_EQ(exclusive_owner_, 0U);
 331     exclusive_owner_ = SafeGetTid(self);
 332     RegisterAsLocked(self);
 333   }
 334   recursion_count_++;
 335   if (kDebugLocking) {
 336     CHECK(recursion_count_ == 1 || recursive_) << "Unexpected recursion count on mutex: "
 337         << name_ << " " << recursion_count_;
 338     AssertHeld(self);
 339   }
 340 }
 341
 342 bool Mutex::ExclusiveTryLock(Thread* self) {
 343   DCHECK(self == NULL || self == Thread::Current());
 344   if (kDebugLocking && !recursive_) {
 345     AssertNotHeld(self);
 346   }
 347   if (!recursive_ || !IsExclusiveHeld(self)) {
 348 #if ART_USE_FUTEXES
 349     bool done = false;
 350     do {
 351       int32_t cur_state = state_.LoadRelaxed();
 352       if (cur_state == 0) {
 353         // Change state from 0 to 1 and impose load/store ordering appropriate for lock acquisition.
 354         done = state_.CompareExchangeWeakAcquire(0 /* cur_state */, 1 /* new state */);
 355       } else {
 356         return false;
 357       }
 358     } while (!done);
 359     DCHECK_EQ(state_.LoadRelaxed(), 1);
 360 #else
 361     int result = pthread_mutex_trylock(&mutex_);
 362     if (result == EBUSY) {
 363       return false;
 364     }
 365     if (result != 0) {
 366       errno = result;
 367       PLOG(FATAL) << "pthread_mutex_trylock failed for " << name_;
 368     }
 369 #endif
 370     DCHECK_EQ(exclusive_owner_, 0U);
 371     exclusive_owner_ = SafeGetTid(self);
 372     RegisterAsLocked(self);
 373   }
 374   recursion_count_++;
 375   if (kDebugLocking) {
 376     CHECK(recursion_count_ == 1 || recursive_) << "Unexpected recursion count on mutex: "
 377         << name_ << " " << recursion_count_;
 378     AssertHeld(self);
 379   }
 380   return true;
 381 }
 382
 383 void Mutex::ExclusiveUnlock(Thread* self) {
 384   DCHECK(self == NULL || self == Thread::Current());
 385   AssertHeld(self);
 386   DCHECK_NE(exclusive_owner_, 0U);
 387   recursion_count_--;
 388   if (!recursive_ || recursion_count_ == 0) {
 389     if (kDebugLocking) {
 390       CHECK(recursion_count_ == 0 || recursive_) << "Unexpected recursion count on mutex: "
 391           << name_ << " " << recursion_count_;
 392     }
 393     RegisterAsUnlocked(self);
 394 #if ART_USE_FUTEXES
 395     bool done = false;
 396     do {
 397       int32_t cur_state = state_.LoadRelaxed();
 398       if (LIKELY(cur_state == 1)) {
 399         // We're no longer the owner.
 400         exclusive_owner_ = 0;
 401         // Change state to 0 and impose load/store ordering appropriate for lock release.
 402         // Note, the relaxed loads below musn't reorder before the CompareExchange.
 403         // TODO: the ordering here is non-trivial as state is split across 3 fields, fix by placing
 404         // a status bit into the state on contention.
 405         done =  state_.CompareExchangeWeakSequentiallyConsistent(cur_state, 0 /* new state */);
 406         if (LIKELY(done)) {  // Spurious fail?
 407           // Wake a contender.
 408           if (UNLIKELY(num_contenders_.LoadRelaxed() > 0)) {
 409             futex(state_.Address(), FUTEX_WAKE, 1, NULL, NULL, 0);
 410           }
 411         }
 412       } else {
 413         // Logging acquires the logging lock, avoid infinite recursion in that case.
 414         if (this != Locks::logging_lock_) {
 415           LOG(FATAL) << "Unexpected state_ in unlock " << cur_state << " for " << name_;
 416         } else {
 417           LogMessageData data(__FILE__, __LINE__, INTERNAL_FATAL, -1);
 418           LogMessage::LogLine(data, StringPrintf("Unexpected state_ %d in unlock for %s",
 419                                                  cur_state, name_).c_str());
 420           _exit(1);
 421         }
 422       }
 423     } while (!done);
 424 #else
 425     exclusive_owner_ = 0;
 426     CHECK_MUTEX_CALL(pthread_mutex_unlock, (&mutex_));
 427 #endif
 428   }
 429 }
 430
 431 void Mutex::Dump(std::ostream& os) const {
 432   os << (recursive_ ? "recursive " : "non-recursive ")
 433       << name_
 434       << " level=" << static_cast<int>(level_)
 435       << " rec=" << recursion_count_
 436       << " owner=" << GetExclusiveOwnerTid() << " ";
 437   DumpContention(os);
 438 }
 439
 440 std::ostream& operator<<(std::ostream& os, const Mutex& mu) {
 441   mu.Dump(os);
 442   return os;
 443 }
 444
 445 ReaderWriterMutex::ReaderWriterMutex(const char* name, LockLevel level)
 446     : BaseMutex(name, level)
 447 #if ART_USE_FUTEXES
 448     , state_(0), num_pending_readers_(0), num_pending_writers_(0)
 449 #endif
 450 {  // NOLINT(whitespace/braces)
 451 #if !ART_USE_FUTEXES
 452   CHECK_MUTEX_CALL(pthread_rwlock_init, (&rwlock_, nullptr));
 453 #endif
 454   exclusive_owner_ = 0;
 455 }
 456
 457 ReaderWriterMutex::~ReaderWriterMutex() {
 458 #if ART_USE_FUTEXES
 459   CHECK_EQ(state_.LoadRelaxed(), 0);
 460   CHECK_EQ(exclusive_owner_, 0U);
 461   CHECK_EQ(num_pending_readers_.LoadRelaxed(), 0);
 462   CHECK_EQ(num_pending_writers_.LoadRelaxed(), 0);
 463 #else
 464   // We can't use CHECK_MUTEX_CALL here because on shutdown a suspended daemon thread
 465   // may still be using locks.
 466   int rc = pthread_rwlock_destroy(&rwlock_);
 467   if (rc != 0) {
 468     errno = rc;
 469     // TODO: should we just not log at all if shutting down? this could be the logging mutex!
 470     MutexLock mu(Thread::Current(), *Locks::runtime_shutdown_lock_);
 471     Runtime* runtime = Runtime::Current();
 472     bool shutting_down = runtime == NULL || runtime->IsShuttingDownLocked();
 473     PLOG(shutting_down ? WARNING : FATAL) << "pthread_rwlock_destroy failed for " << name_;
 474   }
 475 #endif
 476 }
 477
 478 void ReaderWriterMutex::ExclusiveLock(Thread* self) {
 479   DCHECK(self == NULL || self == Thread::Current());
 480   AssertNotExclusiveHeld(self);
 481 #if ART_USE_FUTEXES
 482   bool done = false;
 483   do {
 484     int32_t cur_state = state_.LoadRelaxed();
 485     if (LIKELY(cur_state == 0)) {
 486       // Change state from 0 to -1 and impose load/store ordering appropriate for lock acquisition.
 487       done =  state_.CompareExchangeWeakAcquire(0 /* cur_state*/, -1 /* new state */);
 488     } else {
 489       // Failed to acquire, hang up.
 490       ScopedContentionRecorder scr(this, SafeGetTid(self), GetExclusiveOwnerTid());
 491       ++num_pending_writers_;
 492       if (futex(state_.Address(), FUTEX_WAIT, cur_state, NULL, NULL, 0) != 0) {
 493         // EAGAIN and EINTR both indicate a spurious failure, try again from the beginning.
 494         // We don't use TEMP_FAILURE_RETRY so we can intentionally retry to acquire the lock.
 495         if ((errno != EAGAIN) && (errno != EINTR)) {
 496           PLOG(FATAL) << "futex wait failed for " << name_;
 497         }
 498       }
 499       --num_pending_writers_;
 500     }
 501   } while (!done);
 502   DCHECK_EQ(state_.LoadRelaxed(), -1);
 503 #else
 504   CHECK_MUTEX_CALL(pthread_rwlock_wrlock, (&rwlock_));
 505 #endif
 506   DCHECK_EQ(exclusive_owner_, 0U);
 507   exclusive_owner_ = SafeGetTid(self);
 508   RegisterAsLocked(self);
 509   AssertExclusiveHeld(self);
 510 }
 511
 512 void ReaderWriterMutex::ExclusiveUnlock(Thread* self) {
 513   DCHECK(self == NULL || self == Thread::Current());
 514   AssertExclusiveHeld(self);
 515   RegisterAsUnlocked(self);
 516   DCHECK_NE(exclusive_owner_, 0U);
 517 #if ART_USE_FUTEXES
 518   bool done = false;
 519   do {
 520     int32_t cur_state = state_.LoadRelaxed();
 521     if (LIKELY(cur_state == -1)) {
 522       // We're no longer the owner.
 523       exclusive_owner_ = 0;
 524       // Change state from -1 to 0 and impose load/store ordering appropriate for lock release.
 525       // Note, the relaxed loads below musn't reorder before the CompareExchange.
 526       // TODO: the ordering here is non-trivial as state is split across 3 fields, fix by placing
 527       // a status bit into the state on contention.
 528       done =  state_.CompareExchangeWeakSequentiallyConsistent(-1 /* cur_state*/, 0 /* new state */);
 529       if (LIKELY(done)) {  // Weak CAS may fail spuriously.
 530         // Wake any waiters.
 531         if (UNLIKELY(num_pending_readers_.LoadRelaxed() > 0 ||
 532                      num_pending_writers_.LoadRelaxed() > 0)) {
 533           futex(state_.Address(), FUTEX_WAKE, -1, NULL, NULL, 0);
 534         }
 535       }
 536     } else {
 537       LOG(FATAL) << "Unexpected state_:" << cur_state << " for " << name_;
 538     }
 539   } while (!done);
 540 #else
 541   exclusive_owner_ = 0;
 542   CHECK_MUTEX_CALL(pthread_rwlock_unlock, (&rwlock_));
 543 #endif
 544 }
 545
 546 #if HAVE_TIMED_RWLOCK
 547 bool ReaderWriterMutex::ExclusiveLockWithTimeout(Thread* self, int64_t ms, int32_t ns) {
 548   DCHECK(self == NULL || self == Thread::Current());
 549 #if ART_USE_FUTEXES
 550   bool done = false;
 551   timespec end_abs_ts;
 552   InitTimeSpec(true, CLOCK_REALTIME, ms, ns, &end_abs_ts);
 553   do {
 554     int32_t cur_state = state_.LoadRelaxed();
 555     if (cur_state == 0) {
 556       // Change state from 0 to -1 and impose load/store ordering appropriate for lock acquisition.
 557       done =  state_.CompareExchangeWeakAcquire(0 /* cur_state */, -1 /* new state */);
 558     } else {
 559       // Failed to acquire, hang up.
 560       timespec now_abs_ts;
 561       InitTimeSpec(true, CLOCK_REALTIME, 0, 0, &now_abs_ts);
 562       timespec rel_ts;
 563       if (ComputeRelativeTimeSpec(&rel_ts, end_abs_ts, now_abs_ts)) {
 564         return false;  // Timed out.
 565       }
 566       ScopedContentionRecorder scr(this, SafeGetTid(self), GetExclusiveOwnerTid());
 567       ++num_pending_writers_;
 568       if (futex(state_.Address(), FUTEX_WAIT, cur_state, &rel_ts, NULL, 0) != 0) {
 569         if (errno == ETIMEDOUT) {
 570           --num_pending_writers_;
 571           return false;  // Timed out.
 572         } else if ((errno != EAGAIN) && (errno != EINTR)) {
 573           // EAGAIN and EINTR both indicate a spurious failure,
 574           // recompute the relative time out from now and try again.
 575           // We don't use TEMP_FAILURE_RETRY so we can recompute rel_ts;
 576           PLOG(FATAL) << "timed futex wait failed for " << name_;
 577         }
 578       }
 579       --num_pending_writers_;
 580     }
 581   } while (!done);
 582 #else
 583   timespec ts;
 584   InitTimeSpec(true, CLOCK_REALTIME, ms, ns, &ts);
 585   int result = pthread_rwlock_timedwrlock(&rwlock_, &ts);
 586   if (result == ETIMEDOUT) {
 587     return false;
 588   }
 589   if (result != 0) {
 590     errno = result;
 591     PLOG(FATAL) << "pthread_rwlock_timedwrlock failed for " << name_;
 592   }
 593 #endif
 594   exclusive_owner_ = SafeGetTid(self);
 595   RegisterAsLocked(self);
 596   AssertSharedHeld(self);
 597   return true;
 598 }
 599 #endif
 600
 601 bool ReaderWriterMutex::SharedTryLock(Thread* self) {
 602   DCHECK(self == NULL || self == Thread::Current());
 603 #if ART_USE_FUTEXES
 604   bool done = false;
 605   do {
 606     int32_t cur_state = state_.LoadRelaxed();
 607     if (cur_state >= 0) {
 608       // Add as an extra reader and impose load/store ordering appropriate for lock acquisition.
 609       done =  state_.CompareExchangeWeakAcquire(cur_state, cur_state + 1);
 610     } else {
 611       // Owner holds it exclusively.
 612       return false;
 613     }
 614   } while (!done);
 615 #else
 616   int result = pthread_rwlock_tryrdlock(&rwlock_);
 617   if (result == EBUSY) {
 618     return false;
 619   }
 620   if (result != 0) {
 621     errno = result;
 622     PLOG(FATAL) << "pthread_mutex_trylock failed for " << name_;
 623   }
 624 #endif
 625   RegisterAsLocked(self);
 626   AssertSharedHeld(self);
 627   return true;
 628 }
 629
 630 bool ReaderWriterMutex::IsSharedHeld(const Thread* self) const {
 631   DCHECK(self == NULL || self == Thread::Current());
 632   bool result;
 633   if (UNLIKELY(self == NULL)) {  // Handle unattached threads.
 634     result = IsExclusiveHeld(self);  // TODO: a better best effort here.
 635   } else {
 636     result = (self->GetHeldMutex(level_) == this);
 637   }
 638   return result;
 639 }
 640
 641 void ReaderWriterMutex::Dump(std::ostream& os) const {
 642   os << name_
 643       << " level=" << static_cast<int>(level_)
 644       << " owner=" << GetExclusiveOwnerTid() << " ";
 645   DumpContention(os);
 646 }
 647
 648 std::ostream& operator<<(std::ostream& os, const ReaderWriterMutex& mu) {
 649   mu.Dump(os);
 650   return os;
 651 }
 652
 653 ConditionVariable::ConditionVariable(const char* name, Mutex& guard)
 654     : name_(name), guard_(guard) {
 655 #if ART_USE_FUTEXES
 656   DCHECK_EQ(0, sequence_.LoadRelaxed());
 657   num_waiters_ = 0;
 658 #else
 659   pthread_condattr_t cond_attrs;
 660   CHECK_MUTEX_CALL(pthread_condattr_init, (&cond_attrs));
 661 #if !defined(__APPLE__)
 662   // Apple doesn't have CLOCK_MONOTONIC or pthread_condattr_setclock.
 663   CHECK_MUTEX_CALL(pthread_condattr_setclock(&cond_attrs, CLOCK_MONOTONIC));
 664 #endif
 665   CHECK_MUTEX_CALL(pthread_cond_init, (&cond_, &cond_attrs));
 666 #endif
 667 }
 668
 669 ConditionVariable::~ConditionVariable() {
 670 #if ART_USE_FUTEXES
 671   if (num_waiters_!= 0) {
 672     Runtime* runtime = Runtime::Current();
 673     bool shutting_down = runtime == nullptr || runtime->IsShuttingDown(Thread::Current());
 674     LOG(shutting_down ? WARNING : FATAL) << "ConditionVariable::~ConditionVariable for " << name_
 675         << " called with " << num_waiters_ << " waiters.";
 676   }
 677 #else
 678   // We can't use CHECK_MUTEX_CALL here because on shutdown a suspended daemon thread
 679   // may still be using condition variables.
 680   int rc = pthread_cond_destroy(&cond_);
 681   if (rc != 0) {
 682     errno = rc;
 683     MutexLock mu(Thread::Current(), *Locks::runtime_shutdown_lock_);
 684     Runtime* runtime = Runtime::Current();
 685     bool shutting_down = (runtime == NULL) || runtime->IsShuttingDownLocked();
 686     PLOG(shutting_down ? WARNING : FATAL) << "pthread_cond_destroy failed for " << name_;
 687   }
 688 #endif
 689 }
 690
 691 void ConditionVariable::Broadcast(Thread* self) {
 692   DCHECK(self == NULL || self == Thread::Current());
 693   // TODO: enable below, there's a race in thread creation that causes false failures currently.
 694   // guard_.AssertExclusiveHeld(self);
 695   DCHECK_EQ(guard_.GetExclusiveOwnerTid(), SafeGetTid(self));
 696 #if ART_USE_FUTEXES
 697   if (num_waiters_ > 0) {
 698     sequence_++;  // Indicate the broadcast occurred.
 699     bool done = false;
 700     do {
 701       int32_t cur_sequence = sequence_.LoadRelaxed();
 702       // Requeue waiters onto mutex. The waiter holds the contender count on the mutex high ensuring
 703       // mutex unlocks will awaken the requeued waiter thread.
 704       done = futex(sequence_.Address(), FUTEX_CMP_REQUEUE, 0,
 705                    reinterpret_cast<const timespec*>(std::numeric_limits<int32_t>::max()),
 706                    guard_.state_.Address(), cur_sequence) != -1;
 707       if (!done) {
 708         if (errno != EAGAIN) {
 709           PLOG(FATAL) << "futex cmp requeue failed for " << name_;
 710         }
 711       }
 712     } while (!done);
 713   }
 714 #else
 715   CHECK_MUTEX_CALL(pthread_cond_broadcast, (&cond_));
 716 #endif
 717 }
 718
 719 void ConditionVariable::Signal(Thread* self) {
 720   DCHECK(self == NULL || self == Thread::Current());
 721   guard_.AssertExclusiveHeld(self);
 722 #if ART_USE_FUTEXES
 723   if (num_waiters_ > 0) {
 724     sequence_++;  // Indicate a signal occurred.
 725     // Futex wake 1 waiter who will then come and in contend on mutex. It'd be nice to requeue them
 726     // to avoid this, however, requeueing can only move all waiters.
 727     int num_woken = futex(sequence_.Address(), FUTEX_WAKE, 1, NULL, NULL, 0);
 728     // Check something was woken or else we changed sequence_ before they had chance to wait.
 729     CHECK((num_woken == 0) || (num_woken == 1));
 730   }
 731 #else
 732   CHECK_MUTEX_CALL(pthread_cond_signal, (&cond_));
 733 #endif
 734 }
 735
 736 void ConditionVariable::Wait(Thread* self) {
 737   guard_.CheckSafeToWait(self);
 738   WaitHoldingLocks(self);
 739 }
 740
 741 void ConditionVariable::WaitHoldingLocks(Thread* self) {
 742   DCHECK(self == NULL || self == Thread::Current());
 743   guard_.AssertExclusiveHeld(self);
 744   unsigned int old_recursion_count = guard_.recursion_count_;
 745 #if ART_USE_FUTEXES
 746   num_waiters_++;
 747   // Ensure the Mutex is contended so that requeued threads are awoken.
 748   guard_.num_contenders_++;
 749   guard_.recursion_count_ = 1;
 750   int32_t cur_sequence = sequence_.LoadRelaxed();
 751   guard_.ExclusiveUnlock(self);
 752   if (futex(sequence_.Address(), FUTEX_WAIT, cur_sequence, NULL, NULL, 0) != 0) {
 753     // Futex failed, check it is an expected error.
 754     // EAGAIN == EWOULDBLK, so we let the caller try again.
 755     // EINTR implies a signal was sent to this thread.
 756     if ((errno != EINTR) && (errno != EAGAIN)) {
 757       PLOG(FATAL) << "futex wait failed for " << name_;
 758     }
 759   }
 760   guard_.ExclusiveLock(self);
 761   CHECK_GE(num_waiters_, 0);
 762   num_waiters_--;
 763   // We awoke and so no longer require awakes from the guard_'s unlock.
 764   CHECK_GE(guard_.num_contenders_.LoadRelaxed(), 0);
 765   guard_.num_contenders_--;
 766 #else
 767   uint64_t old_owner = guard_.exclusive_owner_;
 768   guard_.exclusive_owner_ = 0;
 769   guard_.recursion_count_ = 0;
 770   CHECK_MUTEX_CALL(pthread_cond_wait, (&cond_, &guard_.mutex_));
 771   guard_.exclusive_owner_ = old_owner;
 772 #endif
 773   guard_.recursion_count_ = old_recursion_count;
 774 }
 775
 776 void ConditionVariable::TimedWait(Thread* self, int64_t ms, int32_t ns) {
 777   DCHECK(self == NULL || self == Thread::Current());
 778   guard_.AssertExclusiveHeld(self);
 779   guard_.CheckSafeToWait(self);
 780   unsigned int old_recursion_count = guard_.recursion_count_;
 781 #if ART_USE_FUTEXES
 782   timespec rel_ts;
 783   InitTimeSpec(false, CLOCK_REALTIME, ms, ns, &rel_ts);
 784   num_waiters_++;
 785   // Ensure the Mutex is contended so that requeued threads are awoken.
 786   guard_.num_contenders_++;
 787   guard_.recursion_count_ = 1;
 788   int32_t cur_sequence = sequence_.LoadRelaxed();
 789   guard_.ExclusiveUnlock(self);
 790   if (futex(sequence_.Address(), FUTEX_WAIT, cur_sequence, &rel_ts, NULL, 0) != 0) {
 791     if (errno == ETIMEDOUT) {
 792       // Timed out we're done.
 793     } else if ((errno == EAGAIN) || (errno == EINTR)) {
 794       // A signal or ConditionVariable::Signal/Broadcast has come in.
 795     } else {
 796       PLOG(FATAL) << "timed futex wait failed for " << name_;
 797     }
 798   }
 799   guard_.ExclusiveLock(self);
 800   CHECK_GE(num_waiters_, 0);
 801   num_waiters_--;
 802   // We awoke and so no longer require awakes from the guard_'s unlock.
 803   CHECK_GE(guard_.num_contenders_.LoadRelaxed(), 0);
 804   guard_.num_contenders_--;
 805 #else
 806 #if !defined(__APPLE__)
 807   int clock = CLOCK_MONOTONIC;
 808 #else
 809   int clock = CLOCK_REALTIME;
 810 #endif
 811   uint64_t old_owner = guard_.exclusive_owner_;
 812   guard_.exclusive_owner_ = 0;
 813   guard_.recursion_count_ = 0;
 814   timespec ts;
 815   InitTimeSpec(true, clock, ms, ns, &ts);
 816   int rc = TEMP_FAILURE_RETRY(pthread_cond_timedwait(&cond_, &guard_.mutex_, &ts));
 817   if (rc != 0 && rc != ETIMEDOUT) {
 818     errno = rc;
 819     PLOG(FATAL) << "TimedWait failed for " << name_;
 820   }
 821   guard_.exclusive_owner_ = old_owner;
 822 #endif
 823   guard_.recursion_count_ = old_recursion_count;
 824 }
 825
 826 void Locks::Init() {
 827   if (logging_lock_ != nullptr) {
 828     // Already initialized.
 829     if (kRuntimeISA == kX86 || kRuntimeISA == kX86_64) {
 830       DCHECK(modify_ldt_lock_ != nullptr);
 831     } else {
 832       DCHECK(modify_ldt_lock_ == nullptr);
 833     }
 834     DCHECK(abort_lock_ != nullptr);
 835     DCHECK(allocated_thread_ids_lock_ != nullptr);
 836     DCHECK(breakpoint_lock_ != nullptr);
 837     DCHECK(classlinker_classes_lock_ != nullptr);
 838     DCHECK(heap_bitmap_lock_ != nullptr);
 839     DCHECK(logging_lock_ != nullptr);
 840     DCHECK(mutator_lock_ != nullptr);
 841     DCHECK(thread_list_lock_ != nullptr);
 842     DCHECK(thread_suspend_count_lock_ != nullptr);
 843     DCHECK(trace_lock_ != nullptr);
 844     DCHECK(profiler_lock_ != nullptr);
 845     DCHECK(unexpected_signal_lock_ != nullptr);
 846     DCHECK(intern_table_lock_ != nullptr);
 847   } else {
 848     // Create global locks in level order from highest lock level to lowest.
 849     LockLevel current_lock_level = kMutatorLock;
 850     DCHECK(mutator_lock_ == nullptr);
 851     mutator_lock_ = new ReaderWriterMutex("mutator lock", current_lock_level);
 852
 853     #define UPDATE_CURRENT_LOCK_LEVEL(new_level) \
 854         DCHECK_LT(new_level, current_lock_level); \
 855         current_lock_level = new_level;
 856
 857     UPDATE_CURRENT_LOCK_LEVEL(kHeapBitmapLock);
 858     DCHECK(heap_bitmap_lock_ == nullptr);
 859     heap_bitmap_lock_ = new ReaderWriterMutex("heap bitmap lock", current_lock_level);
 860
 861     UPDATE_CURRENT_LOCK_LEVEL(kRuntimeShutdownLock);
 862     DCHECK(runtime_shutdown_lock_ == nullptr);
 863     runtime_shutdown_lock_ = new Mutex("runtime shutdown lock", current_lock_level);
 864
 865     UPDATE_CURRENT_LOCK_LEVEL(kProfilerLock);
 866     DCHECK(profiler_lock_ == nullptr);
 867     profiler_lock_ = new Mutex("profiler lock", current_lock_level);
 868
 869     UPDATE_CURRENT_LOCK_LEVEL(kTraceLock);
 870     DCHECK(trace_lock_ == nullptr);
 871     trace_lock_ = new Mutex("trace lock", current_lock_level);
 872
 873     UPDATE_CURRENT_LOCK_LEVEL(kThreadListLock);
 874     DCHECK(thread_list_lock_ == nullptr);
 875     thread_list_lock_ = new Mutex("thread list lock", current_lock_level);
 876
 877     UPDATE_CURRENT_LOCK_LEVEL(kBreakpointLock);
 878     DCHECK(breakpoint_lock_ == nullptr);
 879     breakpoint_lock_ = new Mutex("breakpoint lock", current_lock_level);
 880
 881     UPDATE_CURRENT_LOCK_LEVEL(kClassLinkerClassesLock);
 882     DCHECK(classlinker_classes_lock_ == nullptr);
 883     classlinker_classes_lock_ = new ReaderWriterMutex("ClassLinker classes lock",
 884                                                       current_lock_level);
 885
 886     UPDATE_CURRENT_LOCK_LEVEL(kAllocatedThreadIdsLock);
 887     DCHECK(allocated_thread_ids_lock_ == nullptr);
 888     allocated_thread_ids_lock_ =  new Mutex("allocated thread ids lock", current_lock_level);
 889
 890     if (kRuntimeISA == kX86 || kRuntimeISA == kX86_64) {
 891       UPDATE_CURRENT_LOCK_LEVEL(kModifyLdtLock);
 892       DCHECK(modify_ldt_lock_ == nullptr);
 893       modify_ldt_lock_ = new Mutex("modify_ldt lock", current_lock_level);
 894     }
 895
 896     UPDATE_CURRENT_LOCK_LEVEL(kInternTableLock);
 897     DCHECK(intern_table_lock_ == nullptr);
 898     intern_table_lock_ = new Mutex("InternTable lock", current_lock_level);
 899
 900
 901     UPDATE_CURRENT_LOCK_LEVEL(kAbortLock);
 902     DCHECK(abort_lock_ == nullptr);
 903     abort_lock_ = new Mutex("abort lock", current_lock_level, true);
 904
 905     UPDATE_CURRENT_LOCK_LEVEL(kThreadSuspendCountLock);
 906     DCHECK(thread_suspend_count_lock_ == nullptr);
 907     thread_suspend_count_lock_ = new Mutex("thread suspend count lock", current_lock_level);
 908
 909     UPDATE_CURRENT_LOCK_LEVEL(kUnexpectedSignalLock);
 910     DCHECK(unexpected_signal_lock_ == nullptr);
 911     unexpected_signal_lock_ = new Mutex("unexpected signal lock", current_lock_level, true);
 912
 913     UPDATE_CURRENT_LOCK_LEVEL(kMemMapsLock);
 914     DCHECK(mem_maps_lock_ == nullptr);
 915     mem_maps_lock_ = new Mutex("mem maps lock", current_lock_level);
 916
 917     UPDATE_CURRENT_LOCK_LEVEL(kLoggingLock);
 918     DCHECK(logging_lock_ == nullptr);
 919     logging_lock_ = new Mutex("logging lock", current_lock_level, true);
 920
 921     #undef UPDATE_CURRENT_LOCK_LEVEL
 922   }
 923 }
 924
 925
 926 }  // namespace art