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大小相同，我认为在原子变量中不会存储锁。

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

- curiousguy12

---

你是否尝试使用比16字节更大的类型？我对x86架构不是非常熟悉，但如果它有一个单独用于16字节的CAS指令，那么就不需要显式锁定了，这一点也不奇怪。 - Xirema

如果是这样，我会期望 is_lock_free() 的返回值为 true。 - François Andrieux

在x86-64 Linux上，gcc / clang如果可用，则使用lock cmpxchg16b指令，但是gcc7及更高版本仍然返回is_lock_free为false，即使从技术上讲它是正确的。但是纯负载和纯存储很慢，且纯负载彼此竞争。有关此设计决策的更多详细信息，请参阅在升级到MacPorts gcc 7.3后，is_lock_free()返回false的链接。 - Peter Cordes

@James 不，这样做违背了 std::atomic 的目的。 - benjarobin

根据 https://github.com/llvm-mirror/compiler-rt/blob/master/lib/builtins/atomic.c#L109 ，clang（也可能是gcc）使用原子变量的地址作为哈希映射中锁的索引。 - user4442671

Answer 1

通常的实现是一个互斥锁的哈希表（甚至只是简单的自旋锁，没有回退到操作系统辅助的睡眠/唤醒），使用原子对象的地址作为关键字。哈希函数可能很简单，只需将地址的低位用作幂为2大小的数组的索引，但@Frank的答案显示LLVM的std::atomic实现会在一些高位上进行异或，这样在由大的2的幂分隔的对象时就不会自动获得别名（这比任何其他随机排列更常见）。

我认为（但不确定）g++和clang++是ABI兼容的；即它们使用相同的哈希函数和表，因此它们会就哪个锁序列化访问哪个对象达成一致。所有锁定都在libatomic中完成，所以如果动态链接libatomic，则调用__atomic_store_16的同一程序内的所有代码都将使用相同的实现；clang++和g++绝对同意调用哪些函数名称，这已经足够了。（但请注意，只有共享内存中的无锁原子对象将起作用：每个进程都有其自己的锁哈希表。在正常CPU体系结构上，无锁对象应该（而实际上确实）在共享内存中正常工作，即使该区域映射到不同的地址。）

哈希冲突意味着两个原子对象可能共享同一个锁。这不是一个正确性问题，但它可能是一个性能问题：与各自争夺两个不同对象的两对线程相比，你可能会有4个线程竞争访问任一对象。据信这很罕见，通常你的原子对象都针对你关心的平台是无锁的。但大多数时候你不会真的很不走运，基本上还是可以的。

死锁并不可能发生，因为没有任何std::atomic函数尝试同时获取两个对象的锁。 因此，在持有这些锁时，获取锁的库代码从不尝试获取另一个锁。 额外的争用/串行化不是正确性问题，只是性能问题。

---

x86-64 16字节对象在GCC和MSVC之间的区别：

作为一种黑客方式，编译器可以使用lock cmpxchg16b来实现16字节原子加载/存储以及实际的读取修改写入操作。

这比锁定更好，但与8字节原子对象相比性能差（例如，纯负载与其他负载争用）。 这是唯一文档记录的安全方式，以原子方式处理任何16字节¹数据。

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

在gcc6及更早版本中，当您使用-mcx16编译时，会内联lock cmpxchg16b（遗憾的是，cmpxchg16b对于x86-64不是基线;第一代AMD K8 CPU缺少它）。

gcc7决定总是调用libatomic并永远不将16字节对象报告为无锁定状态，即使在支持该指令的机器上，libatomic函数仍将使用lock cmpxchg16b。 请参见升级到MacPorts gcc 7.3后is_lock_free()返回false。 解释这种更改的gcc邮件列表消息在此处。

您可以使用一个联合技巧来在x86-64上使用gcc/clang实现一个相对便宜的ABA指针和计数器：如何使用c++11 CAS实现ABA计数器？。对于指针和计数器的更新，可以使用lock cmpxchg16b，但对于仅指针的简单mov加载。但是，这仅适用于16字节对象实际上是自由锁定的情况下使用lock cmpxchg16b。

---

注脚1：实际上，某些（但不是所有）x86微架构上的movdqa 16字节加载/存储在实践中是原子的，而且没有可靠或记录的方法来检测何时它可用。请参见为什么在x86上自然对齐变量的整数赋值是原子的？，以及SSE指令：哪些CPU可以执行原子16B内存操作？，以了解一个例子，在该例子中，K10 Opteron仅在具有HyperTransport的套接字之间在8B边界处显示撕裂。

因此，编译器编写人员必须谨慎行事，并且不能像在32位代码中使用SSE2 movq一样使用movdqa。如果CPU供应商能够为某些微架构文档化一些保证或添加CPUID功能位，以支持基于SSE、AVX和AVX512对齐的原子16、32和64字节矢量加载/存储，那将是很好的。也许哪种移动电话厂商可以在固件上禁用在使用不传输整个缓存线原子的特殊一致性胶水芯片的时尚多插座机器上的movdqa。

- Peter Cordes

---

挑剔一点：LLVM的实现比使用低位作为索引要复杂得多/巧妙得多。 - user4442671

@Frank：谢谢，已修复。我看到了移位和掩码，但当然在更复杂的哈希函数中也会发生这种情况，所以我应该继续寻找一些高位的异或操作。这更有意义；大的2的幂步长在计算机程序中并不罕见，而朴素的低位将会导致冲突。 - Peter Cordes

Answer 2

最简单的回答这类问题的方法通常是查看生成的汇编代码，然后从那里开始分析。

编译以下代码（我将您的结构体放大以避免狡猾的编译器花招）：

#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会产生以下结果：请查看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);
}

这是我们的解释：原子地址用于生成哈希键，以选择预先分配的锁。

- user4442671

---

你可以使用https://godbolt.org/来轻松生成和分享各种编译器的汇编代码。 - François Andrieux

我知道。我个人更喜欢在评论中使用godbolt链接，但在撰写答案时实际上会复制并粘贴结果，以便它们保持完全自包含（如果汇编代码足够短）。 - user4442671

Answer 3

根据C++标准中的29.5.9:

注意：原子特化的表示不需要与其对应的参数类型具有相同的大小。尽可能使特化具有相同的大小，因为这可以减少移植现有代码所需的工作量。—注

最好将原子的大小与其参数类型的大小相同，但并非必须如此。要实现这一点，可以通过避免锁或将锁存储在单独的结构中来实现。正如其他答案已经清楚解释的那样，哈希表用于保存所有锁。这是存储所有正在使用的原子对象的任意数量的锁的最高效的内存方式。

- Hadi Brais

---

不在每个对象内放置锁的另一个原因是与C11原子操作的互操作性问题，其中静态初始化是一个问题。C11标准定义了一个ATOMIC_VAR_INIT宏（对于复合类型不起作用），还要求原子对象的静态零初始化有效。而C11没有提供任何析构函数来释放每个对象锁中的操作系统资源。请参见https://developers.redhat.com/blog/2016/01/14/toward-a-better-use-of-c11-atomics-part-1/以了解在C11标准中发现的一些问题的讨论。 - Peter Cordes