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

[Paul Coccoli]

On Sat, Oct 18, 2008 at 5:30 PM, Fons Adriaensen <fons at kokkinizita.net> wrote:
> On Sat, Oct 18, 2008 at 10:56:31PM +0200, Paul Davis wrote:
>
>> if read_ptr > size then the math should result in the write space being
>> *under* estimated. if thats not happening then my worst nightmares come
>> true, which has happened before. is there a signed/unsigned issue going
>> on here?
>
> The only way to know is to verify all the possible cases in
> jack_ringbuffer_write_space() and jack_ringbuffer_read_space(),
> taking into account that the masking operation may not have
> been applied at the time these are called, and that 'the other'
> *_ptr could be >= size.
>

[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.

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.