要使用单个原子操作同时原子地修改两个事物,您需要将它们放在相邻的内存中,例如在二元结构中。然后你可以使用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*))
应该管用。未对准lock
ed 指令可以是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_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
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/.