19 Oct
2008
19 Oct
'08
1:22 a.m.
On Sat, Oct 18, 2008 at 5:30 PM, Fons Adriaensen <fons(a)kokkinizita.net> wrote:
On Sat, Oct 18, 2008 at 10:56:31PM +0200, Paul Davis
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.
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.
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.
19 Oct
19 Oct
1:29 a.m.
New subject: [LAU] Simple, easy multithreaded circular buffer library for Linux?
On Sat, Oct 18, 2008 at 10:22 PM, Paul Coccoli <pcoccoli(a)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
1:46 a.m.
New subject: [LAU] Simple, easy multithreaded circular buffer library for Linux?
On Sat, Oct 18, 2008 at 11:29 PM, Jack O'Quin <jack.oquin(a)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.
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.
2:24 a.m.
New subject: [LAU] Simple, easy multithreaded circular buffer library for Linux?
On Sat, Oct 18, 2008 at 10:45 PM, Paul Coccoli <pcoccoli(a)gmail.com> wrote:
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
On Sat, Oct 18, 2008 at 11:29 PM, Jack O'Quin
<jack.oquin(a)gmail.com> wrote:
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.
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. 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. 
5:56 a.m.
New subject: [LAU] Simple, easy multithreaded circular buffer library for Linux?
On Sat, 2008-10-18 at 23:24 -0500, Jack O'Quin wrote:
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.
this is indeed the case. for read space, if the write ptr is "ahead" of
the read ptr, we return write_ptr - read_ptr, which will return a value
that is too large if "write_ptr" gets snapshotted after the increment
and before the mask.
the same is true for writing. if the read ptr is ahead of the write ptr,
we return the difference between them minus one (the extra -1 stops the
write ptr catching up with the read ptr, a condition that indicates that
the buffer is empty). this value will also be too large if the read_ptr
is used in its "intermediate" state.
i am deeply embarrassed but also puzzled. i remember worrying about
precisely this issue on and over across a period of several years, and
yet satisfying myself that there actually wasn't a problem. i think that
my mistake was as follows: if you look at the read space case, but focus
on whether the *read* ptr is too large at that time, then the safety of
the ringbuffer is still guaranteed. ditto, in the write space case, the
write ptr being too large doesn't violate the safety guarantee. but this
is backwards - the thread that computes write space is the writing
thread, which is the only one that modifies write_ptr. ergo, it never
sees write_ptr as volatile. ditto, the reading thread never sees
read_ptr as volatile. the problems arise because of the *other* pointer,
where the temporary intermediate state *does* cause the computations to
be in error.
i don't know whether to shoot myself or eat another couple of the
oft-promised hats.
so the next question is how best to prevent it. as far as i can see we
have a couple of proposals:
1) fons' design, which never actually wraps readptr or writeptr, but
masks the address used to access the data buffer
2) removing the intermediate state's visibility
i admit to preferring (2) even though i know that with a 64 bit index,
not wrapping the ptrs is not really a problem.
however, it is not totally clear to me how to prevent an optimizing
compiler from doing the wrong thing here. unlike the claims made by
someone involved with portaudio, i believe that it is correct to declare
the read_ptr and write_ptr volatile, so that the compiler knows that it
cannot try to be clever about it accesses of the "other" ptr (i.e.
read_ptr for the writing thread, and vice versa). maybe the comment on
the use of volatile was based on some idea that i thought it made the
variables thread safe, which is and never was the case.
i suspect that the safest code looks like:
size_t tmp = (ptr + incr) & mask;
barrier();
ptr = tmp;
but i am not sure whether barrier needs to be read, write or both.
i think that the simpler code:
ptr = (ptr + incr) & mask;
is subject to potential compiler and/or processor "optimization" that
might reduce it back to the problem case of two ops without an
intermediate load/store location. the volatile declaration ought to
prevent the compiler from doing this, and i don't see why a processor
would do this, ever, but clearly i've already been deeply wrong about
this. does anybody know for certain?
--p
6:03 a.m.
New subject: [LAU] Simple, easy multithreaded circular buffer library for Linux?
On Sun, 2008-10-19 at 09:55 +0200, Paul Davis wrote:
i am deeply embarrassed but also puzzled.
maybe i don't need to eat any hats except for the "paying insufficient
attention" one. the jack ringbuffer code was ported from my original C++
implementation, which specifically does not have the problem of visible
intermediate state (and, btw, does force the use of atomic loads &
stores).
--p
7:20 a.m.
New subject: [LAU] Simple, easy multithreaded circular buffer library for Linux?
On Sun, Oct 19, 2008 at 09:55:54AM +0200, Paul Davis wrote:
1) fons' design, which never actually wraps
readptr or writeptr, but
masks the address used to access the data buffer
2) removing the intermediate state's visibility
i admit to preferring (2) even though i know that with a 64 bit index,
not wrapping the ptrs is not really a problem.
Another advantage of 1 is that it has no problem with
a completely full buffer, and this doesn't even require
any special code. If access is always in 2^N blocks,
it can store one block more.
i think that the simpler code:
ptr = (ptr + incr) & mask;
is subject to potential compiler and/or processor "optimization" that
might reduce it back to the problem case of two ops without an
intermediate load/store location.
You mean _with_ and intermediate store (I hope) ?
Adding a intermediate store would not really be an
'optimisation'... I doubt if any compiler would do
it. But you can prevent it from doing so, see below.
the volatile declaration ought to prevent the
compiler from
doing this
It does. Declaring a var volatile means that the compiler MUST
assume that reading or writing it can have side effects, and
that therefore it MUST access the var exactly as specified. For
the new code this means that only the correct value will ever
be written, for the old it forced the compiler to write the
wrong one.
Ciao,
--
FA
Laboratorio di Acustica ed Elettroacustica
Parma, Italia
Lascia la spina, cogli la rosa.
11:22 a.m.
New subject: [LAU] Simple, easy multithreaded circular buffer library for Linux?
On Sun, Oct 19, 2008 at 2:55 AM, Paul Davis <paul(a)linuxaudiosystems.com> wrote:
i don't know whether to shoot myself or eat
another couple of the
oft-promised hats.
Don't beat yourself up too badly. Multiple threads accessing shared memory
is *very* tricky. Even smart people (like you) get it wrong sometimes.
so the next question is how best to prevent it. as far
as i can see we
have a couple of proposals:
1) fons' design, which never actually wraps readptr or writeptr, but
masks the address used to access the data buffer
2) removing the intermediate state's visibility
i admit to preferring (2) even though i know that with a 64 bit index,
not wrapping the ptrs is not really a problem.
I also prefer (2).
however, it is not totally clear to me how to prevent
an optimizing
compiler from doing the wrong thing here. unlike the claims made by
someone involved with portaudio, i believe that it is correct to declare
the read_ptr and write_ptr volatile, so that the compiler knows that it
cannot try to be clever about it accesses of the "other" ptr (i.e.
read_ptr for the writing thread, and vice versa). maybe the comment on
the use of volatile was based on some idea that i thought it made the
variables thread safe, which is and never was the case.
i suspect that the safest code looks like:
size_t tmp = (ptr + incr) & mask;
barrier();
ptr = tmp;
but i am not sure whether barrier needs to be read, write or both.
i think that the simpler code:
ptr = (ptr + incr) & mask;
is subject to potential compiler and/or processor "optimization" that
might reduce it back to the problem case of two ops without an
intermediate load/store location. the volatile declaration ought to
prevent the compiler from doing this, and i don't see why a processor
would do this, ever, but clearly i've already been deeply wrong about
this. does anybody know for certain?
It is best to avoid assumptions about what some future compiler may
consider an "optimization". If the register pressure is high at some
point in the program, it may decide to store some value just to free up
register space for other variables.
The "volatile" declaration should remove any need for the compiler
barrier() statement, AFAICT. Note that barrier() is a compiler
directive, and has no effect on the CPU's ability to reorder cache
operations in an SMP memory hierarchy.
Here is a fairly clear and complete description of the memory barrier
issues: http://lxr.linux.no/linux/Documentation/memory-barriers.txt
As best I can tell, both ring buffer threads require "general" memory
barriers, because they both read and write (different) shared data. In
Linux kernel terms, they'd need to use smp_mb(), since the problems
they address are multiprocessor-only. But, since JACK is not compiled
differently for UP and SMP, the full mb() seems more appropriate.
That stuff makes my head hurt.
--
joq
20 Oct
20 Oct
11:13 a.m.
New subject: [LAU] Simple, easy multithreaded circular buffer library for Linux?
Jack O'Quin wrote:
Maybe that is because your approach is too theoretical. I've read many theories
about whether memory barriers are needed or not in lock-free ring buffers, and I
think it might lead nowhere without experimenting, that is: write test cases.
Until now, I just couldn't write a test that fail because of the lack of memory
barrier on x86. However, I think I found another bug in Jack ringbuffer, by
writing another test.
It's a bit of a weird test, I call it "bit circle": I start 16
"node" threads.
Each node :
- communicate with its adjacent node through 2 ring buffers
- is responsible for shifting an integer by one bit
- send the shifted result to the next node through a ring buffer
- checks that the value read from previous node is correct.
On my Debian Quad Core and Mac OS X Core Duo boxes, this test fails with Jack's
ringbuffer even with my patch applied. But it succeeds with Portaudio (both with
and without memory barriers), and also with Fons' implementation.
I wish someone could eventually run my test suite on a PowerPC, especially SMP.
The usage is unchanged:
svn co http://svn.samalyse.com/misc/rbtest
cd rbtest
make test
The run time is now shorter, about 2 minutes. Below is the output. You can see
that jack (test-bit-circle-jack) fails the bit circle test, even when patched
(test-bit-circle-jack-fix1). "|" is printed when a node thread starts, and
"-"
when a node has read 1000 values, to ensure data is really flowing.
The test-int-array-* tests are the same as my original test. All *-lfq tests use
Fons's Lfq ringbuffer (modified to use char instead of uint32_t) as backend.
./run-tests.sh bit-circle 512 jack jack-fix1 portaudio portaudio-nobarrier lfq
test-bit-circle-jack - starting (5s max) - buffer size: 512
|| FAILURE: 2 != 514
test-bit-circle-jack-fix1 - starting (5s max) - buffer size: 512
|| FAILURE: 2 != 514
test-bit-circle-portaudio - starting (5s max) - buffer size: 512
||-|-|-||-|-|-|-|-||--|||--|---- SUCCESS
test-bit-circle-portaudio-nobarrier - starting (5s max) - buffer size: 512
|||--|-|||---||-||-|-|--||--|--- SUCCESS
test-bit-circle-lfq - starting (5s max) - buffer size: 512
|||--|||-|||-|||--|||-------|--- SUCCESS
./run-tests.sh int-array 16 jack jack-fix1 portaudio portaudio-nobarrier lfq
test-int-array-jack - starting (20s max) - array/buffer size: 8/16
[reader started] [writer started] [flowing] 52572 != 52568 at offset 0
FAILURE in chunk 91822
test-int-array-jack-fix1 - starting (20s max) - array/buffer size: 8/16
[reader started] [writer started] [flowing] SUCCESS
test-int-array-portaudio - starting (20s max) - array/buffer size: 8/16
[reader started] [writer started] [flowing] SUCCESS
test-int-array-portaudio-nobarrier - starting (20s max) - array/buffer size: 8/16
[reader started] [writer started] [flowing] SUCCESS
test-int-array-lfq - starting (20s max) - array/buffer size: 8/16
[writer started] [reader started] [flowing] SUCCESS
--
Olivier Guilyardi / Samalyse
On Sun, Oct 19, 2008 at 2:55 AM, Paul Davis
<paul(a)linuxaudiosystems.com> wrote:
I agree with Jack. I remember a friend of mine once qualifying multi-threading
of "kernel quantization". This is complex but also challenging :)
Although your understanding of these matters is far beyond mine, I think that I
have a good professional experience of coding methodology. And to me the problem
here is indeed methodological: there is a lack of unit tests in JACK.
i don't know whether to shoot myself or eat
another couple of the
oft-promised hats.
Don't beat yourself up too badly. Multiple threads accessing shared memory
is *very* tricky. Even smart people (like you) get it wrong sometimes. so the next
question is how best to prevent it. as far as i can see we
have a couple of proposals:
1) fons' design, which never actually wraps readptr or writeptr, but
masks the address used to access the data buffer
2) removing the intermediate state's visibility
i admit to preferring (2) even though i know that with a 64 bit index,
not wrapping the ptrs is not really a problem.
I also prefer (2).
however, it is not totally clear to me how to
prevent an optimizing
compiler from doing the wrong thing here. unlike the claims made by
someone involved with portaudio, i believe that it is correct to declare
the read_ptr and write_ptr volatile, so that the compiler knows that it
cannot try to be clever about it accesses of the "other" ptr (i.e.
read_ptr for the writing thread, and vice versa). maybe the comment on
the use of volatile was based on some idea that i thought it made the
variables thread safe, which is and never was the case.
i suspect that the safest code looks like:
size_t tmp = (ptr + incr) & mask;
barrier();
ptr = tmp;
but i am not sure whether barrier needs to be read, write or both.
i think that the simpler code:
ptr = (ptr + incr) & mask;
is subject to potential compiler and/or processor "optimization" that
might reduce it back to the problem case of two ops without an
intermediate load/store location. the volatile declaration ought to
prevent the compiler from doing this, and i don't see why a processor
would do this, ever, but clearly i've already been deeply wrong about
this. does anybody know for certain?
It is best to avoid assumptions about what some future compiler may
consider an "optimization". If the register pressure is high at some
point in the program, it may decide to store some value just to free up
register space for other variables.
The "volatile" declaration should remove any need for the compiler
barrier() statement, AFAICT. Note that barrier() is a compiler
directive, and has no effect on the CPU's ability to reorder cache
operations in an SMP memory hierarchy.
Here is a fairly clear and complete description of the memory barrier
issues: http://lxr.linux.no/linux/Documentation/memory-barriers.txt
As best I can tell, both ring buffer threads require "general" memory
barriers, because they both read and write (different) shared data. In
Linux kernel terms, they'd need to use smp_mb(), since the problems
they address are multiprocessor-only. But, since JACK is not compiled
differently for UP and SMP, the full mb() seems more appropriate.
That stuff makes my head hurt. 
12:57 p.m.
New subject: olivier's jack ringbuffer tests...
hi everyone!
for the benefit of those JACK devs who don't follow linux-audio-* (if
any), and for posterity in the JACK mailing list archives:
there has been a very insightful discussion on LAU/LAD about ringbuffer
peculiarities and a possible bug. olivier guilyardi has written test
cases that pinpoint those problems.
he has made them available at http://svn.samalyse.com/misc/rbtest.
can i suggest that the rest of this discussion take place on or at least
be cc:ed to jack-devel?
best,
jörn (who has no idea at all about concurrent programming, but knows a
bit about community engineering and data mining :-D)
Olivier Guilyardi wrote:
Jack O'Quin wrote:
Maybe that is because your approach is too theoretical. I've read many theories
about whether memory barriers are needed or not in lock-free ring buffers, and I
think it might lead nowhere without experimenting, that is: write test cases.
Until now, I just couldn't write a test that fail because of the lack of memory
barrier on x86. However, I think I found another bug in Jack ringbuffer, by
writing another test.
It's a bit of a weird test, I call it "bit circle": I start 16
"node" threads.
Each node :
- communicate with its adjacent node through 2 ring buffers
- is responsible for shifting an integer by one bit
- send the shifted result to the next node through a ring buffer
- checks that the value read from previous node is correct.
On my Debian Quad Core and Mac OS X Core Duo boxes, this test fails with Jack's
ringbuffer even with my patch applied. But it succeeds with Portaudio (both with
and without memory barriers), and also with Fons' implementation.
I wish someone could eventually run my test suite on a PowerPC, especially SMP.
The usage is unchanged:
svn co http://svn.samalyse.com/misc/rbtest
cd rbtest
make test
The run time is now shorter, about 2 minutes. Below is the output. You can see
that jack (test-bit-circle-jack) fails the bit circle test, even when patched
(test-bit-circle-jack-fix1). "|" is printed when a node thread starts, and
"-"
when a node has read 1000 values, to ensure data is really flowing.
The test-int-array-* tests are the same as my original test. All *-lfq tests use
Fons's Lfq ringbuffer (modified to use char instead of uint32_t) as backend.
./run-tests.sh bit-circle 512 jack jack-fix1 portaudio portaudio-nobarrier lfq
test-bit-circle-jack - starting (5s max) - buffer size: 512
|| FAILURE: 2 != 514
test-bit-circle-jack-fix1 - starting (5s max) - buffer size: 512
|| FAILURE: 2 != 514
test-bit-circle-portaudio - starting (5s max) - buffer size: 512
||-|-|-||-|-|-|-|-||--|||--|---- SUCCESS
test-bit-circle-portaudio-nobarrier - starting (5s max) - buffer size: 512
|||--|-|||---||-||-|-|--||--|--- SUCCESS
test-bit-circle-lfq - starting (5s max) - buffer size: 512
|||--|||-|||-|||--|||-------|--- SUCCESS
./run-tests.sh int-array 16 jack jack-fix1 portaudio portaudio-nobarrier lfq
test-int-array-jack - starting (20s max) - array/buffer size: 8/16
[reader started] [writer started] [flowing] 52572 != 52568 at offset 0
FAILURE in chunk 91822
test-int-array-jack-fix1 - starting (20s max) - array/buffer size: 8/16
[reader started] [writer started] [flowing] SUCCESS
test-int-array-portaudio - starting (20s max) - array/buffer size: 8/16
[reader started] [writer started] [flowing] SUCCESS
test-int-array-portaudio-nobarrier - starting (20s max) - array/buffer size: 8/16
[reader started] [writer started] [flowing] SUCCESS
test-int-array-lfq - starting (20s max) - array/buffer size: 8/16
[writer started] [reader started] [flowing] SUCCESS
--
jörn nettingsmeier
home://germany/45128 essen/lortzingstr. 11/
http://spunk.dnsalias.org
phone://+49/201/491621
Kurt is up in Heaven now.
On Sun, Oct 19, 2008 at 2:55 AM, Paul Davis
<paul(a)linuxaudiosystems.com> wrote:
I agree with Jack. I remember a friend of mine once qualifying multi-threading
of "kernel quantization". This is complex but also challenging :)
Although your understanding of these matters is far beyond mine, I think that I
have a good professional experience of coding methodology. And to me the problem
here is indeed methodological: there is a lack of unit tests in JACK.
i don't know whether to shoot myself or eat
another couple of the
oft-promised hats.
Don't beat yourself up too badly. Multiple threads
accessing shared memory
is *very* tricky. Even smart people (like you) get it wrong sometimes. so the
next question is how best to prevent it. as far as i can see we
have a couple of proposals:
1) fons' design, which never actually wraps readptr or writeptr, but
masks the address used to access the data buffer
2) removing the intermediate state's visibility
i admit to preferring (2) even though i know that with a 64 bit index,
not wrapping the ptrs is not really a problem.
I also prefer (2).
however, it is not totally clear to me how to
prevent an optimizing
compiler from doing the wrong thing here. unlike the claims made by
someone involved with portaudio, i believe that it is correct to declare
the read_ptr and write_ptr volatile, so that the compiler knows that it
cannot try to be clever about it accesses of the "other" ptr (i.e.
read_ptr for the writing thread, and vice versa). maybe the comment on
the use of volatile was based on some idea that i thought it made the
variables thread safe, which is and never was the case.
i suspect that the safest code looks like:
size_t tmp = (ptr + incr) & mask;
barrier();
ptr = tmp;
but i am not sure whether barrier needs to be read, write or both.
i think that the simpler code:
ptr = (ptr + incr) & mask;
is subject to potential compiler and/or processor "optimization" that
might reduce it back to the problem case of two ops without an
intermediate load/store location. the volatile declaration ought to
prevent the compiler from doing this, and i don't see why a processor
would do this, ever, but clearly i've already been deeply wrong about
this. does anybody know for certain?
It is best to avoid assumptions about what
some future compiler may
consider an "optimization". If the register pressure is high at some
point in the program, it may decide to store some value just to free up
register space for other variables.
The "volatile" declaration should remove any need for the compiler
barrier() statement, AFAICT. Note that barrier() is a compiler
directive, and has no effect on the CPU's ability to reorder cache
operations in an SMP memory hierarchy.
Here is a fairly clear and complete description of the memory barrier
issues: http://lxr.linux.no/linux/Documentation/memory-barriers.txt
As best I can tell, both ring buffer threads require "general" memory
barriers, because they both read and write (different) shared data. In
Linux kernel terms, they'd need to use smp_mb(), since the problems
they address are multiprocessor-only. But, since JACK is not compiled
differently for UP and SMP, the full mb() seems more appropriate.
That stuff makes my head hurt. 
6:42 p.m.
New subject: [LAU] Simple, easy multithreaded circular buffer library for Linux?
Hi Olivier,
On Oct 20, 2008, at 6:13 AM, Olivier Guilyardi wrote:
Until now, I just couldn't write a test that fail
because of the
lack of memory
barrier on x86. However, I think I found another bug in Jack
ringbuffer, by
writing another test.
It's a bit of a weird test, I call it "bit circle": I start 16
"node" threads.
Each node :
- communicate with its adjacent node through 2 ring buffers
- is responsible for shifting an integer by one bit
- send the shifted result to the next node through a ring buffer
- checks that the value read from previous node is correct.
On my Debian Quad Core and Mac OS X Core Duo boxes, this test fails
with Jack's
ringbuffer even with my patch applied. But it succeeds with
Portaudio (both with
and without memory barriers), and also with Fons' implementation.
I wish someone could eventually run my test suite on a PowerPC,
especially SMP.
The usage is unchanged:
svn co http://svn.samalyse.com/misc/rbtest
cd rbtest
make test
The run time is now shorter, about 2 minutes. Below is the output.
You can see
that jack (test-bit-circle-jack) fails the bit circle test, even
when patched
(test-bit-circle-jack-fix1). "|" is printed when a node thread
starts, and "-"
when a node has read 1000 values, to ensure data is really flowing.
The test-int-array-* tests are the same as my original test. All *-
lfq tests use
Fons's Lfq ringbuffer (modified to use char instead of uint32_t) as
backend.
./run-tests.sh bit-circle 512 jack jack-fix1 portaudio portaudio-
nobarrier lfq
test-bit-circle-jack - starting (5s max) - buffer size: 512
|| FAILURE: 2 != 514
I thought it suspicious that 514 = 2 + 2 * 256, while on a PPC it
returns
FAILURE: 2 != 0. Endianness bug? No, but it's a clue...
I don't think you're seeing a *bug* in the jack ringbuffer, just a
difference in
semantics between it and the PortAudio and lfq imlementations. Both PA
and lfq mask the index after reading it, so they can completely fill
the buffer.
The jack implementation masks the stored index, which means it can't
ever completely fill the buffer, or there would be an ambiguity as to
whether
it was full or empty. The most it can store is (size - 1) bytes.
In the jack version of your code, at some point, the buffer almost
fills, and
jack_ringbuffer_write only writes a single byte to the buffer (low
order on x86,
high order on PPC). Next time around, it does this again. Then the
following
thread reads, not 0x0002 like it should, but either 0x0202 (x86) or
0x0000 (PPC).
Paul said he prefers storing the masked pointer, but I think Fons & PA's
approach is better: it allows for full use of the buffer.
-Sean
7:13 p.m.
New subject: [LAU] Simple, easy multithreaded circular buffer library for Linux?
Sean Bolton wrote:
Hi Olivier,
On Oct 20, 2008, at 6:13 AM, Olivier Guilyardi wrote:
I can confirm this, since the following will make the test 'succeed',
although it results in a very slow progress once the buffers are full.
Index: test-bit-circle.c
===================================================================
--- test-bit-circle.c (revision 314)
+++ test-bit-circle.c (working copy)
@@ -50,6 +50,9 @@
if (value)
{
+ while(jack_ringbuffer_write_space(rb[1]) < 2) {
+ usleep(1000);
+ }
jack_ringbuffer_write (rb[1], (char *) &value, sizeof (uint16_t));
value = 0;
}
Pieter
Until now, I just couldn't write a test that
fail because of the
lack of memory
barrier on x86. However, I think I found another bug in Jack
ringbuffer, by
writing another test.
It's a bit of a weird test, I call it "bit circle": I start 16
"node" threads.
Each node :
- communicate with its adjacent node through 2 ring buffers
- is responsible for shifting an integer by one bit
- send the shifted result to the next node through a ring buffer
- checks that the value read from previous node is correct.
On my Debian Quad Core and Mac OS X Core Duo boxes, this test fails
with Jack's
ringbuffer even with my patch applied. But it succeeds with
Portaudio (both with
and without memory barriers), and also with Fons' implementation.
I wish someone could eventually run my test suite on a PowerPC,
especially SMP.
The usage is unchanged:
svn co http://svn.samalyse.com/misc/rbtest
cd rbtest
make test
The run time is now shorter, about 2 minutes. Below is the output.
You can see
that jack (test-bit-circle-jack) fails the bit circle test, even
when patched
(test-bit-circle-jack-fix1). "|" is printed when a node thread
starts, and "-"
when a node has read 1000 values, to ensure data is really flowing.
The test-int-array-* tests are the same as my original test. All *-
lfq tests use
Fons's Lfq ringbuffer (modified to use char instead of uint32_t) as
backend.
./run-tests.sh bit-circle 512 jack jack-fix1 portaudio portaudio-
nobarrier lfq
test-bit-circle-jack - starting (5s max) - buffer size: 512
|| FAILURE: 2 != 514
I thought it suspicious that 514 = 2 + 2 * 256, while on a PPC it
returns
FAILURE: 2 != 0. Endianness bug? No, but it's a clue...
I don't think you're seeing a *bug* in the jack ringbuffer, just a
difference in
semantics between it and the PortAudio and lfq imlementations. Both PA
and lfq mask the index after reading it, so they can completely fill
the buffer.
The jack implementation masks the stored index, which means it can't
ever completely fill the buffer, or there would be an ambiguity as to
whether
it was full or empty. The most it can store is (size - 1) bytes.
In the jack version of your code, at some point, the buffer almost
fills, and
jack_ringbuffer_write only writes a single byte to the buffer (low
order on x86,
high order on PPC). Next time around, it does this again. Then the
following
thread reads, not 0x0002 like it should, but either 0x0202 (x86) or
0x0000 (PPC).
8 p.m.
New subject: [LAU] Simple, easy multithreaded circular buffer library for Linux?
Hi,
Pieter Palmers a écrit :
I know my code performs much more write than read operations, I did that on
purpose, while playing with it.
Now, back to reality, let's say that you have a thread that synthetizes some
sound, puts it into a ringbuffer, for an audio thread to read and play it. Let's
also say that the synth thread performs much faster than the audio thread, so
that the buffer is almost always full. I think this is quite realistic.
In these conditions, if I understand correctly the result of this test, there is
a chance for the output of the ringbuffer to differ from its input. Isn't that
some sort of bug?
--
Olivier Guilyardi / Samalyse
Sean Bolton wrote:
>
>> test-bit-circle-jack - starting (5s max) - buffer size: 512
>> || FAILURE: 2 != 514
>
> I thought it suspicious that 514 = 2 + 2 * 256, while on a PPC it
> returns
> FAILURE: 2 != 0. Endianness bug? No, but it's a clue...
Do you have a PPC? Which one? Can you please paste the whole output of "make
test"?
I don't
think you're seeing a *bug* in the jack ringbuffer, just a
difference in
semantics between it and the PortAudio and lfq imlementations. Both PA
and lfq mask the index after reading it, so they can completely fill
the buffer.
The jack implementation masks the stored index, which means it can't
ever completely fill the buffer, or there would be an ambiguity as to
whether
it was full or empty. The most it can store is (size - 1) bytes.
In the jack version of your code, at some point, the buffer almost
fills, and
jack_ringbuffer_write only writes a single byte to the buffer (low
order on x86,
high order on PPC). Next time around, it does this again. Then the
following
thread reads, not 0x0002 like it should, but either 0x0202 (x86) or
0x0000 (PPC).
I can confirm this, since the following will make the test 'succeed',
although it results in a very slow progress once the buffers are full.
Index: test-bit-circle.c
===================================================================
--- test-bit-circle.c (revision 314)
+++ test-bit-circle.c (working copy)
@@ -50,6 +50,9 @@
if (value)
{
+ while(jack_ringbuffer_write_space(rb[1]) < 2) {
+ usleep(1000);
+ }
jack_ringbuffer_write (rb[1], (char *) &value, sizeof (uint16_t));
value = 0;
}
8:18 p.m.
New subject: [LAU] Simple, easy multithreaded circular buffer library for Linux?
Olivier Guilyardi a écrit :
Hi,
Pieter Palmers a écrit :
I know my code performs much more write than read operations, I did that
on purpose, while playing with it.
Now, back to reality, let's say that you have a thread that synthetizes
some sound, puts it into a ringbuffer, for an audio thread to read and
play it. Let's also say that the synth thread performs much faster than
the audio thread, so that the buffer is almost always full. I think this
is quite realistic.
In these conditions, if I understand correctly the result of this test,
there is a chance for the output of the ringbuffer to differ from its
input. Isn't that some sort of bug?
Hmm, wait, I think I understand your point.. With the Jack implementation, in a
buffer of 16 bytes, you can really put 15 bytes. I didn't notice this. And since
I do not check if there's enough space to write my 16-bits integer, when the
buffer is almost full, it only writes one byte...
So, well, yes it looks like this is no bug... Sorry about confusion.
I've fixed this (r315). This test now indeed passes on all backends.
What about the test-int-array-* family of tests on PPC?
--
Olivier Guilyardi / Samalys
Sean Bolton wrote:
>
>> test-bit-circle-jack - starting (5s max) - buffer size: 512
>> || FAILURE: 2 != 514
>
> I thought it suspicious that 514 = 2 + 2 * 256, while on a PPC it
> returns
> FAILURE: 2 != 0. Endianness bug? No, but it's a clue...
Do you have a PPC? Which one? Can you please paste the whole output of
"make test"?
I
don't think you're seeing a *bug* in the jack ringbuffer, just a
difference in
semantics between it and the PortAudio and lfq imlementations. Both PA
and lfq mask the index after reading it, so they can completely fill
the buffer.
The jack implementation masks the stored index, which means it can't
ever completely fill the buffer, or there would be an ambiguity as
to whether
it was full or empty. The most it can store is (size - 1) bytes.
In the jack version of your code, at some point, the buffer almost
fills, and
jack_ringbuffer_write only writes a single byte to the buffer (low
order on x86,
high order on PPC). Next time around, it does this again. Then the
following
thread reads, not 0x0002 like it should, but either 0x0202 (x86) or
0x0000 (PPC).
I can confirm this, since the following will make the test 'succeed',
although it results in a very slow progress once the buffers are full.
Index: test-bit-circle.c
===================================================================
--- test-bit-circle.c (revision 314)
+++ test-bit-circle.c (working copy)
@@ -50,6 +50,9 @@
if (value)
{
+ while(jack_ringbuffer_write_space(rb[1]) < 2) {
+ usleep(1000);
+ }
jack_ringbuffer_write (rb[1], (char *) &value, sizeof (uint16_t));
value = 0;
}
22 Oct
22 Oct
4:45 p.m.
New subject: [LAU] Simple, easy multithreaded circular buffer library for Linux?
On Oct 20, 2008, at 3:18 PM, Olivier Guilyardi wrote:
What about the test-int-array-* family of tests on
PPC?
They all pass on my uniprocessor G4, but that doesn't
really tell us much. Anybody got a multiprocessor PPC?
This stuff makes my head hurt, too, but as best I can
figure out, I believe the jack code needs memory
barriers on several non-x86 architectures with weak
memory ordering, PPC probably being the most
common. It appears to me that without barriers,
there's a small chance reordered writes on one
processor could result in another processor reading
invalid data:
CPU1: CPU2:
write index ---
write data2 read index
write data3 read data1 <- invalid
write data1 read data2
--- read data3
x
Paul E. McKenney
Memory Ordering in Modern Microprocessors, Part I
http://www.linuxjournal.com/article/8211
Memory Ordering in Modern Microprocessors, Part II
http://www.linuxjournal.com/article/8212
Linus Torvalds
Re: Memory barriers and spin_unlock safety
http://lkml.org/lkml/2006/3/3/142
Parts of this *thread*
Re: Re: [liblf-dev] Possible lock-free ring buffer: msg#00152
http://techweb.rfa.org/pipermail/portaudio/2006-May/005661.html
4:51 p.m.
New subject: Fwd: [LAU] Simple, easy multithreaded circular buffer library for Linux?
Oops, didn't mean to send this, and regret that someone not reading
carefully might think Paul McKenney sent it. I'm following Jorn
Nettingsmeier's advice and taking my further discussion of the memory
barrier issue over to jack-devel. -Sean
Begin forwarded message:
From: Sean Bolton
Date: October 22, 2008 11:45:31 AM PDT
To: Olivier Guilyardi
Cc: linux-audio-dev(a)lists.linuxaudio.org
Subject: Re: [LAD] [LAU] Simple, easy multithreaded circular buffer
library for Linux?
On Oct 20, 2008, at 3:18 PM, Olivier Guilyardi wrote:
What about the test-int-array-* family of tests
on PPC?
They all pass on my uniprocessor G4, but that doesn't
really tell us much. Anybody got a multiprocessor PPC?
This stuff makes my head hurt, too, but as best I can
figure out, I believe the jack code needs memory
barriers on several non-x86 architectures with weak
memory ordering, PPC probably being the most
common. It appears to me that without barriers,
there's a small chance reordered writes on one
processor could result in another processor reading
invalid data:
CPU1: CPU2:
write index ---
write data2 read index
write data3 read data1 <- invalid
write data1 read data2
--- read data3
x
Paul E. McKenney
Memory Ordering in Modern Microprocessors, Part I
http://www.linuxjournal.com/article/8211
Memory Ordering in Modern Microprocessors, Part II
http://www.linuxjournal.com/article/8212
Linus Torvalds
Re: Memory barriers and spin_unlock safety
http://lkml.org/lkml/2006/3/3/142
Parts of this *thread*
Re: Re: [liblf-dev] Possible lock-free ring buffer: msg#00152
http://techweb.rfa.org/pipermail/portaudio/2006-May/005661.html
5:07 p.m.
New subject: [LAU] Simple, easy multithreaded circular buffer library for Linux?
Sean Bolton wrote:
On Oct 20, 2008, at 3:18 PM, Olivier Guilyardi wrote:
I think it might be worth to try the following on your G4:
- run the test *much* longer (change the sleep call at the end of
test-int-array.c). Having experimented a lot with my tests, I know that failures
appear after a truly random amount of time.
- induce entropy, move your mouse, compose music, make a coffee, kick your
computer... ;-)
- experiment with compiler optimization (-O1, -O2 or -O3, ... in the Makefile's
CFLAGS). I'm unsure about this, but it's been mentioned many times on this
thread and I think it's worth trying.
PS: I'm CC-ing this message to jack-devel as Joern (a great community engineer I
know ;) recommended.
--
Olivier Guilyardi / Samalyse
What about the test-int-array-* family of tests
on PPC?
They all pass on my uniprocessor G4, but that doesn't
really tell us much. Anybody got a multiprocessor PPC? 
27 Oct
27 Oct
5:38 p.m.
New subject: [LAU] Simple, easy multithreaded circular buffer library for Linux?
For the records, here is the output from a dual IBM Cell system
(QS-21), each PowerPC unit is exposed with two cores.
jlc
$ cat /proc/cpuinfo
processor : 0
cpu : Cell Broadband Engine, altivec supported
clock : 3200.000000MHz
revision : 5.1 (pvr 0070 0501)
processor : 1
cpu : Cell Broadband Engine, altivec supported
clock : 3200.000000MHz
revision : 5.1 (pvr 0070 0501)
processor : 2
cpu : Cell Broadband Engine, altivec supported
clock : 3200.000000MHz
revision : 5.1 (pvr 0070 0501)
processor : 3
cpu : Cell Broadband Engine, altivec supported
clock : 3200.000000MHz
revision : 5.1 (pvr 0070 0501)
timebase : 14318000
platform : Cell
machine : CHRP MCS, -n/a
=================================================================
./run-tests.sh bit-circle 512 jack jack-fix1 portaudio portaudio-nobarrier lfq
test-bit-circle-jack - starting (5s max) - buffer size: 512
||-||||||-||||-||||------------- SUCCESS
test-bit-circle-jack-fix1 - starting (5s max) - buffer size: 512
||||||||-||||||||--------------- SUCCESS
test-bit-circle-portaudio - starting (5s max) - buffer size: 512
||||||-|||-||||||--|------------ SUCCESS
test-bit-circle-portaudio-nobarrier - starting (5s max) - buffer size: 512
||||-|-|-||||||-||--||---------- SUCCESS
test-bit-circle-lfq - starting (5s max) - buffer size: 512
||-|||||||-||-|-||||------------ SUCCESS
./run-tests.sh int-array 16 jack jack-fix1 portaudio portaudio-nobarrier lfq
test-int-array-jack - starting (120s max) - array/buffer size: 8/16
[reader started] [writer started] [flowing] 29364 != 29360 at offset 0
FAILURE in chunk 702810
test-int-array-jack-fix1 - starting (120s max) - array/buffer size: 8/16
[reader started] [writer started] [flowing] SUCCESS
test-int-array-portaudio - starting (120s max) - array/buffer size: 8/16
[reader started] [writer started] [flowing] SUCCESS
test-int-array-portaudio-nobarrier - starting (120s max) -
array/buffer size: 8/16
[reader started] [writer started] [flowing] SUCCESS
test-int-array-lfq - starting (120s max) - array/buffer size: 8/16
[reader started] [writer started] [flowing] SUCCESS
5:40 p.m.
New subject: [LAU] Simple, easy multithreaded circular buffer library for Linux?
On Mon, Oct 27, 2008 at 4:38 PM, Jesse Chappell <jesse(a)essej.net> wrote:
For the records, here is the output from a dual IBM
Cell system
(QS-21), each PowerPC unit is exposed with two cores.
This is actually a QS-20, sorry.
jlc
28 Oct
28 Oct
9:38 a.m.
New subject: [Jack-Devel] ring buffer memory barriers
Hi,
I'm CC'ing this mail to jack-devel and using a more meaningful subject, to ease
data-mining.
This is the first ring buffer test on a PowerPC SMP, and there is apparently no
failure caused by the lack of memory barrier.
Jesse Chappell wrote:
For the records, here is the output from a dual IBM
Cell system
(QS-21), each PowerPC unit is exposed with two cores.
jlc
$ cat /proc/cpuinfo
processor : 0
cpu : Cell Broadband Engine, altivec supported
clock : 3200.000000MHz
revision : 5.1 (pvr 0070 0501)
processor : 1
cpu : Cell Broadband Engine, altivec supported
clock : 3200.000000MHz
revision : 5.1 (pvr 0070 0501)
processor : 2
cpu : Cell Broadband Engine, altivec supported
clock : 3200.000000MHz
revision : 5.1 (pvr 0070 0501)
processor : 3
cpu : Cell Broadband Engine, altivec supported
clock : 3200.000000MHz
revision : 5.1 (pvr 0070 0501)
timebase : 14318000
platform : Cell
machine : CHRP MCS, -n/a
=================================================================
./run-tests.sh bit-circle 512 jack jack-fix1 portaudio portaudio-nobarrier lfq
test-bit-circle-jack - starting (5s max) - buffer size: 512
||-||||||-||||-||||------------- SUCCESS
test-bit-circle-jack-fix1 - starting (5s max) - buffer size: 512
||||||||-||||||||--------------- SUCCESS
test-bit-circle-portaudio - starting (5s max) - buffer size: 512
||||||-|||-||||||--|------------ SUCCESS
test-bit-circle-portaudio-nobarrier - starting (5s max) - buffer size: 512
||||-|-|-||||||-||--||---------- SUCCESS
test-bit-circle-lfq - starting (5s max) - buffer size: 512
||-|||||||-||-|-||||------------ SUCCESS
./run-tests.sh int-array 16 jack jack-fix1 portaudio portaudio-nobarrier lfq
test-int-array-jack - starting (120s max) - array/buffer size: 8/16
[reader started] [writer started] [flowing] 29364 != 29360 at offset 0
FAILURE in chunk 702810
This failure is normal, it is the Jack ring buffer without my patch applied. It
also happens on x86 SMP and single-cpu, as previously reported.
test-int-array-jack-fix1 - starting (120s max) -
array/buffer size: 8/16
[reader started] [writer started] [flowing] SUCCESS
Once patched, jack's ringbuffer succeeds. The tests run two minutes, I think
Jesse's machine (dual 3.2Ghz PowerPC) runs fast enough so that a failure should
appear in this time interval, if it's technically possible. It's hard to be sure
though.
test-int-array-portaudio - starting (120s max) -
array/buffer size: 8/16
[reader started] [writer started] [flowing] SUCCESS
test-int-array-portaudio-nobarrier - starting (120s max) -
array/buffer size: 8/16
[reader started] [writer started] [flowing] SUCCESS
Whether memory barriers are deactivated or not in Portaudio's ringbuffer, the
test succeeds.
test-int-array-lfq - starting (120s max) -
array/buffer size: 8/16
[reader started] [writer started] [flowing] SUCCESS
This last one is Fons' LFQ.
Jesse: it might be worth running test-int-array longer (change the sleep() call
at the end of test-int-array.c). You could also try and run the test suite
several times: the threads might have been scheduled to run on the same
processor/core in your first attempt.
In this regard you can try with rbtest at r309:
svn co -r309 http://svn.samalyse.com/misc/rbtest
It prints the cpu on which the threads are started (I deactivated this because
sched_getcpu() was randomly absent or crashing, but it might work in you case).
Thanks,
--
Olivier Guilyardi / Samalyse
19 Oct
19 Oct
2:36 p.m.
New subject: [LAU] Simple, easy multithreaded circular buffer library for Linux?
On Sun, Oct 19, 2008 at 12:24 AM, Jack O'Quin <jack.oquin(a)gmail.com> wrote:
On Sat, Oct 18, 2008 at 10:45 PM, Paul Coccoli
<pcoccoli(a)gmail.com> wrote:
The only time you can get away without atomic ops is on uni-processor.
Please cite a reference that says otherwise.
Notice that all the fixes proposed all involve removing the "+=" and
using only assignment.
On Sat, Oct 18, 2008 at 11:29 PM, Jack O'Quin
<jack.oquin(a)gmail.com> wrote:
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. 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.
3:15 p.m.
New subject: [LAU] Simple, easy multithreaded circular buffer library for Linux?
On Sun, Oct 19, 2008 at 12:36:55PM -0400, Paul Coccoli wrote:
The only time you can get away without atomic ops is
on uni-processor.
Please cite a reference that says otherwise.
Plaese show us how using a non-atomic addition could go wrong.
Notice that all the fixes proposed all involve
removing the "+=" and
using only assignment.
First, that is not the same as requiring atomic addition.
Second, it is not true. The one I proposed just does the '+='.
If it's wrong show us how.
Ciao,
--
FA
Laboratorio di Acustica ed Elettroacustica
Parma, Italia
Lascia la spina, cogli la rosa.
4:04 p.m.
New subject: [LAU] Simple, easy multithreaded circular buffer library for Linux?
On Sun, Oct 19, 2008 at 1:08 PM, Fons Adriaensen <fons(a)kokkinizita.net> wrote:
On Sun, Oct 19, 2008 at 12:36:55PM -0400, Paul Coccoli
wrote:
On a side note, does anyone know what the performance penalty is (if
any) for using atomic ops?
And does it scale according to number of CPU cores? What other
factors are there? I assume the caching architecture makes a big
difference.
I've been using the atomic-ops library from HP for doing various
things lately, and I find it quite nice. But I have found myself
wondering whether I am paying some kind of penalty. Of course, I'm
sure it's less than the penalty for using locks.
Steve
The only time you can get away without atomic ops
is on uni-processor.
Please cite a reference that says otherwise.
Plaese show us how using a non-atomic addition could go wrong.
5865
days inactive
5875
days old
linux-audio-dev@lists.linuxaudio.org
22 comments
10 participants
participants (10)
-
Fons Adriaensen -
Jack O'Quin -
Jesse Chappell -
Joern Nettingsmeier -
Olivier Guilyardi -
Paul Coccoli -
Paul Davis -
Pieter Palmers -
Sean Bolton -
Stephen Sinclair