[compiler-rt] Fix atomic support functions on 32-bit architectures

[arichardson]

Summary

The code currently uses c11_atomic_is_lock_free() to detect whether an
atomic operation is natively supported. However, this can result in a
runtime function call to determine whether the given operation is lock-free
and clang generating a call to e.g. atomic_load_8 since the branch is
not a constant zero. Since we are implementing those runtime functions, we
must avoid those calls. This patch replaces c11_atomic_is_lock_free()
with atomic_always_lock_free() which always results in a compile-time
constant value. This problem was found while compiling atomic.c for MIPS32
since the -Watomic-alignment warning was being triggered and objdump showed
an undefined reference to _atomic_is_lock_free.

In addition to fixing 32-bit platforms this also enables the 16-byte case
that was disabled in r153779 (185f2edd70a34d28b305df0cd8ce519ecbca2cfd).

[arichardson]

remove incorrect cast

[luismarques]

LGTM. (I had already gone down roughly the same path in D86281. This patch additionally adds checks for the alignments of the pointers, so it can supersede D86281)

[efriedma]

This problem was found while compiling atomic.c for MIPS32 since the -Watomic-alignment warning was being triggered and objdump showed an undefined reference to _atomic_is_lock_free.

Are you sure this fixes the issue properly? If we're triggering -Watomic-alignment, probably the types are wrong somewhere. (In particular, some targets support lock-free operations on _Atomic long long, but the ABI alignment of long long is lower than 8.)

---

Have you seen https://reviews.llvm.org/D45321 ?

[arichardson]

In D86510#2237437, @efriedma wrote:

This problem was found while compiling atomic.c for MIPS32 since the -Watomic-alignment warning was being triggered and objdump showed an undefined reference to _atomic_is_lock_free.

Are you sure this fixes the issue properly? If we're triggering -Watomic-alignment, probably the types are wrong somewhere. (In particular, some targets support lock-free operations on _Atomic long long, but the ABI alignment of long long is lower than 8.)

We are triggering -Watomic-alignment because __c11_atomic_is_lock_free(8) expands to a __atomic_is_lock_free call for mips32 since the property is not known statically, so the branch inside the switch emitted and contains a call to __atomic_load_8 which triggers the warning. With this patch we know that 8-byte atomics are not always lock free so the branch is not emitted and we fall back to the locking code.

---

Have you seen https://reviews.llvm.org/D45321 ?

Thanks, I had not seen that review and it seems like it does almost the same thing, but uses the lock-free code in more cases.
It seems like both clang and GCC assume that atomic operations on pointers with unknown alignment are not always lock free: https://godbolt.org/z/T3oj1r
Therefore, this approach should be safe? And the optimization that checks the alignment and uses the atomic instructions instead of locks in the aligned case could be added later?

[efriedma]

We are triggering -Watomic-alignment because __c11_atomic_is_lock_free(8) expands to a __atomic_is_lock_free call for mips32 since the property is not known statically, so the branch inside the switch emitted and contains a call to __atomic_load_8 which triggers the warning.

Which -Watomic-alignment warning are we talking about? The "max lock-free size" one, or the "actual alignment" one?

Therefore, this approach should be safe? And the optimization that checks the alignment and uses the atomic instructions instead of locks in the aligned case could be added later?

The way the code with this patch checks for "lock-free" assumes the pointer argument is aligned the same way an a pointer to a uintN_t would be. That isn't correct in general.

[efriedma]

In D86510#2240266, @efriedma wrote:

Therefore, this approach should be safe? And the optimization that checks the alignment and uses the atomic instructions instead of locks in the aligned case could be added later?

The way the code with this patch checks for "lock-free" assumes the pointer argument is aligned the same way an a pointer to a uintN_t would be. That isn't correct in general.

Oh, wait, is the pointer argument here actually a void*? __atomic_always_lock_free will never succeed in that case.

[dim]

In D86510#2240266, @efriedma wrote:

We are triggering -Watomic-alignment because __c11_atomic_is_lock_free(8) expands to a __atomic_is_lock_free call for mips32 since the property is not known statically, so the branch inside the switch emitted and contains a call to __atomic_load_8 which triggers the warning.

Which -Watomic-alignment warning are we talking about? The "max lock-free size" one, or the "actual alignment" one?

The warning: misaligned atomic operation may incur significant performance penalty one.

[efriedma]

In D86510#2240363, @dim wrote:

In D86510#2240266, @efriedma wrote:

We are triggering -Watomic-alignment because __c11_atomic_is_lock_free(8) expands to a __atomic_is_lock_free call for mips32 since the property is not known statically, so the branch inside the switch emitted and contains a call to __atomic_load_8 which triggers the warning.

Which -Watomic-alignment warning are we talking about? The "max lock-free size" one, or the "actual alignment" one?

The warning: misaligned atomic operation may incur significant performance penalty one.

I can't seem to reproduce that... but it would indicate a bug in the code unrelated to the call to __atomic_is_lock_free. atomic.c shouldn't be trying to use misaligned lock-free atomics.

[arichardson]

In D86510#2240580, @efriedma wrote:

In D86510#2240363, @dim wrote:

In D86510#2240266, @efriedma wrote:

We are triggering -Watomic-alignment because __c11_atomic_is_lock_free(8) expands to a __atomic_is_lock_free call for mips32 since the property is not known statically, so the branch inside the switch emitted and contains a call to __atomic_load_8 which triggers the warning.

Which -Watomic-alignment warning are we talking about? The "max lock-free size" one, or the "actual alignment" one?

The warning: misaligned atomic operation may incur significant performance penalty one.

I can't seem to reproduce that... but it would indicate a bug in the code unrelated to the call to __atomic_is_lock_free. atomic.c shouldn't be trying to use misaligned lock-free atomics.

See https://godbolt.org/z/h91ob3. Seems to be the large one not the alignment one for MIPS32.

[luismarques]

I'll leave this to the experts then! :-)

[arichardson]

Use the lock-free code when

a) atomic ops of that size are always lock-free
b) aligned atomics ops are lock-free and the pointer is aligned

Note: the optimized functions assume that the pointer is aligned since the argument is a uint64_t, etc. If this is not correct the signature should be changed to use void* instead.

[efriedma]

Note: the optimized functions assume that the pointer is aligned since the argument is a uint64_t

This should be fine.

compiler-rt/lib/builtins/atomic.c

126

Please use 0, not NULL.

p & size probably doesn't do what you want; do you mean p % size?

[arichardson]

Use 0 instead of NULL and fix broken alignment check

[efriedma]

LGTM

compiler-rt/lib/builtins/atomic.c

static __inline Lock *lock_for_pointer(void *ptr) {
   // Now use the high(er) set of bits to perturb the hash, so that we don't
   // get collisions from atomic fields in a single object
   hash >>= 16;
   hash ^= low;
   // Return a pointer to the word to use
   return locks + (hash & SPINLOCK_MASK);
 }
 
-/// Macros for determining whether a size is lock free.  Clang can not yet
-/// codegen __atomic_is_lock_free(16), so for now we assume 16-byte values are
-/// not lock free.
-#define IS_LOCK_FREE_1 __c11_atomic_is_lock_free(1)
-#define IS_LOCK_FREE_2 __c11_atomic_is_lock_free(2)
-#define IS_LOCK_FREE_4 __c11_atomic_is_lock_free(4)
-#define IS_LOCK_FREE_8 __c11_atomic_is_lock_free(8)
-#define IS_LOCK_FREE_16 0
+/// Macros for determining whether a size is lock free.
+#define ATOMIC_ALWAYS_LOCK_FREE_OR_ALIGNED_LOCK_FREE(size, p)                  \
+  (__atomic_always_lock_free(size, p) ||                                       \
+   (__atomic_always_lock_free(size, 0) && ((uintptr_t)p % size) == 0))
+#define IS_LOCK_FREE_1(p) ATOMIC_ALWAYS_LOCK_FREE_OR_ALIGNED_LOCK_FREE(1, p)
+#define IS_LOCK_FREE_2(p) ATOMIC_ALWAYS_LOCK_FREE_OR_ALIGNED_LOCK_FREE(2, p)
+#define IS_LOCK_FREE_4(p) ATOMIC_ALWAYS_LOCK_FREE_OR_ALIGNED_LOCK_FREE(4, p)
+#define IS_LOCK_FREE_8(p) ATOMIC_ALWAYS_LOCK_FREE_OR_ALIGNED_LOCK_FREE(8, p)
+#define IS_LOCK_FREE_16(p) ATOMIC_ALWAYS_LOCK_FREE_OR_ALIGNED_LOCK_FREE(16, p)
 
 /// Macro that calls the compiler-generated lock-free versions of functions
 /// when they exist.
-#define LOCK_FREE_CASES()                                                      \
+#define TRY_LOCK_FREE_CASE(n, type, ptr)                                       \
+  case n:                                                                      \
+    if (IS_LOCK_FREE_##n(ptr)) {                                               \
+      LOCK_FREE_ACTION(type);                                                  \
+    }                                                                          \
+    break;
+#ifdef __SIZEOF_INT128__
+#define TRY_LOCK_FREE_CASE_16(p) TRY_LOCK_FREE_CASE(16, __uint128_t, p)
+#else
+#define TRY_LOCK_FREE_CASE_16(p) /* __uint128_t not available */
+#endif
+
+#define LOCK_FREE_CASES(ptr)                                                   \
   do {                                                                         \
     switch (size) {                                                            \
-    case 1:                                                                    \
-      if (IS_LOCK_FREE_1) {                                                    \
-        LOCK_FREE_ACTION(uint8_t);                                             \
-      }                                                                        \
-      break;                                                                   \
-    case 2:                                                                    \
-      if (IS_LOCK_FREE_2) {                                                    \
-        LOCK_FREE_ACTION(uint16_t);                                            \
-      }                                                                        \
-      break;                                                                   \
-    case 4:                                                                    \
-      if (IS_LOCK_FREE_4) {                                                    \
-        LOCK_FREE_ACTION(uint32_t);                                            \
-      }                                                                        \
-      break;                                                                   \
-    case 8:                                                                    \
-      if (IS_LOCK_FREE_8) {                                                    \
-        LOCK_FREE_ACTION(uint64_t);                                            \
-      }                                                                        \
-      break;                                                                   \
-    case 16:                                                                   \
-      if (IS_LOCK_FREE_16) {                                                   \
-        /* FIXME: __uint128_t isn't available on 32 bit platforms.             \
-        LOCK_FREE_ACTION(__uint128_t);*/                                       \
-      }                                                                        \
+      TRY_LOCK_FREE_CASE(1, uint8_t, ptr)                                      \
+      TRY_LOCK_FREE_CASE(2, uint16_t, ptr)                                     \
+      TRY_LOCK_FREE_CASE(4, uint32_t, ptr)                                     \
+      TRY_LOCK_FREE_CASE(8, uint64_t, ptr)                                     \
+      TRY_LOCK_FREE_CASE_16(ptr) /* __uint128_t may not be supported */        \
+    default:                                                                   \
       break;                                                                   \
     }                                                                          \
   } while (0)
 
 /// An atomic load operation.  This is atomic with respect to the source
 /// pointer only.
 void __atomic_load_c(int size, void *src, void *dest, int model) {
 #define LOCK_FREE_ACTION(type)                                                 \
   *((type *)dest) = __c11_atomic_load((_Atomic(type) *)src, model);            \
   return;
-  LOCK_FREE_CASES();
+  LOCK_FREE_CASES(src);
 #undef LOCK_FREE_ACTION
   Lock *l = lock_for_pointer(src);
   lock(l);
   memcpy(dest, src, size);
   unlock(l);
 }
 
 /// An atomic store operation.  This is atomic with respect to the destination
 /// pointer only.
 void __atomic_store_c(int size, void *dest, void *src, int model) {
 #define LOCK_FREE_ACTION(type)                                                 \
   __c11_atomic_store((_Atomic(type) *)dest, *(type *)src, model);              \
   return;
-  LOCK_FREE_CASES();
+  LOCK_FREE_CASES(dest);
 #undef LOCK_FREE_ACTION
   Lock *l = lock_for_pointer(dest);
   lock(l);
   memcpy(dest, src, size);
   unlock(l);
 }
 
 /// Atomic compare and exchange operation.  If the value at *ptr is identical
 /// to the value at *expected, then this copies value at *desired to *ptr.  If
 /// they  are not, then this stores the current value from *ptr in *expected.
 ///
 /// This function returns 1 if the exchange takes place or 0 if it fails.
 int __atomic_compare_exchange_c(int size, void *ptr, void *expected,
                                 void *desired, int success, int failure) {
 #define LOCK_FREE_ACTION(type)                                                 \
   return __c11_atomic_compare_exchange_strong(                                 \
       (_Atomic(type) *)ptr, (type *)expected, *(type *)desired, success,       \
       failure)
-  LOCK_FREE_CASES();
+  LOCK_FREE_CASES(ptr);
 #undef LOCK_FREE_ACTION
   Lock *l = lock_for_pointer(ptr);
   lock(l);
   if (memcmp(ptr, expected, size) == 0) {
     memcpy(ptr, desired, size);
     unlock(l);
     return 1;
   }
   memcpy(expected, ptr, size);
   unlock(l);
   return 0;
 }
 
 /// Performs an atomic exchange operation between two pointers.  This is atomic
 /// with respect to the target address.
 void __atomic_exchange_c(int size, void *ptr, void *val, void *old, int model) {
 #define LOCK_FREE_ACTION(type)                                                 \
   *(type *)old =                                                               \
       __c11_atomic_exchange((_Atomic(type) *)ptr, *(type *)val, model);        \
   return;
-  LOCK_FREE_CASES();
+  LOCK_FREE_CASES(ptr);
 #undef LOCK_FREE_ACTION
   Lock *l = lock_for_pointer(ptr);
   lock(l);
   memcpy(old, ptr, size);
   memcpy(ptr, val, size);
   unlock(l);
 }
 
#define OPTIMISED_CASES                                                        \
   OPTIMISED_CASE(1, IS_LOCK_FREE_1, uint8_t)                                   \
   OPTIMISED_CASE(2, IS_LOCK_FREE_2, uint16_t)                                  \
   OPTIMISED_CASE(4, IS_LOCK_FREE_4, uint32_t)                                  \
   OPTIMISED_CASE(8, IS_LOCK_FREE_8, uint64_t)
 #endif
 
 #define OPTIMISED_CASE(n, lockfree, type)                                      \
   type __atomic_load_##n(type *src, int model) {                               \
-    if (lockfree)                                                              \
+    if (lockfree(src))                                                         \
       return __c11_atomic_load((_Atomic(type) *)src, model);                   \
     Lock *l = lock_for_pointer(src);                                           \
     lock(l);                                                                   \
     type val = *src;                                                           \
     unlock(l);                                                                 \
     return val;                                                                \
   }
 OPTIMISED_CASES
 #undef OPTIMISED_CASE
 
 #define OPTIMISED_CASE(n, lockfree, type)                                      \
   void __atomic_store_##n(type *dest, type val, int model) {                   \
-    if (lockfree) {                                                            \
+    if (lockfree(dest)) {                                                      \
       __c11_atomic_store((_Atomic(type) *)dest, val, model);                   \
       return;                                                                  \
     }                                                                          \
     Lock *l = lock_for_pointer(dest);                                          \
     lock(l);                                                                   \
     *dest = val;                                                               \
     unlock(l);                                                                 \
     return;                                                                    \
   }
 OPTIMISED_CASES
 #undef OPTIMISED_CASE
 
 #define OPTIMISED_CASE(n, lockfree, type)                                      \
   type __atomic_exchange_##n(type *dest, type val, int model) {                \
-    if (lockfree)                                                              \
+    if (lockfree(dest))                                                        \
       return __c11_atomic_exchange((_Atomic(type) *)dest, val, model);         \
     Lock *l = lock_for_pointer(dest);                                          \
     lock(l);                                                                   \
     type tmp = *dest;                                                          \
     *dest = val;                                                               \
     unlock(l);                                                                 \
     return tmp;                                                                \
   }
 OPTIMISED_CASES
 #undef OPTIMISED_CASE
 
 #define OPTIMISED_CASE(n, lockfree, type)                                      \
   bool __atomic_compare_exchange_##n(type *ptr, type *expected, type desired,  \
                                      int success, int failure) {               \
-    if (lockfree)                                                              \
+    if (lockfree(ptr))                                                         \
       return __c11_atomic_compare_exchange_strong(                             \
           (_Atomic(type) *)ptr, expected, desired, success, failure);          \
     Lock *l = lock_for_pointer(ptr);                                           \
     lock(l);                                                                   \
     if (*ptr == *expected) {                                                   \
       *ptr = desired;                                                          \
       unlock(l);                                                               \
       return true;                                                             \
     }                                                                          \
     *expected = *ptr;                                                          \
     unlock(l);                                                                 \
     return false;                                                              \
   }
 OPTIMISED_CASES
 #undef OPTIMISED_CASE
 
 ////////////////////////////////////////////////////////////////////////////////
 // Atomic read-modify-write operations for integers of various sizes.
 ////////////////////////////////////////////////////////////////////////////////
 #define ATOMIC_RMW(n, lockfree, type, opname, op)                              \
   type __atomic_fetch_##opname##_##n(type *ptr, type val, int model) {         \
-    if (lockfree)                                                              \
+    if (lockfree(ptr))                                                         \
       return __c11_atomic_fetch_##opname((_Atomic(type) *)ptr, val, model);    \
     Lock *l = lock_for_pointer(ptr);                                           \
     lock(l);                                                                   \
     type tmp = *ptr;                                                           \
     *ptr = tmp op val;                                                         \
     unlock(l);                                                                 \
     return tmp;                                                                \
   }