Looking for the right ring buffer implementation in C
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.
Answer
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).