13cab2bb3Spatrick //===-- sanitizer_deadlock_detector2.cpp ----------------------------------===//
23cab2bb3Spatrick //
33cab2bb3Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
43cab2bb3Spatrick // See https://llvm.org/LICENSE.txt for license information.
53cab2bb3Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
63cab2bb3Spatrick //
73cab2bb3Spatrick //===----------------------------------------------------------------------===//
83cab2bb3Spatrick //
93cab2bb3Spatrick // Deadlock detector implementation based on adjacency lists.
103cab2bb3Spatrick //
113cab2bb3Spatrick //===----------------------------------------------------------------------===//
123cab2bb3Spatrick
133cab2bb3Spatrick #include "sanitizer_deadlock_detector_interface.h"
143cab2bb3Spatrick #include "sanitizer_common.h"
153cab2bb3Spatrick #include "sanitizer_allocator_internal.h"
163cab2bb3Spatrick #include "sanitizer_placement_new.h"
173cab2bb3Spatrick #include "sanitizer_mutex.h"
183cab2bb3Spatrick
193cab2bb3Spatrick #if SANITIZER_DEADLOCK_DETECTOR_VERSION == 2
203cab2bb3Spatrick
213cab2bb3Spatrick namespace __sanitizer {
223cab2bb3Spatrick
233cab2bb3Spatrick const int kMaxNesting = 64;
243cab2bb3Spatrick const u32 kNoId = -1;
253cab2bb3Spatrick const u32 kEndId = -2;
263cab2bb3Spatrick const int kMaxLink = 8;
273cab2bb3Spatrick const int kL1Size = 1024;
283cab2bb3Spatrick const int kL2Size = 1024;
293cab2bb3Spatrick const int kMaxMutex = kL1Size * kL2Size;
303cab2bb3Spatrick
313cab2bb3Spatrick struct Id {
323cab2bb3Spatrick u32 id;
333cab2bb3Spatrick u32 seq;
343cab2bb3Spatrick
Id__sanitizer::Id353cab2bb3Spatrick explicit Id(u32 id = 0, u32 seq = 0)
363cab2bb3Spatrick : id(id)
373cab2bb3Spatrick , seq(seq) {
383cab2bb3Spatrick }
393cab2bb3Spatrick };
403cab2bb3Spatrick
413cab2bb3Spatrick struct Link {
423cab2bb3Spatrick u32 id;
433cab2bb3Spatrick u32 seq;
443cab2bb3Spatrick u32 tid;
453cab2bb3Spatrick u32 stk0;
463cab2bb3Spatrick u32 stk1;
473cab2bb3Spatrick
Link__sanitizer::Link483cab2bb3Spatrick explicit Link(u32 id = 0, u32 seq = 0, u32 tid = 0, u32 s0 = 0, u32 s1 = 0)
493cab2bb3Spatrick : id(id)
503cab2bb3Spatrick , seq(seq)
513cab2bb3Spatrick , tid(tid)
523cab2bb3Spatrick , stk0(s0)
533cab2bb3Spatrick , stk1(s1) {
543cab2bb3Spatrick }
553cab2bb3Spatrick };
563cab2bb3Spatrick
573cab2bb3Spatrick struct DDPhysicalThread {
583cab2bb3Spatrick DDReport rep;
593cab2bb3Spatrick bool report_pending;
603cab2bb3Spatrick bool visited[kMaxMutex];
613cab2bb3Spatrick Link pending[kMaxMutex];
623cab2bb3Spatrick Link path[kMaxMutex];
633cab2bb3Spatrick };
643cab2bb3Spatrick
653cab2bb3Spatrick struct ThreadMutex {
663cab2bb3Spatrick u32 id;
673cab2bb3Spatrick u32 stk;
683cab2bb3Spatrick };
693cab2bb3Spatrick
703cab2bb3Spatrick struct DDLogicalThread {
713cab2bb3Spatrick u64 ctx;
723cab2bb3Spatrick ThreadMutex locked[kMaxNesting];
733cab2bb3Spatrick int nlocked;
743cab2bb3Spatrick };
753cab2bb3Spatrick
76*d89ec533Spatrick struct MutexState {
773cab2bb3Spatrick StaticSpinMutex mtx;
783cab2bb3Spatrick u32 seq;
793cab2bb3Spatrick int nlink;
803cab2bb3Spatrick Link link[kMaxLink];
813cab2bb3Spatrick };
823cab2bb3Spatrick
83*d89ec533Spatrick struct DD final : public DDetector {
843cab2bb3Spatrick explicit DD(const DDFlags *flags);
853cab2bb3Spatrick
863cab2bb3Spatrick DDPhysicalThread* CreatePhysicalThread();
873cab2bb3Spatrick void DestroyPhysicalThread(DDPhysicalThread *pt);
883cab2bb3Spatrick
893cab2bb3Spatrick DDLogicalThread* CreateLogicalThread(u64 ctx);
903cab2bb3Spatrick void DestroyLogicalThread(DDLogicalThread *lt);
913cab2bb3Spatrick
923cab2bb3Spatrick void MutexInit(DDCallback *cb, DDMutex *m);
933cab2bb3Spatrick void MutexBeforeLock(DDCallback *cb, DDMutex *m, bool wlock);
943cab2bb3Spatrick void MutexAfterLock(DDCallback *cb, DDMutex *m, bool wlock,
953cab2bb3Spatrick bool trylock);
963cab2bb3Spatrick void MutexBeforeUnlock(DDCallback *cb, DDMutex *m, bool wlock);
973cab2bb3Spatrick void MutexDestroy(DDCallback *cb, DDMutex *m);
983cab2bb3Spatrick
993cab2bb3Spatrick DDReport *GetReport(DDCallback *cb);
1003cab2bb3Spatrick
1013cab2bb3Spatrick void CycleCheck(DDPhysicalThread *pt, DDLogicalThread *lt, DDMutex *mtx);
1023cab2bb3Spatrick void Report(DDPhysicalThread *pt, DDLogicalThread *lt, int npath);
1033cab2bb3Spatrick u32 allocateId(DDCallback *cb);
104*d89ec533Spatrick MutexState *getMutex(u32 id);
105*d89ec533Spatrick u32 getMutexId(MutexState *m);
1063cab2bb3Spatrick
1073cab2bb3Spatrick DDFlags flags;
1083cab2bb3Spatrick
109*d89ec533Spatrick MutexState *mutex[kL1Size];
1103cab2bb3Spatrick
1113cab2bb3Spatrick SpinMutex mtx;
1123cab2bb3Spatrick InternalMmapVector<u32> free_id;
1133cab2bb3Spatrick int id_gen = 0;
1143cab2bb3Spatrick };
1153cab2bb3Spatrick
Create(const DDFlags * flags)1163cab2bb3Spatrick DDetector *DDetector::Create(const DDFlags *flags) {
1173cab2bb3Spatrick (void)flags;
1183cab2bb3Spatrick void *mem = MmapOrDie(sizeof(DD), "deadlock detector");
1193cab2bb3Spatrick return new(mem) DD(flags);
1203cab2bb3Spatrick }
1213cab2bb3Spatrick
DD(const DDFlags * flags)1223cab2bb3Spatrick DD::DD(const DDFlags *flags) : flags(*flags) { free_id.reserve(1024); }
1233cab2bb3Spatrick
CreatePhysicalThread()1243cab2bb3Spatrick DDPhysicalThread* DD::CreatePhysicalThread() {
1253cab2bb3Spatrick DDPhysicalThread *pt = (DDPhysicalThread*)MmapOrDie(sizeof(DDPhysicalThread),
1263cab2bb3Spatrick "deadlock detector (physical thread)");
1273cab2bb3Spatrick return pt;
1283cab2bb3Spatrick }
1293cab2bb3Spatrick
DestroyPhysicalThread(DDPhysicalThread * pt)1303cab2bb3Spatrick void DD::DestroyPhysicalThread(DDPhysicalThread *pt) {
1313cab2bb3Spatrick pt->~DDPhysicalThread();
1323cab2bb3Spatrick UnmapOrDie(pt, sizeof(DDPhysicalThread));
1333cab2bb3Spatrick }
1343cab2bb3Spatrick
CreateLogicalThread(u64 ctx)1353cab2bb3Spatrick DDLogicalThread* DD::CreateLogicalThread(u64 ctx) {
1363cab2bb3Spatrick DDLogicalThread *lt = (DDLogicalThread*)InternalAlloc(
1373cab2bb3Spatrick sizeof(DDLogicalThread));
1383cab2bb3Spatrick lt->ctx = ctx;
1393cab2bb3Spatrick lt->nlocked = 0;
1403cab2bb3Spatrick return lt;
1413cab2bb3Spatrick }
1423cab2bb3Spatrick
DestroyLogicalThread(DDLogicalThread * lt)1433cab2bb3Spatrick void DD::DestroyLogicalThread(DDLogicalThread *lt) {
1443cab2bb3Spatrick lt->~DDLogicalThread();
1453cab2bb3Spatrick InternalFree(lt);
1463cab2bb3Spatrick }
1473cab2bb3Spatrick
MutexInit(DDCallback * cb,DDMutex * m)1483cab2bb3Spatrick void DD::MutexInit(DDCallback *cb, DDMutex *m) {
1493cab2bb3Spatrick VPrintf(2, "#%llu: DD::MutexInit(%p)\n", cb->lt->ctx, m);
1503cab2bb3Spatrick m->id = kNoId;
1513cab2bb3Spatrick m->recursion = 0;
1523cab2bb3Spatrick atomic_store(&m->owner, 0, memory_order_relaxed);
1533cab2bb3Spatrick }
1543cab2bb3Spatrick
getMutex(u32 id)155*d89ec533Spatrick MutexState *DD::getMutex(u32 id) { return &mutex[id / kL2Size][id % kL2Size]; }
1563cab2bb3Spatrick
getMutexId(MutexState * m)157*d89ec533Spatrick u32 DD::getMutexId(MutexState *m) {
1583cab2bb3Spatrick for (int i = 0; i < kL1Size; i++) {
159*d89ec533Spatrick MutexState *tab = mutex[i];
1603cab2bb3Spatrick if (tab == 0)
1613cab2bb3Spatrick break;
1623cab2bb3Spatrick if (m >= tab && m < tab + kL2Size)
1633cab2bb3Spatrick return i * kL2Size + (m - tab);
1643cab2bb3Spatrick }
1653cab2bb3Spatrick return -1;
1663cab2bb3Spatrick }
1673cab2bb3Spatrick
allocateId(DDCallback * cb)1683cab2bb3Spatrick u32 DD::allocateId(DDCallback *cb) {
1693cab2bb3Spatrick u32 id = -1;
1703cab2bb3Spatrick SpinMutexLock l(&mtx);
1713cab2bb3Spatrick if (free_id.size() > 0) {
1723cab2bb3Spatrick id = free_id.back();
1733cab2bb3Spatrick free_id.pop_back();
1743cab2bb3Spatrick } else {
1753cab2bb3Spatrick CHECK_LT(id_gen, kMaxMutex);
1763cab2bb3Spatrick if ((id_gen % kL2Size) == 0) {
177*d89ec533Spatrick mutex[id_gen / kL2Size] = (MutexState *)MmapOrDie(
178*d89ec533Spatrick kL2Size * sizeof(MutexState), "deadlock detector (mutex table)");
1793cab2bb3Spatrick }
1803cab2bb3Spatrick id = id_gen++;
1813cab2bb3Spatrick }
1823cab2bb3Spatrick CHECK_LE(id, kMaxMutex);
1833cab2bb3Spatrick VPrintf(3, "#%llu: DD::allocateId assign id %d\n", cb->lt->ctx, id);
1843cab2bb3Spatrick return id;
1853cab2bb3Spatrick }
1863cab2bb3Spatrick
MutexBeforeLock(DDCallback * cb,DDMutex * m,bool wlock)1873cab2bb3Spatrick void DD::MutexBeforeLock(DDCallback *cb, DDMutex *m, bool wlock) {
1883cab2bb3Spatrick VPrintf(2, "#%llu: DD::MutexBeforeLock(%p, wlock=%d) nlocked=%d\n",
1893cab2bb3Spatrick cb->lt->ctx, m, wlock, cb->lt->nlocked);
1903cab2bb3Spatrick DDPhysicalThread *pt = cb->pt;
1913cab2bb3Spatrick DDLogicalThread *lt = cb->lt;
1923cab2bb3Spatrick
1933cab2bb3Spatrick uptr owner = atomic_load(&m->owner, memory_order_relaxed);
1943cab2bb3Spatrick if (owner == (uptr)cb->lt) {
1953cab2bb3Spatrick VPrintf(3, "#%llu: DD::MutexBeforeLock recursive\n",
1963cab2bb3Spatrick cb->lt->ctx);
1973cab2bb3Spatrick return;
1983cab2bb3Spatrick }
1993cab2bb3Spatrick
2003cab2bb3Spatrick CHECK_LE(lt->nlocked, kMaxNesting);
2013cab2bb3Spatrick
2023cab2bb3Spatrick // FIXME(dvyukov): don't allocate id if lt->nlocked == 0?
2033cab2bb3Spatrick if (m->id == kNoId)
2043cab2bb3Spatrick m->id = allocateId(cb);
2053cab2bb3Spatrick
2063cab2bb3Spatrick ThreadMutex *tm = <->locked[lt->nlocked++];
2073cab2bb3Spatrick tm->id = m->id;
2083cab2bb3Spatrick if (flags.second_deadlock_stack)
2093cab2bb3Spatrick tm->stk = cb->Unwind();
2103cab2bb3Spatrick if (lt->nlocked == 1) {
2113cab2bb3Spatrick VPrintf(3, "#%llu: DD::MutexBeforeLock first mutex\n",
2123cab2bb3Spatrick cb->lt->ctx);
2133cab2bb3Spatrick return;
2143cab2bb3Spatrick }
2153cab2bb3Spatrick
2163cab2bb3Spatrick bool added = false;
217*d89ec533Spatrick MutexState *mtx = getMutex(m->id);
2183cab2bb3Spatrick for (int i = 0; i < lt->nlocked - 1; i++) {
2193cab2bb3Spatrick u32 id1 = lt->locked[i].id;
2203cab2bb3Spatrick u32 stk1 = lt->locked[i].stk;
221*d89ec533Spatrick MutexState *mtx1 = getMutex(id1);
2223cab2bb3Spatrick SpinMutexLock l(&mtx1->mtx);
2233cab2bb3Spatrick if (mtx1->nlink == kMaxLink) {
2243cab2bb3Spatrick // FIXME(dvyukov): check stale links
2253cab2bb3Spatrick continue;
2263cab2bb3Spatrick }
2273cab2bb3Spatrick int li = 0;
2283cab2bb3Spatrick for (; li < mtx1->nlink; li++) {
2293cab2bb3Spatrick Link *link = &mtx1->link[li];
2303cab2bb3Spatrick if (link->id == m->id) {
2313cab2bb3Spatrick if (link->seq != mtx->seq) {
2323cab2bb3Spatrick link->seq = mtx->seq;
2333cab2bb3Spatrick link->tid = lt->ctx;
2343cab2bb3Spatrick link->stk0 = stk1;
2353cab2bb3Spatrick link->stk1 = cb->Unwind();
2363cab2bb3Spatrick added = true;
2373cab2bb3Spatrick VPrintf(3, "#%llu: DD::MutexBeforeLock added %d->%d link\n",
2383cab2bb3Spatrick cb->lt->ctx, getMutexId(mtx1), m->id);
2393cab2bb3Spatrick }
2403cab2bb3Spatrick break;
2413cab2bb3Spatrick }
2423cab2bb3Spatrick }
2433cab2bb3Spatrick if (li == mtx1->nlink) {
2443cab2bb3Spatrick // FIXME(dvyukov): check stale links
2453cab2bb3Spatrick Link *link = &mtx1->link[mtx1->nlink++];
2463cab2bb3Spatrick link->id = m->id;
2473cab2bb3Spatrick link->seq = mtx->seq;
2483cab2bb3Spatrick link->tid = lt->ctx;
2493cab2bb3Spatrick link->stk0 = stk1;
2503cab2bb3Spatrick link->stk1 = cb->Unwind();
2513cab2bb3Spatrick added = true;
2523cab2bb3Spatrick VPrintf(3, "#%llu: DD::MutexBeforeLock added %d->%d link\n",
2533cab2bb3Spatrick cb->lt->ctx, getMutexId(mtx1), m->id);
2543cab2bb3Spatrick }
2553cab2bb3Spatrick }
2563cab2bb3Spatrick
2573cab2bb3Spatrick if (!added || mtx->nlink == 0) {
2583cab2bb3Spatrick VPrintf(3, "#%llu: DD::MutexBeforeLock don't check\n",
2593cab2bb3Spatrick cb->lt->ctx);
2603cab2bb3Spatrick return;
2613cab2bb3Spatrick }
2623cab2bb3Spatrick
2633cab2bb3Spatrick CycleCheck(pt, lt, m);
2643cab2bb3Spatrick }
2653cab2bb3Spatrick
MutexAfterLock(DDCallback * cb,DDMutex * m,bool wlock,bool trylock)2663cab2bb3Spatrick void DD::MutexAfterLock(DDCallback *cb, DDMutex *m, bool wlock,
2673cab2bb3Spatrick bool trylock) {
2683cab2bb3Spatrick VPrintf(2, "#%llu: DD::MutexAfterLock(%p, wlock=%d, try=%d) nlocked=%d\n",
2693cab2bb3Spatrick cb->lt->ctx, m, wlock, trylock, cb->lt->nlocked);
2703cab2bb3Spatrick DDLogicalThread *lt = cb->lt;
2713cab2bb3Spatrick
2723cab2bb3Spatrick uptr owner = atomic_load(&m->owner, memory_order_relaxed);
2733cab2bb3Spatrick if (owner == (uptr)cb->lt) {
2743cab2bb3Spatrick VPrintf(3, "#%llu: DD::MutexAfterLock recursive\n", cb->lt->ctx);
2753cab2bb3Spatrick CHECK(wlock);
2763cab2bb3Spatrick m->recursion++;
2773cab2bb3Spatrick return;
2783cab2bb3Spatrick }
2793cab2bb3Spatrick CHECK_EQ(owner, 0);
2803cab2bb3Spatrick if (wlock) {
2813cab2bb3Spatrick VPrintf(3, "#%llu: DD::MutexAfterLock set owner\n", cb->lt->ctx);
2823cab2bb3Spatrick CHECK_EQ(m->recursion, 0);
2833cab2bb3Spatrick m->recursion = 1;
2843cab2bb3Spatrick atomic_store(&m->owner, (uptr)cb->lt, memory_order_relaxed);
2853cab2bb3Spatrick }
2863cab2bb3Spatrick
2873cab2bb3Spatrick if (!trylock)
2883cab2bb3Spatrick return;
2893cab2bb3Spatrick
2903cab2bb3Spatrick CHECK_LE(lt->nlocked, kMaxNesting);
2913cab2bb3Spatrick if (m->id == kNoId)
2923cab2bb3Spatrick m->id = allocateId(cb);
2933cab2bb3Spatrick ThreadMutex *tm = <->locked[lt->nlocked++];
2943cab2bb3Spatrick tm->id = m->id;
2953cab2bb3Spatrick if (flags.second_deadlock_stack)
2963cab2bb3Spatrick tm->stk = cb->Unwind();
2973cab2bb3Spatrick }
2983cab2bb3Spatrick
MutexBeforeUnlock(DDCallback * cb,DDMutex * m,bool wlock)2993cab2bb3Spatrick void DD::MutexBeforeUnlock(DDCallback *cb, DDMutex *m, bool wlock) {
3003cab2bb3Spatrick VPrintf(2, "#%llu: DD::MutexBeforeUnlock(%p, wlock=%d) nlocked=%d\n",
3013cab2bb3Spatrick cb->lt->ctx, m, wlock, cb->lt->nlocked);
3023cab2bb3Spatrick DDLogicalThread *lt = cb->lt;
3033cab2bb3Spatrick
3043cab2bb3Spatrick uptr owner = atomic_load(&m->owner, memory_order_relaxed);
3053cab2bb3Spatrick if (owner == (uptr)cb->lt) {
3063cab2bb3Spatrick VPrintf(3, "#%llu: DD::MutexBeforeUnlock recursive\n", cb->lt->ctx);
3073cab2bb3Spatrick if (--m->recursion > 0)
3083cab2bb3Spatrick return;
3093cab2bb3Spatrick VPrintf(3, "#%llu: DD::MutexBeforeUnlock reset owner\n", cb->lt->ctx);
3103cab2bb3Spatrick atomic_store(&m->owner, 0, memory_order_relaxed);
3113cab2bb3Spatrick }
3123cab2bb3Spatrick CHECK_NE(m->id, kNoId);
3133cab2bb3Spatrick int last = lt->nlocked - 1;
3143cab2bb3Spatrick for (int i = last; i >= 0; i--) {
3153cab2bb3Spatrick if (cb->lt->locked[i].id == m->id) {
3163cab2bb3Spatrick lt->locked[i] = lt->locked[last];
3173cab2bb3Spatrick lt->nlocked--;
3183cab2bb3Spatrick break;
3193cab2bb3Spatrick }
3203cab2bb3Spatrick }
3213cab2bb3Spatrick }
3223cab2bb3Spatrick
MutexDestroy(DDCallback * cb,DDMutex * m)3233cab2bb3Spatrick void DD::MutexDestroy(DDCallback *cb, DDMutex *m) {
3243cab2bb3Spatrick VPrintf(2, "#%llu: DD::MutexDestroy(%p)\n",
3253cab2bb3Spatrick cb->lt->ctx, m);
3263cab2bb3Spatrick DDLogicalThread *lt = cb->lt;
3273cab2bb3Spatrick
3283cab2bb3Spatrick if (m->id == kNoId)
3293cab2bb3Spatrick return;
3303cab2bb3Spatrick
3313cab2bb3Spatrick // Remove the mutex from lt->locked if there.
3323cab2bb3Spatrick int last = lt->nlocked - 1;
3333cab2bb3Spatrick for (int i = last; i >= 0; i--) {
3343cab2bb3Spatrick if (lt->locked[i].id == m->id) {
3353cab2bb3Spatrick lt->locked[i] = lt->locked[last];
3363cab2bb3Spatrick lt->nlocked--;
3373cab2bb3Spatrick break;
3383cab2bb3Spatrick }
3393cab2bb3Spatrick }
3403cab2bb3Spatrick
3413cab2bb3Spatrick // Clear and invalidate the mutex descriptor.
3423cab2bb3Spatrick {
343*d89ec533Spatrick MutexState *mtx = getMutex(m->id);
3443cab2bb3Spatrick SpinMutexLock l(&mtx->mtx);
3453cab2bb3Spatrick mtx->seq++;
3463cab2bb3Spatrick mtx->nlink = 0;
3473cab2bb3Spatrick }
3483cab2bb3Spatrick
3493cab2bb3Spatrick // Return id to cache.
3503cab2bb3Spatrick {
3513cab2bb3Spatrick SpinMutexLock l(&mtx);
3523cab2bb3Spatrick free_id.push_back(m->id);
3533cab2bb3Spatrick }
3543cab2bb3Spatrick }
3553cab2bb3Spatrick
CycleCheck(DDPhysicalThread * pt,DDLogicalThread * lt,DDMutex * m)3563cab2bb3Spatrick void DD::CycleCheck(DDPhysicalThread *pt, DDLogicalThread *lt,
3573cab2bb3Spatrick DDMutex *m) {
3583cab2bb3Spatrick internal_memset(pt->visited, 0, sizeof(pt->visited));
3593cab2bb3Spatrick int npath = 0;
3603cab2bb3Spatrick int npending = 0;
3613cab2bb3Spatrick {
362*d89ec533Spatrick MutexState *mtx = getMutex(m->id);
3633cab2bb3Spatrick SpinMutexLock l(&mtx->mtx);
3643cab2bb3Spatrick for (int li = 0; li < mtx->nlink; li++)
3653cab2bb3Spatrick pt->pending[npending++] = mtx->link[li];
3663cab2bb3Spatrick }
3673cab2bb3Spatrick while (npending > 0) {
3683cab2bb3Spatrick Link link = pt->pending[--npending];
3693cab2bb3Spatrick if (link.id == kEndId) {
3703cab2bb3Spatrick npath--;
3713cab2bb3Spatrick continue;
3723cab2bb3Spatrick }
3733cab2bb3Spatrick if (pt->visited[link.id])
3743cab2bb3Spatrick continue;
375*d89ec533Spatrick MutexState *mtx1 = getMutex(link.id);
3763cab2bb3Spatrick SpinMutexLock l(&mtx1->mtx);
3773cab2bb3Spatrick if (mtx1->seq != link.seq)
3783cab2bb3Spatrick continue;
3793cab2bb3Spatrick pt->visited[link.id] = true;
3803cab2bb3Spatrick if (mtx1->nlink == 0)
3813cab2bb3Spatrick continue;
3823cab2bb3Spatrick pt->path[npath++] = link;
3833cab2bb3Spatrick pt->pending[npending++] = Link(kEndId);
3843cab2bb3Spatrick if (link.id == m->id)
3853cab2bb3Spatrick return Report(pt, lt, npath); // Bingo!
3863cab2bb3Spatrick for (int li = 0; li < mtx1->nlink; li++) {
3873cab2bb3Spatrick Link *link1 = &mtx1->link[li];
388*d89ec533Spatrick // MutexState *mtx2 = getMutex(link->id);
3893cab2bb3Spatrick // FIXME(dvyukov): fast seq check
3903cab2bb3Spatrick // FIXME(dvyukov): fast nlink != 0 check
3913cab2bb3Spatrick // FIXME(dvyukov): fast pending check?
3923cab2bb3Spatrick // FIXME(dvyukov): npending can be larger than kMaxMutex
3933cab2bb3Spatrick pt->pending[npending++] = *link1;
3943cab2bb3Spatrick }
3953cab2bb3Spatrick }
3963cab2bb3Spatrick }
3973cab2bb3Spatrick
Report(DDPhysicalThread * pt,DDLogicalThread * lt,int npath)3983cab2bb3Spatrick void DD::Report(DDPhysicalThread *pt, DDLogicalThread *lt, int npath) {
3993cab2bb3Spatrick DDReport *rep = &pt->rep;
4003cab2bb3Spatrick rep->n = npath;
4013cab2bb3Spatrick for (int i = 0; i < npath; i++) {
4023cab2bb3Spatrick Link *link = &pt->path[i];
4033cab2bb3Spatrick Link *link0 = &pt->path[i ? i - 1 : npath - 1];
4043cab2bb3Spatrick rep->loop[i].thr_ctx = link->tid;
4053cab2bb3Spatrick rep->loop[i].mtx_ctx0 = link0->id;
4063cab2bb3Spatrick rep->loop[i].mtx_ctx1 = link->id;
4073cab2bb3Spatrick rep->loop[i].stk[0] = flags.second_deadlock_stack ? link->stk0 : 0;
4083cab2bb3Spatrick rep->loop[i].stk[1] = link->stk1;
4093cab2bb3Spatrick }
4103cab2bb3Spatrick pt->report_pending = true;
4113cab2bb3Spatrick }
4123cab2bb3Spatrick
GetReport(DDCallback * cb)4133cab2bb3Spatrick DDReport *DD::GetReport(DDCallback *cb) {
4143cab2bb3Spatrick if (!cb->pt->report_pending)
4153cab2bb3Spatrick return 0;
4163cab2bb3Spatrick cb->pt->report_pending = false;
4173cab2bb3Spatrick return &cb->pt->rep;
4183cab2bb3Spatrick }
4193cab2bb3Spatrick
4203cab2bb3Spatrick } // namespace __sanitizer
4213cab2bb3Spatrick #endif // #if SANITIZER_DEADLOCK_DETECTOR_VERSION == 2
422