1353944Sdim//===-- sanitizer_deadlock_detector1.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 NxN adjacency bit matrix. 10353944Sdim// 11353944Sdim//===----------------------------------------------------------------------===// 12353944Sdim 13353944Sdim#include "sanitizer_deadlock_detector_interface.h" 14353944Sdim#include "sanitizer_deadlock_detector.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 == 1 20353944Sdim 21353944Sdimnamespace __sanitizer { 22353944Sdim 23353944Sdimtypedef TwoLevelBitVector<> DDBV; // DeadlockDetector's bit vector. 24353944Sdim 25353944Sdimstruct DDPhysicalThread { 26353944Sdim}; 27353944Sdim 28353944Sdimstruct DDLogicalThread { 29353944Sdim u64 ctx; 30353944Sdim DeadlockDetectorTLS<DDBV> dd; 31353944Sdim DDReport rep; 32353944Sdim bool report_pending; 33353944Sdim}; 34353944Sdim 35353944Sdimstruct DD : public DDetector { 36353944Sdim SpinMutex mtx; 37353944Sdim DeadlockDetector<DDBV> dd; 38353944Sdim DDFlags flags; 39353944Sdim 40353944Sdim explicit DD(const DDFlags *flags); 41353944Sdim 42353944Sdim DDPhysicalThread *CreatePhysicalThread() override; 43353944Sdim void DestroyPhysicalThread(DDPhysicalThread *pt) override; 44353944Sdim 45353944Sdim DDLogicalThread *CreateLogicalThread(u64 ctx) override; 46353944Sdim void DestroyLogicalThread(DDLogicalThread *lt) override; 47353944Sdim 48353944Sdim void MutexInit(DDCallback *cb, DDMutex *m) override; 49353944Sdim void MutexBeforeLock(DDCallback *cb, DDMutex *m, bool wlock) override; 50353944Sdim void MutexAfterLock(DDCallback *cb, DDMutex *m, bool wlock, 51353944Sdim bool trylock) override; 52353944Sdim void MutexBeforeUnlock(DDCallback *cb, DDMutex *m, bool wlock) override; 53353944Sdim void MutexDestroy(DDCallback *cb, DDMutex *m) override; 54353944Sdim 55353944Sdim DDReport *GetReport(DDCallback *cb) override; 56353944Sdim 57353944Sdim void MutexEnsureID(DDLogicalThread *lt, DDMutex *m); 58353944Sdim void ReportDeadlock(DDCallback *cb, DDMutex *m); 59353944Sdim}; 60353944Sdim 61353944SdimDDetector *DDetector::Create(const DDFlags *flags) { 62353944Sdim (void)flags; 63353944Sdim void *mem = MmapOrDie(sizeof(DD), "deadlock detector"); 64353944Sdim return new(mem) DD(flags); 65353944Sdim} 66353944Sdim 67353944SdimDD::DD(const DDFlags *flags) 68353944Sdim : flags(*flags) { 69353944Sdim dd.clear(); 70353944Sdim} 71353944Sdim 72353944SdimDDPhysicalThread* DD::CreatePhysicalThread() { 73353944Sdim return nullptr; 74353944Sdim} 75353944Sdim 76353944Sdimvoid DD::DestroyPhysicalThread(DDPhysicalThread *pt) { 77353944Sdim} 78353944Sdim 79353944SdimDDLogicalThread* DD::CreateLogicalThread(u64 ctx) { 80353944Sdim DDLogicalThread *lt = (DDLogicalThread*)InternalAlloc(sizeof(*lt)); 81353944Sdim lt->ctx = ctx; 82353944Sdim lt->dd.clear(); 83353944Sdim lt->report_pending = false; 84353944Sdim return lt; 85353944Sdim} 86353944Sdim 87353944Sdimvoid DD::DestroyLogicalThread(DDLogicalThread *lt) { 88353944Sdim lt->~DDLogicalThread(); 89353944Sdim InternalFree(lt); 90353944Sdim} 91353944Sdim 92353944Sdimvoid DD::MutexInit(DDCallback *cb, DDMutex *m) { 93353944Sdim m->id = 0; 94353944Sdim m->stk = cb->Unwind(); 95353944Sdim} 96353944Sdim 97353944Sdimvoid DD::MutexEnsureID(DDLogicalThread *lt, DDMutex *m) { 98353944Sdim if (!dd.nodeBelongsToCurrentEpoch(m->id)) 99353944Sdim m->id = dd.newNode(reinterpret_cast<uptr>(m)); 100353944Sdim dd.ensureCurrentEpoch(<->dd); 101353944Sdim} 102353944Sdim 103353944Sdimvoid DD::MutexBeforeLock(DDCallback *cb, 104353944Sdim DDMutex *m, bool wlock) { 105353944Sdim DDLogicalThread *lt = cb->lt; 106353944Sdim if (lt->dd.empty()) return; // This will be the first lock held by lt. 107353944Sdim if (dd.hasAllEdges(<->dd, m->id)) return; // We already have all edges. 108353944Sdim SpinMutexLock lk(&mtx); 109353944Sdim MutexEnsureID(lt, m); 110353944Sdim if (dd.isHeld(<->dd, m->id)) 111353944Sdim return; // FIXME: allow this only for recursive locks. 112353944Sdim if (dd.onLockBefore(<->dd, m->id)) { 113353944Sdim // Actually add this edge now so that we have all the stack traces. 114353944Sdim dd.addEdges(<->dd, m->id, cb->Unwind(), cb->UniqueTid()); 115353944Sdim ReportDeadlock(cb, m); 116353944Sdim } 117353944Sdim} 118353944Sdim 119353944Sdimvoid DD::ReportDeadlock(DDCallback *cb, DDMutex *m) { 120353944Sdim DDLogicalThread *lt = cb->lt; 121353944Sdim uptr path[20]; 122353944Sdim uptr len = dd.findPathToLock(<->dd, m->id, path, ARRAY_SIZE(path)); 123353944Sdim if (len == 0U) { 124353944Sdim // A cycle of 20+ locks? Well, that's a bit odd... 125353944Sdim Printf("WARNING: too long mutex cycle found\n"); 126353944Sdim return; 127353944Sdim } 128353944Sdim CHECK_EQ(m->id, path[0]); 129353944Sdim lt->report_pending = true; 130353944Sdim len = Min<uptr>(len, DDReport::kMaxLoopSize); 131353944Sdim DDReport *rep = <->rep; 132353944Sdim rep->n = len; 133353944Sdim for (uptr i = 0; i < len; i++) { 134353944Sdim uptr from = path[i]; 135353944Sdim uptr to = path[(i + 1) % len]; 136353944Sdim DDMutex *m0 = (DDMutex*)dd.getData(from); 137353944Sdim DDMutex *m1 = (DDMutex*)dd.getData(to); 138353944Sdim 139353944Sdim u32 stk_from = -1U, stk_to = -1U; 140353944Sdim int unique_tid = 0; 141353944Sdim dd.findEdge(from, to, &stk_from, &stk_to, &unique_tid); 142353944Sdim // Printf("Edge: %zd=>%zd: %u/%u T%d\n", from, to, stk_from, stk_to, 143353944Sdim // unique_tid); 144353944Sdim rep->loop[i].thr_ctx = unique_tid; 145353944Sdim rep->loop[i].mtx_ctx0 = m0->ctx; 146353944Sdim rep->loop[i].mtx_ctx1 = m1->ctx; 147353944Sdim rep->loop[i].stk[0] = stk_to; 148353944Sdim rep->loop[i].stk[1] = stk_from; 149353944Sdim } 150353944Sdim} 151353944Sdim 152353944Sdimvoid DD::MutexAfterLock(DDCallback *cb, DDMutex *m, bool wlock, bool trylock) { 153353944Sdim DDLogicalThread *lt = cb->lt; 154353944Sdim u32 stk = 0; 155353944Sdim if (flags.second_deadlock_stack) 156353944Sdim stk = cb->Unwind(); 157353944Sdim // Printf("T%p MutexLock: %zx stk %u\n", lt, m->id, stk); 158353944Sdim if (dd.onFirstLock(<->dd, m->id, stk)) 159353944Sdim return; 160353944Sdim if (dd.onLockFast(<->dd, m->id, stk)) 161353944Sdim return; 162353944Sdim 163353944Sdim SpinMutexLock lk(&mtx); 164353944Sdim MutexEnsureID(lt, m); 165353944Sdim if (wlock) // Only a recursive rlock may be held. 166353944Sdim CHECK(!dd.isHeld(<->dd, m->id)); 167353944Sdim if (!trylock) 168353944Sdim dd.addEdges(<->dd, m->id, stk ? stk : cb->Unwind(), cb->UniqueTid()); 169353944Sdim dd.onLockAfter(<->dd, m->id, stk); 170353944Sdim} 171353944Sdim 172353944Sdimvoid DD::MutexBeforeUnlock(DDCallback *cb, DDMutex *m, bool wlock) { 173353944Sdim // Printf("T%p MutexUnLock: %zx\n", cb->lt, m->id); 174353944Sdim dd.onUnlock(&cb->lt->dd, m->id); 175353944Sdim} 176353944Sdim 177353944Sdimvoid DD::MutexDestroy(DDCallback *cb, 178353944Sdim DDMutex *m) { 179353944Sdim if (!m->id) return; 180353944Sdim SpinMutexLock lk(&mtx); 181353944Sdim if (dd.nodeBelongsToCurrentEpoch(m->id)) 182353944Sdim dd.removeNode(m->id); 183353944Sdim m->id = 0; 184353944Sdim} 185353944Sdim 186353944SdimDDReport *DD::GetReport(DDCallback *cb) { 187353944Sdim if (!cb->lt->report_pending) 188353944Sdim return nullptr; 189353944Sdim cb->lt->report_pending = false; 190353944Sdim return &cb->lt->rep; 191353944Sdim} 192353944Sdim 193353944Sdim} // namespace __sanitizer 194353944Sdim#endif // #if SANITIZER_DEADLOCK_DETECTOR_VERSION == 1 195