[tsan] Detect races on modifying accesses in Swift code

[kubamracek]

Summary

This patch allows the Swift compiler to emit calls to __tsan_external_write before starting any modifying access, which will cause TSan to detect races on arrays, dictionaries and other classes defined in non-instrumented modules. Races on collections from the Swift standard library and user-defined structs and a frequent cause of subtle bugs and it's important that TSan detects those on top of existing LLVM IR instrumentation, which already detects races in direct memory accesses.

[kubamracek]

See https://groups.google.com/forum/#!topic/thread-sanitizer/r7HmBkKQiIw for more information about this patch.

[kubamracek]

Updating the patch with a solution to address the problem described at https://groups.google.com/forum/#!topic/thread-sanitizer/r7HmBkKQiIw:

There is a problem is that we often detect the race on the "regular" access (called from LLVM IR instrumentation), and we can't tell that this is a Swift-type race, because we don't store the information that the previous access way a sizeless, external memory access. Currently, the __tsan_external_write API simply does MemoryWrite(addr, kSizeLog8), so we track those accesses as 8-byte long, which is not really true. We'd like to instead treat them as "sizeless".

This patch stores the external tag information in a fake stack frame in thr->shadow_stack, which is later retrieved during issue reporting. I'm open to better suggestions.

[dvyukov]

Hi Kuba,

I've seen a bunch of changes from you and they all are marked in my inbox. The past 1.5 weeks I was travelling and next week I am OOO so won't be able to review them. Just wanted to let you know.

[dvyukov]

In D31630#721583, @dvyukov wrote:

Hi Kuba,

I've seen a bunch of changes from you and they all are marked in my inbox. The past 1.5 weeks I was travelling and next week I am OOO so won't be able to review them. Just wanted to let you know.

I am back. Slowly working on backlog.

[dvyukov]

I don't like that we sprinkle swift-specific bits throughout the code when the external API was meant to be general enough to cover all such cases.
We have the special tag for swift, so it really seems to me that it should be the only swift-specific bit here and the rest must be handled by the external API on general basis. We have 3 potential users for the external API (Go, Java, races on fd, potentially more in future). So I would be really interested in making the external API general and flexible enough to support all of them, rather than later sprinkle Go/Java/fd/etc-specific bits throughout the code again later.

Why do we say "Mutating" for external and "Modifying" for swift? Please settle on 1 form.
Why is the tag for switch includes "modifying"? Modifying/non-modifying is orthogonal to the object type and is controlled by __tsan_external_read/write. It really should be kExternalTagSwiftAccess.
If we want to say "swift" in header line, why don't we want the same level of support for other external objects?

I propose we say for usual data races:

ThreadSanitizer: data race

Write of size X at P by S
Previous write of size X at P by S

and for external accesses:

ThreadSanitizer: race on TAG_NAME

Mutating access at P by S
Previous mutating access at P by S

(or Modifying, I don't care too much)

This will allow us to have:

ThreadSanitizer: race on file descriptor
ThreadSanitizer: race on curl handle
ThreadSanitizer: race on Swift array
ThreadSanitizer: race on Swift map
ThreadSanitizer: race on Go map

Also, could swift runtime register a tag at startup? Or performance overhead is a concern?

test/tsan/Darwin/external-swift.cc

11

Declare them in test.h. They will be used by other tests in future.

[dvyukov]

We have 3 potential users for the external API (Go, Java, races on fd, potentially more in future).

Also add races on vptr to the list.

lib/tsan/rtl/tsan_rtl.h

651 ↗

(On Diff #94144)

Why is it 128? It seems it should be 2.

[dvyukov]

In D31630#730957, @dvyukov wrote:

In D31630#721583, @dvyukov wrote:

Hi Kuba,

I've seen a bunch of changes from you and they all are marked in my inbox. The past 1.5 weeks I was travelling and next week I am OOO so won't be able to review them. Just wanted to let you know.

I am back. Slowly working on backlog.

I now think that I replied to all pending reviews. If there is anything left, please ping them.

lib/tsan/rtl/tsan_report.cc

215

It's better to drop "object" here to make it more general. A user can always add "object" to tag name if necessary.

lib/tsan/rtl/tsan_suppressions.cc

79

It seems to me that we now won't see ReportTypeExternalRace/ReportTypeSwiftAccessRace here.

[kubamracek]

First, let me split out the conversion of tag tracking in ThreadState into tracking in thread event logs: https://reviews.llvm.org/D32382.

[kubamracek]

lib/tsan/rtl/tsan_report.cc

215

https://reviews.llvm.org/D32383

lib/tsan/rtl/tsan_rtl.h

651 ↗

(On Diff #94144)

https://reviews.llvm.org/D32382

test/tsan/Darwin/external-swift.cc

11

https://reviews.llvm.org/D32384

[kubamracek]

Uploading with without the extracted standalone parts.

[kubamracek]

Addressing review comments.

[kubamracek]

ThreadSanitizer: race on Swift array
ThreadSanitizer: race on Swift map

Unfortunately, we won't be able to tell the type of the variable (at least not now). I've updated the patch to say "race on Swift variable", but that's not really exact and it's not describing the problem well. Swift is getting exact threading rules that are very different from C/C++ and I'm trying to focus on making the reports readable and understandable by Swift users.

Is there a way we could still special-case the Swift reports? I understand the desire to keep the API generic, but I think we need to make sure the users understand the report. E.g. "Swift access race" much better describes what the problem is, and users words that define the Swift threading model.

Also, could swift runtime register a tag at startup? Or performance overhead is a concern?

It's quite hard to make the runtime call the registration at process startup, because it would need to dynamically figure out whether we're running with TSan or not, plus we'd need to add an indirection to each access (to read the value of the tag). I'd really prefer to keep the value as a well-defined constant in TSan.

[dvyukov]

In D31630#734474, @kubamracek wrote:

Also, could swift runtime register a tag at startup? Or performance overhead is a concern?

It's quite hard to make the runtime call the registration at process startup, because it would need to dynamically figure out whether we're running with TSan or not, plus we'd need to add an indirection to each access (to read the value of the tag). I'd really prefer to keep the value as a well-defined constant in TSan.

Agree, I think, a constant is the right way to do it.
Any other uses that I think of will also be much simpler/faster with a constant.

[dvyukov]

In D31630#734474, @kubamracek wrote:

ThreadSanitizer: race on Swift array
ThreadSanitizer: race on Swift map

Unfortunately, we won't be able to tell the type of the variable (at least not now). I've updated the patch to say "race on Swift variable", but that's not really exact and it's not describing the problem well. Swift is getting exact threading rules that are very different from C/C++ and I'm trying to focus on making the reports readable and understandable by Swift users.

Is there a way we could still special-case the Swift reports? I understand the desire to keep the API generic, but I think we need to make sure the users understand the report. E.g. "Swift access race" much better describes what the problem is, and users words that define the Swift threading model.

Humm... what is so special about Swift? Isn't it that concurrent accesses to some objects are a bug? I would expect that it is, and then it's no different from C/C++ variables, C++ containers, Go variables and containers, Java containers, file descriptors and everything else.

I don't understand why saying race or data race on something is confusing or not understand-able. What's ambiguous/obscure/wrong about it?
On the other hand I have problems understanding meaning of "Swift access race". Does it mean "race during access to a Swift object"? If so it's semantically equivalent to "race on Swift object".

[kubamracek]

In D31630#736670, @dvyukov wrote:

In D31630#734474, @kubamracek wrote:

ThreadSanitizer: race on Swift array
ThreadSanitizer: race on Swift map

Unfortunately, we won't be able to tell the type of the variable (at least not now). I've updated the patch to say "race on Swift variable", but that's not really exact and it's not describing the problem well. Swift is getting exact threading rules that are very different from C/C++ and I'm trying to focus on making the reports readable and understandable by Swift users.

Is there a way we could still special-case the Swift reports? I understand the desire to keep the API generic, but I think we need to make sure the users understand the report. E.g. "Swift access race" much better describes what the problem is, and users words that define the Swift threading model.

Humm... what is so special about Swift? Isn't it that concurrent accesses to some objects are a bug? I would expect that it is, and then it's no different from C/C++ variables, C++ containers, Go variables and containers, Java containers, file descriptors and everything else.

I don't understand why saying race or data race on something is confusing or not understand-able. What's ambiguous/obscure/wrong about it?
On the other hand I have problems understanding meaning of "Swift access race". Does it mean "race during access to a Swift object"? If so it's semantically equivalent to "race on Swift object".

The memory/threading model of Swift defines races in terms of accesses: Starting a new "modifying" access requires that there are no outstanding accesses. And "access" here means the formal duration over which the variable is accessed, e.g. the whole function call for inout arguments. This is all pretty new and still being worked on: https://github.com/apple/swift/blob/master/docs/OwnershipManifesto.md.

[dvyukov]

In D31630#736944, @kubamracek wrote:

In D31630#736670, @dvyukov wrote:

In D31630#734474, @kubamracek wrote:

ThreadSanitizer: race on Swift array
ThreadSanitizer: race on Swift map

Unfortunately, we won't be able to tell the type of the variable (at least not now). I've updated the patch to say "race on Swift variable", but that's not really exact and it's not describing the problem well. Swift is getting exact threading rules that are very different from C/C++ and I'm trying to focus on making the reports readable and understandable by Swift users.

Is there a way we could still special-case the Swift reports? I understand the desire to keep the API generic, but I think we need to make sure the users understand the report. E.g. "Swift access race" much better describes what the problem is, and users words that define the Swift threading model.

Humm... what is so special about Swift? Isn't it that concurrent accesses to some objects are a bug? I would expect that it is, and then it's no different from C/C++ variables, C++ containers, Go variables and containers, Java containers, file descriptors and everything else.

I don't understand why saying race or data race on something is confusing or not understand-able. What's ambiguous/obscure/wrong about it?
On the other hand I have problems understanding meaning of "Swift access race". Does it mean "race during access to a Swift object"? If so it's semantically equivalent to "race on Swift object".

The memory/threading model of Swift defines races in terms of accesses: Starting a new "modifying" access requires that there are no outstanding accesses. And "access" here means the formal duration over which the variable is accessed, e.g. the whole function call for inout arguments. This is all pretty new and still being worked on: https://github.com/apple/swift/blob/master/docs/OwnershipManifesto.md.

Then let's register report header for external tags.

[kubamracek]

The memory/threading model of Swift defines races in terms of accesses: Starting a new "modifying" access requires that there are no outstanding accesses. And "access" here means the formal duration over which the variable is accessed, e.g. the whole function call for inout arguments. This is all pretty new and still being worked on: https://github.com/apple/swift/blob/master/docs/OwnershipManifesto.md.

Then let's register report header for external tags.

What do you mean by that? Can you explain?

[dvyukov]

In D31630#736979, @kubamracek wrote:

The memory/threading model of Swift defines races in terms of accesses: Starting a new "modifying" access requires that there are no outstanding accesses. And "access" here means the formal duration over which the variable is accessed, e.g. the whole function call for inout arguments. This is all pretty new and still being worked on: https://github.com/apple/swift/blob/master/docs/OwnershipManifesto.md.

Then let's register report header for external tags.

What do you mean by that? Can you explain?

Currently we have:

void *__tsan_external_register_tag(const char *object_type);

I am proposing:

void *__tsan_external_register_tag(const char *report_header, const char *object_type);

Then we can have customized report header for external tags.
For the dedicated swift tag, you will need to pre-populate the global tag descriptor with necessary report header and object name. Then we don't need any swift-specific changes in ReportRace/PrintReport.
To make this work we will also need to associate tag with the whole report (rather than with memory access descriptors), but it looks like the right thing to do regardless.
I am not sure if we will still need object_type then.

[kubamracek]

Updating the patch, addressing review comments. I added a separate API to register report header strings to avoid breaking existing users of the API.

[dvyukov]

Thanks!
I think this now provides a solid foundation for future extensions.

lib/tsan/rtl/tsan_debugging.cc

 using namespace __tsan;
 
 static const char *ReportTypeDescription(ReportType typ) {
   if (typ == ReportTypeRace) return "data-race";
   if (typ == ReportTypeVptrRace) return "data-race-vptr";
   if (typ == ReportTypeUseAfterFree) return "heap-use-after-free";
   if (typ == ReportTypeVptrUseAfterFree) return "heap-use-after-free-vptr";
   if (typ == ReportTypeExternalRace) return "external-race";
+  if (typ == ReportTypeSwiftAccessRace) return "swift-access-race";
   if (typ == ReportTypeThreadLeak) return "thread-leak";
   if (typ == ReportTypeMutexDestroyLocked) return "locked-mutex-destroy";
   if (typ == ReportTypeMutexDoubleLock) return "mutex-double-lock";
   if (typ == ReportTypeMutexInvalidAccess) return "mutex-invalid-access";
   if (typ == ReportTypeMutexBadUnlock) return "mutex-bad-unlock";
   if (typ == ReportTypeMutexBadReadLock) return "mutex-bad-read-lock";
   if (typ == ReportTypeMutexBadReadUnlock) return "mutex-bad-read-unlock";
   if (typ == ReportTypeSignalUnsafe) return "signal-unsafe-call";

lib/tsan/rtl/tsan_report.h

 namespace __tsan {
 
 enum ReportType {
   ReportTypeRace,
   ReportTypeVptrRace,
   ReportTypeUseAfterFree,
   ReportTypeVptrUseAfterFree,
   ReportTypeExternalRace,
+  ReportTypeSwiftAccessRace,
   ReportTypeThreadLeak,
   ReportTypeMutexDestroyLocked,
   ReportTypeMutexDoubleLock,
   ReportTypeMutexInvalidAccess,
   ReportTypeMutexBadUnlock,
   ReportTypeMutexBadReadLock,
   ReportTypeMutexBadReadUnlock,
   ReportTypeSignalUnsafe,

lib/tsan/rtl/tsan_report.cc

static const char *ReportTypeString(ReportType typ) {
   if (typ == ReportTypeVptrRace)
     return "data race on vptr (ctor/dtor vs virtual call)";
   if (typ == ReportTypeUseAfterFree)
     return "heap-use-after-free";
   if (typ == ReportTypeVptrUseAfterFree)
     return "heap-use-after-free (virtual call vs free)";
   if (typ == ReportTypeExternalRace)
     return "race on a library object";
+  if (typ == ReportTypeSwiftAccessRace)
+    return "Swift access race";
   if (typ == ReportTypeThreadLeak)
     return "thread leak";
   if (typ == ReportTypeMutexDestroyLocked)
     return "destroy of a locked mutex";
   if (typ == ReportTypeMutexDoubleLock)
     return "double lock of a mutex";
   if (typ == ReportTypeMutexInvalidAccess)
     return "use of an invalid mutex (e.g. uninitialized or destroyed)";
return atomic ? (first ? (write ? "Atomic write" : "Atomic read")
                 : (write ? "Previous write" : "Previous read"));
 }
 
 static const char *ExternalMopDesc(bool first, bool write) {
   return first ? (write ? "Mutating" : "Read-only")
                : (write ? "Previous mutating" : "Previous read-only");
 }
 
+static const char *SwiftMopDesc(bool first) {
+  return first ? "Modifying" : "Previous modifying";
+}
+
 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 == kExternalTagSwiftModifyingAccess) {
+    Printf("  %s access at %p by %s",
+           SwiftMopDesc(first), (void *)mop->addr,
+           thread_name(thrbuf, mop->tid));
+  } else 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 object %s at %p by %s",
            ExternalMopDesc(first, mop->write), object_type,
            (void *)mop->addr, thread_name(thrbuf, mop->tid));
   }
static void PrintLocation(const ReportLocation *loc) {
   } else if (loc->type == ReportLocationHeap) {
     char thrbuf[kThreadBufSize];
     const char *object_type = GetObjectTypeFromTag(loc->external_tag);
     if (!object_type) {
       Printf("  Location is heap block of size %zu at %p allocated by %s:\n",
              loc->heap_chunk_size, loc->heap_chunk_start,
              thread_name(thrbuf, loc->tid));
     } else {
       Printf("  Location is %s object of size %zu at %p allocated by %s:\n",
              object_type, loc->heap_chunk_size, loc->heap_chunk_start,
              thread_name(thrbuf, loc->tid));
     }
     print_stack = true;
   } else if (loc->type == ReportLocationStack) {
     Printf("  Location is stack of %s.\n\n", thread_name(thrbuf, loc->tid));
   } else if (loc->type == ReportLocationTLS) {
     Printf("  Location is TLS of %s.\n\n", thread_name(thrbuf, loc->tid));

lib/tsan/rtl/tsan_rtl_report.cc

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++) {
+    uptr tag = RetrieveTagFromStackTrace(&traces[i]);
+    if (tag == kExternalTagSwiftModifyingAccess) {
+      rep.SetType(ReportTypeSwiftAccessRace);
+    } else if (tag != kExternalTagNone) {
+      rep.SetType(ReportTypeExternalRace);
+    }
+
     Shadow s(thr->racy_state[i]);
-    rep.AddMemoryAccess(addr, thr->external_tag, s, traces[i],
-                        i == 0 ? &thr->mset : mset2);
+    rep.AddMemoryAccess(addr, tag, 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)
       continue;

lib/tsan/rtl/tsan_suppressions.cc

static const char *conv(ReportType typ) {
   else if (typ == ReportTypeVptrRace)
     return kSuppressionRace;
   else if (typ == ReportTypeUseAfterFree)
     return kSuppressionRace;
   else if (typ == ReportTypeVptrUseAfterFree)
     return kSuppressionRace;
   else if (typ == ReportTypeExternalRace)
     return kSuppressionRace;
+  else if (typ == ReportTypeSwiftAccessRace)
+    return kSuppressionRace;
   else if (typ == ReportTypeThreadLeak)
     return kSuppressionThread;
   else if (typ == ReportTypeMutexDestroyLocked)
     return kSuppressionMutex;
   else if (typ == ReportTypeMutexDoubleLock)
     return kSuppressionMutex;
   else if (typ == ReportTypeMutexInvalidAccess)
     return kSuppressionMutex;

test/tsan/Darwin/external-swift.cc

+// RUN: %clangxx_tsan %s -o %t
+// RUN: %deflake %run %t 2>&1 | FileCheck %s
+
+#include <thread>
+
+#import "../test.h"
+
+static void *tag = (void *)0x1;
+
+__attribute__((no_sanitize("thread")))
+void ExternalWrite(void *addr) {
+  __tsan_external_write(addr, nullptr, tag);
+}
+
+__attribute__((no_sanitize("thread")))
+void RegularWrite(void *addr) {
+  __tsan_write8(addr);
+}
+
+int main(int argc, char *argv[]) {
+  barrier_init(&barrier, 2);
+  fprintf(stderr, "Start.\n");
+  // CHECK: Start.
+  
+  {
+    void *opaque_object = malloc(16);
+    std::thread t1([opaque_object] {
+      ExternalWrite(opaque_object);
+      barrier_wait(&barrier);
+    });
+    std::thread t2([opaque_object] {
+      barrier_wait(&barrier);
+      ExternalWrite(opaque_object);
+    });
+    // CHECK: WARNING: ThreadSanitizer: Swift access race
+    // CHECK: Modifying access at {{.*}} by thread {{.*}}
+    // CHECK: Previous modifying access at {{.*}} by thread {{.*}}
+    t1.join();
+    t2.join();
+  }
+
+  fprintf(stderr, "external+external test done.\n");
+  // CHECK: external+external test done.
+
+  {
+    void *opaque_object = malloc(16);
+    std::thread t1([opaque_object] {
+      ExternalWrite(opaque_object);
+      barrier_wait(&barrier);
+    });
+    std::thread t2([opaque_object] {
+      barrier_wait(&barrier);
+      RegularWrite(opaque_object);
+    });
+    // CHECK: WARNING: ThreadSanitizer: Swift access race
+    // CHECK: Write of size 8 at {{.*}} by thread {{.*}}
+    // CHECK: Previous modifying access at {{.*}} by thread {{.*}}
+    t1.join();
+    t2.join();
+  }
+  
+  fprintf(stderr, "external+regular test done.\n");
+  // CHECK: external+regular test done.
+  
+  {
+    void *opaque_object = malloc(16);
+    std::thread t1([opaque_object] {
+      RegularWrite(opaque_object);
+      barrier_wait(&barrier);
+    });
+    std::thread t2([opaque_object] {
+      barrier_wait(&barrier);
+      ExternalWrite(opaque_object);
+    });
+    // CHECK: WARNING: ThreadSanitizer: Swift access race
+    // CHECK: Modifying access at {{.*}} by thread {{.*}}
+    // CHECK: Previous write of size 8 at {{.*}} by thread {{.*}}
+    t1.join();
+    t2.join();
+  }
+  
+  fprintf(stderr, "regular+external test done.\n");
+  // CHECK: regular+external test done.
+}
+