is already close to the C11 call interface as given above.

In addition to the more or less obvious operands, the built-in functions take one or two additional parameters that reflect an eventual requirement for the memory_order of the operation. So the functions represent the C11 "explicit" features such as atomic_fetch_add_explicit. The non-explicit versions have to be mapped to the explicit version by providing memory_order_seq_cst as parameter(s).

Observe that the built-in functions only foresee one interface compare_exchange.

• The distinction between weak and strong versions of these built-in functions are ruled through an additional parameter, not through a different function interface.

• The function symbol fall-back __atomic_compare_exchange confusingly has a different semantic and prototype than the built-in function. It misses the parameter to chose between the "weak" and the "strong" version, and solely corresponds to the C11 operation

  atomic_compare_exchange_strong_explicit

As said, load, store and compare_exchange operations have memory semantics. The implementation may use = or == operators in some places for optimization, but it then does so with objects of uintXX_t, so every bit is accounted for.

Function call interfaces for the arithmetic operations are only generated if we can suppose that an integer type for the corresponding size exists. We can reasonably assume that there are always types uint8_t, uint16_t, uint32_t and uint64_t, so the variants for 1, 2, 4 and 8 can always be generated.

For a 128 bit type these are only generated if __SIZEOF_INT128__ or __GCC_HAVE_SYNC_COMPARE_AND_SWAP_16 exist. If so, we assume that __uint128_t is such an integer type and known to the compiler.

Arithmetic operations can safely use these uintXX_t types internally, since the standard imposes two's complement representation for signed atomic types and also enforces that atomic operations may not produce traps on overflow.

Additionally to the operations that have generic function interfaces in the C11 standard, gcc additionally implements six other built-ins, namely

• __atomic_add_fetch for integer or pointer addition, returning the updated value
• __atomic_sub_fetch for integer or pointer subtraction, returning the updated value
• __atomic_or_fetch for bitwise or, returning the updated value
• __atomic_and_fetch for bitwise and, returning the updated value
• __atomic_xor_fetch for bitwise xor, returning the updated value
• __atomic_fetch_nand for bitwise nand (x = ~(x & v)), returning the previous value
• __atomic_nand_fetch for bitwise nand (x = ~(x & v)), returning the updated value

For the completeness of the library interface we supply analogous functions with the _X suffix for these. They might be called by the compiler if the user code uses assign and add or similar operators on atomic integers. The __atomic_add_fetch and __atomic_sub_fetch functions may also eventually be used by the compiler to implement an atomic prefix increment or decrement operation (++x and --x). This would e.g happen if x is an object of type __int128_t and the platform doesn't implement lock-free atomics for types of size 16.

Clang has gone a different path for the built-ins that implement C11 atomics, prefixed with __c11_atomic. These are a directly feature equivalent to the C11 generic functions that have memory_order arguments (_explicit suffix).

For the cases that no atomic instructions can be synthesized, clang falls back to the same external calls as described for gcc's __atomic ABI.

It dates back long before the C11 atomic interface had been designed and thus cannot be directly conforming to it. It has basically the same built-ins for arithmetic types as above, only that

• The functions are named a bit differently.
• They only implement sequential consistency.
• There are no load, store or exchange features.
• The nand operations changed their meaning from version 4.4 onward. Therefore this operation cannot be used portably in an environment that might use different versions of compilers. So we don't implement these function interfaces and we deprecate the use of this built-in.

Additionally this interface also implements a test_and_set functionality that is used to implement the atomic_flag functions. This built-in is documented to have acquire-release consistency. If used with sequential consistency, an additional fence is inserted to ensure that.

These features are sufficient to provide a decent implementation of C11 atomics.

In absence of proper architecture support, all fallbacks (for the three built-in families) with _X suffix use the ones without suffix underneath. These external interfaces receive the size of the data type as an additional, leading parameter:

• __atomic_load
• __atomic_store
• __atomic_exchange
• __atomic_compare_exchange

They have pure memory semantics and their basic operations are memcpy and memcmp for load, store and comparison.

These functions cannot be called directly from within your code, because the compiler cannot distinguish them from the gcc built-ins, and they have different prototypes than these.

We implement these functions as critical sections that are protected with a lock, similar to a mutex. This implementations uses a table of locks and a hash function to choose one of the entries that only depends on the address of the atomic object.

At the moment, this implementation has several address-hash functions that can be chosen a library-compile time. Any function that mixes the bits of the address should perform reasonably well.

More important for performance is the choice of the lock. Such a lock can be relatively simple, since C11 atomics that are not lock-free don't have to be asynchronous signal safe.

There are several possibilities, in order of preference:

• An OS specific light-weighted lock with non-active waits. The integration into musl uses Linux' futex underneath to do an efficient wait. If by coincidence these are called in an un-threaded process, they are close to non-ops.
• C11's mtx_t type has an shallow interface that should allow it to be implemented a bit simpler and efficient than OS specific mutexes that implement a lot of functionality. This solution should be portable to all platforms that implement this part of C11. In a relatively near future these could be all POSIX and Windows platforms. This approach has the disadvantage that a table of mtx_t must be initialized at process startup because mtx_t doesn't guarantee static initialization.
• POSIX' pthread_mutex_t is a little less portable, but allows for static initialization.

• A spinlock similar to atomic_flag. Such an approach is portable to all platforms that implement atomics and allows for static initialization. This is the only choice when compiled without OS or library support.

  The wait functionality is an active wait, that burns CPU cycles and memory bandwidth. In many circumstances this should do well, the critical sections that are protected by this are nice and small.

Since this approach may reinterpret data through pointer casts, it could potentially be dangerous. So let us discuss the possible issues.

• The generic fallbacks for memory access only use memcpy and memcmp to access the data itself. So the access of the data is within the constraints of the standard.
• The generic fallbacks for memory access ensure that their arguments have compatible base types (if a pointer is passed in) or are assignment compatible with the base type of the atomic (if a value is passed in). So data that is copied across can never be misinterpreted as being of a wrong type because the two target types are compatible.
• The specialized functions with _X suffix may reinterpret their data as the corresponding uintXX_t for the size. Copying or comparing such data is always guaranteed to use all bits, so in that sense it is equivalent to memcpy and memcmp.
• The arithmetic operations that are executed then are operations on an unsigned integer type that has no padding bits. This arithmetic is compatible for all integer types that have no padding bits and, for the signed types, are represented with two's complement.
• An emulated atomic with this approach is implemented as an array to the base type, and so in the user code the base type of the object remains visible to the compiler. As a consequence this approach has no effect on the aliasing rules, the compiler always has complete information about the type of each object.

The only potential problem for our approach that remains is alignment. Since the stub functions that are provided may use casts to uintXX_t of "atomic" objects you have to ensure that these objects are at least aligned as these types would be. This should not be a problem, if the base type is an integer type, too. Integer types with same size should have the same alignment.

If you encounter problems with a user defined type that has a size that is a small power of two you could force alignment

_Alignas(sizeof(toto)) _Atomic(toto) toto1;
__attribute__((__aligned__(sizeof(toto)))) _Atomic(toto) toto2;

with whatever of the two constructs works for you.

I am currently struggling to provide a version of the _Atomic(T) macro that ensures that automatically. It seems to be possible but produces a lot of noise for function parameters that are pointers to atomics.

You should be able to compile this implementation with any version of modern gcc and clang. (Versions are hard to tell, gcc should work for 4.1) The quality of the resulting binary will depend on the implementation of atomic support by the compiler.

There are three different implementations, for modern clang and gcc, and one for those compilers that only support the __sync_ built-ins. They are only tested with clang and gcc, but might work with other compilers that implement one of the sets of built-ins and is otherwise compatible to some gcc extensions:

• compound expressions with ({ })
• __typeof__
• __attribute__((__unused__))
• __builtin_choose_expr for the __sync version as a precursor of C11's _Generic
• #pragma redefine_extname to rename the external symbols that are produced

If aligment happens to be an issue you might also need

• __attribute__((__aligned__(something)))
• __alignof__

or the equivalent C11 features _Alignas and _Alignof.

There are some heuristics in place to decide at compile time which case applies, namely __clang__ to detect clang, __ATOMIC_... macros to detect the C11 versions of the built-ins.

The library may work with different lock constructs, as described above, that is a futex based support for Linux, C11's mtx_t, POSIX' pthread_mutex_t, and active spinning as a last resort. You may find a description of the algorithms and some performance figures in the article https://hal.inria.fr/hal-01236734

If you would like to see support for other OS or runtime environments, don't hesitate to contact me if you'd like to work on implementing and integrating this.

There is one important difficulty when compiling this. The original __atomic library interface was developed with C++ in mind and not C. Therefore it freely uses function overloading for the built-ins versus the library interface. Since we also use the library functions as fallbacks in the implementation of some of the _X variants this naming scheme is not supportable with a C compiler.

We get away with it by using internal names, prefixed with __impl_ for all functions. Then a gcc extension is used to map that internal name to an external name, e.g

#pragma redefine_extname __impl_load __atomic_load

If your compiler doesn't support this feature, you'd have to use an external tool such as objcopy to achieve the same.

The main difference for modern processors that is relevant here is if it supports 16 byte atomic instructions or not. There is no difficulty to detect this at compile time, but if the library is used with code that is compiled with a different compiler or just different compiler options, incompatible binary code may be produced.

My plan is to freeze that feature at compile time of the library and reflect the capacity in the <stdatomic.h> that is provided. This then may result in code that is a bit less optimized than it could, but that is compatible.

• If the library is not compiled with direct 16 byte support the application may not use it, and thus use a memory implementation for such operations.
• If the library is compiled with direct 16 byte support but the application compiler doesn't support it, the user code should fallback to library calls, but which in turn use the atomic instructions. So such a variant would have a call overhead and would not be able to inline the atomics in the user binary.

I already have a working implementation of such a safety feature in some other code, so this is feasible. But for the moment this is not yet done, here. Be careful when using this preliminary version.

There is optional instrumentation for the lock functions. Switching it on changes overall performance substantially, and thus I'd expect a noticeable effect by the observation principle. These counters can give qualitative information about what happens, but you shouldn't take the figures verbally. Also these counters are only protected if you test the library with only one lock, using atomics for these counters themselves would have a strong performance impact and the resulting statistics would basically be worthless.

You can switch the instrumentation of the code on by defining the symbol BENCH at compile time. A function atomic_summary can be used at the end of all operations to print the collected data to stderr.

To test the behavior of the locking algorithm you may inject a function call just after the acquisition of the lock. Thereby you can e.g force the thread that obtains the lock to be descheduled, and test the worst-case behavior of the locking algorithm.

This feature is switched on by defining the macro ATOMIC_INJECT at compile time. By that you have a thread local variable atomic_faulty and a function interface atomic_inject at your disposal, namely atomic_inject is called iff atomic_faulty is true for the calling thread.

There is a "weak" version of atomic_inject that does nothing. It can be overwritten by a specific version that you provide yourself. E.g for the benchmarks using Modular C in the article that we mentionned above, slow path of the algorithm is stressed by simply calling thrd_yield.

The variable atomic_faulty can be used to switch the code injection on and off, such that you may experiment with different probabilities of failure.

For this application the performance in the lower range of is largely dominated by the fast path, that is by a very small number of assembler instructions that constitute the good case, when a thread doesn't encounter congestion. On a x86_64 machine, our implementation of the four different categories result in the following memory instructions:

The spinlock and futex implementation here have very similar performance, because they have a minimal number memory instructions.

Musl's internal lock implementation actually looses for the unlock. It has four different memory instructions. Two of them originate from the internal macro a_store, which needs a synchronization of the mov instruction to avoid reordering on the processor. It results in two instructions:

mov eax, (%rdi)
lock orl (%rsp)

We observed an improvement whe a_store is implemented directly with on atomic instruction, e.g.

xchg %eax, (%rdi)

Such a change could perhaps be integrated into musl at a later stage.

The mutex implementations have two memory instructions for the unlock functions. One movl from memory to CPU for a waiters counter, and one xchg to manipulate the lock itself.

Our implementation attempts to combine the two instructions for unlock into one: on the fast path we only need one atomic addition. By that we are better than the mutex, we save one movl instruction for the waiters counter. We may be a bit worse than the spinlock, because that only has a write to memory to perform, and doesn't need information from memory to be returned to the CPU.

If you have the sources of musl the easiest is to integrate the library directly into the libc. To achieve that just do

make MUSL=your/path/to/musl musl

This copies all necessary code to a subdirectory of your musl path. Then just compile and install musl as you would do usually.

By default this chooses the futex implementation of the generic lock function.

If you want to compile a standalone libstdatomic.a library archive file, you first need to compile one object file that encapsulates all system calls to futex. This can be done with the same command as above

make MUSL=your/path/to/musl musl

and then

make MUSL=your/path/to/musl libstdatomic.a

This will compile the one file inside the musl src hierarchy and then assemble all to one "standalone" library.