tpl_mpsc_queue.H File Reference

Unbounded lock-free multi-producer/single-consumer queue (Aleph::MpscQueue). More...

#include <atomic>
#include <memory>
#include <optional>
#include <utility>

Include dependency graph for tpl_mpsc_queue.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::MpscQueue< T >
	Unbounded lock-free multi-producer/single-consumer queue. More...
struct	Aleph::MpscQueue< T >::Node

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Typedefs
template<typename T >
using	Aleph::mpsc_queue = MpscQueue< T >
	Alias for Aleph::MpscQueue.

Detailed Description

Unbounded lock-free multi-producer/single-consumer queue (Aleph::MpscQueue).

MpscQueue<T> is an intrusive, singly-linked, unbounded FIFO queue that any number of producer threads can push into concurrently, while exactly one consumer thread pops from it. It implements the well-known Vyukov intrusive MPSC queue algorithm (http://www.1024cores.net/home/lock-free-algorithms/queues/intrusive-mpsc-node-based-queue): each push is a single atomic exchange (lock-free, wait-free per push), and the consumer walks the resulting singly-linked list without ever taking a lock.

How it differs from the existing queues in this library:

• Aleph::SpscQueue<T> (in concurrency_utils.H) is bounded and supports exactly one producer and one consumer; MpscQueue supports any number of producers but still exactly one consumer, and it never reports "full" (it grows one node per push, released back to the heap as the consumer pops).
• Aleph::BoundedChannel<T> is a general MPMC blocking channel. MpscQueue is narrower (MPSC only) but non-blocking end to end: a push never waits, and try_pop never waits.

Thread-safety

push/emplace may be called concurrently from any number of producer threads. try_pop/is_empty must only ever be called from a single, consistent consumer thread (never concurrently with each other, and never from more than one thread). Calling a consumer-side operation from more than one thread, or concurrently with another consumer-side call, is a precondition violation with no defined behavior – see docs/data_structure_thread_safety.md for the vocabulary this file follows (this is an MPSC topology).

Progress guarantees

Every push/emplace is lock-free: it completes after one atomic read-modify-write (exchange) on the shared insertion point, regardless of what other producers are doing, followed by one plain atomic store that never contends (each producer store targets a different, just- allocated node). No producer thread can block another. try_pop is normally lock-free too, but it has one narrow exception: if try_pop is called at the exact moment a producer has completed its exchange but not yet completed the following store, try_pop cannot yet tell "empty" from "a push is in flight" and conservatively reports empty (try_pop returns false/std::nullopt). That in-flight window is a single store's worth of time; the item becomes visible on the very next try_pop call once the racing producer finishes. This makes try_pop obstruction-free but not strictly lock-free in that narrow window – document and test it as such rather than claiming an unconditional lock-free consumer guarantee.

Memory ordering

Producers publish a node with exchange(..., acq_rel) on the shared insertion pointer followed by store(..., release) on the previous node's link. The consumer reads links with load(acquire), which synchronizes with the producer's release store and establishes happens-before for everything the producer wrote into the node (including the payload) before publishing it.

Ordering

FIFO per producer: two pushes from the same thread are dequeued in the order they were pushed. There is no guaranteed global order between pushes from different producer threads beyond what their relative real-time completion already implies.

T requirements

T must be move-constructible (or copy-constructible, for the const-reference push overload). Move-only types are fully supported.

See also

concurrency_utils.H for Aleph::SpscQueue (bounded, single producer) and Aleph::BoundedChannel (bounded, blocking, MPMC).

Author

Leandro Rabindranath Leon

Definition in file tpl_mpsc_queue.H.