[LAD] [LAU] Simple, easy multithreaded circular buffer library for Linux?

[Jack O'Quin]

On Sat, Oct 18, 2008 at 10:45 PM, Paul Coccoli <pcoccoli at gmail.com> wrote:
> On Sat, Oct 18, 2008 at 11:29 PM, Jack O'Quin <jack.oquin at gmail.com> wrote:
>> This is wrong.  For the single reader, single writer case, atomic operations
>> are *not* necessary.  The bug, as was already pointed out, is due to storing
>
> Let's agree to disagree, then.  Single-reader, single-writer does not
> automatically make something SMP safe.  There is large body of
> literature on lock-free data structures that agrees with me; someone
> posted a link to a collection of those earlier in the thread.

Let's not.  This is not just a matter of opinion.  If you read that literature,
you will find that the ring buffer *is* safe for the single reader,
single writer
case.  In many other SMP situations, atomic operations *are* required,
but not for ring buffers.

However, for non-x86 machines which do not provide strong cache
coherency between processors (NUMA, PowerPC, etc.), I believe it *is*
possible for the read thread to look at buffer locations whose contents have
been written by the write thread, but those data may not yet be visible to
the other processor.  This is why memory barriers may be needed on some
machines.  For portability, we should include them in the code.  On many
machines, they will be no-ops, but that's OK.

>> the unmasked pointer in the ringbuffer, allowing the other thread to see it
>> in an invalid state.
>
> Paul Davis disagrees, and I have yet to come up with a scenario where
> read_ptr can be assigned a value larger than size.  And I'm the one
> who pointed out the bug in the first place.

If the amount read or written exactly fills the buffer, then a read or write
pointer equal to the last entry plus one will be stored momentarily, before
the correct (masked) value wraps it back to the beginning of the buffer.  If
the other thread looks at it in that state, I believe data will be
copied outside
the bounds of the buffer, which is bad.

Note that this is a bug even in the uni-processor case.  SMP merely makes
it more likely.
-- 
 joq