Real-world example where std::atomic::compare_exchange used with two memory_order parameters

Question

Can you give a real-world example where two memory_order parameter version of std::atomic::compare_exchange is used for a reason (so the one memory_order parameter version is not adequate)?

Answer 1

In many cases, the second memory orderering parameter on compare_exchange is set to memory_order_relaxed. In those cases, it is usually not wrong to omit it, just potentially less efficient.

Here is an example of a simple, lock-free, list/stack that requires a second, different, ordering parameter on compare_exchange_weak in order to be data-race-free.

Calls to push can be executed concurrently, but to avoid the complexities of lock-free data manipulation, the assumption is made that nodes cannot be removed from the stack while calls to push are executed; i.e. to avoid dangling pointers.

template<typename T>
class mystack {

    struct node {
        node *next = nullptr;

        T data;
        int id;

        node(int id) : id{id} { }
    };

    std::atomic<node *> head{nullptr};

public:
    void push(T data, int id);
    bool pop(T &data); // not implemented
};


template<typename T>
void mystack<T>::push(T data, int id)
{
    node *newnode = new node{id};

    newnode->data = std::move(data);

    node *current_head = head.load(std::memory_order_relaxed);   // A

    for (;;)
    {
        newnode->next = current_head;

        if (head.compare_exchange_weak(current_head, newnode,
                                       std::memory_order_release,   // B
                                       std::memory_order_acquire))  // C
        {
            /*
             * 'current_head' may not be derefenced here since the initial load (at A)
             * does not order memory 'current_head' is pointing at.
             *
             * a release barrier (at B) is necessary to make 'newnode' available
             * to other threads
             */
            std::cout << "Insertion successful\n";

            break;

        } else
        {
            /*
             * 'current_head' is the updated head pointer after 'compare_exchange' failed
             * Since it was inserted by another thread (the CAS failed),
             * an acquire barrier must be set (at C) in order to be able to access data
             * 'current_head' is pointing at.
             */
            std::cout << "Insertion failed after head changed to id: " <<
                          current_head->id << std::endl;
        }
    }
}

In push, the initial load (at A) is a relaxed operation, meaning that even though the head pointer is loaded atomically, it may not be dereferenced since the memory it refers to is unordered in this thread.

In case compare_exchange_weak returns success, newnode is inserted at the head of the list and made available to other threads by setting a release barrier (at B). Another thread that accesses this data (later, via pop) needs to set an acquire barrier.

In case compare_exchange_weak returns failure (forget spuriously), another thread just inserted a new node instance and current_head is updated with the new value of head. Since current_head is now pointing at data that was allocated and released in another thread, an acquire barrier is necessary if current_head is going to be dereferenced.
This is true since the cout failure message includes current_head->id.

Had the last parameter been omitted, the first barrier parameter would have been used for the failure load scenario, but since this is a release barrier, the effective barrier would have decayed to memory_order_relaxed, causing a data race on current_head->id.