c++ - Is using the result of an std::atomic fetch_add to index an array still atomic?

Question

So I wanted to try implementing a fixed sized, wait free stack with the fetch_add and fetch_sub atomic instructions. Say that I have a basic stack, with two operations, push and pop.

struct WaitFreeStack {
    std::atomic<size_t> cur;
    std::atomic<int>* buf;

    void push(int i) {
        buf[cur.fetch_add(1)].store(i);
    }

    int pop() {
        return buf[cur.fetch_sub(1) - 1].load();
    }
};

My question is, are operations in the form of B[X], where B is an array and X is an integer atomic ? In my example for instance, is it possible that after a fetch_add call for the push() method is executed, and before the B[X] is executed, that a whole pop and push in separate threads could be executed, causing a push to overwrite another push ?

question from:https://stackoverflow.com/questions/65933744/is-using-the-result-of-an-stdatomic-fetch-add-to-index-an-array-still-atomic

Answer 1

B[X] is not atomic. But if it even would be atomic, it wouldn't help much.

The problem is that you have expression of multiple atomic operations. Although operations are atomic, the whole expression is not atomic.

Or: an expression containing of multiple atomic operations does not need to be atomic.

The class invariant here should be that cur points to the current object in buf. But this invariant is broken between 2 atomic operations fetch_add and store.

If B[X] would be atomic (which is not), one would have following sequence of atomic operations for push:

X = cur.fetch_add(1);  // atomic
// 1. dT
ref = B[X];             // let's assume atomic
// 2. dT
ref.store(i);           // atomic

For example in the time interval 2.dT imagine second thread popping 2 items and third thread pushing 1 item, all executing before ref.store(i). In this time the value under ref reference would change.