I have an C++ implementation of the MPSC queue. Under normal circumstances
it works correctly, but under heavy load it skips nodes when releasing.
That is, in a test of many writers and a single reader, nodes are popped
in the same order each thread wrote them, but sometimes a node does not get
returned at all. If anyone can see what is wrong with this I would
appreciate it very much.
class Node
{
public:
// Atomic here as a shortcut for placing
// memory fences. Assignment is an atomic
// store with an acquire and release fence
std::atomic<Node*> next;
};
template <typename T>
class MpscQueue
{
public:
MpscQueue()
: _head(&_stub)
, _tail(&_stub)
{
_stub.next = nullptr;
}
void push(T* obj)
{
_push(obj);
}
T* pop()
{
auto tail = _tail;
Node* next = tail->next;
if (tail == &_stub)
{
if (!next)
{
return nullptr;
}
tail = next;
next = next->next;
}
if (next)
{
_tail = next;
return static_cast<T*>(tail);
}
if (tail != _head)
{
return nullptr; // HERE
}
_push(&_stub);
next = tail->next;
if (next)
{
_tail = next;
return static_cast<T*>(tail);
}
return nullptr; // HERE
}
private:
void _push(Node* node)
{
node->next = nullptr;
auto prev = _head.exchange(node);
prev->next = node;
}
std::atomic<Node*> _head;
Node* _tail;
Node _stub;
};
As a clue, if I replace the lines above marked HERE with a call to this
function my tests always pass, except one time in one configuration where
it entered a continuous loop.
T* spin_pop(Node* tail)
{
do
{
_tail = tail->next;
} while (!_tail);
return static_cast<T*>(tail);
}
--
---
You received this message because you are subscribed to the Google Groups
"Scalable Synchronization Algorithms" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to lock-free+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/lock-free/07cb3e3f-9933-4588-ab74-50aec4206c67%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
