c++ - 如何使用 c++11 CAS 实现 ABA 计数器？

Question

我正在基于此实现一个无锁队列 algorithm ，它使用计数器来解决 ABA 问题。但我不知道如何用 c++11 CAS 实现这个计数器。例如，从算法:

E9:    if CAS(&tail.ptr->next, next, <node, next.count+1>)

这是一个原子操作，意思是如果 tail.ptr->next等于 next , 让 tail.ptr->next指向 node和 同时(原子)制作 next.count+1 .但是，使用C++11 CAS，我只能实现:

std::atomic_compare_exchange_weak(&tail.ptr->next, next, node);

不能做 next.count+1同时发生。

Answer 1

要使用单个原子操作一次原子地修改两件事，您需要将它们放在相邻的内存中，例如在一个两成员结构中。那么你可以使用std::atomic<my_struct>让 gcc 发出 lock cmpxchg16b 例如，在 x86-64 上。
为此，您不需要内联 asm，为了避免它，值得花一点 C++ 语法的痛苦。 https://gcc.gnu.org/wiki/DontUseInlineAsm .
不幸的是，对于当前的编译器，您需要使用 union获得仅读取一对的有效代码。对结构进行原子加载然后只使用一个成员的“明显”方式仍然会导致 lock cmpxchg16b即使我们只需要一个成员，也可以读取整个结构。 (慢得多，并且弄脏了缓存线，因此读者与其他读者竞争)。我相信指针的正常 64b 负载仍然可以正确实现 x86 上的获取内存排序语义(以及原子性)，但是当前的编译器即使对于 std::memory_order_relaxed 也不会进行这种优化。 ，所以我们用 union 来欺骗他们。
(提交 GCC bug 80835 关于这个。TODO:如果这是一个有用的想法，那么对于 clang 也是如此。)

list :

确保您的编译器生成有效的代码，以便在只读情况下仅加载一个成员，而不是 lock cmpxchg16b对。例如使用 union 。

确保您的编译器保证在编写不同的 union 成员后访问 union 的一个成员在该实现中具有明确定义的行为。 union 类型双关在 C99 中是合法的(所以这应该适用于 C11 stdatomic)，但它在 ISO C++11 中是 UB .但是，它在 C++ 的 GNU 方言中是合法的(由 gcc、clang 和 ICC 等支持)。

确保您的对象是 16B 对齐的 ，或 8B 对齐的 32 位指针。更一般地说，alignas(2*sizeof(void*))应该管用。未对齐 lock ed 指令在 x86 上可能非常慢，尤其是当它们跨越缓存线边界时。如果对象未对齐，clang3.8 甚至会将其编译为库调用。

编译 -mcx16 对于 x86-64 版本。 cmpxchg16b最早的 x86-64 CPU (AMD K8) 不支持，但之后的所有内容都应该支持。无 -mcx16 ，你会得到一个库函数调用(它可能使用全局锁)。 32 位等效项，cmpxchg8b , 已经足够现代编译器支持它了。 (并且可以使用 SSE、MMX 甚至 x87 来执行 64b 原子加载/存储，因此在读取一个成员时，使用 union 对于获得良好性能来说不太重要)。

确保指针+uintptr_t 原子对象是无锁的。这对于 x32 和 32 位 ABI(8B 对象)几乎是有保证的，但对于 16B 对象则不然。例如MSVC 使用 x86-64 的锁。
gcc7 及更高版本将调用 libatomic 而不是内联 lock cmpxchg16b ，将从 atomic_is_lock_free 返回 false ( for reasons including that it's so slow it's not what users expect is_lock_free to mean )，但至少现在 libatomic 实现仍然使用 lock cmpxchg16b在该指令可用的目标上。 (它甚至可以为只读原子对象出现段错误，所以它真的不理想。更重要的是，读取器与其他读取器争夺对缓存行的独占访问。这就是为什么我们要如此费力地避免 lock cmpxchg16b for当我们只想要一个 8 字节的一半时，这里的读取端。)

这是一个带有 CAS 重试循环的代码示例，它编译为看起来正确的 asm，我认为对于允许 union 类型双关语的实现来说，没有 UB 或其他不安全的 C++。它是用 C 风格编写的(非成员函数等)，但如果你编写成员函数，它会是一样的。
查看带有 asm 输出的代码 from gcc6.3 on the Godbolt compiler explorer .与 -m32 ，它使用 cmpxchg8b同样的方式 64 位代码使用 cmpxchg16b .与 -mx32 (长模式下的 32 位指针)它可以简单地使用 64 位 cmpxchg , 和正常的 64 位整数加载以在一个原子加载中获取两个成员。
这是可移植的 C++11( union 类型双关除外)，没有特定于 x86 的内容。但是，它仅对可以 CAS 两个指针大小的对象的目标有效。 例如它编译为对 __atomic_compare_exchange_16 的调用ARM/ARM64 和 MIPS64 的库函数，你可以在 Godbolt 上看到。
它不能在 MSVC 上编译，其中 atomic<counted_ptr>大于 counted_ptr_separate ，所以 static_assert捕获它。据推测，MSVC 在原子对象中包含一个锁成员。

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

来自 clang 4.0 的 asm 输出 -O3 -mcx16是:

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

gcc 做了一些笨重的存储/重新加载，但基本上是相同的逻辑。 follow(node*)编译为 mov rax, [rdi]/ ret ，因此对指针的只读访问尽可能便宜，这要归功于 union hack。

它确实依赖于通过一个成员编写 union 并通过另一个成员读取它，以便在不使用 lock cmpxchg16b 的情况下高效读取指针。 .这保证适用于 GNU C++(和 ISO C99/C11)，但不适用于 ISO C++。许多其他 C++ 编译器确实保证 union 类型双关有效，但即使没有它它可能仍然有效:我们总是使用 std::atomic必须假设值被异步修改的负载。因此，我们应该避免类似别名的问题，即在通过另一个指针(或 union 成员)写入值后，寄存器中的值仍然被认为是有效的。但是，编译器认为是独立的东西的编译时重新排序可能是一个问题。
在指针 + 计数器的原子 cmpxchg 之后原子地读取指针仍然应该为您提供 x86 上的获取/释放语义，但我认为 ISO C++ 对此没有任何说明。 我猜想，一个广泛的发布存储(作为 compare_exchange_weak 的一部分将与大多数架构上来自同一地址的更窄的负载同步(就像在 x86 上一样)，但 AFAIK C++ std::atomic 不保证任何关于打字。
与指针 + ABA 计数器无关，但可以用于其他使用 union 以允许访问较大原子对象子集的应用程序: 不要使用 union 来允许原子存储只是指针或计数器 .至少如果您关心与该对的获取负载同步，则不会。即使是强序 x86 也可以 reorder a narrow store with a wider load that fully contains it .一切仍然是原子的，但就内存排序而言，您进入了奇怪的领域。
在 x86-64 上，16B 原子负载需要 lock cmpxchg16b (这是一个完整的内存屏障，防止前面的窄存储在它之后变得全局可见)。但是，如果您将它与 32 位指针(或 32 位数组索引)一起使用，则很容易遇到问题，因为可以使用常规 64b 加载来加载两半。如果您需要与其他线程同步而不仅仅是原子性，我不知道您会在其他架构上看到什么问题。

要了解有关 std::memory_order 获取和释放的更多信息 ，见 Jeff Preshing's excellent articles .