1353944Sdim//===-- sanitizer_deadlock_detector2.cpp ----------------------------------===// 2353944Sdim// 3353944Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353944Sdim// See https://llvm.org/LICENSE.txt for license information. 5353944Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6353944Sdim// 7353944Sdim//===----------------------------------------------------------------------===// 8353944Sdim// 9353944Sdim// Deadlock detector implementation based on adjacency lists. 10353944Sdim// 11353944Sdim//===----------------------------------------------------------------------===// 12353944Sdim 13353944Sdim#include "sanitizer_deadlock_detector_interface.h" 14353944Sdim#include "sanitizer_common.h" 15353944Sdim#include "sanitizer_allocator_internal.h" 16353944Sdim#include "sanitizer_placement_new.h" 17353944Sdim#include "sanitizer_mutex.h" 18353944Sdim 19353944Sdim#if SANITIZER_DEADLOCK_DETECTOR_VERSION == 2 20353944Sdim 21353944Sdimnamespace __sanitizer { 22353944Sdim 23353944Sdimconst int kMaxNesting = 64; 24353944Sdimconst u32 kNoId = -1; 25353944Sdimconst u32 kEndId = -2; 26353944Sdimconst int kMaxLink = 8; 27353944Sdimconst int kL1Size = 1024; 28353944Sdimconst int kL2Size = 1024; 29353944Sdimconst int kMaxMutex = kL1Size * kL2Size; 30353944Sdim 31353944Sdimstruct Id { 32353944Sdim u32 id; 33353944Sdim u32 seq; 34353944Sdim 35353944Sdim explicit Id(u32 id = 0, u32 seq = 0) 36353944Sdim : id(id) 37353944Sdim , seq(seq) { 38353944Sdim } 39353944Sdim}; 40353944Sdim 41353944Sdimstruct Link { 42353944Sdim u32 id; 43353944Sdim u32 seq; 44353944Sdim u32 tid; 45353944Sdim u32 stk0; 46353944Sdim u32 stk1; 47353944Sdim 48353944Sdim explicit Link(u32 id = 0, u32 seq = 0, u32 tid = 0, u32 s0 = 0, u32 s1 = 0) 49353944Sdim : id(id) 50353944Sdim , seq(seq) 51353944Sdim , tid(tid) 52353944Sdim , stk0(s0) 53353944Sdim , stk1(s1) { 54353944Sdim } 55353944Sdim}; 56353944Sdim 57353944Sdimstruct DDPhysicalThread { 58353944Sdim DDReport rep; 59353944Sdim bool report_pending; 60353944Sdim bool visited[kMaxMutex]; 61353944Sdim Link pending[kMaxMutex]; 62353944Sdim Link path[kMaxMutex]; 63353944Sdim}; 64353944Sdim 65353944Sdimstruct ThreadMutex { 66353944Sdim u32 id; 67353944Sdim u32 stk; 68353944Sdim}; 69353944Sdim 70353944Sdimstruct DDLogicalThread { 71353944Sdim u64 ctx; 72353944Sdim ThreadMutex locked[kMaxNesting]; 73353944Sdim int nlocked; 74353944Sdim}; 75353944Sdim 76353944Sdimstruct Mutex { 77353944Sdim StaticSpinMutex mtx; 78353944Sdim u32 seq; 79353944Sdim int nlink; 80353944Sdim Link link[kMaxLink]; 81353944Sdim}; 82353944Sdim 83353944Sdimstruct DD : public DDetector { 84353944Sdim explicit DD(const DDFlags *flags); 85353944Sdim 86353944Sdim DDPhysicalThread* CreatePhysicalThread(); 87353944Sdim void DestroyPhysicalThread(DDPhysicalThread *pt); 88353944Sdim 89353944Sdim DDLogicalThread* CreateLogicalThread(u64 ctx); 90353944Sdim void DestroyLogicalThread(DDLogicalThread *lt); 91353944Sdim 92353944Sdim void MutexInit(DDCallback *cb, DDMutex *m); 93353944Sdim void MutexBeforeLock(DDCallback *cb, DDMutex *m, bool wlock); 94353944Sdim void MutexAfterLock(DDCallback *cb, DDMutex *m, bool wlock, 95353944Sdim bool trylock); 96353944Sdim void MutexBeforeUnlock(DDCallback *cb, DDMutex *m, bool wlock); 97353944Sdim void MutexDestroy(DDCallback *cb, DDMutex *m); 98353944Sdim 99353944Sdim DDReport *GetReport(DDCallback *cb); 100353944Sdim 101353944Sdim void CycleCheck(DDPhysicalThread *pt, DDLogicalThread *lt, DDMutex *mtx); 102353944Sdim void Report(DDPhysicalThread *pt, DDLogicalThread *lt, int npath); 103353944Sdim u32 allocateId(DDCallback *cb); 104353944Sdim Mutex *getMutex(u32 id); 105353944Sdim u32 getMutexId(Mutex *m); 106353944Sdim 107353944Sdim DDFlags flags; 108353944Sdim 109353944Sdim Mutex* mutex[kL1Size]; 110353944Sdim 111353944Sdim SpinMutex mtx; 112353944Sdim InternalMmapVector<u32> free_id; 113353944Sdim int id_gen = 0; 114353944Sdim}; 115353944Sdim 116353944SdimDDetector *DDetector::Create(const DDFlags *flags) { 117353944Sdim (void)flags; 118353944Sdim void *mem = MmapOrDie(sizeof(DD), "deadlock detector"); 119353944Sdim return new(mem) DD(flags); 120353944Sdim} 121353944Sdim 122353944SdimDD::DD(const DDFlags *flags) : flags(*flags) { free_id.reserve(1024); } 123353944Sdim 124353944SdimDDPhysicalThread* DD::CreatePhysicalThread() { 125353944Sdim DDPhysicalThread *pt = (DDPhysicalThread*)MmapOrDie(sizeof(DDPhysicalThread), 126353944Sdim "deadlock detector (physical thread)"); 127353944Sdim return pt; 128353944Sdim} 129353944Sdim 130353944Sdimvoid DD::DestroyPhysicalThread(DDPhysicalThread *pt) { 131353944Sdim pt->~DDPhysicalThread(); 132353944Sdim UnmapOrDie(pt, sizeof(DDPhysicalThread)); 133353944Sdim} 134353944Sdim 135353944SdimDDLogicalThread* DD::CreateLogicalThread(u64 ctx) { 136353944Sdim DDLogicalThread *lt = (DDLogicalThread*)InternalAlloc( 137353944Sdim sizeof(DDLogicalThread)); 138353944Sdim lt->ctx = ctx; 139353944Sdim lt->nlocked = 0; 140353944Sdim return lt; 141353944Sdim} 142353944Sdim 143353944Sdimvoid DD::DestroyLogicalThread(DDLogicalThread *lt) { 144353944Sdim lt->~DDLogicalThread(); 145353944Sdim InternalFree(lt); 146353944Sdim} 147353944Sdim 148353944Sdimvoid DD::MutexInit(DDCallback *cb, DDMutex *m) { 149353944Sdim VPrintf(2, "#%llu: DD::MutexInit(%p)\n", cb->lt->ctx, m); 150353944Sdim m->id = kNoId; 151353944Sdim m->recursion = 0; 152353944Sdim atomic_store(&m->owner, 0, memory_order_relaxed); 153353944Sdim} 154353944Sdim 155353944SdimMutex *DD::getMutex(u32 id) { 156353944Sdim return &mutex[id / kL2Size][id % kL2Size]; 157353944Sdim} 158353944Sdim 159353944Sdimu32 DD::getMutexId(Mutex *m) { 160353944Sdim for (int i = 0; i < kL1Size; i++) { 161353944Sdim Mutex *tab = mutex[i]; 162353944Sdim if (tab == 0) 163353944Sdim break; 164353944Sdim if (m >= tab && m < tab + kL2Size) 165353944Sdim return i * kL2Size + (m - tab); 166353944Sdim } 167353944Sdim return -1; 168353944Sdim} 169353944Sdim 170353944Sdimu32 DD::allocateId(DDCallback *cb) { 171353944Sdim u32 id = -1; 172353944Sdim SpinMutexLock l(&mtx); 173353944Sdim if (free_id.size() > 0) { 174353944Sdim id = free_id.back(); 175353944Sdim free_id.pop_back(); 176353944Sdim } else { 177353944Sdim CHECK_LT(id_gen, kMaxMutex); 178353944Sdim if ((id_gen % kL2Size) == 0) { 179353944Sdim mutex[id_gen / kL2Size] = (Mutex*)MmapOrDie(kL2Size * sizeof(Mutex), 180353944Sdim "deadlock detector (mutex table)"); 181353944Sdim } 182353944Sdim id = id_gen++; 183353944Sdim } 184353944Sdim CHECK_LE(id, kMaxMutex); 185353944Sdim VPrintf(3, "#%llu: DD::allocateId assign id %d\n", cb->lt->ctx, id); 186353944Sdim return id; 187353944Sdim} 188353944Sdim 189353944Sdimvoid DD::MutexBeforeLock(DDCallback *cb, DDMutex *m, bool wlock) { 190353944Sdim VPrintf(2, "#%llu: DD::MutexBeforeLock(%p, wlock=%d) nlocked=%d\n", 191353944Sdim cb->lt->ctx, m, wlock, cb->lt->nlocked); 192353944Sdim DDPhysicalThread *pt = cb->pt; 193353944Sdim DDLogicalThread *lt = cb->lt; 194353944Sdim 195353944Sdim uptr owner = atomic_load(&m->owner, memory_order_relaxed); 196353944Sdim if (owner == (uptr)cb->lt) { 197353944Sdim VPrintf(3, "#%llu: DD::MutexBeforeLock recursive\n", 198353944Sdim cb->lt->ctx); 199353944Sdim return; 200353944Sdim } 201353944Sdim 202353944Sdim CHECK_LE(lt->nlocked, kMaxNesting); 203353944Sdim 204353944Sdim // FIXME(dvyukov): don't allocate id if lt->nlocked == 0? 205353944Sdim if (m->id == kNoId) 206353944Sdim m->id = allocateId(cb); 207353944Sdim 208353944Sdim ThreadMutex *tm = <->locked[lt->nlocked++]; 209353944Sdim tm->id = m->id; 210353944Sdim if (flags.second_deadlock_stack) 211353944Sdim tm->stk = cb->Unwind(); 212353944Sdim if (lt->nlocked == 1) { 213353944Sdim VPrintf(3, "#%llu: DD::MutexBeforeLock first mutex\n", 214353944Sdim cb->lt->ctx); 215353944Sdim return; 216353944Sdim } 217353944Sdim 218353944Sdim bool added = false; 219353944Sdim Mutex *mtx = getMutex(m->id); 220353944Sdim for (int i = 0; i < lt->nlocked - 1; i++) { 221353944Sdim u32 id1 = lt->locked[i].id; 222353944Sdim u32 stk1 = lt->locked[i].stk; 223353944Sdim Mutex *mtx1 = getMutex(id1); 224353944Sdim SpinMutexLock l(&mtx1->mtx); 225353944Sdim if (mtx1->nlink == kMaxLink) { 226353944Sdim // FIXME(dvyukov): check stale links 227353944Sdim continue; 228353944Sdim } 229353944Sdim int li = 0; 230353944Sdim for (; li < mtx1->nlink; li++) { 231353944Sdim Link *link = &mtx1->link[li]; 232353944Sdim if (link->id == m->id) { 233353944Sdim if (link->seq != mtx->seq) { 234353944Sdim link->seq = mtx->seq; 235353944Sdim link->tid = lt->ctx; 236353944Sdim link->stk0 = stk1; 237353944Sdim link->stk1 = cb->Unwind(); 238353944Sdim added = true; 239353944Sdim VPrintf(3, "#%llu: DD::MutexBeforeLock added %d->%d link\n", 240353944Sdim cb->lt->ctx, getMutexId(mtx1), m->id); 241353944Sdim } 242353944Sdim break; 243353944Sdim } 244353944Sdim } 245353944Sdim if (li == mtx1->nlink) { 246353944Sdim // FIXME(dvyukov): check stale links 247353944Sdim Link *link = &mtx1->link[mtx1->nlink++]; 248353944Sdim link->id = m->id; 249353944Sdim link->seq = mtx->seq; 250353944Sdim link->tid = lt->ctx; 251353944Sdim link->stk0 = stk1; 252353944Sdim link->stk1 = cb->Unwind(); 253353944Sdim added = true; 254353944Sdim VPrintf(3, "#%llu: DD::MutexBeforeLock added %d->%d link\n", 255353944Sdim cb->lt->ctx, getMutexId(mtx1), m->id); 256353944Sdim } 257353944Sdim } 258353944Sdim 259353944Sdim if (!added || mtx->nlink == 0) { 260353944Sdim VPrintf(3, "#%llu: DD::MutexBeforeLock don't check\n", 261353944Sdim cb->lt->ctx); 262353944Sdim return; 263353944Sdim } 264353944Sdim 265353944Sdim CycleCheck(pt, lt, m); 266353944Sdim} 267353944Sdim 268353944Sdimvoid DD::MutexAfterLock(DDCallback *cb, DDMutex *m, bool wlock, 269353944Sdim bool trylock) { 270353944Sdim VPrintf(2, "#%llu: DD::MutexAfterLock(%p, wlock=%d, try=%d) nlocked=%d\n", 271353944Sdim cb->lt->ctx, m, wlock, trylock, cb->lt->nlocked); 272353944Sdim DDLogicalThread *lt = cb->lt; 273353944Sdim 274353944Sdim uptr owner = atomic_load(&m->owner, memory_order_relaxed); 275353944Sdim if (owner == (uptr)cb->lt) { 276353944Sdim VPrintf(3, "#%llu: DD::MutexAfterLock recursive\n", cb->lt->ctx); 277353944Sdim CHECK(wlock); 278353944Sdim m->recursion++; 279353944Sdim return; 280353944Sdim } 281353944Sdim CHECK_EQ(owner, 0); 282353944Sdim if (wlock) { 283353944Sdim VPrintf(3, "#%llu: DD::MutexAfterLock set owner\n", cb->lt->ctx); 284353944Sdim CHECK_EQ(m->recursion, 0); 285353944Sdim m->recursion = 1; 286353944Sdim atomic_store(&m->owner, (uptr)cb->lt, memory_order_relaxed); 287353944Sdim } 288353944Sdim 289353944Sdim if (!trylock) 290353944Sdim return; 291353944Sdim 292353944Sdim CHECK_LE(lt->nlocked, kMaxNesting); 293353944Sdim if (m->id == kNoId) 294353944Sdim m->id = allocateId(cb); 295353944Sdim ThreadMutex *tm = <->locked[lt->nlocked++]; 296353944Sdim tm->id = m->id; 297353944Sdim if (flags.second_deadlock_stack) 298353944Sdim tm->stk = cb->Unwind(); 299353944Sdim} 300353944Sdim 301353944Sdimvoid DD::MutexBeforeUnlock(DDCallback *cb, DDMutex *m, bool wlock) { 302353944Sdim VPrintf(2, "#%llu: DD::MutexBeforeUnlock(%p, wlock=%d) nlocked=%d\n", 303353944Sdim cb->lt->ctx, m, wlock, cb->lt->nlocked); 304353944Sdim DDLogicalThread *lt = cb->lt; 305353944Sdim 306353944Sdim uptr owner = atomic_load(&m->owner, memory_order_relaxed); 307353944Sdim if (owner == (uptr)cb->lt) { 308353944Sdim VPrintf(3, "#%llu: DD::MutexBeforeUnlock recursive\n", cb->lt->ctx); 309353944Sdim if (--m->recursion > 0) 310353944Sdim return; 311353944Sdim VPrintf(3, "#%llu: DD::MutexBeforeUnlock reset owner\n", cb->lt->ctx); 312353944Sdim atomic_store(&m->owner, 0, memory_order_relaxed); 313353944Sdim } 314353944Sdim CHECK_NE(m->id, kNoId); 315353944Sdim int last = lt->nlocked - 1; 316353944Sdim for (int i = last; i >= 0; i--) { 317353944Sdim if (cb->lt->locked[i].id == m->id) { 318353944Sdim lt->locked[i] = lt->locked[last]; 319353944Sdim lt->nlocked--; 320353944Sdim break; 321353944Sdim } 322353944Sdim } 323353944Sdim} 324353944Sdim 325353944Sdimvoid DD::MutexDestroy(DDCallback *cb, DDMutex *m) { 326353944Sdim VPrintf(2, "#%llu: DD::MutexDestroy(%p)\n", 327353944Sdim cb->lt->ctx, m); 328353944Sdim DDLogicalThread *lt = cb->lt; 329353944Sdim 330353944Sdim if (m->id == kNoId) 331353944Sdim return; 332353944Sdim 333353944Sdim // Remove the mutex from lt->locked if there. 334353944Sdim int last = lt->nlocked - 1; 335353944Sdim for (int i = last; i >= 0; i--) { 336353944Sdim if (lt->locked[i].id == m->id) { 337353944Sdim lt->locked[i] = lt->locked[last]; 338353944Sdim lt->nlocked--; 339353944Sdim break; 340353944Sdim } 341353944Sdim } 342353944Sdim 343353944Sdim // Clear and invalidate the mutex descriptor. 344353944Sdim { 345353944Sdim Mutex *mtx = getMutex(m->id); 346353944Sdim SpinMutexLock l(&mtx->mtx); 347353944Sdim mtx->seq++; 348353944Sdim mtx->nlink = 0; 349353944Sdim } 350353944Sdim 351353944Sdim // Return id to cache. 352353944Sdim { 353353944Sdim SpinMutexLock l(&mtx); 354353944Sdim free_id.push_back(m->id); 355353944Sdim } 356353944Sdim} 357353944Sdim 358353944Sdimvoid DD::CycleCheck(DDPhysicalThread *pt, DDLogicalThread *lt, 359353944Sdim DDMutex *m) { 360353944Sdim internal_memset(pt->visited, 0, sizeof(pt->visited)); 361353944Sdim int npath = 0; 362353944Sdim int npending = 0; 363353944Sdim { 364353944Sdim Mutex *mtx = getMutex(m->id); 365353944Sdim SpinMutexLock l(&mtx->mtx); 366353944Sdim for (int li = 0; li < mtx->nlink; li++) 367353944Sdim pt->pending[npending++] = mtx->link[li]; 368353944Sdim } 369353944Sdim while (npending > 0) { 370353944Sdim Link link = pt->pending[--npending]; 371353944Sdim if (link.id == kEndId) { 372353944Sdim npath--; 373353944Sdim continue; 374353944Sdim } 375353944Sdim if (pt->visited[link.id]) 376353944Sdim continue; 377353944Sdim Mutex *mtx1 = getMutex(link.id); 378353944Sdim SpinMutexLock l(&mtx1->mtx); 379353944Sdim if (mtx1->seq != link.seq) 380353944Sdim continue; 381353944Sdim pt->visited[link.id] = true; 382353944Sdim if (mtx1->nlink == 0) 383353944Sdim continue; 384353944Sdim pt->path[npath++] = link; 385353944Sdim pt->pending[npending++] = Link(kEndId); 386353944Sdim if (link.id == m->id) 387353944Sdim return Report(pt, lt, npath); // Bingo! 388353944Sdim for (int li = 0; li < mtx1->nlink; li++) { 389353944Sdim Link *link1 = &mtx1->link[li]; 390353944Sdim // Mutex *mtx2 = getMutex(link->id); 391353944Sdim // FIXME(dvyukov): fast seq check 392353944Sdim // FIXME(dvyukov): fast nlink != 0 check 393353944Sdim // FIXME(dvyukov): fast pending check? 394353944Sdim // FIXME(dvyukov): npending can be larger than kMaxMutex 395353944Sdim pt->pending[npending++] = *link1; 396353944Sdim } 397353944Sdim } 398353944Sdim} 399353944Sdim 400353944Sdimvoid DD::Report(DDPhysicalThread *pt, DDLogicalThread *lt, int npath) { 401353944Sdim DDReport *rep = &pt->rep; 402353944Sdim rep->n = npath; 403353944Sdim for (int i = 0; i < npath; i++) { 404353944Sdim Link *link = &pt->path[i]; 405353944Sdim Link *link0 = &pt->path[i ? i - 1 : npath - 1]; 406353944Sdim rep->loop[i].thr_ctx = link->tid; 407353944Sdim rep->loop[i].mtx_ctx0 = link0->id; 408353944Sdim rep->loop[i].mtx_ctx1 = link->id; 409353944Sdim rep->loop[i].stk[0] = flags.second_deadlock_stack ? link->stk0 : 0; 410353944Sdim rep->loop[i].stk[1] = link->stk1; 411353944Sdim } 412353944Sdim pt->report_pending = true; 413353944Sdim} 414353944Sdim 415353944SdimDDReport *DD::GetReport(DDCallback *cb) { 416353944Sdim if (!cb->pt->report_pending) 417353944Sdim return 0; 418353944Sdim cb->pt->report_pending = false; 419353944Sdim return &cb->pt->rep; 420353944Sdim} 421353944Sdim 422353944Sdim} // namespace __sanitizer 423353944Sdim#endif // #if SANITIZER_DEADLOCK_DETECTOR_VERSION == 2 424