std::atomic 的锁在哪里？

Question

如果一个数据结构中有多个元素，它的原子版本不能（总是）是无锁的。有人告诉我这对于较大的类型是正确的，因为 CPU 不能在不使用某种锁的情况下自动更改数据。

例如：

#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;
}

输出 (Linux/gcc) 是：

0
16
16

由于原子和foo大小相同，我认为原子中没有存储锁。

我的问题是：
如果原子变量使用锁，它存储在哪里，对于该变量的多个实例意味着什么？

Answer 1

回答此类问题的最简单方法通常是只查看生成的程序集并从那里获取它。

编译以下内容（我将你的结构变大以避开狡猾的编译器恶作剧）：

#include <atomic>

struct foo {
    double a;
    double b;
    double c;
    double d;
    double e;
};

std::atomic<foo> var;

void bar()
{
    var.store(foo{1.0,2.0,1.0,2.0,1.0});
}

在 clang 5.0.0 中，在 -O3 下产生以下内容：see on godbolt

bar(): # @bar()
  sub rsp, 40
  movaps xmm0, xmmword ptr [rip + .LCPI0_0] # xmm0 = [1.000000e+00,2.000000e+00]
  movaps xmmword ptr [rsp], xmm0
  movaps xmmword ptr [rsp + 16], xmm0
  movabs rax, 4607182418800017408
  mov qword ptr [rsp + 32], rax
  mov rdx, rsp
  mov edi, 40
  mov esi, var
  mov ecx, 5
  call __atomic_store

很好，编译器委托给了一个内在函数 (__atomic_store)，这并没有告诉我们这里到底发生了什么。但是，由于编译器是开源的，我们很容易找到内在的实现（我在https://github.com/llvm-mirror/compiler-rt/blob/master/lib/builtins/atomic.c找到了）：

void __atomic_store_c(int size, void *dest, void *src, int model) {
#define LOCK_FREE_ACTION(type) \
    __c11_atomic_store((_Atomic(type)*)dest, *(type*)dest, model);\
    return;
  LOCK_FREE_CASES();
#undef LOCK_FREE_ACTION
  Lock *l = lock_for_pointer(dest);
  lock(l);
  memcpy(dest, src, size);
  unlock(l);
}

lock_for_pointer()好像有神奇的事情发生了，一起来看看吧:

static __inline Lock *lock_for_pointer(void *ptr) {
  intptr_t hash = (intptr_t)ptr;
  // Disregard the lowest 4 bits.  We want all values that may be part of the
  // same memory operation to hash to the same value and therefore use the same
  // lock.  
  hash >>= 4;
  // Use the next bits as the basis for the hash
  intptr_t low = hash & SPINLOCK_MASK;
  // 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);
}

这是我们的解释：原子地址用于为 select 预分配锁生成散列键。

Answer 2

通常的实现是互斥体的哈希-table（或者甚至只是简单的自旋锁，没有退回到OS-辅助sleep/wakeup），使用原子对象的地址作为键。哈希函数可能就像使用地址的低位作为 2 的幂大小数组的索引一样简单，但是@Frank 的回答显示 LLVM 的 std::atomic 实现在一些更高的位上进行异或，所以你不' 当对象被 2 的大幂分开时（这比任何其他随机排列更常见），会自动出现锯齿。

我认为（但我不确定）g++ 和 clang++ 是 ABI 兼容的；也就是说，它们使用相同的散列函数和 table，因此它们就哪个锁序列化对哪个对象的访问达成一致。但是，锁定全部在 libatomic 中完成，因此如果您动态地 link libatomic 那么调用 __atomic_store_16 的同一程序中的所有代码将使用相同的实现； clang++ 和 g++ 在调用哪些函数名称上肯定一致，这就足够了。（但请注意，只有不同进程之间共享内存中的无锁原子对象才能工作：每个进程都有自己的锁散列 table。无锁对象应该（事实上也是如此）只需在普通 CPU 架构的共享内存中工作，即使该区域映射到不同的地址。）

散列冲突意味着两个原子对象可能共享同一个锁。这不是正确性问题，但可能是性能问题：不是两对线程分别为两个不同的对象相互竞争，而是让所有 4 个线程竞争访问任一对象。大概这是不寻常的，通常你的目标是你的原子对象在你关心的平台上是无锁的。但大多数时候你不会真的倒霉，基本上就没事了。

不可能出现死锁，因为没有任何std::atomic 函数试图同时锁定两个对象。因此，获取锁的库代码永远不会在持有其中一个锁的同时尝试获取另一个锁。额外的争用/序列化不是正确性问题，只是性能问题。

x86-64 16 字节对象与 GCC 对比 MSVC:

作为 hack，编译器可以使用 lock cmpxchg16b 来实现 16 字节原子 load/store，以及实际的读取-修改-写入操作。

这比锁定好，但与 8 字节原子对象相比性能较差（例如，纯加载与其他加载竞争）。这是唯一记录在案的安全方法，可以原子地执行任何 16 字节的操作¹.

据我所知，MSVC 从不对 16 字节对象使用 lock cmpxchg16b，它们与 24 或 32 字节对象基本相同。

当您使用 -mcx16 编译时，

gcc6 和更早版本内联 lock cmpxchg16b（不幸的是，cmpxchg16b 不是 x86-64 的基线；第一代 AMD K8 CPUs 缺少它。 )

gcc7 决定始终调用 libatomic 并且从不将 16 字节对象报告为无锁，即使 libatomic 函数仍会在指令可用的机器上使用 lock cmpxchg16b。参见 . The gcc mailing list message explaining this change is here。

您可以使用 union hack 在 x86-64 上使用 gcc/clang: 获得相当便宜的 ABA 指针+计数器。 lock cmpxchg16b 用于指针和计数器的更新，但简单 mov 仅加载指针。不过，这仅在 16 字节对象实际上使用 lock cmpxchg16b 无锁时有效。

脚注 1：movdqa 16 字节 load/store 在某些实践中是原子的（但不是 all) x86 微架构，并且没有可靠的或有记录的方法来检测它何时可用。请参阅 , and SSE instructions: which CPUs can do atomic 16B memory operations? 示例，其中 K10 Opteron 仅在具有 HyperTransport 的套接字之间显示 8B 边界撕裂。

因此编译器编写者必须谨慎行事，不能像在 32 位中使用 SSE2 movq 用于 8 字节原子 load/store 那样使用 movdqa代码。如果 CPU 供应商可以记录某些微体系结构的一些保证，或者为原子 16、32 和 64 字节对齐向量 load/store 添加 CPUID 特征位（使用 SSE， AVX 和 AVX512）。也许哪个主板供应商可以在时髦的多路机器上禁用固件，这些机器使用特殊的一致性粘合芯片，不会自动传输整个缓存行。

Answer 3

来自 C++ 标准的 29.5.9：

Note: The representation of an atomic specialization need not have the same size as its corresponding argument type. Specializations should have the same size whenever possible, as this reduces the effort required to port existing code. — end note

最好使原子的大小与其参数类型的大小相同，尽管这不是必需的。实现此目的的方法是避免使用锁或将锁存储在单独的结构中。正如其他答案已经解释清楚的那样，哈希 table 用于保存所有锁。这是为所有正在使用的原子对象存储任意数量锁的最有效内存方式。

std::atomic 的锁在哪里？

Where is the lock for a std::atomic?

c++

x86

atomic

c++11

stdatomic