[tsan] Add support for OS X OSAtomic* functions

[kubamracek]

Summary

OS X provides atomic functions in libkern/OSAtomic.h. These provide atomic guarantees and they have alternatives which have barrier semantics. This patch adds proper TSan support for these functions (all from libkern/OSAtomic.h):

• OSAtomicAdd32
• OSAtomicAdd32Barrier
• OSAtomicAdd64
• OSAtomicAdd64Barrier
• OSAtomicAnd32
• OSAtomicAnd32Barrier
• OSAtomicAnd32Orig
• OSAtomicAnd32OrigBarrier
• OSAtomicCompareAndSwap32
• OSAtomicCompareAndSwap32Barrier
• OSAtomicCompareAndSwap64
• OSAtomicCompareAndSwap64Barrier
• OSAtomicCompareAndSwapInt
• OSAtomicCompareAndSwapIntBarrier
• OSAtomicCompareAndSwapLong
• OSAtomicCompareAndSwapLongBarrier
• OSAtomicCompareAndSwapPtr
• OSAtomicCompareAndSwapPtrBarrier
• OSAtomicDecrement32
• OSAtomicDecrement32Barrier
• OSAtomicDecrement64
• OSAtomicDecrement64Barrier
• OSAtomicDequeue
• OSAtomicEnqueue
• OSAtomicFifoDequeue
• OSAtomicFifoEnqueue
• OSAtomicIncrement32
• OSAtomicIncrement32Barrier
• OSAtomicIncrement64
• OSAtomicIncrement64Barrier
• OSAtomicOr32
• OSAtomicOr32Barrier
• OSAtomicOr32Orig
• OSAtomicOr32OrigBarrier
• OSAtomicTestAndClear
• OSAtomicTestAndClearBarrier
• OSAtomicTestAndSet
• OSAtomicTestAndSetBarrier
• OSAtomicXor32
• OSAtomicXor32Barrier
• OSAtomicXor32Orig
• OSAtomicXor32OrigBarrier

[kubamracek]

Updating patch, OSAtomicFifoEnqueue and OSAtomicFifoDequeue are only available on OS X.

[kubamracek]

Updating patch to use "tsan_interface.h" instead of the system clang's <sanitizer/tsan_interface_atomic.h>. Relies on http://reviews.llvm.org/D18543.

[dvyukov]

lib/tsan/rtl/tsan_interceptors_mac.cc

121

This is not correct. If you separate the operation itself and the memory barrier, release barrier needs to precede the operation itself (while acquire barrier needs to follow the operation itself). If you split this into acquire+operation+release, it will increase cost of the operation significantly, as we will lock sync mutex twice and process vector clock twice.
I would suggest to use __tsan_atomic8_fetch_or/and to implement these bit flag operations. For NoBarrier versions you can pass mo_relaxed and it should be as cheap as calling the REAL function.

135

same here

143

Release must precede the operation. Also I would use __tsan_release(item).
If you do it after, then consumer can dequeue the item and do acquire before we do release. This will lead to false positives.

149

__tsan_acquire(item)

160

__tsan_release(item) before the operation.

167

__tsan_acquire(item)

[kubamracek]

Addressing review comments.

lib/tsan/rtl/tsan_interceptors_mac.cc

 
 #include "sanitizer_common/sanitizer_platform.h"
 #if SANITIZER_MAC
 
 #include "interception/interception.h"
 #include "tsan_interceptors.h"
 
 #include <libkern/OSAtomic.h>
+#include <sanitizer/tsan_interface_atomic.h>
+
+typedef long long_t;  // NOLINT
 
 namespace __tsan {
 
+#define OSATOMIC_INTERCEPTOR(return_t, t, tsan_t, f, tsan_atomic_f, mo) \
+  TSAN_INTERCEPTOR(return_t, f, t x, volatile t *ptr) {                 \
+    SCOPED_TSAN_INTERCEPTOR(f, x, ptr);                                 \
+    return tsan_atomic_f((volatile tsan_t *)ptr, x, mo);                \
+  }
+
+#define OSATOMIC_INTERCEPTOR_PLUS_X(return_t, t, tsan_t, f, tsan_atomic_f, mo) \
+  TSAN_INTERCEPTOR(return_t, f, t x, volatile t *ptr) {                        \
+    SCOPED_TSAN_INTERCEPTOR(f, x, ptr);                                        \
+    return tsan_atomic_f((volatile tsan_t *)ptr, x, mo) + x;                   \
+  }
+
+#define OSATOMIC_INTERCEPTOR_PLUS_1(return_t, t, tsan_t, f, tsan_atomic_f, mo) \
+  TSAN_INTERCEPTOR(return_t, f, volatile t *ptr) {                             \
+    SCOPED_TSAN_INTERCEPTOR(f, ptr);                                           \
+    return tsan_atomic_f((volatile tsan_t *)ptr, 1, mo) + 1;                   \
+  }
+
+#define OSATOMIC_INTERCEPTOR_MINUS_1(return_t, t, tsan_t, f, tsan_atomic_f, \
+                                     mo)                                    \
+  TSAN_INTERCEPTOR(return_t, f, volatile t *ptr) {                          \
+    SCOPED_TSAN_INTERCEPTOR(f, ptr);                                        \
+    return tsan_atomic_f((volatile tsan_t *)ptr, 1, mo) - 1;                \
+  }
+
+#define OSATOMIC_INTERCEPTORS_ARITHMETIC(f, tsan_atomic_f, m)     \
+  m(int32_t, int32_t, __tsan_atomic32, f##32,                     \
+    __tsan_atomic32_##tsan_atomic_f, __tsan_memory_order_relaxed) \
+  m(int32_t, int32_t, __tsan_atomic32, f##32##Barrier,            \
+    __tsan_atomic32_##tsan_atomic_f, __tsan_memory_order_acq_rel) \
+  m(int64_t, int64_t, __tsan_atomic64, f##64,                     \
+    __tsan_atomic64_##tsan_atomic_f, __tsan_memory_order_relaxed) \
+  m(int64_t, int64_t, __tsan_atomic64, f##64##Barrier,            \
+    __tsan_atomic64_##tsan_atomic_f, __tsan_memory_order_acq_rel)
+
+#define OSATOMIC_INTERCEPTORS_BITWISE(f, tsan_atomic_f, m, m_orig) \
+  m(int32_t, uint32_t, __tsan_atomic32, f##32,                     \
+    __tsan_atomic32_##tsan_atomic_f, __tsan_memory_order_relaxed)  \
+  m(int32_t, uint32_t, __tsan_atomic32, f##32##Barrier,            \
+    __tsan_atomic32_##tsan_atomic_f, __tsan_memory_order_acq_rel)  \
+  m_orig(int32_t, uint32_t, __tsan_atomic32, f##32##Orig,          \
+     __tsan_atomic32_##tsan_atomic_f, __tsan_memory_order_relaxed) \
+  m_orig(int32_t, uint32_t, __tsan_atomic32, f##32##OrigBarrier,   \
+     __tsan_atomic32_##tsan_atomic_f, __tsan_memory_order_acq_rel)
+
+OSATOMIC_INTERCEPTORS_ARITHMETIC(OSAtomicAdd, fetch_add,
+                                 OSATOMIC_INTERCEPTOR_PLUS_X)
+OSATOMIC_INTERCEPTORS_ARITHMETIC(OSAtomicIncrement, fetch_add,
+                                 OSATOMIC_INTERCEPTOR_PLUS_1)
+OSATOMIC_INTERCEPTORS_ARITHMETIC(OSAtomicDecrement, fetch_sub,
+                                 OSATOMIC_INTERCEPTOR_MINUS_1)
+OSATOMIC_INTERCEPTORS_BITWISE(OSAtomicOr, fetch_or,
+                              OSATOMIC_INTERCEPTOR_PLUS_X, OSATOMIC_INTERCEPTOR)
+OSATOMIC_INTERCEPTORS_BITWISE(OSAtomicAnd, fetch_and,
+                              OSATOMIC_INTERCEPTOR_PLUS_X, OSATOMIC_INTERCEPTOR)
+OSATOMIC_INTERCEPTORS_BITWISE(OSAtomicXor, fetch_xor,
+                              OSATOMIC_INTERCEPTOR_PLUS_X, OSATOMIC_INTERCEPTOR)
+
+#define OSATOMIC_INTERCEPTORS_CAS(f, tsan_t, t)                          \
+  TSAN_INTERCEPTOR(bool, f, t old_value, t new_value, t volatile *ptr) { \
+    SCOPED_TSAN_INTERCEPTOR(f, old_value, new_value, ptr);               \
+    return tsan_t##_compare_exchange_strong(                             \
+        (tsan_t *)ptr, (tsan_t *)&old_value, (tsan_t)new_value,          \
+        __tsan_memory_order_relaxed, __tsan_memory_order_relaxed);       \
+  }                                                                      \
+                                                                         \
+  TSAN_INTERCEPTOR(bool, f##Barrier, t old_value, t new_value,           \
+                   t volatile *ptr) {                                    \
+    SCOPED_TSAN_INTERCEPTOR(f##Barrier, old_value, new_value, ptr);      \
+    return tsan_t##_compare_exchange_strong(                             \
+        (tsan_t *)ptr, (tsan_t *)&old_value, (tsan_t)new_value,          \
+        __tsan_memory_order_acq_rel, __tsan_memory_order_relaxed);       \
+  }
+
+OSATOMIC_INTERCEPTORS_CAS(OSAtomicCompareAndSwapInt, __tsan_atomic32, int)
+OSATOMIC_INTERCEPTORS_CAS(OSAtomicCompareAndSwapLong, __tsan_atomic64, long_t)
+OSATOMIC_INTERCEPTORS_CAS(OSAtomicCompareAndSwapPtr, __tsan_atomic64, void *)
+OSATOMIC_INTERCEPTORS_CAS(OSAtomicCompareAndSwap32, __tsan_atomic32, int32_t)
+OSATOMIC_INTERCEPTORS_CAS(OSAtomicCompareAndSwap64, __tsan_atomic64, int64_t)
+
+TSAN_INTERCEPTOR(bool, OSAtomicTestAndSet, uint32_t n, volatile void *ptr) {
+  SCOPED_TSAN_INTERCEPTOR(OSAtomicTestAndSet, n, ptr);
+  return REAL(OSAtomicTestAndSet)(n, ptr);
+}
+
+TSAN_INTERCEPTOR(bool, OSAtomicTestAndSetBarrier, uint32_t n,
+                 volatile void *ptr) {
+  SCOPED_TSAN_INTERCEPTOR(OSAtomicTestAndSetBarrier, n, ptr);
+  bool result = REAL(OSAtomicTestAndSetBarrier)(n, ptr);
+  char *byte_ptr = ((char *)ptr) + (n >> 3);
+  __tsan_atomic8_fetch_or(byte_ptr, 0, __tsan_memory_order_acq_rel);
+  return result;
+}
+
+TSAN_INTERCEPTOR(bool, OSAtomicTestAndClear, uint32_t n, volatile void *ptr) {
+  SCOPED_TSAN_INTERCEPTOR(OSAtomicTestAndClear, n, ptr);
+  return REAL(OSAtomicTestAndClear)(n, ptr);
+}
+
+TSAN_INTERCEPTOR(bool, OSAtomicTestAndClearBarrier, uint32_t n,
+                 volatile void *ptr) {
+  SCOPED_TSAN_INTERCEPTOR(OSAtomicTestAndClearBarrier, n, ptr);
+  bool result = REAL(OSAtomicTestAndClearBarrier)(n, ptr);
+  char *byte_ptr = ((char *)ptr) + (n >> 3);
+  __tsan_atomic8_fetch_or(byte_ptr, 0, __tsan_memory_order_acq_rel);
+  return result;
+}
+
+TSAN_INTERCEPTOR(void, OSAtomicEnqueue, OSQueueHead *list, void *item,
+                 size_t offset) {
+  SCOPED_TSAN_INTERCEPTOR(OSAtomicEnqueue, list, item, offset);
+  REAL(OSAtomicEnqueue)(list, item, offset);
+  __tsan_atomic64_fetch_or((volatile __tsan_atomic64 *)item, 0,
+                           __tsan_memory_order_release);
+}
+
+TSAN_INTERCEPTOR(void *, OSAtomicDequeue, OSQueueHead *list, size_t offset) {
+  SCOPED_TSAN_INTERCEPTOR(OSAtomicDequeue, list, offset);
+  void *item = REAL(OSAtomicDequeue)(list, offset);
+  if (item)
+    __tsan_atomic64_load((volatile __tsan_atomic64 *)item,
+                         __tsan_memory_order_acquire);
+  return item;
+}
+
+TSAN_INTERCEPTOR(void, OSAtomicFifoEnqueue, OSFifoQueueHead *list, void *item,
+                 size_t offset) {
+  SCOPED_TSAN_INTERCEPTOR(OSAtomicFifoEnqueue, list, item, offset);
+  REAL(OSAtomicFifoEnqueue)(list, item, offset);
+  __tsan_atomic64_fetch_or((volatile __tsan_atomic64 *)item, 0,
+                           __tsan_memory_order_release);
+}
+
+TSAN_INTERCEPTOR(void *, OSAtomicFifoDequeue, OSFifoQueueHead *list,
+                 size_t offset) {
+  SCOPED_TSAN_INTERCEPTOR(OSAtomicFifoDequeue, list, offset);
+  void *item = REAL(OSAtomicFifoDequeue)(list, offset);
+  if (item)
+    __tsan_atomic64_load((volatile __tsan_atomic64 *)item,
+                         __tsan_memory_order_acquire);
+  return item;
+}
+
 TSAN_INTERCEPTOR(void, OSSpinLockLock, volatile OSSpinLock *lock) {
   CHECK(!cur_thread()->is_dead);
   if (!cur_thread()->is_inited) {
     return REAL(OSSpinLockLock)(lock);
   }
   SCOPED_TSAN_INTERCEPTOR(OSSpinLockLock, lock);
   REAL(OSSpinLockLock)(lock);
   Acquire(thr, pc, (uptr)lock);

test/tsan/Darwin/osatomics-add.mm

+// RUN: %clang_tsan %s -o %t -framework Foundation -std=c++11
+// RUN: %run %t 2>&1 | FileCheck %s
+
+#import <Foundation/Foundation.h>
+#import <libkern/OSAtomic.h>
+
+#include <thread>
+
+volatile int64_t retainCount = 0;
+
+long g = 0;
+
+void dealloc() {
+  g = 42;
+}
+
+void release() {
+  if (OSAtomicAdd64Barrier(-1, &retainCount) == 0) {
+    dealloc();
+  }
+}
+
+void retain() {
+  OSAtomicAdd64Barrier(1, &retainCount);
+}
+
+int main(int argc, const char * argv[]) {
+  fprintf(stderr, "start\n");
+  retain();
+  retain();
+  
+  std::thread t([]{
+    release();
+  });
+
+  g = 47;
+
+  release();
+  t.join();
+
+  fprintf(stderr, "end, g = %ld\n", g);
+
+  return 0;
+}
+
+// CHECK: start
+// CHECK: end, g = 42
+// CHECK-NOT: WARNING: ThreadSanitizer

test/tsan/Darwin/osatomics-list.mm

+// RUN: %clang_tsan %s -o %t -framework Foundation -std=c++11
+// RUN: %run %t 2>&1 | FileCheck %s
+
+#import <Foundation/Foundation.h>
+#import <libkern/OSAtomic.h>
+
+#include <thread>
+
+#include "../test.h"
+
+typedef struct {
+  void *next;
+  long data;
+} ListItem;
+
+OSQueueHead q;
+
+int main(int argc, const char *argv[]) {
+  barrier_init(&barrier, 2);
+
+  std::thread t1([] {
+    ListItem *li = new ListItem{nullptr, 42};
+    OSAtomicEnqueue(&q, li, 0);
+    barrier_wait(&barrier);
+  });
+
+  std::thread t2([] {
+    barrier_wait(&barrier);
+    ListItem *li = (ListItem *)OSAtomicDequeue(&q, 0);
+    fprintf(stderr, "data = %ld\n", li->data);
+  });
+
+  t1.join();
+  t2.join();
+
+  fprintf(stderr, "done\n");
+
+  return 0;
+}
+
+// CHECK: data = 42
+// CHECK: done
+// CHECK-NOT: WARNING: ThreadSanitizer