mpmc_queue.h File Reference

Lock-free bounded multi-producer multi-consumer queue with optional blocking behaviour. More...

#include <array>
#include <atomic>
#include <chrono>
#include <cstddef>
#include <limits>
#include <memory>
#include <mutex>
#include <new>
#include <stdexcept>
#include <utility>
#include "./condition_variable.h"
#include "./macros.h"
#include "./utils.h"

Include dependency graph for mpmc_queue.h:

Go to the source code of this file.

Classes
class	vlink::MpmcQueue< T >
	Fixed-capacity, lock-free, cache-line-aligned MPMC ring buffer. More...

Namespaces
namespace	vlink

Macros
#define	VLINK_NO_INSTRUMENT

Detailed Description

Lock-free bounded multi-producer multi-consumer queue with optional blocking behaviour.

MpmcQueue<T> is a fixed-capacity, cache-line-aligned, lock-free MPMC ring buffer based on a turn-counting algorithm. Each slot contains an atomic turn counter that tracks whether the slot is empty (ready for a producer) or full (ready for a consumer).

Concurrency model:

• Producers atomically increment head_ to claim a slot, then wait until chunk.turn == turn(head) * 2 (slot is empty) before constructing the value.
• Consumers atomically increment tail_ to claim a slot, then wait until chunk.turn == turn(tail) * 2 + 1 (slot is full) before moving the value out.
• All waits spin for kFirstSpinTimes (32) iterations before calling yield_cpu().

Behaviour modes:

Behavior	Effect on emplace/push	Effect on pop
kNoBehavior	No notification	No blocking
kConditionBehavior	Signals cv_not_empty_ on push	Signals cv_not_full_ on pop

kConditionBehavior enables wait_not_empty() and wait_not_full() to wake correctly. Use it with kBlockStrategy message loops.

Cache-line alignment:

• head_ and tail_ are each aligned to 64 bytes to prevent false sharing.
• Each Chunk slot is also 64-byte aligned.
• The queue object itself is a multiple of 64 bytes.

Note

• emplace() / pop() block indefinitely (spinning) until a slot is available. For bounded producers, use try_emplace() / try_push() instead.
• notify_to_quit() sets a quit flag and wakes all blocked wait_not_empty() / wait_not_full() calls. After calling this, further pushes are silently dropped.
• Capacity must be >= 1; passing 0 throws std::invalid_argument.
• The VLINK_NO_INSTRUMENT attribute suppresses GCC's -finstrument-functions on Linux.

Example

vlink::MpmcQueue<int> q(1024);
 
// Producer thread:
q.push<vlink::MpmcQueue<int>::kConditionBehavior>(42);
 
// Consumer thread:
q.wait_not_empty();
int val;
q.pop<vlink::MpmcQueue<int>::kConditionBehavior>(val);

Macro Definition Documentation

VLINK_NO_INSTRUMENT

#define VLINK_NO_INSTRUMENT