Merge remote-tracking branch 'origin/wip/tsan/all'

9 files changed, 186 insertions, 35 deletions

diff --git a/includes/Rts.h b/includes/Rts.h
index 5768e0eb7d..1e5a60262b 100644
--- a/includes/Rts.h
+++ b/includes/Rts.h
@@ -193,6 +193,7 @@ void _assertFail(const char *filename, unsigned int linenum)
 
 /* Parallel information */
 #include "rts/OSThreads.h"
+#include "rts/TSANUtils.h"
 #include "rts/SpinLock.h"
 
 #include "rts/Messages.h"
diff --git a/includes/rts/OSThreads.h b/includes/rts/OSThreads.h
index a68f1ea140..21b92950b2 100644
--- a/includes/rts/OSThreads.h
+++ b/includes/rts/OSThreads.h
@@ -164,7 +164,8 @@ typedef void* OSThreadProcAttr OSThreadProc(void *);
 extern int  createOSThread        ( OSThreadId* tid, char *name,
                                     OSThreadProc *startProc, void *param);
 extern bool osThreadIsAlive       ( OSThreadId id );
-extern void interruptOSThread     (OSThreadId id);
+extern void interruptOSThread     ( OSThreadId id );
+extern void joinOSThread          ( OSThreadId id );
 
 //
 // Condition Variables
diff --git a/includes/rts/SpinLock.h b/includes/rts/SpinLock.h
index 9f09099e2e..c1fe6c866c 100644
--- a/includes/rts/SpinLock.h
+++ b/includes/rts/SpinLock.h
@@ -39,35 +39,28 @@ typedef struct SpinLock_
 #define IF_PROF_SPIN(x)
 #endif
 
+void acquire_spin_lock_slow_path(SpinLock * p);
+
 // acquire spin lock
 INLINE_HEADER void ACQUIRE_SPIN_LOCK(SpinLock * p)
 {
-    do {
-        for (uint32_t i = 0; i < SPIN_COUNT; i++) {
-            StgWord32 r = cas((StgVolatilePtr)&(p->lock), 1, 0);
-            if (r != 0) return;
-            IF_PROF_SPIN(p->spin++);
-            busy_wait_nop();
-        }
-        IF_PROF_SPIN(p->yield++);
-        yieldThread();
-    } while (1);
+    StgWord32 r = cas((StgVolatilePtr)&(p->lock), 1, 0);
+    if (RTS_UNLIKELY(r == 0))
+        acquire_spin_lock_slow_path(p);
 }
 
 // release spin lock
 INLINE_HEADER void RELEASE_SPIN_LOCK(SpinLock * p)
 {
-    write_barrier();
-    p->lock = 1;
+    RELEASE_STORE(&p->lock, 1);
 }
 
 // initialise spin lock
 INLINE_HEADER void initSpinLock(SpinLock * p)
 {
-    write_barrier();
-    p->lock = 1;
     IF_PROF_SPIN(p->spin = 0);
     IF_PROF_SPIN(p->yield = 0);
+    RELEASE_STORE(&p->lock, 1);
 }
 
 #else /* !THREADED_RTS */
diff --git a/includes/rts/StablePtr.h b/includes/rts/StablePtr.h
index f42c353d2b..56113b9f81 100644
--- a/includes/rts/StablePtr.h
+++ b/includes/rts/StablePtr.h
@@ -31,5 +31,9 @@ extern DLL_IMPORT_RTS spEntry *stable_ptr_table;
 EXTERN_INLINE
 StgPtr deRefStablePtr(StgStablePtr sp)
 {
-    return stable_ptr_table[(StgWord)sp].addr;
+    // acquire load to ensure that we see the new SPT if it has been recently
+    // enlarged.
+    const spEntry *spt = ACQUIRE_LOAD(&stable_ptr_table);
+    // acquire load to ensure that the referenced object is visible.
+    return ACQUIRE_LOAD(&spt[(StgWord)sp].addr);
 }
diff --git a/includes/rts/TSANUtils.h b/includes/rts/TSANUtils.h
new file mode 100644
index 0000000000..72f4541a89
--- /dev/null
+++ b/includes/rts/TSANUtils.h
@@ -0,0 +1,67 @@
+/* ----------------------------------------------------------------------------
+ *
+ * (c) The GHC Team, 2006-2019
+ *
+ * Utilities for annotating "safe" data races for Thread Sanitizer
+ * -------------------------------------------------------------------------- */
+
+/*
+ * Note [ThreadSanitizer]
+ * ~~~~~~~~~~~~~~~~~~~~~~~
+ * ThreadSanitizer (abbreviated TSAN) is a library and set of compiler
+ * instrumentation (supported by both GCC and Clang) for checking C/C++ code
+ * for data races.
+ *
+ * In GHC we use it to check the runtime system implementation (but not yet
+ * generated code). TSAN requires that the checked program uses C++11-style
+ * atomics for all potentially-racing accesses. Note that we use the __atomic_*
+ * builtin operations but not the C11 _Atomic types to maintain compatibility
+ * with older compilers.
+ *
+ * In addition to the atomic operations themselves, TSAN provides a variety of
+ * annotation operations which can be used to annotate cases where the
+ * intended semantics are either ambiguous or intentionally racy (known as a
+ * *benign race*).
+ *
+ * Finally, there are a few benign races which we can't easily annotate. To
+ * silence these errors we have a suppressions file in rts/.tsan-suppressions.
+ * In general it's best to add suppressions only as a last resort, when the
+ * more precise annotation functions prove to be insufficient.
+ *
+ * Users guide: https://github.com/google/sanitizers/wiki/ThreadSanitizerCppManual
+ */
+
+#if defined(__SANITIZE_THREAD__)
+#define TSAN_ENABLED
+#elif defined(__has_feature)
+#if __has_feature(thread_sanitizer)
+#define TSAN_ENABLED
+#endif
+#endif
+
+#if defined(TSAN_ENABLED)
+#if !defined(HAVE_C11_ATOMICS)
+#error TSAN cannot be enabled without C11 atomics suppoort.
+#endif
+
+#define TSAN_ANNOTATE_HAPPENS_BEFORE(addr)                              \
+    AnnotateHappensBefore(__FILE__, __LINE__, (void*)(addr))
+#define TSAN_ANNOTATE_HAPPENS_AFTER(addr)                               \
+    AnnotateHappensAfter(__FILE__, __LINE__, (void*)(addr))
+#define TSAN_ANNOTATE_BENIGN_RACE_SIZED(addr,size,desc)                 \
+    AnnotateBenignRaceSized(__FILE__, __LINE__, (void*)(addr), size, desc)
+void AnnotateHappensBefore(const char* f, int l, void* addr);
+void AnnotateHappensAfter(const char* f, int l, void* addr);
+void AnnotateBenignRaceSized(const char *file,
+                             int line,
+                             const volatile void *mem,
+                             long size,
+                             const char *description);
+#else
+#define TSAN_ANNOTATE_HAPPENS_BEFORE(addr)
+#define TSAN_ANNOTATE_HAPPENS_AFTER(addr)
+#define TSAN_ANNOTATE_BENIGN_RACE_SIZED(addr,size,desc)
+#endif
+
+#define TSAN_ANNOTATE_BENIGN_RACE(addr,desc)                            \
+    TSAN_ANNOTATE_BENIGN_RACE_SIZED((void*)(addr), sizeof(*addr), desc)
diff --git a/includes/rts/storage/ClosureMacros.h b/includes/rts/storage/ClosureMacros.h
index 0e956c4fa3..5674322bd2 100644
--- a/includes/rts/storage/ClosureMacros.h
+++ b/includes/rts/storage/ClosureMacros.h
@@ -46,10 +46,13 @@
    -------------------------------------------------------------------------- */
 
 INLINE_HEADER void SET_INFO(StgClosure *c, const StgInfoTable *info) {
-    c->header.info = info;
+    RELAXED_STORE(&c->header.info, info);
+}
+INLINE_HEADER void SET_INFO_RELEASE(StgClosure *c, const StgInfoTable *info) {
+    RELEASE_STORE(&c->header.info, info);
 }
 INLINE_HEADER const StgInfoTable *GET_INFO(StgClosure *c) {
-    return c->header.info;
+    return RELAXED_LOAD(&c->header.info);
 }
 
 #if defined(TABLES_NEXT_TO_CODE)
@@ -81,28 +84,28 @@ INLINE_HEADER StgConInfoTable *itbl_to_con_itbl(const StgInfoTable *i) {return (
 EXTERN_INLINE const StgInfoTable *get_itbl(const StgClosure *c);
 EXTERN_INLINE const StgInfoTable *get_itbl(const StgClosure *c)
 {
-   return INFO_PTR_TO_STRUCT(c->header.info);
+    return INFO_PTR_TO_STRUCT(RELAXED_LOAD(&c->header.info));
 }
 
 EXTERN_INLINE const StgRetInfoTable *get_ret_itbl(const StgClosure *c);
 EXTERN_INLINE const StgRetInfoTable *get_ret_itbl(const StgClosure *c)
 {
-   return RET_INFO_PTR_TO_STRUCT(c->header.info);
+    return RET_INFO_PTR_TO_STRUCT(RELAXED_LOAD(&c->header.info));
 }
 
 INLINE_HEADER const StgFunInfoTable *get_fun_itbl(const StgClosure *c)
 {
-   return FUN_INFO_PTR_TO_STRUCT(c->header.info);
+    return FUN_INFO_PTR_TO_STRUCT(RELAXED_LOAD(&c->header.info));
 }
 
 INLINE_HEADER const StgThunkInfoTable *get_thunk_itbl(const StgClosure *c)
 {
-   return THUNK_INFO_PTR_TO_STRUCT(c->header.info);
+    return THUNK_INFO_PTR_TO_STRUCT(RELAXED_LOAD(&c->header.info));
 }
 
 INLINE_HEADER const StgConInfoTable *get_con_itbl(const StgClosure *c)
 {
-   return CON_INFO_PTR_TO_STRUCT((c)->header.info);
+    return CON_INFO_PTR_TO_STRUCT(RELAXED_LOAD(&c->header.info));
 }
 
 INLINE_HEADER StgHalfWord GET_TAG(const StgClosure *con)
@@ -137,13 +140,19 @@ INLINE_HEADER StgHalfWord GET_TAG(const StgClosure *con)
 
 #define SET_HDR(c,_info,ccs)                            \
    {                                                    \
-        (c)->header.info = _info;                       \
         SET_PROF_HDR((StgClosure *)(c),ccs);            \
+        RELAXED_STORE(&(c)->header.info, _info);        \
+   }
+
+#define SET_HDR_RELEASE(c,_info,ccs)                    \
+   {                                                    \
+        SET_PROF_HDR((StgClosure *)(c),ccs);            \
+        RELEASE_STORE(&(c)->header.info, _info);        \
    }
 
 #define SET_ARR_HDR(c,info,costCentreStack,n_bytes)     \
-   SET_HDR(c,info,costCentreStack);                     \
-   (c)->bytes = n_bytes;
+   (c)->bytes = n_bytes;                                \
+   SET_HDR(c,info,costCentreStack);
 
 // Use when changing a closure from one kind to another
 #define OVERWRITE_INFO(c, new_info)                             \
@@ -251,8 +260,8 @@ INLINE_HEADER bool LOOKS_LIKE_INFO_PTR (StgWord p)
 
 INLINE_HEADER bool LOOKS_LIKE_CLOSURE_PTR (const void *p)
 {
-    return LOOKS_LIKE_INFO_PTR((StgWord)
-            (UNTAG_CONST_CLOSURE((const StgClosure *)(p)))->header.info);
+    const StgInfoTable *info = RELAXED_LOAD(&UNTAG_CONST_CLOSURE((const StgClosure *) (p))->header.info);
+    return LOOKS_LIKE_INFO_PTR((StgWord) info);
 }
 
 /* -----------------------------------------------------------------------------
diff --git a/includes/rts/storage/Closures.h b/includes/rts/storage/Closures.h
index 3196efd3de..981e162ec1 100644
--- a/includes/rts/storage/Closures.h
+++ b/includes/rts/storage/Closures.h
@@ -340,9 +340,9 @@ typedef struct StgTVarWatchQueue_ {
 
 typedef struct {
   StgHeader                  header;
-  StgClosure                *volatile current_value;
-  StgTVarWatchQueue         *volatile first_watch_queue_entry;
-  StgInt                     volatile num_updates;
+  StgClosure                *current_value; /* accessed via atomics */
+  StgTVarWatchQueue         *first_watch_queue_entry; /* accessed via atomics */
+  StgInt                     num_updates; /* accessed via atomics */
 } StgTVar;
 
 /* new_value == expected_value for read-only accesses */
diff --git a/includes/rts/storage/GC.h b/includes/rts/storage/GC.h
index 9f4a0dde07..e8dc05048a 100644
--- a/includes/rts/storage/GC.h
+++ b/includes/rts/storage/GC.h
@@ -247,9 +247,9 @@ extern bool keepCAFs;
 
 INLINE_HEADER void initBdescr(bdescr *bd, generation *gen, generation *dest)
 {
-    bd->gen     = gen;
-    bd->gen_no  = gen->no;
-    bd->dest_no = dest->no;
+    RELAXED_STORE(&bd->gen, gen);
+    RELAXED_STORE(&bd->gen_no, gen->no);
+    RELAXED_STORE(&bd->dest_no, dest->no);
 
 #if !IN_STG_CODE
     /* See Note [RtsFlags is a pointer in STG code] */
diff --git a/includes/stg/SMP.h b/includes/stg/SMP.h
index cb9660c591..389dd95c88 100644
--- a/includes/stg/SMP.h
+++ b/includes/stg/SMP.h
@@ -81,7 +81,7 @@ EXTERN_INLINE void busy_wait_nop(void);
 
 /*
  * Various kinds of memory barrier.
- *  write_barrier: prevents future stores occurring before prededing stores.
+ *  write_barrier: prevents future stores occurring before preceding stores.
  *  store_load_barrier: prevents future loads occurring before preceding stores.
  *  load_load_barrier: prevents future loads occurring before earlier loads.
  *
@@ -257,6 +257,9 @@ EXTERN_INLINE void load_load_barrier(void);
 EXTERN_INLINE StgWord
 xchg(StgPtr p, StgWord w)
 {
+#if defined(HAVE_C11_ATOMICS)
+    return __atomic_exchange_n(p, w, __ATOMIC_SEQ_CST);
+#else
     // When porting GHC to a new platform check that
     // __sync_lock_test_and_set() actually stores w in *p.
     // Use test rts/atomicxchg to verify that the correct value is stored.
@@ -272,6 +275,7 @@ xchg(StgPtr p, StgWord w)
     // only valid value to store is the immediate constant 1. The
     // exact value actually stored in *ptr is implementation defined.
     return __sync_lock_test_and_set(p, w);
+#endif
 }
 
 /*
@@ -281,13 +285,23 @@ xchg(StgPtr p, StgWord w)
 EXTERN_INLINE StgWord
 cas(StgVolatilePtr p, StgWord o, StgWord n)
 {
+#if defined(HAVE_C11_ATOMICS)
+    __atomic_compare_exchange_n(p, &o, n, 0, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST);
+    return o;
+#else
     return __sync_val_compare_and_swap(p, o, n);
+#endif
 }
 
 EXTERN_INLINE StgWord8
 cas_word8(StgWord8 *volatile p, StgWord8 o, StgWord8 n)
 {
+#if defined(HAVE_C11_ATOMICS)
+    __atomic_compare_exchange_n(p, &o, n, 0, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST);
+    return o;
+#else
     return __sync_val_compare_and_swap(p, o, n);
+#endif
 }
 
 // RRN: Generalized to arbitrary increments to enable fetch-and-add in
@@ -296,13 +310,21 @@ cas_word8(StgWord8 *volatile p, StgWord8 o, StgWord8 n)
 EXTERN_INLINE StgWord
 atomic_inc(StgVolatilePtr p, StgWord incr)
 {
+#if defined(HAVE_C11_ATOMICS)
+    return __atomic_add_fetch(p, incr, __ATOMIC_SEQ_CST);
+#else
     return __sync_add_and_fetch(p, incr);
+#endif
 }
 
 EXTERN_INLINE StgWord
 atomic_dec(StgVolatilePtr p)
 {
+#if defined(HAVE_C11_ATOMICS)
+    return __atomic_sub_fetch(p, 1, __ATOMIC_SEQ_CST);
+#else
     return __sync_sub_and_fetch(p, (StgWord) 1);
+#endif
 }
 
 /*
@@ -338,6 +360,11 @@ EXTERN_INLINE void
 write_barrier(void) {
 #if defined(NOSMP)
     return;
+#elif defined(TSAN_ENABLED)
+    // RELEASE is a bit stronger than the store-store barrier provided by
+    // write_barrier, consequently we only use this case as a conservative
+    // approximation when using ThreadSanitizer. See Note [ThreadSanitizer].
+    __atomic_thread_fence(__ATOMIC_RELEASE);
 #elif defined(i386_HOST_ARCH) || defined(x86_64_HOST_ARCH)
     __asm__ __volatile__ ("" : : : "memory");
 #elif defined(powerpc_HOST_ARCH) || defined(powerpc64_HOST_ARCH) \
@@ -410,6 +437,31 @@ load_load_barrier(void) {
 // a busy wait loop for example.
 #define VOLATILE_LOAD(p) (*((StgVolatilePtr)(p)))
 
+// Relaxed atomic operations.
+#define RELAXED_LOAD(ptr) __atomic_load_n(ptr, __ATOMIC_RELAXED)
+#define RELAXED_STORE(ptr,val) __atomic_store_n(ptr, val, __ATOMIC_RELAXED)
+#define RELAXED_ADD(ptr,val) __atomic_add_fetch(ptr, val, __ATOMIC_RELAXED)
+
+// Acquire/release atomic operations
+#define ACQUIRE_LOAD(ptr) __atomic_load_n(ptr, __ATOMIC_ACQUIRE)
+#define RELEASE_STORE(ptr,val) __atomic_store_n(ptr, val, __ATOMIC_RELEASE)
+
+// Sequentially consistent atomic operations
+#define SEQ_CST_LOAD(ptr) __atomic_load_n(ptr, __ATOMIC_SEQ_CST)
+#define SEQ_CST_STORE(ptr,val) __atomic_store_n(ptr, val, __ATOMIC_SEQ_CST)
+#define SEQ_CST_ADD(ptr,val) __atomic_add_fetch(ptr, val, __ATOMIC_SEQ_CST)
+
+// Non-atomic addition for "approximate" counters that can be lossy
+#define NONATOMIC_ADD(ptr,val) RELAXED_STORE(ptr, RELAXED_LOAD(ptr) + val)
+
+// Explicit fences
+//
+// These are typically necessary only in very specific cases (e.g. WSDeque)
+// where the ordered operations aren't expressive enough to capture the desired
+// ordering.
+#define RELEASE_FENCE() __atomic_thread_fence(__ATOMIC_RELEASE)
+#define SEQ_CST_FENCE() __atomic_thread_fence(__ATOMIC_SEQ_CST)
+
 /* ---------------------------------------------------------------------- */
 #else /* !THREADED_RTS */
 
@@ -420,6 +472,27 @@ EXTERN_INLINE void write_barrier     () {} /* nothing */
 EXTERN_INLINE void store_load_barrier() {} /* nothing */
 EXTERN_INLINE void load_load_barrier () {} /* nothing */
 
+// Relaxed atomic operations
+#define RELAXED_LOAD(ptr) *ptr
+#define RELAXED_STORE(ptr,val) *ptr = val
+#define RELAXED_ADD(ptr,val) *ptr += val
+
+// Acquire/release atomic operations
+#define ACQUIRE_LOAD(ptr) *ptr
+#define RELEASE_STORE(ptr,val) *ptr = val
+
+// Sequentially consistent atomic operations
+#define SEQ_CST_LOAD(ptr) *ptr
+#define SEQ_CST_STORE(ptr,val) *ptr = val
+#define SEQ_CST_ADD(ptr,val) *ptr += val
+
+// Non-atomic addition for "approximate" counters that can be lossy
+#define NONATOMIC_ADD(ptr,val) *ptr += val
+
+// Fences
+#define RELEASE_FENCE()
+#define SEQ_CST_FENCE()
+
 #if !IN_STG_CODE || IN_STGCRUN
 INLINE_HEADER StgWord
 xchg(StgPtr p, StgWord w)
@@ -468,6 +541,9 @@ atomic_dec(StgVolatilePtr p)
 }
 #endif
 
+/* An alias for the C11 declspec */
+#define ATOMIC
+
 #define VOLATILE_LOAD(p) ((StgWord)*((StgWord*)(p)))
 
 #endif /* !THREADED_RTS */