[TSan] Optimize handling of racy address

[protze.joachim]

Summary

This patch splits the handling of racy address and racy stack into separate functions. If a race was already reported for the address, we can avoid the cost for collecting the involved stacks.

This patch also removes the race condition in storing the racy address / racy stack. This race allows all threads to report the race. Because all threads get the read lock first, it is quite probable that they all finish the lookup before one thread gets the chance to aquire the write lock.

For certain data race patterns in OpenMP programs, this patch significantly reduces the execution time. As an example the execution times for below code:
master (report_bugs=1): real 0m24s
master (report_bugs=0): real 0m0.2s
patch (report_bugs=1): real 0m0.5s
patch (report_bugs=0): real 0m0.2s

// RUN: clang -fopenmp -fsanitize=thread %s -o %t; env TSAN_OPTIONS="ignore_noninstrumented_modules=1" %t
#include <stdio.h>
int main(void)
{
  long sum=0;
  #pragma omp parallel num_threads(4) //reduction(+:sum)
  for(int i=0; i<1000000; i++)
  {
    sum++;
  } 
  printf("Sum: %ld\n",sum);
}

[dvyukov]

Hi Joachim,

I think this is useful.
As far a I see this changes behavior a bit. Previously if we match existing racy addrs, we still memorize racy stacks. So reports can be suppressed transitively: second report matches addr, but different stacks; then third report matches stacks with the second one, but a new address; and so on. Now we will match address and bail out.
But I think it's OK. I don't remember now why that transitive behavior was important, and if it was at all or not.

Now looking at the code I am confused about AddRacyStacks. Shouldn't we have both address and stacks already memorized at that point? Maybe we should remove it while we are here.

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

444

Please add a helper function for this check b/c it's now duplicated twice.
The same for the address check.

[protze.joachim]

I moved the loops into functions.
I think for the previous controlflow, AddRacyStacks was necessary because of the early return false in line 475. I removed it, as the functions now add the entry directly to the vector.

[protze.joachim]

I agree, that the patch changes the transitive suppression of reports. Unfortunately, this would bring back the overhead of reconstructing the remote stack trace.

As a follow-up patch I was thinking about adding a suppress_equal_location flag.
I would only compare the local stack trace with previously reported stack traces in racy_stacks.
Initially I was thinking about suppress_equal_pc, but especially for wrapper functions, the top pc is function pointer of the wrapper.

Also, I plan to add a suppress_max_stack_depth=n flag. The HandleRacyStacks function will only compare the top n frames in this case.
For race in recursive algorithms, this will allow to remove duplicates with different recursion depth. (For OpenMP, this specifically helps for tasking programs)

[protze.joachim]

I added a missing a return statement

[protze.joachim]

After a pull from master, all tests were successful with this patch.

[dvyukov]

Looks good to me.
You have access, right? If so, please land it.

[dvyukov]

In D83625#2150120, @protze.joachim wrote:

I agree, that the patch changes the transitive suppression of reports. Unfortunately, this would bring back the overhead of reconstructing the remote stack trace.

As a follow-up patch I was thinking about adding a suppress_equal_location flag.
I would only compare the local stack trace with previously reported stack traces in racy_stacks.
Initially I was thinking about suppress_equal_pc, but especially for wrapper functions, the top pc is function pointer of the wrapper.

Right, it can do more harm.

Also, I plan to add a suppress_max_stack_depth=n flag. The HandleRacyStacks function will only compare the top n frames in this case.
For race in recursive algorithms, this will allow to remove duplicates with different recursion depth. (For OpenMP, this specifically helps for tasking programs)

What will be the default? What is the useful value for OpenMP programs?

[protze.joachim]

In D83625#2152829, @dvyukov wrote:

In D83625#2150120, @protze.joachim wrote:

I agree, that the patch changes the transitive suppression of reports. Unfortunately, this would bring back the overhead of reconstructing the remote stack trace.

As a follow-up patch I was thinking about adding a suppress_equal_location flag.
I would only compare the local stack trace with previously reported stack traces in racy_stacks.
Initially I was thinking about suppress_equal_pc, but especially for wrapper functions, the top pc is function pointer of the wrapper.

Right, it can do more harm.

What do you think about comparing the local stack against the two hashes in racy_stacks?
I would propably have this defaulting to false unless we find it convenient for the typical usecase.

Also, I plan to add a suppress_max_stack_depth=n flag. The HandleRacyStacks function will only compare the top n frames in this case.
For race in recursive algorithms, this will allow to remove duplicates with different recursion depth. (For OpenMP, this specifically helps for tasking programs)

What will be the default? What is the useful value for OpenMP programs?

My suggestion for the default is infinite / MAX_INT, i.e. not change existing behavior.

Is there a runtime interface to adjust the flags? This would allow libarcher to tweak this flag during initialization, and I could also choose different defaults for other flags.
I always suggest ignore_noninstrumented_modules=1 for OpenMP and Fortran codes to suppress false reports from libomp and libgfortran.

[dvyukov]

In D83625#2153333, @protze.joachim wrote:

Right, it can do more harm.

What do you think about comparing the local stack against the two hashes in racy_stacks?
I would propably have this defaulting to false unless we find it convenient for the typical usecase.

I would avoid doing this right now because the use case for this is moot, and this is additional code, code reviews and slowdown.

Also, I plan to add a suppress_max_stack_depth=n flag. The HandleRacyStacks function will only compare the top n frames in this case.
For race in recursive algorithms, this will allow to remove duplicates with different recursion depth. (For OpenMP, this specifically helps for tasking programs)

What will be the default? What is the useful value for OpenMP programs?

My suggestion for the default is infinite / MAX_INT, i.e. not change existing behavior.

And what do you plan to use/suggest for openmp? I am asking because if it's, say, 50, then we could probably simply make it the default and no flag at all. But if it's 5, then probably we can't.

Is there a runtime interface to adjust the flags? This would allow libarcher to tweak this flag during initialization, and I could also choose different defaults for other flags.
I always suggest ignore_noninstrumented_modules=1 for OpenMP and Fortran codes to suppress false reports from libomp and libgfortran.

No, I don't think there such interface.
There is something like __default_options global var. It's supposed for end program (b/c there can be only 1). It also needs to override the weak definition we have in the runtime.
You may try. If we are super lucky then it may work and end program may even be able to override it again. But it all will depend on how the openmp library is linked.

[protze.joachim]

I reverted the commit, because all buildbots failed for these tests:

TEST 'ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.RaceWithOffset' FAILED
TEST 'ThreadSanitizer-Unit :: rtl/./TsanRtlTest-x86_64-Test/ThreadSanitizer.RaceWithOffset2' FAILED

As I understand the issue, the two tests trigger data race on different memory locations, but only the first is reported and all following are suppressed for the same stack.
I updated the tests, so that the PC of the "memory access" is in the stacktrace.
I have no idea why this did not fail before.

[protze.joachim]

I think, the better solution is to use the _pc version of the access functions to use the "real" access location.

[dvyukov]

No idea why it broke now. THe change to tsan_test_util_posix.cpp looks fine to me.

[hans]

Joachim suggested cherry-picking this (https://reviews.llvm.org/rG7358a1104a02) to the 11.x branch. Dmitry, what do you think?

[dvyukov]

In D83625#2161663, @hans wrote:

Joachim suggested cherry-picking this (https://reviews.llvm.org/rG7358a1104a02) to the 11.x branch. Dmitry, what do you think?

I dunno, never dealt with clang backports (continuous releases rulez).

I personally don't mind. We have some tests, so it should not break things completely. But I don't know what risks are involved.

[hans]

I personally don't mind. We have some tests, so it should not break things completely. But I don't know what risks are involved.

We're early in the process, so I think the risk is low. Joachim, please let me know if there are any problems or follow-ups to this patch.

Pushed to 11.x as 96313d2de45ace49d40606dda71f03396f13ddef.

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

void RestoreStack(int tid, const u64 epoch, VarSizeStackTrace *stk,
   }
   if (pos == 0 && stack[0] == 0)
     return;
   pos++;
   stk->Init(&stack[0], pos);
   ExtractTagFromStack(stk, tag);
 }
 
-static bool HandleRacyStacks(ThreadState *thr, VarSizeStackTrace traces[2],
-                             uptr addr_min, uptr addr_max) {
-  bool equal_stack = false;
-  RacyStacks hash;
-  bool equal_address = false;
-  RacyAddress ra0 = {addr_min, addr_max};
-  {
-    ReadLock lock(&ctx->racy_mtx);
-    if (flags()->suppress_equal_stacks) {
-      hash.hash[0] = md5_hash(traces[0].trace, traces[0].size * sizeof(uptr));
-      hash.hash[1] = md5_hash(traces[1].trace, traces[1].size * sizeof(uptr));
-      for (uptr i = 0; i < ctx->racy_stacks.Size(); i++) {
-        if (hash == ctx->racy_stacks[i]) {
-          VPrintf(2,
-              "ThreadSanitizer: suppressing report as doubled (stack)\n");
-          equal_stack = true;
-          break;
-        }
-      }
-    }
-    if (flags()->suppress_equal_addresses) {
-      for (uptr i = 0; i < ctx->racy_addresses.Size(); i++) {
-        RacyAddress ra2 = ctx->racy_addresses[i];
-        uptr maxbeg = max(ra0.addr_min, ra2.addr_min);
-        uptr minend = min(ra0.addr_max, ra2.addr_max);
-        if (maxbeg < minend) {
-          VPrintf(2, "ThreadSanitizer: suppressing report as doubled (addr)\n");
-          equal_address = true;
-          break;
-        }
-      }
+static bool FindRacyStacks(const RacyStacks &hash) {
+      VPrintf(2, "ThreadSanitizer: suppressing report as doubled (stack)\n");
+      return true;
+  return false;
+
+static bool HandleRacyStacks(ThreadState *thr, VarSizeStackTrace traces[2]) {
+  if (!flags()->suppress_equal_stacks)
+    return false;
+  RacyStacks hash;
+  hash.hash[0] = md5_hash(traces[0].trace, traces[0].size * sizeof(uptr));
+  hash.hash[1] = md5_hash(traces[1].trace, traces[1].size * sizeof(uptr));
+  {
+    ReadLock lock(&ctx->racy_mtx);
+    if (FindRacyStacks(hash))
+      return true;
+  }
+  Lock lock(&ctx->racy_mtx);
+  if (FindRacyStacks(hash))
+    return true;
+  ctx->racy_stacks.PushBack(hash);
+  return false;
+}
+
+static bool FindRacyAddress(const RacyAddress &ra0) {
+      return true;
     }
   }
-  if (!equal_stack && !equal_address)
-    return false;
-  if (!equal_stack) {
-    Lock lock(&ctx->racy_mtx);
-    ctx->racy_stacks.PushBack(hash);
-  }
-  if (!equal_address) {
-    Lock lock(&ctx->racy_mtx);
-    ctx->racy_addresses.PushBack(ra0);
-  }
+
+static bool HandleRacyAddress(ThreadState *thr, uptr addr_min, uptr addr_max) {
+  if (!flags()->suppress_equal_addresses)
+    return false;
+  RacyAddress ra0 = {addr_min, addr_max};
+  {
+    ReadLock lock(&ctx->racy_mtx);
+    if (FindRacyAddress(ra0))
       return true;
   }
-
-static void AddRacyStacks(ThreadState *thr, VarSizeStackTrace traces[2],
-                          uptr addr_min, uptr addr_max) {
   Lock lock(&ctx->racy_mtx);
-  if (flags()->suppress_equal_stacks) {
-    RacyStacks hash;
-    hash.hash[0] = md5_hash(traces[0].trace, traces[0].size * sizeof(uptr));
-    hash.hash[1] = md5_hash(traces[1].trace, traces[1].size * sizeof(uptr));
-    ctx->racy_stacks.PushBack(hash);
-  }
-  if (flags()->suppress_equal_addresses) {
-    RacyAddress ra0 = {addr_min, addr_max};
-    ctx->racy_addresses.PushBack(ra0);
-  }
+  if (FindRacyAddress(ra0))
+    return true;
+  return false;
 }
 
 bool OutputReport(ThreadState *thr, const ScopedReport &srep) {
   if (!flags()->report_bugs || thr->suppress_reports)
     return false;
   atomic_store_relaxed(&ctx->last_symbolize_time_ns, NanoTime());
   const ReportDesc *rep = srep.GetReport();
   CHECK_EQ(thr->current_report, nullptr);
uptr addr_max = 0;
     uptr a1 = addr + Shadow(thr->racy_state[1]).addr0();
     uptr e0 = a0 + Shadow(thr->racy_state[0]).size();
     uptr e1 = a1 + Shadow(thr->racy_state[1]).size();
     addr_min = min(a0, a1);
     addr_max = max(e0, e1);
     if (IsExpectedReport(addr_min, addr_max - addr_min))
       return;
   }
+  if (HandleRacyAddress(thr, addr_min, addr_max))
+    return;
 
   ReportType typ = ReportTypeRace;
   if (thr->is_vptr_access && freed)
     typ = ReportTypeVptrUseAfterFree;
   else if (thr->is_vptr_access)
     typ = ReportTypeVptrRace;
   else if (freed)
     typ = ReportTypeUseAfterFree;
void ReportRace(ThreadState *thr) {
   mset_buffer.Resize(sizeof(MutexSet) / sizeof(u64) + 1);
   MutexSet *mset2 = new(&mset_buffer[0]) MutexSet();
 
   Shadow s2(thr->racy_state[1]);
   RestoreStack(s2.tid(), s2.epoch(), &traces[1], mset2, &tags[1]);
   if (IsFiredSuppression(ctx, typ, traces[1]))
     return;
 
-  if (HandleRacyStacks(thr, traces, addr_min, addr_max))
+  if (HandleRacyStacks(thr, traces))
     return;
 
   // If any of the accesses has a tag, treat this as an "external" race.
   uptr tag = kExternalTagNone;
   for (uptr i = 0; i < kMop; i++) {
     if (tags[i] != kExternalTagNone) {
       typ = ReportTypeExternalRace;
       tag = tags[i];
#if !SANITIZER_GO
     if (s.epoch() <= thr->last_sleep_clock.get(s.tid()))
       rep.AddSleep(thr->last_sleep_stack_id);
   }
 #endif
 
   if (!OutputReport(thr, rep))
     return;
 
-  AddRacyStacks(thr, traces, addr_min, addr_max);
 }
 
 void PrintCurrentStack(ThreadState *thr, uptr pc) {
   VarSizeStackTrace trace;
   ObtainCurrentStack(thr, pc, &trace);
   PrintStack(SymbolizeStack(trace));
 }
 

compiler-rt/lib/tsan/tests/rtl/tsan_test_util_posix.cpp

 #include <assert.h>
 #include <pthread.h>
 #include <stdio.h>
 #include <stdint.h>
 #include <string.h>
 #include <unistd.h>
 #include <errno.h>
 
+#define CALLERPC (__builtin_return_address(0))
+
 using namespace __tsan;
 
 static __thread bool expect_report;
 static __thread bool expect_report_reported;
 static __thread ReportType expect_report_type;
 
 static void *BeforeInitThread(void *param) {
   (void)param;

 void ScopedThread::Impl::HandleEvent(Event *ev) {
   CHECK_EQ(expect_report, false);
   expect_report = ev->expect_report;
   expect_report_reported = false;
   expect_report_type = ev->report_type;
   switch (ev->type) {
   case Event::READ:
   case Event::WRITE: {
-    void (*tsan_mop)(void *addr) = 0;
+    void (*tsan_mop)(void *addr, void* pc) = 0;
     if (ev->type == Event::READ) {
       switch (ev->arg /*size*/) {
-        case 1: tsan_mop = __tsan_read1; break;
-        case 2: tsan_mop = __tsan_read2; break;
-        case 4: tsan_mop = __tsan_read4; break;
-        case 8: tsan_mop = __tsan_read8; break;
-        case 16: tsan_mop = __tsan_read16; break;
+        case 1: tsan_mop = __tsan_read1_pc; break;
+        case 2: tsan_mop = __tsan_read2_pc; break;
+        case 4: tsan_mop = __tsan_read4_pc; break;
+        case 8: tsan_mop = __tsan_read8_pc; break;
+        case 16: tsan_mop = __tsan_read16_pc; break;
       }
     } else {
       switch (ev->arg /*size*/) {
-        case 1: tsan_mop = __tsan_write1; break;
-        case 2: tsan_mop = __tsan_write2; break;
-        case 4: tsan_mop = __tsan_write4; break;
-        case 8: tsan_mop = __tsan_write8; break;
-        case 16: tsan_mop = __tsan_write16; break;
+        case 1: tsan_mop = __tsan_write1_pc; break;
+        case 2: tsan_mop = __tsan_write2_pc; break;
+        case 4: tsan_mop = __tsan_write4_pc; break;
+        case 8: tsan_mop = __tsan_write8_pc; break;
+        case 16: tsan_mop = __tsan_write16_pc; break;
       }
     }
     CHECK_NE(tsan_mop, 0);
 #if defined(__FreeBSD__) || defined(__APPLE__) || defined(__NetBSD__)
     const int ErrCode = ESOCKTNOSUPPORT;
 #else
     const int ErrCode = ECHRNG;
 #endif
     errno = ErrCode;
-    tsan_mop(ev->ptr);
+    tsan_mop(ev->ptr, (void*)ev->arg2);
     CHECK_EQ(ErrCode, errno);  // In no case must errno be changed.
     break;
   }
   case Event::VPTR_UPDATE:
     __tsan_vptr_update((void**)ev->ptr, (void*)ev->arg);
     break;
   case Event::CALL:
     __tsan_func_entry((void*)((uptr)ev->ptr));
#endif
   if (expect_report && !expect_report_reported) {
     printf("Missed expected report of type %d\n", (int)ev->report_type);
     EXPECT_TRUE(false) << "Missed expected race";
   }
   expect_report = false;
 }
 
 void *ScopedThread::Impl::ScopedThreadCallback(void *arg) {
-  __tsan_func_entry(__builtin_return_address(0));
+  __tsan_func_entry(CALLERPC);
   Impl *impl = (Impl*)arg;
   for (;;) {
     Event* ev = (Event*)atomic_load(&impl->event, memory_order_acquire);
     if (ev == 0) {
       sched_yield();
       continue;
     }
     if (ev->type == Event::SHUTDOWN) {
void ScopedThread::Detach() {
   CHECK(!impl_->main);
   CHECK(!impl_->detached);
   impl_->detached = true;
   __interceptor_pthread_detach(impl_->thread);
 }
 
 void ScopedThread::Access(void *addr, bool is_write,
                           int size, bool expect_race) {
-  Event event(is_write ? Event::WRITE : Event::READ, addr, size);
+  Event event(is_write ? Event::WRITE : Event::READ, addr, size, (uptr)CALLERPC);
   if (expect_race)
     event.ExpectReport(ReportTypeRace);
   impl_->send(&event);
 }
 
 void ScopedThread::VptrUpdate(const MemLoc &vptr,
                               const MemLoc &new_val,
                               bool expect_race) {