[tsan] Implement basic GCD interceptors for OS X

[kubamracek]

Summary

We need to intercept libdispatch APIs (dispatch_sync, dispatch_async, etc.) to add synchronization between the code that submits the task and the code that gets executed (possibly on a different thread).

This code adds release+acquire semantics for dispatch_sync, dispatch_async, dispatch_after and dispatch_apply (plus their "_f" variants). Added a simple testcase using dispatch_async, I'll add more GCD tests later.

For a program using libdispatch, TSan produces a bunch of false positives (from libxpc, libobjc, etc.). In order to suppress those, I added a few system libraries into a list of default suppressions.

Secondly, dispatch_once is not properly interceptible, because part of it is inlined, see the comment in the patch. To avoid false positives here, this patch ignores all reads and writes coming from the initializer within dispatch_once.

[dvyukov]

Doh! Don't know whether I need to laugh or cry.
If you mean this one:
http://www.opensource.apple.com/source/libdispatch/libdispatch-339.1.9/dispatch/once.h
It does contain real, harmful data race. Load of predicate on fast path must be an atomic load with acquire memory ordering.

First we need to fix the actual bug in libdispatch.
Then you can do the same thing I did for pthread_once. Namely, reimplement dispatch_once entirely expecting that the inlined fast-path will load acquire load of the predicate address.

[dvyukov]

lib/tsan/rtl/tsan_libdispatch_mac.cc

1 ↗

(On Diff #40387)

s/tsan_platform_mac.cc/tsan_libdispatch_mac.cc/

162 ↗

(On Diff #40387)

I see the issue with non-instrumented system libraries.
Does it actually happen?

171 ↗

(On Diff #40387)

Why do you use a code block here, but don't use it in dispatch_once_f?
Can't we simply wrap REAL(dispatch_once) in ThreadIgnoreBegin/End here as well?

lib/tsan/rtl/tsan_suppressions.cc

39 ↗

(On Diff #40387)

Note that if you ignore interceptors, this can also introduce new false positives because of missed synchronization. So if you ignore a library you need to annotate all synchonization this library provides to user code.

test/tsan/Darwin/gcd-simple.mm

20 ↗

(On Diff #40387)

Also print DONE at the end of the program and check that it is printed. It happened several times that interceptors crash badly, but tests pass.

[dvyukov]

lib/tsan/rtl/tsan_libdispatch_mac.cc

65 ↗

(On Diff #40387)

You've added libdispatch to suppressions, and caller_pc inside of SCOPED_INTERCEPTOR_RAW should point into libdispatch, and you call user functions in the scope of SCOPED_INTERCEPTOR_RAW. This means that ScopedInterceptor constructor will disable memory accesses inside of user callback as well and we don't get any race detection.
Does it work at all? Please add a test with a data race inside of the callback.

75 ↗

(On Diff #40387)

It would be good to synchronize on an address associated with the work item submitted, rather than on the queue address. Synchronization on queue address will introduce lots of parasitic synchronization. Think of a widely used concurrent queue.

I guess we can't use the context for synchronization, because internal allocator memory does not have meta shadow mapped. Don't know whether a code block address can be used for that purpose (and whether it can be casted to uptr at all or not). If block address can't be used, then it worth it to allocate a context with malloc and use it address for synchronization.

81 ↗

(On Diff #40387)

Are closures for these code blocks dynamically allocated? With malloc?

86 ↗

(On Diff #40387)

empty line between macros, please

88 ↗

(On Diff #40387)

Why here you use a code block, but below you use an explicit context and function wrapper?

153 ↗

(On Diff #40387)

Is RELEASE_ACQUIRE_QUEUE_FUNCTION_INDEX intended to be used more? Currently it is the only call site. Which makes introduction of the helper macro questionable.

[kubamracek]

In D14745#290906, @dvyukov wrote:

Doh! Don't know whether I need to laugh or cry.
If you mean this one:
http://www.opensource.apple.com/source/libdispatch/libdispatch-339.1.9/dispatch/once.h
It does contain real, harmful data race. Load of predicate on fast path must be an atomic load with acquire memory ordering.

First we need to fix the actual bug in libdispatch.
Then you can do the same thing I did for pthread_once. Namely, reimplement dispatch_once entirely expecting that the inlined fast-path will load acquire load of the predicate address.

I talked to the maintainers of libdispatch, and I couldn't convince them that the race is actually harmful (including linking to https://software.intel.com/en-us/blogs/2013/01/06/benign-data-races-what-could-possibly-go-wrong). I think they'd be fine with changing the read into a *relaxed* atomic read (because that wouldn't actually change the generated ASM instructions), but that's still not enough for us (it needs to be *acquire*). Even if they did change it into a *load acquire* that TSan would catch, there'll be these issues left:

1. TSan will miss the *load acquire* in already compiled code (system libraries). This is unfortunately quite common.
2. It will only work properly in the next OS X release.

So at this point, I'd like to implement something that 1) works on current OS X and 2) doesn't produce false positives in system libraries. If you know of a better way (other than disabling reads/writes in the initializer), I'll be glad to consider it.

[dvyukov]

I talked to the maintainers of libdispatch, and I couldn't convince them that the race is actually harmful

This is a bug and it must be fixed. Filed:
https://libdispatch.macosforge.org/trac/ticket/2779

[dvyukov]

So at this point, I'd like to implement something that 1) works on current OS X and 2) doesn't produce false positives in system libraries. If you know of a better way (other than disabling reads/writes in the initializer), I'll be glad to consider it.

We can do:

TSAN_INTERCEPTOR(void, dispatch_once_f, dispatch_once_t *predicate, void *context, dispatch_function_t function) {

SCOPED_INTERCEPTOR_RAW(dispatch_once_f, predicate, context, function);
atomic_uint32_t *a = static_cast<atomic_uint32_t*>(predicate);
u32 v = atomic_load(a, memory_order_acquire);
if (v == 0 && atomic_compare_exchange_strong(a, &v, 1,
                                             memory_order_relaxed)) {
  (*function)(context);
  Release(thr, pc, (uptr)a);
  atomic_store(a, 2, memory_order_release);
} else {
  while (v != 2) {
    internal_sched_yield();
    v = atomic_load(a, memory_order_acquire);
  }
  Acquire(thr, pc, (uptr)a);
}
return 0;

}

Since we don't store ~0 into the predicate, the fast path will never be taken. So we will be able to annotate it even for non-instrumented code. Also, since tsan does not see own atomic stores, the race on predicate won't be reported: the only accesses to it that tsan sees is the load on fast path. Loads don't race.

[kubamracek]

In D14745#290962, @dvyukov wrote:

I talked to the maintainers of libdispatch, and I couldn't convince them that the race is actually harmful

This is a bug and it must be fixed. Filed:
https://libdispatch.macosforge.org/trac/ticket/2779

This bugtracking system seems to be unused. Would you mind filing a bug at https://bugreport.apple.com instead?

[dvyukov]

Filed radar bug 23575208. There does not seem to be a way to get a link to it....

[kubamracek]

In D14745#290972, @dvyukov wrote:

Filed radar bug 23575208. There does not seem to be a way to get a link to it....

Thanks!

[kubamracek]

I extracted the dispatch_once part of this patch into a separate revision: http://reviews.llvm.org/D14811

[kubamracek]

Simplifying this patch to only add interceptors for dispatch_sync and dispatch_async (and their _f and _barrier variants). Added more tests to show usage of dispatch_sync and dispatch_async, for cases where we expect no warnings and for cases where TSan finds races.

This patch doesn't need any suppressions (which was a bad idea and didn't work, you were right). The synchronization is now done on malloc'd contexts (separate for each submitted block/callback).

compiler-rt/trunk/lib/tsan/rtl/tsan_libdispatch_mac.cc

 #if SANITIZER_MAC
 
 #include "sanitizer_common/sanitizer_common.h"
 #include "interception/interception.h"
 #include "tsan_interceptors.h"
 #include "tsan_platform.h"
 #include "tsan_rtl.h"
 
+#include <Block.h>
 #include <dispatch/dispatch.h>
 #include <pthread.h>
 
 namespace __tsan {
 
+typedef struct {
+  dispatch_queue_t queue;
+  void *orig_context;
+  dispatch_function_t orig_work;
+} tsan_block_context_t;
+
+static tsan_block_context_t *AllocContext(ThreadState *thr, uptr pc,
+                                          dispatch_queue_t queue,
+                                          void *orig_context,
+                                          dispatch_function_t orig_work) {
+  tsan_block_context_t *new_context =
+      (tsan_block_context_t *)user_alloc(thr, pc, sizeof(tsan_block_context_t));
+  new_context->queue = queue;
+  new_context->orig_context = orig_context;
+  new_context->orig_work = orig_work;
+  return new_context;
+}
+
+static void dispatch_callback_wrap_acquire(void *param) {
+  SCOPED_INTERCEPTOR_RAW(dispatch_async_f_callback_wrap);
+  tsan_block_context_t *context = (tsan_block_context_t *)param;
+  Acquire(thr, pc, (uptr)context);
+  context->orig_work(context->orig_context);
+  user_free(thr, pc, context);
+}
+
+static void invoke_and_release_block(void *param) {
+  dispatch_block_t block = (dispatch_block_t)param;
+  block();
+  Block_release(block);
+}
+
+#define DISPATCH_INTERCEPT_B(name)                                           \
+  TSAN_INTERCEPTOR(void, name, dispatch_queue_t q, dispatch_block_t block) { \
+    SCOPED_TSAN_INTERCEPTOR(name, q, block);                                 \
+    dispatch_block_t heap_block = Block_copy(block);                         \
+    tsan_block_context_t *new_context =                                      \
+        AllocContext(thr, pc, q, heap_block, &invoke_and_release_block);     \
+    Release(thr, pc, (uptr)new_context);                                     \
+    REAL(name##_f)(q, new_context, dispatch_callback_wrap_acquire);          \
+  }
+
+#define DISPATCH_INTERCEPT_F(name)                                \
+  TSAN_INTERCEPTOR(void, name, dispatch_queue_t q, void *context, \
+                   dispatch_function_t work) {                    \
+    SCOPED_TSAN_INTERCEPTOR(name, q, context, work);              \
+    tsan_block_context_t *new_context =                           \
+        AllocContext(thr, pc, q, context, work);                  \
+    Release(thr, pc, (uptr)new_context);                          \
+    REAL(name)(q, new_context, dispatch_callback_wrap_acquire);   \
+  }
+
+// We wrap dispatch_async, dispatch_sync and friends where we allocate a new
+// context, which is used to synchronize (we release the context before
+// submitting, and the callback acquires it before executing the original
+// callback).
+DISPATCH_INTERCEPT_B(dispatch_async)
+DISPATCH_INTERCEPT_B(dispatch_barrier_async)
+DISPATCH_INTERCEPT_F(dispatch_async_f)
+DISPATCH_INTERCEPT_F(dispatch_barrier_async_f)
+DISPATCH_INTERCEPT_B(dispatch_sync)
+DISPATCH_INTERCEPT_B(dispatch_barrier_sync)
+DISPATCH_INTERCEPT_F(dispatch_sync_f)
+DISPATCH_INTERCEPT_F(dispatch_barrier_sync_f)
+
 // GCD's dispatch_once implementation has a fast path that contains a racy read
 // and it's inlined into user's code. Furthermore, this fast path doesn't
 // establish a proper happens-before relations between the initialization and
 // code following the call to dispatch_once. We could deal with this in
 // instrumented code, but there's not much we can do about it in system
 // libraries. Let's disable the fast path (by never storing the value ~0 to
 // predicate), so the interceptor is always called, and let's add proper release
 // and acquire semantics. Since TSan does not see its own atomic stores, the

compiler-rt/trunk/test/tsan/Darwin/gcd-async-norace.mm

+// RUN: %clang_tsan %s -o %t -framework Foundation
+// RUN: %run %t 2>&1
+
+#import <Foundation/Foundation.h>
+
+long global;
+
+int main() {
+  NSLog(@"Hello world.");
+
+  global = 42;
+  dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
+    global = 43;
+
+    dispatch_sync(dispatch_get_main_queue(), ^{
+      CFRunLoopStop(CFRunLoopGetCurrent());
+    });
+  });
+
+  CFRunLoopRun();
+  NSLog(@"Done.");
+}
+
+// CHECK: Hello world.
+// CHECK: Done.
+// CHECK-NOT: WARNING: ThreadSanitizer

compiler-rt/trunk/test/tsan/Darwin/gcd-async-race.mm

+// RUN: %clang_tsan %s -o %t -framework Foundation
+// RUN: %deflake %run %t 2>&1
+
+#import <Foundation/Foundation.h>
+
+#import "../test.h"
+
+long global;
+
+int main() {
+  NSLog(@"Hello world.");
+  NSLog(@"addr=%p\n", &global);
+  barrier_init(&barrier, 2);
+
+  global = 42;
+  dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
+    global = 43;
+    barrier_wait(&barrier);
+  });
+
+  dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
+    barrier_wait(&barrier);
+    global = 44;
+
+    dispatch_sync(dispatch_get_main_queue(), ^{
+      CFRunLoopStop(CFRunLoopGetCurrent());
+    });
+  });
+
+  CFRunLoopRun();
+  NSLog(@"Done.");
+}
+
+// CHECK: Hello world.
+// CHECK: addr=[[ADDR:0x[0-9,a-f]+]]
+// CHECK: WARNING: ThreadSanitizer: data race
+// CHECK: Location is global 'global' at [[ADDR]] (global_race.cc.exe+0x{{[0-9,a-f]+}})
+// CHECK: Done.

compiler-rt/trunk/test/tsan/Darwin/gcd-sync-norace.mm

+// RUN: %clang_tsan %s -o %t -framework Foundation
+// RUN: %run %t 2>&1
+
+#import <Foundation/Foundation.h>
+
+long global;
+
+static const long nIter = 1000;
+
+int main() {
+  NSLog(@"Hello world.");
+
+  global = 42;
+  for (int i = 0; i < nIter; i++) {
+    dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
+      dispatch_sync(dispatch_get_main_queue(), ^{
+        global = i;
+
+        if (i == nIter - 1) {
+          CFRunLoopStop(CFRunLoopGetCurrent());
+        }
+      });
+    });
+  }
+
+  CFRunLoopRun();
+  NSLog(@"Done.");
+}
+
+// CHECK: Hello world.
+// CHECK: Done.
+// CHECK-NOT: WARNING: ThreadSanitizer

compiler-rt/trunk/test/tsan/Darwin/gcd-sync-race.mm

+// RUN: %clang_tsan %s -o %t -framework Foundation
+// RUN: %deflake %run %t 2>&1
+
+#import <Foundation/Foundation.h>
+
+#import "../test.h"
+
+long global;
+
+int main() {
+  NSLog(@"Hello world.");
+  NSLog(@"addr=%p\n", &global);
+  barrier_init(&barrier, 2);
+
+  dispatch_queue_t q1 = dispatch_queue_create("my.queue1", DISPATCH_QUEUE_CONCURRENT);
+  dispatch_queue_t q2 = dispatch_queue_create("my.queue2", DISPATCH_QUEUE_CONCURRENT);
+
+  global = 42;
+  dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
+    dispatch_sync(q1, ^{
+      global = 43;
+      barrier_wait(&barrier);
+    });
+  });
+  dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
+    dispatch_sync(q2, ^{
+      barrier_wait(&barrier);
+      global = 44;
+
+      dispatch_sync(dispatch_get_main_queue(), ^{
+        CFRunLoopStop(CFRunLoopGetCurrent());
+      });
+    });
+  });
+
+  CFRunLoopRun();
+  NSLog(@"Done.");
+}
+
+// CHECK: Hello world.
+// CHECK: addr=[[ADDR:0x[0-9,a-f]+]]
+// CHECK: WARNING: ThreadSanitizer: data race
+// CHECK: Location is global 'global' at [[ADDR]] (global_race.cc.exe+0x{{[0-9,a-f]+}})
+// CHECK: Done.