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