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
17 namespace __tsan {
18
19 void DDMutexInit(ThreadState *thr, uptr pc, SyncVar *s);
20
SyncVar()21 SyncVar::SyncVar() : mtx(MutexTypeSyncVar) { Reset(0); }
22
Init(ThreadState * thr,uptr pc,uptr addr,u64 uid)23 void SyncVar::Init(ThreadState *thr, uptr pc, uptr addr, u64 uid) {
24 this->addr = addr;
25 this->uid = uid;
26 this->next = 0;
27
28 creation_stack_id = 0;
29 if (!SANITIZER_GO) // Go does not use them
30 creation_stack_id = CurrentStackId(thr, pc);
31 if (common_flags()->detect_deadlocks)
32 DDMutexInit(thr, pc, this);
33 }
34
Reset(Processor * proc)35 void SyncVar::Reset(Processor *proc) {
36 uid = 0;
37 creation_stack_id = 0;
38 owner_tid = kInvalidTid;
39 last_lock = 0;
40 recursion = 0;
41 atomic_store_relaxed(&flags, 0);
42
43 if (proc == 0) {
44 CHECK_EQ(clock.size(), 0);
45 CHECK_EQ(read_clock.size(), 0);
46 } else {
47 clock.Reset(&proc->clock_cache);
48 read_clock.Reset(&proc->clock_cache);
49 }
50 }
51
MetaMap()52 MetaMap::MetaMap()
53 : block_alloc_(LINKER_INITIALIZED, "heap block allocator"),
54 sync_alloc_(LINKER_INITIALIZED, "sync allocator") {
55 atomic_store(&uid_gen_, 0, memory_order_relaxed);
56 }
57
AllocBlock(ThreadState * thr,uptr pc,uptr p,uptr sz)58 void MetaMap::AllocBlock(ThreadState *thr, uptr pc, uptr p, uptr sz) {
59 u32 idx = block_alloc_.Alloc(&thr->proc()->block_cache);
60 MBlock *b = block_alloc_.Map(idx);
61 b->siz = sz;
62 b->tag = 0;
63 b->tid = thr->tid;
64 b->stk = CurrentStackId(thr, pc);
65 u32 *meta = MemToMeta(p);
66 DCHECK_EQ(*meta, 0);
67 *meta = idx | kFlagBlock;
68 }
69
FreeBlock(Processor * proc,uptr p)70 uptr MetaMap::FreeBlock(Processor *proc, uptr p) {
71 MBlock* b = GetBlock(p);
72 if (b == 0)
73 return 0;
74 uptr sz = RoundUpTo(b->siz, kMetaShadowCell);
75 FreeRange(proc, p, sz);
76 return sz;
77 }
78
FreeRange(Processor * proc,uptr p,uptr sz)79 bool MetaMap::FreeRange(Processor *proc, uptr p, uptr sz) {
80 bool has_something = false;
81 u32 *meta = MemToMeta(p);
82 u32 *end = MemToMeta(p + sz);
83 if (end == meta)
84 end++;
85 for (; meta < end; meta++) {
86 u32 idx = *meta;
87 if (idx == 0) {
88 // Note: don't write to meta in this case -- the block can be huge.
89 continue;
90 }
91 *meta = 0;
92 has_something = true;
93 while (idx != 0) {
94 if (idx & kFlagBlock) {
95 block_alloc_.Free(&proc->block_cache, idx & ~kFlagMask);
96 break;
97 } else if (idx & kFlagSync) {
98 DCHECK(idx & kFlagSync);
99 SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask);
100 u32 next = s->next;
101 s->Reset(proc);
102 sync_alloc_.Free(&proc->sync_cache, idx & ~kFlagMask);
103 idx = next;
104 } else {
105 CHECK(0);
106 }
107 }
108 }
109 return has_something;
110 }
111
112 // ResetRange removes all meta objects from the range.
113 // It is called for large mmap-ed regions. The function is best-effort wrt
114 // freeing of meta objects, because we don't want to page in the whole range
115 // which can be huge. The function probes pages one-by-one until it finds a page
116 // without meta objects, at this point it stops freeing meta objects. Because
117 // thread stacks grow top-down, we do the same starting from end as well.
ResetRange(Processor * proc,uptr p,uptr sz)118 void MetaMap::ResetRange(Processor *proc, uptr p, uptr sz) {
119 if (SANITIZER_GO) {
120 // UnmapOrDie/MmapFixedNoReserve does not work on Windows,
121 // so we do the optimization only for C/C++.
122 FreeRange(proc, p, sz);
123 return;
124 }
125 const uptr kMetaRatio = kMetaShadowCell / kMetaShadowSize;
126 const uptr kPageSize = GetPageSizeCached() * kMetaRatio;
127 if (sz <= 4 * kPageSize) {
128 // If the range is small, just do the normal free procedure.
129 FreeRange(proc, p, sz);
130 return;
131 }
132 // First, round both ends of the range to page size.
133 uptr diff = RoundUp(p, kPageSize) - p;
134 if (diff != 0) {
135 FreeRange(proc, p, diff);
136 p += diff;
137 sz -= diff;
138 }
139 diff = p + sz - RoundDown(p + sz, kPageSize);
140 if (diff != 0) {
141 FreeRange(proc, p + sz - diff, diff);
142 sz -= diff;
143 }
144 // Now we must have a non-empty page-aligned range.
145 CHECK_GT(sz, 0);
146 CHECK_EQ(p, RoundUp(p, kPageSize));
147 CHECK_EQ(sz, RoundUp(sz, kPageSize));
148 const uptr p0 = p;
149 const uptr sz0 = sz;
150 // Probe start of the range.
151 for (uptr checked = 0; sz > 0; checked += kPageSize) {
152 bool has_something = FreeRange(proc, p, kPageSize);
153 p += kPageSize;
154 sz -= kPageSize;
155 if (!has_something && checked > (128 << 10))
156 break;
157 }
158 // Probe end of the range.
159 for (uptr checked = 0; sz > 0; checked += kPageSize) {
160 bool has_something = FreeRange(proc, p + sz - kPageSize, kPageSize);
161 sz -= kPageSize;
162 // Stacks grow down, so sync object are most likely at the end of the region
163 // (if it is a stack). The very end of the stack is TLS and tsan increases
164 // TLS by at least 256K, so check at least 512K.
165 if (!has_something && checked > (512 << 10))
166 break;
167 }
168 // Finally, page out the whole range (including the parts that we've just
169 // freed). Note: we can't simply madvise, because we need to leave a zeroed
170 // range (otherwise __tsan_java_move can crash if it encounters a left-over
171 // meta objects in java heap).
172 uptr metap = (uptr)MemToMeta(p0);
173 uptr metasz = sz0 / kMetaRatio;
174 UnmapOrDie((void*)metap, metasz);
175 if (!MmapFixedSuperNoReserve(metap, metasz))
176 Die();
177 }
178
GetBlock(uptr p)179 MBlock* MetaMap::GetBlock(uptr p) {
180 u32 *meta = MemToMeta(p);
181 u32 idx = *meta;
182 for (;;) {
183 if (idx == 0)
184 return 0;
185 if (idx & kFlagBlock)
186 return block_alloc_.Map(idx & ~kFlagMask);
187 DCHECK(idx & kFlagSync);
188 SyncVar * s = sync_alloc_.Map(idx & ~kFlagMask);
189 idx = s->next;
190 }
191 }
192
GetOrCreateAndLock(ThreadState * thr,uptr pc,uptr addr,bool write_lock)193 SyncVar* MetaMap::GetOrCreateAndLock(ThreadState *thr, uptr pc,
194 uptr addr, bool write_lock) {
195 return GetAndLock(thr, pc, addr, write_lock, true);
196 }
197
GetIfExistsAndLock(uptr addr,bool write_lock)198 SyncVar* MetaMap::GetIfExistsAndLock(uptr addr, bool write_lock) {
199 return GetAndLock(0, 0, addr, write_lock, false);
200 }
201
GetAndLock(ThreadState * thr,uptr pc,uptr addr,bool write_lock,bool create)202 SyncVar *MetaMap::GetAndLock(ThreadState *thr, uptr pc, uptr addr, bool write_lock,
203 bool create) NO_THREAD_SAFETY_ANALYSIS {
204 u32 *meta = MemToMeta(addr);
205 u32 idx0 = *meta;
206 u32 myidx = 0;
207 SyncVar *mys = 0;
208 for (;;) {
209 u32 idx = idx0;
210 for (;;) {
211 if (idx == 0)
212 break;
213 if (idx & kFlagBlock)
214 break;
215 DCHECK(idx & kFlagSync);
216 SyncVar * s = sync_alloc_.Map(idx & ~kFlagMask);
217 if (s->addr == addr) {
218 if (myidx != 0) {
219 mys->Reset(thr->proc());
220 sync_alloc_.Free(&thr->proc()->sync_cache, myidx);
221 }
222 if (write_lock)
223 s->mtx.Lock();
224 else
225 s->mtx.ReadLock();
226 return s;
227 }
228 idx = s->next;
229 }
230 if (!create)
231 return 0;
232 if (*meta != idx0) {
233 idx0 = *meta;
234 continue;
235 }
236
237 if (myidx == 0) {
238 const u64 uid = atomic_fetch_add(&uid_gen_, 1, memory_order_relaxed);
239 myidx = sync_alloc_.Alloc(&thr->proc()->sync_cache);
240 mys = sync_alloc_.Map(myidx);
241 mys->Init(thr, pc, addr, uid);
242 }
243 mys->next = idx0;
244 if (atomic_compare_exchange_strong((atomic_uint32_t*)meta, &idx0,
245 myidx | kFlagSync, memory_order_release)) {
246 if (write_lock)
247 mys->mtx.Lock();
248 else
249 mys->mtx.ReadLock();
250 return mys;
251 }
252 }
253 }
254
MoveMemory(uptr src,uptr dst,uptr sz)255 void MetaMap::MoveMemory(uptr src, uptr dst, uptr sz) {
256 // src and dst can overlap,
257 // there are no concurrent accesses to the regions (e.g. stop-the-world).
258 CHECK_NE(src, dst);
259 CHECK_NE(sz, 0);
260 uptr diff = dst - src;
261 u32 *src_meta = MemToMeta(src);
262 u32 *dst_meta = MemToMeta(dst);
263 u32 *src_meta_end = MemToMeta(src + sz);
264 uptr inc = 1;
265 if (dst > src) {
266 src_meta = MemToMeta(src + sz) - 1;
267 dst_meta = MemToMeta(dst + sz) - 1;
268 src_meta_end = MemToMeta(src) - 1;
269 inc = -1;
270 }
271 for (; src_meta != src_meta_end; src_meta += inc, dst_meta += inc) {
272 CHECK_EQ(*dst_meta, 0);
273 u32 idx = *src_meta;
274 *src_meta = 0;
275 *dst_meta = idx;
276 // Patch the addresses in sync objects.
277 while (idx != 0) {
278 if (idx & kFlagBlock)
279 break;
280 CHECK(idx & kFlagSync);
281 SyncVar *s = sync_alloc_.Map(idx & ~kFlagMask);
282 s->addr += diff;
283 idx = s->next;
284 }
285 }
286 }
287
OnProcIdle(Processor * proc)288 void MetaMap::OnProcIdle(Processor *proc) {
289 block_alloc_.FlushCache(&proc->block_cache);
290 sync_alloc_.FlushCache(&proc->sync_cache);
291 }
292
293 } // namespace __tsan
294