1 //===-- tsan_sync.cc ------------------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file is a part of ThreadSanitizer (TSan), a race detector.
12 //===----------------------------------------------------------------------===//
13 #include "sanitizer_common/sanitizer_placement_new.h"
14 #include "tsan_sync.h"
16 #include "tsan_mman.h"
20 void DDMutexInit(ThreadState *thr, uptr pc, SyncVar *s);
23 : mtx(MutexTypeSyncVar, StatMtxSyncVar) {
27 void SyncVar::Init(ThreadState *thr, uptr pc, uptr addr, u64 uid) {
32 creation_stack_id = 0;
33 if (!SANITIZER_GO) // Go does not use them
34 creation_stack_id = CurrentStackId(thr, pc);
35 if (common_flags()->detect_deadlocks)
36 DDMutexInit(thr, pc, this);
39 void SyncVar::Reset(Processor *proc) {
41 creation_stack_id = 0;
42 owner_tid = kInvalidTid;
45 atomic_store_relaxed(&flags, 0);
48 CHECK_EQ(clock.size(), 0);
49 CHECK_EQ(read_clock.size(), 0);
51 clock.Reset(&proc->clock_cache);
52 read_clock.Reset(&proc->clock_cache);
57 : block_alloc_("heap block allocator")
58 , sync_alloc_("sync allocator") {
59 atomic_store(&uid_gen_, 0, memory_order_relaxed);
62 void MetaMap::AllocBlock(ThreadState *thr, uptr pc, uptr p, uptr sz) {
63 u32 idx = block_alloc_.Alloc(&thr->proc()->block_cache);
64 MBlock *b = block_alloc_.Map(idx);
68 b->stk = CurrentStackId(thr, pc);
69 u32 *meta = MemToMeta(p);
71 *meta = idx | kFlagBlock;
74 uptr MetaMap::FreeBlock(Processor *proc, uptr p) {
75 MBlock* b = GetBlock(p);
78 uptr sz = RoundUpTo(b->siz, kMetaShadowCell);
79 FreeRange(proc, p, sz);
83 bool MetaMap::FreeRange(Processor *proc, uptr p, uptr sz) {
84 bool has_something = false;
85 u32 *meta = MemToMeta(p);
86 u32 *end = MemToMeta(p + sz);
89 for (; meta < end; meta++) {
92 // Note: don't write to meta in this case -- the block can be huge.
98 if (idx & kFlagBlock) {
99 block_alloc_.Free(&proc->block_cache, idx & ~kFlagMask);
101 } else if (idx & kFlagSync) {
102 DCHECK(idx & kFlagSync);
103 SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask);
106 sync_alloc_.Free(&proc->sync_cache, idx & ~kFlagMask);
113 return has_something;
116 // ResetRange removes all meta objects from the range.
117 // It is called for large mmap-ed regions. The function is best-effort wrt
118 // freeing of meta objects, because we don't want to page in the whole range
119 // which can be huge. The function probes pages one-by-one until it finds a page
120 // without meta objects, at this point it stops freeing meta objects. Because
121 // thread stacks grow top-down, we do the same starting from end as well.
122 void MetaMap::ResetRange(Processor *proc, uptr p, uptr sz) {
124 // UnmapOrDie/MmapFixedNoReserve does not work on Windows,
125 // so we do the optimization only for C/C++.
126 FreeRange(proc, p, sz);
129 const uptr kMetaRatio = kMetaShadowCell / kMetaShadowSize;
130 const uptr kPageSize = GetPageSizeCached() * kMetaRatio;
131 if (sz <= 4 * kPageSize) {
132 // If the range is small, just do the normal free procedure.
133 FreeRange(proc, p, sz);
136 // First, round both ends of the range to page size.
137 uptr diff = RoundUp(p, kPageSize) - p;
139 FreeRange(proc, p, diff);
143 diff = p + sz - RoundDown(p + sz, kPageSize);
145 FreeRange(proc, p + sz - diff, diff);
148 // Now we must have a non-empty page-aligned range.
150 CHECK_EQ(p, RoundUp(p, kPageSize));
151 CHECK_EQ(sz, RoundUp(sz, kPageSize));
154 // Probe start of the range.
155 for (uptr checked = 0; sz > 0; checked += kPageSize) {
156 bool has_something = FreeRange(proc, p, kPageSize);
159 if (!has_something && checked > (128 << 10))
162 // Probe end of the range.
163 for (uptr checked = 0; sz > 0; checked += kPageSize) {
164 bool has_something = FreeRange(proc, p + sz - kPageSize, kPageSize);
166 // Stacks grow down, so sync object are most likely at the end of the region
167 // (if it is a stack). The very end of the stack is TLS and tsan increases
168 // TLS by at least 256K, so check at least 512K.
169 if (!has_something && checked > (512 << 10))
172 // Finally, page out the whole range (including the parts that we've just
173 // freed). Note: we can't simply madvise, because we need to leave a zeroed
174 // range (otherwise __tsan_java_move can crash if it encounters a left-over
175 // meta objects in java heap).
176 uptr metap = (uptr)MemToMeta(p0);
177 uptr metasz = sz0 / kMetaRatio;
178 UnmapOrDie((void*)metap, metasz);
179 MmapFixedNoReserve(metap, metasz);
182 MBlock* MetaMap::GetBlock(uptr p) {
183 u32 *meta = MemToMeta(p);
188 if (idx & kFlagBlock)
189 return block_alloc_.Map(idx & ~kFlagMask);
190 DCHECK(idx & kFlagSync);
191 SyncVar * s = sync_alloc_.Map(idx & ~kFlagMask);
196 SyncVar* MetaMap::GetOrCreateAndLock(ThreadState *thr, uptr pc,
197 uptr addr, bool write_lock) {
198 return GetAndLock(thr, pc, addr, write_lock, true);
201 SyncVar* MetaMap::GetIfExistsAndLock(uptr addr, bool write_lock) {
202 return GetAndLock(0, 0, addr, write_lock, false);
205 SyncVar* MetaMap::GetAndLock(ThreadState *thr, uptr pc,
206 uptr addr, bool write_lock, bool create) {
207 u32 *meta = MemToMeta(addr);
216 if (idx & kFlagBlock)
218 DCHECK(idx & kFlagSync);
219 SyncVar * s = sync_alloc_.Map(idx & ~kFlagMask);
220 if (s->addr == addr) {
222 mys->Reset(thr->proc());
223 sync_alloc_.Free(&thr->proc()->sync_cache, myidx);
241 const u64 uid = atomic_fetch_add(&uid_gen_, 1, memory_order_relaxed);
242 myidx = sync_alloc_.Alloc(&thr->proc()->sync_cache);
243 mys = sync_alloc_.Map(myidx);
244 mys->Init(thr, pc, addr, uid);
247 if (atomic_compare_exchange_strong((atomic_uint32_t*)meta, &idx0,
248 myidx | kFlagSync, memory_order_release)) {
258 void MetaMap::MoveMemory(uptr src, uptr dst, uptr sz) {
259 // src and dst can overlap,
260 // there are no concurrent accesses to the regions (e.g. stop-the-world).
263 uptr diff = dst - src;
264 u32 *src_meta = MemToMeta(src);
265 u32 *dst_meta = MemToMeta(dst);
266 u32 *src_meta_end = MemToMeta(src + sz);
269 src_meta = MemToMeta(src + sz) - 1;
270 dst_meta = MemToMeta(dst + sz) - 1;
271 src_meta_end = MemToMeta(src) - 1;
274 for (; src_meta != src_meta_end; src_meta += inc, dst_meta += inc) {
275 CHECK_EQ(*dst_meta, 0);
279 // Patch the addresses in sync objects.
281 if (idx & kFlagBlock)
283 CHECK(idx & kFlagSync);
284 SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask);
291 void MetaMap::OnProcIdle(Processor *proc) {
292 block_alloc_.FlushCache(&proc->block_cache);
293 sync_alloc_.FlushCache(&proc->sync_cache);
296 } // namespace __tsan