Looking for the right ring buffer implementation in C

8
votes

I am looking for a ring buffer implementation (or pseudocode) in C with the following characteristics:

  • multiple producer single consumer pattern (MPSC)
  • consumer blocks on empty
  • producers block on full
  • lock-free (I expect high contention)

So far I've been working only with SPSC buffers - one per producer - but I would like to avoid the continuous spinning of the consumer to check for new data over all its input buffers (and maybe to get rid of some marshaling threads in my system).

I develop for Linux on Intel machines.

2
cmultithreadingproducer-consumerlock-freecircular-buffer
I don't know what enviroment you're in, but in Win32 you can use WaitForMultipleObjects to have consumer wait at all queues at once without spinning. - Agent_L
I am sorry, I didn't mention that I mainly work on Linux - ziu
Just in case you won't get a real answer, it'll be a breeze to sync multiple buffers with this: neosmart.net/blog/2011/… - Agent_L
Take a look at this article on Port Windows IPC apps to Linus (ibm.com/developerworks/linux/library/l-ipc2lin3/index.html) which describes how the different synchronization primitives compare between Windows and Linux. This is a multipart article. I would expect that some kind of locking will needed in order to ensure that only one process or thread at a time has access to the management data structures for the queue between producers and consumer. - Richard Chambers
And here is an interesting article on Dr. Dobb's about "Use Critical Sections (Preferably Locks) to Eliminate Races" drdobbs.com/cpp/use-critical-sections-preferably-locks-t/… - Richard Chambers

2 Answers

4
votes

See liblfds, a lock-free MPMC ringbuffer. It won't block at all—lock-free data structures don't tend to do this, because the point of being lock-free is to avoid blocking; you need to handle this, when the data structure comes back to you with a NULL—returns NULL if you try to read on empty, but doesn't match your requirement when writing on full; here, it will throw away the oldest element and give you that for your write.

However, it would only take a small modification to obtain that behaviour.

But there may be a better solution. The tricky part of a ringbuffer is when full getting the oldest previous element and re-using that. You don't need this. I think you could take the SPSC memory-barrier only circular buffer and rewrite it using atomic operations. That will be a lot more performant that the MPMC ringbuffer in liblfds (which is a combination of a queue and a stack).

3
votes

I think I have what you are looking for. It is a lock free ring buffer implementation that blocks producer/consumer. You only need access to atomic primitives - in this example I will use gcc's sync functions.

It has a known bug - if you overflow the buffer by more than 100% it is not guaranteed that the queue remains FIFO (it will still process them all eventually).

This implementation relies on reading/writing the buffer elements as being an atomic operation (which is pretty much guaranteed for pointers)

struct ringBuffer
{
   void** buffer;
   uint64_t writePosition;
   size_t size;
   sem_t* semaphore;
}

//create the ring buffer
struct ringBuffer* buf = calloc(1, sizeof(struct ringBuffer));
buf->buffer = calloc(bufferSize, sizeof(void*));
buf->size = bufferSize;
buf->semaphore = malloc(sizeof(sem_t));
sem_init(buf->semaphore, 0, 0);

//producer
void addToBuffer(void* newValue, struct ringBuffer* buf)
{
   uint64_t writepos = __sync_fetch_and_add(&buf->writePosition, 1) % buf->size;

   //spin lock until buffer space available
   while(!__sync_bool_compare_and_swap(&(buf->buffer[writePosition]), NULL, newValue));
   sem_post(buf->semaphore);
}    

//consumer
void processBuffer(struct ringBuffer* buf)
{
   uint64_t readPos = 0;
   while(1)
   {
       sem_wait(buf->semaphore);

       //process buf->buffer[readPos % buf->size]
       buf->buffer[readPos % buf->size] = NULL;
       readPos++;
   }
}