[tsan] Track external tags in thread traces

[kubamracek]

Summary

To make the TSan external API work with Swift and other use cases, we need to track "tags" for individual memory accesses. Since there is no space to store this information in shadow cells, let's use the thread traces for that. This patch stores the tag as an extra frame in the stack traces (by calling FuncEntry and FuncExit with the address of a registered tag), this extra frame is then stripped before printing the backtrace to stderr.

[dvyukov]

lib/tsan/rtl/tsan_rtl_report.cc

662

I think it's better to separate stack and tag directly in ObtainCurrentStack and RestoreStack because:

1. We will not need to copy traces here (which is ugly and confusing at first glance).
2. No chance that the fake PCs pop up somewhere else because we forgot to remove them.
3. Racy stacks will be more difficult to break (currently a future change to this function can lead to a situation when we remember a stripped stack but check against non-stripped).
4. It will be easier to figure out report type without creating ScopedReport first and then fixing up the type with SetType.

665

I wonder if we need ReportTypeExternalRace at all.
We could always use ReportTypeRace, but attach tag to the report instead of memory accesses. Then we don't need SetType and PrintReport will be able to specialize report header with e.g. "data race on curl handle", because then it will know that the whole report is about an external access.
What do you think?

[kubamracek]

Updating patch.

[kubamracek]

lib/tsan/rtl/tsan_rtl_report.cc

662

Done.

665

I'd still like to keep it. There's at least the debugger support that needs to be able to distinguish an "external" race from a regular one.

[dvyukov]

One last thing. Otherwise LGTM.

lib/tsan/rtl/tsan_rtl_report.cc

662

Calculate typ before creating ScopedReport and remove SetType function. It feels clumsy that we can't figure out report type when we are creating it and add setters to patch it afterwards.

if (tags[0] != kExternalTagNone || tags[1] != kExternalTagNone)
  typ = ReportTypeExternalRace;
ScopedReport rep(typ);

will do.

lib/tsan/go/buildgo.sh

 #!/bin/sh
 
 set -e
 
 SRCS="
   tsan_go.cc
   ../rtl/tsan_clock.cc
+  ../rtl/tsan_external.cc
   ../rtl/tsan_flags.cc
   ../rtl/tsan_interface_atomic.cc
   ../rtl/tsan_md5.cc
   ../rtl/tsan_mutex.cc
   ../rtl/tsan_report.cc
   ../rtl/tsan_rtl.cc
   ../rtl/tsan_rtl_mutex.cc
   ../rtl/tsan_rtl_report.cc

lib/tsan/rtl/tsan_external.cc

 //===----------------------------------------------------------------------===//
 #include "tsan_rtl.h"
 #include "tsan_interceptors.h"
 
 namespace __tsan {
 
 #define CALLERPC ((uptr)__builtin_return_address(0))
 
-const uptr kMaxTag = 128;  // Limited to 65,536, since MBlock only stores tags
-                           // as 16-bit values, see tsan_defs.h.
-
-const char *registered_tags[kMaxTag];
-static atomic_uint32_t used_tags{1};  // Tag 0 means "no tag". NOLINT
+const char *registered_tags[kExternalTagMax];
+static atomic_uint32_t used_tags{kExternalTagFirstUserAvailable};  // NOLINT.
 
 const char *GetObjectTypeFromTag(uptr tag) {
   if (tag == 0) return nullptr;
   // Invalid/corrupted tag?  Better return NULL and let the caller deal with it.
   if (tag >= atomic_load(&used_tags, memory_order_relaxed)) return nullptr;
   return registered_tags[tag];
 }
 
+void InsertShadowStackFrameForTag(ThreadState *thr, uptr tag) {
+  FuncEntry(thr, (uptr)&registered_tags[tag]);
+}
+
+uptr TagFromShadowStackFrame(uptr pc) {
+  uptr tag_count = atomic_load(&used_tags, memory_order_relaxed);
+  void *pc_ptr = (void *)pc;
+  if (pc_ptr < &registered_tags[0] || pc_ptr >= &registered_tags[tag_count])
+    return 0;
+  return (const char **)pc_ptr - &registered_tags[0];
+}
+
+#if !SANITIZER_GO
+
 typedef void(*AccessFunc)(ThreadState *, uptr, uptr, int);
 void ExternalAccess(void *addr, void *caller_pc, void *tag, AccessFunc access) {
   CHECK_LT(tag, atomic_load(&used_tags, memory_order_relaxed));
   ThreadState *thr = cur_thread();
-  thr->external_tag = (uptr)tag;
   if (caller_pc) FuncEntry(thr, (uptr)caller_pc);
+  InsertShadowStackFrameForTag(thr, (uptr)tag);
   bool in_ignored_lib;
   if (!caller_pc || !libignore()->IsIgnored((uptr)caller_pc, &in_ignored_lib)) {
     access(thr, CALLERPC, (uptr)addr, kSizeLog1);
   }
+  FuncExit(thr);
   if (caller_pc) FuncExit(thr);
-  thr->external_tag = 0;
 }
 
 extern "C" {
 SANITIZER_INTERFACE_ATTRIBUTE
 void *__tsan_external_register_tag(const char *object_type) {
   uptr new_tag = atomic_fetch_add(&used_tags, 1, memory_order_relaxed);
-  CHECK_LT(new_tag, kMaxTag);
+  CHECK_LT(new_tag, kExternalTagMax);
   registered_tags[new_tag] = internal_strdup(object_type);
   return (void *)new_tag;
 }
 
 SANITIZER_INTERFACE_ATTRIBUTE
 void __tsan_external_assign_tag(void *addr, void *tag) {
   CHECK_LT(tag, atomic_load(&used_tags, memory_order_relaxed));
   Allocator *a = allocator();

 }
 
 SANITIZER_INTERFACE_ATTRIBUTE
 void __tsan_external_write(void *addr, void *caller_pc, void *tag) {
   ExternalAccess(addr, caller_pc, tag, MemoryWrite);
 }
 }  // extern "C"
 
+#endif  // !SANITIZER_GO
+
 }  // namespace __tsan

lib/tsan/rtl/tsan_report.cc

return first ? (write ? "Mutating" : "Read-only")
                : (write ? "Previous mutating" : "Previous read-only");
 }
 
 static void PrintMop(const ReportMop *mop, bool first) {
   Decorator d;
   char thrbuf[kThreadBufSize];
   Printf("%s", d.Access());
   const char *object_type = GetObjectTypeFromTag(mop->external_tag);
-  if (!object_type) {
+  if (mop->external_tag == kExternalTagNone || !object_type) {
     Printf("  %s of size %d at %p by %s",
            MopDesc(first, mop->write, mop->atomic), mop->size,
            (void *)mop->addr, thread_name(thrbuf, mop->tid));
   } else {
     Printf("  %s access of %s at %p by %s",
            ExternalMopDesc(first, mop->write), object_type,
            (void *)mop->addr, thread_name(thrbuf, mop->tid));
   }

lib/tsan/rtl/tsan_rtl.h

#endif
   const int tid;
   const int unique_id;
   bool in_symbolizer;
   bool in_ignored_lib;
   bool is_inited;
   bool is_dead;
   bool is_freeing;
   bool is_vptr_access;
-  uptr external_tag;
   const uptr stk_addr;
   const uptr stk_size;
   const uptr tls_addr;
   const uptr tls_size;
   ThreadContext *tctx;
 
 #if SANITIZER_DEBUG && !SANITIZER_GO
   InternalDeadlockDetector internal_deadlock_detector;
#endif
 
   ~ScopedIgnoreInterceptors() {
 #if !SANITIZER_GO
     cur_thread()->ignore_interceptors--;
 #endif
   }
 };
 
+enum ExternalTag : uptr {
+  kExternalTagNone = 0,
+  kExternalTagFirstUserAvailable = 1,
+  kExternalTagMax = 1024,
+  // Don't set kExternalTagMax over 65,536, since MBlock only stores tags
+  // as 16-bit values, see tsan_defs.h.
+};
+const char *GetObjectTypeFromTag(uptr tag);
+uptr TagFromShadowStackFrame(uptr pc);
+
 class ScopedReport {
  public:
   explicit ScopedReport(ReportType typ);
   ~ScopedReport();
 
   void AddMemoryAccess(uptr addr, uptr external_tag, Shadow s, StackTrace stack,
                        const MutexSet *mset);
   void AddStack(StackTrace stack, bool suppressable = false);
   void AddThread(const ThreadContext *tctx, bool suppressable = false);
   void AddThread(int unique_tid, bool suppressable = false);
   void AddUniqueTid(int unique_tid);
   void AddMutex(const SyncVar *s);
   u64 AddMutex(u64 id);
   void AddLocation(uptr addr, uptr size);
   void AddSleep(u32 stack_id);
   void SetCount(int count);
+  void SetType(ReportType typ);
 
   const ReportDesc *GetReport() const;
 
  private:
   ReportDesc *rep_;
   // Symbolizer makes lots of intercepted calls. If we try to process them,
   // at best it will cause deadlocks on internal mutexes.
   ScopedIgnoreInterceptors ignore_interceptors_;
 
   void AddDeadMutex(u64 id);
 
   ScopedReport(const ScopedReport&);
   void operator = (const ScopedReport&);
 };
 
 ThreadContext *IsThreadStackOrTls(uptr addr, bool *is_stack);
 void RestoreStack(int tid, const u64 epoch, VarSizeStackTrace *stk,
-                  MutexSet *mset);
+                  MutexSet *mset, uptr *tag = nullptr);
+
+// The stack could look like:
+//   <start> | <main> | <foo> | tag | <bar>
+// This will extract the tag and keep:
+//   <start> | <main> | <foo> | <bar>
+template<typename StackTraceTy>
+void ExtractTagFromStack(StackTraceTy *stack, uptr *tag = nullptr) {
+  if (stack->size < 2) return;
+  uptr possible_tag_pc = stack->trace[stack->size - 2];
+  uptr possible_tag = TagFromShadowStackFrame(possible_tag_pc);
+  if (possible_tag == kExternalTagNone) return;
+  stack->trace_buffer[stack->size - 2] = stack->trace_buffer[stack->size - 1];
+  stack->size -= 1;
+  if (tag) *tag = possible_tag;
+}
 
 template<typename StackTraceTy>
-void ObtainCurrentStack(ThreadState *thr, uptr toppc, StackTraceTy *stack) {
+void ObtainCurrentStack(ThreadState *thr, uptr toppc, StackTraceTy *stack,
+                        uptr *tag = nullptr) {
   uptr size = thr->shadow_stack_pos - thr->shadow_stack;
   uptr start = 0;
   if (size + !!toppc > kStackTraceMax) {
     start = size + !!toppc - kStackTraceMax;
     size = kStackTraceMax - !!toppc;
   }
   stack->Init(&thr->shadow_stack[start], size, toppc);
+  ExtractTagFromStack(stack, tag);
 }
 
 
 #if TSAN_COLLECT_STATS
 void StatAggregate(u64 *dst, u64 *src);
 void StatOutput(u64 *stat);
 #endif
 

 void ForkChildAfter(ThreadState *thr, uptr pc);
 
 void ReportRace(ThreadState *thr);
 bool OutputReport(ThreadState *thr, const ScopedReport &srep);
 bool IsFiredSuppression(Context *ctx, ReportType type, StackTrace trace);
 bool IsExpectedReport(uptr addr, uptr size);
 void PrintMatchedBenignRaces();
 
-const char *GetObjectTypeFromTag(uptr tag);
-
 #if defined(TSAN_DEBUG_OUTPUT) && TSAN_DEBUG_OUTPUT >= 1
 # define DPrintf Printf
 #else
 # define DPrintf(...)
 #endif
 
 #if defined(TSAN_DEBUG_OUTPUT) && TSAN_DEBUG_OUTPUT >= 2
 # define DPrintf2 Printf

lib/tsan/rtl/tsan_rtl_report.cc

void ScopedReport::AddSleep(u32 stack_id) {
   rep_->sleep = SymbolizeStackId(stack_id);
 }
 #endif
 
 void ScopedReport::SetCount(int count) {
   rep_->count = count;
 }
 
+void ScopedReport::SetType(ReportType typ) {
+  rep_->typ = typ;
+}
+
 const ReportDesc *ScopedReport::GetReport() const {
   return rep_;
 }
 
 void RestoreStack(int tid, const u64 epoch, VarSizeStackTrace *stk,
-                  MutexSet *mset) {
+                  MutexSet *mset, uptr *tag) {
   // This function restores stack trace and mutex set for the thread/epoch.
   // It does so by getting stack trace and mutex set at the beginning of
   // trace part, and then replaying the trace till the given epoch.
   Trace* trace = ThreadTrace(tid);
   ReadLock l(&trace->mtx);
   const int partidx = (epoch / kTracePartSize) % TraceParts();
   TraceHeader* hdr = &trace->headers[partidx];
   if (epoch < hdr->epoch0 || epoch >= hdr->epoch0 + kTracePartSize)
for (uptr i = ebegin; i <= eend; i++) {
     }
     for (uptr j = 0; j <= pos; j++)
       DPrintf2("      #%zu: %zx\n", j, stack[j]);
   }
   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};
void ReportRace(ThreadState *thr) {
 
   ReportType typ = ReportTypeRace;
   if (thr->is_vptr_access && freed)
     typ = ReportTypeVptrUseAfterFree;
   else if (thr->is_vptr_access)
     typ = ReportTypeVptrRace;
   else if (freed)
     typ = ReportTypeUseAfterFree;
-  else if (thr->external_tag > 0)
-    typ = ReportTypeExternalRace;
 
   if (IsFiredSuppression(ctx, typ, addr))
     return;
 
   const uptr kMop = 2;
   VarSizeStackTrace traces[kMop];
+  uptr tags[kMop];
   const uptr toppc = TraceTopPC(thr);
-  ObtainCurrentStack(thr, toppc, &traces[0]);
+  ObtainCurrentStack(thr, toppc, &traces[0], &tags[0]);
   if (IsFiredSuppression(ctx, typ, traces[0]))
     return;
 
   // MutexSet is too large to live on stack.
   Vector<u64> mset_buffer(MBlockScopedBuf);
   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);
+  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))
     return;
 
   ThreadRegistryLock l0(ctx->thread_registry);
   ScopedReport rep(typ);
   for (uptr i = 0; i < kMop; i++) {
+    if (tags[i] != kExternalTagNone) {
+      rep.SetType(ReportTypeExternalRace);
+    }
+
     Shadow s(thr->racy_state[i]);
-    rep.AddMemoryAccess(addr, thr->external_tag, s, traces[i],
+    rep.AddMemoryAccess(addr, tags[i], s, traces[i],
                         i == 0 ? &thr->mset : mset2);
   }
 
   for (uptr i = 0; i < kMop; i++) {
     FastState s(thr->racy_state[i]);
     ThreadContext *tctx = static_cast<ThreadContext*>(
         ctx->thread_registry->GetThreadLocked(s.tid()));
     if (s.epoch() < tctx->epoch0 || s.epoch() > tctx->epoch1)