tsan: prevent pathological slowdown for spurious races

[dvyukov]

Summary

Prevent the following 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.

[dvyukov]

compiler-rt/lib/tsan/rtl/tsan_rtl.h

338

Thinking if we should do an array just to be sure... I would assume the size of the array will be 0/1 in most cases, rarely 2.

340

I am not super happy about this fix, but I also don't see any other reasonable way to fix this.
I did not find any reasonable way to synchronize memory accesses with DoReset,
and I don't see an easy way to radically speed up RestoreStack. Plus I am now leaning towards
stabilizing the current algorithms rather than radically rework everything again.

[melver]

compiler-rt/lib/tsan/rtl/tsan_rtl.h

338

Just one looks fine until there's evidence it needs more than 1.

340

Is the biggest problem not wanting to do more work on memory accesses?

Which, I assume means that on an access writing the shadow it cannot revalidate at the end (a'la transaction and retry).

[dvyukov]

compiler-rt/lib/tsan/rtl/tsan_rtl.h

340

Yes.

The memory access part also needs to synchronize with another thread, so it either needs to use an atomic RMW/expensive fence, or use some kind of asymmetric synchronization. I've considered doing asymmetric synchronization, but that's still instructions on fast path and portability issues.
I've also tried to use signals to synchronize with fast paths. It was nightmare to develop and debug.

compiler-rt/lib/tsan/rtl/tsan_rtl.h

#endif
   int nreported;
   atomic_uint64_t last_symbolize_time_ns;
 
   void *background_thread;
   atomic_uint32_t stop_background_thread;
 
   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<RacyStacks> racy_stacks;
   // Number of fired suppressions may be large enough.
   Mutex fired_suppressions_mtx;
   InternalMmapVector<FiredSuppression> fired_suppressions;
   DDetector *dd;
 
   Flags flags;

compiler-rt/lib/tsan/rtl/tsan_rtl.cpp

static void DoResetImpl(uptr epoch) {
   DPrintf("Resetting shadow...\n");
   if (!MmapFixedSuperNoReserve(ShadowBeg(), ShadowEnd() - ShadowBeg(),
                                "shadow")) {
     Printf("failed to reset shadow memory\n");
     Die();
   }
   DPrintf("Resetting meta shadow...\n");
   ctx->metamap.ResetClocks();
+  StoreShadow(&ctx->last_spurious_race, Shadow::kEmpty);
   ctx->resetting = false;
 }
 
 // Clang does not understand locking all slots in the loop:
 // error: expecting mutex 'slot.mtx' to be held at start of each loop
 void DoReset(ThreadState* thr, uptr epoch) SANITIZER_NO_THREAD_SAFETY_ANALYSIS {
   for (auto& slot : ctx->slots) {
     slot.mtx.Lock();

compiler-rt/lib/tsan/rtl/tsan_rtl_access.cpp

void TraceTime(ThreadState* thr) {
   ev.is_func = 0;
   ev.type = EventType::kTime;
   ev.sid = static_cast<u64>(fast_state.sid());
   ev.epoch = static_cast<u64>(fast_state.epoch());
   ev._ = 0;
   TraceEvent(thr, ev);
 }
 
-ALWAYS_INLINE RawShadow LoadShadow(RawShadow* p) {
-  return static_cast<RawShadow>(
-      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<u32>(s), memory_order_relaxed);
-}
-
 NOINLINE void DoReportRace(ThreadState* thr, RawShadow* shadow_mem, Shadow cur,
                            Shadow old,
                            AccessType typ) SANITIZER_NO_THREAD_SAFETY_ANALYSIS {
   // For the free shadow markers the first element (that contains kFreeSid)
   // triggers the race, but the second element contains info about the freeing
   // thread, take it.
   if (old.sid() == kFreeSid)
     old = Shadow(LoadShadow(&shadow_mem[1]));

compiler-rt/lib/tsan/rtl/tsan_rtl_report.cpp

if (addr == s->pc_or_addr) {
       if (s->supp)
         atomic_fetch_add(&s->supp->hit_count, 1, memory_order_relaxed);
       return true;
     }
   }
   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();
 
   // Symbolizer makes lots of intercepted calls. If we try to process them,
   // at best it will cause deadlocks on internal mutexes.
   ScopedIgnoreInterceptors ignore;
 
   uptr addr = ShadowToMem(shadow_mem);
   DPrintf("#%d: ReportRace %p\n", thr->tid, (void *)addr);
   if (!ShouldReport(thr, ReportTypeRace))
     return;
   uptr addr_off0, size0;
   cur.GetAccess(&addr_off0, &size0, nullptr);
   uptr addr_off1, size1, typ1;
   old.GetAccess(&addr_off1, &size1, &typ1);
   if (!flags()->report_atomic_races &&
       ((typ0 & kAccessAtomic) || (typ1 & kAccessAtomic)) &&
       !(typ0 & kAccessFree) && !(typ1 & kAccessFree))
     return;
+  if (SpuriousRace(old))
+    return;
 
   const uptr kMop = 2;
   Shadow s[kMop] = {cur, old};
   uptr addr0 = addr + addr_off0;
   uptr addr1 = addr + addr_off1;
   uptr end0 = addr0 + size0;
   uptr end1 = addr1 + size1;
   uptr addr_min = min(addr0, addr1);
void ReportRace(ThreadState *thr, RawShadow *shadow_mem, Shadow cur, Shadow old,
   DynamicMutexSet mset1;
   MutexSet *mset[kMop] = {&thr->mset, mset1};
 
   // We need to lock the slot during RestoreStack because it protects
   // the slot journal.
   Lock slot_lock(&ctx->slots[static_cast<uptr>(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;
 
   if (HandleRacyStacks(thr, traces))
     return;
 
   // If any of the accesses has a tag, treat this as an "external" race.

compiler-rt/lib/tsan/rtl/tsan_shadow.h

  public:
   // .rodata shadow marker, see MapRodata and ContainsSameAccessFast.
   static constexpr RawShadow kRodata =
       static_cast<RawShadow>(1 << kIsReadShift);
 };
 
 static_assert(sizeof(Shadow) == kShadowSize, "bad Shadow size");
 
+ALWAYS_INLINE RawShadow LoadShadow(RawShadow *p) {
+  return static_cast<RawShadow>(
+      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<u32>(s),
+               memory_order_relaxed);
+}
+
 }  // namespace __tsan
 
 #endif