1 Mar
2016
1 Mar
'16
6:09 p.m.
On Tue, Mar 1, 2016 at 4:54 PM, Paul Davis <paul(a)linuxaudiosystems.com> wrote:
On Tue, Mar 1, 2016 at 10:12 AM, Sebastian Gesemann
<s.gesemann(a)gmail.com>
wrote:
Oh, don't be sad. I'm sure you're underestimating my understanding of the
topic.
Thank you all for the responses!
On Mon, Feb 29, 2016 at 9:05 PM, Harry van Haaren <harryhaaren(a)gmail.com>
wrote:
Sadly, you still don't understand how a lock-free ringbuffer works. On Mon, Feb 29, 2016 at 7:52 PM, Spencer Jackson
<ssjackson71(a)gmail.com>
wrote:
I've looked into JACK's ringbuffer implementation. It doesn't look too
complicated. Thank you all for suggesting it! But I'm a little bit
concerned about ISO standard compliance. According to the
multi-threading-aware update to the C11 and C++11 memory models, the
access to the ringbuffer's data (*buf) is technically a data race and
therefore invokes undefined behaviour. Only read_ptr/write_ptr are
somewhat protected (volatile). From what I understand, given the
C11/C++11 memory model, one is supposed to use "atomics" for all
read/write accesses in such situations (including *buf). But so far, I
havn't gathered much experience in this kind of lock-free programming. > The generic solution for cases like this is
a lock-free ringbuffer.
I've also used the jack ringbuffer for this and it was easy enough.
Simple tutorial on using JACK ringbuffer and C++ event class here:
https://github.com/harryhaaren/realtimeAudioThreading The key insight to have is this:
* the calculation of what can be read and what can be written may, in
fact
be incorrect due to threading
BUT
they are ALWAYS wrong in the "safe" direction. if the calculation is
wrong
it will ALWAYS underestimate data-to-be-read and space-to-be-written.
I understand that.
that is: you will never attempt to read data that
should not be read, and
you will never attempt to write to space that should not be written. This is
true of ALL lock-free ringbuffer designs, not just JACK's. The property
arises from the requirement that they are single-reader/single-writer. If
you violate this (e.g. attempt to move the read-ptr from the write thread or
vice versa), then all bets are off unless you use some higher level mutual
exclusion logic (which has no place in the ringbuffer itself. The design
works because in audio contexts, when you use a ringbuffer, you are more or
less guaranteed to be using a design where you keep reading and keep writing
to the ringbuffer over and over. The design cannot work for single-shot
communication where you must always collect ALL possible data in a
thread-synchronous fashion. This is not the case for audio work.
I understand that. So far, nothing you said was new to me.
Now, that said, there are some under-the-hood issues
with the actual JACK
ringbuffer code, but they have absolutely nothing to do with the high level
semantics, and that is what you're relying on. Those issues concern the use
of memory barriers, and are thus related to code-reordering not to
atomicity.
It depends on what meanings you attach to the words "atomics" and
"atomicity". I was trying to use the term "atomic" in a way
consistent
with the C11/C++11 memory model. In this context, atomicity is not
only about having logically multiple operations done as a single one
(fetch-and-add, compare-and-swap, etc) but it also involves memory
ordering hints (defaulting to sequential constistency but weaker
models are possible). So, it seems to me that you were not familiar
with this. I said I have little experience with lock-free programming
but that does not mean I'm completely unaware of the theoretical
aspects.
Although a clean fix/patch for this would still be a
good thing,
the ringbuffer's are used widely and they function as intended in almost all
situations.
Sure. I'm not surprized that it works in practice. If the compiler
emits a memory barrier for the volatile memory access, it's all you
need. But technically, it's still undefined behaviour.
You need not concern yourself with this issue if you
are just
starting out.
Well, for me, that's part of the fun -- figuring out how it's supposed
to be written without invoking U.B.
sg
1 Mar
1 Mar
6:40 p.m.
On Tue, Mar 1, 2016 at 12:09 PM, Sebastian Gesemann <s.gesemann(a)gmail.com>
wrote:
It depends on what meanings you attach to the words "atomics" and
"atomicity". I was trying to use the term "atomic" in a way
consistent
with the C11/C++11 memory model. In this context, atomicity is not
only about having logically multiple operations done as a single one
(fetch-and-add, compare-and-swap, etc) but it also involves memory
ordering hints (defaulting to sequential constistency but weaker
models are possible). So, it seems to me that you were not familiar
with this. I said I have little experience with lock-free programming
but that does not mean I'm completely unaware of the theoretical
aspects.
the evil that lock-free data structures seek to avoid is mutual exclusion
that involves stopping thread execution. they do not require that things
are atomic in either the weak or strong sense, but they do require that the
data structures remain consistent and accurate from the POV of the threads
that use them.
the JACK implementation relies on two things to work:
* pointer and integer operations are (weakly) atomic on all platforms
that JACK runs on
* code reordering will either not happen or will be prevented by the
compiler
the first assumption is a strong one, and the second one is at best weak,
and at worst actually incorrect.
the implementation inside Ardour uses glib's atomic wrappers to make the
second assumption strong.
https://github.com/Ardour/ardour/blob/master/libs/pbd/pbd/ringbuffer.h
(there is also a non-power-of-two size version one level up).
Well, for me, that's part of the fun -- figuring out how it's supposed
to be written without invoking U.B.
"Never let what you are really seeking to accomplish interfere with
deepening your knowledge of computer science".
2 Mar
2 Mar
2:21 p.m.
On Tue, Mar 1, 2016 at 6:40 PM, Paul Davis <paul(a)linuxaudiosystems.com> wrote:
On Tue, Mar 1, 2016 at 12:09 PM, Sebastian Gesemann
<s.gesemann(a)gmail.com>
wrote:
Exactly. Specifically, I would want to make sure that the consumer
thread sees the update to the write pointer *not before* the updates
to the buffer's memory. This was my concern because memory access with
three levels of partly shared caches between cores is more complicated
than possible instruction reorderings. But by now I have convinced
myself that this is guaranteed if the producer writes a new value to
write_pos with *release semantics* after updating the buffer and the
consumer loads the value of write_pos with *acquire semantics*.
http://en.cppreference.com/w/cpp/atomic/memory_order
It depends on what meanings you attach to the words "atomics" and
"atomicity". I was trying to use the term "atomic" in a way
consistent
with the C11/C++11 memory model. In this context, atomicity is not
only about having logically multiple operations done as a single one
(fetch-and-add, compare-and-swap, etc) but it also involves memory
ordering hints (defaulting to sequential constistency but weaker
models are possible). So, it seems to me that you were not familiar
with this. I said I have little experience with lock-free programming
but that does not mean I'm completely unaware of the theoretical
aspects.
the evil that lock-free data structures seek to avoid is mutual exclusion
that involves stopping thread execution. they do not require that things are
atomic in either the weak or strong sense, but they do require that the data
structures remain consistent and accurate from the POV of the threads that
use them. [...]
the implementation inside Ardour uses glib's atomic wrappers to make the
second assumption strong.
https://github.com/Ardour/ardour/blob/master/libs/pbd/pbd/ringbuffer.h
Nice. Yeah, it seems glib's atomics make the strongest possible memory
ordering guarantee (more than you actually need in this ringbuffer
case).
@all: Thank you for your responses. I'm going to use my own ringbuffer
using C++11's std::atomics.
@Paul:
As for the rest of the code, I just noticed a couple of other things
you might be interested in:
lines 103-107 are
if (w > r) {
return w - r;
} else {
return (w - r + size) & size_mask;
}
If I'm not miskaten, this could be simplified to
return (unsigned)(w - r) & size_mask;
The "(unsigned)" isn't even necessary because of integral promotion,
but I'd prefer this to be explicit.
The class violates the "rule of three". It allows a user to
copy-construct as well as copy-assign such ringbuffer objects
resulting in double-free errors. I'd prefer to manually disable the
copy constructor and assignment operator. Right now these special
member functions can be generated by the compiler and would do the
wrong thing.
I'd mark the constructor as explicit to avoid accidental int-to-buffer
conversions (like std::vector).
Cheers!
sg
5:55 p.m.
New subject: Code reordering
On 3/1/2016 11:40 AM, Paul Davis wrote:
the JACK implementation relies on two things to work:
* pointer and integer operations are (weakly) atomic on all
platforms that JACK runs on
* code reordering will either not happen or will be prevented by
the compiler
Does #2 mean that -O3 should always be avoided when compiling JACK
clients?
--
Jonathan E. Brickman jeb(a)ponderworthy.com (785)233-9977
Hear us at http://ponderworthy.com -- CDs and MP3 now available!
<http://ponderworthy.com/ad-astra/ad-astra.html>
Music of compassion; fire, and life!!!
5:59 p.m.
New subject: Code reordering
On Wed, Mar 2, 2016 at 11:55 AM, Jonathan Brickman <jeb(a)ponderworthy.com>
wrote:
On 3/1/2016 11:40 AM, Paul Davis wrote:
the JACK implementation relies on two things to work:
* pointer and integer operations are (weakly) atomic on all platforms
that JACK runs on
* code reordering will either not happen or will be prevented by the
compiler
Does #2 mean that -O3 should always be avoided when compiling JACK clients?
No, it does not.
4 Mar
4 Mar
10:16 a.m.
New subject: Code reordering
On Wed, Mar 2, 2016 at 5:55 PM, Jonathan Brickman <jeb(a)ponderworthy.com> wrote:
On 3/1/2016 11:40 AM, Paul Davis wrote:
As I said, I consider JACK's ringbuffer implementation to be broken.
According to the C11/C++11 memory model there is nothing in the code
that prevents reordering the update to write_ptr and the update to
*buf in jack_ringbuffer_write. The use of volatile only makes sure
that read/write accesses to the volatile variables are not reordered
or "optimized out" by caching. Specificaly, a volatile write is not a
release barrier. It does not constrain reordering with respect to
other memory locations (*buf). This makes the access to the buffer's
content unordered and invokes undefined behaviour.
Having said that, if you can be sure that the compiler does not
reorder this (by checking the assembly code, for example) then you
will be fine on an x86/x64 platform because this platform makes an
extra guarantee: writes in one thread are never seen out of order from
another thread's perspective.
the JACK implementation relies on two things to
work:
* pointer and integer operations are (weakly) atomic on all platforms
that JACK runs on
* code reordering will either not happen or will be prevented by the
compiler
Does #2 mean that -O3 should always be avoided when compiling JACK clients? 
11:21 p.m.
New subject: Code reordering
On Fri, Mar 04, 2016 at 10:16:02AM +0100, Sebastian Gesemann wrote:
As I said, I consider JACK's ringbuffer
implementation to be broken.
According to the C11/C++11 memory model there is nothing in the code
that prevents reordering the update to write_ptr and the update to
*buf in jack_ringbuffer_write. The use of volatile only makes sure
that read/write accesses to the volatile variables are not reordered
or "optimized out" by caching. Specificaly, a volatile write is not a
release barrier. It does not constrain reordering with respect to
other memory locations (*buf). This makes the access to the buffer's
content unordered and invokes undefined behaviour.
What if writing to the buffer and updating the write pointer is
done by two separate function calls (and in that order of course) ?
The second could be inlined, but even then it's still a function call.
Ciao,
--
FA
A world of exhaustive, reliable metadata would be an utopia.
It's also a pipe-dream, founded on self-delusion, nerd hubris
and hysterically inflated market opportunities. (Cory Doctorow)
5 Mar
5 Mar
10:17 a.m.
New subject: Code reordering
On Fri, Mar 4, 2016 at 11:21 PM, Fons Adriaensen <fons(a)linuxaudio.org> wrote:
On Fri, Mar 04, 2016 at 10:16:02AM +0100, Sebastian
Gesemann wrote:
You're right. Calling functions the compiler does not know anything
about will constrain reordering because the compiler has to assume the
worst about what happens in this function. But once you give it the
chance of inlining or enable link-time optimization, this could break
again. In general, you would want to avoid relying on compilers being
"stupid enough". Better not violate the contract in the first place.
Control of memory ordering and atomics are officially part of the C
and C++ languages since 2011. GCC already supported this when the ISO
standards was finalized. Microsoft and Clang started supporting it in
2012. So, it's been pretty much portable since 2012. This is 2016.
IMHO, it's time to make use of it. :)
Cheers!
sg
As I said, I consider JACK's ringbuffer
implementation to be broken.
According to the C11/C++11 memory model there is nothing in the code
that prevents reordering the update to write_ptr and the update to
*buf in jack_ringbuffer_write. The use of volatile only makes sure
that read/write accesses to the volatile variables are not reordered
or "optimized out" by caching. Specificaly, a volatile write is not a
release barrier. It does not constrain reordering with respect to
other memory locations (*buf). This makes the access to the buffer's
content unordered and invokes undefined behaviour.
What if writing to the buffer and updating the write pointer is
done by two separate function calls (and in that order of course) ?
The second could be inlined, but even then it's still a function call.
2980
days inactive
2984
days old
linux-audio-dev@lists.linuxaudio.org
7 comments
4 participants
participants (4)
-
Fons Adriaensen -
Jonathan Brickman -
Paul Davis -
Sebastian Gesemann