tsan: detect races between plain and atomic memory accesses
[blocksruntime.git] / lib / tsan / rtl / tsan_rtl.cc
blob855d645db85485039df6b1395d6ba698bb5c20a2
1 //===-- tsan_rtl.cc -------------------------------------------------------===//
2 //
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.
12 // Main file (entry points) for the TSan run-time.
13 //===----------------------------------------------------------------------===//
15 #include "sanitizer_common/sanitizer_atomic.h"
16 #include "sanitizer_common/sanitizer_common.h"
17 #include "sanitizer_common/sanitizer_libc.h"
18 #include "sanitizer_common/sanitizer_stackdepot.h"
19 #include "sanitizer_common/sanitizer_placement_new.h"
20 #include "sanitizer_common/sanitizer_symbolizer.h"
21 #include "tsan_defs.h"
22 #include "tsan_platform.h"
23 #include "tsan_rtl.h"
24 #include "tsan_mman.h"
25 #include "tsan_suppressions.h"
27 volatile int __tsan_resumed = 0;
29 extern "C" void __tsan_resume() {
30 __tsan_resumed = 1;
33 namespace __tsan {
35 #ifndef TSAN_GO
36 THREADLOCAL char cur_thread_placeholder[sizeof(ThreadState)] ALIGNED(64);
37 #endif
38 static char ctx_placeholder[sizeof(Context)] ALIGNED(64);
40 // Can be overriden by a front-end.
41 bool CPP_WEAK OnFinalize(bool failed) {
42 return failed;
45 static Context *ctx;
46 Context *CTX() {
47 return ctx;
50 Context::Context()
51 : initialized()
52 , report_mtx(MutexTypeReport, StatMtxReport)
53 , nreported()
54 , nmissed_expected()
55 , thread_mtx(MutexTypeThreads, StatMtxThreads)
56 , racy_stacks(MBlockRacyStacks)
57 , racy_addresses(MBlockRacyAddresses)
58 , fired_suppressions(MBlockRacyAddresses) {
61 // The objects are allocated in TLS, so one may rely on zero-initialization.
62 ThreadState::ThreadState(Context *ctx, int tid, int unique_id, u64 epoch,
63 uptr stk_addr, uptr stk_size,
64 uptr tls_addr, uptr tls_size)
65 : fast_state(tid, epoch)
66 // Do not touch these, rely on zero initialization,
67 // they may be accessed before the ctor.
68 // , fast_ignore_reads()
69 // , fast_ignore_writes()
70 // , in_rtl()
71 , shadow_stack_pos(&shadow_stack[0])
72 , tid(tid)
73 , unique_id(unique_id)
74 , stk_addr(stk_addr)
75 , stk_size(stk_size)
76 , tls_addr(tls_addr)
77 , tls_size(tls_size) {
80 ThreadContext::ThreadContext(int tid)
81 : tid(tid)
82 , unique_id()
83 , os_id()
84 , user_id()
85 , thr()
86 , status(ThreadStatusInvalid)
87 , detached()
88 , reuse_count()
89 , epoch0()
90 , epoch1()
91 , dead_info()
92 , dead_next()
93 , name() {
96 static void WriteMemoryProfile(char *buf, uptr buf_size, int num) {
97 uptr shadow = GetShadowMemoryConsumption();
99 int nthread = 0;
100 int nlivethread = 0;
101 uptr threadmem = 0;
103 Lock l(&ctx->thread_mtx);
104 for (unsigned i = 0; i < kMaxTid; i++) {
105 ThreadContext *tctx = ctx->threads[i];
106 if (tctx == 0)
107 continue;
108 nthread += 1;
109 threadmem += sizeof(ThreadContext);
110 if (tctx->status != ThreadStatusRunning)
111 continue;
112 nlivethread += 1;
113 threadmem += sizeof(ThreadState);
117 uptr nsync = 0;
118 uptr syncmem = CTX()->synctab.GetMemoryConsumption(&nsync);
120 internal_snprintf(buf, buf_size, "%d: shadow=%zuMB"
121 " thread=%zuMB(total=%d/live=%d)"
122 " sync=%zuMB(cnt=%zu)\n",
123 num,
124 shadow >> 20,
125 threadmem >> 20, nthread, nlivethread,
126 syncmem >> 20, nsync);
129 static void MemoryProfileThread(void *arg) {
130 ScopedInRtl in_rtl;
131 fd_t fd = (fd_t)(uptr)arg;
132 for (int i = 0; ; i++) {
133 InternalScopedBuffer<char> buf(4096);
134 WriteMemoryProfile(buf.data(), buf.size(), i);
135 internal_write(fd, buf.data(), internal_strlen(buf.data()));
136 SleepForSeconds(1);
140 static void InitializeMemoryProfile() {
141 if (flags()->profile_memory == 0 || flags()->profile_memory[0] == 0)
142 return;
143 InternalScopedBuffer<char> filename(4096);
144 internal_snprintf(filename.data(), filename.size(), "%s.%d",
145 flags()->profile_memory, GetPid());
146 fd_t fd = internal_open(filename.data(), true);
147 if (fd == kInvalidFd) {
148 Printf("Failed to open memory profile file '%s'\n", &filename[0]);
149 Die();
151 internal_start_thread(&MemoryProfileThread, (void*)(uptr)fd);
154 static void MemoryFlushThread(void *arg) {
155 ScopedInRtl in_rtl;
156 for (int i = 0; ; i++) {
157 SleepForMillis(flags()->flush_memory_ms);
158 FlushShadowMemory();
162 static void InitializeMemoryFlush() {
163 if (flags()->flush_memory_ms == 0)
164 return;
165 if (flags()->flush_memory_ms < 100)
166 flags()->flush_memory_ms = 100;
167 internal_start_thread(&MemoryFlushThread, 0);
170 void MapShadow(uptr addr, uptr size) {
171 MmapFixedNoReserve(MemToShadow(addr), size * kShadowMultiplier);
174 void MapThreadTrace(uptr addr, uptr size) {
175 DPrintf("#0: Mapping trace at %p-%p(0x%zx)\n", addr, addr + size, size);
176 CHECK_GE(addr, kTraceMemBegin);
177 CHECK_LE(addr + size, kTraceMemBegin + kTraceMemSize);
178 if (addr != (uptr)MmapFixedNoReserve(addr, size)) {
179 Printf("FATAL: ThreadSanitizer can not mmap thread trace\n");
180 Die();
184 void Initialize(ThreadState *thr) {
185 // Thread safe because done before all threads exist.
186 static bool is_initialized = false;
187 if (is_initialized)
188 return;
189 is_initialized = true;
190 SanitizerToolName = "ThreadSanitizer";
191 // Install tool-specific callbacks in sanitizer_common.
192 SetCheckFailedCallback(TsanCheckFailed);
194 ScopedInRtl in_rtl;
195 #ifndef TSAN_GO
196 InitializeAllocator();
197 #endif
198 InitializeInterceptors();
199 const char *env = InitializePlatform();
200 InitializeMutex();
201 InitializeDynamicAnnotations();
202 ctx = new(ctx_placeholder) Context;
203 #ifndef TSAN_GO
204 InitializeShadowMemory();
205 #endif
206 ctx->dead_list_size = 0;
207 ctx->dead_list_head = 0;
208 ctx->dead_list_tail = 0;
209 InitializeFlags(&ctx->flags, env);
210 // Setup correct file descriptor for error reports.
211 if (internal_strcmp(flags()->log_path, "stdout") == 0)
212 __sanitizer_set_report_fd(kStdoutFd);
213 else if (internal_strcmp(flags()->log_path, "stderr") == 0)
214 __sanitizer_set_report_fd(kStderrFd);
215 else
216 __sanitizer_set_report_path(flags()->log_path);
217 InitializeSuppressions();
218 #ifndef TSAN_GO
219 // Initialize external symbolizer before internal threads are started.
220 const char *external_symbolizer = flags()->external_symbolizer_path;
221 if (external_symbolizer != 0 && external_symbolizer[0] != '\0') {
222 if (!InitializeExternalSymbolizer(external_symbolizer)) {
223 Printf("Failed to start external symbolizer: '%s'\n",
224 external_symbolizer);
225 Die();
228 #endif
229 InitializeMemoryProfile();
230 InitializeMemoryFlush();
232 if (ctx->flags.verbosity)
233 Printf("***** Running under ThreadSanitizer v2 (pid %d) *****\n",
234 GetPid());
236 // Initialize thread 0.
237 ctx->thread_seq = 0;
238 int tid = ThreadCreate(thr, 0, 0, true);
239 CHECK_EQ(tid, 0);
240 ThreadStart(thr, tid, GetPid());
241 CHECK_EQ(thr->in_rtl, 1);
242 ctx->initialized = true;
244 if (flags()->stop_on_start) {
245 Printf("ThreadSanitizer is suspended at startup (pid %d)."
246 " Call __tsan_resume().\n",
247 GetPid());
248 while (__tsan_resumed == 0) {}
252 int Finalize(ThreadState *thr) {
253 ScopedInRtl in_rtl;
254 Context *ctx = __tsan::ctx;
255 bool failed = false;
257 if (flags()->atexit_sleep_ms > 0 && ThreadCount(thr) > 1)
258 SleepForMillis(flags()->atexit_sleep_ms);
260 // Wait for pending reports.
261 ctx->report_mtx.Lock();
262 ctx->report_mtx.Unlock();
264 #ifndef TSAN_GO
265 if (ctx->flags.verbosity)
266 AllocatorPrintStats();
267 #endif
269 ThreadFinalize(thr);
271 if (ctx->nreported) {
272 failed = true;
273 #ifndef TSAN_GO
274 Printf("ThreadSanitizer: reported %d warnings\n", ctx->nreported);
275 #else
276 Printf("Found %d data race(s)\n", ctx->nreported);
277 #endif
280 if (ctx->nmissed_expected) {
281 failed = true;
282 Printf("ThreadSanitizer: missed %d expected races\n",
283 ctx->nmissed_expected);
286 failed = OnFinalize(failed);
288 StatAggregate(ctx->stat, thr->stat);
289 StatOutput(ctx->stat);
290 return failed ? flags()->exitcode : 0;
293 #ifndef TSAN_GO
294 u32 CurrentStackId(ThreadState *thr, uptr pc) {
295 if (thr->shadow_stack_pos == 0) // May happen during bootstrap.
296 return 0;
297 if (pc) {
298 thr->shadow_stack_pos[0] = pc;
299 thr->shadow_stack_pos++;
301 u32 id = StackDepotPut(thr->shadow_stack,
302 thr->shadow_stack_pos - thr->shadow_stack);
303 if (pc)
304 thr->shadow_stack_pos--;
305 return id;
307 #endif
309 void TraceSwitch(ThreadState *thr) {
310 thr->nomalloc++;
311 ScopedInRtl in_rtl;
312 Lock l(&thr->trace.mtx);
313 unsigned trace = (thr->fast_state.epoch() / kTracePartSize) % TraceParts();
314 TraceHeader *hdr = &thr->trace.headers[trace];
315 hdr->epoch0 = thr->fast_state.epoch();
316 hdr->stack0.ObtainCurrent(thr, 0);
317 hdr->mset0 = thr->mset;
318 thr->nomalloc--;
321 uptr TraceTopPC(ThreadState *thr) {
322 Event *events = (Event*)GetThreadTrace(thr->tid);
323 uptr pc = events[thr->fast_state.GetTracePos()];
324 return pc;
327 uptr TraceSize() {
328 return (uptr)(1ull << (kTracePartSizeBits + flags()->history_size + 1));
331 uptr TraceParts() {
332 return TraceSize() / kTracePartSize;
335 #ifndef TSAN_GO
336 extern "C" void __tsan_trace_switch() {
337 TraceSwitch(cur_thread());
340 extern "C" void __tsan_report_race() {
341 ReportRace(cur_thread());
343 #endif
345 ALWAYS_INLINE
346 static Shadow LoadShadow(u64 *p) {
347 u64 raw = atomic_load((atomic_uint64_t*)p, memory_order_relaxed);
348 return Shadow(raw);
351 ALWAYS_INLINE
352 static void StoreShadow(u64 *sp, u64 s) {
353 atomic_store((atomic_uint64_t*)sp, s, memory_order_relaxed);
356 ALWAYS_INLINE
357 static void StoreIfNotYetStored(u64 *sp, u64 *s) {
358 StoreShadow(sp, *s);
359 *s = 0;
362 static inline void HandleRace(ThreadState *thr, u64 *shadow_mem,
363 Shadow cur, Shadow old) {
364 thr->racy_state[0] = cur.raw();
365 thr->racy_state[1] = old.raw();
366 thr->racy_shadow_addr = shadow_mem;
367 #ifndef TSAN_GO
368 HACKY_CALL(__tsan_report_race);
369 #else
370 ReportRace(thr);
371 #endif
374 static inline bool OldIsInSameSynchEpoch(Shadow old, ThreadState *thr) {
375 return old.epoch() >= thr->fast_synch_epoch;
378 static inline bool HappensBefore(Shadow old, ThreadState *thr) {
379 return thr->clock.get(old.TidWithIgnore()) >= old.epoch();
382 ALWAYS_INLINE
383 void MemoryAccessImpl(ThreadState *thr, uptr addr,
384 int kAccessSizeLog, bool kAccessIsWrite, bool kIsAtomic,
385 u64 *shadow_mem, Shadow cur) {
386 StatInc(thr, StatMop);
387 StatInc(thr, kAccessIsWrite ? StatMopWrite : StatMopRead);
388 StatInc(thr, (StatType)(StatMop1 + kAccessSizeLog));
390 // This potentially can live in an MMX/SSE scratch register.
391 // The required intrinsics are:
392 // __m128i _mm_move_epi64(__m128i*);
393 // _mm_storel_epi64(u64*, __m128i);
394 u64 store_word = cur.raw();
396 // scan all the shadow values and dispatch to 4 categories:
397 // same, replace, candidate and race (see comments below).
398 // we consider only 3 cases regarding access sizes:
399 // equal, intersect and not intersect. initially I considered
400 // larger and smaller as well, it allowed to replace some
401 // 'candidates' with 'same' or 'replace', but I think
402 // it's just not worth it (performance- and complexity-wise).
404 Shadow old(0);
405 if (kShadowCnt == 1) {
406 int idx = 0;
407 #include "tsan_update_shadow_word_inl.h"
408 } else if (kShadowCnt == 2) {
409 int idx = 0;
410 #include "tsan_update_shadow_word_inl.h"
411 idx = 1;
412 #include "tsan_update_shadow_word_inl.h"
413 } else if (kShadowCnt == 4) {
414 int idx = 0;
415 #include "tsan_update_shadow_word_inl.h"
416 idx = 1;
417 #include "tsan_update_shadow_word_inl.h"
418 idx = 2;
419 #include "tsan_update_shadow_word_inl.h"
420 idx = 3;
421 #include "tsan_update_shadow_word_inl.h"
422 } else if (kShadowCnt == 8) {
423 int idx = 0;
424 #include "tsan_update_shadow_word_inl.h"
425 idx = 1;
426 #include "tsan_update_shadow_word_inl.h"
427 idx = 2;
428 #include "tsan_update_shadow_word_inl.h"
429 idx = 3;
430 #include "tsan_update_shadow_word_inl.h"
431 idx = 4;
432 #include "tsan_update_shadow_word_inl.h"
433 idx = 5;
434 #include "tsan_update_shadow_word_inl.h"
435 idx = 6;
436 #include "tsan_update_shadow_word_inl.h"
437 idx = 7;
438 #include "tsan_update_shadow_word_inl.h"
439 } else {
440 CHECK(false);
443 // we did not find any races and had already stored
444 // the current access info, so we are done
445 if (LIKELY(store_word == 0))
446 return;
447 // choose a random candidate slot and replace it
448 StoreShadow(shadow_mem + (cur.epoch() % kShadowCnt), store_word);
449 StatInc(thr, StatShadowReplace);
450 return;
451 RACE:
452 HandleRace(thr, shadow_mem, cur, old);
453 return;
456 ALWAYS_INLINE
457 void MemoryAccess(ThreadState *thr, uptr pc, uptr addr,
458 int kAccessSizeLog, bool kAccessIsWrite, bool kIsAtomic) {
459 u64 *shadow_mem = (u64*)MemToShadow(addr);
460 DPrintf2("#%d: MemoryAccess: @%p %p size=%d"
461 " is_write=%d shadow_mem=%p {%zx, %zx, %zx, %zx}\n",
462 (int)thr->fast_state.tid(), (void*)pc, (void*)addr,
463 (int)(1 << kAccessSizeLog), kAccessIsWrite, shadow_mem,
464 (uptr)shadow_mem[0], (uptr)shadow_mem[1],
465 (uptr)shadow_mem[2], (uptr)shadow_mem[3]);
466 #if TSAN_DEBUG
467 if (!IsAppMem(addr)) {
468 Printf("Access to non app mem %zx\n", addr);
469 DCHECK(IsAppMem(addr));
471 if (!IsShadowMem((uptr)shadow_mem)) {
472 Printf("Bad shadow addr %p (%zx)\n", shadow_mem, addr);
473 DCHECK(IsShadowMem((uptr)shadow_mem));
475 #endif
477 FastState fast_state = thr->fast_state;
478 if (fast_state.GetIgnoreBit())
479 return;
480 fast_state.IncrementEpoch();
481 thr->fast_state = fast_state;
482 Shadow cur(fast_state);
483 cur.SetAddr0AndSizeLog(addr & 7, kAccessSizeLog);
484 cur.SetWrite(kAccessIsWrite);
485 cur.SetAtomic(kIsAtomic);
487 // We must not store to the trace if we do not store to the shadow.
488 // That is, this call must be moved somewhere below.
489 TraceAddEvent(thr, fast_state, EventTypeMop, pc);
491 MemoryAccessImpl(thr, addr, kAccessSizeLog, kAccessIsWrite, kIsAtomic,
492 shadow_mem, cur);
495 static void MemoryRangeSet(ThreadState *thr, uptr pc, uptr addr, uptr size,
496 u64 val) {
497 if (size == 0)
498 return;
499 // FIXME: fix me.
500 uptr offset = addr % kShadowCell;
501 if (offset) {
502 offset = kShadowCell - offset;
503 if (size <= offset)
504 return;
505 addr += offset;
506 size -= offset;
508 DCHECK_EQ(addr % 8, 0);
509 // If a user passes some insane arguments (memset(0)),
510 // let it just crash as usual.
511 if (!IsAppMem(addr) || !IsAppMem(addr + size - 1))
512 return;
513 (void)thr;
514 (void)pc;
515 // Some programs mmap like hundreds of GBs but actually used a small part.
516 // So, it's better to report a false positive on the memory
517 // then to hang here senselessly.
518 const uptr kMaxResetSize = 4ull*1024*1024*1024;
519 if (size > kMaxResetSize)
520 size = kMaxResetSize;
521 size = (size + (kShadowCell - 1)) & ~(kShadowCell - 1);
522 u64 *p = (u64*)MemToShadow(addr);
523 CHECK(IsShadowMem((uptr)p));
524 CHECK(IsShadowMem((uptr)(p + size * kShadowCnt / kShadowCell - 1)));
525 // FIXME: may overwrite a part outside the region
526 for (uptr i = 0; i < size * kShadowCnt / kShadowCell;) {
527 p[i++] = val;
528 for (uptr j = 1; j < kShadowCnt; j++)
529 p[i++] = 0;
533 void MemoryResetRange(ThreadState *thr, uptr pc, uptr addr, uptr size) {
534 MemoryRangeSet(thr, pc, addr, size, 0);
537 void MemoryRangeFreed(ThreadState *thr, uptr pc, uptr addr, uptr size) {
538 MemoryAccessRange(thr, pc, addr, size, true);
539 Shadow s(thr->fast_state);
540 s.ClearIgnoreBit();
541 s.MarkAsFreed();
542 s.SetWrite(true);
543 s.SetAddr0AndSizeLog(0, 3);
544 MemoryRangeSet(thr, pc, addr, size, s.raw());
547 void MemoryRangeImitateWrite(ThreadState *thr, uptr pc, uptr addr, uptr size) {
548 Shadow s(thr->fast_state);
549 s.ClearIgnoreBit();
550 s.SetWrite(true);
551 s.SetAddr0AndSizeLog(0, 3);
552 MemoryRangeSet(thr, pc, addr, size, s.raw());
555 ALWAYS_INLINE
556 void FuncEntry(ThreadState *thr, uptr pc) {
557 DCHECK_EQ(thr->in_rtl, 0);
558 StatInc(thr, StatFuncEnter);
559 DPrintf2("#%d: FuncEntry %p\n", (int)thr->fast_state.tid(), (void*)pc);
560 thr->fast_state.IncrementEpoch();
561 TraceAddEvent(thr, thr->fast_state, EventTypeFuncEnter, pc);
563 // Shadow stack maintenance can be replaced with
564 // stack unwinding during trace switch (which presumably must be faster).
565 DCHECK_GE(thr->shadow_stack_pos, &thr->shadow_stack[0]);
566 #ifndef TSAN_GO
567 DCHECK_LT(thr->shadow_stack_pos, &thr->shadow_stack[kShadowStackSize]);
568 #else
569 if (thr->shadow_stack_pos == thr->shadow_stack_end) {
570 const int sz = thr->shadow_stack_end - thr->shadow_stack;
571 const int newsz = 2 * sz;
572 uptr *newstack = (uptr*)internal_alloc(MBlockShadowStack,
573 newsz * sizeof(uptr));
574 internal_memcpy(newstack, thr->shadow_stack, sz * sizeof(uptr));
575 internal_free(thr->shadow_stack);
576 thr->shadow_stack = newstack;
577 thr->shadow_stack_pos = newstack + sz;
578 thr->shadow_stack_end = newstack + newsz;
580 #endif
581 thr->shadow_stack_pos[0] = pc;
582 thr->shadow_stack_pos++;
585 ALWAYS_INLINE
586 void FuncExit(ThreadState *thr) {
587 DCHECK_EQ(thr->in_rtl, 0);
588 StatInc(thr, StatFuncExit);
589 DPrintf2("#%d: FuncExit\n", (int)thr->fast_state.tid());
590 thr->fast_state.IncrementEpoch();
591 TraceAddEvent(thr, thr->fast_state, EventTypeFuncExit, 0);
593 DCHECK_GT(thr->shadow_stack_pos, &thr->shadow_stack[0]);
594 #ifndef TSAN_GO
595 DCHECK_LT(thr->shadow_stack_pos, &thr->shadow_stack[kShadowStackSize]);
596 #endif
597 thr->shadow_stack_pos--;
600 void IgnoreCtl(ThreadState *thr, bool write, bool begin) {
601 DPrintf("#%d: IgnoreCtl(%d, %d)\n", thr->tid, write, begin);
602 thr->ignore_reads_and_writes += begin ? 1 : -1;
603 CHECK_GE(thr->ignore_reads_and_writes, 0);
604 if (thr->ignore_reads_and_writes)
605 thr->fast_state.SetIgnoreBit();
606 else
607 thr->fast_state.ClearIgnoreBit();
610 bool MD5Hash::operator==(const MD5Hash &other) const {
611 return hash[0] == other.hash[0] && hash[1] == other.hash[1];
614 #if TSAN_DEBUG
615 void build_consistency_debug() {}
616 #else
617 void build_consistency_release() {}
618 #endif
620 #if TSAN_COLLECT_STATS
621 void build_consistency_stats() {}
622 #else
623 void build_consistency_nostats() {}
624 #endif
626 #if TSAN_SHADOW_COUNT == 1
627 void build_consistency_shadow1() {}
628 #elif TSAN_SHADOW_COUNT == 2
629 void build_consistency_shadow2() {}
630 #elif TSAN_SHADOW_COUNT == 4
631 void build_consistency_shadow4() {}
632 #else
633 void build_consistency_shadow8() {}
634 #endif
636 } // namespace __tsan
638 #ifndef TSAN_GO
639 // Must be included in this file to make sure everything is inlined.
640 #include "tsan_interface_inl.h"
641 #endif