How to express in C++11 ordinary store (export) and load (import) barriers (fences)?

Question

The following code implements some lock-free (and atomic-free!) inter-thread communication that requires the usage of the store and load memory barriers but the C++11 release-acquire semantics is not appropriate nor guarantee the correctness. Actually the algorithm exposes a need for a kind of inversion of the release-acquire semantic i.e. to signal that some operation didn't take place rather than it did.

volatile bool valid=true;
volatile uint8_t blob[1024] = {/*some values*/};

void zero_blob() {
    valid=false;
    STORE_BARRIER;
    memset(blob,0,1024);
}

int32_t try_get_sum(size_t index_1, size_t index_2) {
    uint8_t res = blob[index_1] + blob[index_2];
    LOAD_BARRIER;
    return valid ? res : -1; 
}

I'm able to make this code correct on all hardware architectures simply using native memory barriers e.g. on Intel there is no need for memory barriers here, on Sparc (RMO) membar #StoreStore and membar #LoadLoad, on PowerPC lwsync for both. So no big deal and the code is a typical example of using store and load barriers. Now, what C++11 construction should I use to make the code correct assuming that I don't want to convert 'blob' to std::atomic objects as it would make 'blob' a guard object and variable 'valid' a guarded one whereas it's the other way around. Converting variable 'valid' to a std::atomic object is OK for me, but there are no barriers to guarantee the correctness. To make it clear, let's consider the following code:

volatile std::atomic<bool> valid{true};
volatile uint8_t blob[1024] = {/*some values*/};

void zero_blob() {
    valid.store(false, std::memory_order_release);
    memset(blob,0,1024);
}

int32_t try_get_sum(size_t index_1, size_t index_2) {
    uint8_t res = blob[index_1] + blob[index_2];
    return valid.load(std::memory_order_acquire) ? res : -1; 
}

The code is incorrect as the barriers are placed in the wrong places and hence writing to 'blob' can precede writing to 'valid' or/and loading from 'valid' can precede loading from 'blob'. I thought that in order to deal with such constructions C++11 provided std::atomic_thread_fence and the code should be:

volatile std::atomic<bool> valid{true};
volatile uint8_t blob[1024] = {/*some values*/};

void zero_blob() {
    valid.store(false, std::memory_order_relaxed);
    std::atomic_thread_fence(std::memory_order_release);
    memset(blob,0,1024);
}

int32_t try_get_sum(size_t index_1, size_t index_2) {
    uint8_t res = blob[index_1] + blob[index_2];
    std::atomic_thread_fence(std::memory_order_acquire);
    return valid.load(std::memory_order_relaxed); ? res : -1; 
}

Unfortunately C++11 says:

A release fence A synchronizes with an acquire fence B if there exist atomic operations X and Y, both operating on some atomic object M, such that A is sequenced before X, X modifies M, Y is sequenced before B, and Y reads the value written by X or a value written by any side effect in the hypothetical release sequence X would head if it were a release operation.

which clearly states that std::atomic_thread_fence should be placed in the opposite sides of the operations on the atomic object.

LATER EDIT

Below please find much more usable example:

volatile uint64_t clock=1;
volatile uint8_t blob[1024] = {/*some values*/};

void update_blob(uint8_t vals[1024]) {
    clock++;
    STORE_BARRIER;
    memcpy(blob,vals,1024);
    STORE_BARRIER;
    clock++;
}

int32_t try_get_sum(size_t index_1, size_t index_2) {
    uint64_t snapshot = clock;
    if(snapshot & 0x1) {
        LOAD_BARRIER;
        uint8_t res = blob[index_1] + blob[index_2];
        LOAD_BARRIER;
        if(snapshot == clock)
            return res;
    }
    return -1;
}

Answer 1

According to the memory_order article, to be conservatively safe you need to use memory_order_release after the store and memory_order_acquire before the load (both of the same atomic variable).

So:

 std::atomic<int> var;

 // Writer
 // something important <happens-before> writing 42 in the writer thread
 var.store(42, std::std::memory_order_release);

 // Reader
 auto result = var.load(std::std::memory_order_acquire);
 if (result == 42) {
    // transitively, as the result's new value is observed, the "something important" is here too
 }

More generally, depending on what effect you need to achieve and what your target architecture supports, you can do it less conservatively.

You would generally prefer std::atomic_flag over std::atomic<bool>, as the former is guaranteed to be lock-free, unlike the latter.

Lastly - why not starting from a mutex-protected critical section, or even better, push the updates to the consumer via a lock free ring buffer, so they don’t share anything?

Answer 2

Below please find much more usable example:

Allow me to restate what you're essentially doing.

Your code is reading from memory. That memory may be updated at any time by some other thread. But you do not want to impose an execution synchronization (that is, some kind of mutex) between the reader and writer. So instead, you build a system that allows you to detect whether the reads you have already performed may have been overwritten by some other thread. And if they were, you just ignore the values you read.

C++ doesn't let you do that.

If you are reading from a non-atomic object which is potentially written by some other thread, without appropriate execution and memory synchronization between the two operations, then you have a data race. The presence of a data race does not mean that you may read incorrect values; it means that your code has undefined behavior.

You cannot undo UB. Once your program enters undefined-behavior land, all bets are off. At least, as far as the standard is concerned.

You can rewrite your code to work within the standard, of course. But it has to prevent the execution of the reads while a write may be happening, not merely checking after the fact to see if the read is OK. If the write is always 1KB, an atomic-based spinlock is probably appropriate for the writing function, and the reader can just return -1 if the atomic lock isn't available.

You can also write this kind of system (apparently called a "SeqLock") using C++ atomics, with the full and complete knowledge that it invokes UB as far as the standard is concerned. As long as the types you're copying are trivial, it'll work just fine.

Note that the C++ Concurrency TS 2 will include a feature that will allow SeqLock implementations. This will hopefully see the full standard with C++23.

Answer 3

Your example is correct. I don't think the standard is very clear when it comes to how non-atomics are handled.

std::atomic<bool> valid{true};           // removed volatile
uint8_t blob[1024] = {/*some values*/};  // removed volatile

void zero_blob() {
    valid.store(false, std::memory_order_relaxed);            // A)
    std::atomic_thread_fence(std::memory_order_release);      // B)
    memset(blob,0,1024);                                      // C)
}                                                              

int32_t try_get_sum(size_t index_1, size_t index_2) {          
    uint8_t res = blob[index_1] + blob[index_2];              // D)
    std::atomic_thread_fence(std::memory_order_acquire);      // E)
    return valid.load(std::memory_order_relaxed) ? res : -1;  // F)
}

The fence in step B) guarantees program order will be respected, and the standard doesn't really say this but the store to valid should be propagated before any subsequent writes in the same thread.

The fence in step E) guarantees program order will be respected.

So A) inter-thread happens-before C) and D) happens before F)

If F) perceives that valid is true, then, assuming no ABA problem, F) happens before A).

If F) happens before A), then D) happens before A).

If F perceives that valid is false, then A) happens before F). This doesn't necessarily mean that C) happens before D), but we discard the result just in case. It really is important to discard because the values in blob can be totally invalid. (Though using uint8_t protects against partial read from conversion to void*. It's cache-aligned, but It's technically not word-sized, which calls the atomicity into question. IIRC it could also theoretically be vulnerable to a true partial-read on some unlikely architectures.)

These deductions are based on the Linux Kernel Memory Consistency Model (LKMM), not the C++ memory model. From what I've read on cppreference.com, when they talk about propagation order in the C++ memory model, they uses phrases like "all changes prior to X in thread A will be visible after Y in thread B", but usually only in the context of atomic operations. I think it's relatively low-risk to expect that the C++ compiler will emit instructions that guarantee propagation order, at least on consumer-grade CPUs. You should still check the assembly and consult the CPU documentation. You'll definitely be fine on x86 thanks to TSO, but I haven't ever looked out at what propagation order primitives are available on weakly-ordered architectures.

Lastly, if you are going to be re-using blob, there should be another atomic variable to indicate that the memset is done.