Recently I was looking for some code to pass buffers between two threads in a memory allocator benchmark. The code had to be low overhead enough to ensure that it wouldn’t obscure the performance characteristics of the code being benchmarked, so I was looking for a data structure that was lock-free and reasonably simple and fast. It also had to avoid calling the allocator at any point.
The code below is what I came up with – it’s a blocking, single producer, single consumer lock-free ring buffer FIFO queue.
/* * Copyright (c) 2013, Linaro Limited * * Licensed under the 3 clause BSD license. */ #ifndef __LFQ_H__ #define __LFQ_H__ #include #include struct lfq { volatile unsigned int producer; volatile unsigned int consumer; size_t queue_size; void **data; }; /* Initialize a struct lfq with a size and array of memory. */ static inline void lfq_init(struct lfq *q, size_t queue_size, void **data) { q->queue_size = queue_size; q->data = data; q->producer = 0; q->consumer = 0; } /* Internal function to backoff on contention. */ static inline void __lfq_backoff(void) { sched_yield(); } /* Dequeue an item from the ring. Spin waiting if it is empty. */ static inline void *lfq_dequeue(struct lfq *q) { void *ret; while (q->producer == q->consumer) __lfq_backoff(); ret = q->data[q->consumer % q->queue_size]; q->consumer++; return ret; } /* Enqueue an item onto the ring. Spin waiting if it is full. */ static inline void lfq_queue(struct lfq *q, void *item) { while (q->producer - q->consumer >= q->queue_size) __lfq_backoff(); q->data[q->producer % q->queue_size] = item; __sync_synchronize(); q->producer++; } /* Test is the queue is empty. */ static inline bool lfq_empty(struct lfq *q) { return q->producer == q->consumer; } #endif