Multi-Producer Multi-Consumer FIFO Ring

include/structures/mpmc_fifo_ring.h View source View on GitHub

Bounded Vyukov MPMC FIFO ring, like

MPMC_FIFO_RING_DECLARE(foo_ring, struct foo);

emits struct foo_ring and foo_ring_{init,destroy,enqueue,dequeue, empty,capacity,drain,produced,consumed}

Structs

mpmc_fifo_ring_hdr

struct mpmc_fifo_ring_hdr (1 field) source

§ atomic_uint64_t tail

Functions

mpmc_fifo_ring_slots_alloc

void * mpmc_fifo_ring_slots_alloc(
    struct mpmc_fifo_ring_hdr *h,
    size_t cap,
    size_t stride
)

source

cap rounds up to next_pow2

mpmc_fifo_ring_slots_free

void mpmc_fifo_ring_slots_free(
    struct mpmc_fifo_ring_hdr *h,
    void *slots
)

source

mpmc_fifo_ring_claim

cc_always_inline bool mpmc_fifo_ring_claim(
    atomic_uint64_t *cursor,
    size_t mask,
    void *slots,
    size_t stride,
    uint64_t lag,
    uint64_t *pos_out
)

source

mpmc_fifo_ring_claim_range

cc_always_inline bool mpmc_fifo_ring_claim_range(
    struct mpmc_fifo_ring_hdr *h,
    void *slots,
    size_t stride,
    uint64_t *first_out,
    uint64_t *count_out
)

source

mpmc_fifo_ring_hdr_empty

bool mpmc_fifo_ring_hdr_empty(const struct mpmc_fifo_ring_hdr *h)

source

_drain

size_t name## _drain(struct name *q)

source

Drain and return how many were drained

_empty

bool name## _empty(const struct name *q)

source

_capacity

size_t name## _capacity(const struct name *q)

source

_produced

cc_unused uint64_t name## _produced(struct name *q)

source

_consumed

cc_unused uint64_t name## _consumed(struct name *q)

source

Macros

MPMC_FIFO_RING_DECLARE

#define MPMC_FIFO_RING_DECLARE(name, T)

source

Expansion

#define MPMC_FIFO_RING_DECLARE(name, T) \
    struct name##_slot { \
        atomic_uint64_t seq; \
        T val; \
    }; \
 \
    struct name { \
        struct name##_slot *slots; \
        struct mpmc_fifo_ring_hdr hdr; \
    }; \
 \
    static inline bool name##_init(struct name *q, size_t cap) { \
        q->slots = \
            mpmc_fifo_ring_slots_alloc(&q->hdr, cap, sizeof(*q->slots)); \
        return q->slots != NULL; \
    } \
 \
    static inline void name##_destroy(struct name *q) { \
        mpmc_fifo_ring_slots_free(&q->hdr, q->slots); \
        q->slots = NULL; \
    } \
 \
    static inline bool name##_enqueue(struct name *q, T v) { \
        uint64_t pos; \
        if (!mpmc_fifo_ring_claim(&q->hdr.head, q->hdr.mask, q->slots, \
                                  sizeof(*q->slots), 0, &pos)) \
            return false; \
 \
        struct name##_slot *s = &q->slots[pos & q->hdr.mask]; \
        s->val = v; \
        atomic_store_release(&s->seq, pos + 1); \
        return true; \
    } \
 \
    static inline bool name##_dequeue(struct name *q, T *out) { \
        uint64_t pos; \
        if (!mpmc_fifo_ring_claim(&q->hdr.tail, q->hdr.mask, q->slots, \
                                  sizeof(*q->slots), 1, &pos)) \
            return false; \
 \
        struct name##_slot *s = &q->slots[pos & q->hdr.mask]; \
        if (out) \
            *out = s->val; \
 \
        s->val = (T) {0}; \
        atomic_store_release(&s->seq, pos + q->hdr.mask + 1); \
        return true; \
    } \
 \
    /* Drain and return how many were drained */