如何用c ++ 11 CAS实现ABA计数器？
我正在实现基于此algorithm的无锁队列，该algorithm使用计数器来解决ABA问题。 但是我不知道如何用c ++ 11 CAS来实现这个计数器。 例如，从algorithm：
E9: if CAS(&tail.ptr->next, next, <node, next.count+1>) 这是一个primefaces操作，意思是如果tail.ptr->next等于next ，则让tail.ptr->next指向node ， 同时（primefaces地）使next.count+1 。 但是，使用C ++ 11 CAS，我只能实现：
std::atomic_compare_exchange_weak(&tail.ptr->next, next, node);
不能使next.count+1同时发生。
要用一个primefaces操作一次自动修改两件事情，你需要把它们放在相邻的内存中，例如在一个两元结构中。 然后你可以使用std::atomic<my_struct>来获得gcc在x86-64上发出lock cmpxchg16b 。
你不需要内联asm，为了避免这个问题，值得一些C ++语法的痛苦。 https://gcc.gnu.org/wiki/DontUseInlineAsm 。
不幸的是，对于目前的编译器，你需要使用一个union来获得有效的代码来读取这个对中的一个。 尽pipe我们只需要一个成员，但是对结构进行primefaces加载然后只使用一个成员的“显而易见”的方式仍然导致lock cmpxchg16b读取整个结构。 我相信，一个正常的64b的指针负载仍然会正确地实现在x86上的获取内存sorting语义（以及primefaces性），但是当前的编译器不会为std::memory_order_relaxed做这样的优化，所以我们把戏他们与工会合并。
（提交GCC臭虫80835关于这个。TODO ：如果这是一个有用的想法clang相同。）
清单：
- 确保您的编译器正在生成有效代码，用于在只读情况下加载一个成员，而不是该对的
lock cmpxchg16b。 例如使用联合。 - 确保您的编译器保证在编写不同的联合成员之后访问联合的一个成员在该实现中具有明确定义的行为。 在C99中，联合types双击是合法的（所以这应该适用于C11
stdatomic），但是它是ISO C ++ 11中的UB 。 然而，在C ++的GNU方言中，这是合法的（由gcc，clang和ICC等支持）。 - 确保你的对象是16Balignment的 ，或者8Balignment的32位指针。 更一般地说，
alignas(2*sizeof(void*))应该可以工作。 未alignment的lock指令在x86上可能非常慢，特别是如果它们跨越caching线边界。 如果对象没有alignment，clang3.8甚至会把它编译成一个库调用。 -
使用
-mcx16编译 x86-64版本。 最早的x86-64 CPU（AMD K8）不支持cmpxchg16b，但是之后的所有应用程序都应该支持。 没有-mcx16，你会得到一个库函数调用（可能使用全局锁）。 相当于32位的cmpxchg8b已经足够老，现代编译器就可以支持它了。 （可以使用SSE，MMX甚至x87做64bprimefaces加载/存储，所以在读取一个成员时，使用联合对于良好的性能不那么重要）。 -
确保指针+ uintptr_tprimefaces对象是无锁的。 这对于x32和32位ABIs（8B对象）来说是非常有保证的，但是对于16B对象来说则不是这样。 例如MSVC使用x86-64的锁。
gcc7和更高版本将调用libatomic而不是内
lock cmpxchg16b，并将从atomic_is_lock_free返回false（ 由于速度太慢，这不是用户期望的is_lock_free意味着什么 ），但至less现在libatomic实现仍然在目标上使用lock cmpxchg16b该指令可用。 （对于只读的primefaces对象甚至可以是段错误，所以实际上并不理想。）
下面是一个CAS重试循环的代码示例，编译为asm，看起来是正确的，我认为没有UB或其他不安全的C ++实现允许联合types的双关语。 它是用C风格编写的（非成员函数等），但是如果你写了成员函数也是一样的。
在Godbolt编译器资源pipe理器中查看来自gcc6.3的 asm输出的代码。 使用-m32 ，使用cmpxchg8b的方式与使用cmpxchg8b的64位代码cmpxchg16b 。 使用-mx32 （长模式下的32位指针），它可以简单地使用一个64位的cmpxchg ，以及一般的64位整数加载，以一个primefaces负载抓取两个成员。
这是可移植的C ++ 11（除了union-punning），没有任何x86特定的。 尽pipe如此，CAS只能反对两个指针的大小。 例如，它可以编译为对ARM / ARM64和MIPS64的__atomic_compare_exchange_16库函数的调用，如Godbolt所示。
它不会在MSVC上进行编译， atomic<counted_ptr>大于counted_ptr_separate ，所以static_assert捕获它。 推测MSVC在primefaces对象中包含一个locking成员。
#include <atomic> #include <stdint.h> using namespace std; struct node { // This alignas is essential for clang to use cmpxchg16b instead of a function call // Apparently just having it on the union member isn't enough. struct alignas(2*sizeof(node*)) counted_ptr { node * ptr; uintptr_t count; // use pointer-sized integers to avoid padding }; // hack to allow reading just the pointer without lock-cmpxchg16b, // but still without any C++ data race struct counted_ptr_separate { atomic<node *> ptr; atomic<uintptr_t> count_separate; // var name emphasizes that accessing this way isn't atomic with ptr }; static_assert(sizeof(atomic<counted_ptr>) == sizeof(counted_ptr_separate), "atomic<counted_ptr> isn't the same size as the separate version; union type-punning will be bogus"); //static_assert(std::atomic<counted_ptr>{}.is_lock_free()); union { // anonymous union: the members are directly part of struct node alignas(2*sizeof(node*)) atomic<counted_ptr> next_and_count; counted_ptr_separate next; }; // TODO: write member functions to read next.ptr or read/write next_and_count int data[4]; }; // make sure read-only access is efficient. node *follow(node *p) { // good asm, just a mov load return p->next.ptr.load(memory_order_acquire); } node *follow_nounion(node *p) { // really bad asm, using cmpxchg16b to load the whole thing return p->next_and_count.load(memory_order_acquire).ptr; } void update_next(node &target, node *desired) { // read the old value efficiently to avoid overhead for the no-contention case // tearing (or stale data from a relaxed load) will just lead to a retry node::counted_ptr expected = { target.next.ptr.load(memory_order_relaxed), target.next.count_separate.load(memory_order_relaxed) }; bool success; do { node::counted_ptr newval = { desired, expected.count + 1 }; // x86-64: compiles to cmpxchg16b success = target.next_and_count.compare_exchange_weak( expected, newval, memory_order_acq_rel); // updates exected on failure } while( !success ); }
铛4.0 -O3 -mcx16的asm输出是：
update_next(node&, node*): push rbx # cmpxchg16b uses rbx implicitly so it has to be saved/restored mov rbx, rsi mov rax, qword ptr [rdi] # load the pointer mov rdx, qword ptr [rdi + 8] # load the counter .LBB2_1: # =>This Inner Loop Header: Depth=1 lea rcx, [rdx + 1] lock cmpxchg16b xmmword ptr [rdi] jne .LBB2_1 pop rbx ret
海湾合作委员会做一些笨重的存储/重新加载，但基本上是相同的逻辑。
follow(node*)编译为mov rax, [rdi] / ret ，所以对指针的只读访问就像它应该是便宜的，这要感谢联合黑客。
它的确依赖于通过一个成员编写一个联合，并通过另一个成员来读取它，从而不使用lock cmpxchg16b来高效地读取指针 。 这保证在GNU C ++（和ISO C99 / C11）中工作，但不能在ISO C ++中工作。 许多其他的C ++编译器确实可以保证联合types的双击工作，但是即使没有，也可能仍然有效：我们总是使用std::atomic加载，它们必须假设值是asynchronous修改的。 所以我们应该避免类似混淆的问题，其中在通过另一个指针（或联合成员）写入值之后，寄存器中的值仍然被视为活动的。 但编译器认为是独立的事情的编译时重新sorting可能是一个问题。
在指针+计数器的primefacescmpxchg之后，primefaces地读取指针应该仍然会给你在x86上的获取/释放语义，但是我不认为ISO C ++提到了这一点。 我猜测一个广泛的发行版（作为compare_exchange_weak一部分将与大多数体系结构上的相同地址的较窄负载同步（就像它在x86上一样），但AFAIK C ++ std::atomic并不保证types-punning。
与指针+ ABA-计数器不相关，但可以用于使用联合的其他应用程序允许访问较大的primefaces对象的子集： 不要使用联合来允许primefaces存储只是指针或只是计数器 。 至less不是如果你关心与这个对的获取负载同步的话。 即使是强有序的x86也可以用一个更大的负载来重新sorting一个狭小的存储，这个负载完全包含它 。 一切仍然是primefaces，但是就内存sorting而言，你进入了奇怪的领域。
在x86-64上，一个primefaces16B的加载需要一个lock cmpxchg16b （这是一个完整的内存屏障，防止之前的窄存储在全局可见之后）。 但是如果你使用32位指针（或者32位数组索引），那么你可能会遇到一个问题，因为这两个部分都可以使用常规的64b加载。 而且我不知道在其他体系结构上可以看到什么问题，如果需要与其他线程同步，而不仅仅是primefaces性。
要了解有关std :: memory_order的更多信息 ，请参阅Jeff Preshing的优秀文章 。
