Where is the lock for a std::atomic?

Question

If a data structure has multiple elements in it, the atomic version of it cannot (always) be lock-free. I was told that this is true for larger types because the CPU can not atomically change the data without using some sort of lock.

for example:

#include <iostream> #include <atomic>  struct foo {     double a;     double b; };  std::atomic<foo> var;  int main() {     std::cout << var.is_lock_free() << std::endl;     std::cout << sizeof(foo) << std::endl;     std::cout << sizeof(var) << std::endl; } 

the output (Linux/gcc) is:

0 16 16 

Since the atomic and foo are the same size, I don't think a lock is stored in the atomic.

My question is:
If an atomic variable uses a lock, where is it stored and what does that mean for multiple instances of that variable ?

Answer 1

The usual implementation is a hash-table of mutexes (or even just simple spinlocks without a fallback to OS-assisted sleep/wakeup), using the address of the atomic object as a key. The hash function might be as simple as just using the low bits of the address as an index into a power-of-2 sized array, but @Frank's answer shows LLVM's std::atomic implementation does XOR in some higher bits so you don't automatically get aliasing when objects are separated by a large power of 2 (which is more common than any other random arrangement).

I think (but I'm not sure) that g++ and clang++ are ABI-compatible; i.e. that they use the same hash function and table, so they agree on which lock serializes access to which object. The locking is all done in libatomic, though, so if you dynamically link libatomic then all code inside the same program that calls __atomic_store_16 will use the same implementation; clang++ and g++ definitely agree on which function names to call, and that's enough. (But note that only lock-free atomic objects in shared memory between different processes will work: each process has its own hash table of locks. Lock-free objects are supposed to (and in fact do) Just Work in shared memory on normal CPU architectures, even if the region is mapped to different addresses.)

Hash collisions mean that two atomic objects might share the same lock. This is not a correctness problem, but it could be a performance problem: instead of two pairs of threads separately contending with each other for two different objects, you could have all 4 threads contending for access to either object. Presumably that's unusual, and usually you aim for your atomic objects to be lock-free on the platforms you care about. But most of the time you don't get really unlucky, and it's basically fine.

Deadlocks aren't possible because there aren't any std::atomic functions that try to take the lock on two objects at once. So the library code that takes the lock never tries to take another lock while holding one of these locks. Extra contention / serialization is not a correctness problem, just performance.

---

x86-64 16-byte objects with GCC vs. MSVC:

As a hack, compilers can use lock cmpxchg16b to implement 16-byte atomic load/store, as well as actual read-modify-write operations.

This is better than locking, but has bad performance compared to 8-byte atomic objects (e.g. pure loads contend with other loads). It's the only documented safe way to atomically do anything with 16 bytes¹.

AFAIK, MSVC never uses lock cmpxchg16b for 16-byte objects, and they're basically the same as a 24 or 32 byte object.

gcc6 and earlier inlined lock cmpxchg16b when you compile with -mcx16 (cmpxchg16b unfortunately isn't baseline for x86-64; first-gen AMD K8 CPUs are missing it.)

gcc7 decided to always call libatomic and never report 16-byte objects as lock-free, even though libatomic functions would still use lock cmpxchg16b on machines where the instruction is available. See is_lock_free() returned false after upgrading to MacPorts gcc 7.3. The gcc mailing list message explaining this change is here.

You can use a union hack to get a reasonably cheap ABA pointer+counter on x86-64 with gcc/clang: How can I implement ABA counter with c++11 CAS?. lock cmpxchg16b for updates of both pointer and counter, but simple mov loads of just the pointer. This only works if the 16-byte object is actually lock-free using lock cmpxchg16b, though.

---

Footnote 1: movdqa 16-byte load/store is atomic in practice on some (but not all) x86 microarchitectures, and there's no reliable or documented way to detect when it's usable. See Why is integer assignment on a naturally aligned variable atomic on x86?, and SSE instructions: which CPUs can do atomic 16B memory operations? for an example where K10 Opteron shows tearing at 8B boundaries only between sockets with HyperTransport.

So compiler writers have to err on the side of caution and can't use movdqa the way they use SSE2 movq for 8-byte atomic load/store in 32-bit code. It would be great if CPU vendors could document some guarantees for some microarchitectures, or add CPUID feature bits for atomic 16, 32, and 64-byte aligned vector load/store (with SSE, AVX, and AVX512). Maybe which mobo vendors could disable in firmware on funky many-socket machines that use special coherency glue chips that don't transfer whole cache lines atomically.