Home | History | Annotate | Line # | Download | only in sanitizer_common 
      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 
     22 namespace __sanitizer {
     23 
     24 const int kMaxNesting = 64;
     25 const u32 kNoId = -1;
     26 const u32 kEndId = -2;
     27 const int kMaxLink = 8;
     28 const int kL1Size = 1024;
     29 const int kL2Size = 1024;
     30 const int kMaxMutex = kL1Size * kL2Size;
     31 
     32 struct 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 
     42 struct 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 
     58 struct DDPhysicalThread {
     59   DDReport rep;
     60   bool report_pending;
     61   bool visited[kMaxMutex];
     62   Link pending[kMaxMutex];
     63   Link path[kMaxMutex];
     64 };
     65 
     66 struct ThreadMutex {
     67   u32 id;
     68   u32 stk;
     69 };
     70 
     71 struct DDLogicalThread {
     72   u64         ctx;
     73   ThreadMutex locked[kMaxNesting];
     74   int         nlocked;
     75 };
     76 
     77 struct Mutex {
     78   StaticSpinMutex mtx;
     79   u32 seq;
     80   int nlink;
     81   Link link[kMaxLink];
     82 };
     83 
     84 struct 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 
    117 DDetector *DDetector::Create(const DDFlags *flags) {
    118   (void)flags;
    119   void *mem = MmapOrDie(sizeof(DD), "deadlock detector");
    120   return new(mem) DD(flags);
    121 }
    122 
    123 DD::DD(const DDFlags *flags) : flags(*flags) { free_id.reserve(1024); }
    124 
    125 DDPhysicalThread* DD::CreatePhysicalThread() {
    126   DDPhysicalThread *pt = (DDPhysicalThread*)MmapOrDie(sizeof(DDPhysicalThread),
    127       "deadlock detector (physical thread)");
    128   return pt;
    129 }
    130 
    131 void DD::DestroyPhysicalThread(DDPhysicalThread *pt) {
    132   pt->~DDPhysicalThread();
    133   UnmapOrDie(pt, sizeof(DDPhysicalThread));
    134 }
    135 
    136 DDLogicalThread* 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 
    144 void DD::DestroyLogicalThread(DDLogicalThread *lt) {
    145   lt->~DDLogicalThread();
    146   InternalFree(lt);
    147 }
    148 
    149 void 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 
    156 Mutex *DD::getMutex(u32 id) {
    157   return &mutex[id / kL2Size][id % kL2Size];
    158 }
    159 
    160 u32 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 
    171 u32 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 
    190 void 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 = &lt->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 
    269 void 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 = &lt->locked[lt->nlocked++];
    297   tm->id = m->id;
    298   if (flags.second_deadlock_stack)
    299     tm->stk = cb->Unwind();
    300 }
    301 
    302 void 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 
    326 void 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 
    359 void 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 
    401 void 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 
    416 DDReport *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