1//===-- sanitizer_deadlock_detector2.cc -----------------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// Deadlock detector implementation based on adjacency lists. 11// 12//===----------------------------------------------------------------------===// 13 14#include "sanitizer_deadlock_detector_interface.h" 15#include "sanitizer_common.h" 16#include "sanitizer_allocator_internal.h" 17#include "sanitizer_placement_new.h" 18#include "sanitizer_mutex.h" 19 20#if SANITIZER_DEADLOCK_DETECTOR_VERSION == 2 21 22namespace __sanitizer { 23 24const int kMaxNesting = 64; 25const u32 kNoId = -1; 26const u32 kEndId = -2; 27const int kMaxLink = 8; 28const int kL1Size = 1024; 29const int kL2Size = 1024; 30const int kMaxMutex = kL1Size * kL2Size; 31 32struct Id { 33 u32 id; 34 u32 seq; 35 36 explicit Id(u32 id = 0, u32 seq = 0) 37 : id(id) 38 , seq(seq) { 39 } 40}; 41 42struct Link { 43 u32 id; 44 u32 seq; 45 u32 tid; 46 u32 stk0; 47 u32 stk1; 48 49 explicit Link(u32 id = 0, u32 seq = 0, u32 tid = 0, u32 s0 = 0, u32 s1 = 0) 50 : id(id) 51 , seq(seq) 52 , tid(tid) 53 , stk0(s0) 54 , stk1(s1) { 55 } 56}; 57 58struct DDPhysicalThread { 59 DDReport rep; 60 bool report_pending; 61 bool visited[kMaxMutex]; 62 Link pending[kMaxMutex]; 63 Link path[kMaxMutex]; 64}; 65 66struct ThreadMutex { 67 u32 id; 68 u32 stk; 69}; 70 71struct DDLogicalThread { 72 u64 ctx; 73 ThreadMutex locked[kMaxNesting]; 74 int nlocked; 75}; 76 77struct Mutex { 78 StaticSpinMutex mtx; 79 u32 seq; 80 int nlink; 81 Link link[kMaxLink]; 82}; 83 84struct DD : public DDetector { 85 explicit DD(const DDFlags *flags); 86 87 DDPhysicalThread* CreatePhysicalThread(); 88 void DestroyPhysicalThread(DDPhysicalThread *pt); 89 90 DDLogicalThread* CreateLogicalThread(u64 ctx); 91 void DestroyLogicalThread(DDLogicalThread *lt); 92 93 void MutexInit(DDCallback *cb, DDMutex *m); 94 void MutexBeforeLock(DDCallback *cb, DDMutex *m, bool wlock); 95 void MutexAfterLock(DDCallback *cb, DDMutex *m, bool wlock, 96 bool trylock); 97 void MutexBeforeUnlock(DDCallback *cb, DDMutex *m, bool wlock); 98 void MutexDestroy(DDCallback *cb, DDMutex *m); 99 100 DDReport *GetReport(DDCallback *cb); 101 102 void CycleCheck(DDPhysicalThread *pt, DDLogicalThread *lt, DDMutex *mtx); 103 void Report(DDPhysicalThread *pt, DDLogicalThread *lt, int npath); 104 u32 allocateId(DDCallback *cb); 105 Mutex *getMutex(u32 id); 106 u32 getMutexId(Mutex *m); 107 108 DDFlags flags; 109 110 Mutex* mutex[kL1Size]; 111 112 SpinMutex mtx; 113 InternalMmapVector<u32> free_id; 114 int id_gen = 0; 115}; 116 117DDetector *DDetector::Create(const DDFlags *flags) { 118 (void)flags; 119 void *mem = MmapOrDie(sizeof(DD), "deadlock detector"); 120 return new(mem) DD(flags); 121} 122 123DD::DD(const DDFlags *flags) : flags(*flags) { free_id.reserve(1024); } 124 125DDPhysicalThread* DD::CreatePhysicalThread() { 126 DDPhysicalThread *pt = (DDPhysicalThread*)MmapOrDie(sizeof(DDPhysicalThread), 127 "deadlock detector (physical thread)"); 128 return pt; 129} 130 131void DD::DestroyPhysicalThread(DDPhysicalThread *pt) { 132 pt->~DDPhysicalThread(); 133 UnmapOrDie(pt, sizeof(DDPhysicalThread)); 134} 135 136DDLogicalThread* DD::CreateLogicalThread(u64 ctx) { 137 DDLogicalThread *lt = (DDLogicalThread*)InternalAlloc( 138 sizeof(DDLogicalThread)); 139 lt->ctx = ctx; 140 lt->nlocked = 0; 141 return lt; 142} 143 144void DD::DestroyLogicalThread(DDLogicalThread *lt) { 145 lt->~DDLogicalThread(); 146 InternalFree(lt); 147} 148 149void DD::MutexInit(DDCallback *cb, DDMutex *m) { 150 VPrintf(2, "#%llu: DD::MutexInit(%p)\n", cb->lt->ctx, m); 151 m->id = kNoId; 152 m->recursion = 0; 153 atomic_store(&m->owner, 0, memory_order_relaxed); 154} 155 156Mutex *DD::getMutex(u32 id) { 157 return &mutex[id / kL2Size][id % kL2Size]; 158} 159 160u32 DD::getMutexId(Mutex *m) { 161 for (int i = 0; i < kL1Size; i++) { 162 Mutex *tab = mutex[i]; 163 if (tab == 0) 164 break; 165 if (m >= tab && m < tab + kL2Size) 166 return i * kL2Size + (m - tab); 167 } 168 return -1; 169} 170 171u32 DD::allocateId(DDCallback *cb) { 172 u32 id = -1; 173 SpinMutexLock l(&mtx); 174 if (free_id.size() > 0) { 175 id = free_id.back(); 176 free_id.pop_back(); 177 } else { 178 CHECK_LT(id_gen, kMaxMutex); 179 if ((id_gen % kL2Size) == 0) { 180 mutex[id_gen / kL2Size] = (Mutex*)MmapOrDie(kL2Size * sizeof(Mutex), 181 "deadlock detector (mutex table)"); 182 } 183 id = id_gen++; 184 } 185 CHECK_LE(id, kMaxMutex); 186 VPrintf(3, "#%llu: DD::allocateId assign id %d\n", cb->lt->ctx, id); 187 return id; 188} 189 190void DD::MutexBeforeLock(DDCallback *cb, DDMutex *m, bool wlock) { 191 VPrintf(2, "#%llu: DD::MutexBeforeLock(%p, wlock=%d) nlocked=%d\n", 192 cb->lt->ctx, m, wlock, cb->lt->nlocked); 193 DDPhysicalThread *pt = cb->pt; 194 DDLogicalThread *lt = cb->lt; 195 196 uptr owner = atomic_load(&m->owner, memory_order_relaxed); 197 if (owner == (uptr)cb->lt) { 198 VPrintf(3, "#%llu: DD::MutexBeforeLock recursive\n", 199 cb->lt->ctx); 200 return; 201 } 202 203 CHECK_LE(lt->nlocked, kMaxNesting); 204 205 // FIXME(dvyukov): don't allocate id if lt->nlocked == 0? 206 if (m->id == kNoId) 207 m->id = allocateId(cb); 208 209 ThreadMutex *tm = <->locked[lt->nlocked++]; 210 tm->id = m->id; 211 if (flags.second_deadlock_stack) 212 tm->stk = cb->Unwind(); 213 if (lt->nlocked == 1) { 214 VPrintf(3, "#%llu: DD::MutexBeforeLock first mutex\n", 215 cb->lt->ctx); 216 return; 217 } 218 219 bool added = false; 220 Mutex *mtx = getMutex(m->id); 221 for (int i = 0; i < lt->nlocked - 1; i++) { 222 u32 id1 = lt->locked[i].id; 223 u32 stk1 = lt->locked[i].stk; 224 Mutex *mtx1 = getMutex(id1); 225 SpinMutexLock l(&mtx1->mtx); 226 if (mtx1->nlink == kMaxLink) { 227 // FIXME(dvyukov): check stale links 228 continue; 229 } 230 int li = 0; 231 for (; li < mtx1->nlink; li++) { 232 Link *link = &mtx1->link[li]; 233 if (link->id == m->id) { 234 if (link->seq != mtx->seq) { 235 link->seq = mtx->seq; 236 link->tid = lt->ctx; 237 link->stk0 = stk1; 238 link->stk1 = cb->Unwind(); 239 added = true; 240 VPrintf(3, "#%llu: DD::MutexBeforeLock added %d->%d link\n", 241 cb->lt->ctx, getMutexId(mtx1), m->id); 242 } 243 break; 244 } 245 } 246 if (li == mtx1->nlink) { 247 // FIXME(dvyukov): check stale links 248 Link *link = &mtx1->link[mtx1->nlink++]; 249 link->id = m->id; 250 link->seq = mtx->seq; 251 link->tid = lt->ctx; 252 link->stk0 = stk1; 253 link->stk1 = cb->Unwind(); 254 added = true; 255 VPrintf(3, "#%llu: DD::MutexBeforeLock added %d->%d link\n", 256 cb->lt->ctx, getMutexId(mtx1), m->id); 257 } 258 } 259 260 if (!added || mtx->nlink == 0) { 261 VPrintf(3, "#%llu: DD::MutexBeforeLock don't check\n", 262 cb->lt->ctx); 263 return; 264 } 265 266 CycleCheck(pt, lt, m); 267} 268 269void DD::MutexAfterLock(DDCallback *cb, DDMutex *m, bool wlock, 270 bool trylock) { 271 VPrintf(2, "#%llu: DD::MutexAfterLock(%p, wlock=%d, try=%d) nlocked=%d\n", 272 cb->lt->ctx, m, wlock, trylock, cb->lt->nlocked); 273 DDLogicalThread *lt = cb->lt; 274 275 uptr owner = atomic_load(&m->owner, memory_order_relaxed); 276 if (owner == (uptr)cb->lt) { 277 VPrintf(3, "#%llu: DD::MutexAfterLock recursive\n", cb->lt->ctx); 278 CHECK(wlock); 279 m->recursion++; 280 return; 281 } 282 CHECK_EQ(owner, 0); 283 if (wlock) { 284 VPrintf(3, "#%llu: DD::MutexAfterLock set owner\n", cb->lt->ctx); 285 CHECK_EQ(m->recursion, 0); 286 m->recursion = 1; 287 atomic_store(&m->owner, (uptr)cb->lt, memory_order_relaxed); 288 } 289 290 if (!trylock) 291 return; 292 293 CHECK_LE(lt->nlocked, kMaxNesting); 294 if (m->id == kNoId) 295 m->id = allocateId(cb); 296 ThreadMutex *tm = <->locked[lt->nlocked++]; 297 tm->id = m->id; 298 if (flags.second_deadlock_stack) 299 tm->stk = cb->Unwind(); 300} 301 302void DD::MutexBeforeUnlock(DDCallback *cb, DDMutex *m, bool wlock) { 303 VPrintf(2, "#%llu: DD::MutexBeforeUnlock(%p, wlock=%d) nlocked=%d\n", 304 cb->lt->ctx, m, wlock, cb->lt->nlocked); 305 DDLogicalThread *lt = cb->lt; 306 307 uptr owner = atomic_load(&m->owner, memory_order_relaxed); 308 if (owner == (uptr)cb->lt) { 309 VPrintf(3, "#%llu: DD::MutexBeforeUnlock recursive\n", cb->lt->ctx); 310 if (--m->recursion > 0) 311 return; 312 VPrintf(3, "#%llu: DD::MutexBeforeUnlock reset owner\n", cb->lt->ctx); 313 atomic_store(&m->owner, 0, memory_order_relaxed); 314 } 315 CHECK_NE(m->id, kNoId); 316 int last = lt->nlocked - 1; 317 for (int i = last; i >= 0; i--) { 318 if (cb->lt->locked[i].id == m->id) { 319 lt->locked[i] = lt->locked[last]; 320 lt->nlocked--; 321 break; 322 } 323 } 324} 325 326void DD::MutexDestroy(DDCallback *cb, DDMutex *m) { 327 VPrintf(2, "#%llu: DD::MutexDestroy(%p)\n", 328 cb->lt->ctx, m); 329 DDLogicalThread *lt = cb->lt; 330 331 if (m->id == kNoId) 332 return; 333 334 // Remove the mutex from lt->locked if there. 335 int last = lt->nlocked - 1; 336 for (int i = last; i >= 0; i--) { 337 if (lt->locked[i].id == m->id) { 338 lt->locked[i] = lt->locked[last]; 339 lt->nlocked--; 340 break; 341 } 342 } 343 344 // Clear and invalidate the mutex descriptor. 345 { 346 Mutex *mtx = getMutex(m->id); 347 SpinMutexLock l(&mtx->mtx); 348 mtx->seq++; 349 mtx->nlink = 0; 350 } 351 352 // Return id to cache. 353 { 354 SpinMutexLock l(&mtx); 355 free_id.push_back(m->id); 356 } 357} 358 359void DD::CycleCheck(DDPhysicalThread *pt, DDLogicalThread *lt, 360 DDMutex *m) { 361 internal_memset(pt->visited, 0, sizeof(pt->visited)); 362 int npath = 0; 363 int npending = 0; 364 { 365 Mutex *mtx = getMutex(m->id); 366 SpinMutexLock l(&mtx->mtx); 367 for (int li = 0; li < mtx->nlink; li++) 368 pt->pending[npending++] = mtx->link[li]; 369 } 370 while (npending > 0) { 371 Link link = pt->pending[--npending]; 372 if (link.id == kEndId) { 373 npath--; 374 continue; 375 } 376 if (pt->visited[link.id]) 377 continue; 378 Mutex *mtx1 = getMutex(link.id); 379 SpinMutexLock l(&mtx1->mtx); 380 if (mtx1->seq != link.seq) 381 continue; 382 pt->visited[link.id] = true; 383 if (mtx1->nlink == 0) 384 continue; 385 pt->path[npath++] = link; 386 pt->pending[npending++] = Link(kEndId); 387 if (link.id == m->id) 388 return Report(pt, lt, npath); // Bingo! 389 for (int li = 0; li < mtx1->nlink; li++) { 390 Link *link1 = &mtx1->link[li]; 391 // Mutex *mtx2 = getMutex(link->id); 392 // FIXME(dvyukov): fast seq check 393 // FIXME(dvyukov): fast nlink != 0 check 394 // FIXME(dvyukov): fast pending check? 395 // FIXME(dvyukov): npending can be larger than kMaxMutex 396 pt->pending[npending++] = *link1; 397 } 398 } 399} 400 401void DD::Report(DDPhysicalThread *pt, DDLogicalThread *lt, int npath) { 402 DDReport *rep = &pt->rep; 403 rep->n = npath; 404 for (int i = 0; i < npath; i++) { 405 Link *link = &pt->path[i]; 406 Link *link0 = &pt->path[i ? i - 1 : npath - 1]; 407 rep->loop[i].thr_ctx = link->tid; 408 rep->loop[i].mtx_ctx0 = link0->id; 409 rep->loop[i].mtx_ctx1 = link->id; 410 rep->loop[i].stk[0] = flags.second_deadlock_stack ? link->stk0 : 0; 411 rep->loop[i].stk[1] = link->stk1; 412 } 413 pt->report_pending = true; 414} 415 416DDReport *DD::GetReport(DDCallback *cb) { 417 if (!cb->pt->report_pending) 418 return 0; 419 cb->pt->report_pending = false; 420 return &cb->pt->rep; 421} 422 423} // namespace __sanitizer 424#endif // #if SANITIZER_DEADLOCK_DETECTOR_VERSION == 2 425