[tsan] Add HB edges for GCD barrier blocks

[kubamracek]

Summary

We currently have false positives when using GCD barrier blocks with concurrent queues. The semantics of a submitted barrier block are:

1. All previously submitted blocks are completely finished before the barrier block starts executing.
2. The barrier block executed exclusively in the queue (as if the queue was serial for the duration of the block).
3. All subsequently submitted blocks are only executed after the barrier block has completely finished.

TSan needs two more HB edges to cover these semantics: One edge from previous (regular) blocks to the barrier block and one edge from the barrier block to all subsequent (regular) blocks. Only applies to concurrent queues.

[dvyukov]

lib/tsan/rtl/tsan_libdispatch_mac.cc

106

Shouldn't it be if (!queue_serial && !context->is_barrier_block). Because serial blocks and barriers blocks are already synchronized by other means.

It is very difficult to understand serial/concurrent/barrier/non-barrier synchronization now.
First observation is that serial queues are equivalent to concurrent queue with all blocks being barriers.
Second observation is that barrier/non-barrier blocks are equivalent to reader-writer mutexes with barriers being writers and non-barriers being readers.
Reader-writer synchronization is handled with 2 sync objects as:

uptr serial_sync = ((uptr)context->queue);
uptr concurrent_sync = ((uptr)context->queue) + sizeof(uptr);
bool serial_task = IsQueueSerial(context->queue) || context->is_barrier_block;

Acquire(thr, pc, serial_sync);
if (serial_task)
  Acquire(thr, pc, concurrent_sync);

SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_START();
context->orig_work(context->orig_context);
SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_END();

Release(thr, pc, serial_task ? serial_sync : concurrent_sync);

This looks simpler than your new code. Please use it.

[kubamracek]

Updating patch using Dmitry’s suggestion for simplifying serial and concurrent sync objects. I’m also simplifying some other stuff: Removing sync_object and object_to_release, because they were only used for dispatch groups, but they can now use is_barrier_block instead. Renaming release_sync_object_in_callback to submitted_synchronously.

[kubamracek]

One more typo fix in the dispatch groups interceptors.

[dvyukov]

I've submitted:
http://llvm.org/viewvc/llvm-project?view=revision&revision=273862
It should make these annotations more efficient for some cases (serial queues and concurrent queues with only concurrent tasks).

lib/tsan/rtl/tsan_libdispatch_mac.cc

 typedef long long_t;  // NOLINT
 
 namespace __tsan {
 
 typedef struct {
   dispatch_queue_t queue;
   void *orig_context;
   dispatch_function_t orig_work;
-  uptr sync_object;
-  dispatch_object_t object_to_release;
   bool free_context_in_callback;
-  bool release_sync_object_in_callback;
+  bool submitted_synchronously;
+  bool is_barrier_block;
 } tsan_block_context_t;
 
 // The offsets of different fields of the dispatch_queue_t structure, exported
 // by libdispatch.dylib.
 extern "C" struct dispatch_queue_offsets_s {
   const uint16_t dqo_version;
   const uint16_t dqo_label;
   const uint16_t dqo_label_size;
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;
-  new_context->sync_object = (uptr)new_context;
-  new_context->object_to_release = nullptr;
   new_context->free_context_in_callback = true;
-  new_context->release_sync_object_in_callback = false;
+  new_context->submitted_synchronously = false;
+  new_context->is_barrier_block = false;
   return new_context;
 }
 
 static void dispatch_callback_wrap(void *param) {
   SCOPED_INTERCEPTOR_RAW(dispatch_callback_wrap);
   tsan_block_context_t *context = (tsan_block_context_t *)param;
+  dispatch_queue_t q = context->queue;
 
-  Acquire(thr, pc, context->sync_object);
+  uptr serial_sync = (uptr)q;
+  uptr concurrent_sync = ((uptr)q) + sizeof(uptr);
+  uptr submit_sync = (uptr)context;
+  bool serial_task = IsQueueSerial(q) || context->is_barrier_block;
+
+  Acquire(thr, pc, submit_sync);
+  Acquire(thr, pc, serial_sync);
+  if (serial_task) Acquire(thr, pc, concurrent_sync);
 
-  // Extra retain/release is required for dispatch groups. We use the group
-  // itself to synchronize, but in a notification (dispatch_group_notify
-  // callback), it may be disposed already. To solve this, we retain the group
-  // and release it here.
-  if (context->object_to_release) dispatch_release(context->object_to_release);
-
-  // In serial queues, work items can be executed on different threads, we need
-  // to explicitly synchronize on the queue itself.
-  if (IsQueueSerial(context->queue)) Acquire(thr, pc, (uptr)context->queue);
   SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_START();
   context->orig_work(context->orig_context);
   SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_END();
-  if (IsQueueSerial(context->queue)) Release(thr, pc, (uptr)context->queue);
 
-  if (context->release_sync_object_in_callback)
-    Release(thr, pc, context->sync_object);
+  Release(thr, pc, serial_task ? serial_sync : concurrent_sync);
+  if (context->submitted_synchronously) Release(thr, pc, submit_sync);
 
   if (context->free_context_in_callback) 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)                                           \
+#define DISPATCH_INTERCEPT_B(name, barrier)                                  \
   TSAN_INTERCEPTOR(void, name, dispatch_queue_t q, dispatch_block_t block) { \
     SCOPED_TSAN_INTERCEPTOR(name, q, block);                                 \
     SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_START();                           \
     dispatch_block_t heap_block = Block_copy(block);                         \
     SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_END();                             \
     tsan_block_context_t *new_context =                                      \
         AllocContext(thr, pc, q, heap_block, &invoke_and_release_block);     \
+    new_context->is_barrier_block = barrier;                                 \
     Release(thr, pc, (uptr)new_context);                                     \
     SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_START();                           \
     REAL(name##_f)(q, new_context, dispatch_callback_wrap);                  \
     SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_END();                             \
   }
 
-#define DISPATCH_INTERCEPT_SYNC_B(name)                                      \
+#define DISPATCH_INTERCEPT_SYNC_B(name, barrier)                             \
   TSAN_INTERCEPTOR(void, name, dispatch_queue_t q, dispatch_block_t block) { \
     SCOPED_TSAN_INTERCEPTOR(name, q, block);                                 \
     SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_START();                           \
     dispatch_block_t heap_block = Block_copy(block);                         \
     SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_END();                             \
     tsan_block_context_t new_context = {                                     \
-        q, heap_block, &invoke_and_release_block, 0, 0, false, true};        \
-    new_context.sync_object = (uptr)&new_context;                            \
+        q, heap_block, &invoke_and_release_block, false, true, barrier};     \
     Release(thr, pc, (uptr)&new_context);                                    \
     SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_START();                           \
     REAL(name##_f)(q, &new_context, dispatch_callback_wrap);                 \
     SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_END();                             \
     Acquire(thr, pc, (uptr)&new_context);                                    \
   }
 
-#define DISPATCH_INTERCEPT_F(name)                                \
+#define DISPATCH_INTERCEPT_F(name, barrier)                       \
   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);                  \
+    new_context->is_barrier_block = barrier;                      \
     Release(thr, pc, (uptr)new_context);                          \
     SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_START();                \
     REAL(name)(q, new_context, dispatch_callback_wrap);           \
     SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_END();                  \
   }
 
-#define DISPATCH_INTERCEPT_SYNC_F(name)                                       \
+#define DISPATCH_INTERCEPT_SYNC_F(name, barrier)                              \
   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 = {q, context, work, 0, 0, false, true}; \
-    new_context.sync_object = (uptr)&new_context;                             \
+    tsan_block_context_t new_context = {                                      \
+        q, context, work, false, true, barrier};                              \
     Release(thr, pc, (uptr)&new_context);                                     \
     SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_START();                            \
     REAL(name)(q, &new_context, dispatch_callback_wrap);                      \
     SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_END();                              \
     Acquire(thr, pc, (uptr)&new_context);                                     \
   }
 
 // 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_SYNC_B(dispatch_sync)
-DISPATCH_INTERCEPT_SYNC_B(dispatch_barrier_sync)
-DISPATCH_INTERCEPT_SYNC_F(dispatch_sync_f)
-DISPATCH_INTERCEPT_SYNC_F(dispatch_barrier_sync_f)
+DISPATCH_INTERCEPT_B(dispatch_async, false)
+DISPATCH_INTERCEPT_B(dispatch_barrier_async, true)
+DISPATCH_INTERCEPT_F(dispatch_async_f, false)
+DISPATCH_INTERCEPT_F(dispatch_barrier_async_f, true)
+DISPATCH_INTERCEPT_SYNC_B(dispatch_sync, false)
+DISPATCH_INTERCEPT_SYNC_B(dispatch_barrier_sync, true)
+DISPATCH_INTERCEPT_SYNC_F(dispatch_sync_f, false)
+DISPATCH_INTERCEPT_SYNC_F(dispatch_barrier_sync_f, true)
 
 TSAN_INTERCEPTOR(void, dispatch_after, dispatch_time_t when,
                  dispatch_queue_t queue, dispatch_block_t block) {
   SCOPED_TSAN_INTERCEPTOR(dispatch_after, when, queue, block);
   SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_START();
   dispatch_block_t heap_block = Block_copy(block);
   SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_END();
   tsan_block_context_t *new_context =

 TSAN_INTERCEPTOR(void, dispatch_group_notify, dispatch_group_t group,
                  dispatch_queue_t q, dispatch_block_t block) {
   SCOPED_TSAN_INTERCEPTOR(dispatch_group_notify, group, q, block);
   SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_START();
   dispatch_block_t heap_block = Block_copy(block);
   SCOPED_TSAN_INTERCEPTOR_USER_CALLBACK_END();
   tsan_block_context_t *new_context =
       AllocContext(thr, pc, q, heap_block, &invoke_and_release_block);
-  new_context->sync_object = (uptr)group;
-
-  // Will be released in dispatch_callback_wrap.
-  new_context->object_to_release = group;
-  dispatch_retain(group);
-
-  Release(thr, pc, (uptr)group);
+  new_context->is_barrier_block = true;
+  Release(thr, pc, (uptr)q);
   REAL(dispatch_group_notify_f)(group, q, new_context,
                                 dispatch_callback_wrap);
 }
 
 TSAN_INTERCEPTOR(void, dispatch_group_notify_f, dispatch_group_t group,
                  dispatch_queue_t q, void *context, dispatch_function_t work) {
   SCOPED_TSAN_INTERCEPTOR(dispatch_group_notify_f, group, q, context, work);
   tsan_block_context_t *new_context = AllocContext(thr, pc, q, context, work);
-  new_context->sync_object = (uptr)group;
-
-  // Will be released in dispatch_callback_wrap.
-  new_context->object_to_release = group;
-  dispatch_retain(group);
-
-  Release(thr, pc, (uptr)group);
+  new_context->is_barrier_block = true;
+  Release(thr, pc, (uptr)q);
   REAL(dispatch_group_notify_f)(group, q, new_context,
                                 dispatch_callback_wrap);
 }
 
 TSAN_INTERCEPTOR(void, dispatch_source_set_event_handler,
                  dispatch_source_t source, dispatch_block_t handler) {
   SCOPED_TSAN_INTERCEPTOR(dispatch_source_set_event_handler, source, handler);
   if (handler == nullptr)

test/tsan/Darwin/gcd-barrier-race.mm

+// RUN: %clang_tsan %s -o %t -framework Foundation
+// RUN: %env_tsan_opts=ignore_interceptors_accesses=1 %deflake %run %t 2>&1 | FileCheck %s
+
+#import <Foundation/Foundation.h>
+
+#import "../test.h"
+
+long global;
+
+int main() {
+  fprintf(stderr, "Hello world.\n");
+  print_address("addr=", 1, &global);
+  barrier_init(&barrier, 2);
+
+  dispatch_queue_t q = dispatch_queue_create("my.queue", DISPATCH_QUEUE_CONCURRENT);
+  dispatch_queue_t bgq = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
+
+  dispatch_barrier_sync(q, ^{
+    global = 42;
+  });
+
+  dispatch_async(bgq, ^{
+    dispatch_sync(q, ^{
+      global = 43;
+      barrier_wait(&barrier);
+    });
+  });
+
+  dispatch_async(bgq, ^{
+    dispatch_sync(q, ^{
+      barrier_wait(&barrier);
+      global = 44;
+
+      dispatch_sync(dispatch_get_main_queue(), ^{
+        CFRunLoopStop(CFRunLoopGetCurrent());
+      });
+    });
+  });
+
+  CFRunLoopRun();
+  fprintf(stderr, "Done.\n");
+}
+
+// CHECK: Hello world.
+// CHECK: addr=[[ADDR:0x[0-9,a-f]+]]
+// CHECK: WARNING: ThreadSanitizer: data race
+// CHECK: Location is global 'global' {{(of size 8 )?}}at [[ADDR]] (gcd-barrier-race.mm.tmp+0x{{[0-9,a-f]+}})
+// CHECK: Done.

test/tsan/Darwin/gcd-barrier.mm

+// RUN: %clang_tsan %s -o %t -framework Foundation
+// RUN: %env_tsan_opts=ignore_interceptors_accesses=1 %run %t 2>&1 | FileCheck %s
+
+#import <Foundation/Foundation.h>
+
+#import "../test.h"
+
+long global;
+
+int main() {
+  fprintf(stderr, "Hello world.\n");
+  print_address("addr=", 1, &global);
+  barrier_init(&barrier, 2);
+
+  dispatch_queue_t q = dispatch_queue_create("my.queue", DISPATCH_QUEUE_CONCURRENT);
+  dispatch_queue_t bgq = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
+
+  dispatch_async(bgq, ^{
+    dispatch_sync(q, ^{
+      global = 42;
+    });
+    barrier_wait(&barrier);
+  });
+
+  dispatch_async(bgq, ^{
+    barrier_wait(&barrier);
+    dispatch_barrier_sync(q, ^{
+      global = 43;
+    });
+
+    dispatch_async(bgq, ^{
+      barrier_wait(&barrier);
+      global = 44;
+    });
+
+    barrier_wait(&barrier);
+    
+    dispatch_sync(dispatch_get_main_queue(), ^{
+      CFRunLoopStop(CFRunLoopGetCurrent());
+    });
+  });
+
+  CFRunLoopRun();
+  fprintf(stderr, "Done.\n");
+}
+
+// CHECK: Hello world.
+// CHECK: Done.
+// CHECK-NOT: WARNING: ThreadSanitizer