c++ - 真正测试std::atomic是否无锁

Question

由于std::atomic::is_lock_free()可能无法真正反射(reflect)现实情况[ref]，因此我正在考虑编写真正的运行时测试。但是，当我着手解决这个问题时，我发现这并不是我认为的微不足道的任务。我想知道是否有一些聪明的主意可以做到这一点。

Answer 1

除了性能以外，该标准并不能保证您可以说出任何方法。这或多或少是关键。
如果愿意引入某些特定于平台的UB，则可以执行类似将atomic<int64_t> *转换为volatile int64_t*的操作，并查看是否在其他线程读取对象时观察到“撕裂”。 (When to use volatile with multi threading?-通常从不，但是真正的硬件在运行线程的内核之间具有一致的缓存，因此普通的asm加载/存储基本上就像是原子的放松。)
如果此测试成功(即普通的C++类型自然是原子的，仅带有volatile)，这将告诉您任何理智的编译器都将使其廉价地实现无锁。但是，如果失败了，它不会告诉您太多。该类型的无锁原子可能仅比用于加载/存储的普通版本稍微贵一点，或者编译器可能根本没有使其成为无锁。例如在32位x86上，无锁int64_t仅使用少量开销即可有效(使用SSE2或x87)，但是volatile int64_t*将使用两个单独的4字节整数加载产生撕裂，或存储大多数编译器对其进行编译的方式。
在任何特定平台/目标体系结构上，您都可以在调试器中单步执行代码，并查看运行的asm指令。 (包括进入像__atomic_store_16这样的libatomic函数调用)。这是唯一100％可靠的方法。 (另请参阅ISA文档，以检查不同指令的原子性保证，例如，在什么条件下是否保证ARM加载/存储对。)
(有趣的事实:gcc7 with statically linked libatomic可能始终对x86-64上的16个字节的对象使用锁定，因为它没有机会在动态链接时进行运行时CPU检测，而没有机会使用支持glibc的相同机制在支持它的CPU上使用lock cmpxchg16b用于为当前系统选择最佳的memcpy/strchr实现。)

您可以轻而易举地寻求性能差异(例如，具有多个读取器的可伸缩性)，但是x86-64 lock cmpxchg16b无法缩放1。 与8个字节或更窄的原子对象where pure asm loads are atomic and can be used不同，多个阅读器相互竞争。 lock cmpxchg16b在执行之前获得对缓存行的排他访问；在无法实现.load()的情况下滥用原子加载旧值的副作用要比仅编译为常规加载指令的8字节原子加载严重得多。
这是gcc7决定停止在in the GCC mailing list message about the change you're asking about中描述的16字节对象上对is_lock_free()返回true的部分原因。
还要注意，在32位x86上的clang使用lock cmpxchg8b来实现std::atomic<int64_t>，就像在64位模式下对16字节对象一样。因此，您也会发现它缺乏并行读取缩放。 (https://bugs.llvm.org/show_bug.cgi?id=33109)

使用锁定的std::atomic<>实现通常仍不会通过在每个对象中包含lock字节或单词来使对象变大。它将改变ABI，但是无锁与锁定已经是ABI的区别。我认为该标准允许这样做，但是即使在无锁的情况下，怪异的硬件也可能在对象中需要额外的字节。无论如何，sizeof(atomic<T>) == sizeof(T)都不会告诉您任何信息。如果更大，则很可能是您的实现中添加了互斥锁，但是如果不检查asm，就无法确定。 (如果大小不是2的幂，则可能会扩大它以进行对齐。)
(在C11中，在对象中包括锁的范围要小得多:即使在最小的初始化(例如，静态地为0)且没有析构函数的情况下，它也必须起作用，并且没有析构函数。编译器/ABI通常希望其C stdatomic.h原子与它们的C++兼容。 std::atomic原子。)
正常的机制是将原子对象的地址用作锁全局哈希表的键。别名/冲突和共享同一锁的两个对象是额外的争用，但不是正确性问题。这些锁仅从库函数中获取/释放，而不是在持有其他此类锁的同时释放，因此它无法创建死锁。
您可以通过使用两个不同进程之间的共享内存来检测到此情况(因此每个进程将具有自己的锁哈希表)。
Is C++11 atomic<T> usable with mmap?

检查std::atomic<T>与T的大小是否相同(因此该锁不在对象本身中)。

映射来自两个单独进程的共享内存段，这些进程否则不会共享任何地址空间。在每个进程中将其映射到其他基址都没有关系。

存储一个进程中的全一和全零之类的模式，而从另一进程中读取(并寻找撕裂)。与我上面volatile建议的内容相同。

还要测试原子增量:让每个线程以1G增量递增，并每次检查结果是否为2G。即使纯负载和纯存储自然是原子的(撕裂测试)，诸如fetch_add/operator++之类的读-修改-写操作也需要特殊支持:Can num++ be atomic for 'int num'?

从C++ 11标准开始，目的是对于无锁对象仍然应该是原子的。它也可能适用于非无锁对象(如果它们将锁嵌入对象中)，这就是为什么您必须通过检查sizeof()来排除这种情况的原因。

To facilitate inter-process communication via shared memory, it is our intent that lock-free operations also be address-free. That is, atomic operations on the same memory location via two different addresses will communicate atomically. The implementation shall not depend on any per-process state.

如果您看到两个进程之间存在裂痕，则说明该对象不是无锁的(至少不是C++ 11的预期目的，也不是您在普通共享内存CPU上所期望的方式。)
我不确定，如果进程不必共享除包含原子对象2的1页之外的任何地址空间，为什么不使用地址就很重要。 (当然，C++ 11完全不需要实现使用页面。或者实现可能会将锁的哈希表放在每个页面的顶部或底部？在这种情况下，使用依赖于超出页面偏移量的地址位完全是愚蠢的。)
无论如何，取决于许多关于计算机如何工作的假设，这些假设在所有普通CPU上都是正确的，但C++却没有。 如果您关心的实现是在标准OS下的主流CPU(例如x86或ARM)上进行的，则此测试方法应相当准确，并且可以作为仅读取asm的替代方法。 在编译时自动执行并不是很实际的事情，但是有可能像这样自动化测试并将其放入构建脚本中，这与读取asm不同。

脚注1:x86上的16字节原子
不支持使用SSE指令的16字节原子加载/存储的x86硬件文档。实际上，许多现代CPU确实具有原子movaps加载/存储，但是在Intel/AMD手册中并不能保证在奔腾及以后的8字节x87/MMX/SSE加载/存储中会采用这种方式。由于无法检测到哪些CPU/没有原子的128位操作(除了lock cmpxchg16b)，因此编译器编写者无法安全地使用它们。
请参阅SSE instructions: which CPUs can do atomic 16B memory operations?以获取令人讨厌的极端情况:在K10上进行的测试表明，对齐的xmm加载/存储显示同一套接字上的线程之间没有撕裂，但是不同套接字上的线程却很少发生撕裂，因为HyperTransport显然仅提供8字节对象的最低x86原子性保证。 。 (如果lock cmpxchg16b在这样的系统上更昂贵，则为IDK。)
没有供应商的公开保证，我们也无法确定奇怪的微体系结构极端案例。在一个简单的测试中，没有一个线程编写模式而另一个线程进行撕裂的尝试是一个很好的证据，但是在某些特殊情况下，CPU设计师总是决定以不同于正常的方式处理某些事情，这总是有可能有所不同的。

指针+计数器结构(只读访问仅需要指针)可能很便宜，但是当前的编译器需要union hack才能使其仅对对象的前半部分执行8字节的原子加载。 How can I implement ABA counter with c++11 CAS?。对于ABA计数器，通常无论如何都要用CAS更新它，因此缺少16字节的原子纯存储不是问题。
64位模式下的ILP32 ABI(32位指针)(例如Linux's x32 ABI或AArch64的ILP32 ABI)意味着指针+整数只能容纳8个字节，但整数寄存器的宽度仍为8个字节。与使用指针为8字节的完整64位模式相比，使用指针+计数器原子对象的效率更高。

脚注2:无地址
我认为“无地址”一词是一个独立的主张，而不是不依赖于任何按进程的状态。据我了解，这意味着正确性不依赖于两个线程在相同的内存位置使用相同的地址。但是，如果正确性还取决于它们共享同一个全局哈希表(IDK，为什么将对象的地址存储在对象本身中会有所帮助)，则只有在同一个对象中可以为同一对象拥有多个地址的情况下，这才有意义过程。在x86的实模式分段模型中，这是可能的，其中20位线性地址空间使用32位segment:offset寻址。 (针对16位x86的实际C实现将分段公开给程序员；可以将其隐藏在C的规则后面，但性能不高。)
虚拟内存也是可能的:同一过程中同一物理页面到不同虚拟地址的两个映射是可能的，但是很奇怪。可能使用或可能不使用相同的锁，具体取决于哈希函数是否使用页面偏移量以上的任何地址位。
(代表页面内偏移量的地址低位对于每个映射都是相同的。即，这些位的虚拟到物理转换是空操作，这就是VIPT caches are usually designed to take advantage of that to get speed without aliasing的原因。)
因此，即使非锁定对象使用单独的全局哈希表，而不是向原子对象添加互斥锁，也可以在单个进程中实现无地址锁定。但这将是非常不寻常的情况。使用虚拟内存技巧为同一进程内的同一变量创建两个地址(在线程之间共享其所有地址空间)是极为罕见的。进程之间共享内存中的原子对象更为常见。 (我可能会误解“无地址”的含义；可能是“无地址空间”，即不依赖于共享其他地址。)