Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 1 | //===-- sanitizer_deadlock_detector1.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 NxN adjacency bit matrix. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #include "sanitizer_deadlock_detector_interface.h" |
| 15 | #include "sanitizer_deadlock_detector.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 == 1 |
| 21 | |
| 22 | namespace __sanitizer { |
| 23 | |
| 24 | typedef TwoLevelBitVector<> DDBV; // DeadlockDetector's bit vector. |
| 25 | |
| 26 | struct DDPhysicalThread { |
| 27 | }; |
| 28 | |
| 29 | struct DDLogicalThread { |
| 30 | u64 ctx; |
| 31 | DeadlockDetectorTLS<DDBV> dd; |
| 32 | DDReport rep; |
| 33 | bool report_pending; |
| 34 | }; |
| 35 | |
| 36 | struct DD : public DDetector { |
| 37 | SpinMutex mtx; |
| 38 | DeadlockDetector<DDBV> dd; |
| 39 | DDFlags flags; |
| 40 | |
| 41 | explicit DD(const DDFlags *flags); |
| 42 | |
Pirama Arumuga Nainar | 259f706 | 2015-05-06 11:49:53 -0700 | [diff] [blame] | 43 | DDPhysicalThread *CreatePhysicalThread() override; |
| 44 | void DestroyPhysicalThread(DDPhysicalThread *pt) override; |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 45 | |
Pirama Arumuga Nainar | 259f706 | 2015-05-06 11:49:53 -0700 | [diff] [blame] | 46 | DDLogicalThread *CreateLogicalThread(u64 ctx) override; |
| 47 | void DestroyLogicalThread(DDLogicalThread *lt) override; |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 48 | |
Pirama Arumuga Nainar | 259f706 | 2015-05-06 11:49:53 -0700 | [diff] [blame] | 49 | void MutexInit(DDCallback *cb, DDMutex *m) override; |
| 50 | void MutexBeforeLock(DDCallback *cb, DDMutex *m, bool wlock) override; |
| 51 | void MutexAfterLock(DDCallback *cb, DDMutex *m, bool wlock, |
| 52 | bool trylock) override; |
| 53 | void MutexBeforeUnlock(DDCallback *cb, DDMutex *m, bool wlock) override; |
| 54 | void MutexDestroy(DDCallback *cb, DDMutex *m) override; |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 55 | |
Pirama Arumuga Nainar | 259f706 | 2015-05-06 11:49:53 -0700 | [diff] [blame] | 56 | DDReport *GetReport(DDCallback *cb) override; |
Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame] | 57 | |
| 58 | void MutexEnsureID(DDLogicalThread *lt, DDMutex *m); |
| 59 | void ReportDeadlock(DDCallback *cb, DDMutex *m); |
| 60 | }; |
| 61 | |
| 62 | DDetector *DDetector::Create(const DDFlags *flags) { |
| 63 | (void)flags; |
| 64 | void *mem = MmapOrDie(sizeof(DD), "deadlock detector"); |
| 65 | return new(mem) DD(flags); |
| 66 | } |
| 67 | |
| 68 | DD::DD(const DDFlags *flags) |
| 69 | : flags(*flags) { |
| 70 | dd.clear(); |
| 71 | } |
| 72 | |
| 73 | DDPhysicalThread* DD::CreatePhysicalThread() { |
| 74 | return 0; |
| 75 | } |
| 76 | |
| 77 | void DD::DestroyPhysicalThread(DDPhysicalThread *pt) { |
| 78 | } |
| 79 | |
| 80 | DDLogicalThread* DD::CreateLogicalThread(u64 ctx) { |
| 81 | DDLogicalThread *lt = (DDLogicalThread*)InternalAlloc(sizeof(*lt)); |
| 82 | lt->ctx = ctx; |
| 83 | lt->dd.clear(); |
| 84 | lt->report_pending = false; |
| 85 | return lt; |
| 86 | } |
| 87 | |
| 88 | void DD::DestroyLogicalThread(DDLogicalThread *lt) { |
| 89 | lt->~DDLogicalThread(); |
| 90 | InternalFree(lt); |
| 91 | } |
| 92 | |
| 93 | void DD::MutexInit(DDCallback *cb, DDMutex *m) { |
| 94 | m->id = 0; |
| 95 | m->stk = cb->Unwind(); |
| 96 | } |
| 97 | |
| 98 | void DD::MutexEnsureID(DDLogicalThread *lt, DDMutex *m) { |
| 99 | if (!dd.nodeBelongsToCurrentEpoch(m->id)) |
| 100 | m->id = dd.newNode(reinterpret_cast<uptr>(m)); |
| 101 | dd.ensureCurrentEpoch(<->dd); |
| 102 | } |
| 103 | |
| 104 | void DD::MutexBeforeLock(DDCallback *cb, |
| 105 | DDMutex *m, bool wlock) { |
| 106 | DDLogicalThread *lt = cb->lt; |
| 107 | if (lt->dd.empty()) return; // This will be the first lock held by lt. |
| 108 | if (dd.hasAllEdges(<->dd, m->id)) return; // We already have all edges. |
| 109 | SpinMutexLock lk(&mtx); |
| 110 | MutexEnsureID(lt, m); |
| 111 | if (dd.isHeld(<->dd, m->id)) |
| 112 | return; // FIXME: allow this only for recursive locks. |
| 113 | if (dd.onLockBefore(<->dd, m->id)) { |
| 114 | // Actually add this edge now so that we have all the stack traces. |
| 115 | dd.addEdges(<->dd, m->id, cb->Unwind(), cb->UniqueTid()); |
| 116 | ReportDeadlock(cb, m); |
| 117 | } |
| 118 | } |
| 119 | |
| 120 | void DD::ReportDeadlock(DDCallback *cb, DDMutex *m) { |
| 121 | DDLogicalThread *lt = cb->lt; |
| 122 | uptr path[10]; |
| 123 | uptr len = dd.findPathToLock(<->dd, m->id, path, ARRAY_SIZE(path)); |
| 124 | CHECK_GT(len, 0U); // Hm.. cycle of 10 locks? I'd like to see that. |
| 125 | CHECK_EQ(m->id, path[0]); |
| 126 | lt->report_pending = true; |
| 127 | DDReport *rep = <->rep; |
| 128 | rep->n = len; |
| 129 | for (uptr i = 0; i < len; i++) { |
| 130 | uptr from = path[i]; |
| 131 | uptr to = path[(i + 1) % len]; |
| 132 | DDMutex *m0 = (DDMutex*)dd.getData(from); |
| 133 | DDMutex *m1 = (DDMutex*)dd.getData(to); |
| 134 | |
| 135 | u32 stk_from = -1U, stk_to = -1U; |
| 136 | int unique_tid = 0; |
| 137 | dd.findEdge(from, to, &stk_from, &stk_to, &unique_tid); |
| 138 | // Printf("Edge: %zd=>%zd: %u/%u T%d\n", from, to, stk_from, stk_to, |
| 139 | // unique_tid); |
| 140 | rep->loop[i].thr_ctx = unique_tid; |
| 141 | rep->loop[i].mtx_ctx0 = m0->ctx; |
| 142 | rep->loop[i].mtx_ctx1 = m1->ctx; |
| 143 | rep->loop[i].stk[0] = stk_to; |
| 144 | rep->loop[i].stk[1] = stk_from; |
| 145 | } |
| 146 | } |
| 147 | |
| 148 | void DD::MutexAfterLock(DDCallback *cb, DDMutex *m, bool wlock, bool trylock) { |
| 149 | DDLogicalThread *lt = cb->lt; |
| 150 | u32 stk = 0; |
| 151 | if (flags.second_deadlock_stack) |
| 152 | stk = cb->Unwind(); |
| 153 | // Printf("T%p MutexLock: %zx stk %u\n", lt, m->id, stk); |
| 154 | if (dd.onFirstLock(<->dd, m->id, stk)) |
| 155 | return; |
| 156 | if (dd.onLockFast(<->dd, m->id, stk)) |
| 157 | return; |
| 158 | |
| 159 | SpinMutexLock lk(&mtx); |
| 160 | MutexEnsureID(lt, m); |
| 161 | if (wlock) // Only a recursive rlock may be held. |
| 162 | CHECK(!dd.isHeld(<->dd, m->id)); |
| 163 | if (!trylock) |
| 164 | dd.addEdges(<->dd, m->id, stk ? stk : cb->Unwind(), cb->UniqueTid()); |
| 165 | dd.onLockAfter(<->dd, m->id, stk); |
| 166 | } |
| 167 | |
| 168 | void DD::MutexBeforeUnlock(DDCallback *cb, DDMutex *m, bool wlock) { |
| 169 | // Printf("T%p MutexUnLock: %zx\n", cb->lt, m->id); |
| 170 | dd.onUnlock(&cb->lt->dd, m->id); |
| 171 | } |
| 172 | |
| 173 | void DD::MutexDestroy(DDCallback *cb, |
| 174 | DDMutex *m) { |
| 175 | if (!m->id) return; |
| 176 | SpinMutexLock lk(&mtx); |
| 177 | if (dd.nodeBelongsToCurrentEpoch(m->id)) |
| 178 | dd.removeNode(m->id); |
| 179 | m->id = 0; |
| 180 | } |
| 181 | |
| 182 | DDReport *DD::GetReport(DDCallback *cb) { |
| 183 | if (!cb->lt->report_pending) |
| 184 | return 0; |
| 185 | cb->lt->report_pending = false; |
| 186 | return &cb->lt->rep; |
| 187 | } |
| 188 | |
| 189 | } // namespace __sanitizer |
| 190 | #endif // #if SANITIZER_DEADLOCK_DETECTOR_VERSION == 1 |