[compiler-rt] [builtins] Port atomic.c to GCC

[krytarowski]

Summary

Add support for GCC builtins. This is a step towards
reusing LLVM atomic.c as libatomic compatible with GCC.

Add public function prototypes to avoid build errors with
enabled warnings

[theraven]

I don't think that this should be including <stdatomic.h>. These routines are used to implement interfaces in <stdatomic.h> and it would be completely valid for a conforming implementation to use _Generic macros to directly call these functions from things in <stdatomic.h> that we then depend call, giving a circular dependency.

I don't particularly object to moving this to using the GCC builtins, since clang supports both the GCC ones and the __c11 ones, but the only two valid implementations of the routines in this file are to use compiler builtins or inline assembly.

[krytarowski]

In D79713#2029387, @theraven wrote:

I don't think that this should be including <stdatomic.h>. These routines are used to implement interfaces in <stdatomic.h> and it would be completely valid for a conforming implementation to use _Generic macros to directly call these functions from things in <stdatomic.h> that we then depend call, giving a circular dependency.

I don't particularly object to moving this to using the GCC builtins, since clang supports both the GCC ones and the __c11 ones, but the only two valid implementations of the routines in this file are to use compiler builtins or inline assembly.

I've switched to GCC builtins. I had to remove _Atomic() in order to make it buildable.

[jfb]

Without looking at the details, this generally seems fine... but why is this desirable? The commit message should have that information. If there's not really a reason then I'd rather leave it alone and not change something that's fine.

[krytarowski]

In D79713#2029514, @jfb wrote:

Without looking at the details, this generally seems fine... but why is this desirable? The commit message should have that information. If there's not really a reason then I'd rather leave it alone and not change something that's fine.

I intend to use LLVM (lib)atomic implementation with GCC, instead of the GNU libatomic version.

[jfb]

In D79713#2029528, @krytarowski wrote:

In D79713#2029514, @jfb wrote:

Without looking at the details, this generally seems fine... but why is this desirable? The commit message should have that information. If there's not really a reason then I'd rather leave it alone and not change something that's fine.

I intend to use LLVM (lib)atomic implementation with GCC, instead of the GNU libatomic version.

I think that's a fine motivation. libatomic from LLVM and GCC have the same API, and it's not big. However, this is a new thing for LLVM to support. I'd suggest sending an RFC, basically asking "are we OK supporting libatomic for non-LLVM compilers?". I suspect the answer is "yes" because it seems like very low overhead. However I might be missing details that make this complicated, where for example there's non-trivial and non-portable tie-in between the compiler and the runtime's implementation.

[ldionne]

compiler-rt/lib/builtins/atomic.c

310

Sorry if that's a dumb question (I'm not super familiar with how things are stringed between the compiler and compiler-rt), but doesn't that mean the builtin will now take an additional argument bool weak? IOW, is that an API breaking change?

[krytarowski]

compiler-rt/lib/builtins/atomic.c

310

I think that there is a bug in Clang/LLVM as it forgets about weak in certain places (CGAtomic.cpp) and notes it in other ones (generally __atomic_compare_exchange_n).

[jfb]

compiler-rt/lib/builtins/atomic.c

310

This does seem like a divergence from GCC. Docs are consistent with the code though:

https://llvm.org/docs/Atomics.html#libcalls-atomic

https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html

I'm not sure that we can unconditionally "fix" this, because it would be an ABI break.

[krytarowski]

compiler-rt/lib/builtins/atomic.c

310

This still could be fixed unconditionally at this phase as this library is not widely used (not building by default for me either). It also contains missing calls, even if they are generated in Clang (__atomic_fetch_nand_N existing in GNU libatomic or lack of version of __c11_atomic_fetch_min?).

I have got intention to use the same libatomic implementation for both compilers, even if there will be ABI switch in syncing the interface, however I defer this decision to the Clang maintainers.

If there is a decision to support only Clang and be incompatible with GCC on purpose, it would be good to know.

[theraven]

To give some background (please correct me if I'm wrong): This is initially motivated by having snmalloc working on NetBSD. Snmalloc relies on two-pointer compare-and-exchange. When passing -mcx16, clang will happily emit these instructions for the atomic builtins used by <atomic> but GCC currently contains a bug that will emit these only for the old-style __sync_* builtins and not for the __atomic_ ones. As a result, the gcc builds of snmalloc include a call to __atomic_compare_exchange_16, which is not found on NetBSD because they don't ship the relevant support functions. NetBSD would like to ship chunks of compiler-rt, compiled with their default toolchain (GCC).

Unfortunately, I don't believe these changes will actually work as expected. Because of the aforementioned GCC but, __atomic_compare_exchange_16 will compile to the version with a lock on x86-64 with GCC, not the lock-free version. This means that _Atomic-qualified 16-byte values will not be correctly synchronised between GCC code, clang code, and clang code compiled with -mcx16.

I'm also somewhat opposed to removing the _Atomic qualifier. I'd rather that we did a #define _Atomic(x) x guarded by a check for broken compilers. Unfortunately, the C11 spec is somewhat broken in this regard. _Atomic qualifiers were added to allow Atomic(T) and T to have different padding and alignment requirements (and even different representations, such as requiring an inline lock for large values of T), but then the <stdatomic.h> functions were defined to take volatile T* instead of _Atomic(T) * arguments, violating the intent. The porting of C++11's atomics to C was not handled well at all by WG14. Part of the early goal was for _Atomic(T) and std::atomic<T> to be ABI-compatible (or, at least, for ABIs where these two were compatible to be possible), but it's quite easy to define a C++ template that switches from lock-free to having an inline lock. but it's impossible to do that with the eventual APIs in <stdatomic.h>. Supporting the eventual mess is likely to cause pain for many years to come.

[krytarowski]

• drop ABI change in __atomic_compare_exchange_##n

[krytarowski]

In D79713#2031145, @theraven wrote:

To give some background (please correct me if I'm wrong): This is initially motivated by having snmalloc working on NetBSD.

There is a growing number of software that requires libatomic, especially for older and 32-bit CPUs and we cannot keep forcing usage of shiny CPU types in all circumstances. snmalloc is only one of them, but not the only one.

We would want use the same library in the basesystem for both compilers. Something along these lines was also originally proposed in the snmalloc repository to deliver a basesystem version of libatomic.

GCC will likely fix -mcx16 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80878

I'm also somewhat opposed to removing the _Atomic qualifier.

Would you like to fix Clang? _Atomic() specifiers shall not be at least rejected.

I have removed from the proposed patch ABI change in __atomic_compare_exchange_##n in order to make it easier to merge, that one shall be fixed too.

[krytarowski]

In D79713#2031145, @theraven wrote:

it's quite easy to define a C++ template that switches from lock-free to having an inline lock

While there... LLDB forces std::atomic<uint64_t> in https://github.com/llvm/llvm-project/blob/cdc514e4c67f268b07863bbac3d8d7e0d088186c/lldb/include/lldb/Utility/Timer.h#L32 This makes import of LLDB into the NetBSD basesystem harder.

Should we have llvm::atomic<> that reimplements libatomic? Have you got an idea how to design it? As I looked into std::atomic<> the implementation is rather too large for reimplementation (around 3000 LOC). That's not the first time when we see std::atomic<> in the LLDB codebase and this will eventually return back.

I presume that it's best to just deliver libatomic at this point, as it is a part of the C11/C++14 runtime.

[ldionne]

compiler-rt/lib/builtins/atomic.c

310

My question was simply whether this was an API breaking change for existing users of Clang. I'm still not sure of the answer, however it seems you've reverted this part of the patch, so I guess the point is moot.

I don't think anybody claims that libatomic should only support Clang and not GCC, I think we're just trying to figure out what that means and whether we can do it without breaking existing users on Clang. At least, that's what I'm trying to determine.

FWIW, Apple doesn't ship libatomic yet (AFAICT), so whatever we do here should be fine from that perspective. I can't speak for other vendors.

[krytarowski]

compiler-rt/lib/builtins/atomic.c

310

FreeBSD uses GNU libatomic for the combination with GCC.
OpenBSD doesn't use LLVM atomic.c.
NetBSD doesn't use LLVM atomic.c yet.

Apple doesn't ship it according to you.

After a quick search in Linux distros, there are probably no users of atomic.c, if there are any, they are not in mainstream distros.

NetBSD is apparently the first wannabe user of LLVM atomic and thus I have been first to find out the mismatch in the builtin with GCC.

I don't want to block the entire review on this mismatch and that can be submitted separately.

[theraven]

FreeBSD uses GNU libatomic for the combination with GCC.

I'm not sure what this means. FreeBSD now uses LLVM's atomic.c in our libgcc_s implementation.

[jfb]

Still, I think this needs an RFC on LLVM dev. Supporting a new platform should be done deliberately.

[krytarowski]

I rewrote this code again to support GCC. This time without removal of _Atomic().

Now, there is a separation for Clang and GCC builtins. It's easier to handle them separately as they are not compatible sufficiently.

Is this version looking fine?

In D79713#2031627, @jfb wrote:

Still, I think this needs an RFC on LLVM dev. Supporting a new platform should be done deliberately.

Once I will get something acceptable to merge, I can send a mail. I will speak up for merging the __atomic_compare_exchange_##n semantics.

[ldionne]

It's not super pretty, but I think this would work (assuming my concern about PP expansions above is wrong).

That being said, I somewhat agree that adding support for another platform or building with another compiler is something that should be done deliberately. In this case, for example, it means that the compiler-rt maintainers (who are they?) will be "stuck" making sure that libatomic builds on GCC forever. For instance, do we have a buildbot that does that? This is the kind of thing that would cause me to say "nope, we don't support that compiler because we can't test such support".

I'm not a compiler-rt maintainer, but I would definitely hold that position for libc++ and libc++abi.

compiler-rt/lib/builtins/atomic.c

332

Does this really work? I thought you'd need to go through another PP expansion in order for this to expand properly. I'd think you need to write something like CONCAT(ATOMIC_FETCH_, opname, _EXPLICIT) where #define CONCAT(x,y,z) x ## y ## z?

[krytarowski]

will be "stuck" making sure that libatomic builds on GCC forever.

Generally... we [used to] build everything in compiler-rt with GCC except this single file.

[ldionne]

In D79713#2032236, @krytarowski wrote:

will be "stuck" making sure that libatomic builds on GCC forever.

Generally... we [used to] build everything in compiler-rt with GCC except this single file.

Interesting! Where is the corresponding build system change in this patch?

[krytarowski]

In D79713#2032372, @ldionne wrote:

In D79713#2032236, @krytarowski wrote:

will be "stuck" making sure that libatomic builds on GCC forever.

Generally... we [used to] build everything in compiler-rt with GCC except this single file.

Interesting! Where is the corresponding build system change in this patch?

In this case my only intention is to reuse atomic.c and construct libatomic with custom build system.

I'm kind to upstream local modifications, before doing it, for the general benefit.

[krytarowski]

I've separated two independent changes out of this revision into a separate review.
D79845 + D79846.

Please review them. I will be easier to focus here on the proper GCC support only.

[ldionne]

In D79713#2032426, @krytarowski wrote:

In D79713#2032372, @ldionne wrote:

In D79713#2032236, @krytarowski wrote:

will be "stuck" making sure that libatomic builds on GCC forever.

Generally... we [used to] build everything in compiler-rt with GCC except this single file.

Interesting! Where is the corresponding build system change in this patch?

In this case my only intention is to reuse atomic.c and construct libatomic with custom build system.

The point I'm trying to make is that it seems this change allows you to build this file with GCC at this point in time, which is great. But it also appears like none of this is stringed into the rest of LLVM (build system, build bots, etc.). That's kind of what I'm worried about. To make my concern clearer, after you commit this, what would prevent someone from unknowingly removing the prototypes before the function definitions and breaking you? Nothing AFAICT. That's the sort of thing that tells me this change is "lazy", in the sense that it allows you to solve your problem right now, but it does introduce latent tech debt.

Anyway, I'm not trying to block you, I'm not even a maintainer of compiler-rt. It just seems like this is flaky.

In all cases, this looks OK for libc++ as long as you don't break the builtins when compiled with Clang (and I include changing their API in "break").

[ldionne]

Is this still relevant? If not, let's abandon to clear up the review queue.

[krytarowski]

It's relevant but I encountered issues to pass the review..

[ldionne]

In D79713#2369874, @krytarowski wrote:

It's relevant but I encountered issues to pass the review..

If you're thinking about my comments, they are not blocking. I don't own compiler-rt. I was just giving my opinion.

compiler-rt/lib/builtins/atomic.c

 //
 //  To avoid needing a per-object lock, this code allocates an array of
 //  locks and hashes the object pointers to find the one that it should use.
 //  For operations that must be atomic on two locations, the lower lock is
 //  always acquired first, to avoid deadlock.
 //
 //===----------------------------------------------------------------------===//
 
+#include <stdbool.h>
 #include <stdint.h>
 #include <string.h>
 
 #include "assembly.h"
 
 // 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)

 typedef OSSpinLock Lock;
 __inline static void unlock(Lock *l) { OSSpinLockUnlock(l); }
 /// Locks a lock.  In the current implementation, this is potentially
 /// unbounded in the contended case.
 __inline static void lock(Lock *l) { OSSpinLockLock(l); }
 static Lock locks[SPINLOCK_COUNT]; // initialized to OS_SPINLOCK_INIT which is 0
 
 #else
-typedef _Atomic(uintptr_t) Lock;
+typedef uintptr_t Lock;
 /// Unlock a lock.  This is a release operation.
 __inline static void unlock(Lock *l) {
-  __c11_atomic_store(l, 0, __ATOMIC_RELEASE);
+  __atomic_store_n(l, 0, __ATOMIC_RELEASE);
 }
 /// Locks a lock.  In the current implementation, this is potentially
 /// unbounded in the contended case.
 __inline static void lock(Lock *l) {
   uintptr_t old = 0;
-  while (!__c11_atomic_compare_exchange_weak(l, &old, 1, __ATOMIC_ACQUIRE,
-                                             __ATOMIC_RELAXED))
+  while (!__atomic_compare_exchange_n(l, &old, 1, 1, __ATOMIC_ACQUIRE,
     old = 0;
 }
 /// locks for atomic operations
 static Lock locks[SPINLOCK_COUNT];
 #endif
 
 /// Returns a lock to use for a given pointer.
 static __inline Lock *lock_for_pointer(void *ptr) {
static __inline Lock *lock_for_pointer(void *ptr) {
   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(x) __atomic_is_lock_free(sizeof(*(x)), (x))
+#define IS_LOCK_FREE_1 __IS_LOCK_FREE((uint8_t *)NULL)
+#define IS_LOCK_FREE_2 __IS_LOCK_FREE((uint16_t *)NULL)
+#define IS_LOCK_FREE_4 __IS_LOCK_FREE((uint32_t *)NULL)
+#define IS_LOCK_FREE_8 __IS_LOCK_FREE((uint64_t *)NULL)
 #define IS_LOCK_FREE_16 0
 
 /// Macro that calls the compiler-generated lock-free versions of functions
 /// when they exist.
 #define LOCK_FREE_CASES()                                                      \
   do {                                                                         \
     switch (size) {                                                            \
     case 1:                                                                    \
case 16:                                                                   \
         LOCK_FREE_ACTION(__uint128_t);*/                                       \
       }                                                                        \
       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);
 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);            \
+  *((type *)dest) = __atomic_load_n((type *)src, model);                       \
   return;
   LOCK_FREE_CASES();
 #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);
 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);              \
+  __atomic_store_n((type *)dest, *(type *)src, model);                         \
   return;
   LOCK_FREE_CASES();
 #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);
+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)
+  return __atomic_compare_exchange_n((type *)ptr, (type *)expected,            \
+                                     *(type *)desired, 0, success, failure)
   LOCK_FREE_CASES();
 #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);
 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);        \
+  *(type *)old = __atomic_exchange_n((type *)ptr, *(type *)val, model);        \
   return;
   LOCK_FREE_CASES();
 #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);                                \
   type __atomic_load_##n(type *src, int model) {                               \
     if (lockfree)                                                              \
-      return __c11_atomic_load((_Atomic(type) *)src, model);                   \
+      return __atomic_load_n((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);                    \
   void __atomic_store_##n(type *dest, type val, int model) {                   \
     if (lockfree) {                                                            \
-      __c11_atomic_store((_Atomic(type) *)dest, val, model);                   \
+      __atomic_store_n(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);                 \
   type __atomic_exchange_##n(type *dest, type val, int model) {                \
     if (lockfree)                                                              \
-      return __c11_atomic_exchange((_Atomic(type) *)dest, val, model);         \
+      return __atomic_exchange_n(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)                                      \
-  int __atomic_compare_exchange_##n(type *ptr, type *expected, type desired,   \
-                                    int success, int failure) {                \
+  bool __atomic_compare_exchange_##n(type *ptr, type *expected, type desired,  \
+                                     int success, int failure);                \
+  bool __atomic_compare_exchange_##n(type *ptr, type *expected, type desired,  \
+                                     int success, int failure) {               \
     if (lockfree)                                                              \
-      return __c11_atomic_compare_exchange_strong(                             \
-          (_Atomic(type) *)ptr, expected, desired, success, failure);          \
+      return __atomic_compare_exchange_n(ptr, expected, desired, 0, success,   \
+                                         failure);                             \
     Lock *l = lock_for_pointer(ptr);                                           \
     lock(l);                                                                   \
     if (*ptr == *expected) {                                                   \
       *ptr = desired;                                                          \
       unlock(l);                                                               \
       return 1;                                                                \
     }                                                                          \
     *expected = *ptr;                                                          \
     unlock(l);                                                                 \
     return 0;                                                                  \
   }
 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);          \
   type __atomic_fetch_##opname##_##n(type *ptr, type val, int model) {         \
     if (lockfree)                                                              \
-      return __c11_atomic_fetch_##opname((_Atomic(type) *)ptr, val, model);    \
+      return __atomic_fetch_##opname(ptr, val, model);                         \
     Lock *l = lock_for_pointer(ptr);                                           \
     lock(l);                                                                   \
     type tmp = *ptr;                                                           \
     *ptr = tmp op val;                                                         \
     unlock(l);                                                                 \
     return tmp;                                                                \
   }