出于排序的目的，原子读-修改-写是一个还是两个操作? [英] For purposes of ordering, is atomic read-modify-write one operation or two?

问题描述

考虑一个原子的读-修改-写操作，例如 x.exchange(...，std :: memory_order_acq_rel).出于排序的目的，将其装载和存储到其他对象中，将其视为:

1. 具有获取释放语义的单个操作?

2. 或者作为获取负载，然后是发布存储，并额外保证了 x 的其他负载和存储将不会同时观察到它们?

如果它是#2，则尽管在加载之前或在存储之后，无法对同一线程中的其他操作进行重新排序，但仍有可能在两个线程之间对它们进行重新排序.

作为一个具体示例，请考虑:

  std :: atomic< int>x，y;无效thread_A(){x.exchange(1，std :: memory_order_acq_rel);y.store(1，std :: memory_order_relaxed);}无效thread_B(){//这两个负载无法重新排序int yy = y.load(std :: memory_order_acquire);int xx = x.load(std :: memory_order_acquire);std :: cout<<xx<<"，"<<yy<<std :: endl;} 

thread_B 是否可以输出 0，1 ?

如果将 x.exchange()替换为 x.store(1，std :: memory_order_release); ，那么 thread_B 肯定可以输出 0，1 .

是否应该排除 exchange()中的额外隐式负载?

cppreference 听起来像是#1，并且 0、1 :

具有此存储顺序的读-修改-写操作既是获取操作又是释放操作.在此存储之前或之后，无法对当前线程中的任何内存读写进行重新排序.

但是我在标准中找不到任何明确的证据来支持这一点.实际上，除了N4860中的31.4(10)之外，该标准几乎没有涉及原子性的读取-修改-写入操作，这只是显而易见的属性，即读取必须读取写入前的最后一个值.因此，尽管我讨厌质疑cppreference，但我想知道这是否正确.

我也在研究如何在ARM64上实现它.gcc和clang都基本上将 thread_A 编译为

  ldaxr [x]stlxr#1，[x]str#1，[y] 

(参见Godbolt.)基于对ARM64语义的理解以及一些测试(包括(而不是商店)加载 y 的方式，我认为 str [y] 可以在 stlxr [x] 之前可见(尽管当然不是在 ldaxr 之前).这将使 thread_B 可以观察 0，1 .因此，如果#1是正确的，那么gcc和clang似乎都错了，我对此深信不疑.

最后，据我所知，用 seq_cst 替换 memory_order_acq_rel 不会改变此分析的任何内容，因为它仅增加了与其他相关的语义> seq_cst 操作，这里没有任何操作.

---

我发现解决方案

这不是语言标准级别的答案，但是一些证据表明，答案实际上是两个".正如我在问题中所猜到的那样，即使RMW是 seq_cst .

我无法像最初的问题那样观察到商店的重新排序，但这是一个示例，显示了原子 seq_cst RMW的商店进行了重新排序，并带有以下 relaxed加载.

下面的程序是Peterson算法的实现，该算法改编自 https://godbolt.org/z/fhjjn7 ，第116-120行程序集输出.(gcc是相同的，但是埋在库函数中.)通过ARM64内存排序语义，可以通过以下加载和存储来对发布存储 stlxrb 进行重新排序.它是排他性的事实并不会改变这一点.

为了使重新排序更频繁地进行，我们安排要存储的数据取决于错过高速缓存的先前负载，这可以通过使用 dc civac 将该行逐出来确保.我们还需要将两个标志 me 和 other 放在单独的缓存行中.否则，据我了解，即使线程A在存储之前进行了加载，线程B也必须等待开始其RMW，直到A的存储完成为止，尤其是直到A的存储可见时才进行加载./p>

在多核Cortex A72(Raspberry Pi 4B)上，断言通常在几千次迭代后失败，这几乎是瞬时的.

该代码需要使用 -O2 构建.我怀疑如果为ARMv8.2或更高版本(其中 swpalb 可用)构建，它将无法正常工作.

 //基于LWimsey的https://stackoverflow.com/a/41859912/634919#include< thread>#include< atomic>#include< cassert>//大小至少等于缓存行constexpr size_t cache_line_size = 256;static void take_lock(std :: atomic< bool& me，std :: atomic< bool>& other){alignas(cache_line_size)bool uncached_true = true;为了 (;;) {//从缓存中撤出uncached_true.asm volatile("dc civac，％0" ::"r"(& uncached_true):存储器")；//因此，"me"的发布存储可能会延迟//`uncached_true`已加载.这应该给机器//是时候进行`other`的加载了，这不是//商店对`me`的发布语义禁止.me.exchange(uncached_true，std :: memory_order_seq_cst);如果(other.load(std :: memory_order_relaxed)== false){//采取！std :: atomic_thread_fence(std :: memory_order_seq_cst);返回;}//重来me.store(false，std :: memory_order_seq_cst);}}静态void drop_lock(std :: atomic< bool>& me){me.store(false，std :: memory_order_seq_cst);}alignas(cache_line_size)std :: atomic< int>计数器{0}；静态无效的critical_section(void){//我们应该是这里唯一的线程.int tmp = counter.fetch_add(1，std :: memory_order_seq_cst);assert(tmp == 0);//延迟赋予其他线程尝试锁定的机会对于(int i = 0; i< 100; i ++)asm volatile(")；tmp = counter.fetch_sub(1，std :: memory_order_seq_cst);assert(tmp == 1);}静态空忙(std :: atomic< bool>我，std :: atomic< bool>其他){为了 (;;) {take_lock(* me，* other);std :: atomic_thread_fence(std :: memory_order_seq_cst);//偏执狂critical_section();std :: atomic_thread_fence(std :: memory_order_seq_cst);//偏执狂drop_lock(* me);}}//这两个标志必须位于单独的缓存行中.alignas(cache_line_size)std :: atomic< bool>flag1 {false}，flag2 {false}；int main(){std ::线程t1(忙，& flag1，& flag2);std ::线程t2(忙，& flag2，& flag1);t1.join();//永远不会发生t2.join();返回0;} 

Consider an atomic read-modify-write operation such as x.exchange(..., std::memory_order_acq_rel). For purposes of ordering with respect to loads and stores to other objects, is this treated as:

1. a single operation with acquire-release semantics?

2. Or, as an acquire load followed by a release store, with the added guarantee that other loads and stores to x will observe both of them or neither?

If it's #2, then although no other operations in the same thread could be reordered before the load or after the store, it leaves open the possibility that they could be reordered in between the two.

As a concrete example, consider:

std::atomic<int> x, y;

void thread_A() {
    x.exchange(1, std::memory_order_acq_rel);
    y.store(1, std::memory_order_relaxed);
}

void thread_B() {
    // These two loads cannot be reordered
    int yy = y.load(std::memory_order_acquire);
    int xx = x.load(std::memory_order_acquire);
    std::cout << xx << ", " << yy << std::endl;
}

Is it possible for thread_B to output 0, 1?

If the x.exchange() were replaced by x.store(1, std::memory_order_release); then thread_B could certainly output 0, 1. Should the extra implicit load in exchange() rule that out?

cppreference makes it sound like #1 is the case and 0, 1 is forbidden:

A read-modify-write operation with this memory order is both an acquire operation and a release operation. No memory reads or writes in the current thread can be reordered before or after this store.

But I can't find anything explicit in the standard to support this. Actually the standard says very little about atomic read-modify-write operations at all, except 31.4 (10) in N4860 which is just the obvious property that the read has to read the last value written before the write. So although I hate to question cppreference, I'm wondering if this is actually correct.

I'm also looking at how it's implemented on ARM64. Both gcc and clang compile thread_A as essentially

ldaxr [x]
stlxr #1, [x]
str #1, [y]

(See on godbolt.) Based on my understanding of ARM64 semantics, and some tests (with a load of y instead of a store), I think that the str [y] can become visible before the stlxr [x] (though of course not before the ldaxr). This would make it possible for thread_B to observe 0, 1. So if #1 is true then it would seem that gcc and clang are both wrong, which I hesitate to believe.

Finally, as far as I can tell, replacing memory_order_acq_rel with seq_cst wouldn't change anything about this analysis, since it only adds semantics with respect to other seq_cst operations, and we don't have any here.

---

I found What exact rules in the C++ memory model prevent reordering before acquire operations? which, if I understand it correctly, seems to agree that #2 is correct, and that 0, 1 could be observed. I'd still appreciate confirmation, as well as a check on whether the cppreference quote is actually wrong or if I'm misunderstanding it.

解决方案

Not an answer at the level of the language standard, but some evidence that in practice, the answer can be "two". And as I guessed in the question, this can happen even if the RMW is seq_cst.

I haven't been able to observe stores being reordered as in the original question, but here is an example that shows the store of an atomic seq_cst RMW being reordered with a following relaxed load.

The program below is an implementation of Peterson's algorithm adapted from LWimsey's example in What's are practical example where acquire release memory order differs from sequential consistency?. As explained there, the correct version of the algorithm involves

me.store(true, std::memory_order_seq_cst);
if (other.load(std::memory_order_seq_cst) == false) 
    // lock taken

where it is essential that the load become visible after the store.

If RMW were a single operation for the purposes of ordering semantics, we would expect that it would be safe to do

me.exchange(true, std::memory_order_seq_cst);
if (other.load(std::memory_order_relaxed) == false) {
    // Ensure critical section doesn't start until we know we have the lock
    std::atomic_thread_fence(std::memory_order_seq_cst);
    // lock taken
}

on the theory that since the exchange operation has acquire semantics, the load must become visible after the exchange has completed, and in particular after the store of true to me has become visible.

But in fact on ARMv8-a, using either gcc or clang, such code frequently fails. It appears that in fact, exchange does consist of an acquire-load and a release-store, and that other.load may become visible before the release-store. (Though not before the acquire-load of the exchange, but that is irrelevant here.)

clang generates code like the following:

mov w11, #1
retry:
ldaxrb wzr, [me]
stlxrb w12, w11, [me]
cbnz w12, retry
ldrb w11, [other]

See https://godbolt.org/z/fhjjn7, lines 116-120 of the assembly output. (gcc is the same but buried inside a library function.) By ARM64 memory ordering semantics, the release-store stlxrb can be reordered with following loads and stores. The fact that it's exclusive doesn't change that.

To make the reordering happen more often, we arrange for the data being stored to depend on a previous load that missed cache, which we ensure by evicting that line with dc civac. We also need to put the two flags me and other on separate cache lines. Otherwise, as I understand it, even if thread A does its load before the store, then thread B has to wait to begin its RMW until after A's store completes, and in particular won't do its load until A's store is visible.

On a multi-core Cortex A72 (Raspberry Pi 4B), the assertion typically fails after a few thousand iterations, which is nearly instantaneous.

The code needs to be built with -O2. I suspect it will not work if built for ARMv8.2 or higher, where swpalb is available.

// Based on https://stackoverflow.com/a/41859912/634919 by LWimsey
#include <thread>
#include <atomic>
#include <cassert>

// size that's at least as big as a cache line
constexpr size_t cache_line_size = 256;

static void take_lock(std::atomic<bool> &me, std::atomic<bool> &other) {
    alignas(cache_line_size) bool uncached_true = true;
    for (;;) {
        // Evict uncached_true from cache.
        asm volatile("dc civac, %0" : : "r" (&uncached_true) : "memory");
        
        // So the release store to `me` may be delayed while
        // `uncached_true` is loaded.  This should give the machine
        // time to proceed with the load of `other`, which is not
        // forbidden by the release semantics of the store to `me`.
        
        me.exchange(uncached_true, std::memory_order_seq_cst);
        if (other.load(std::memory_order_relaxed) == false) {
            // taken!
            std::atomic_thread_fence(std::memory_order_seq_cst);
            return;
        }
        // start over
        me.store(false, std::memory_order_seq_cst);
    }
}

static void drop_lock(std::atomic<bool> &me) {
    me.store(false, std::memory_order_seq_cst);
}

alignas(cache_line_size) std::atomic<int> counter{0};

static void critical_section(void) {
    // We should be the only thread inside here.
    int tmp = counter.fetch_add(1, std::memory_order_seq_cst);
    assert(tmp == 0);
    
    // Delay to give the other thread a chance to try the lock
    for (int i = 0; i < 100; i++)
        asm volatile("");
    
    tmp = counter.fetch_sub(1, std::memory_order_seq_cst);
    assert(tmp == 1);
}    

static void busy(std::atomic<bool> *me, std::atomic<bool> *other)
{
    for (;;) {  
        take_lock(*me, *other);
        std::atomic_thread_fence(std::memory_order_seq_cst); // paranoia
        critical_section();
        std::atomic_thread_fence(std::memory_order_seq_cst); // paranoia
        drop_lock(*me);
    }
}


// The two flags need to be on separate cache lines.
alignas(cache_line_size) std::atomic<bool> flag1{false}, flag2{false};

int main()
{
    std::thread t1(busy, &flag1, &flag2);
    std::thread t2(busy, &flag2, &flag1);
    
    t1.join(); // will never happen
    t2.join();
    return 0;
}

这篇关于出于排序的目的，原子读-修改-写是一个还是两个操作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！