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