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