blob: 9cc77894754ab11ebe4ef3b5c6069eddb364c51b [file] [log] [blame]
Alexey Samsonov3b2f9f42012-06-04 13:55:19 +00001//===-- tsan_sync.cc ------------------------------------------------------===//
Kostya Serebryany4ad375f2012-05-10 13:48:04 +00002//
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 Samsonov8bd90982012-06-07 09:50:16 +000013#include "sanitizer_common/sanitizer_placement_new.h"
Kostya Serebryany4ad375f2012-05-10 13:48:04 +000014#include "tsan_sync.h"
Kostya Serebryany4ad375f2012-05-10 13:48:04 +000015#include "tsan_rtl.h"
16#include "tsan_mman.h"
17
18namespace __tsan {
19
Dmitry Vyukov9b410fb2014-03-05 13:41:21 +000020void DDMutexInit(ThreadState *thr, uptr pc, SyncVar *s);
21
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +000022SyncVar::SyncVar()
23 : mtx(MutexTypeSyncVar, StatMtxSyncVar) {
Dmitry Vyukov70db9d42014-08-05 18:45:02 +000024 Reset(0);
Kostya Serebryany4ad375f2012-05-10 13:48:04 +000025}
26
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +000027void SyncVar::Init(ThreadState *thr, uptr pc, uptr addr, u64 uid) {
28 this->addr = addr;
29 this->uid = uid;
Dmitry Vyukov67ccf982014-07-08 20:37:16 +000030 this->next = 0;
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +000031
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 Serebryany4ad375f2012-05-10 13:48:04 +000037}
38
Dmitry Vyukov70db9d42014-08-05 18:45:02 +000039void SyncVar::Reset(ThreadState *thr) {
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +000040 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 Vyukovbde4c9c2014-05-29 13:50:54 +000049
Dmitry Vyukov70db9d42014-08-05 18:45:02 +000050 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 Serebryany4ad375f2012-05-10 13:48:04 +000057}
58
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +000059MetaMap::MetaMap() {
60 atomic_store(&uid_gen_, 0, memory_order_relaxed);
61}
62
63void 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
74uptr 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
83void 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 Vyukov9eaae3d2014-06-21 02:10:17 +000099 SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask);
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +0000100 u32 next = s->next;
Dmitry Vyukov70db9d42014-08-05 18:45:02 +0000101 s->Reset(thr);
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +0000102 sync_alloc_.Free(&thr->sync_cache, idx & ~kFlagMask);
103 idx = next;
104 } else {
105 CHECK(0);
106 }
Kostya Serebryany4ad375f2012-05-10 13:48:04 +0000107 }
108 }
109}
110
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +0000111MBlock* 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
125SyncVar* MetaMap::GetOrCreateAndLock(ThreadState *thr, uptr pc,
126 uptr addr, bool write_lock) {
Dmitry Vyukovfd5ebcd2012-12-06 12:16:15 +0000127 return GetAndLock(thr, pc, addr, write_lock, true);
128}
129
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +0000130SyncVar* MetaMap::GetIfExistsAndLock(uptr addr) {
131 return GetAndLock(0, 0, addr, true, false);
Dmitry Vyukovfd5ebcd2012-12-06 12:16:15 +0000132}
133
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +0000134SyncVar* MetaMap::GetAndLock(ThreadState *thr, uptr pc,
Dmitry Vyukovfd5ebcd2012-12-06 12:16:15 +0000135 uptr addr, bool write_lock, bool create) {
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +0000136 u32 *meta = MemToMeta(addr);
137 u32 idx0 = *meta;
138 u32 myidx = 0;
139 SyncVar *mys = 0;
140 for (;;) {
Dmitry Vyukov67ccf982014-07-08 20:37:16 +0000141 u32 idx = idx0;
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +0000142 for (;;) {
143 if (idx == 0)
Dmitry Vyukov1c0b3c62012-08-15 17:27:20 +0000144 break;
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +0000145 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 Vyukov70db9d42014-08-05 18:45:02 +0000151 mys->Reset(thr);
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +0000152 sync_alloc_.Free(&thr->sync_cache, myidx);
153 }
Kostya Serebryany4ad375f2012-05-10 13:48:04 +0000154 if (write_lock)
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +0000155 s->mtx.Lock();
Kostya Serebryany4ad375f2012-05-10 13:48:04 +0000156 else
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +0000157 s->mtx.ReadLock();
158 return s;
Kostya Serebryany4ad375f2012-05-10 13:48:04 +0000159 }
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +0000160 idx = s->next;
161 }
162 if (!create)
163 return 0;
Dmitry Vyukov67ccf982014-07-08 20:37:16 +0000164 if (*meta != idx0) {
165 idx0 = *meta;
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +0000166 continue;
Dmitry Vyukov67ccf982014-07-08 20:37:16 +0000167 }
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +0000168
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 Serebryany4ad375f2012-05-10 13:48:04 +0000183 }
184 }
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +0000185}
186
187void MetaMap::MoveMemory(uptr src, uptr dst, uptr sz) {
Dmitry Vyukov3f5ad1a2014-07-08 20:01:12 +0000188 // 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 Vyukovbde4c9c2014-05-29 13:50:54 +0000192 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 Vyukov3f5ad1a2014-07-08 20:01:12 +0000196 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 Vyukovbde4c9c2014-05-29 13:50:54 +0000204 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 Serebryany4ad375f2012-05-10 13:48:04 +0000211 break;
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +0000212 CHECK(idx & kFlagSync);
213 SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask);
214 s->addr += diff;
215 idx = s->next;
Kostya Serebryany4ad375f2012-05-10 13:48:04 +0000216 }
217 }
Kostya Serebryany4ad375f2012-05-10 13:48:04 +0000218}
219
Dmitry Vyukovbde4c9c2014-05-29 13:50:54 +0000220void MetaMap::OnThreadIdle(ThreadState *thr) {
221 block_alloc_.FlushCache(&thr->block_cache);
222 sync_alloc_.FlushCache(&thr->sync_cache);
Kostya Serebryany4ad375f2012-05-10 13:48:04 +0000223}
224
225} // namespace __tsan