1//===-- tsan_sync.cpp -----------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file is a part of ThreadSanitizer (TSan), a race detector.
10//
11//===----------------------------------------------------------------------===//
12#include "sanitizer_common/sanitizer_placement_new.h"
13#include "tsan_sync.h"
14#include "tsan_rtl.h"
15#include "tsan_mman.h"
16
17namespace __tsan {
18
19void DDMutexInit(ThreadState *thr, uptr pc, SyncVar *s);
20
21SyncVar::SyncVar() : mtx(MutexTypeSyncVar) { Reset(); }
22
23void SyncVar::Init(ThreadState *thr, uptr pc, uptr addr, bool save_stack) {
24 Reset();
25 this->addr = addr;
26 next = 0;
27 if (save_stack && !SANITIZER_GO) // Go does not use them
28 creation_stack_id = CurrentStackId(thr, pc);
29 if (common_flags()->detect_deadlocks)
30 DDMutexInit(thr, pc, s: this);
31}
32
33void SyncVar::Reset() {
34 CHECK(!ctx->resetting);
35 creation_stack_id = kInvalidStackID;
36 owner_tid = kInvalidTid;
37 last_lock.Reset();
38 recursion = 0;
39 atomic_store_relaxed(a: &flags, v: 0);
40 Free(p&: clock);
41 Free(p&: read_clock);
42}
43
44MetaMap::MetaMap()
45 : block_alloc_("heap block allocator"), sync_alloc_("sync allocator") {}
46
47void MetaMap::AllocBlock(ThreadState *thr, uptr pc, uptr p, uptr sz) {
48 u32 idx = block_alloc_.Alloc(c: &thr->proc()->block_cache);
49 MBlock *b = block_alloc_.Map(idx);
50 b->siz = sz;
51 b->tag = 0;
52 b->tid = thr->tid;
53 b->stk = CurrentStackId(thr, pc);
54 u32 *meta = MemToMeta(x: p);
55 DCHECK_EQ(*meta, 0);
56 *meta = idx | kFlagBlock;
57}
58
59uptr MetaMap::FreeBlock(Processor *proc, uptr p, bool reset) {
60 MBlock* b = GetBlock(p);
61 if (b == 0)
62 return 0;
63 uptr sz = RoundUpTo(size: b->siz, boundary: kMetaShadowCell);
64 FreeRange(proc, p, sz, reset);
65 return sz;
66}
67
68bool MetaMap::FreeRange(Processor *proc, uptr p, uptr sz, bool reset) {
69 bool has_something = false;
70 u32 *meta = MemToMeta(x: p);
71 u32 *end = MemToMeta(x: p + sz);
72 if (end == meta)
73 end++;
74 for (; meta < end; meta++) {
75 u32 idx = *meta;
76 if (idx == 0) {
77 // Note: don't write to meta in this case -- the block can be huge.
78 continue;
79 }
80 *meta = 0;
81 has_something = true;
82 while (idx != 0) {
83 if (idx & kFlagBlock) {
84 block_alloc_.Free(c: &proc->block_cache, idx: idx & ~kFlagMask);
85 break;
86 } else if (idx & kFlagSync) {
87 DCHECK(idx & kFlagSync);
88 SyncVar *s = sync_alloc_.Map(idx: idx & ~kFlagMask);
89 u32 next = s->next;
90 if (reset)
91 s->Reset();
92 sync_alloc_.Free(c: &proc->sync_cache, idx: idx & ~kFlagMask);
93 idx = next;
94 } else {
95 CHECK(0);
96 }
97 }
98 }
99 return has_something;
100}
101
102// ResetRange removes all meta objects from the range.
103// It is called for large mmap-ed regions. The function is best-effort wrt
104// freeing of meta objects, because we don't want to page in the whole range
105// which can be huge. The function probes pages one-by-one until it finds a page
106// without meta objects, at this point it stops freeing meta objects. Because
107// thread stacks grow top-down, we do the same starting from end as well.
108void MetaMap::ResetRange(Processor *proc, uptr p, uptr sz, bool reset) {
109 if (SANITIZER_GO) {
110 // UnmapOrDie/MmapFixedNoReserve does not work on Windows,
111 // so we do the optimization only for C/C++.
112 FreeRange(proc, p, sz, reset);
113 return;
114 }
115 const uptr kMetaRatio = kMetaShadowCell / kMetaShadowSize;
116 const uptr kPageSize = GetPageSizeCached() * kMetaRatio;
117 if (sz <= 4 * kPageSize) {
118 // If the range is small, just do the normal free procedure.
119 FreeRange(proc, p, sz, reset);
120 return;
121 }
122 // First, round both ends of the range to page size.
123 uptr diff = RoundUp(p, align: kPageSize) - p;
124 if (diff != 0) {
125 FreeRange(proc, p, sz: diff, reset);
126 p += diff;
127 sz -= diff;
128 }
129 diff = p + sz - RoundDown(p: p + sz, align: kPageSize);
130 if (diff != 0) {
131 FreeRange(proc, p: p + sz - diff, sz: diff, reset);
132 sz -= diff;
133 }
134 // Now we must have a non-empty page-aligned range.
135 CHECK_GT(sz, 0);
136 CHECK_EQ(p, RoundUp(p, kPageSize));
137 CHECK_EQ(sz, RoundUp(sz, kPageSize));
138 const uptr p0 = p;
139 const uptr sz0 = sz;
140 // Probe start of the range.
141 for (uptr checked = 0; sz > 0; checked += kPageSize) {
142 bool has_something = FreeRange(proc, p, sz: kPageSize, reset);
143 p += kPageSize;
144 sz -= kPageSize;
145 if (!has_something && checked > (128 << 10))
146 break;
147 }
148 // Probe end of the range.
149 for (uptr checked = 0; sz > 0; checked += kPageSize) {
150 bool has_something = FreeRange(proc, p: p + sz - kPageSize, sz: kPageSize, reset);
151 sz -= kPageSize;
152 // Stacks grow down, so sync object are most likely at the end of the region
153 // (if it is a stack). The very end of the stack is TLS and tsan increases
154 // TLS by at least 256K, so check at least 512K.
155 if (!has_something && checked > (512 << 10))
156 break;
157 }
158 // Finally, page out the whole range (including the parts that we've just
159 // freed). Note: we can't simply madvise, because we need to leave a zeroed
160 // range (otherwise __tsan_java_move can crash if it encounters a left-over
161 // meta objects in java heap).
162 uptr metap = (uptr)MemToMeta(x: p0);
163 uptr metasz = sz0 / kMetaRatio;
164 UnmapOrDie(addr: (void*)metap, size: metasz);
165 if (!MmapFixedSuperNoReserve(fixed_addr: metap, size: metasz))
166 Die();
167}
168
169void MetaMap::ResetClocks() {
170 // This can be called from the background thread
171 // which does not have proc/cache.
172 // The cache is too large for stack.
173 static InternalAllocatorCache cache;
174 internal_memset(s: &cache, c: 0, n: sizeof(cache));
175 internal_allocator()->InitCache(cache: &cache);
176 sync_alloc_.ForEach(func: [&](SyncVar *s) {
177 if (s->clock) {
178 InternalFree(p: s->clock, cache: &cache);
179 s->clock = nullptr;
180 }
181 if (s->read_clock) {
182 InternalFree(p: s->read_clock, cache: &cache);
183 s->read_clock = nullptr;
184 }
185 s->last_lock.Reset();
186 });
187 internal_allocator()->DestroyCache(cache: &cache);
188}
189
190MBlock* MetaMap::GetBlock(uptr p) {
191 u32 *meta = MemToMeta(x: p);
192 u32 idx = *meta;
193 for (;;) {
194 if (idx == 0)
195 return 0;
196 if (idx & kFlagBlock)
197 return block_alloc_.Map(idx: idx & ~kFlagMask);
198 DCHECK(idx & kFlagSync);
199 SyncVar * s = sync_alloc_.Map(idx: idx & ~kFlagMask);
200 idx = s->next;
201 }
202}
203
204SyncVar *MetaMap::GetSync(ThreadState *thr, uptr pc, uptr addr, bool create,
205 bool save_stack) {
206 DCHECK(!create || thr->slot_locked);
207 u32 *meta = MemToMeta(x: addr);
208 u32 idx0 = *meta;
209 u32 myidx = 0;
210 SyncVar *mys = nullptr;
211 for (;;) {
212 for (u32 idx = idx0; idx && !(idx & kFlagBlock);) {
213 DCHECK(idx & kFlagSync);
214 SyncVar * s = sync_alloc_.Map(idx: idx & ~kFlagMask);
215 if (LIKELY(s->addr == addr)) {
216 if (UNLIKELY(myidx != 0)) {
217 mys->Reset();
218 sync_alloc_.Free(c: &thr->proc()->sync_cache, idx: myidx);
219 }
220 return s;
221 }
222 idx = s->next;
223 }
224 if (!create)
225 return nullptr;
226 if (UNLIKELY(*meta != idx0)) {
227 idx0 = *meta;
228 continue;
229 }
230
231 if (LIKELY(myidx == 0)) {
232 myidx = sync_alloc_.Alloc(c: &thr->proc()->sync_cache);
233 mys = sync_alloc_.Map(idx: myidx);
234 mys->Init(thr, pc, addr, save_stack);
235 }
236 mys->next = idx0;
237 if (atomic_compare_exchange_strong(a: (atomic_uint32_t*)meta, cmp: &idx0,
238 xchg: myidx | kFlagSync, mo: memory_order_release)) {
239 return mys;
240 }
241 }
242}
243
244void MetaMap::MoveMemory(uptr src, uptr dst, uptr sz) {
245 // src and dst can overlap,
246 // there are no concurrent accesses to the regions (e.g. stop-the-world).
247 CHECK_NE(src, dst);
248 CHECK_NE(sz, 0);
249
250 // The current MoveMemory implementation behaves incorrectly when src, dst,
251 // and sz are not aligned to kMetaShadowCell.
252 // For example, with kMetaShadowCell == 8:
253 // - src = 4: unexpectedly clears the metadata for the range [0, 4).
254 // - src = 16, dst = 4, size = 8: A sync variable for addr = 20, which should
255 // be moved to the metadata for address 8, is incorrectly moved to the
256 // metadata for address 0 instead.
257 // - src = 0, sz = 4: fails to move the tail metadata.
258 // Therefore, the following assertions is needed.
259 DCHECK_EQ(src % kMetaShadowCell, 0);
260 DCHECK_EQ(dst % kMetaShadowCell, 0);
261 DCHECK_EQ(sz % kMetaShadowCell, 0);
262
263 uptr diff = dst - src;
264 u32 *src_meta, *dst_meta, *src_meta_end;
265 uptr inc;
266 if (dst < src) {
267 src_meta = MemToMeta(x: src);
268 dst_meta = MemToMeta(x: dst);
269 src_meta_end = MemToMeta(x: src + sz);
270 inc = 1;
271 } else {
272 src_meta = MemToMeta(x: src + sz) - 1;
273 dst_meta = MemToMeta(x: dst + sz) - 1;
274 src_meta_end = MemToMeta(x: src) - 1;
275 inc = -1;
276 }
277 for (; src_meta != src_meta_end; src_meta += inc, dst_meta += inc) {
278 CHECK_EQ(*dst_meta, 0);
279 u32 idx = *src_meta;
280 *src_meta = 0;
281 *dst_meta = idx;
282 // Patch the addresses in sync objects.
283 while (idx != 0) {
284 if (idx & kFlagBlock)
285 break;
286 CHECK(idx & kFlagSync);
287 SyncVar *s = sync_alloc_.Map(idx: idx & ~kFlagMask);
288 s->addr += diff;
289 idx = s->next;
290 }
291 }
292}
293
294void MetaMap::OnProcIdle(Processor *proc) {
295 block_alloc_.FlushCache(c: &proc->block_cache);
296 sync_alloc_.FlushCache(c: &proc->sync_cache);
297}
298
299MetaMap::MemoryStats MetaMap::GetMemoryStats() const {
300 MemoryStats stats;
301 stats.mem_block = block_alloc_.AllocatedMemory();
302 stats.sync_obj = sync_alloc_.AllocatedMemory();
303 return stats;
304}
305
306} // namespace __tsan
307