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

2024-06-19

我正在基于此实现一个无锁队列算法 http://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html,它使用计数器来解决 ABA 问题。但我不知道如何用c++11 CAS实现这个计数器。例如,从算法来看:

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

这是一个原子操作,意味着如果tail.ptr->next等于next, let tail.ptr->next指向node and 同时(原子地) make next.count+1。但是,使用C++11 CAS,我只能实现:

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

哪个不能使next.count+1同时发生。


要使用单个原子操作同时原子地修改两个事物,您需要将它们放在相邻的内存中,例如在二元结构中。然后你可以使用std::atomic<my_struct>让 gcc 发出lock cmpxchg16b http://www.felixcloutier.com/x86/CMPXCHG8B:CMPXCHG16B.html例如,在 x86-64 上。

为此,您不需要内联汇编,并且值得花费一些 C++ 语法来避免它。https://gcc.gnu.org/wiki/DontUseInlineAsm https://gcc.gnu.org/wiki/DontUseInlineAsm.

不幸的是,对于当前的编译器,您需要使用union获得仅读取一对中的一个的有效代码。对结构进行原子加载然后仅使用一个成员的“明显”方式仍然会导致lock cmpxchg16b读取整个结构,即使我们只需要一个成员。 (速度慢得多,并且会弄脏缓存行,因此读者会与其他读者竞争)。我相信指针的正常 64b 加载仍然会在 x86 上正确实现获取内存排序语义(以及原子性),但当前的编译器甚至不会进行这种优化std::memory_order_relaxed,所以我们用工会来欺骗他们。

(已提交海湾合作委员会错误 80835 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80835对这个。 TODO:如果这是一个有用的想法,那么对于 clang 来说也是如此。)


清单:

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

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

  • 确保您的对象是 16B 对齐的,或 32 位指针的 8B 对齐。更普遍,alignas(2*sizeof(void*))应该管用。未对准locked 指令可以是very在 x86 上速度很慢,特别是当它们跨越缓存行边界时。如果对象未对齐,clang3.8 甚至会将其编译为库调用。

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

  • 确保指针+uintptr_t原子对象是无锁的。这对于 x32 和 32 位 ABI(8B 对象)来说几乎可以保证,但对于 16B 对象则不然。例如MSVC 使用 x86-64 的锁。

    gcc7 及更高版本将调用 libatomic 而不是内联lock cmpxchg16b,并将返回 falseatomic_is_lock_free (原因包括它太慢了,这不是用户所期望的is_lock_free to mean https://gcc.gnu.org/ml/gcc-patches/2017-01/msg02344.html),但至少现在 libatomic 实现仍然使用lock cmpxchg16b在该指令可用的目标上。 (对于只读原子对象,它甚至可能出现段错误,所以这确实不理想。更重要的是,读取器与其他读取器争夺对缓存行的独占访问权。这就是为什么我们要费很大的力气来避免lock cmpxchg16b对于这里的读取端,我们只需要一个 8 字节的一半。)


下面是一个带有 CAS 重试循环的代码示例,该代码编译为看起来正确的 asm,并且我认为对于允许联合类型双关的实现,没有 UB 或其他不安全的 C++。它是用 C 风格编写的(非成员函数等),但如果你编写成员函数,效果是一样的。

请参阅带有 asm 输出的代码来自 Godbolt 编译器浏览器上的 gcc6.3 https://gcc.godbolt.org/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaPECAKxAEZSBnVAV2OUxAHIB6bgagAeADgBsAWhEAWPgDtMmdAz5iAtsgG0RfAEaZkAQ2YNMO/cYA2eOYNETp6VJgYywnAnyvJzzLB4IA6AFIABgBBXj5sfWJzAE8%2BAGshPgBhAAUAVSVzfWQEhT8gsIj9GViCBCtgPkt85RVo5ARAgGYAETkEfXNMFT5upj5MGX1tHqVCItCQ6YAmFs9vX1aU/SIVPGRW7BnA%2BcWfExWGAnwZAOaWnbCZoyrZfRUnAAdckxP0VoAhXbCT4mYyHcMgwRwA7D8wnw%2BBEKnglN08MARhMlE5jOc8N0%2BAAzEh8LylapEPhGEzIFTPARNYCabQeGQnTD6dB8VA4/q45gyIF4VAyAndcwzaERULPV7EYYEOJ8KhGdxdABu90IbIFFRM3L5AqeKl0xA8zlc7mGLGACCm0P%2BgPciORZggswAVAw8AAvTDsiAgrDOgCU/oJLHOCgA%2Bs8CIbAhCRdDZKC%2BM743xI8RvnHocwrAQ02H3GhuQRvqL%2BGTU6gc5hiGI3Z7WVXgNWlCT9ErK6zXugzsA4zG2hmoXw4xEunk%2BK3zOZUAB3PhSln3eUnCcIEzPSuhw0zwgIFjuad5MQUqk0umkEf8bTMdwnPBTvg7ir7/plVJ7H6zL58dBrfTzt44xtIFgyLcM82MSU1nBSFQhTNZUA2LYWhSX0TGdbYUzTQc4PjBCkJWbNzjzYsrlA84w0g6JoJLGF%2BCVaIHieIZKS6OsnFXNZ%2BmQdgGDdGRiUqJQZ30eJ4RcNx%2BnWTZH13VMoz7MEBxaWCgIINZNjDMxjGIAgIHY718M2FZC1DdAIwUq4g1aZS2j4AycQgUyCHAqNKMwKCXP9Uhh1mWYjOQlJnNc9MyPEk1V3eR53g9EwzEi%2ByPOoly%2BCVZsdRLbV%2BQnWJnkwMRnm5GR7h3B9dB0VBgCMPZZn9HDSxODTkC0vjqz0j4QBAAKTJDFzzOwq4Yx%2BJT/HhMNDwSMMcSlTAIEDerhyHLKBSG0tX35WIVBYJRlpABK9QNBEpR/PApSBWVJXcdl7KjW0EywTN%2BksB0GCdV1Yu9NCAyDbqUOC/rLOwWRMAEAgtJkcznIW6F/os4h3M8kxgdBhb%2BwWiIABUAHk2ixvaZ2IQgTAO6suR5AgdRbVB52ZVk5FB/w0zZQ0F3QbgCaJ5GwdKSHet%2BXCcx/P9AgAVi%2BSRReU1SlJw/mIgaOoGFYExWbEflZVyXjUSGHEcU2PBpSmNCkzxKdZx9RNnWeayIXjCJgFQDB%2BgYFQfOXO0%2BC2pUalQFk4ylAhWAFZ4xG2emAjTfxpxZCA9RIWIwxILB4dyABHbMpTqlTdhlsJjedU3pxnMMQWWi3fCtm3vzommhXibQWWd13SX46oT2pBBaREekSWj1lNUfPcelXKp/cwQPiGD0OrnD8HeaLKPffQWPenjxPiGTrTkHT07MH9RnLOlgcbhP0J2zwVlmGeX8XJLkG9ONvYRHU4gmwIHz86wN0pXQOqbltmurMEqoHMKyBi3gTCYF1vraUspWzn1ZKgNKxA1yNzxIaAeIJjz8hcpibKBhjCZlhMyQmAk%2BAQHxI1YeN9/zTUQpyKUOQBAFD7kGUq5g5QKhqLTCc1N/wB2ILEOMaFOqwyZiDPKQICg2WHLGIcKYX5v38OHA%2BxBF4xzjoI9em9GH6GYb/C88j4yKPHso%2B%2B/hnII2SpgdRy9NEJyTtWMMuj9E2ylpePgZ8OyvikohGSfc2Qcm0KgCofAujmDSgiK6PJMA%2BQqGsVwSgGBFxAB4kRKBeohSGAISRfVhztAJKwCxmTzIqL7ivLaWjHEp23hnPetF7Y8Rbhxf8yTZw%2B3HO3GkuJ8RwgYPzaEwSQH2UBFrBaDhZGwRTOksRUZgYznAfkuyq0v673QD5CReg%2BrFKLL5b8tBZHuKMREYQ4gpB7TQJSe8HESRdM7nSR6SseLoiWROaISjZ48zDM5YplJoiYDDCDJoRIAUzmZAkCAj0UzQphbC7JuSFAf0wAs7oPl7HaKcWnZxmBzBZymXbMs19oJomYVIxBAocT6HvMrRSdkZyVB6BAPgYAwBPK1nwPFOdj7TGKPwAA6nJVQAgWizHIacuwslQkirENoNUG4qzEAYN5R8Jg358GlbKg8S8EQQ3spUHEBBuAkBmLCamlzZXWAgCSYw7gr49MNP%2BKQMq1R3OAPvaEABle8spLnPGuYqqYYoDzMhXMAJpPMCQ5DIRM/8zwA4EHiA7J2VBUD0nQT0s2xdS7FWylYTiBYzA2P5ia5MBK%2BAYzXGyTU25RK8IZGqOQKLzAXNQM8eIEatr4BxPETZZKrTQoiGkVAfE8BjHruPFyho8AcgHsBRU8Uuw9kMbhFMvArw3nVLKadKqTqsn/DuXwATroD3pSAkwJAkRWGxKmqgWzyFtJnH/Fd90OAZLAgDQ0jbFkyN7X1aG8zwGqNeasn%2B/6v3dB2ecD80Hs5hGdNwGYnBvLNs4CLTgpAZBcGCOh1AXAUjQa/PZFgbAjjzFoOhggWGkPeQSCAEWwRSAockOhzDnBsOkFw5wdDDAQAMco2xpDpA4CwCQL6/15BKBiZ6MQEAwARAtFIHrcwk6eMQG0FR0glynjnCxjIOIGn8BnQppEjTVYUPYe8q2im/IeOcFrKcGyyJmAEa%2BLQA5YgsYtGUHyoU3n77EH/KodQmhlA4mQcE4wYgzAqG48R9gdBkNcDQxhjTnHxVSD4GG5AfARD%2BC8xAXAhB8R7BaPQVIiE/XSd8qV/0FGqOBlIKg5OlAaN0YY0x9DKg6DBAY6x9jnHuO8dIPxiziXOCzBY6lrgdWBMNeQW6fkIBJBAA. With -m32, 它用cmpxchg8b与 64 位代码使用的方式相同cmpxchg16b. With -mx32(长模式下的32位指针)它可以简单地使用64位cmpxchg,以及普通的 64 位整数加载,以在一次原子加载中获取两个成员。

这是可移植的 C++11(联合类型双关除外),没有任何特定于 x86 的内容。这只是高效的不过,在可以 CAS 两个指针大小的对象的目标上。例如它编译为对__atomic_compare_exchange_16ARM / 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 is:

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。


它确实依赖于通过一个成员写入联合体并通过另一个成员读取联合体,从而在不使用lock cmpxchg16b。这保证可以在 GNU C++(和 ISO C99/C11)中工作,但不能在 ISO C++ 中工作。许多其他 C++ 编译器确实保证联合类型双关有效,但即使没有它,它可能仍然有效:我们总是使用std::atomic必须假设该值是异步修改的负载。因此,我们应该避免类似别名的问题,即通过另一个指针(或联合成员)写入值后,寄存器中的值仍然被认为是活动的。不过,编译时对编译器认为独立的事物进行重新排序可能是一个问题。

在指针+计数器的原子 cmpxchg 之后原子地读取指针仍然应该为您提供 x86 上的获取/释放语义,但我不认为 ISO C++ 对此有任何说明。我猜想一个广泛的发布商店(作为compare_exchange_weak在大多数架构上,将与来自同一地址的较窄负载同步(就像在 x86 上一样),但 AFAIK C++std::atomic不保证有关类型双关的任何内容。

与指针 + ABA 计数器无关,但可能会出现在使用联合来允许访问较大原子对象的子集的其他应用程序中:不要使用联合来允许原子存储仅指向指针或计数器。至少如果您关心与该对的获取负载的同步,则至少不会。即使是强有序的 x86 也可以重新订购一个狭窄的商店,并使用更宽的负载来完全容纳它 https://stackoverflow.com/questions/35830641/can-x86-reorder-a-narrow-store-with-a-wider-load-that-fully-contains-it/35910141#35910141。一切仍然是原子的,但就内存排序而言,您会进入奇怪的领域。

在 x86-64 上,原子 16B 加载需要lock cmpxchg16b(这是一个完整的内存屏障,防止前面的窄存储在其之后变得全局可见)。但是,如果将其与 32 位指针(或 32 位数组索引)一起使用,则很容易出现问题,因为两半都可以使用常规 64b 加载来加载。而且我不知道如果您需要与其他线程同步而不仅仅是原子性,您会在其他架构上看到什么问题。


了解有关 std::memory_order 获取和释放的更多信息, see Jeff Preshing 的优秀文章 http://preshing.com/20120913/acquire-and-release-semantics/.

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

如何使用 c++11 CAS 实现 ABA 计数器? 的相关文章

  • 如何为 C 分配的 numpy 数组注册析构函数?

    我想在 C C 中为 numpy 数组分配数字 并将它们作为 numpy 数组传递给 python 我可以做的PyArray SimpleNewFromData http docs scipy org doc numpy reference
  • 如何修复此错误“GDI+ 中发生一般错误”?

    从默认名称打开图像并以默认名称保存 覆盖它 我需要从 Image Default jpg 制作图形 将其放在 picturebox1 image 上并在 picurebox1 上绘制一些图形 它有效 这不是我的问题 但我无法保存 pictu
  • 在新的浏览器进程中打开 URL

    我需要在新的浏览器进程中打开 URL 当浏览器进程退出时我需要收到通知 我当前使用的代码如下 Process browser new Process browser EnableRaisingEvents true browser Star
  • 互斥体实现可以互换(独立于线程实现)

    所有互斥体实现最终都会调用相同的基本系统 硬件调用吗 这意味着它们可以互换吗 具体来说 如果我使用 gnu parallel算法 使用openmp 并且我想让他们称之为线程安全的类我可以使用boost mutex用于锁定 或者我必须编写自己
  • 单元测试一起运行时失败,单独运行时通过

    所以我的单元测试遇到了一些问题 我不能只是将它们复制并粘贴到这里 但我会尽力而为 问题似乎是 如果我一项一项地运行测试 一切都会按预期进行 但如果我告诉它一起运行测试 则 1 5 将通过 TestMethod public void Obj
  • 如何从 .resx 文件条目获取注释

    资源文件中的字符串有名称 值和注释 The ResXResourceReader类让我可以访问名称和值 有办法看评论吗 你应该能够得到Comment via ResXDataNode class http msdn microsoft co
  • 将 System.Windows.Input.KeyEventArgs 键转换为 char

    我需要将事件参数作为char 但是当我尝试转换 Key 枚举时 我得到的字母和符号与传入的字母和符号完全不同 如何正确地将密钥转换为字符 这是我尝试过的 ObserveKeyStroke this new ObervableKeyStrok
  • 存储来自其他程序的事件

    我想将其他应用程序的事件存储在我自己的应用程序中 事件示例 打开 最小化 Word 或打开文件时 这样的事可能吗 运行程序 http msdn microsoft com en us library ms813609 aspx and 打开
  • 无法在 Windows 运行时组件库的 UserControl 中创建依赖项属性

    我想在用户控件内创建数据可绑定属性 这个用户控件包含一个 Windows 运行时组件 项目 我使用下面的代码来创建属性 public MyItem CurrentItem get return MyItem GetValue Current
  • 获取 WPF 控件的所有附加事件处理程序

    我正在开发一个应用程序 在其中动态分配按钮的事件 现在的问题是 我希望获取按钮单击事件的所有事件 因为我希望删除以前的处理程序 我尝试将事件处理程序设置为 null 如下所示 Button Click null 但是我收到了一个无法分配 n
  • 如何在 Linq 中获得左外连接?

    我的数据库中有两个表 如下所示 顾客 C ID city 1 Dhaka 2 New york 3 London 个人信息 P ID C ID Field value 1 1 First Name Nasir 2 1 Last Name U
  • C++:.bmp 到文件中的字节数组

    是的 我已经解决了与此相关的其他问题 但我发现它们没有太大帮助 他们提供了一些帮助 但我仍然有点困惑 所以这是我需要做的 我们有一个 132x65 的屏幕 我有一个 132x65 的 bmp 我想遍历 bmp 并将其分成小的 1x8 列以获
  • 将 log4net 与 Autofac 结合使用

    我正在尝试将 log4net 与 Autofac 一起使用 我粘贴了这段代码http autofac readthedocs org en latest examples log4net html http autofac readthed
  • 如何对 Web Api 操作进行后调用?

    我创建了一个 Web API 操作 如下所示 HttpPost public void Load string siteName string providerName UserDetails userDetails implementat
  • gcc 的配置选项如何确定默认枚举大小(短或非短)?

    我尝试了一些 gcc 编译器来查看默认枚举大小是否很短 至少一个字节 强制使用 fshort enums 或无短 至少 4 个字节 强制使用 fno short enums user host echo Static assert 4 si
  • Server.MapPath - 给定的物理路径,预期的虚拟路径

    我正在使用这行代码 var files Directory GetFiles Server MapPath E ftproot sales 在文件夹中查找文件 但是我收到错误消息说 给定物理路径但虚拟路径 预期的 我对在 C 中使用 Sys
  • 如何在按钮单击时模拟按键 - Unity

    我对 Unity 中的脚本编写非常陌生 我正在尝试创建一个按钮 一旦单击它就需要模拟按下 F 键 要拾取一个项目 这是我当前的代码 在编写此代码之前我浏览了所有统一论坛 但找不到任何有效的东西 Code using System Colle
  • 英特尔 Pin 与 C++14

    问题 我有一些关于在 C 14 或其他 C 版本中使用英特尔 Pin 的问题 使用较新版本从较旧的 C 编译代码很少会出现任何问题 但由于 Intel Pin 是操作指令级别的 如果我使用 C 11 或 C 14 编译它 是否会出现任何不良
  • 使用 GROUP 和 SUM 的 LINQ 查询

    请帮助我了解如何使用带有 GROUP 和 SUM 的 LINQ 进行查询 Query the database IEnumerable
  • 防止在工厂方法之外实例化对象

    假设我有一个带有工厂方法的类 class A public static A newA Some code logging return new A 是否可以使用 a 来阻止此类对象的实例化new 那么工厂方法是创建对象实例的唯一方法吗 当

随机推荐