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(locked[max_idx].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