libsanitizer/tsan/tsan_rtl.cc

   1 //===-- tsan_rtl.cc -------------------------------------------------------===//
   2 //
   3 // This file is distributed under the University of Illinois Open Source
   4 // License. See LICENSE.TXT for details.
   5 //
   6 //===----------------------------------------------------------------------===//
   7 //
   8 // This file is a part of ThreadSanitizer (TSan), a race detector.
   9 //
  10 // Main file (entry points) for the TSan run-time.
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "sanitizer_common/sanitizer_atomic.h"
  14 #include "sanitizer_common/sanitizer_common.h"
  15 #include "sanitizer_common/sanitizer_libc.h"
  16 #include "sanitizer_common/sanitizer_stackdepot.h"
  17 #include "sanitizer_common/sanitizer_placement_new.h"
  18 #include "sanitizer_common/sanitizer_symbolizer.h"
  19 #include "tsan_defs.h"
  20 #include "tsan_platform.h"
  21 #include "tsan_rtl.h"
  22 #include "tsan_mman.h"
  23 #include "tsan_suppressions.h"
  24 #include "tsan_symbolize.h"
  25
  26 #ifdef __SSE3__
  27 // <emmintrin.h> transitively includes <stdlib.h>,
  28 // and it's prohibited to include std headers into tsan runtime.
  29 // So we do this dirty trick.
  30 #define _MM_MALLOC_H_INCLUDED
  31 #define __MM_MALLOC_H
  32 #include <emmintrin.h>
  33 typedef __m128i m128;
  34 #endif
  35
  36 volatile int __tsan_resumed = 0;
  37
  38 extern "C" void __tsan_resume() {
  39   __tsan_resumed = 1;
  40 }
  41
  42 namespace __tsan {
  43
  44 #ifndef TSAN_GO
  45 THREADLOCAL char cur_thread_placeholder[sizeof(ThreadState)] ALIGNED(64);
  46 #endif
  47 static char ctx_placeholder[sizeof(Context)] ALIGNED(64);
  48 Context *ctx;
  49
  50 // Can be overriden by a front-end.
  51 #ifdef TSAN_EXTERNAL_HOOKS
  52 bool OnFinalize(bool failed);
  53 void OnInitialize();
  54 #else
  55 SANITIZER_INTERFACE_ATTRIBUTE
  56 bool WEAK OnFinalize(bool failed) {
  57   return failed;
  58 }
  59 SANITIZER_INTERFACE_ATTRIBUTE
  60 void WEAK OnInitialize() {}
  61 #endif
  62
  63 static char thread_registry_placeholder[sizeof(ThreadRegistry)];
  64
  65 static ThreadContextBase *CreateThreadContext(u32 tid) {
  66   // Map thread trace when context is created.
  67   MapThreadTrace(GetThreadTrace(tid), TraceSize() * sizeof(Event));
  68   MapThreadTrace(GetThreadTraceHeader(tid), sizeof(Trace));
  69   new(ThreadTrace(tid)) Trace();
  70   void *mem = internal_alloc(MBlockThreadContex, sizeof(ThreadContext));
  71   return new(mem) ThreadContext(tid);
  72 }
  73
  74 #ifndef TSAN_GO
  75 static const u32 kThreadQuarantineSize = 16;
  76 #else
  77 static const u32 kThreadQuarantineSize = 64;
  78 #endif
  79
  80 Context::Context()
  81   : initialized()
  82   , report_mtx(MutexTypeReport, StatMtxReport)
  83   , nreported()
  84   , nmissed_expected()
  85   , thread_registry(new(thread_registry_placeholder) ThreadRegistry(
  86       CreateThreadContext, kMaxTid, kThreadQuarantineSize, kMaxTidReuse))
  87   , racy_stacks(MBlockRacyStacks)
  88   , racy_addresses(MBlockRacyAddresses)
  89   , fired_suppressions(8) {
  90 }
  91
  92 // The objects are allocated in TLS, so one may rely on zero-initialization.
  93 ThreadState::ThreadState(Context *ctx, int tid, int unique_id, u64 epoch,
  94                          unsigned reuse_count,
  95                          uptr stk_addr, uptr stk_size,
  96                          uptr tls_addr, uptr tls_size)
  97   : fast_state(tid, epoch)
  98   // Do not touch these, rely on zero initialization,
  99   // they may be accessed before the ctor.
 100   // , ignore_reads_and_writes()
 101   // , ignore_interceptors()
 102   , clock(tid, reuse_count)
 103 #ifndef TSAN_GO
 104   , jmp_bufs(MBlockJmpBuf)
 105 #endif
 106   , tid(tid)
 107   , unique_id(unique_id)
 108   , stk_addr(stk_addr)
 109   , stk_size(stk_size)
 110   , tls_addr(tls_addr)
 111   , tls_size(tls_size)
 112 #ifndef TSAN_GO
 113   , last_sleep_clock(tid)
 114 #endif
 115 {
 116 }
 117
 118 static void MemoryProfiler(Context *ctx, fd_t fd, int i) {
 119   uptr n_threads;
 120   uptr n_running_threads;
 121   ctx->thread_registry->GetNumberOfThreads(&n_threads, &n_running_threads);
 122   InternalScopedBuffer<char> buf(4096);
 123   WriteMemoryProfile(buf.data(), buf.size(), n_threads, n_running_threads);
 124   internal_write(fd, buf.data(), internal_strlen(buf.data()));
 125 }
 126
 127 static void BackgroundThread(void *arg) {
 128 #ifndef TSAN_GO
 129   // This is a non-initialized non-user thread, nothing to see here.
 130   // We don't use ScopedIgnoreInterceptors, because we want ignores to be
 131   // enabled even when the thread function exits (e.g. during pthread thread
 132   // shutdown code).
 133   cur_thread()->ignore_interceptors++;
 134 #endif
 135   const u64 kMs2Ns = 1000 * 1000;
 136
 137   fd_t mprof_fd = kInvalidFd;
 138   if (flags()->profile_memory && flags()->profile_memory[0]) {
 139     if (internal_strcmp(flags()->profile_memory, "stdout") == 0) {
 140       mprof_fd = 1;
 141     } else if (internal_strcmp(flags()->profile_memory, "stderr") == 0) {
 142       mprof_fd = 2;
 143     } else {
 144       InternalScopedBuffer<char> filename(4096);
 145       internal_snprintf(filename.data(), filename.size(), "%s.%d",
 146           flags()->profile_memory, (int)internal_getpid());
 147       uptr openrv = OpenFile(filename.data(), true);
 148       if (internal_iserror(openrv)) {
 149         Printf("ThreadSanitizer: failed to open memory profile file '%s'\n",
 150             &filename[0]);
 151       } else {
 152         mprof_fd = openrv;
 153       }
 154     }
 155   }
 156
 157   u64 last_flush = NanoTime();
 158   uptr last_rss = 0;
 159   for (int i = 0;
 160       atomic_load(&ctx->stop_background_thread, memory_order_relaxed) == 0;
 161       i++) {
 162     SleepForMillis(100);
 163     u64 now = NanoTime();
 164
 165     // Flush memory if requested.
 166     if (flags()->flush_memory_ms > 0) {
 167       if (last_flush + flags()->flush_memory_ms * kMs2Ns < now) {
 168         VPrintf(1, "ThreadSanitizer: periodic memory flush\n");
 169         FlushShadowMemory();
 170         last_flush = NanoTime();
 171       }
 172     }
 173     // GetRSS can be expensive on huge programs, so don't do it every 100ms.
 174     if (flags()->memory_limit_mb > 0) {
 175       uptr rss = GetRSS();
 176       uptr limit = uptr(flags()->memory_limit_mb) << 20;
 177       VPrintf(1, "ThreadSanitizer: memory flush check"
 178                  " RSS=%llu LAST=%llu LIMIT=%llu\n",
 179               (u64)rss >> 20, (u64)last_rss >> 20, (u64)limit >> 20);
 180       if (2 * rss > limit + last_rss) {
 181         VPrintf(1, "ThreadSanitizer: flushing memory due to RSS\n");
 182         FlushShadowMemory();
 183         rss = GetRSS();
 184         VPrintf(1, "ThreadSanitizer: memory flushed RSS=%llu\n", (u64)rss>>20);
 185       }
 186       last_rss = rss;
 187     }
 188
 189     // Write memory profile if requested.
 190     if (mprof_fd != kInvalidFd)
 191       MemoryProfiler(ctx, mprof_fd, i);
 192
 193 #ifndef TSAN_GO
 194     // Flush symbolizer cache if requested.
 195     if (flags()->flush_symbolizer_ms > 0) {
 196       u64 last = atomic_load(&ctx->last_symbolize_time_ns,
 197                              memory_order_relaxed);
 198       if (last != 0 && last + flags()->flush_symbolizer_ms * kMs2Ns < now) {
 199         Lock l(&ctx->report_mtx);
 200         SpinMutexLock l2(&CommonSanitizerReportMutex);
 201         SymbolizeFlush();
 202         atomic_store(&ctx->last_symbolize_time_ns, 0, memory_order_relaxed);
 203       }
 204     }
 205 #endif
 206   }
 207 }
 208
 209 static void StartBackgroundThread() {
 210   ctx->background_thread = internal_start_thread(&BackgroundThread, 0);
 211 }
 212
 213 #ifndef TSAN_GO
 214 static void StopBackgroundThread() {
 215   atomic_store(&ctx->stop_background_thread, 1, memory_order_relaxed);
 216   internal_join_thread(ctx->background_thread);
 217   ctx->background_thread = 0;
 218 }
 219 #endif
 220
 221 void DontNeedShadowFor(uptr addr, uptr size) {
 222   uptr shadow_beg = MemToShadow(addr);
 223   uptr shadow_end = MemToShadow(addr + size);
 224   FlushUnneededShadowMemory(shadow_beg, shadow_end - shadow_beg);
 225 }
 226
 227 void MapShadow(uptr addr, uptr size) {
 228   // Global data is not 64K aligned, but there are no adjacent mappings,
 229   // so we can get away with unaligned mapping.
 230   // CHECK_EQ(addr, addr & ~((64 << 10) - 1));  // windows wants 64K alignment
 231   MmapFixedNoReserve(MemToShadow(addr), size * kShadowMultiplier);
 232
 233   // Meta shadow is 2:1, so tread carefully.
 234   static bool data_mapped = false;
 235   static uptr mapped_meta_end = 0;
 236   uptr meta_begin = (uptr)MemToMeta(addr);
 237   uptr meta_end = (uptr)MemToMeta(addr + size);
 238   meta_begin = RoundDownTo(meta_begin, 64 << 10);
 239   meta_end = RoundUpTo(meta_end, 64 << 10);
 240   if (!data_mapped) {
 241     // First call maps data+bss.
 242     data_mapped = true;
 243     MmapFixedNoReserve(meta_begin, meta_end - meta_begin);
 244   } else {
 245     // Mapping continous heap.
 246     // Windows wants 64K alignment.
 247     meta_begin = RoundDownTo(meta_begin, 64 << 10);
 248     meta_end = RoundUpTo(meta_end, 64 << 10);
 249     if (meta_end <= mapped_meta_end)
 250       return;
 251     if (meta_begin < mapped_meta_end)
 252       meta_begin = mapped_meta_end;
 253     MmapFixedNoReserve(meta_begin, meta_end - meta_begin);
 254     mapped_meta_end = meta_end;
 255   }
 256   VPrintf(2, "mapped meta shadow for (%p-%p) at (%p-%p)\n",
 257       addr, addr+size, meta_begin, meta_end);
 258 }
 259
 260 void MapThreadTrace(uptr addr, uptr size) {
 261   DPrintf("#0: Mapping trace at %p-%p(0x%zx)\n", addr, addr + size, size);
 262   CHECK_GE(addr, kTraceMemBegin);
 263   CHECK_LE(addr + size, kTraceMemBegin + kTraceMemSize);
 264   CHECK_EQ(addr, addr & ~((64 << 10) - 1));  // windows wants 64K alignment
 265   uptr addr1 = (uptr)MmapFixedNoReserve(addr, size);
 266   if (addr1 != addr) {
 267     Printf("FATAL: ThreadSanitizer can not mmap thread trace (%p/%p->%p)\n",
 268         addr, size, addr1);
 269     Die();
 270   }
 271 }
 272
 273 void Initialize(ThreadState *thr) {
 274   // Thread safe because done before all threads exist.
 275   static bool is_initialized = false;
 276   if (is_initialized)
 277     return;
 278   is_initialized = true;
 279   // We are not ready to handle interceptors yet.
 280   ScopedIgnoreInterceptors ignore;
 281   SanitizerToolName = "ThreadSanitizer";
 282   // Install tool-specific callbacks in sanitizer_common.
 283   SetCheckFailedCallback(TsanCheckFailed);
 284
 285   ctx = new(ctx_placeholder) Context;
 286   const char *options = GetEnv(kTsanOptionsEnv);
 287   InitializeFlags(&ctx->flags, options);
 288 #ifndef TSAN_GO
 289   InitializeAllocator();
 290 #endif
 291   InitializeInterceptors();
 292   InitializePlatform();
 293   InitializeMutex();
 294   InitializeDynamicAnnotations();
 295 #ifndef TSAN_GO
 296   InitializeShadowMemory();
 297 #endif
 298   // Setup correct file descriptor for error reports.
 299   __sanitizer_set_report_path(common_flags()->log_path);
 300   InitializeSuppressions();
 301 #ifndef TSAN_GO
 302   InitializeLibIgnore();
 303   Symbolizer::GetOrInit()->AddHooks(EnterSymbolizer, ExitSymbolizer);
 304 #endif
 305   StartBackgroundThread();
 306 #ifndef TSAN_GO
 307   SetSandboxingCallback(StopBackgroundThread);
 308 #endif
 309   if (common_flags()->detect_deadlocks)
 310     ctx->dd = DDetector::Create(flags());
 311
 312   VPrintf(1, "***** Running under ThreadSanitizer v2 (pid %d) *****\n",
 313           (int)internal_getpid());
 314
 315   // Initialize thread 0.
 316   int tid = ThreadCreate(thr, 0, 0, true);
 317   CHECK_EQ(tid, 0);
 318   ThreadStart(thr, tid, internal_getpid());
 319   ctx->initialized = true;
 320
 321   if (flags()->stop_on_start) {
 322     Printf("ThreadSanitizer is suspended at startup (pid %d)."
 323            " Call __tsan_resume().\n",
 324            (int)internal_getpid());
 325     while (__tsan_resumed == 0) {}
 326   }
 327
 328   OnInitialize();
 329 }
 330
 331 int Finalize(ThreadState *thr) {
 332   bool failed = false;
 333
 334   if (flags()->atexit_sleep_ms > 0 && ThreadCount(thr) > 1)
 335     SleepForMillis(flags()->atexit_sleep_ms);
 336
 337   // Wait for pending reports.
 338   ctx->report_mtx.Lock();
 339   CommonSanitizerReportMutex.Lock();
 340   CommonSanitizerReportMutex.Unlock();
 341   ctx->report_mtx.Unlock();
 342
 343 #ifndef TSAN_GO
 344   if (common_flags()->verbosity)
 345     AllocatorPrintStats();
 346 #endif
 347
 348   ThreadFinalize(thr);
 349
 350   if (ctx->nreported) {
 351     failed = true;
 352 #ifndef TSAN_GO
 353     Printf("ThreadSanitizer: reported %d warnings\n", ctx->nreported);
 354 #else
 355     Printf("Found %d data race(s)\n", ctx->nreported);
 356 #endif
 357   }
 358
 359   if (ctx->nmissed_expected) {
 360     failed = true;
 361     Printf("ThreadSanitizer: missed %d expected races\n",
 362         ctx->nmissed_expected);
 363   }
 364
 365   if (common_flags()->print_suppressions)
 366     PrintMatchedSuppressions();
 367 #ifndef TSAN_GO
 368   if (flags()->print_benign)
 369     PrintMatchedBenignRaces();
 370 #endif
 371
 372   failed = OnFinalize(failed);
 373
 374   StatAggregate(ctx->stat, thr->stat);
 375   StatOutput(ctx->stat);
 376   return failed ? flags()->exitcode : 0;
 377 }
 378
 379 #ifndef TSAN_GO
 380 void ForkBefore(ThreadState *thr, uptr pc) {
 381   ctx->thread_registry->Lock();
 382   ctx->report_mtx.Lock();
 383 }
 384
 385 void ForkParentAfter(ThreadState *thr, uptr pc) {
 386   ctx->report_mtx.Unlock();
 387   ctx->thread_registry->Unlock();
 388 }
 389
 390 void ForkChildAfter(ThreadState *thr, uptr pc) {
 391   ctx->report_mtx.Unlock();
 392   ctx->thread_registry->Unlock();
 393
 394   uptr nthread = 0;
 395   ctx->thread_registry->GetNumberOfThreads(0, 0, &nthread /* alive threads */);
 396   VPrintf(1, "ThreadSanitizer: forked new process with pid %d,"
 397       " parent had %d threads\n", (int)internal_getpid(), (int)nthread);
 398   if (nthread == 1) {
 399     internal_start_thread(&BackgroundThread, 0);
 400   } else {
 401     // We've just forked a multi-threaded process. We cannot reasonably function
 402     // after that (some mutexes may be locked before fork). So just enable
 403     // ignores for everything in the hope that we will exec soon.
 404     ctx->after_multithreaded_fork = true;
 405     thr->ignore_interceptors++;
 406     ThreadIgnoreBegin(thr, pc);
 407     ThreadIgnoreSyncBegin(thr, pc);
 408   }
 409 }
 410 #endif
 411
 412 #ifdef TSAN_GO
 413 NOINLINE
 414 void GrowShadowStack(ThreadState *thr) {
 415   const int sz = thr->shadow_stack_end - thr->shadow_stack;
 416   const int newsz = 2 * sz;
 417   uptr *newstack = (uptr*)internal_alloc(MBlockShadowStack,
 418       newsz * sizeof(uptr));
 419   internal_memcpy(newstack, thr->shadow_stack, sz * sizeof(uptr));
 420   internal_free(thr->shadow_stack);
 421   thr->shadow_stack = newstack;
 422   thr->shadow_stack_pos = newstack + sz;
 423   thr->shadow_stack_end = newstack + newsz;
 424 }
 425 #endif
 426
 427 u32 CurrentStackId(ThreadState *thr, uptr pc) {
 428   if (thr->shadow_stack_pos == 0)  // May happen during bootstrap.
 429     return 0;
 430   if (pc != 0) {
 431 #ifndef TSAN_GO
 432     DCHECK_LT(thr->shadow_stack_pos, thr->shadow_stack_end);
 433 #else
 434     if (thr->shadow_stack_pos == thr->shadow_stack_end)
 435       GrowShadowStack(thr);
 436 #endif
 437     thr->shadow_stack_pos[0] = pc;
 438     thr->shadow_stack_pos++;
 439   }
 440   u32 id = StackDepotPut(thr->shadow_stack,
 441                          thr->shadow_stack_pos - thr->shadow_stack);
 442   if (pc != 0)
 443     thr->shadow_stack_pos--;
 444   return id;
 445 }
 446
 447 void TraceSwitch(ThreadState *thr) {
 448   thr->nomalloc++;
 449   Trace *thr_trace = ThreadTrace(thr->tid);
 450   Lock l(&thr_trace->mtx);
 451   unsigned trace = (thr->fast_state.epoch() / kTracePartSize) % TraceParts();
 452   TraceHeader *hdr = &thr_trace->headers[trace];
 453   hdr->epoch0 = thr->fast_state.epoch();
 454   hdr->stack0.ObtainCurrent(thr, 0);
 455   hdr->mset0 = thr->mset;
 456   thr->nomalloc--;
 457 }
 458
 459 Trace *ThreadTrace(int tid) {
 460   return (Trace*)GetThreadTraceHeader(tid);
 461 }
 462
 463 uptr TraceTopPC(ThreadState *thr) {
 464   Event *events = (Event*)GetThreadTrace(thr->tid);
 465   uptr pc = events[thr->fast_state.GetTracePos()];
 466   return pc;
 467 }
 468
 469 uptr TraceSize() {
 470   return (uptr)(1ull << (kTracePartSizeBits + flags()->history_size + 1));
 471 }
 472
 473 uptr TraceParts() {
 474   return TraceSize() / kTracePartSize;
 475 }
 476
 477 #ifndef TSAN_GO
 478 extern "C" void __tsan_trace_switch() {
 479   TraceSwitch(cur_thread());
 480 }
 481
 482 extern "C" void __tsan_report_race() {
 483   ReportRace(cur_thread());
 484 }
 485 #endif
 486
 487 ALWAYS_INLINE
 488 Shadow LoadShadow(u64 *p) {
 489   u64 raw = atomic_load((atomic_uint64_t*)p, memory_order_relaxed);
 490   return Shadow(raw);
 491 }
 492
 493 ALWAYS_INLINE
 494 void StoreShadow(u64 *sp, u64 s) {
 495   atomic_store((atomic_uint64_t*)sp, s, memory_order_relaxed);
 496 }
 497
 498 ALWAYS_INLINE
 499 void StoreIfNotYetStored(u64 *sp, u64 *s) {
 500   StoreShadow(sp, *s);
 501   *s = 0;
 502 }
 503
 504 ALWAYS_INLINE
 505 void HandleRace(ThreadState *thr, u64 *shadow_mem,
 506                               Shadow cur, Shadow old) {
 507   thr->racy_state[0] = cur.raw();
 508   thr->racy_state[1] = old.raw();
 509   thr->racy_shadow_addr = shadow_mem;
 510 #ifndef TSAN_GO
 511   HACKY_CALL(__tsan_report_race);
 512 #else
 513   ReportRace(thr);
 514 #endif
 515 }
 516
 517 static inline bool HappensBefore(Shadow old, ThreadState *thr) {
 518   return thr->clock.get(old.TidWithIgnore()) >= old.epoch();
 519 }
 520
 521 ALWAYS_INLINE
 522 void MemoryAccessImpl1(ThreadState *thr, uptr addr,
 523     int kAccessSizeLog, bool kAccessIsWrite, bool kIsAtomic,
 524     u64 *shadow_mem, Shadow cur) {
 525   StatInc(thr, StatMop);
 526   StatInc(thr, kAccessIsWrite ? StatMopWrite : StatMopRead);
 527   StatInc(thr, (StatType)(StatMop1 + kAccessSizeLog));
 528
 529   // This potentially can live in an MMX/SSE scratch register.
 530   // The required intrinsics are:
 531   // __m128i _mm_move_epi64(__m128i*);
 532   // _mm_storel_epi64(u64*, __m128i);
 533   u64 store_word = cur.raw();
 534
 535   // scan all the shadow values and dispatch to 4 categories:
 536   // same, replace, candidate and race (see comments below).
 537   // we consider only 3 cases regarding access sizes:
 538   // equal, intersect and not intersect. initially I considered
 539   // larger and smaller as well, it allowed to replace some
 540   // 'candidates' with 'same' or 'replace', but I think
 541   // it's just not worth it (performance- and complexity-wise).
 542
 543   Shadow old(0);
 544   if (kShadowCnt == 1) {
 545     int idx = 0;
 546 #include "tsan_update_shadow_word_inl.h"
 547   } else if (kShadowCnt == 2) {
 548     int idx = 0;
 549 #include "tsan_update_shadow_word_inl.h"
 550     idx = 1;
 551 #include "tsan_update_shadow_word_inl.h"
 552   } else if (kShadowCnt == 4) {
 553     int idx = 0;
 554 #include "tsan_update_shadow_word_inl.h"
 555     idx = 1;
 556 #include "tsan_update_shadow_word_inl.h"
 557     idx = 2;
 558 #include "tsan_update_shadow_word_inl.h"
 559     idx = 3;
 560 #include "tsan_update_shadow_word_inl.h"
 561   } else if (kShadowCnt == 8) {
 562     int idx = 0;
 563 #include "tsan_update_shadow_word_inl.h"
 564     idx = 1;
 565 #include "tsan_update_shadow_word_inl.h"
 566     idx = 2;
 567 #include "tsan_update_shadow_word_inl.h"
 568     idx = 3;
 569 #include "tsan_update_shadow_word_inl.h"
 570     idx = 4;
 571 #include "tsan_update_shadow_word_inl.h"
 572     idx = 5;
 573 #include "tsan_update_shadow_word_inl.h"
 574     idx = 6;
 575 #include "tsan_update_shadow_word_inl.h"
 576     idx = 7;
 577 #include "tsan_update_shadow_word_inl.h"
 578   } else {
 579     CHECK(false);
 580   }
 581
 582   // we did not find any races and had already stored
 583   // the current access info, so we are done
 584   if (LIKELY(store_word == 0))
 585     return;
 586   // choose a random candidate slot and replace it
 587   StoreShadow(shadow_mem + (cur.epoch() % kShadowCnt), store_word);
 588   StatInc(thr, StatShadowReplace);
 589   return;
 590  RACE:
 591   HandleRace(thr, shadow_mem, cur, old);
 592   return;
 593 }
 594
 595 void UnalignedMemoryAccess(ThreadState *thr, uptr pc, uptr addr,
 596     int size, bool kAccessIsWrite, bool kIsAtomic) {
 597   while (size) {
 598     int size1 = 1;
 599     int kAccessSizeLog = kSizeLog1;
 600     if (size >= 8 && (addr & ~7) == ((addr + 7) & ~7)) {
 601       size1 = 8;
 602       kAccessSizeLog = kSizeLog8;
 603     } else if (size >= 4 && (addr & ~7) == ((addr + 3) & ~7)) {
 604       size1 = 4;
 605       kAccessSizeLog = kSizeLog4;
 606     } else if (size >= 2 && (addr & ~7) == ((addr + 1) & ~7)) {
 607       size1 = 2;
 608       kAccessSizeLog = kSizeLog2;
 609     }
 610     MemoryAccess(thr, pc, addr, kAccessSizeLog, kAccessIsWrite, kIsAtomic);
 611     addr += size1;
 612     size -= size1;
 613   }
 614 }
 615
 616 ALWAYS_INLINE
 617 bool ContainsSameAccessSlow(u64 *s, u64 a, u64 sync_epoch, bool is_write) {
 618   Shadow cur(a);
 619   for (uptr i = 0; i < kShadowCnt; i++) {
 620     Shadow old(LoadShadow(&s[i]));
 621     if (Shadow::Addr0AndSizeAreEqual(cur, old) &&
 622         old.TidWithIgnore() == cur.TidWithIgnore() &&
 623         old.epoch() > sync_epoch &&
 624         old.IsAtomic() == cur.IsAtomic() &&
 625         old.IsRead() <= cur.IsRead())
 626       return true;
 627   }
 628   return false;
 629 }
 630
 631 #if defined(__SSE3__) && TSAN_SHADOW_COUNT == 4
 632 #define SHUF(v0, v1, i0, i1, i2, i3) _mm_castps_si128(_mm_shuffle_ps( \
 633     _mm_castsi128_ps(v0), _mm_castsi128_ps(v1), \
 634     (i0)*1 + (i1)*4 + (i2)*16 + (i3)*64))
 635 ALWAYS_INLINE
 636 bool ContainsSameAccessFast(u64 *s, u64 a, u64 sync_epoch, bool is_write) {
 637   // This is an optimized version of ContainsSameAccessSlow.
 638   // load current access into access[0:63]
 639   const m128 access     = _mm_cvtsi64_si128(a);
 640   // duplicate high part of access in addr0:
 641   // addr0[0:31]        = access[32:63]
 642   // addr0[32:63]       = access[32:63]
 643   // addr0[64:95]       = access[32:63]
 644   // addr0[96:127]      = access[32:63]
 645   const m128 addr0      = SHUF(access, access, 1, 1, 1, 1);
 646   // load 4 shadow slots
 647   const m128 shadow0    = _mm_load_si128((__m128i*)s);
 648   const m128 shadow1    = _mm_load_si128((__m128i*)s + 1);
 649   // load high parts of 4 shadow slots into addr_vect:
 650   // addr_vect[0:31]    = shadow0[32:63]
 651   // addr_vect[32:63]   = shadow0[96:127]
 652   // addr_vect[64:95]   = shadow1[32:63]
 653   // addr_vect[96:127]  = shadow1[96:127]
 654   m128 addr_vect        = SHUF(shadow0, shadow1, 1, 3, 1, 3);
 655   if (!is_write) {
 656     // set IsRead bit in addr_vect
 657     const m128 rw_mask1 = _mm_cvtsi64_si128(1<<15);
 658     const m128 rw_mask  = SHUF(rw_mask1, rw_mask1, 0, 0, 0, 0);
 659     addr_vect           = _mm_or_si128(addr_vect, rw_mask);
 660   }
 661   // addr0 == addr_vect?
 662   const m128 addr_res   = _mm_cmpeq_epi32(addr0, addr_vect);
 663   // epoch1[0:63]       = sync_epoch
 664   const m128 epoch1     = _mm_cvtsi64_si128(sync_epoch);
 665   // epoch[0:31]        = sync_epoch[0:31]
 666   // epoch[32:63]       = sync_epoch[0:31]
 667   // epoch[64:95]       = sync_epoch[0:31]
 668   // epoch[96:127]      = sync_epoch[0:31]
 669   const m128 epoch      = SHUF(epoch1, epoch1, 0, 0, 0, 0);
 670   // load low parts of shadow cell epochs into epoch_vect:
 671   // epoch_vect[0:31]   = shadow0[0:31]
 672   // epoch_vect[32:63]  = shadow0[64:95]
 673   // epoch_vect[64:95]  = shadow1[0:31]
 674   // epoch_vect[96:127] = shadow1[64:95]
 675   const m128 epoch_vect = SHUF(shadow0, shadow1, 0, 2, 0, 2);
 676   // epoch_vect >= sync_epoch?
 677   const m128 epoch_res  = _mm_cmpgt_epi32(epoch_vect, epoch);
 678   // addr_res & epoch_res
 679   const m128 res        = _mm_and_si128(addr_res, epoch_res);
 680   // mask[0] = res[7]
 681   // mask[1] = res[15]
 682   // ...
 683   // mask[15] = res[127]
 684   const int mask        = _mm_movemask_epi8(res);
 685   return mask != 0;
 686 }
 687 #endif
 688
 689 ALWAYS_INLINE
 690 bool ContainsSameAccess(u64 *s, u64 a, u64 sync_epoch, bool is_write) {
 691 #if defined(__SSE3__) && TSAN_SHADOW_COUNT == 4
 692   bool res = ContainsSameAccessFast(s, a, sync_epoch, is_write);
 693   DCHECK_EQ(res, ContainsSameAccessSlow(s, a, sync_epoch, is_write));
 694   return res;
 695 #else
 696   return ContainsSameAccessSlow(s, a, sync_epoch, is_write);
 697 #endif
 698 }
 699
 700 ALWAYS_INLINE USED
 701 void MemoryAccess(ThreadState *thr, uptr pc, uptr addr,
 702     int kAccessSizeLog, bool kAccessIsWrite, bool kIsAtomic) {
 703   u64 *shadow_mem = (u64*)MemToShadow(addr);
 704   DPrintf2("#%d: MemoryAccess: @%p %p size=%d"
 705       " is_write=%d shadow_mem=%p {%zx, %zx, %zx, %zx}\n",
 706       (int)thr->fast_state.tid(), (void*)pc, (void*)addr,
 707       (int)(1 << kAccessSizeLog), kAccessIsWrite, shadow_mem,
 708       (uptr)shadow_mem[0], (uptr)shadow_mem[1],
 709       (uptr)shadow_mem[2], (uptr)shadow_mem[3]);
 710 #if TSAN_DEBUG
 711   if (!IsAppMem(addr)) {
 712     Printf("Access to non app mem %zx\n", addr);
 713     DCHECK(IsAppMem(addr));
 714   }
 715   if (!IsShadowMem((uptr)shadow_mem)) {
 716     Printf("Bad shadow addr %p (%zx)\n", shadow_mem, addr);
 717     DCHECK(IsShadowMem((uptr)shadow_mem));
 718   }
 719 #endif
 720
 721   if (kCppMode && *shadow_mem == kShadowRodata) {
 722     // Access to .rodata section, no races here.
 723     // Measurements show that it can be 10-20% of all memory accesses.
 724     StatInc(thr, StatMop);
 725     StatInc(thr, kAccessIsWrite ? StatMopWrite : StatMopRead);
 726     StatInc(thr, (StatType)(StatMop1 + kAccessSizeLog));
 727     StatInc(thr, StatMopRodata);
 728     return;
 729   }
 730
 731   FastState fast_state = thr->fast_state;
 732   if (fast_state.GetIgnoreBit()) {
 733     StatInc(thr, StatMop);
 734     StatInc(thr, kAccessIsWrite ? StatMopWrite : StatMopRead);
 735     StatInc(thr, (StatType)(StatMop1 + kAccessSizeLog));
 736     StatInc(thr, StatMopIgnored);
 737     return;
 738   }
 739
 740   Shadow cur(fast_state);
 741   cur.SetAddr0AndSizeLog(addr & 7, kAccessSizeLog);
 742   cur.SetWrite(kAccessIsWrite);
 743   cur.SetAtomic(kIsAtomic);
 744
 745   if (LIKELY(ContainsSameAccess(shadow_mem, cur.raw(),
 746       thr->fast_synch_epoch, kAccessIsWrite))) {
 747     StatInc(thr, StatMop);
 748     StatInc(thr, kAccessIsWrite ? StatMopWrite : StatMopRead);
 749     StatInc(thr, (StatType)(StatMop1 + kAccessSizeLog));
 750     StatInc(thr, StatMopSame);
 751     return;
 752   }
 753
 754   if (kCollectHistory) {
 755     fast_state.IncrementEpoch();
 756     thr->fast_state = fast_state;
 757     TraceAddEvent(thr, fast_state, EventTypeMop, pc);
 758     cur.IncrementEpoch();
 759   }
 760
 761   MemoryAccessImpl1(thr, addr, kAccessSizeLog, kAccessIsWrite, kIsAtomic,
 762       shadow_mem, cur);
 763 }
 764
 765 // Called by MemoryAccessRange in tsan_rtl_thread.cc
 766 ALWAYS_INLINE USED
 767 void MemoryAccessImpl(ThreadState *thr, uptr addr,
 768     int kAccessSizeLog, bool kAccessIsWrite, bool kIsAtomic,
 769     u64 *shadow_mem, Shadow cur) {
 770   if (LIKELY(ContainsSameAccess(shadow_mem, cur.raw(),
 771       thr->fast_synch_epoch, kAccessIsWrite))) {
 772     StatInc(thr, StatMop);
 773     StatInc(thr, kAccessIsWrite ? StatMopWrite : StatMopRead);
 774     StatInc(thr, (StatType)(StatMop1 + kAccessSizeLog));
 775     StatInc(thr, StatMopSame);
 776     return;
 777   }
 778
 779   MemoryAccessImpl1(thr, addr, kAccessSizeLog, kAccessIsWrite, kIsAtomic,
 780       shadow_mem, cur);
 781 }
 782
 783 static void MemoryRangeSet(ThreadState *thr, uptr pc, uptr addr, uptr size,
 784                            u64 val) {
 785   (void)thr;
 786   (void)pc;
 787   if (size == 0)
 788     return;
 789   // FIXME: fix me.
 790   uptr offset = addr % kShadowCell;
 791   if (offset) {
 792     offset = kShadowCell - offset;
 793     if (size <= offset)
 794       return;
 795     addr += offset;
 796     size -= offset;
 797   }
 798   DCHECK_EQ(addr % 8, 0);
 799   // If a user passes some insane arguments (memset(0)),
 800   // let it just crash as usual.
 801   if (!IsAppMem(addr) || !IsAppMem(addr + size - 1))
 802     return;
 803   // Don't want to touch lots of shadow memory.
 804   // If a program maps 10MB stack, there is no need reset the whole range.
 805   size = (size + (kShadowCell - 1)) & ~(kShadowCell - 1);
 806   // UnmapOrDie/MmapFixedNoReserve does not work on Windows,
 807   // so we do it only for C/C++.
 808   if (kGoMode || size < common_flags()->clear_shadow_mmap_threshold) {
 809     u64 *p = (u64*)MemToShadow(addr);
 810     CHECK(IsShadowMem((uptr)p));
 811     CHECK(IsShadowMem((uptr)(p + size * kShadowCnt / kShadowCell - 1)));
 812     // FIXME: may overwrite a part outside the region
 813     for (uptr i = 0; i < size / kShadowCell * kShadowCnt;) {
 814       p[i++] = val;
 815       for (uptr j = 1; j < kShadowCnt; j++)
 816         p[i++] = 0;
 817     }
 818   } else {
 819     // The region is big, reset only beginning and end.
 820     const uptr kPageSize = 4096;
 821     u64 *begin = (u64*)MemToShadow(addr);
 822     u64 *end = begin + size / kShadowCell * kShadowCnt;
 823     u64 *p = begin;
 824     // Set at least first kPageSize/2 to page boundary.
 825     while ((p < begin + kPageSize / kShadowSize / 2) || ((uptr)p % kPageSize)) {
 826       *p++ = val;
 827       for (uptr j = 1; j < kShadowCnt; j++)
 828         *p++ = 0;
 829     }
 830     // Reset middle part.
 831     u64 *p1 = p;
 832     p = RoundDown(end, kPageSize);
 833     UnmapOrDie((void*)p1, (uptr)p - (uptr)p1);
 834     MmapFixedNoReserve((uptr)p1, (uptr)p - (uptr)p1);
 835     // Set the ending.
 836     while (p < end) {
 837       *p++ = val;
 838       for (uptr j = 1; j < kShadowCnt; j++)
 839         *p++ = 0;
 840     }
 841   }
 842 }
 843
 844 void MemoryResetRange(ThreadState *thr, uptr pc, uptr addr, uptr size) {
 845   MemoryRangeSet(thr, pc, addr, size, 0);
 846 }
 847
 848 void MemoryRangeFreed(ThreadState *thr, uptr pc, uptr addr, uptr size) {
 849   // Processing more than 1k (4k of shadow) is expensive,
 850   // can cause excessive memory consumption (user does not necessary touch
 851   // the whole range) and most likely unnecessary.
 852   if (size > 1024)
 853     size = 1024;
 854   CHECK_EQ(thr->is_freeing, false);
 855   thr->is_freeing = true;
 856   MemoryAccessRange(thr, pc, addr, size, true);
 857   thr->is_freeing = false;
 858   if (kCollectHistory) {
 859     thr->fast_state.IncrementEpoch();
 860     TraceAddEvent(thr, thr->fast_state, EventTypeMop, pc);
 861   }
 862   Shadow s(thr->fast_state);
 863   s.ClearIgnoreBit();
 864   s.MarkAsFreed();
 865   s.SetWrite(true);
 866   s.SetAddr0AndSizeLog(0, 3);
 867   MemoryRangeSet(thr, pc, addr, size, s.raw());
 868 }
 869
 870 void MemoryRangeImitateWrite(ThreadState *thr, uptr pc, uptr addr, uptr size) {
 871   if (kCollectHistory) {
 872     thr->fast_state.IncrementEpoch();
 873     TraceAddEvent(thr, thr->fast_state, EventTypeMop, pc);
 874   }
 875   Shadow s(thr->fast_state);
 876   s.ClearIgnoreBit();
 877   s.SetWrite(true);
 878   s.SetAddr0AndSizeLog(0, 3);
 879   MemoryRangeSet(thr, pc, addr, size, s.raw());
 880 }
 881
 882 ALWAYS_INLINE USED
 883 void FuncEntry(ThreadState *thr, uptr pc) {
 884   StatInc(thr, StatFuncEnter);
 885   DPrintf2("#%d: FuncEntry %p\n", (int)thr->fast_state.tid(), (void*)pc);
 886   if (kCollectHistory) {
 887     thr->fast_state.IncrementEpoch();
 888     TraceAddEvent(thr, thr->fast_state, EventTypeFuncEnter, pc);
 889   }
 890
 891   // Shadow stack maintenance can be replaced with
 892   // stack unwinding during trace switch (which presumably must be faster).
 893   DCHECK_GE(thr->shadow_stack_pos, thr->shadow_stack);
 894 #ifndef TSAN_GO
 895   DCHECK_LT(thr->shadow_stack_pos, thr->shadow_stack_end);
 896 #else
 897   if (thr->shadow_stack_pos == thr->shadow_stack_end)
 898     GrowShadowStack(thr);
 899 #endif
 900   thr->shadow_stack_pos[0] = pc;
 901   thr->shadow_stack_pos++;
 902 }
 903
 904 ALWAYS_INLINE USED
 905 void FuncExit(ThreadState *thr) {
 906   StatInc(thr, StatFuncExit);
 907   DPrintf2("#%d: FuncExit\n", (int)thr->fast_state.tid());
 908   if (kCollectHistory) {
 909     thr->fast_state.IncrementEpoch();
 910     TraceAddEvent(thr, thr->fast_state, EventTypeFuncExit, 0);
 911   }
 912
 913   DCHECK_GT(thr->shadow_stack_pos, thr->shadow_stack);
 914 #ifndef TSAN_GO
 915   DCHECK_LT(thr->shadow_stack_pos, thr->shadow_stack_end);
 916 #endif
 917   thr->shadow_stack_pos--;
 918 }
 919
 920 void ThreadIgnoreBegin(ThreadState *thr, uptr pc) {
 921   DPrintf("#%d: ThreadIgnoreBegin\n", thr->tid);
 922   thr->ignore_reads_and_writes++;
 923   CHECK_GT(thr->ignore_reads_and_writes, 0);
 924   thr->fast_state.SetIgnoreBit();
 925 #ifndef TSAN_GO
 926   if (!ctx->after_multithreaded_fork)
 927     thr->mop_ignore_set.Add(CurrentStackId(thr, pc));
 928 #endif
 929 }
 930
 931 void ThreadIgnoreEnd(ThreadState *thr, uptr pc) {
 932   DPrintf("#%d: ThreadIgnoreEnd\n", thr->tid);
 933   thr->ignore_reads_and_writes--;
 934   CHECK_GE(thr->ignore_reads_and_writes, 0);
 935   if (thr->ignore_reads_and_writes == 0) {
 936     thr->fast_state.ClearIgnoreBit();
 937 #ifndef TSAN_GO
 938     thr->mop_ignore_set.Reset();
 939 #endif
 940   }
 941 }
 942
 943 void ThreadIgnoreSyncBegin(ThreadState *thr, uptr pc) {
 944   DPrintf("#%d: ThreadIgnoreSyncBegin\n", thr->tid);
 945   thr->ignore_sync++;
 946   CHECK_GT(thr->ignore_sync, 0);
 947 #ifndef TSAN_GO
 948   if (!ctx->after_multithreaded_fork)
 949     thr->sync_ignore_set.Add(CurrentStackId(thr, pc));
 950 #endif
 951 }
 952
 953 void ThreadIgnoreSyncEnd(ThreadState *thr, uptr pc) {
 954   DPrintf("#%d: ThreadIgnoreSyncEnd\n", thr->tid);
 955   thr->ignore_sync--;
 956   CHECK_GE(thr->ignore_sync, 0);
 957 #ifndef TSAN_GO
 958   if (thr->ignore_sync == 0)
 959     thr->sync_ignore_set.Reset();
 960 #endif
 961 }
 962
 963 bool MD5Hash::operator==(const MD5Hash &other) const {
 964   return hash[0] == other.hash[0] && hash[1] == other.hash[1];
 965 }
 966
 967 #if TSAN_DEBUG
 968 void build_consistency_debug() {}
 969 #else
 970 void build_consistency_release() {}
 971 #endif
 972
 973 #if TSAN_COLLECT_STATS
 974 void build_consistency_stats() {}
 975 #else
 976 void build_consistency_nostats() {}
 977 #endif
 978
 979 #if TSAN_SHADOW_COUNT == 1
 980 void build_consistency_shadow1() {}
 981 #elif TSAN_SHADOW_COUNT == 2
 982 void build_consistency_shadow2() {}
 983 #elif TSAN_SHADOW_COUNT == 4
 984 void build_consistency_shadow4() {}
 985 #else
 986 void build_consistency_shadow8() {}
 987 #endif
 988
 989 }  // namespace __tsan
 990
 991 #ifndef TSAN_GO
 992 // Must be included in this file to make sure everything is inlined.
 993 #include "tsan_interface_inl.h"
 994 #endif