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 uptr diff = dst - src;
250 u32 *src_meta = MemToMeta(x: src);
251 u32 *dst_meta = MemToMeta(x: dst);
252 u32 *src_meta_end = MemToMeta(x: src + sz);
253 uptr inc = 1;
254 if (dst > src) {
255 src_meta = MemToMeta(x: src + sz) - 1;
256 dst_meta = MemToMeta(x: dst + sz) - 1;
257 src_meta_end = MemToMeta(x: src) - 1;
258 inc = -1;
259 }
260 for (; src_meta != src_meta_end; src_meta += inc, dst_meta += inc) {
261 CHECK_EQ(*dst_meta, 0);
262 u32 idx = *src_meta;
263 *src_meta = 0;
264 *dst_meta = idx;
265 // Patch the addresses in sync objects.
266 while (idx != 0) {
267 if (idx & kFlagBlock)
268 break;
269 CHECK(idx & kFlagSync);
270 SyncVar *s = sync_alloc_.Map(idx: idx & ~kFlagMask);
271 s->addr += diff;
272 idx = s->next;
273 }
274 }
275}
276
277void MetaMap::OnProcIdle(Processor *proc) {
278 block_alloc_.FlushCache(c: &proc->block_cache);
279 sync_alloc_.FlushCache(c: &proc->sync_cache);
280}
281
282MetaMap::MemoryStats MetaMap::GetMemoryStats() const {
283 MemoryStats stats;
284 stats.mem_block = block_alloc_.AllocatedMemory();
285 stats.sync_obj = sync_alloc_.AllocatedMemory();
286 return stats;
287}
288
289} // namespace __tsan
290

source code of compiler-rt/lib/tsan/rtl/tsan_sync.cpp