[tsan] Add release+acquire semantics for serial dispatch queues

[kubamracek]

Summary

Serial queues need extra happens-before between individual tasks executed in the same queue. This patch adds Acquire(queue) before the executed task and Release(queue) just after it (for serial queues only). Added a test case.

[dvyukov]

lib/tsan/rtl/tsan_libdispatch_mac.cc

81

Do you mean that work items can be executed on different threads for serial queues? If so, add a comment here, because it is not completely obvious.

Also, please move Acquire call to a separate line.

86

same here

[kubamracek]

Do you mean that work items can be executed on different threads for serial queues? If so, add a comment here, because it is not completely obvious.

Updated patch.

Also, please move Acquire call to a separate line.

It's clang-format (Google style) doing this. Is there some extra setting I should be using? Should we add it to the .clang-format file we have in lib/tsan?

[dvyukov]

It's clang-format (Google style) doing this. Is there some extra setting I should be using? Should we add it to the .clang-format file we have in lib/tsan?

Ah, OK, I am more than happy with any automatic formatting. Please format it back. Sorry.
I've looked at other .clang-format files, they all are just "BasedOnStyle: Google". It does not make sense to have different rules for tsan.
At some point we need to reformat all tsan sources. I don't want to step on your work, so I can do it later, or you can do it now.

lib/tsan/rtl/tsan_libdispatch_mac.cc

 namespace __tsan {
 
 typedef struct {
   dispatch_queue_t queue;
   void *orig_context;
   dispatch_function_t orig_work;
 } 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;
+  const uint16_t dqo_flags;
+  const uint16_t dqo_flags_size;
+  const uint16_t dqo_serialnum;
+  const uint16_t dqo_serialnum_size;
+  const uint16_t dqo_width;
+  const uint16_t dqo_width_size;
+  const uint16_t dqo_running;
+  const uint16_t dqo_running_size;
+  const uint16_t dqo_suspend_cnt;
+  const uint16_t dqo_suspend_cnt_size;
+  const uint16_t dqo_target_queue;
+  const uint16_t dqo_target_queue_size;
+  const uint16_t dqo_priority;
+  const uint16_t dqo_priority_size;
+} dispatch_queue_offsets;
+
+static bool IsQueueSerial(dispatch_queue_t q) {
+  CHECK_EQ(dispatch_queue_offsets.dqo_width_size, 2);
+  uptr width = *(uint16_t *)(((uptr)q) + dispatch_queue_offsets.dqo_width);
+  CHECK_NE(width, 0);
+  return width == 1;
+}
+
 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);
+  // 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);
   context->orig_work(context->orig_context);
+  if (IsQueueSerial(context->queue))
+    Release(thr, pc, (uptr)context->queue);
   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);
 }

test/tsan/Darwin/gcd-serial-queue-norace.mm

+// RUN: %clang_tsan %s -o %t -framework Foundation
+// RUN: %run %t 2>&1
+
+#import <Foundation/Foundation.h>
+
+#import "../test.h"
+
+long global;
+
+int main() {
+  NSLog(@"Hello world.");
+  NSLog(@"addr=%p\n", &global);
+
+  dispatch_queue_t q1 = dispatch_queue_create("my.queue1", DISPATCH_QUEUE_CONCURRENT);
+  dispatch_queue_t q2 = dispatch_queue_create("my.queue2", DISPATCH_QUEUE_SERIAL);
+
+  global = 42;
+  for (int i = 0; i < 10; i++) {
+    dispatch_async(q1, ^{
+      for (int i = 0; i < 100; i++) {
+        dispatch_sync(q2, ^{
+          global++;
+        });
+      }
+    });
+  }
+
+  dispatch_barrier_async(q1, ^{
+    dispatch_sync(dispatch_get_main_queue(), ^{
+      CFRunLoopStop(CFRunLoopGetCurrent());
+    });
+  });
+
+  CFRunLoopRun();
+  NSLog(@"Done.");
+}
+
+// CHECK: Hello world.
+// CHECK: Done.
+// CHECK-NOT: WARNING: ThreadSanitizer