Simple lock-free ring buffer implementation

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__


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)

/* 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)
  ret = q->data[q->consumer % q->queue_size];
  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)
  q->data[q->producer % q->queue_size] = item;

/* Test is the queue is empty. */
static inline bool lfq_empty(struct lfq *q)
  return q->producer == q->consumer;

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s