Alexey Samsonov | 3b2f9f4 | 2012-06-04 13:55:19 +0000 | [diff] [blame] | 1 | //===-- tsan_sync.cc ------------------------------------------------------===// |
Kostya Serebryany | 4ad375f | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 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 | // This file is a part of ThreadSanitizer (TSan), a race detector. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
Alexey Samsonov | 8bd9098 | 2012-06-07 09:50:16 +0000 | [diff] [blame] | 13 | #include "sanitizer_common/sanitizer_placement_new.h" |
Kostya Serebryany | 4ad375f | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 14 | #include "tsan_sync.h" |
Kostya Serebryany | 4ad375f | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 15 | #include "tsan_rtl.h" |
| 16 | #include "tsan_mman.h" |
| 17 | |
| 18 | namespace __tsan { |
| 19 | |
Dmitry Vyukov | 9b410fb | 2014-03-05 13:41:21 +0000 | [diff] [blame] | 20 | void DDMutexInit(ThreadState *thr, uptr pc, SyncVar *s); |
| 21 | |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 22 | SyncVar::SyncVar() |
| 23 | : mtx(MutexTypeSyncVar, StatMtxSyncVar) { |
Dmitry Vyukov | 70db9d4 | 2014-08-05 18:45:02 +0000 | [diff] [blame^] | 24 | Reset(0); |
Kostya Serebryany | 4ad375f | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 25 | } |
| 26 | |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 27 | void SyncVar::Init(ThreadState *thr, uptr pc, uptr addr, u64 uid) { |
| 28 | this->addr = addr; |
| 29 | this->uid = uid; |
Dmitry Vyukov | 67ccf98 | 2014-07-08 20:37:16 +0000 | [diff] [blame] | 30 | this->next = 0; |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 31 | |
| 32 | creation_stack_id = 0; |
| 33 | if (kCppMode) // Go does not use them |
| 34 | creation_stack_id = CurrentStackId(thr, pc); |
| 35 | if (flags()->detect_deadlocks) |
| 36 | DDMutexInit(thr, pc, this); |
Kostya Serebryany | 4ad375f | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 37 | } |
| 38 | |
Dmitry Vyukov | 70db9d4 | 2014-08-05 18:45:02 +0000 | [diff] [blame^] | 39 | void SyncVar::Reset(ThreadState *thr) { |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 40 | uid = 0; |
| 41 | creation_stack_id = 0; |
| 42 | owner_tid = kInvalidTid; |
| 43 | last_lock = 0; |
| 44 | recursion = 0; |
| 45 | is_rw = 0; |
| 46 | is_recursive = 0; |
| 47 | is_broken = 0; |
| 48 | is_linker_init = 0; |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 49 | |
Dmitry Vyukov | 70db9d4 | 2014-08-05 18:45:02 +0000 | [diff] [blame^] | 50 | if (thr == 0) { |
| 51 | CHECK_EQ(clock.size(), 0); |
| 52 | CHECK_EQ(read_clock.size(), 0); |
| 53 | } else { |
| 54 | clock.Reset(&thr->clock_cache); |
| 55 | read_clock.Reset(&thr->clock_cache); |
| 56 | } |
Kostya Serebryany | 4ad375f | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 57 | } |
| 58 | |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 59 | MetaMap::MetaMap() { |
| 60 | atomic_store(&uid_gen_, 0, memory_order_relaxed); |
| 61 | } |
| 62 | |
| 63 | void MetaMap::AllocBlock(ThreadState *thr, uptr pc, uptr p, uptr sz) { |
| 64 | u32 idx = block_alloc_.Alloc(&thr->block_cache); |
| 65 | MBlock *b = block_alloc_.Map(idx); |
| 66 | b->siz = sz; |
| 67 | b->tid = thr->tid; |
| 68 | b->stk = CurrentStackId(thr, pc); |
| 69 | u32 *meta = MemToMeta(p); |
| 70 | DCHECK_EQ(*meta, 0); |
| 71 | *meta = idx | kFlagBlock; |
| 72 | } |
| 73 | |
| 74 | uptr MetaMap::FreeBlock(ThreadState *thr, uptr pc, uptr p) { |
| 75 | MBlock* b = GetBlock(p); |
| 76 | if (b == 0) |
| 77 | return 0; |
| 78 | uptr sz = RoundUpTo(b->siz, kMetaShadowCell); |
| 79 | FreeRange(thr, pc, p, sz); |
| 80 | return sz; |
| 81 | } |
| 82 | |
| 83 | void MetaMap::FreeRange(ThreadState *thr, uptr pc, uptr p, uptr sz) { |
| 84 | u32 *meta = MemToMeta(p); |
| 85 | u32 *end = MemToMeta(p + sz); |
| 86 | if (end == meta) |
| 87 | end++; |
| 88 | for (; meta < end; meta++) { |
| 89 | u32 idx = *meta; |
| 90 | *meta = 0; |
| 91 | for (;;) { |
| 92 | if (idx == 0) |
| 93 | break; |
| 94 | if (idx & kFlagBlock) { |
| 95 | block_alloc_.Free(&thr->block_cache, idx & ~kFlagMask); |
| 96 | break; |
| 97 | } else if (idx & kFlagSync) { |
| 98 | DCHECK(idx & kFlagSync); |
Dmitry Vyukov | 9eaae3d | 2014-06-21 02:10:17 +0000 | [diff] [blame] | 99 | SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask); |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 100 | u32 next = s->next; |
Dmitry Vyukov | 70db9d4 | 2014-08-05 18:45:02 +0000 | [diff] [blame^] | 101 | s->Reset(thr); |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 102 | sync_alloc_.Free(&thr->sync_cache, idx & ~kFlagMask); |
| 103 | idx = next; |
| 104 | } else { |
| 105 | CHECK(0); |
| 106 | } |
Kostya Serebryany | 4ad375f | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 107 | } |
| 108 | } |
| 109 | } |
| 110 | |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 111 | MBlock* MetaMap::GetBlock(uptr p) { |
| 112 | u32 *meta = MemToMeta(p); |
| 113 | u32 idx = *meta; |
| 114 | for (;;) { |
| 115 | if (idx == 0) |
| 116 | return 0; |
| 117 | if (idx & kFlagBlock) |
| 118 | return block_alloc_.Map(idx & ~kFlagMask); |
| 119 | DCHECK(idx & kFlagSync); |
| 120 | SyncVar * s = sync_alloc_.Map(idx & ~kFlagMask); |
| 121 | idx = s->next; |
| 122 | } |
| 123 | } |
| 124 | |
| 125 | SyncVar* MetaMap::GetOrCreateAndLock(ThreadState *thr, uptr pc, |
| 126 | uptr addr, bool write_lock) { |
Dmitry Vyukov | fd5ebcd | 2012-12-06 12:16:15 +0000 | [diff] [blame] | 127 | return GetAndLock(thr, pc, addr, write_lock, true); |
| 128 | } |
| 129 | |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 130 | SyncVar* MetaMap::GetIfExistsAndLock(uptr addr) { |
| 131 | return GetAndLock(0, 0, addr, true, false); |
Dmitry Vyukov | fd5ebcd | 2012-12-06 12:16:15 +0000 | [diff] [blame] | 132 | } |
| 133 | |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 134 | SyncVar* MetaMap::GetAndLock(ThreadState *thr, uptr pc, |
Dmitry Vyukov | fd5ebcd | 2012-12-06 12:16:15 +0000 | [diff] [blame] | 135 | uptr addr, bool write_lock, bool create) { |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 136 | u32 *meta = MemToMeta(addr); |
| 137 | u32 idx0 = *meta; |
| 138 | u32 myidx = 0; |
| 139 | SyncVar *mys = 0; |
| 140 | for (;;) { |
Dmitry Vyukov | 67ccf98 | 2014-07-08 20:37:16 +0000 | [diff] [blame] | 141 | u32 idx = idx0; |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 142 | for (;;) { |
| 143 | if (idx == 0) |
Dmitry Vyukov | 1c0b3c6 | 2012-08-15 17:27:20 +0000 | [diff] [blame] | 144 | break; |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 145 | if (idx & kFlagBlock) |
| 146 | break; |
| 147 | DCHECK(idx & kFlagSync); |
| 148 | SyncVar * s = sync_alloc_.Map(idx & ~kFlagMask); |
| 149 | if (s->addr == addr) { |
| 150 | if (myidx != 0) { |
Dmitry Vyukov | 70db9d4 | 2014-08-05 18:45:02 +0000 | [diff] [blame^] | 151 | mys->Reset(thr); |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 152 | sync_alloc_.Free(&thr->sync_cache, myidx); |
| 153 | } |
Kostya Serebryany | 4ad375f | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 154 | if (write_lock) |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 155 | s->mtx.Lock(); |
Kostya Serebryany | 4ad375f | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 156 | else |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 157 | s->mtx.ReadLock(); |
| 158 | return s; |
Kostya Serebryany | 4ad375f | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 159 | } |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 160 | idx = s->next; |
| 161 | } |
| 162 | if (!create) |
| 163 | return 0; |
Dmitry Vyukov | 67ccf98 | 2014-07-08 20:37:16 +0000 | [diff] [blame] | 164 | if (*meta != idx0) { |
| 165 | idx0 = *meta; |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 166 | continue; |
Dmitry Vyukov | 67ccf98 | 2014-07-08 20:37:16 +0000 | [diff] [blame] | 167 | } |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 168 | |
| 169 | if (myidx == 0) { |
| 170 | const u64 uid = atomic_fetch_add(&uid_gen_, 1, memory_order_relaxed); |
| 171 | myidx = sync_alloc_.Alloc(&thr->sync_cache); |
| 172 | mys = sync_alloc_.Map(myidx); |
| 173 | mys->Init(thr, pc, addr, uid); |
| 174 | } |
| 175 | mys->next = idx0; |
| 176 | if (atomic_compare_exchange_strong((atomic_uint32_t*)meta, &idx0, |
| 177 | myidx | kFlagSync, memory_order_release)) { |
| 178 | if (write_lock) |
| 179 | mys->mtx.Lock(); |
| 180 | else |
| 181 | mys->mtx.ReadLock(); |
| 182 | return mys; |
Kostya Serebryany | 4ad375f | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 183 | } |
| 184 | } |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 185 | } |
| 186 | |
| 187 | void MetaMap::MoveMemory(uptr src, uptr dst, uptr sz) { |
Dmitry Vyukov | 3f5ad1a | 2014-07-08 20:01:12 +0000 | [diff] [blame] | 188 | // src and dst can overlap, |
| 189 | // there are no concurrent accesses to the regions (e.g. stop-the-world). |
| 190 | CHECK_NE(src, dst); |
| 191 | CHECK_NE(sz, 0); |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 192 | uptr diff = dst - src; |
| 193 | u32 *src_meta = MemToMeta(src); |
| 194 | u32 *dst_meta = MemToMeta(dst); |
| 195 | u32 *src_meta_end = MemToMeta(src + sz); |
Dmitry Vyukov | 3f5ad1a | 2014-07-08 20:01:12 +0000 | [diff] [blame] | 196 | uptr inc = 1; |
| 197 | if (dst > src) { |
| 198 | src_meta = MemToMeta(src + sz) - 1; |
| 199 | dst_meta = MemToMeta(dst + sz) - 1; |
| 200 | src_meta_end = MemToMeta(src) - 1; |
| 201 | inc = -1; |
| 202 | } |
| 203 | for (; src_meta != src_meta_end; src_meta += inc, dst_meta += inc) { |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 204 | CHECK_EQ(*dst_meta, 0); |
| 205 | u32 idx = *src_meta; |
| 206 | *src_meta = 0; |
| 207 | *dst_meta = idx; |
| 208 | // Patch the addresses in sync objects. |
| 209 | while (idx != 0) { |
| 210 | if (idx & kFlagBlock) |
Kostya Serebryany | 4ad375f | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 211 | break; |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 212 | CHECK(idx & kFlagSync); |
| 213 | SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask); |
| 214 | s->addr += diff; |
| 215 | idx = s->next; |
Kostya Serebryany | 4ad375f | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 216 | } |
| 217 | } |
Kostya Serebryany | 4ad375f | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 218 | } |
| 219 | |
Dmitry Vyukov | bde4c9c | 2014-05-29 13:50:54 +0000 | [diff] [blame] | 220 | void MetaMap::OnThreadIdle(ThreadState *thr) { |
| 221 | block_alloc_.FlushCache(&thr->block_cache); |
| 222 | sync_alloc_.FlushCache(&thr->sync_cache); |
Kostya Serebryany | 4ad375f | 2012-05-10 13:48:04 +0000 | [diff] [blame] | 223 | } |
| 224 | |
| 225 | } // namespace __tsan |