Introduce a backport of C11 atomics

This introduces a backport of C11 atomics.  It has four implementations; ranked
in order of preference, they are:
- GCC/Clang __atomic builtins
- GCC/Clang __sync builtins
- MSVC _Interlocked builtins
- C11 atomics, from <stdatomic.h>

The primary advantages are:
- Close adherence to the standard API gives us a defined memory model.
- Type safety: atomic objects are now separate types from non-atomic ones, so
  that it's impossible to mix up atomic and non-atomic updates (which is
  undefined behavior that compilers are starting to take advantage of).
- Efficiency: we can specify ordering for operations, avoiding fences and
  atomic operations on strongly ordered architectures (example:
  `atomic_write_u32(ptr, val);` involves a CAS loop, whereas
  `atomic_store(ptr, val, ATOMIC_RELEASE);` is a plain store.

This diff leaves in the current atomics API (implementing them in terms of the
backport).  This lets us transition uses over piecemeal.

Testing:
This is by nature hard to test. I've manually tested the first three options on
Linux on gcc by futzing with the #defines manually, on freebsd with gcc and
clang, on MSVC, and on OS X with clang.  All of these were x86 machines though,
and we don't have any test infrastructure set up for non-x86 platforms.

1 files changed, 227 insertions, 71 deletions

diff --git a/test/unit/atomic.c b/test/unit/atomic.c
index 7866159..237c747 100644
--- a/test/unit/atomic.c
+++ b/test/unit/atomic.c
@@ -1,101 +1,257 @@
 #include "test/jemalloc_test.h"
 
-#define TEST_STRUCT(p, t)						\
-struct p##_test_s {							\
-	t	accum0;							\
-	t	x;							\
-	t	s;							\
-};									\
-typedef struct p##_test_s p##_test_t;
+/*
+ * We *almost* have consistent short names (e.g. "u32" for uint32_t, "b" for
+ * bool, etc.  The one exception is that the short name for void * is "p" in
+ * some places and "ptr" in others.  In the long run it would be nice to unify
+ * these, but in the short run we'll use this shim.
+ */
+#define assert_p_eq assert_ptr_eq
 
-#define TEST_BODY(p, t, tc, ta, FMT) do {				\
-	const p##_test_t tests[] = {					\
-		{(t)-1, (t)-1, (t)-2},					\
-		{(t)-1, (t) 0, (t)-2},					\
-		{(t)-1, (t) 1, (t)-2},					\
-									\
-		{(t) 0, (t)-1, (t)-2},					\
-		{(t) 0, (t) 0, (t)-2},					\
-		{(t) 0, (t) 1, (t)-2},					\
-									\
-		{(t) 1, (t)-1, (t)-2},					\
-		{(t) 1, (t) 0, (t)-2},					\
-		{(t) 1, (t) 1, (t)-2},					\
-									\
-		{(t)0, (t)-(1 << 22), (t)-2},				\
-		{(t)0, (t)(1 << 22), (t)-2},				\
-		{(t)(1 << 22), (t)-(1 << 22), (t)-2},			\
-		{(t)(1 << 22), (t)(1 << 22), (t)-2}			\
-	};								\
-	unsigned i;							\
-									\
-	for (i = 0; i < sizeof(tests)/sizeof(p##_test_t); i++) {	\
-		bool err;						\
-		t accum = tests[i].accum0;				\
-		assert_##ta##_eq(atomic_read_##p(&accum),		\
-		    tests[i].accum0,					\
-		    "Erroneous read, i=%u", i);				\
-									\
-		assert_##ta##_eq(atomic_add_##p(&accum, tests[i].x),	\
-		    (t)((tc)tests[i].accum0 + (tc)tests[i].x),		\
-		    "i=%u, accum=%"FMT", x=%"FMT,			\
-		    i, tests[i].accum0, tests[i].x);			\
-		assert_##ta##_eq(atomic_read_##p(&accum), accum,	\
-		    "Erroneous add, i=%u", i);				\
-									\
-		accum = tests[i].accum0;				\
-		assert_##ta##_eq(atomic_sub_##p(&accum, tests[i].x),	\
-		    (t)((tc)tests[i].accum0 - (tc)tests[i].x),		\
-		    "i=%u, accum=%"FMT", x=%"FMT,			\
-		    i, tests[i].accum0, tests[i].x);			\
-		assert_##ta##_eq(atomic_read_##p(&accum), accum,	\
-		    "Erroneous sub, i=%u", i);				\
-									\
-		accum = tests[i].accum0;				\
-		err = atomic_cas_##p(&accum, tests[i].x, tests[i].s);	\
-		assert_b_eq(err, tests[i].accum0 != tests[i].x,		\
-		    "Erroneous cas success/failure result");		\
-		assert_##ta##_eq(accum, err ? tests[i].accum0 :		\
-		    tests[i].s, "Erroneous cas effect, i=%u", i);	\
-									\
-		accum = tests[i].accum0;				\
-		atomic_write_##p(&accum, tests[i].s);			\
-		assert_##ta##_eq(accum, tests[i].s,			\
-		    "Erroneous write, i=%u", i);			\
+/*
+ * t: the non-atomic type, like "uint32_t".
+ * ta: the short name for the type, like "u32".
+ * val[1,2,3]: Values of the given type.  The CAS tests use val2 for expected,
+ * and val3 for desired.
+ */
+
+#define DO_TESTS(t, ta, val1, val2, val3) do {				\
+	t val;								\
+	t raw_atomic;							\
+	t expected;							\
+	bool success;							\
+	/* This (along with the load below) also tests ATOMIC_LOAD. */	\
+	atomic_##ta##_t atom = ATOMIC_INIT(val1);			\
+									\
+	/* ATOMIC_INIT and load. */					\
+	val = atomic_load_##ta(&atom, ATOMIC_RELAXED);			\
+	assert_##ta##_eq(val1, val, "Load or init failed");		\
+									\
+	/* Store. */							\
+	atomic_store_##ta(&atom, val1, ATOMIC_RELAXED);			\
+	atomic_store_##ta(&atom, val2, ATOMIC_RELAXED);			\
+	val = atomic_load_##ta(&atom, ATOMIC_RELAXED);			\
+	assert_##ta##_eq(val2, val, "Store failed");			\
+									\
+	/* Exchange. */							\
+	atomic_store_##ta(&atom, val1, ATOMIC_RELAXED);			\
+	val = atomic_exchange_##ta(&atom, val2, ATOMIC_RELAXED);	\
+	assert_##ta##_eq(val1, val, "Exchange returned invalid value");	\
+	val = atomic_load_##ta(&atom, ATOMIC_RELAXED);			\
+	assert_##ta##_eq(val2, val, "Exchange store invalid value");	\
+									\
+	/* 								\
+	 * Weak CAS.  Spurious failures are allowed, so we loop a few	\
+	 * times.							\
+	 */								\
+	atomic_store_##ta(&atom, val1, ATOMIC_RELAXED);			\
+	success = false;						\
+	for (int i = 0; i < 10 && !success; i++) {			\
+		expected = val2;					\
+		success = atomic_compare_exchange_weak_##ta(&atom,	\
+		    &expected, val3, ATOMIC_RELAXED, ATOMIC_RELAXED);	\
+		assert_##ta##_eq(val1, expected, 			\
+		    "CAS should update expected");			\
+	}								\
+	assert_b_eq(val1 == val2, success,				\
+	    "Weak CAS did the wrong state update");			\
+	val = atomic_load_##ta(&atom, ATOMIC_RELAXED);			\
+	if (success) {							\
+		assert_##ta##_eq(val3, val,				\
+		    "Successful CAS should update atomic");		\
+	} else {							\
+		assert_##ta##_eq(val1, val,				\
+		    "Unsuccessful CAS should not update atomic");	\
+	}								\
+									\
+	/* Strong CAS. */						\
+	atomic_store_##ta(&atom, val1, ATOMIC_RELAXED);			\
+	expected = val2;						\
+	success = atomic_compare_exchange_strong_##ta(&atom, &expected,	\
+	    val3, ATOMIC_RELAXED, ATOMIC_RELAXED);			\
+	assert_b_eq(val1 == val2, success,				\
+	    "Strong CAS did the wrong state update");			\
+	val = atomic_load_##ta(&atom, ATOMIC_RELAXED);			\
+	if (success) {							\
+		assert_##ta##_eq(val3, val,				\
+		    "Successful CAS should update atomic");		\
+	} else {							\
+		assert_##ta##_eq(val1, val,				\
+		    "Unsuccessful CAS should not update atomic");	\
+	}								\
+									\
+									\
+	/* Previous atomics API. */					\
+									\
+	/* Read. */							\
+	raw_atomic = val1;						\
+	val = atomic_read_##ta(&raw_atomic);				\
+	assert_##ta##_eq(val1, val, "Read failed");			\
+									\
+	/* Write. */							\
+	raw_atomic = val1;						\
+	atomic_write_##ta(&raw_atomic, val2);				\
+	assert_##ta##_eq(val2, raw_atomic, "Write failed");		\
+									\
+	/* CAS. */							\
+	raw_atomic = val1;						\
+	success = !atomic_cas_##ta(&raw_atomic, val2, val3);		\
+	assert_b_eq(val1 == val2, success, 				\
+	    "CAS did the wrong state update");				\
+	val = raw_atomic;						\
+	if (success) {							\
+		assert_##ta##_eq(val3, val,				\
+		    "Successful CAS should update atomic");		\
+	} else {							\
+		assert_##ta##_eq(val1, val,				\
+		    "Unsuccessful CAS should not update atomic");	\
 	}								\
 } while (0)
 
-TEST_STRUCT(u64, uint64_t)
+#define DO_INTEGER_TESTS(t, ta, val1, val2) do {			\
+	atomic_##ta##_t atom;						\
+	t val;								\
+	t raw_atomic;							\
+									\
+	/* Fetch-add. */						\
+	atomic_store_##ta(&atom, val1, ATOMIC_RELAXED);			\
+	val = atomic_fetch_add_##ta(&atom, val2, ATOMIC_RELAXED);	\
+	assert_##ta##_eq(val1, val,					\
+	    "Fetch-add should return previous value");			\
+	val = atomic_load_##ta(&atom, ATOMIC_RELAXED);			\
+	assert_##ta##_eq(val1 + val2, val,				\
+	    "Fetch-add should update atomic");				\
+									\
+	/* Fetch-sub. */						\
+	atomic_store_##ta(&atom, val1, ATOMIC_RELAXED);			\
+	val = atomic_fetch_sub_##ta(&atom, val2, ATOMIC_RELAXED);	\
+	assert_##ta##_eq(val1, val,					\
+	    "Fetch-sub should return previous value");			\
+	val = atomic_load_##ta(&atom, ATOMIC_RELAXED);			\
+	assert_##ta##_eq(val1 - val2, val,				\
+	    "Fetch-sub should update atomic");				\
+									\
+	/* Fetch-and. */						\
+	atomic_store_##ta(&atom, val1, ATOMIC_RELAXED);			\
+	val = atomic_fetch_and_##ta(&atom, val2, ATOMIC_RELAXED);	\
+	assert_##ta##_eq(val1, val,					\
+	    "Fetch-and should return previous value");			\
+	val = atomic_load_##ta(&atom, ATOMIC_RELAXED);			\
+	assert_##ta##_eq(val1 & val2, val,				\
+	    "Fetch-and should update atomic");				\
+									\
+	/* Fetch-or. */							\
+	atomic_store_##ta(&atom, val1, ATOMIC_RELAXED);			\
+	val = atomic_fetch_or_##ta(&atom, val2, ATOMIC_RELAXED);	\
+	assert_##ta##_eq(val1, val,					\
+	    "Fetch-or should return previous value");			\
+	val = atomic_load_##ta(&atom, ATOMIC_RELAXED);			\
+	assert_##ta##_eq(val1 | val2, val,				\
+	    "Fetch-or should update atomic");				\
+									\
+	/* Fetch-xor. */						\
+	atomic_store_##ta(&atom, val1, ATOMIC_RELAXED);			\
+	val = atomic_fetch_xor_##ta(&atom, val2, ATOMIC_RELAXED);	\
+	assert_##ta##_eq(val1, val,					\
+	    "Fetch-xor should return previous value");			\
+	val = atomic_load_##ta(&atom, ATOMIC_RELAXED);			\
+	assert_##ta##_eq(val1 ^ val2, val,				\
+	    "Fetch-xor should update atomic");				\
+									\
+	/* Previous atomics API. */					\
+									\
+	/* Add. */							\
+	raw_atomic = val1;						\
+	val = atomic_add_##ta(&raw_atomic, val2);			\
+	assert_##ta##_eq(val1 + val2, val,				\
+	    "atomic_add should return new value");			\
+	assert_##ta##_eq(val1 + val2, raw_atomic,			\
+	    "atomic_add should update atomic");				\
+									\
+	/* Sub. */							\
+	raw_atomic = val1;						\
+	val = atomic_sub_##ta(&raw_atomic, val2);			\
+	assert_##ta##_eq(val1 - val2, val,				\
+	    "atomic_sub should return new value");			\
+	assert_##ta##_eq(val1 - val2, raw_atomic,			\
+	    "atomic_add should update atomic");				\
+} while (0)
+
+#define TEST_STRUCT(t, ta)						\
+typedef struct {							\
+	t val1;								\
+	t val2;								\
+	t val3;								\
+} ta##_test_t;
+
+#define TEST_CASES(t) {							\
+	{(t)-1, (t)-1, (t)-2},						\
+	{(t)-1, (t) 0, (t)-2},						\
+	{(t)-1, (t) 1, (t)-2},						\
+									\
+	{(t) 0, (t)-1, (t)-2},						\
+	{(t) 0, (t) 0, (t)-2},						\
+	{(t) 0, (t) 1, (t)-2},						\
+									\
+	{(t) 1, (t)-1, (t)-2},						\
+	{(t) 1, (t) 0, (t)-2},						\
+	{(t) 1, (t) 1, (t)-2},						\
+									\
+	{(t)0, (t)-(1 << 22), (t)-2},					\
+	{(t)0, (t)(1 << 22), (t)-2},					\
+	{(t)(1 << 22), (t)-(1 << 22), (t)-2},				\
+	{(t)(1 << 22), (t)(1 << 22), (t)-2}				\
+}
+
+#define TEST_BODY(t, ta) do {						\
+	const ta##_test_t tests[] = TEST_CASES(t);			\
+	for (unsigned i = 0; i < sizeof(tests)/sizeof(tests[0]); i++) {	\
+		ta##_test_t test = tests[i];				\
+		DO_TESTS(t, ta, test.val1, test.val2, test.val3);	\
+	}								\
+} while (0)
+
+#define INTEGER_TEST_BODY(t, ta) do {					\
+	const ta##_test_t tests[] = TEST_CASES(t);			\
+	for (unsigned i = 0; i < sizeof(tests)/sizeof(tests[0]); i++) {	\
+		ta##_test_t test = tests[i];				\
+		DO_TESTS(t, ta, test.val1, test.val2, test.val3);	\
+		DO_INTEGER_TESTS(t, ta, test.val1, test.val2);		\
+	}								\
+} while (0)
+
+TEST_STRUCT(uint64_t, u64);
 TEST_BEGIN(test_atomic_u64) {
 #if !(LG_SIZEOF_PTR == 3 || LG_SIZEOF_INT == 3)
 	test_skip("64-bit atomic operations not supported");
 #else
-	TEST_BODY(u64, uint64_t, uint64_t, u64, FMTx64);
+	INTEGER_TEST_BODY(uint64_t, u64);
 #endif
 }
 TEST_END
 
-TEST_STRUCT(u32, uint32_t)
+
+TEST_STRUCT(uint32_t, u32);
 TEST_BEGIN(test_atomic_u32) {
-	TEST_BODY(u32, uint32_t, uint32_t, u32, "#"FMTx32);
+	INTEGER_TEST_BODY(uint32_t, u32);
 }
 TEST_END
 
-TEST_STRUCT(p, void *)
+TEST_STRUCT(void *, p);
 TEST_BEGIN(test_atomic_p) {
-	TEST_BODY(p, void *, uintptr_t, ptr, "p");
+	TEST_BODY(void *, p);
 }
 TEST_END
 
-TEST_STRUCT(zu, size_t)
+TEST_STRUCT(size_t, zu);
 TEST_BEGIN(test_atomic_zu) {
-	TEST_BODY(zu, size_t, size_t, zu, "#zx");
+	INTEGER_TEST_BODY(size_t, zu);
 }
 TEST_END
 
-TEST_STRUCT(u, unsigned)
+TEST_STRUCT(unsigned, u);
 TEST_BEGIN(test_atomic_u) {
-	TEST_BODY(u, unsigned, unsigned, u, "#x");
+	INTEGER_TEST_BODY(unsigned, u);
 }
 TEST_END