15 Dec
2009
15 Dec
'09
9:44 a.m.
Here are the details...
http://effocore.googlecode.com/files/EffoDesign_LockFree.pdf
15 Dec
15 Dec
9:54 a.m.
New subject: Atomic Operations
On Tue, Dec 15, 2009 at 8:43 AM, lieven moors <lievenmoors(a)gmail.com> wrote:
Here are the details...
http://effocore.googlecode.com/files/EffoDesign_LockFree.pdf
these concepts have been around in this community (and others) for
years. i suspect that it is more than a decade since the folks at
GRAME published their paper on lock free data structures (used in
MidiShare), and its probably a decade or more since LAD first
discussed lock free (single-read/single-writer) ringbuffers. there's
nothing wrong with having new eyes and new ideas but i couldn't see
anything from a casual glance in that paper that hasn't been
documented and used by people on this list for a long time.
--p
9:58 a.m.
New subject: Atomic Operations
On Tue, Dec 15, 2009 at 8:54 AM, Paul Davis <paul(a)linuxaudiosystems.com> wrote:
these concepts have been around in this community (and
others) for
years. i suspect that it is more than a decade since the folks at
GRAME published their paper on lock free data structures (used in
MidiShare), and its probably a decade or more since LAD first
discussed lock free (single-read/single-writer) ringbuffers. there's
nothing wrong with having new eyes and new ideas but i couldn't see
anything from a casual glance in that paper that hasn't been
documented and used by people on this list for a long time.
i should perhaps note that there tends to be less use of generic lock
free data structures because of the absence of nice libraries. maybe
effo can be a useful addition there. its not as if its the first one,
however.
10:24 a.m.
New subject: Atomic Operations
On Tue, 15 Dec 2009, Paul Davis wrote:
i should perhaps note that there tends to be less use
of generic lock
free data structures because of the absence of nice libraries. maybe
effo can be a useful addition there. its not as if its the first one,
however.
Also worth mentioning... for C++ fans out there...
The ringbuffer shipped with libjack is a C port of the
RingBuffer<T> container from libpbd in Ardour (written by
Paul Davis and Benno Senoner).
This implementation uses the glib atomic ops and some glib
types. Since my app doesn't currently use glib, I was
looking at replacing those with some equivalent. That's
partially how this thread got started. :-)
Peace,
Gabriel
10:25 a.m.
New subject: Atomic Operations
On Tue, Dec 15, 2009 at 9:24 AM, Gabriel M. Beddingfield
<gabriel(a)teuton.org> wrote:
The ringbuffer shipped with libjack is a C port of the
RingBuffer<T>
container from libpbd in Ardour (written by Paul Davis and Benno Senoner).
This implementation uses the glib atomic ops and some glib types. Since my
app doesn't currently use glib, I was looking at replacing those with some
equivalent. That's partially how this thread got started. :-)
why not use glib? as some folk like to say: "even Qt does these days" :)
10:36 a.m.
New subject: Atomic Operations
On Tue, 15 Dec 2009, Paul Davis wrote:
why not use glib? as some folk like to say: "even
Qt does these days" :)
True... but I'm just trying to avoid a "dependency creep"
(which becomes a bigger issue when porting to Windows).
No glib hate. I just don't want to add a dependency to glib
so that I can use a single class template.
Peace,
Gabriel
11:48 a.m.
New subject: Atomic Operations
On Tuesday 15 December 2009 15:36:04 Gabriel M. Beddingfield wrote:
On Tue, 15 Dec 2009, Paul Davis wrote:
But when its a template, why not include that header in your project?
The original shouldn't change that much that it qualifies as a "must have
external dependency"?
Arnold
why not use glib? as some folk like to say:
"even Qt does these days" :)
True... but I'm just trying to avoid a
"dependency creep"
(which becomes a bigger issue when porting to Windows).
No glib hate. I just don't want to add a dependency to glib
so that I can use a single class template.
12:01 p.m.
New subject: Atomic Operations
On Tue, 15 Dec 2009, Arnold Krille wrote:
On Tuesday 15 December 2009 15:36:04 Gabriel M.
Beddingfield wrote:
I am. :-)
Guess I should have said that. Otherwise, it would appear I
have made this very silly statement: "I have added a
dependency on Ardour (libpbd), but I refuse to add a
dependency on glib!"
-gabriel
No glib hate. I just don't want to add a
dependency to glib
so that I can use a single class template.
But when its a template, why not include that header in your project?
The original shouldn't change that much that it qualifies as a "must have
external dependency"? 
12:23 p.m.
New subject: Atomic Operations
On Tue, Dec 15, 2009 at 9:24 AM, Gabriel M. Beddingfield
<gabriel(a)teuton.org> wrote:
On Tue, 15 Dec 2009, Paul Davis wrote:
For one of my projects I once ported the kfifo implementation in the
Linux kernel to a C++ class. Feel free to use it if you'd find it
useful. (GPL)
http://github.com/radarsat1/dimple/blob/master/src/CircBuffer.h
Steve
i should perhaps note that there tends to be less
use of generic lock
free data structures because of the absence of nice libraries. maybe
effo can be a useful addition there. its not as if its the first one,
however.
Also worth mentioning... for C++ fans out there...
The ringbuffer shipped with libjack is a C port of the
RingBuffer<T> container from libpbd in Ardour (written by
Paul Davis and Benno Senoner).
This implementation uses the glib atomic ops and some glib
types. Since my app doesn't currently use glib, I was
looking at replacing those with some equivalent. That's
partially how this thread got started. :-) 
12:37 p.m.
New subject: Atomic Operations
For one of my projects I once ported the kfifo
implementation in the
Linux kernel to a C++ class. Feel free to use it if you'd find it
useful. (GPL)
http://github.com/radarsat1/dimple/blob/master/src/CircBuffer.h
you should add memory barriers, when reading or writing to the reader or
writer indices ... my implementation (without size limitation to a power
of two) can be found at [1]
hth, tim
[1]
http://tim.klingt.org/git?p=boost_lockfree.git;a=blob;f=boost/lockfree/ring…
--
tim(a)klingt.org
http://tim.klingt.org
art is short - life is long
Jack Kerouac
2:33 p.m.
New subject: Atomic Operations
Hi Tim,
On Tue, 15 Dec 2009, Tim Blechmann wrote:
you should add memory barriers, when reading or writing to the reader or
Actually, his implementation is similar to ringbuffer.c in
libjack... and assumes that reading and writing can happen
atomically (as was pointed out by someone else) -- which can
be managed with single reader / single writer
requirement.[a]
Unless I've misunderstood the code, ringbuffer.c is /not/
using special atomic operations.
writer indices ... my implementation (without size
limitation to a power
of two) can be found at [1]
[1]
http://tim.klingt.org/git?p=boost_lockfree.git;a=blob;f=boost/lockfree/ring…
This looks nice, too. Have you considered trying to give it
an interface like the existing boost::circular_buffer<T,Alloc>?
The distinguishing feature of your implementation is that is
lock-free... but it's otherwise the same concept (and
already in Boost).
Also, does yours have a single reader / single writer
requirement?
I tried to clone the git repos, but hit ^C when it was
20% and 40MB (!!). :-)
Peace,
Gabriel
[a] I'm talking over my head on this point, so
if I have misspoken, please be gentle! :-)
2:47 p.m.
New subject: Atomic Operations
you should add memory barriers, when reading or writing to the reader or
Actually, his implementation is similar to ringbuffer.c in
libjack... and assumes that reading and writing can happen
atomically (as was pointed out by someone else) -- which can
be managed with single reader / single writer
requirement.[a]
Unless I've misunderstood the code, ringbuffer.c is /not/
using special atomic operations. writer indices
... my implementation (without size limitation to a power
of two) can be found at [1]
[1]
http://tim.klingt.org/git?p=boost_lockfree.git;a=blob;f=boost/lockfree/ring…
This looks nice, too. Have you considered trying to give it
an interface like the existing boost::circular_buffer<T,Alloc>?
The distinguishing feature of your implementation is that is
lock-free... but it's otherwise the same concept (and
already in Boost). Also, does yours have a single reader / single writer
requirement?
yes
I tried to clone the git repos, but hit ^C when it was
20% and 40MB (!!). :-)
it includes the full source tree of boost (160mb on my machine)
cheers, tim
--
tim(a)klingt.org
http://tim.klingt.org
Happiness is a byproduct of function, purpose, and conflict; those who
seek happiness for itself seek victory without war.
William S. Burroughs
3:04 p.m.
New subject: Atomic Operations
On Tue, Dec 15, 2009 at 1:47 PM, Tim Blechmann <tim(a)klingt.org> wrote:
the jack ringbuffer code is not multiprocessor safe then ... it is prbly
not an issue for jack1, but maybe for jack2, if it is used there ...
this was discussed at some considerable length on jack-devel last year, IIRC.
for single reader/single writer ringbuffers, i believe that we
concluded that memory barriers are not necessary.
you should add memory barriers, when reading or writing to the reader or
Actually, his implementation is similar to ringbuffer.c in
libjack... and assumes that reading and writing can happen
atomically (as was pointed out by someone else) -- which can
be managed with single reader / single writer
requirement.[a]
Unless I've misunderstood the code, ringbuffer.c is /not/
using special atomic operations. 
3:42 p.m.
New subject: Atomic Operations
On 12/15/2009 08:04 PM, Paul Davis wrote:
On Tue, Dec 15, 2009 at 1:47 PM, Tim Blechmann
<tim(a)klingt.org> wrote:
the jack ringbuffer code is not multiprocessor
safe then ... it is prbly
not an issue for jack1, but maybe for jack2, if it is used there ...
this was discussed at some considerable length on jack-devel last year, IIRC.
for single reader/single writer ringbuffers, i believe that we
concluded that memory barriers are not necessary.
No, to me the conclusion was: we can't programmatically prove that memory
barriers are needed (even on the most vulnerable architectures), but the theory
say that they are, and they should be added for correctness.
--
Olivier
>
http://github.com/radarsat1/dimple/blob/master/src/CircBuffer.h
you should add memory barriers, when reading or writing to the reader or
Actually,
his implementation is similar to ringbuffer.c in
libjack... and assumes that reading and writing can happen
atomically (as was pointed out by someone else) -- which can
be managed with single reader / single writer
requirement.[a]
Unless I've misunderstood the code, ringbuffer.c is /not/
using special atomic operations. 
8:11 p.m.
New subject: Atomic Operations
Yikes, not this again....
On Dec 15, 2009, at 11:42 AM, Olivier Guilyardi wrote:
On 12/15/2009 08:04 PM, Paul Davis wrote:
My understanding matches Olivier's. Intel processors have strong memory
ordering, and so on them the jack ringbuffer is safe without memory
barriers. However, some PPC processors, and SPARC V9s under linux
(but not
Solaris), use weak memory ordering, and on them, the jack ringbuffer
code
can theoretically fail.
See the "ring buffer memory barriers" discussion on jack-devel back in
October of last year for more information; in particular, this article
by Paul E. McKenney is very helpful:
http://www.linuxjournal.com/article/8211
And, until the jack ringbuffer gets fixed, the PortAudio ringbuffer
appears safe for use on multiprocessor weakly-ordered systems.
-Sean
this was discussed at some considerable length on
jack-devel last
year, IIRC.
for single reader/single writer ringbuffers, i believe that we
concluded that memory barriers are not necessary.
No, to me the conclusion was: we can't programmatically prove that
memory
barriers are needed (even on the most vulnerable architectures),
but the theory
say that they are, and they should be added for correctness.
16 Dec
16 Dec
5:44 a.m.
New subject: Atomic Operations
this was discussed at some considerable length on
jack-devel last
year, IIRC.
for single reader/single writer ringbuffers, i believe that we
concluded that memory barriers are not necessary.
No, to me the conclusion was: we can't programmatically prove that
memory
barriers are needed (even on the most vulnerable architectures),
but the theory
say that they are, and they should be added for correctness. See the "ring buffer memory barriers"
discussion on jack-devel back in
October of last year for more information; in particular, this article
by Paul E. McKenney is very helpful:
http://www.linuxjournal.com/article/8211
memory-barriers.txt of the linux kernel documentation is interesting as
well ...
cheers, tim
--
tim(a)klingt.org
http://tim.klingt.org
Contrary to general belief, an artist is never ahead of his time but
most people are far behind theirs.
Edgar Varèse
1:50 p.m.
New subject: Atomic Operations
On 12/16/2009 10:43 AM, Tim Blechmann wrote:
My understanding
matches Olivier's. Intel processors have strong memory
ordering, and so on them the jack ringbuffer is safe without memory
barriers. However, some PPC processors, and SPARC V9s under linux
(but not
Solaris), use weak memory ordering, and on them, the jack ringbuffer
code
can theoretically fail.
exactly, the issue may not appear on x86, because of its memory
consistency, weakly-ordered machines will need some barriers ...
The point is, I wrote ringbuffer stress tests, and someone reported on this list
that they succeeded on a weakly-ordered (PowerPC SMP) system, even without
memory barriers. Anyway...
The portaudio ringbuffer is also a good source of inspiration I think:
http://portaudio.com/trac/browser/portaudio/trunk/src/common/pa_ringbuffer.c
In short, they use memory barriers at only three places, especially:
- "to ensure that previous writes are seen before we update the write index"
- "to ensure that previous writes are always seen before updating the (read)
index."
It shouldn't be so complex to fix in jack I guess.
--
Olivier
this was
discussed at some considerable length on jack-devel last
year, IIRC.
for single reader/single writer ringbuffers, i believe that we
concluded that memory barriers are not necessary.
No, to me the conclusion was: we
can't programmatically prove that
memory
barriers are needed (even on the most vulnerable architectures),
but the theory
say that they are, and they should be added for correctness. See the
"ring buffer memory barriers" discussion on jack-devel back in
October of last year for more information; in particular, this article
by Paul E. McKenney is very helpful:
http://www.linuxjournal.com/article/8211
memory-barriers.txt of the linux kernel documentation is interesting as
well ...
1:57 p.m.
New subject: Atomic Operations
> this was
discussed at some considerable length on jack-devel last
> year, IIRC.
> for single reader/single writer ringbuffers, i believe that we
> concluded that memory barriers are not necessary.
No, to me the conclusion was: we can't programmatically prove that
memory
barriers are needed (even on the most vulnerable architectures),
but the theory
say that they are, and they should be added for correctness.
My understanding
matches Olivier's. Intel processors have strong memory
ordering, and so on them the jack ringbuffer is safe without memory
barriers. However, some PPC processors, and SPARC V9s under linux
(but not
Solaris), use weak memory ordering, and on them, the jack ringbuffer
code
can theoretically fail. See the "ring buffer memory barriers"
discussion on jack-devel back in
October of last year for more information; in particular, this article
by Paul E. McKenney is very helpful:
http://www.linuxjournal.com/article/8211
memory-barriers.txt of the linux kernel documentation is interesting as
well ...
17 Dec
17 Dec
7:40 a.m.
New subject: Atomic Operations
On 12/16/2009 06:57 PM, Tim Blechmann wrote:
My tests helped to find and fix a race bug in jack ringbuffer. I guess this
should have worked for memory barriers too. Unless they need to run for a
century before an error occur.. ;)
The portaudio ringbuffer is also a good source of inspiration I think:
http://portaudio.com/trac/browser/portaudio/trunk/src/common/pa_ringbuffer.c
In short, they use memory barriers at only three places, especially:
- "to ensure that previous writes are seen before we update the write index"
- "to ensure that previous writes are always seen before updating the (read)
index."
the kfifo doesn't look too different, either ...
Okay, I got a patch for Jack1's ringbuffer, it's not finished, but it's a
beginning. I think it misses some "read" memory barriers, as described in
kernel's memory-barriers.txt (in SMP BARRIER PAIRING) : "A write barrier should
always be paired with a data dependency barrier or read barrier[...]".
It's attached. What do you think?
--
Olivier
Index: libjack/ringbuffer.c
===================================================================
--- libjack/ringbuffer.c (revision 3862)
+++ libjack/ringbuffer.c (working copy)
@@ -29,6 +29,15 @@
#endif /* USE_MLOCK */
#include <jack/ringbuffer.h>
+#if defined(__APPLE__)
+#include <libkern/OSAtomic.h>
+#define MEMORY_BARRIER() OSMemoryBarrier()
+#elif (__GNUC__ > 4) || (__GNUC__ == 4 && __GNUC_MINOR__ >= 1)
+#define MEMORY_BARRIER() __sync_synchronize()
+#else
+#warning SMP Danger: memory barriers are not supported on this system
+#endif
+
/* Create a new ringbuffer to hold at least `sz' bytes of data. The
actual buffer size is rounded up to the next power of two. */
@@ -146,6 +155,7 @@
size_t cnt2;
size_t to_read;
size_t n1, n2;
+ size_t new_ptr;
if ((free_cnt = jack_ringbuffer_read_space (rb)) == 0) {
return 0;
@@ -164,13 +174,17 @@
}
memcpy (dest, &(rb->buf[rb->read_ptr]), n1);
- rb->read_ptr = (rb->read_ptr + n1) & rb->size_mask;
+ new_ptr = (rb->read_ptr + n1) & rb->size_mask;
if (n2) {
memcpy (dest + n1, &(rb->buf[rb->read_ptr]), n2);
- rb->read_ptr = (rb->read_ptr + n2) & rb->size_mask;
+ new_ptr = (rb->read_ptr + n2) & rb->size_mask;
}
+ /* Ensure that the read pointer gets updated after copying the data */
+ MEMORY_BARRIER();
+ rb->read_ptr = new_ptr;
+
return to_read;
}
@@ -226,6 +240,7 @@
size_t cnt2;
size_t to_write;
size_t n1, n2;
+ size_t new_ptr;
if ((free_cnt = jack_ringbuffer_write_space (rb)) == 0) {
return 0;
@@ -244,13 +259,17 @@
}
memcpy (&(rb->buf[rb->write_ptr]), src, n1);
- rb->write_ptr = (rb->write_ptr + n1) & rb->size_mask;
+ new_ptr = (rb->write_ptr + n1) & rb->size_mask;
if (n2) {
memcpy (&(rb->buf[rb->write_ptr]), src + n1, n2);
- rb->write_ptr = (rb->write_ptr + n2) & rb->size_mask;
+ new_ptr = (rb->write_ptr + n2) & rb->size_mask;
}
+ /* Ensure that the write pointer gets updated after copying the data */
+ MEMORY_BARRIER();
+ rb->write_ptr = new_ptr;
+
return to_write;
}
@@ -260,6 +279,8 @@
jack_ringbuffer_read_advance (jack_ringbuffer_t * rb, size_t cnt)
{
size_t tmp = (rb->read_ptr + cnt) & rb->size_mask;
+ /* Ensure that the read pointer gets updated after external data change */
+ MEMORY_BARRIER();
rb->read_ptr = tmp;
}
@@ -269,6 +290,8 @@
jack_ringbuffer_write_advance (jack_ringbuffer_t * rb, size_t cnt)
{
size_t tmp = (rb->write_ptr + cnt) & rb->size_mask;
+ /* Ensure that the write pointer gets updated after external data change */
+ MEMORY_BARRIER();
rb->write_ptr = tmp;
}
The point is,
I wrote ringbuffer stress tests, and someone reported on this list
that they succeeded on a weakly-ordered (PowerPC SMP) system, even without
memory barriers. Anyway...
unfortunately stress tests won't necessarily show the race condition See the
"ring buffer memory barriers" discussion on jack-devel back in
October of last year for more information; in particular, this article
by Paul E. McKenney is very helpful:
http://www.linuxjournal.com/article/8211
memory-barriers.txt of the linux kernel
documentation is interesting as
well ...
7:49 a.m.
New subject: Atomic Operations
On 12/17/2009 12:40 PM, Olivier Guilyardi wrote:
On 12/16/2009 06:57 PM, Tim Blechmann wrote:
My tests helped to find and fix a race bug in jack ringbuffer. I guess this
should have worked for memory barriers too. Unless they need to run for a
century before an error occur.. ;)
the kfifo doesn't look too different, either ...
Okay, I got a patch for Jack1's ringbuffer, it's not finished, but it's a
beginning. I think it misses some "read" memory barriers, as described in
kernel's memory-barriers.txt (in SMP BARRIER PAIRING) : "A write barrier should
always be paired with a data dependency barrier or read barrier[...]".
It's attached. What do you think?
Oups, sorry, ignore my previous patch. It contained an obvious bug in
jack_ringbuffer_read() and jack_ringbuffer_write(). See the new one, attached.
--
Olivier
Index: libjack/ringbuffer.c
===================================================================
--- libjack/ringbuffer.c (revision 3862)
+++ libjack/ringbuffer.c (working copy)
@@ -29,6 +29,15 @@
#endif /* USE_MLOCK */
#include <jack/ringbuffer.h>
+#if defined(__APPLE__)
+#include <libkern/OSAtomic.h>
+#define MEMORY_BARRIER() OSMemoryBarrier()
+#elif (__GNUC__ > 4) || (__GNUC__ == 4 && __GNUC_MINOR__ >= 1)
+#define MEMORY_BARRIER() __sync_synchronize()
+#else
+#warning SMP Danger: memory barriers are not supported on this system
+#endif
+
/* Create a new ringbuffer to hold at least `sz' bytes of data. The
actual buffer size is rounded up to the next power of two. */
@@ -146,6 +155,7 @@
size_t cnt2;
size_t to_read;
size_t n1, n2;
+ size_t new_ptr;
if ((free_cnt = jack_ringbuffer_read_space (rb)) == 0) {
return 0;
@@ -164,13 +174,17 @@
}
memcpy (dest, &(rb->buf[rb->read_ptr]), n1);
- rb->read_ptr = (rb->read_ptr + n1) & rb->size_mask;
+ new_ptr = (rb->read_ptr + n1) & rb->size_mask;
if (n2) {
- memcpy (dest + n1, &(rb->buf[rb->read_ptr]), n2);
- rb->read_ptr = (rb->read_ptr + n2) & rb->size_mask;
+ memcpy (dest + n1, &(rb->buf[new_ptr]), n2);
+ new_ptr = (new_ptr + n2) & rb->size_mask;
}
+ /* Ensure that the read pointer gets updated after copying the data */
+ MEMORY_BARRIER();
+ rb->read_ptr = new_ptr;
+
return to_read;
}
@@ -226,6 +240,7 @@
size_t cnt2;
size_t to_write;
size_t n1, n2;
+ size_t new_ptr;
if ((free_cnt = jack_ringbuffer_write_space (rb)) == 0) {
return 0;
@@ -244,13 +259,17 @@
}
memcpy (&(rb->buf[rb->write_ptr]), src, n1);
- rb->write_ptr = (rb->write_ptr + n1) & rb->size_mask;
+ new_ptr = (rb->write_ptr + n1) & rb->size_mask;
if (n2) {
- memcpy (&(rb->buf[rb->write_ptr]), src + n1, n2);
- rb->write_ptr = (rb->write_ptr + n2) & rb->size_mask;
+ memcpy (&(rb->buf[new_ptr]), src + n1, n2);
+ new_ptr = (new_ptr + n2) & rb->size_mask;
}
+ /* Ensure that the write pointer gets updated after copying the data */
+ MEMORY_BARRIER();
+ rb->write_ptr = new_ptr;
+
return to_write;
}
@@ -260,6 +279,8 @@
jack_ringbuffer_read_advance (jack_ringbuffer_t * rb, size_t cnt)
{
size_t tmp = (rb->read_ptr + cnt) & rb->size_mask;
+ /* Ensure that the read pointer gets updated after external data change */
+ MEMORY_BARRIER();
rb->read_ptr = tmp;
}
@@ -269,6 +290,8 @@
jack_ringbuffer_write_advance (jack_ringbuffer_t * rb, size_t cnt)
{
size_t tmp = (rb->write_ptr + cnt) & rb->size_mask;
+ /* Ensure that the write pointer gets updated after external data change */
+ MEMORY_BARRIER();
rb->write_ptr = tmp;
}
The point
is, I wrote ringbuffer stress tests, and someone reported on this list
that they succeeded on a weakly-ordered (PowerPC SMP) system, even without
memory barriers. Anyway...
unfortunately stress tests won't necessarily show
the race condition > See the "ring buffer memory barriers"
discussion on jack-devel back in
> October of last year for more information; in particular, this article
> by Paul E. McKenney is very helpful:
>
> http://www.linuxjournal.com/article/8211
memory-barriers.txt of the linux kernel documentation is interesting as
well ...
The portaudio ringbuffer is also a good source of inspiration I think:
http://portaudio.com/trac/browser/portaudio/trunk/src/common/pa_ringbuffer.c
In short, they use memory barriers at only three places, especially:
- "to ensure that previous writes are seen before we update the write index"
- "to ensure that previous writes are always seen before updating the (read)
index."
8:03 a.m.
New subject: Atomic Operations
+#if defined(__APPLE__)
+#include <libkern/OSAtomic.h>
+#define MEMORY_BARRIER() OSMemoryBarrier()
+#elif (__GNUC__ > 4) || (__GNUC__ == 4 && __GNUC_MINOR__ >= 1)
+#define MEMORY_BARRIER() __sync_synchronize()
+#else
+#warning SMP Danger: memory barriers are not supported on this system
+#endif
there was a buggy gcc version, that didn't implement
__sync_synchronize() correctly on x86, causing errors on nehalem
machines (which don't have a shared cache).
if sse is enabled, _mm_mfence() can be used to work around this compiler
bug ...
tim
--
tim(a)klingt.org
http://tim.klingt.org
/"\ ASCII Ribbon Campaign
\ / no HTML in email & vCards
X no proprietary attachments
/ \ use open standards
9:56 a.m.
New subject: Atomic Operations
On 12/17/2009 01:03 PM, Tim Blechmann wrote:
There also are bugs on ARM, x86-64, etc..
+#if
defined(__APPLE__)
+#include <libkern/OSAtomic.h>
+#define MEMORY_BARRIER() OSMemoryBarrier()
+#elif (__GNUC__ > 4) || (__GNUC__ == 4 && __GNUC_MINOR__ >= 1)
+#define MEMORY_BARRIER() __sync_synchronize()
+#else
+#warning SMP Danger: memory barriers are not supported on this system
+#endif
there was a buggy gcc version, that didn't implement
__sync_synchronize() correctly on x86, causing errors on nehalem
machines (which don't have a shared cache). if sse is enabled, _mm_mfence() can be used to work
around this compiler
bug ...
IMO, it's the compiler job to figure how to implement a memory barrier.
Otherwise, we're going to end up with a 200 lines macro def, with a workaround
for this, a workaround for that,... GCC devs are more competent for this I
think, and will keep it up-to-date.
--
Olivier
11 a.m.
New subject: Atomic Operations
[Olivier Guilyardi]
On 12/17/2009 01:03 PM, Tim Blechmann wrote:
>> +#if defined(__APPLE__)
>> +#include <libkern/OSAtomic.h>
>> +#define MEMORY_BARRIER() OSMemoryBarrier()
>> +#elif (__GNUC__ > 4) || (__GNUC__ == 4 && __GNUC_MINOR__ >= 1)
>> +#define MEMORY_BARRIER() __sync_synchronize()
>> +#else
>> +#warning SMP Danger: memory barriers are not supported on this system
>> +#endif
I may be wrong but if neither __APPLE__ nor __GNUC__ >= 4.1 are true
shouldn't MEMORY_BARRIER() at least be an empty define to keep cpp
happy?
After all, your #warning statement seems to indicate you don't want
compilation to fail.
Cheers, Tim
1:04 p.m.
New subject: Atomic Operations
On 12/17/2009 04:00 PM, Tim Goetze wrote:
[Olivier Guilyardi]
Yes indeed. Fixed.
--
Olivier
Index: libjack/ringbuffer.c
===================================================================
--- libjack/ringbuffer.c (revision 3862)
+++ libjack/ringbuffer.c (working copy)
@@ -29,6 +29,16 @@
#endif /* USE_MLOCK */
#include <jack/ringbuffer.h>
+#if defined(__APPLE__)
+#include <libkern/OSAtomic.h>
+#define MEMORY_BARRIER() OSMemoryBarrier()
+#elif (__GNUC__ > 4) || (__GNUC__ == 4 && __GNUC_MINOR__ >= 1)
+#define MEMORY_BARRIER() __sync_synchronize()
+#else
+#warning SMP Danger: memory barriers are not supported on this system
+#define MEMORY_BARRIER()
+#endif
+
/* Create a new ringbuffer to hold at least `sz' bytes of data. The
actual buffer size is rounded up to the next power of two. */
@@ -146,6 +156,7 @@
size_t cnt2;
size_t to_read;
size_t n1, n2;
+ size_t new_ptr;
if ((free_cnt = jack_ringbuffer_read_space (rb)) == 0) {
return 0;
@@ -164,13 +175,17 @@
}
memcpy (dest, &(rb->buf[rb->read_ptr]), n1);
- rb->read_ptr = (rb->read_ptr + n1) & rb->size_mask;
+ new_ptr = (rb->read_ptr + n1) & rb->size_mask;
if (n2) {
- memcpy (dest + n1, &(rb->buf[rb->read_ptr]), n2);
- rb->read_ptr = (rb->read_ptr + n2) & rb->size_mask;
+ memcpy (dest + n1, &(rb->buf[new_ptr]), n2);
+ new_ptr = (new_ptr + n2) & rb->size_mask;
}
+ /* Ensure that the read pointer gets updated after copying the data */
+ MEMORY_BARRIER();
+ rb->read_ptr = new_ptr;
+
return to_read;
}
@@ -226,6 +241,7 @@
size_t cnt2;
size_t to_write;
size_t n1, n2;
+ size_t new_ptr;
if ((free_cnt = jack_ringbuffer_write_space (rb)) == 0) {
return 0;
@@ -244,13 +260,17 @@
}
memcpy (&(rb->buf[rb->write_ptr]), src, n1);
- rb->write_ptr = (rb->write_ptr + n1) & rb->size_mask;
+ new_ptr = (rb->write_ptr + n1) & rb->size_mask;
if (n2) {
- memcpy (&(rb->buf[rb->write_ptr]), src + n1, n2);
- rb->write_ptr = (rb->write_ptr + n2) & rb->size_mask;
+ memcpy (&(rb->buf[new_ptr]), src + n1, n2);
+ new_ptr = (new_ptr + n2) & rb->size_mask;
}
+ /* Ensure that the write pointer gets updated after copying the data */
+ MEMORY_BARRIER();
+ rb->write_ptr = new_ptr;
+
return to_write;
}
@@ -260,6 +280,8 @@
jack_ringbuffer_read_advance (jack_ringbuffer_t * rb, size_t cnt)
{
size_t tmp = (rb->read_ptr + cnt) & rb->size_mask;
+ /* Ensure that the read pointer gets updated after external data change */
+ MEMORY_BARRIER();
rb->read_ptr = tmp;
}
@@ -269,6 +291,8 @@
jack_ringbuffer_write_advance (jack_ringbuffer_t * rb, size_t cnt)
{
size_t tmp = (rb->write_ptr + cnt) & rb->size_mask;
+ /* Ensure that the write pointer gets updated after external data change */
+ MEMORY_BARRIER();
rb->write_ptr = tmp;
}
On 12/17/2009 01:03 PM, Tim Blechmann wrote:
>> +#if defined(__APPLE__)
>> +#include <libkern/OSAtomic.h>
>> +#define MEMORY_BARRIER() OSMemoryBarrier()
>> +#elif (__GNUC__ > 4) || (__GNUC__ == 4 && __GNUC_MINOR__ >= 1)
>> +#define MEMORY_BARRIER() __sync_synchronize()
>> +#else
>> +#warning SMP Danger: memory barriers are not supported on this system
>> +#endif
I may be wrong but if neither __APPLE__ nor __GNUC__ >= 4.1 are true
shouldn't MEMORY_BARRIER() at least be an empty define to keep cpp
happy?
After all, your #warning statement seems to indicate you don't want
compilation to fail.
15 Dec
15 Dec
2:51 p.m.
New subject: Atomic Operations
On Tue, Dec 15, 2009 at 1:33 PM, Gabriel M. Beddingfield
<gabriel(a)teuton.org> wrote:
Hi Tim,
On Tue, 15 Dec 2009, Tim Blechmann wrote:
Yes, sorry I should have stated the single/single requirement.
I'm not really sure about memory barriers and where and when they're
needed. In any case I've been using this code successfully for
message passing between threads. I'm sure there is better code out
there (like in boost), but I just like that it's self-contained.
Steve
you should add memory barriers, when reading or writing to the reader or
Actually, his implementation is similar to ringbuffer.c in
libjack... and assumes that reading and writing can happen
atomically (as was pointed out by someone else) -- which can
be managed with single reader / single writer
requirement.[a]
4:05 p.m.
New subject: Atomic Operations
Hi,
On Tuesday 15 December 2009 19:33:18 Gabriel M. Beddingfield wrote:
On Tue, 15 Dec 2009, Tim Blechmann wrote:
Why should a single-reader-single-writer ring-buffer need atomic operations?
The reader increments the read-pointer (which doesn't have to be a pointer)
last when its finished, the writer increments the write-pointer last when it
has written. All other access is read-only. No problems. (At least in my app.)
increment = read the old value, add one, modulo (or bit-mask) the size, write
the new value
Arnold
you should add
memory barriers, when reading or writing to the reader or
Actually, his
implementation is similar to ringbuffer.c in
libjack... and assumes that reading and writing can happen
atomically (as was pointed out by someone else) -- which can
be managed with single reader / single writer
requirement.[a]
Unless I've misunderstood the code, ringbuffer.c is /not/
using special atomic operations.
16 Dec
16 Dec
6:05 a.m.
New subject: Atomic Operations
Actually, his
implementation is similar to ringbuffer.c in
libjack... and assumes that reading and writing can happen
atomically (as was pointed out by someone else) -- which can
be managed with single reader / single writer
requirement.[a]
Unless I've misunderstood the code, ringbuffer.c is /not/
using special atomic operations.
Why should a single-reader-single-writer ring-buffer need atomic operations?
The reader increments the read-pointer (which doesn't have to be a pointer)
last when its finished, the writer increments the write-pointer last when it
has written.
likewise, how do you ensure, that the write pointer is incremented
_after_ the data has been written to the ringbuffer?
also, when reading the read/write pointers, you need to ensure, that
they are loaded, before you touch the ringbuffer.
All other access is read-only. No problems. (At least
in my app.)
your code may work on x86, not necessarily on ppc, ia64 ... and then
there is alpha ...
we are not in a world, where assembler instructions are executed one
after the other, but we have out-of-order cpus with speculation and
multi-processor systems with non-shared caches ...
hth, tim
--
tim(a)klingt.org
http://tim.klingt.org
Which is more musical, a truck passing by a factory or a truck passing
by a music school?
John Cage
15 Dec
15 Dec
10:36 a.m.
New subject: Atomic Operations
On 12/15/2009 02:58 PM, Paul Davis wrote:
On Tue, Dec 15, 2009 at 8:54 AM, Paul Davis
<paul-dDzkXPnfpdxaomM2pvQuqZqQE7yCjDx5(a)public.gmane.org> wrote:
fyi, i am working on boost-style c++ implementations of some lockfree
data structures ... the library is on the boost review queue, however
counting the number of libs in the queue and review processes per year,
it may take some time, until it is an official part of boost ..
http://tim.klingt.org/git?p=boost_lockfree.git
http://tim.klingt.org/boost_lockfree/
suggestions/thoughts/criticism is welcome ...
tim
--
tim(a)klingt.org
http://tim.klingt.org
I had nothing to offer anybody except my own confusion
Jack Kerouac
these concepts have been around in this community
(and others) for
years. i suspect that it is more than a decade since the folks at
GRAME published their paper on lock free data structures (used in
MidiShare), and its probably a decade or more since LAD first
discussed lock free (single-read/single-writer) ringbuffers. there's
nothing wrong with having new eyes and new ideas but i couldn't see
anything from a casual glance in that paper that hasn't been
documented and used by people on this list for a long time.
i should perhaps note that there tends to be less use of generic lock
free data structures because of the absence of nice libraries. maybe
effo can be a useful addition there. its not as if its the first one,
however.
10:16 a.m.
New subject: Atomic Operations
Paul Davis wrote:
On Tue, Dec 15, 2009 at 8:43 AM, lieven moors
<lievenmoors(a)gmail.com> wrote:
I just wanted to say that these concepts are still above my
head because I am not an experienced programmer...
I know that ringbuffers are lock-free by design for two threads,
but I find it hard to understand what it means for a ringbuffer
or a queue to use atomic operations.
Here are the details...
http://effocore.googlecode.com/files/EffoDesign_LockFree.pdf
these concepts have been around in this community (and others) for
years. i suspect that it is more than a decade since the folks at
GRAME published their paper on lock free data structures (used in
MidiShare), and its probably a decade or more since LAD first
discussed lock free (single-read/single-writer) ringbuffers. there's
nothing wrong with having new eyes and new ideas but i couldn't see
anything from a casual glance in that paper that hasn't been
documented and used by people on this list for a long time.
--p
5405
days inactive
5407
days old
linux-audio-dev@lists.linuxaudio.org
28 comments
9 participants
participants (9)
-
Arnold Krille -
Gabriel M. Beddingfield -
lieven moors -
Olivier Guilyardi -
Paul Davis -
Sean Bolton -
Stephen Sinclair -
Tim Blechmann -
Tim Goetze