[compiler-rt] Implement __atomic_is_lock_free

[arichardson]

Summary

This function is called by the __atomic_is_lock_free builtin if the value
cannot be resolved to true at compile time. Lack of this function is
causing the non-lockfree atomics tests in libc++ to not be run (see D91911)

This function is also added in D85044, but that also add support for using
lock-free atomics in more cases, whereas this just adds __atomic_is_lock_free
for the current state of atomic.c.

[ldionne]

Actually, this appears to be missing a test.

[arichardson]

Will add tests for this in the coming days.

[arichardson]

I just tried adding tests for this, and it turns out the existing atomic_test.c crashes due to __c11_atomic_load being implemented with cmpxchg16b. This crashes if the source is in read-only memory (as happens with this test). Do we need change __atomic_is_lock_free to return false for 16 byte atomics on x86 if clang generates incorrect code?

[arichardson]

• Add a test case (passes on x86_64 macOS, not tried other architectures yet)
• Rebased on top of D92833

[ldionne]

In D92302#2439218, @arichardson wrote:

Do we need change __atomic_is_lock_free to return false for 16 byte atomics on x86 if clang generates incorrect code?

I believe compiler-rt should be consistent with the code that Clang generates, even if Clang generates sub-optimal code. Then, we can fix compiler-rt at the same time as we fix Clang. Otherwise, it seems like one could say that we have two bugs: one is the fact that Clang doesn't implement 16 bytes atomics without locks, and the other one is that compiler-rt lies, by pretending that we do.

[oontvoo]

compiler-rt/test/builtins/Unit/atomic_test.c

594–595

Why should size 0 never be lock free?

(I would've thought they'd always be lock free given no operation is needed )

[oontvoo]

! In D92302#2439218, @arichardson wrote:
I just tried adding tests for this, and it turns out the existing atomic_test.c crashes due to __c11_atomic_load being implemented with cmpxchg16b. This crashes if the source is in read-only memory (as happens with this test).

I think this is expected. (GCC also has this issue - there's no 16byte load-instruction so compxchg16b is the only option right now).

Do we need change __atomic_is_lock_free to return false for 16 byte atomics on x86 if clang generates incorrect code?

I believe the answer is "no" - it should return the *right* answer.

[arichardson]

In D92302#2440107, @ldionne wrote:

In D92302#2439218, @arichardson wrote:

Do we need change __atomic_is_lock_free to return false for 16 byte atomics on x86 if clang generates incorrect code?

I believe compiler-rt should be consistent with the code that Clang generates, even if Clang generates sub-optimal code. Then, we can fix compiler-rt at the same time as we fix Clang. Otherwise, it seems like one could say that we have two bugs: one is the fact that Clang doesn't implement 16 bytes atomics without locks, and the other one is that compiler-rt lies, by pretending that we do.

I agree that __atomic_is_lock_free should return a value consistent with the atomic.c implementation.
16-byte atomics are currently lock-free on amd64, but using an atomic_load of read-only memory will result in a crash (if compiler-rt was compiled with cmxchg16b support). However, that is a problem that should be fixed in a separate review and D92832 and D85044 are probably a better place to discuss this issue.

compiler-rt/test/builtins/Unit/atomic_test.c

594–595

Size zero *could* be lock-free by returning immediately, but that's not what atomic.c does. __atomic_is_lock_free should return an answer that matches the implementation.

Fixing this should be part of a separate commit IMO. Also I'm not sure whether passing size=0 to any of the libatomic functions is valid.

[oontvoo]

In D92302#2439218, @arichardson wrote:

Do we need change __atomic_is_lock_free to return false for 16 byte atomics on x86 if clang generates incorrect code?

I believe compiler-rt should be consistent with the code that Clang generates, even if Clang generates sub-optimal code. Then, we can fix compiler-rt at the same time as we fix Clang. Otherwise, it seems like one could say that we have two bugs: one is the fact that Clang doesn't implement 16 bytes atomics without locks, and the other one is that compiler-rt lies, by pretending that we do.

I agree that __atomic_is_lock_free should return a value consistent with the atomic.c implementation.
16-byte atomics are currently lock-free on amd64, but using an atomic_load of read-only memory will result in a crash (if compiler-rt was compiled with cmxchg16b support). However, that is a problem that should be fixed in a separate review and D92832 and D85044 are probably a better place to discuss this issue.

SGTM - thanks!

[arichardson]

@ldionne Test has been added, is this okay to commit now?

[arichardson]

ping?

[ldionne]

Thanks!

compiler-rt/lib/builtins/atomic.c

 
 // Clang objects if you redefine a builtin.  This little hack allows us to
 // define a function with the same name as an intrinsic.
 #pragma redefine_extname __atomic_load_c SYMBOL_NAME(__atomic_load)
 #pragma redefine_extname __atomic_store_c SYMBOL_NAME(__atomic_store)
 #pragma redefine_extname __atomic_exchange_c SYMBOL_NAME(__atomic_exchange)
 #pragma redefine_extname __atomic_compare_exchange_c SYMBOL_NAME(              \
     __atomic_compare_exchange)
+#pragma redefine_extname __atomic_is_lock_free_c SYMBOL_NAME(                  \
+    __atomic_is_lock_free)
 
 /// Number of locks.  This allocates one page on 32-bit platforms, two on
 /// 64-bit.  This can be specified externally if a different trade between
 /// memory usage and contention probability is required for a given platform.
 #ifndef SPINLOCK_COUNT
 #define SPINLOCK_COUNT (1 << 10)
 #endif
 static const long SPINLOCK_MASK = SPINLOCK_COUNT - 1;
switch (size) {                                                            \
       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)
 
+/// Whether atomic operations for the given size (and alignment) are lock-free.
+bool __atomic_is_lock_free_c(size_t size, void *ptr) {
+#define LOCK_FREE_ACTION(type) return true;
+  LOCK_FREE_CASES(ptr);
+#undef LOCK_FREE_ACTION
+  return false;
+}
+
 /// 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(src);
 #undef LOCK_FREE_ACTION

compiler-rt/test/builtins/Unit/atomic_test.c

 //
 //===----------------------------------------------------------------------===//
 
 #include <stdbool.h>
 #include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
+#undef NDEBUG
+#include <assert.h>
 
 // We directly test the library atomic functions, not using the C builtins. This
 // should avoid confounding factors, ensuring that we actually test the
 // functions themselves, regardless of how the builtins are lowered. We need to
 // use asm labels because we can't redeclare the builtins.
 // Note: we need to prepend an underscore to this name for e.g. macOS.
 #define _STRINGIFY(x) #x
 #define STRINGIFY(x) _STRINGIFY(x)
 #define EXTERNAL_NAME(name) asm(STRINGIFY(__USER_LABEL_PREFIX__) #name)
 
+bool __atomic_is_lock_free_c(size_t size, void *ptr)
+    EXTERNAL_NAME(__atomic_is_lock_free);
+
 void __atomic_load_c(int size, void *src, void *dest,
                      int model) EXTERNAL_NAME(__atomic_load);
 
 uint8_t __atomic_load_1(uint8_t *src, int model);
 uint16_t __atomic_load_2(uint16_t *src, int model);
 uint32_t __atomic_load_4(uint32_t *src, int model);
 uint64_t __atomic_load_8(uint64_t *src, int model);
 
if (a128 != V * 2 + m)
       abort();
     __atomic_fetch_sub_16(&a128, V, model);
     if (a128 != V + m)
       abort();
 #endif
   }
 }
 
+void test_is_lock_free(void) {
+  // The result of __atomic_is_lock_free is architecture dependent, so we only
+  // check for a true return value for the sizes where we know that at compile
+  // time that they are supported. If __atomic_always_lock_free() returns false
+  // for a given size, we can only check that __atomic_is_lock_free() returns
+  // false for unaligned values.
+  // Note: This assumption will have to be revisited when we support an
+  // architecture that allows for unaligned atomics.
+  // XXX: Do any architectures report true for unaligned atomics?
+
+  // All atomic.c implementations fall back to the non-specialized case for
+  // size=0, so despite the operation being a no-op, they still take locks and
+  // therefore __atomic_is_lock_free should return false.
+  assert(!__atomic_is_lock_free_c(0, NULL) && "size zero should never be lock-free");
+  assert(!__atomic_is_lock_free_c(0, (void *)8) && "size zero should never be lock-free");
+
+  if (__atomic_always_lock_free(1, 0)) {
+    assert(__atomic_is_lock_free_c(1, NULL) && "aligned size=1 should always be lock-free");
+    assert(__atomic_is_lock_free_c(1, (void *)1) && "aligned size=1 should always be lock-free");
+  }
+
+  if (__atomic_always_lock_free(2, 0)) {
+    assert(__atomic_is_lock_free_c(2, NULL) && "aligned size=2 should always be lock-free");
+    assert(__atomic_is_lock_free_c(2, (void *)2) && "aligned size=2 should always be lock-free");
+  }
+  assert(!__atomic_is_lock_free_c(2, (void *)1) && "unaligned size=2 should not be lock-free");
+
+  if (__atomic_always_lock_free(4, 0)) {
+    assert(__atomic_is_lock_free_c(4, NULL) && "aligned size=4 should always be lock-free");
+    assert(__atomic_is_lock_free_c(4, (void *)4) && "aligned size=4 should always be lock-free");
+  }
+  assert(!__atomic_is_lock_free_c(4, (void *)3) && "unaligned size=4 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(4, (void *)2) && "unaligned size=4 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(4, (void *)1) && "unaligned size=4 should not be lock-free");
+
+  if (__atomic_always_lock_free(8, 0)) {
+    assert(__atomic_is_lock_free_c(8, NULL) && "aligned size=8 should always be lock-free");
+    assert(__atomic_is_lock_free_c(8, (void *)8) && "aligned size=8 should always be lock-free");
+  }
+  assert(!__atomic_is_lock_free_c(8, (void *)7) && "unaligned size=8 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(8, (void *)4) && "unaligned size=8 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(8, (void *)2) && "unaligned size=8 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(8, (void *)1) && "unaligned size=8 should not be lock-free");
+
+  if (__atomic_always_lock_free(16, 0)) {
+    assert(__atomic_is_lock_free_c(16, NULL) && "aligned size=16 should always be lock-free");
+    assert(__atomic_is_lock_free_c(16, (void *)16) && "aligned size=16 should always be lock-free");
+  }
+  assert(!__atomic_is_lock_free_c(16, (void *)15) && "unaligned size=16 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(16, (void *)8) && "unaligned size=16 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(16, (void *)4) && "unaligned size=16 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(16, (void *)2) && "unaligned size=16 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(16, (void *)1) && "unaligned size=16 should not be lock-free");
+
+  // In the current implementation > 16 bytes are never lock-free:
+  assert(!__atomic_is_lock_free_c(32, NULL) && "aligned size=32 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(32, (void*)32) && "aligned size=32 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(32, (void*)31) && "unaligned size=32 should not be lock-free");
+
+  // We also don't support non-power-of-two sizes:
+  assert(!__atomic_is_lock_free_c(3, NULL) && "aligned size=3 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(5, NULL) && "aligned size=5 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(6, NULL) && "aligned size=6 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(7, NULL) && "aligned size=7 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(9, NULL) && "aligned size=9 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(10, NULL) && "aligned size=10 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(11, NULL) && "aligned size=11 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(12, NULL) && "aligned size=12 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(13, NULL) && "aligned size=13 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(14, NULL) && "aligned size=14 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(15, NULL) && "aligned size=15 should not be lock-free");
+  assert(!__atomic_is_lock_free_c(17, NULL) && "aligned size=17 should not be lock-free");
+}
+
 int main() {
   test_loads();
   test_stores();
   test_exchanges();
   test_compare_exchanges();
   test_fetch_op();
+  test_is_lock_free();
   return 0;
 }