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

[Jack O'Quin]

On Sat, Oct 18, 2008 at 10:22 PM, Paul Coccoli <pcoccoli at gmail.com> wrote:

> [Switched from LAU to LAD]
>
> Forget I said anything about context switches.  Those don't matter.
> The concern here is SMP systems.  The bug in the original code is +=
> operator used to increment the read and write pointers.  That operator
> generates the addl instruction, which is not atomic.  It needs to be
> locked on SMP.  The reason Olivier's patch works is because the
> increment is done on a temp and then assinged (using plain old =) to
> the shared variable.  The assignment *is* atomic (since size_t is 4
> bytes and presumably aligned to a 4-byte boundary).
>
> I can't prove this right now, but I think I'm correct.  That means it
> may be possible to make the original code SMP-safe without the
> (subtle) change in semantics Olivier's patch makes.  Like increment a
> temp, store it, mask the temp, store it again.
>
> You can't write lock-free data structures without atomic operations.

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
the unmasked pointer in the ringbuffer, allowing the other thread to see it
in an invalid state.

> While the x86 doesn't need any memory barriers (all stores are seen by
> all other CPUs), other platforms could (someone mentioned PowerPC).
> The code still needs to be patched for that; just make the x86 version
> no-ops.

This is correct.  Some other architectures (PowerPC, etc.) *do*
require the memory barrier.  So, for portability it should be included.

-- 
 joq