diff --git a/compiler-rt/lib/tsan/rtl/tsan_rtl.h b/compiler-rt/lib/tsan/rtl/tsan_rtl.h --- a/compiler-rt/lib/tsan/rtl/tsan_rtl.h +++ b/compiler-rt/lib/tsan/rtl/tsan_rtl.h @@ -314,6 +314,41 @@ ThreadRegistry thread_registry; + // This is used to prevent a very unlikely but very pathological behavior. + // Since memory access handling is not synchronized with DoReset, + // a thread running concurrently with DoReset can leave a bogus shadow value + // that will be later falsely detected as a race. For such false races + // RestoreStack will return false and we will not report it. + // However, consider that a thread leaves a whole lot of such bogus values + // and these values are later read by a whole lot of threads. + // This will cause massive amounts of ReportRace calls and lots of + // serialization. In very pathological cases the resulting slowdown + // can be >100x. This is very unlikely, but it was presumably observed + // in practice: https://github.com/google/sanitizers/issues/1552 + // If this happens, previous access sid+epoch will be the same for all of + // these false races b/c if the thread will try to increment epoch, it will + // notice that DoReset has happened and will stop producing bogus shadow + // values. So, last_spurious_race is used to remember the last sid+epoch + // for which RestoreStack returned false. Then it is used to filter out + // races with the same sid+epoch very early and quickly. + // It is of course possible that multiple threads left multiple bogus shadow + // values and all of them are read by lots of threads at the same time. + // In such case last_spurious_race will only be able to deduplicate a few + // races from one thread, then few from another and so on. An alternative + // would be to hold an array of such sid+epoch, but we consider such scenario + // as even less likely. + // Note: this can lead to some rare false negatives as well: + // 1. When a legit access with the same sid+epoch participates in a race + // as the "previous" memory access, it will be wrongly filtered out. + // 2. When RestoreStack returns false for a legit memory access because it + // was already evicted from the thread trace, we will still remember it in + // last_spurious_race. Then if there is another racing memory access from + // the same thread that happened in the same epoch, but was stored in the + // next thread trace part (which is still preserved in the thread trace), + // we will also wrongly filter it out while RestoreStack would actually + // succeed for that second memory access. + RawShadow last_spurious_race; + Mutex racy_mtx; Vector racy_stacks; Vector racy_addresses; diff --git a/compiler-rt/lib/tsan/rtl/tsan_rtl.cpp b/compiler-rt/lib/tsan/rtl/tsan_rtl.cpp --- a/compiler-rt/lib/tsan/rtl/tsan_rtl.cpp +++ b/compiler-rt/lib/tsan/rtl/tsan_rtl.cpp @@ -204,6 +204,7 @@ } DPrintf("Resetting meta shadow...\n"); ctx->metamap.ResetClocks(); + StoreShadow(&ctx->last_spurious_race, Shadow::kEmpty); ctx->resetting = false; } diff --git a/compiler-rt/lib/tsan/rtl/tsan_rtl_access.cpp b/compiler-rt/lib/tsan/rtl/tsan_rtl_access.cpp --- a/compiler-rt/lib/tsan/rtl/tsan_rtl_access.cpp +++ b/compiler-rt/lib/tsan/rtl/tsan_rtl_access.cpp @@ -145,15 +145,6 @@ TraceEvent(thr, ev); } -ALWAYS_INLINE RawShadow LoadShadow(RawShadow* p) { - return static_cast( - atomic_load((atomic_uint32_t*)p, memory_order_relaxed)); -} - -ALWAYS_INLINE void StoreShadow(RawShadow* sp, RawShadow s) { - atomic_store((atomic_uint32_t*)sp, static_cast(s), memory_order_relaxed); -} - NOINLINE void DoReportRace(ThreadState* thr, RawShadow* shadow_mem, Shadow cur, Shadow old, AccessType typ) SANITIZER_NO_THREAD_SAFETY_ANALYSIS { diff --git a/compiler-rt/lib/tsan/rtl/tsan_rtl_report.cpp b/compiler-rt/lib/tsan/rtl/tsan_rtl_report.cpp --- a/compiler-rt/lib/tsan/rtl/tsan_rtl_report.cpp +++ b/compiler-rt/lib/tsan/rtl/tsan_rtl_report.cpp @@ -730,6 +730,11 @@ return false; } +static bool SpuriousRace(Shadow old) { + Shadow last(LoadShadow(&ctx->last_spurious_race)); + return last.sid() == old.sid() && last.epoch() == old.epoch(); +} + void ReportRace(ThreadState *thr, RawShadow *shadow_mem, Shadow cur, Shadow old, AccessType typ0) { CheckedMutex::CheckNoLocks(); @@ -750,6 +755,8 @@ ((typ0 & kAccessAtomic) || (typ1 & kAccessAtomic)) && !(typ0 & kAccessFree) && !(typ1 & kAccessFree)) return; + if (SpuriousRace(old)) + return; const uptr kMop = 2; Shadow s[kMop] = {cur, old}; @@ -791,9 +798,13 @@ Lock slot_lock(&ctx->slots[static_cast(s[1].sid())].mtx); ThreadRegistryLock l0(&ctx->thread_registry); Lock slots_lock(&ctx->slot_mtx); + if (SpuriousRace(old)) + return; if (!RestoreStack(EventType::kAccessExt, s[1].sid(), s[1].epoch(), addr1, - size1, typ1, &tids[1], &traces[1], mset[1], &tags[1])) + size1, typ1, &tids[1], &traces[1], mset[1], &tags[1])) { + StoreShadow(&ctx->last_spurious_race, old.raw()); return; + } if (IsFiredSuppression(ctx, rep_typ, traces[1])) return; diff --git a/compiler-rt/lib/tsan/rtl/tsan_shadow.h b/compiler-rt/lib/tsan/rtl/tsan_shadow.h --- a/compiler-rt/lib/tsan/rtl/tsan_shadow.h +++ b/compiler-rt/lib/tsan/rtl/tsan_shadow.h @@ -178,6 +178,16 @@ static_assert(sizeof(Shadow) == kShadowSize, "bad Shadow size"); +ALWAYS_INLINE RawShadow LoadShadow(RawShadow *p) { + return static_cast( + atomic_load((atomic_uint32_t *)p, memory_order_relaxed)); +} + +ALWAYS_INLINE void StoreShadow(RawShadow *sp, RawShadow s) { + atomic_store((atomic_uint32_t *)sp, static_cast(s), + memory_order_relaxed); +} + } // namespace __tsan #endif