# Lock-free bounded stack in C++11

Here is a classical attempt to implement a lock-free stack (based on this article). I rewrote it in C++11 and also tried to add memory orders which I would like to confirm to be correct.

template<typename T>
class stack
{
struct node_t final
{
T value;
node_t *next;
};

{
uintptr_t aba;
node_t *node;
{}
{}
};

typedef typename std::aligned_storage<sizeof(node_t), std::alignment_of<node_t>::value>::type aligned_node_t;

std::unique_ptr<aligned_node_t[]> buffer_ptr;
node_t *node_buffer;

public:

stack(size_t capacity)
{
// preallocate nodes
buffer_ptr.reset(new aligned_node_t[capacity]);
node_buffer = reinterpret_cast<node_t*>(buffer_ptr.get());
for(size_t i = 0; i < capacity - 1; ++i)
{
node_buffer[i].next = &node_buffer[i + 1];
}
node_buffer[capacity-1].next = nullptr;
}

template<class U>
bool push(U && data)
{
node_t *node = _pop(free_nodes);
if (node == nullptr)
return false;
node->value = std::forward<U>(data);
return true;
}

bool pop(T& data)
{
if (node == nullptr)
return false;
data = std::move(node->value);
_push(free_nodes, node);
return true;
}

private:
{
do {
if (orig.node == nullptr)
return nullptr;
next.aba = orig.aba + 1;
next.node = orig.node->next;
} while (!h.compare_exchange_weak(orig, next,
std::memory_order_acq_rel,
std::memory_order_acquire));
return orig.node;
}

{
do {
node->next = orig.node;
next.aba = orig.aba + 1;
next.node = node;
} while (!h.compare_exchange_weak(orig, next,
std::memory_order_acq_rel,
std::memory_order_acquire));
}
};

• This implementation looks good to me so far. The 2*ptr atomic swaps with the aba field should prevent the problems you were having with the first version. I still wonder if you really need all this complicated code vs either a lock/mutex version or a non-LIFO version. – JS1 Jun 19 '15 at 23:40
• @JS1 yeah this is definitely overhead :) would be great if you could look at unordered version i posted in old question with Gist link. thanx. – inspirit Jun 19 '15 at 23:43
• I just looked at your unordered version on Gist. That one seems correct and a lot simpler than these other versions. – JS1 Jun 20 '15 at 0:00
• Whats the source for those memory order specifiiers? Not saying they are wrong, just wonder whether they have to be analysed too, or if we just have to check whether they are correctly copied from a correct source. – MikeMB Jun 20 '15 at 20:23
• @MikeMB if you look into original article the author did not use any memory orders. I tried to figure out them myself. but since here we use Double Width CAS operation most likely it doesnt matter what order we specify it will always be full memory barrier – inspirit Jun 20 '15 at 22:20

The general push/pop logic of the stack looks fine. The memory management however is somewhat flawed:

Missing Destructor

From the perspective of the unique ptr, the stack doesn't contain Nodes, but uninitialized memory (effectively a char array). So at destruction of the stack object, it won't call the destructor of the individual nodes, which in turn won't call the destructor of value.

In order to correct that, one could write a destructor for stack that traverses the nodes and manually calls the destructor on them.

Assignment into uninitialized variables

node->value = std::forward<U>(data);


Upon construction, no actual nodes are created, but only properly aligned memory is reserved, on which you later call the assignment operator. I believe (although I'm not sure) this is OK if T is a POD, but if not, then (move) assigning values to them is definitively not allowed, because custom move assignment operators usually assume that this points to a valid, initialized object.

So in general, I see two possibilities:

1. You default construct all nodes upon construction of the stack and destruct them when stack is destructed, in which case std::aligned_storage is unnecessary. One can just use an array of nodes and pass it to the unique_ptr. In this case you also don't need a destructor for stack. Obviously that only works with default constructable T's and makes only sense, if T doesn't hold any resources after it has been moved from.

2. You actually create and delete objects upon calls to push and pop, in which case you have to use placement new (new(&node->value)T(std::forward<U>(data));) and manually call the destructor node->value.~T() (not delete &node->value)

I just want to point out that aside from the false sharing between head and free_nodes, which is avoided via padding, any thread calling push or pop will access both variables anyway and afterwards you still have false sharing between the actual nodes.
Also I want to repeat my warning from the comments that for some reason, VS2013 (and also 2015RT) seems to be unable to implement std::atomic<head_t> in a lock-free manner, in which case the whole structure is probably much slower than a normal stack with a mutex.