Ring buffer mutual exclusión

[perencia]

I'm curious, why do we need mutual exclusión in the ring buffer if we are in the spsc scenario?

[DNedic]

Good question! The reason mutual exlusion is needed even in the SPSC scenario is to keep operation ordering and prevent data races.

Both compilers and out of order CPUs are allowed to reorder code they deem independent, and while doing this they cannot take into account the fact that multiple threads could be operating on the same data, leading to data races where two threads can see events in different orders.

Consider the following example using the Queue:

template <typename T, size_t size> bool Queue<T, size>::Push(const T &element) {
    const size_t w = _w.load(std::memory_order_relaxed);
    size_t w_next = w + 1;
    if (w_next == size) {
        w_next = 0U;
    }

    const size_t r = _r.load(std::memory_order_acquire);
    if (w_next == r) {
        return false;
    }

    _data[w] = element;

    _w.store(w_next, std::memory_order_release);
    return true;
}

Without atomic operations here, the compiler or the CPU might decide that placing the element and bumping the write index are independent operations as there is no data dependency from their viewpoint. However, we know that if the write index is stored first and the operation is interrupted, the reading thread will believe there is data to be read.

While mutual exclusion just prevents the entire object from being accessed from different threads at the same time, bypassing this problem, atomic operations are about preventing the compiler and the CPU from reordering operations by generating code in the order we intended and hardware barriers that prevent operation reordering on the CPU side.

[perencia-wc]

Hi Djordje,
I really appreciate your didactic answer.
I have a couple more questions. The context in which I plan to use your code does not have threads or tasks, but it does have interruptions. I understand that I could call the Write method from the ISR. There is a memcpy in there, which causes me some concern; what do you think about that? Also, shouldn't the variables _r and _w be declared as volatile?

Aside from that, certainly I bet most of ring buffers out there do not take the precautions regarding memory reordering that your library take. At first I thought that the reason for mutual exclusion was only to prevent partial write/read of _r and _w, which I suppose could happen in some architectures (don't know if that's the case with ARM CORTEX-M, with which I'm working). Why do you think that people normally don't take memory reordering into account, either by using lock or lockless solutions?

(Ops, It seems I did respond with my other account, sorry about that).

[DNedic]

Threads or tasks and interrupts share the same behavior, with the exception that interrupts on Cortex M and most architectures share one stack. From the concurrency point of view, this creates no difference in handling preemption for cases like this.

Next up, using the volatile specifier for concurrency is misuse. Essentially, volatile only ensures 3 things:

1. volatile variables cannot completely be optimized out by the compiler
2. Writes and reads to and from volatile variables cannot be optimized out by the compiler
3. The compiler cannot reorder writes and reads to and from volatile variables in relation to other volatile writes and reads

Notice how there is no mention of the CPU reordering writes and reads or preventing them from being interrupted?
On architectures such as Cortex M and RV32, volatile writes and reads of up to word size are atomic, however this is not a general case, and these are in-order architectures. Were we to write to a larger than word-size variable, the write would have to be split into two or more instructions, which could be preempted, leaving the variable with a bogus value in the meantime. Additionally, out of order architectures, as mentioned are allowed to reorder writes and reads in the CPU, and volatile has no mechanism to prevent that, unlike as mentioned above, atomic instructions which have hardware mechanisms for synchronization.

One last thing: since the volatile writes and reads cannot be reordered only in relation to one another, using memcpy would not work here on any architecture, as memcpy is not a volatile operation.

As a sidenote, volatile should only ever be used for memory mapped values, you can read more about this here.

Finally, memcpy itself should be reentrant on all architectures if properly implemented, at least it was on all platforms I have dealt with, and the atomic reads and writes lock it into place from being moved by the compiler in dangerous ways.

If your goal is to only have a Cortex M or RV32 safe ring buffer, yes, you can use volatile for the indices, making sure they are word-size or less, and instead of using memcpy, use a volatile declared array for storage and a for loop to copy manually. I don't see that as extremely beneficial as lockfree probably has either a small performance hit or even better performance due to memcpy use, and you never know if your code might need to be ported on architectures where this won't work in the future.

[perencia]

Thanks for your response and your work, I'd probably use it now that I is more clear for me hot it works 👍