1200590Sluigi//===-- sanitizer_deadlock_detector2.cc -----------------------------------===// 2200673Sru// 3200590Sluigi// The LLVM Compiler Infrastructure 4200590Sluigi// 5200590Sluigi// This file is distributed under the University of Illinois Open Source 6200590Sluigi// License. See LICENSE.TXT for details. 7200590Sluigi// 8200590Sluigi//===----------------------------------------------------------------------===// 9200590Sluigi// 10200590Sluigi// Deadlock detector implementation based on adjacency lists. 11200590Sluigi// 12200590Sluigi//===----------------------------------------------------------------------===// 13200590Sluigi 14200590Sluigi#include "sanitizer_deadlock_detector_interface.h" 15200590Sluigi#include "sanitizer_common.h" 16200590Sluigi#include "sanitizer_allocator_internal.h" 17200590Sluigi#include "sanitizer_placement_new.h" 18200590Sluigi#include "sanitizer_mutex.h" 19200590Sluigi 20200590Sluigi#if SANITIZER_DEADLOCK_DETECTOR_VERSION == 2 21200590Sluigi 22200590Sluiginamespace __sanitizer { 23200590Sluigi 24200590Sluigiconst int kMaxNesting = 64; 25200590Sluigiconst u32 kNoId = -1; 26200590Sluigiconst u32 kEndId = -2; 27200590Sluigiconst int kMaxLink = 8; 28200590Sluigiconst int kL1Size = 1024; 29200590Sluigiconst int kL2Size = 1024; 30200601Sluigiconst int kMaxMutex = kL1Size * kL2Size; 31200601Sluigi 32200601Sluigistruct Id { 33200601Sluigi u32 id; 34200601Sluigi u32 seq; 35200601Sluigi 36200601Sluigi explicit Id(u32 id = 0, u32 seq = 0) 37200838Sluigi : id(id) 38200838Sluigi , seq(seq) { 39200838Sluigi } 40200590Sluigi}; 41200590Sluigi 42200590Sluigistruct Link { 43200590Sluigi u32 id; 44200590Sluigi u32 seq; 45200590Sluigi u32 tid; 46200590Sluigi u32 stk0; 47200590Sluigi u32 stk1; 48200590Sluigi 49200590Sluigi explicit Link(u32 id = 0, u32 seq = 0, u32 tid = 0, u32 s0 = 0, u32 s1 = 0) 50200590Sluigi : id(id) 51200590Sluigi , seq(seq) 52200590Sluigi , tid(tid) 53200590Sluigi , stk0(s0) 54200590Sluigi , stk1(s1) { 55200590Sluigi } 56200590Sluigi}; 57200590Sluigi 58200590Sluigistruct DDPhysicalThread { 59200590Sluigi DDReport rep; 60200590Sluigi bool report_pending; 61200590Sluigi bool visited[kMaxMutex]; 62200590Sluigi Link pending[kMaxMutex]; 63200590Sluigi Link path[kMaxMutex]; 64200590Sluigi}; 65200590Sluigi 66200590Sluigistruct ThreadMutex { 67201732Sluigi u32 id; 68200590Sluigi u32 stk; 69204591Sluigi}; 70200590Sluigi 71200590Sluigistruct DDLogicalThread { 72200590Sluigi u64 ctx; 73200590Sluigi ThreadMutex locked[kMaxNesting]; 74200590Sluigi int nlocked; 75200590Sluigi}; 76200590Sluigi 77200590Sluigistruct Mutex { 78200590Sluigi StaticSpinMutex mtx; 79200590Sluigi u32 seq; 80200590Sluigi int nlink; 81200590Sluigi Link link[kMaxLink]; 82200590Sluigi}; 83200590Sluigi 84201120Sluigistruct DD : public DDetector { 85201120Sluigi explicit DD(const DDFlags *flags); 86201120Sluigi 87201120Sluigi DDPhysicalThread* CreatePhysicalThread(); 88201120Sluigi void DestroyPhysicalThread(DDPhysicalThread *pt); 89201120Sluigi 90201120Sluigi DDLogicalThread* CreateLogicalThread(u64 ctx); 91201120Sluigi void DestroyLogicalThread(DDLogicalThread *lt); 92201120Sluigi 93201120Sluigi void MutexInit(DDCallback *cb, DDMutex *m); 94201120Sluigi void MutexBeforeLock(DDCallback *cb, DDMutex *m, bool wlock); 95201120Sluigi void MutexAfterLock(DDCallback *cb, DDMutex *m, bool wlock, 96200590Sluigi bool trylock); 97200590Sluigi void MutexBeforeUnlock(DDCallback *cb, DDMutex *m, bool wlock); 98200590Sluigi void MutexDestroy(DDCallback *cb, DDMutex *m); 99200590Sluigi 100200590Sluigi DDReport *GetReport(DDCallback *cb); 101200590Sluigi 102200590Sluigi void CycleCheck(DDPhysicalThread *pt, DDLogicalThread *lt, DDMutex *mtx); 103200590Sluigi void Report(DDPhysicalThread *pt, DDLogicalThread *lt, int npath); 104200590Sluigi u32 allocateId(DDCallback *cb); 105200590Sluigi Mutex *getMutex(u32 id); 106200590Sluigi u32 getMutexId(Mutex *m); 107200590Sluigi 108200590Sluigi DDFlags flags; 109200590Sluigi 110200590Sluigi Mutex* mutex[kL1Size]; 111201120Sluigi 112200590Sluigi SpinMutex mtx; 113200590Sluigi InternalMmapVector<u32> free_id; 114200590Sluigi int id_gen = 0; 115200590Sluigi}; 116200590Sluigi 117200590SluigiDDetector *DDetector::Create(const DDFlags *flags) { 118200590Sluigi (void)flags; 119200590Sluigi void *mem = MmapOrDie(sizeof(DD), "deadlock detector"); 120200590Sluigi return new(mem) DD(flags); 121200590Sluigi} 122200590Sluigi 123200590SluigiDD::DD(const DDFlags *flags) : flags(*flags) { free_id.reserve(1024); } 124200590Sluigi 125200590SluigiDDPhysicalThread* DD::CreatePhysicalThread() { 126200590Sluigi DDPhysicalThread *pt = (DDPhysicalThread*)MmapOrDie(sizeof(DDPhysicalThread), 127200590Sluigi "deadlock detector (physical thread)"); 128200590Sluigi return pt; 129200590Sluigi} 130200590Sluigi 131200590Sluigivoid DD::DestroyPhysicalThread(DDPhysicalThread *pt) { 132200590Sluigi pt->~DDPhysicalThread(); 133200590Sluigi UnmapOrDie(pt, sizeof(DDPhysicalThread)); 134200590Sluigi} 135200590Sluigi 136201120SluigiDDLogicalThread* DD::CreateLogicalThread(u64 ctx) { 137200590Sluigi DDLogicalThread *lt = (DDLogicalThread*)InternalAlloc( 138200590Sluigi sizeof(DDLogicalThread)); 139200590Sluigi lt->ctx = ctx; 140200590Sluigi lt->nlocked = 0; 141200590Sluigi return lt; 142200590Sluigi} 143200590Sluigi 144200590Sluigivoid DD::DestroyLogicalThread(DDLogicalThread *lt) { 145200590Sluigi lt->~DDLogicalThread(); 146200590Sluigi InternalFree(lt); 147200590Sluigi} 148200590Sluigi 149200590Sluigivoid DD::MutexInit(DDCallback *cb, DDMutex *m) { 150200590Sluigi VPrintf(2, "#%llu: DD::MutexInit(%p)\n", cb->lt->ctx, m); 151200590Sluigi m->id = kNoId; 152200590Sluigi m->recursion = 0; 153200590Sluigi atomic_store(&m->owner, 0, memory_order_relaxed); 154200590Sluigi} 155200590Sluigi 156200590SluigiMutex *DD::getMutex(u32 id) { 157200590Sluigi return &mutex[id / kL2Size][id % kL2Size]; 158200590Sluigi} 159200590Sluigi 160200590Sluigiu32 DD::getMutexId(Mutex *m) { 161200590Sluigi for (int i = 0; i < kL1Size; i++) { 162200590Sluigi Mutex *tab = mutex[i]; 163200590Sluigi if (tab == 0) 164200590Sluigi break; 165200590Sluigi if (m >= tab && m < tab + kL2Size) 166200590Sluigi return i * kL2Size + (m - tab); 167200590Sluigi } 168200590Sluigi return -1; 169200590Sluigi} 170200590Sluigi 171200590Sluigiu32 DD::allocateId(DDCallback *cb) { 172200590Sluigi u32 id = -1; 173200590Sluigi SpinMutexLock l(&mtx); 174200590Sluigi if (free_id.size() > 0) { 175200590Sluigi id = free_id.back(); 176200590Sluigi free_id.pop_back(); 177200590Sluigi } else { 178200590Sluigi CHECK_LT(id_gen, kMaxMutex); 179200590Sluigi if ((id_gen % kL2Size) == 0) { 180200590Sluigi mutex[id_gen / kL2Size] = (Mutex*)MmapOrDie(kL2Size * sizeof(Mutex), 181200590Sluigi "deadlock detector (mutex table)"); 182200590Sluigi } 183200590Sluigi id = id_gen++; 184200590Sluigi } 185200590Sluigi CHECK_LE(id, kMaxMutex); 186200590Sluigi VPrintf(3, "#%llu: DD::allocateId assign id %d\n", cb->lt->ctx, id); 187200590Sluigi return id; 188200590Sluigi} 189200590Sluigi 190200590Sluigivoid DD::MutexBeforeLock(DDCallback *cb, DDMutex *m, bool wlock) { 191200590Sluigi VPrintf(2, "#%llu: DD::MutexBeforeLock(%p, wlock=%d) nlocked=%d\n", 192200590Sluigi cb->lt->ctx, m, wlock, cb->lt->nlocked); 193200590Sluigi DDPhysicalThread *pt = cb->pt; 194200590Sluigi DDLogicalThread *lt = cb->lt; 195200590Sluigi 196201120Sluigi uptr owner = atomic_load(&m->owner, memory_order_relaxed); 197200590Sluigi if (owner == (uptr)cb->lt) { 198200590Sluigi VPrintf(3, "#%llu: DD::MutexBeforeLock recursive\n", 199200590Sluigi cb->lt->ctx); 200200590Sluigi return; 201200590Sluigi } 202200590Sluigi 203200590Sluigi CHECK_LE(lt->nlocked, kMaxNesting); 204200590Sluigi 205200590Sluigi // FIXME(dvyukov): don't allocate id if lt->nlocked == 0? 206200590Sluigi if (m->id == kNoId) 207200590Sluigi m->id = allocateId(cb); 208200590Sluigi 209200590Sluigi ThreadMutex *tm = <->locked[lt->nlocked++]; 210200590Sluigi tm->id = m->id; 211200590Sluigi if (flags.second_deadlock_stack) 212200590Sluigi tm->stk = cb->Unwind(); 213200590Sluigi if (lt->nlocked == 1) { 214200590Sluigi VPrintf(3, "#%llu: DD::MutexBeforeLock first mutex\n", 215200590Sluigi cb->lt->ctx); 216200590Sluigi return; 217201120Sluigi } 218200590Sluigi 219200590Sluigi bool added = false; 220200590Sluigi Mutex *mtx = getMutex(m->id); 221200590Sluigi for (int i = 0; i < lt->nlocked - 1; i++) { 222200590Sluigi u32 id1 = lt->locked[i].id; 223200590Sluigi u32 stk1 = lt->locked[i].stk; 224200590Sluigi Mutex *mtx1 = getMutex(id1); 225200590Sluigi SpinMutexLock l(&mtx1->mtx); 226200590Sluigi if (mtx1->nlink == kMaxLink) { 227200590Sluigi // FIXME(dvyukov): check stale links 228200590Sluigi continue; 229200590Sluigi } 230200590Sluigi int li = 0; 231200590Sluigi for (; li < mtx1->nlink; li++) { 232200590Sluigi Link *link = &mtx1->link[li]; 233200590Sluigi if (link->id == m->id) { 234200590Sluigi if (link->seq != mtx->seq) { 235200590Sluigi link->seq = mtx->seq; 236200590Sluigi link->tid = lt->ctx; 237200590Sluigi link->stk0 = stk1; 238200590Sluigi link->stk1 = cb->Unwind(); 239200590Sluigi added = true; 240200590Sluigi VPrintf(3, "#%llu: DD::MutexBeforeLock added %d->%d link\n", 241200590Sluigi cb->lt->ctx, getMutexId(mtx1), m->id); 242200590Sluigi } 243200590Sluigi break; 244200590Sluigi } 245200590Sluigi } 246200590Sluigi if (li == mtx1->nlink) { 247200590Sluigi // FIXME(dvyukov): check stale links 248200590Sluigi Link *link = &mtx1->link[mtx1->nlink++]; 249200590Sluigi link->id = m->id; 250200590Sluigi link->seq = mtx->seq; 251200590Sluigi link->tid = lt->ctx; 252200590Sluigi link->stk0 = stk1; 253200590Sluigi link->stk1 = cb->Unwind(); 254200590Sluigi added = true; 255200590Sluigi VPrintf(3, "#%llu: DD::MutexBeforeLock added %d->%d link\n", 256200590Sluigi cb->lt->ctx, getMutexId(mtx1), m->id); 257200590Sluigi } 258200590Sluigi } 259200590Sluigi 260200590Sluigi if (!added || mtx->nlink == 0) { 261200590Sluigi VPrintf(3, "#%llu: DD::MutexBeforeLock don't check\n", 262200590Sluigi cb->lt->ctx); 263200590Sluigi return; 264200590Sluigi } 265200590Sluigi 266200590Sluigi CycleCheck(pt, lt, m); 267200590Sluigi} 268200590Sluigi 269200590Sluigivoid DD::MutexAfterLock(DDCallback *cb, DDMutex *m, bool wlock, 270200590Sluigi bool trylock) { 271200590Sluigi VPrintf(2, "#%llu: DD::MutexAfterLock(%p, wlock=%d, try=%d) nlocked=%d\n", 272200590Sluigi cb->lt->ctx, m, wlock, trylock, cb->lt->nlocked); 273200590Sluigi DDLogicalThread *lt = cb->lt; 274200590Sluigi 275200590Sluigi uptr owner = atomic_load(&m->owner, memory_order_relaxed); 276200590Sluigi if (owner == (uptr)cb->lt) { 277200590Sluigi VPrintf(3, "#%llu: DD::MutexAfterLock recursive\n", cb->lt->ctx); 278200590Sluigi CHECK(wlock); 279200590Sluigi m->recursion++; 280200590Sluigi return; 281200590Sluigi } 282200601Sluigi 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