CODEWITHSUNDEEP
c++c++11
MWright
MWright

Reputation: 1711

c++11 std::atomic compare_exchange_weak and the stack container

I am working my way through Anthony Williams Concurrency book for C++11.

I am a bit confused by the pop implementation of the lock free stack.

template<typename T>
class lock_free_stack
{
private:
struct node
{
    std::shared_ptr<T> data;
    node* next;
    node(T const& data_): data( std::make_shared<T>(data_)){}
};

std::atomic<node*> head;

public:

void push(T const& data)
{
    node* const new_node = new node(data);
    new_node->next = head.load();
    while(!head.compare_exchange_weak(new_node->next, new_node));
}

std::shared_ptr<T> pop()
{
    node* old_head = head.load();
    while( old_head && !head.compare_exchange_weak(old_head, old_head->next));

            // Does This not return the data of the next node before the head if 
            // compare_exchange_weak returns true
    return old_head ? old_head->data : std::shared_ptr<T>();
}
};

The line that is causing me confusion is the last two lines of the pop function.

    while( old_head && !head.compare_exchange_weak(old_head, old_head->next));
    return old_head ? old_head->data : std::shared_ptr<T>();

Will the compare_exchange_weak function not change the old_head to the next node in the stack if it returns true? This will lead to the return statement returning data from the next node and not the old head at the top of the stack when old_head is not a nullptr.

Have I interpreted this incorrectly?

Upvotes: 3

Views: 1491

Answers (2)

Mike Vine
Mike Vine

Reputation: 9852

Apart from my comment, if compare_exchange_weak succeeded, it managed to update head from the value old_head to the value old_head->next and therefore old_head is no longer part of the list and so can be correctly returned.

Its only if it returns false that it modifies the value of old_head

EDIT: Showing issues with the above code.

Firstly, if 2 threads get into pop and both read head (via head.load()) and get the same value of old_head

Thread one gets swapped out (say)

Thread two carries on running, pops the head and returns to caller, and the caller then deletes the value which holds the node.

Thread one then gets resumed and tries to read old_head->next to even call compare_exchange_weak.

HOWEVER, old_head points to memory which has been deleted. Undefined behavoir, you're lucky if you segfault.

Secondly, this has the classic ABA problem. I wont bother to explain that as its well documented and understood. Search for it.

Upvotes: 3

Nemo
Nemo

Reputation: 71605

When head.compare_exchange_weak returns false, it modifies old_head.

When it returns true, it modifies head and does not modify old_head.

See http://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange and/or http://cpp0x.centaur.ath.cx/atomics.types.operations.req.html#p21

Upvotes: 1

Related Questions