tsan_mutex.cc revision 5d71de26cedae3dafc17449fe0182045c0bd20e8
14b95526e5c4eb4fecde1cd642cf991a82c51b9f2johannkoenig@chromium.org//===-- tsan_mutex.cc -----------------------------------------------------===// 24b95526e5c4eb4fecde1cd642cf991a82c51b9f2johannkoenig@chromium.org// 38ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org// The LLVM Compiler Infrastructure 48ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org// 58ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org// This file is distributed under the University of Illinois Open Source 68ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org// License. See LICENSE.TXT for details. 78ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org// 88ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org//===----------------------------------------------------------------------===// 98ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org// 10dddee1ec7cedf276305b107429f684539b105276johannkoenig@chromium.org// This file is a part of ThreadSanitizer (TSan), a race detector. 11dddee1ec7cedf276305b107429f684539b105276johannkoenig@chromium.org// 12dddee1ec7cedf276305b107429f684539b105276johannkoenig@chromium.org//===----------------------------------------------------------------------===// 13dddee1ec7cedf276305b107429f684539b105276johannkoenig@chromium.org#include "sanitizer_common/sanitizer_libc.h" 148ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org#include "tsan_mutex.h" 158ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org#include "tsan_platform.h" 168ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org#include "tsan_rtl.h" 178ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org 188ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.orgnamespace __tsan { 198ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org 208ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org// Simple reader-writer spin-mutex. Optimized for not-so-contended case. 218ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org// Readers have preference, can possibly starvate writers. 228ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org 238ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org// The table fixes what mutexes can be locked under what mutexes. 248ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org// E.g. if the row for MutexTypeThreads contains MutexTypeReport, 258ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org// then Report mutex can be locked while under Threads mutex. 268ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org// The leaf mutexes can be locked under any other mutexes. 278ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org// Recursive locking is not supported. 288ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org#if TSAN_DEBUG && !TSAN_GO 2962346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.orgconst MutexType MutexTypeLeaf = (MutexType)-1; 3062346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.orgstatic MutexType CanLockTab[MutexTypeCount][MutexTypeCount] = { 3162346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org /*0 MutexTypeInvalid*/ {}, 3262346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org /*1 MutexTypeTrace*/ {MutexTypeLeaf}, 3362346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org /*2 MutexTypeThreads*/ {MutexTypeReport}, 348ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org /*3 MutexTypeReport*/ {MutexTypeSyncVar, 3562346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org MutexTypeMBlock, MutexTypeJavaMBlock}, 3662346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org /*4 MutexTypeSyncVar*/ {MutexTypeDDetector}, 3762346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org /*5 MutexTypeSyncTab*/ {}, // unused 388ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org /*6 MutexTypeSlab*/ {MutexTypeLeaf}, 3962346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org /*7 MutexTypeAnnotations*/ {}, 4062346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org /*8 MutexTypeAtExit*/ {MutexTypeSyncVar}, 4162346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org /*9 MutexTypeMBlock*/ {MutexTypeSyncVar}, 428ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org /*10 MutexTypeJavaMBlock*/ {MutexTypeSyncVar}, 4362346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org /*11 MutexTypeDDetector*/ {}, 4462346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org}; 4562346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org 4662346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.orgstatic bool CanLockAdj[MutexTypeCount][MutexTypeCount]; 4762346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org#endif 488ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org 4962346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.orgvoid InitializeMutex() { 5062346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org#if TSAN_DEBUG && !TSAN_GO 518ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org // Build the "can lock" adjacency matrix. 5262346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org // If [i][j]==true, then one can lock mutex j while under mutex i. 5362346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org const int N = MutexTypeCount; 548ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org int cnt[N] = {}; 5562346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org bool leaf[N] = {}; 5662346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org for (int i = 1; i < N; i++) { 578ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org for (int j = 0; j < N; j++) { 5862346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org MutexType z = CanLockTab[i][j]; 5962346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org if (z == MutexTypeInvalid) 6062346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org continue; 6162346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org if (z == MutexTypeLeaf) { 628ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org CHECK(!leaf[i]); 6362346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org leaf[i] = true; 6462346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org continue; 6562346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 6662346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org CHECK(!CanLockAdj[i][(int)z]); 678ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org CanLockAdj[i][(int)z] = true; 6862346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org cnt[i]++; 6962346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 7062346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 7162346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org for (int i = 0; i < N; i++) { 728ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org CHECK(!leaf[i] || cnt[i] == 0); 7362346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 7462346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org // Add leaf mutexes. 7562346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org for (int i = 0; i < N; i++) { 768ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org if (!leaf[i]) 7762346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org continue; 7862346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org for (int j = 0; j < N; j++) { 7962346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org if (i == j || leaf[j] || j == MutexTypeInvalid) 8062346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org continue; 818ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org CHECK(!CanLockAdj[j][i]); 828ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org CanLockAdj[j][i] = true; 838ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org } 848ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org } 858ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org // Build the transitive closure. 868ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org bool CanLockAdj2[MutexTypeCount][MutexTypeCount]; 878ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org for (int i = 0; i < N; i++) { 888ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org for (int j = 0; j < N; j++) { 898ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org CanLockAdj2[i][j] = CanLockAdj[i][j]; 908ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org } 9162346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 9262346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org for (int k = 0; k < N; k++) { 9362346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org for (int i = 0; i < N; i++) { 948ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org for (int j = 0; j < N; j++) { 9562346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org if (CanLockAdj2[i][k] && CanLockAdj2[k][j]) { 9662346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org CanLockAdj2[i][j] = true; 9762346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 988ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org } 9962346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 10062346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 10162346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org#if 0 1028ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org Printf("Can lock graph:\n"); 10362346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org for (int i = 0; i < N; i++) { 10462346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org for (int j = 0; j < N; j++) { 10562346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org Printf("%d ", CanLockAdj[i][j]); 1068ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org } 10762346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org Printf("\n"); 10862346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 10962346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org Printf("Can lock graph closure:\n"); 11062346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org for (int i = 0; i < N; i++) { 1118ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org for (int j = 0; j < N; j++) { 11262346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org Printf("%d ", CanLockAdj2[i][j]); 11362346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 11462346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org Printf("\n"); 11562346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 1168ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org#endif 11762346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org // Verify that the graph is acyclic. 11862346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org for (int i = 0; i < N; i++) { 11962346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org if (CanLockAdj2[i][i]) { 1208ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org Printf("Mutex %d participates in a cycle\n", i); 12162346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org Die(); 12262346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 12362346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 1248ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org#endif 12562346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org} 12662346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org 12762346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.orgInternalDeadlockDetector::InternalDeadlockDetector() { 12862346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org // Rely on zero initialization because some mutexes can be locked before ctor. 1298ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org} 13062346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org 13162346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org#if TSAN_DEBUG && !TSAN_GO 1328ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.orgvoid InternalDeadlockDetector::Lock(MutexType t) { 1338ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org // Printf("LOCK %d @%zu\n", t, seq_ + 1); 1348ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org CHECK_GT(t, MutexTypeInvalid); 1358ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org CHECK_LT(t, MutexTypeCount); 1368ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org u64 max_seq = 0; 13762346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org u64 max_idx = MutexTypeInvalid; 13862346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org for (int i = 0; i != MutexTypeCount; i++) { 13962346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org if (locked_[i] == 0) 1408ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org continue; 1418ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org CHECK_NE(locked_[i], max_seq); 1428ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org if (max_seq < locked_[i]) { 1438ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org max_seq = locked_[i]; 14462346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org max_idx = i; 14562346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 14662346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 14762346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org locked_[t] = ++seq_; 1488ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org if (max_idx == MutexTypeInvalid) 14962346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org return; 15062346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org // Printf(" last %d @%zu\n", max_idx, max_seq); 15162346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org if (!CanLockAdj[max_idx][t]) { 1528ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org Printf("ThreadSanitizer: internal deadlock detected\n"); 15362346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org Printf("ThreadSanitizer: can't lock %d while under %zu\n", 15462346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org t, (uptr)max_idx); 15562346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org CHECK(0); 15662346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 1578ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org} 15862346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org 15962346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.orgvoid InternalDeadlockDetector::Unlock(MutexType t) { 1608ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org // Printf("UNLO %d @%zu #%zu\n", t, seq_, locked_[t]); 16162346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org CHECK(locked_[t]); 16262346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org locked_[t] = 0; 16362346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org} 16462346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org 1658ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.orgvoid InternalDeadlockDetector::CheckNoLocks() { 16662346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org for (int i = 0; i != MutexTypeCount; i++) { 16762346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org CHECK_EQ(locked_[i], 0); 16862346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 16962346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org} 1708ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org#endif 17162346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org 17262346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.orgvoid CheckNoLocks(ThreadState *thr) { 17362346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org#if TSAN_DEBUG && !TSAN_GO 17462346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org thr->internal_deadlock_detector.CheckNoLocks(); 1758ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org#endif 17662346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org} 17762346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org 17862346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.orgconst uptr kUnlocked = 0; 17962346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.orgconst uptr kWriteLock = 1; 1808ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.orgconst uptr kReadLock = 2; 18162346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org 18262346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.orgclass Backoff { 18362346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org public: 18462346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org Backoff() 1858ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org : iter_() { 18662346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 18762346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org 18862346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org bool Do() { 18962346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org if (iter_++ < kActiveSpinIters) 1908ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org proc_yield(kActiveSpinCnt); 19162346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org else 19262346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org internal_sched_yield(); 19362346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org return true; 19462346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 1958ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org 19662346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org u64 Contention() const { 19762346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org u64 active = iter_ % kActiveSpinIters; 19862346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org u64 passive = iter_ - active; 19962346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org return active + 10 * passive; 2008ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org } 20162346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org 20262346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org private: 20362346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org int iter_; 20462346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org static const int kActiveSpinIters = 10; 2058ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org static const int kActiveSpinCnt = 20; 20662346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org}; 20762346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org 20862346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.orgMutex::Mutex(MutexType type, StatType stat_type) { 2098ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org CHECK_GT(type, MutexTypeInvalid); 21062346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org CHECK_LT(type, MutexTypeCount); 21162346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org#if TSAN_DEBUG 21262346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org type_ = type; 21362346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org#endif 2148ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org#if TSAN_COLLECT_STATS 21562346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org stat_type_ = stat_type; 21662346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org#endif 21762346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org atomic_store(&state_, kUnlocked, memory_order_relaxed); 21862346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org} 2198ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org 22062346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.orgMutex::~Mutex() { 22162346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org CHECK_EQ(atomic_load(&state_, memory_order_relaxed), kUnlocked); 22262346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org} 22362346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org 2248ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.orgvoid Mutex::Lock() { 22562346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org#if TSAN_DEBUG && !TSAN_GO 22662346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org cur_thread()->internal_deadlock_detector.Lock(type_); 22762346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org#endif 22862346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org uptr cmp = kUnlocked; 2298ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org if (atomic_compare_exchange_strong(&state_, &cmp, kWriteLock, 23062346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org memory_order_acquire)) 23162346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org return; 23262346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org for (Backoff backoff; backoff.Do();) { 2338ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org if (atomic_load(&state_, memory_order_relaxed) == kUnlocked) { 23462346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org cmp = kUnlocked; 23562346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org if (atomic_compare_exchange_weak(&state_, &cmp, kWriteLock, 2368ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org memory_order_acquire)) { 23762346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org#if TSAN_COLLECT_STATS && !TSAN_GO 23862346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org StatInc(cur_thread(), stat_type_, backoff.Contention()); 2398ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org#endif 24062346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org return; 24162346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 2428ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org } 24362346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 24462346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org} 24562346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org 2468ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.orgvoid Mutex::Unlock() { 24762346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org uptr prev = atomic_fetch_sub(&state_, kWriteLock, memory_order_release); 24862346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org (void)prev; 24962346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org DCHECK_NE(prev & kWriteLock, 0); 2508ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org#if TSAN_DEBUG && !TSAN_GO 25162346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org cur_thread()->internal_deadlock_detector.Unlock(type_); 25262346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org#endif 2538ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org} 2548ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org 2558ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.orgvoid Mutex::ReadLock() { 2568ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org#if TSAN_DEBUG && !TSAN_GO 2578ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org cur_thread()->internal_deadlock_detector.Lock(type_); 2588ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org#endif 2598ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org uptr prev = atomic_fetch_add(&state_, kReadLock, memory_order_acquire); 26062346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org if ((prev & kWriteLock) == 0) 26162346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org return; 26262346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org for (Backoff backoff; backoff.Do();) { 26362346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org prev = atomic_load(&state_, memory_order_acquire); 2648ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org if ((prev & kWriteLock) == 0) { 26562346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org#if TSAN_COLLECT_STATS && !TSAN_GO 26662346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org StatInc(cur_thread(), stat_type_, backoff.Contention()); 26762346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org#endif 2688ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org return; 26962346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 27062346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org } 27162346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org} 27262346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org 27362346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.orgvoid Mutex::ReadUnlock() { 27462346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org uptr prev = atomic_fetch_sub(&state_, kReadLock, memory_order_release); 27562346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org (void)prev; 27662346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org DCHECK_EQ(prev & kWriteLock, 0); 2778ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org DCHECK_GT(prev & ~kWriteLock, 0); 2788ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org#if TSAN_DEBUG && !TSAN_GO 2798ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org cur_thread()->internal_deadlock_detector.Unlock(type_); 2808ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org#endif 2818ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org} 2828ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org 28362346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.orgvoid Mutex::CheckLocked() { 28462346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org CHECK_NE(atomic_load(&state_, memory_order_relaxed), 0); 28562346fffe2566140c9f486b24be8377abf9e5b59fgalligan@chromium.org} 2868ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org 2878ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org} // namespace __tsan 2888ae1e8e2c7efa47d8464e8a3205dbfaed138690ffgalligan@chromium.org