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