1 //===-- sanitizer_mutex.cpp -----------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file is shared between AddressSanitizer and ThreadSanitizer 10 // run-time libraries. 11 //===----------------------------------------------------------------------===// 12 13 #include "sanitizer_mutex.h" 14 15 #include "sanitizer_common.h" 16 17 namespace __sanitizer { 18 19 void StaticSpinMutex::LockSlow() { 20 for (int i = 0;; i++) { 21 if (i < 100) 22 proc_yield(1); 23 else 24 internal_sched_yield(); 25 if (atomic_load(&state_, memory_order_relaxed) == 0 && 26 atomic_exchange(&state_, 1, memory_order_acquire) == 0) 27 return; 28 } 29 } 30 31 void Semaphore::Wait() { 32 u32 count = atomic_load(&state_, memory_order_relaxed); 33 for (;;) { 34 if (count == 0) { 35 FutexWait(&state_, 0); 36 count = atomic_load(&state_, memory_order_relaxed); 37 continue; 38 } 39 if (atomic_compare_exchange_weak(&state_, &count, count - 1, 40 memory_order_acquire)) 41 break; 42 } 43 } 44 45 void Semaphore::Post(u32 count) { 46 CHECK_NE(count, 0); 47 atomic_fetch_add(&state_, count, memory_order_release); 48 FutexWake(&state_, count); 49 } 50 51 #if SANITIZER_CHECK_DEADLOCKS 52 // An empty mutex meta table, it effectively disables deadlock detection. 53 // Each tool can override the table to define own mutex hierarchy and 54 // enable deadlock detection. 55 // The table defines a static mutex type hierarchy (what mutex types can be locked 56 // under what mutex types). This table is checked to be acyclic and then 57 // actual mutex lock/unlock operations are checked to adhere to this hierarchy. 58 // The checking happens on mutex types rather than on individual mutex instances 59 // because doing it on mutex instances will both significantly complicate 60 // the implementation, worsen performance and memory overhead and is mostly 61 // unnecessary (we almost never lock multiple mutexes of the same type recursively). 62 static constexpr int kMutexTypeMax = 20; 63 SANITIZER_WEAK_ATTRIBUTE MutexMeta mutex_meta[kMutexTypeMax] = {}; 64 SANITIZER_WEAK_ATTRIBUTE void PrintMutexPC(uptr pc) {} 65 static StaticSpinMutex mutex_meta_mtx; 66 static int mutex_type_count = -1; 67 // Adjacency matrix of what mutexes can be locked under what mutexes. 68 static bool mutex_can_lock[kMutexTypeMax][kMutexTypeMax]; 69 // Mutex types with MutexMulti mark. 70 static bool mutex_multi[kMutexTypeMax]; 71 72 void DebugMutexInit() { 73 // Build adjacency matrix. 74 bool leaf[kMutexTypeMax]; 75 internal_memset(&leaf, 0, sizeof(leaf)); 76 int cnt[kMutexTypeMax] = {}; 77 internal_memset(&cnt, 0, sizeof(cnt)); 78 for (int t = 0; t < kMutexTypeMax; t++) { 79 mutex_type_count = t; 80 if (!mutex_meta[t].name) 81 break; 82 CHECK_EQ(t, mutex_meta[t].type); 83 for (uptr j = 0; j < ARRAY_SIZE(mutex_meta[t].can_lock); j++) { 84 MutexType z = mutex_meta[t].can_lock[j]; 85 if (z == MutexInvalid) 86 break; 87 if (z == MutexLeaf) { 88 CHECK(!leaf[t]); 89 leaf[t] = true; 90 continue; 91 } 92 if (z == MutexMulti) { 93 mutex_multi[t] = true; 94 continue; 95 } 96 CHECK_LT(z, kMutexTypeMax); 97 CHECK(!mutex_can_lock[t][z]); 98 mutex_can_lock[t][z] = true; 99 cnt[t]++; 100 } 101 } 102 // Indicates the array is not properly terminated. 103 CHECK_LT(mutex_type_count, kMutexTypeMax); 104 // Add leaf mutexes. 105 for (int t = 0; t < mutex_type_count; t++) { 106 if (!leaf[t]) 107 continue; 108 CHECK_EQ(cnt[t], 0); 109 for (int z = 0; z < mutex_type_count; z++) { 110 if (z == MutexInvalid || t == z || leaf[z]) 111 continue; 112 CHECK(!mutex_can_lock[z][t]); 113 mutex_can_lock[z][t] = true; 114 } 115 } 116 // Build the transitive closure and check that the graphs is acyclic. 117 u32 trans[kMutexTypeMax]; 118 static_assert(sizeof(trans[0]) * 8 >= kMutexTypeMax, 119 "kMutexTypeMax does not fit into u32, switch to u64"); 120 internal_memset(&trans, 0, sizeof(trans)); 121 for (int i = 0; i < mutex_type_count; i++) { 122 for (int j = 0; j < mutex_type_count; j++) 123 if (mutex_can_lock[i][j]) 124 trans[i] |= 1 << j; 125 } 126 for (int k = 0; k < mutex_type_count; k++) { 127 for (int i = 0; i < mutex_type_count; i++) { 128 if (trans[i] & (1 << k)) 129 trans[i] |= trans[k]; 130 } 131 } 132 for (int i = 0; i < mutex_type_count; i++) { 133 if (trans[i] & (1 << i)) { 134 Printf("Mutex %s participates in a cycle\n", mutex_meta[i].name); 135 Die(); 136 } 137 } 138 } 139 140 struct InternalDeadlockDetector { 141 struct LockDesc { 142 u64 seq; 143 uptr pc; 144 int recursion; 145 }; 146 int initialized; 147 u64 sequence; 148 LockDesc locked[kMutexTypeMax]; 149 150 void Lock(MutexType type, uptr pc) { 151 if (!Initialize(type)) 152 return; 153 CHECK_LT(type, mutex_type_count); 154 // Find the last locked mutex type. 155 // This is the type we will use for hierarchy checks. 156 u64 max_seq = 0; 157 MutexType max_idx = MutexInvalid; 158 for (int i = 0; i != mutex_type_count; i++) { 159 if (locked[i].seq == 0) 160 continue; 161 CHECK_NE(locked[i].seq, max_seq); 162 if (max_seq < locked[i].seq) { 163 max_seq = locked[i].seq; 164 max_idx = (MutexType)i; 165 } 166 } 167 if (max_idx == type && mutex_multi[type]) { 168 // Recursive lock of the same type. 169 CHECK_EQ(locked[type].seq, max_seq); 170 CHECK(locked[type].pc); 171 locked[type].recursion++; 172 return; 173 } 174 if (max_idx != MutexInvalid && !mutex_can_lock[max_idx][type]) { 175 Printf("%s: internal deadlock: can't lock %s under %s mutex\n", SanitizerToolName, 176 mutex_meta[type].name, mutex_meta[max_idx].name); 177 PrintMutexPC(pc); 178 CHECK(0); 179 } 180 locked[type].seq = ++sequence; 181 locked[type].pc = pc; 182 locked[type].recursion = 1; 183 } 184 185 void Unlock(MutexType type) { 186 if (!Initialize(type)) 187 return; 188 CHECK_LT(type, mutex_type_count); 189 CHECK(locked[type].seq); 190 CHECK_GT(locked[type].recursion, 0); 191 if (--locked[type].recursion) 192 return; 193 locked[type].seq = 0; 194 locked[type].pc = 0; 195 } 196 197 void CheckNoLocks() { 198 for (int i = 0; i < mutex_type_count; i++) CHECK_EQ(locked[i].recursion, 0); 199 } 200 201 bool Initialize(MutexType type) { 202 if (type == MutexUnchecked || type == MutexInvalid) 203 return false; 204 CHECK_GT(type, MutexInvalid); 205 if (initialized != 0) 206 return initialized > 0; 207 initialized = -1; 208 SpinMutexLock lock(&mutex_meta_mtx); 209 if (mutex_type_count < 0) 210 DebugMutexInit(); 211 initialized = mutex_type_count ? 1 : -1; 212 return initialized > 0; 213 } 214 }; 215 216 static THREADLOCAL InternalDeadlockDetector deadlock_detector; 217 218 void CheckedMutex::LockImpl(uptr pc) { deadlock_detector.Lock(type_, pc); } 219 220 void CheckedMutex::UnlockImpl() { deadlock_detector.Unlock(type_); } 221 222 void CheckedMutex::CheckNoLocksImpl() { deadlock_detector.CheckNoLocks(); } 223 #endif 224 225 } // namespace __sanitizer 226