真正测试std::atomic是否无锁

由于std::atomic::is_lock_free()可能没有真正反映现实[ 参考 ],我正在考虑编写一个真正的运行时测试.然而,当我开始研究它时,我发现这不是一个我认为不可能完成的微不足道的任务.我想知道是否有一些聪明的想法可以做到这一点.

除了表演,标准不保证您能说出任何方式; 这或多或少都是重点.

如果你愿意推出一些特定于平台的UB,你可以做这样的事情蒙上了atomic *一个volatile int64_t*,看你是否遵守"撕裂"当另一个线程读取的对象.但失败在32位x86其中无锁是的int64_t效率只有少的开销(使用SSE2或的x87),但volatile int64_t*会产生使用两个分离的4个字节的存储方式大多数编译器编译它撕裂.

如果这个测试成功(即普通的C++类型只是自然原子volatile),那就告诉你任何理智的编译器都会非常便宜地锁定它.但如果它失败了,它就不会告诉你.该类型的无锁原子可能仅比加载/存储的普通版本略贵,或者编译器可能根本不使其无锁.

在任何特定的平台/目标体系结构上,您可以在调试器中单步执行代码,并查看运行的asm指令.(包括踩到类似libatomic函数的调用__atomic_store_16).这是唯一100%可靠的方式.

(有趣的事实:gcc7与静态链接libatomic可以一直使用锁定了对x86-64 16字节的对象,因为它没有机会做运行时的CPU检测在动态链接时,用lock cmpxchg16b在支持它的CPU,用glibc使用相同的机制为当前系统选择最佳的memcpy/strchr实现.)

您可以寻找性能差异(例如,具有多个读取器的可伸缩性),但x86-64 lock cmpxchg16b不能扩展¹. 多个读者彼此竞争,不同于8字节和更窄的原子对象,其中纯asm加载是原子的并且可以使用. lock cmpxchg16b在执行之前获取对高速缓存行的独占访问权; 滥用的原子装上未能实现旧值的副作用.load()是很多比编译成只是一个普通的加载指令的8个字节的原子负荷加重.

这就是gcc7决定停止is_lock_free()在16字节对象上返回true的部分原因,如GCC邮件列表消息中所描述的那样,您正在询问的更改.

另请注意,32位x86上的clang lock cmpxchg8b用于实现std::atomic,就像64位模式下的16字节对象一样.因此,您也会看到缺少并行读取缩放.(https://bugs.llvm.org/show_bug.cgi?id=33109)

std::atomic<>使用锁定的实现通常仍然不会通过lock在每个对象中包含一个字节或单词来使对象更大.它会改变ABI,但无锁与锁定已经是ABI的差异.标准允许这样,但奇怪的硬件可能需要在对象中额外的字节,即使在无锁时也是如此.无论如何,无论如何sizeof(atomic) == sizeof(T)都不会告诉你任何事情.如果它更大,那么您的实现最有可能添加了互斥锁,但是如果不检查asm,则无法确定.

通常的机制是使用原子对象的地址作为锁的全局哈希表的键.别名/冲突和共享同一个锁的两个对象是额外的争用,但不是正确性问题.这些锁仅从库函数中获取/释放,而不是在保存其他此类锁时,因此无法创建死锁.

您可以通过在两个不同进程之间使用共享内存来检测这一点(因此每个进程都有自己的锁定哈希表). C++ 11 atomic 可用于mmap吗？

检查std::atomic大小是否相同T(因此锁不在对象本身中).

映射来自两个单独进程的共享内存段,否则这些进程不共享任何地址空间.如果将其映射到每个进程中的不同基址,则无关紧要.

从一个进程中存储模式,如all-one和all-zero,同时从另一个进程读取(并寻找撕裂).与我volatile上面提到的相同.

还测试原子增量:让每个线程以1G为增量并每次检查结果是2G.即使纯粹的加载和纯存储是自然原子的(撕裂测试),像fetch_add/ operator++需要特殊支持的读取 - 修改 - 写入操作:对于"int num",num ++可以是原子的吗？

从C++ 11标准来看,目的是对于无锁对象,这应该仍然是原子的.它也适用于非无锁对象(如果它们将锁嵌入对象中),这就是为什么你必须通过检查来排除它sizeof().

为了通过共享内存促进进程间通信,我们的意图是无锁操作也是无地址的.也就是说,通过两个不同地址在同一存储器位置上的原子操作将以原子方式进行通信.实现不应依赖于任何每个进程的状态.

如果你看到两个进程之间发生撕裂,那么该对象不是无锁的(至少不是C++ 11的预期方式,而不是你在普通共享内存CPU上的预期方式.)

如果进程不必共享包含原子对象^2的 1页以外的任何地址空间,我不确定为什么无地址问题.(当然,C++ 11并不要求实现使用页面.或者实现可能会将锁的哈希表放在每个页面的顶部或底部？在这种情况下使用依赖于的哈希函数页面偏移之上的地址位将是完全愚蠢的.)

无论如何,这取决于很多关于计算机如何在所有正常CPU上工作的假设,但是C++没有做到这一点. 如果您关心的实现是在普通操作系统下的x86或ARM等主流CPU上,那么这种测试方法应该相当准确,可能只是读取asm的替代方法. 在编译时自动执行并不是非常实用的东西,但是可以自动执行这样的测试并将其放入构建脚本中,这与读取asm不同.

脚注1:x86上的16字节原子

没有x86硬件保证支持带有SSE指令的16字节原子加载/存储.在实践中,许多现代CPU确实具有原子movaps加载/存储,但在Intel/AMD手册中无法保证这与Pentium及更高版本上的8字节x87/MMX/SSE加载/存储的方式相同.并且无法检测哪些CPU具有/不具有原子128位操作(除了lock cmpxchg16b),因此编译器编写者无法安全地使用它们.

请参阅SSE指令:哪些CPU可以执行原子16B内存操作？对于一个令人讨厌的角落案例:在K10上进行的测试表明,对齐的xmm加载/存储显示同一套接字上的线程之间没有撕裂,但是不同套接字上的线程经历了罕见的撕裂,因为HyperTransport显然只给出了8字节对象的最小x86原子性保证.(IDK如果 lock cmpxchg16b在这样的系统上更贵.)

如果没有供应商发布的保证,我们也无法确定奇怪的微架构角落案例.在一个简单的测试中,一个线程写入模式和另一个读取缺乏撕裂是相当好的证据,但在某些特殊情况下,CPU设计者决定采用与正常情况不同的方式,总是可能会有所不同.

只读访问只需要指针的指针+计数器结构可能很便宜,但是当前的编译器需要union黑客才能让它们只执行对象前半部分的8字节原子负载. 如何用c ++ 11 CAS实现ABA计数器？.对于ABA计数器,您通常使用CAS更新它,因此缺少16字节原子纯存储不是问题.

一个ILP32 ABI(32位指针)在64位模式下(如Linux的的X32 ABI,或AArch64的ILP32 ABI)指指针+整数可以适合仅在8个字节,但整数寄存器仍然8个字节宽.这使得使用指针+计数器原子对象比使用指针为8个字节的完整64位模式更有效.

脚注2:无地址

我认为"无地址"一词是一个单独的声明,不依赖于任何每个进程的状态.据我了解,这意味着正确性不依赖于使用相同内存位置的相同地址的两个线程.但是如果正确性还取决于它们共享相同的全局哈希表(IDK为什么将对象的地址存储在对象本身中会有所帮助),那只会在同一个对象中有多个地址的情况下才有意义.处理.这在x86的实模式分段模型中是可能的,其中20位线性地址空间用32位段寻址:偏移.(对程序员进行16位x86暴露分段的实际C实现;将其隐藏在C规则之后是可能的但不是高性能.)

虚拟内存也是可能的:同一物理页面到同一进程中的不同虚拟地址的两次映射是可能的,但很奇怪.这可能会也可能不会使用相同的锁,具体取决于散列函数是否使用页面偏移量之上的任何地址位.(一个地址的低位,即表示一个页内的偏移,是相同的,每映射.即,虚拟到物理转换为那些位是一个空操作,这就是为什么VIPT高速缓存通常被设计成充分利用这一点在没有别名的情况下获得速度.)

因此,非锁定对象在单个进程中可能是无地址的,即使它使用单独的全局哈希表而不是向原子对象添加互斥锁.但这将是一个非常不寻常的情况; 在同一进程中为同一个变量创建两个地址并在线程之间共享其所有地址空间是非常罕见的.更常见的是进程之间共享内存中的原子对象.(我可能误解了"无地址"的含义;可能意味着"地址空间自由",即缺乏对共享其他地址的依赖.)