25 Feb
2012
25 Feb
'12
11:26 p.m.
Hi everyone, hoping to get opinions from gurus on here, who have been
*incredibly* helpful in getting my project to where its at. A million thank
yous!
Ok, the situation so far, which is working well:
- the app uses a generalized 'message' structure, all the different forms
of messages fit into this structure by having it act alike a union. ( ie, a
message always takes up the same amount of space, no matter the type )
- messages do not container pointers, in order that they be simple to send
and receive over network clients, hardware, etc
- there are ringbuffers between my audio thread and real time thread
What I'm tackling:
- I want to add the capability for messages to have deferred execution, so
they can be sent with a 'process at 4:3:1' kind of thing
- I think the best tradeoff for my app so far will be to use a hybrid of a
timeline array and a linked list. there will be coarse time values stored
by raw array indexing, speeding up lookup, and fine time values will be
stored in the messages themselves
- so, when the engine is processing deferred messages, it will go and check
timelineArray for all messages at bar 1:beat 1, which will be a linked list
of all the messages with start time between bar:1 beat 1 and bar 1: beat 2
( time resolution may change, this just for example
- then the engine iterates on every tick through that list of messages.
This way, iteration on every tick is limited to a reasonable sized linked
list and I can play with the cpu vs data storage equation by simply
changing the resolution of the time line array
Issues:
- I need to allocate memory for new linked list items in the realtime thread
- the timeline array needs to be able to grow in the real time thread
Thoughts:
- I don't need to get it perfect *right now* but I need to be able to
change it to Really Good later
- I checked out some resources, like this one the Design Patterns for *Real*
-*Time* Computer *Music*
Systems<http://www.google.ca/url?sa=t&rct=j&q=audio%20allocating%20memory%20in%20real%20time%20thread&source=web&cd=3&ved=0CDIQFjAC&url=http%3A%2F%2Fwww.cs.cmu.edu%2F%7Erbd%2Fdoc%2Ficmc2005workshop%2Freal-time-systems-concepts-design-patterns.pdf&ei=g1xJT66mEYvOiALDnN3oAQ&usg=AFQjCNET-FI8lrlYfnIBP39Dwr-GLDptrA&sig2=f5fUXFebwZ6MpOcF2tYJug&cad=rja>
and the supercollider book chapter and see there are a lot of options
- I could pre-allocate a giant list of messages and pluck the data off that
list when I need to make a new one
- I could pre-allocate a block of memory and allocate off that
- I could allocate in the non-realtime thread and then pass memory over in
queues.
Would love to hear opinions on how others would solve these, including
tradeoffs of each.
thanks!
iain
25 Feb
25 Feb
11:26 p.m.
New subject: memory allocation for the real time thread, opinions wanted
On Sat, Feb 25, 2012 at 2:25 PM, Iain Duncan <iainduncanlists(a)gmail.com>wrote;wrote:
Hi everyone, hoping to get opinions from gurus on
here, who have been
*incredibly* helpful in getting my project to where its at. A million thank
yous!
Ok, the situation so far, which is working well:
- the app uses a generalized 'message' structure, all the different forms
of messages fit into this structure by having it act alike a union. ( ie, a
message always takes up the same amount of space, no matter the type )
- messages do not container pointers, in order that they be simple to send
and receive over network clients, hardware, etc
- there are ringbuffers between my audio thread and real time thread
What I'm tackling:
- I want to add the capability for messages to have deferred execution, so
they can be sent with a 'process at 4:3:1' kind of thing
- I think the best tradeoff for my app so far will be to use a hybrid of a
timeline array and a linked list. there will be coarse time values stored
by raw array indexing, speeding up lookup, and fine time values will be
stored in the messages themselves
- so, when the engine is processing deferred messages, it will go and
check timelineArray for all messages at bar 1:beat 1, which will be a
linked list of all the messages with start time between bar:1 beat 1 and
bar 1: beat 2 ( time resolution may change, this just for example
- then the engine iterates on every tick through that list of messages.
This way, iteration on every tick is limited to a reasonable sized linked
list and I can play with the cpu vs data storage equation by simply
changing the resolution of the time line array
Issues:
- I need to allocate memory for new linked list items in the realtime
thread
- the timeline array needs to be able to grow in the real time thread
Thoughts:
- I don't need to get it perfect *right now* but I need to be able to
change it to Really Good later
- I checked out some resources, like this one the Design Patterns for *
Real*-*Time* Computer *Music*
Systems<http://www.google.ca/url?sa=t&rct=j&q=audio%20allocating%20memory%20in%20real%20time%20thread&source=web&cd=3&ved=0CDIQFjAC&url=http%3A%2F%2Fwww.cs.cmu.edu%2F%7Erbd%2Fdoc%2Ficmc2005workshop%2Freal-time-systems-concepts-design-patterns.pdf&ei=g1xJT66mEYvOiALDnN3oAQ&usg=AFQjCNET-FI8lrlYfnIBP39Dwr-GLDptrA&sig2=f5fUXFebwZ6MpOcF2tYJug&cad=rja>
and the supercollider book chapter and see there are a lot of options
- I could pre-allocate a giant list of messages and pluck the data off
that list when I need to make a new one
- I could pre-allocate a block of memory and allocate off that
- I could allocate in the non-realtime thread and then pass memory over in
queues.
Would love to hear opinions on how others would solve these, including
tradeoffs of each.
Also, any thoughts on 'good enough to start with' techniques welcome!
iain
26 Feb
26 Feb
12:28 p.m.
New subject: memory allocation for the real time thread, opinions wanted
Iain Duncan <iainduncanlists(a)gmail.com> wrote:
Hi
- I could pre-allocate a giant list of messages and
pluck the data off
that
list when I need to make a new one
- I could pre-allocate a block of memory and allocate off that
I'm writing from my phone, so for the sake of brevity, I will only talk about one
option you might have missed:
Google for "A Study in Malloc: A Case of Excessive Minor Faults - USENIX" by
Ezolt.
You can instruct your malloc implementation to operate on a previously allocated (and
prefaulted) memory pool. free() will then never return the memory to the OS, but back to
this memory pool.
This way, if you have a rough estimation for your overall memory requirements, you simply
allocate it once in a non-real-time context and then use malloc/free at will.
HTH
27 Feb
27 Feb
9:38 a.m.
New subject: memory allocation for the real time thread, opinions wanted
[Adrian Knoth]
Iain Duncan <iainduncanlists(a)gmail.com> wrote:
Hi
This, I'm afraid, is an idea with a fair share of issues. It does not
seem a trivial problem to estimate the total memory needs of a
reasonably complex application. And even if you can solve this, you
will find that common malloc implementations (such as the one in
glibc) protect the heap with mutexes. Regardless of memory
availability, your real-time thread can always stall in malloc() or
free() when a heap mutex is found locked by another thread.
As for the original question, I'd suggest handling the maintenance and
memory management of large lists of events in low-priority,
low-frequency threads. These threads periodically feed the realtime
thread bursts of a small number of events, ahead of time and using
preallocated FIFO queues which can be of reasonably modest size. (In
fact, I seem to remember that this approach has been discussed on this
list recently, if perhaps briefly.)
Cheers, Tim
- I could pre-allocate a giant list of messages
and pluck the data off
that
list when I need to make a new one
- I could pre-allocate a block of memory and allocate off that
I'm writing from my phone, so for the sake of brevity, I will only
talk about one option you might have missed:
Google for "A Study in Malloc: A Case of Excessive Minor Faults - USENIX" by
Ezolt.
You can instruct your malloc implementation to operate on a
previously allocated (and prefaulted) memory pool. free() will then
never return the memory to the OS, but back to this memory pool.
This way, if you have a rough estimation for your overall memory
requirements, you simply allocate it once in a non-real-time context
and then use malloc/free at will. 
9:59 a.m.
Hi Iain,Can you use any alternatives such as:
a. Don't malloc/memcpy space for these messages in the RT thread - just use the
copythat is on the ringbuffer and move the write pointers when you have used the message.
b. Just write memory pointers on to the ringbuffer: this gives you quite a lot more
spacesince a memory pointer is likely to be smaller than you message union. Your code
canassume that when the low prio thread has put something on the ringbuffer it cannot
befreed/rereused until the read index has moved past it.
Both of these methods are affectively the same, what you are trying to do is providea
method that the low prio thread is responsible for both malloc and free. You can
alsoreduce the amount of copies you are making although that is not a big overhead
sinceyour message union is probably pretty small.
If you think the RT thread is going to need these bits of message memory for more timethan
the size of the ringbuffer then you could consider using pointers but passing themback
from the RT thread over another ringbuffer when you no longer need them.
Regards, nick
"at the end of the day its nil nil at half time”.
Trevor Brooking
Date: Mon, 27 Feb 2012 09:38:34 +0100
From: tim(a)quitte.de
To: adi(a)drcomp.erfurt.thur.de
CC: linux-audio-dev(a)lists.linuxaudio.org
Subject: Re: [LAD] memory allocation for the real time thread, opinions wanted
[Adrian Knoth]
Iain Duncan <iainduncanlists(a)gmail.com>
wrote:
Hi
This, I'm afraid, is an idea with a fair share of issues. It does not
seem a trivial problem to estimate the total memory needs of a
reasonably complex application. And even if you can solve this, you
will find that common malloc implementations (such as the one in
glibc) protect the heap with mutexes. Regardless of memory
availability, your real-time thread can always stall in malloc() or
free() when a heap mutex is found locked by another thread.
As for the original question, I'd suggest handling the maintenance and
memory management of large lists of events in low-priority,
low-frequency threads. These threads periodically feed the realtime
thread bursts of a small number of events, ahead of time and using
preallocated FIFO queues which can be of reasonably modest size. (In
fact, I seem to remember that this approach has been discussed on this
list recently, if perhaps briefly.)
Cheers, Tim
_______________________________________________
Linux-audio-dev mailing list
Linux-audio-dev(a)lists.linuxaudio.org
http://lists.linuxaudio.org/listinfo/linux-audio-dev - I could pre-allocate a giant list of messages
and pluck the data off
that
list when I need to make a new one
- I could pre-allocate a block of memory and allocate off that
I'm writing from my phone, so for the sake of brevity, I will only
talk about one option you might have missed:
Google for "A Study in Malloc: A Case of Excessive Minor Faults - USENIX" by
Ezolt.
You can instruct your malloc implementation to operate on a
previously allocated (and prefaulted) memory pool. free() will then
never return the memory to the OS, but back to this memory pool.
This way, if you have a rough estimation for your overall memory
requirements, you simply allocate it once in a non-real-time context
and then use malloc/free at will. 
11:59 a.m.
New subject: memory allocation for the real time thread, opinions wanted
Hi
It's good to work with pointers, as Nick pointed out.
If that is not possilbe for any reason,
an options is to use a (pre-allocated) memory pool.
You might want to examine this library : TLSF
http://www.gii.upv.es/tlsf/
" I could allocate in the non-realtime thread and then pass memory
over in queues. "
That could be feasable.
-
E.R.
2:04 p.m.
New subject: memory allocation for the real time thread, opinions wanted
On Mon, Feb 27, 2012 at 09:59:19AM +0100, Nick Copeland wrote:
Both of these methods are affectively the same, what
you are trying to do is provide
a method that the low prio thread is responsible for both malloc and free.
That's a nice method, it effectively uses the LFQ to 'send back' an item
after
use by the recipient. It depends on the particular implementation of the queue,
you need one that allows to read one (or more if necessary) items without moving
the read pointer - that should be done only after the data has been used since
it signals that the data can be freed.
The alternative is to make this explicit, by having two pairs of indices
operate on the same buffer:
---------cccccccbbbbbbbbaaaaaaa---------
^ ^ ^ ^
R2 W2 R1 W1
W1 and R1 are the usual W/R indices, assume they increment whenever
an item is written or read. The 'aaaaa' are items sent by the low-prio
thread but not yet received by the RT one.
W2 is incremented by the RT thread whenever it's done with an item
(this is a 'write' operation, but no data transfer is necessary).
The 'bbbbbb' are items currently being used by the RT thread.
R2 is used by the low-prio thread to 'read' items that can be freed
or re-used (the 'ccccccc').
In fact this can be generalised to support any linear chain of threads
operating sequentially on the same data, just use as many R/W pairs as
there are threads. As long as there is only one thread modifying each
index and only one other thread reading it, it can still be lock-free.
Ciao,
--
FA
Vor uns liegt ein weites Tal, die Sonne scheint - ein Glitzerstrahl.
28 Feb
28 Feb
2:01 a.m.
New subject: memory allocation for the real time thread, opinions wanted
On Mon, Feb 27, 2012 at 8:04 AM, Fons Adriaensen <fons(a)linuxaudio.org> wrote:
On Mon, Feb 27, 2012 at 09:59:19AM +0100, Nick
Copeland wrote:
[SNIP]
Why not just use 2 ringbuffers: one to send pointers to the RT thread,
and a second to send them back to the low prio thread (so it can free
them). You probably need a semaphore for the return ringbuffer, but
that should be RT-safe.
Both of these methods are affectively the same,
what you are trying to do is provide
a method that the low prio thread is responsible for both malloc and free.
That's a nice method, it effectively uses the LFQ to 'send back' an item
after
use by the recipient. It depends on the particular implementation of the queue,
you need one that allows to read one (or more if necessary) items without moving
the read pointer - that should be done only after the data has been used since
it signals that the data can be freed.
The alternative is to make this explicit, by having two pairs of indices
operate on the same buffer: 
2:44 a.m.
On Mon, 27 Feb 2012 20:01:18 -0500
Paul Coccoli <pcoccoli(a)gmail.com> wrote:
On Mon, Feb 27, 2012 at 8:04 AM, Fons Adriaensen
<fons(a)linuxaudio.org> wrote:
That's what I thought... would be better for someone who is new to real
time threads and memory allocation... and is what I decided on... minus
the semaphore.
So why is a semaphore needed? If the RT thread only sends an item back
when it absolutely no longer will use it?
James.
On Mon, Feb 27, 2012 at 09:59:19AM +0100, Nick
Copeland wrote:
[SNIP]
Why not just use 2 ringbuffers: one to send pointers to the RT thread,
and a second to send them back to the low prio thread (so it can free
them). You probably need a semaphore for the return ringbuffer, but
that should be RT-safe. Both of these methods are affectively the same,
what you are
trying to do is provide a method that the low prio thread is
responsible for both malloc and free.
That's a nice method, it effectively uses the LFQ to 'send back' an
item after use by the recipient. It depends on the particular
implementation of the queue, you need one that allows to read one
(or more if necessary) items without moving the read pointer - that
should be done only after the data has been used since it signals
that the data can be freed.
The alternative is to make this explicit, by having two pairs of
indices operate on the same buffer: _______________________________________________
Linux-audio-dev mailing list
Linux-audio-dev(a)lists.linuxaudio.org
http://lists.linuxaudio.org/listinfo/linux-audio-dev
--
http://jwm-art.net/
image/audio/text/code/
10:34 p.m.
New subject: memory allocation for the real time thread, opinions wanted
On Mon, Feb 27, 2012 at 8:43 PM, James Morris <james(a)jwm-art.net> wrote:
I suppose the semaphore isn't strictly necessary, but I think it's an
easy way to tell the main thread that it has a message to process.
Although one that probably doesn't integrate well with most
main/non-RT threads.
On Mon, 27 Feb 2012 20:01:18 -0500
Paul Coccoli <pcoccoli(a)gmail.com> wrote:
[Mass snippage]
Why not just
use 2 ringbuffers: one to send pointers to the RT thread,
and a second to send them back to the low prio thread (so it can free
them). You probably need a semaphore for the return ringbuffer, but
that should be RT-safe.
That's what I thought... would be better for someone who is new to real
time threads and memory allocation... and is what I decided on... minus
the semaphore.
So why is a semaphore needed? If the RT thread only sends an item back
when it absolutely no longer will use it?
29 Feb
29 Feb
7:24 p.m.
New subject: memory allocation for the real time thread, opinions wanted
Thanks for all the comments everyone!
iain
On Tue, Feb 28, 2012 at 1:34 PM, Paul Coccoli <pcoccoli(a)gmail.com> wrote:
On Mon, Feb 27, 2012 at 8:43 PM, James Morris
<james(a)jwm-art.net> wrote:
I suppose the semaphore isn't strictly necessary, but I think it's an
easy way to tell the main thread that it has a message to process.
Although one that probably doesn't integrate well with most
main/non-RT threads.
_______________________________________________
Linux-audio-dev mailing list
Linux-audio-dev(a)lists.linuxaudio.org
http://lists.linuxaudio.org/listinfo/linux-audio-dev
On Mon, 27 Feb 2012 20:01:18 -0500
Paul Coccoli <pcoccoli(a)gmail.com> wrote:
[Mass snippage]
Why not
just use 2 ringbuffers: one to send pointers to the RT thread,
and a second to send them back to the low prio thread (so it can free
them). You probably need a semaphore for the return ringbuffer, but
that should be RT-safe.
That's what I thought... would be better for someone who is new to real
time threads and memory allocation... and is what I decided on... minus
the semaphore.
So why is a semaphore needed? If the RT thread only sends an item back
when it absolutely no longer will use it? 
9:12 p.m.
On Tue, 2012-02-28 at 16:34 -0500, Paul Coccoli wrote:
On Mon, Feb 27, 2012 at 8:43 PM, James Morris
<james(a)jwm-art.net> wrote:
I suppose the semaphore isn't strictly necessary, but I think it's an
easy way to tell the main thread that it has a message to process.
Although one that probably doesn't integrate well with most
main/non-RT threads.
For a main thread that's always rolling anyway you wouldn't use one.
The semaphore is to wake up a receiving thread that is *waiting* for a
message from the ringbuffer (e.g. it is a worker thread solely dedicated
to that)
-dr
On Mon, 27 Feb 2012 20:01:18 -0500
Paul Coccoli <pcoccoli(a)gmail.com> wrote:
[Mass snippage]
Why not
just use 2 ringbuffers: one to send pointers to the RT thread,
and a second to send them back to the low prio thread (so it can free
them). You probably need a semaphore for the return ringbuffer, but
that should be RT-safe.
That's what I thought... would be better for someone who is new to real
time threads and memory allocation... and is what I decided on... minus
the semaphore.
So why is a semaphore needed? If the RT thread only sends an item back
when it absolutely no longer will use it?
28 Feb
28 Feb
2:49 a.m.
On Mon, 2012-02-27 at 20:01 -0500, Paul Coccoli wrote:
On Mon, Feb 27, 2012 at 8:04 AM, Fons Adriaensen
<fons(a)linuxaudio.org> wrote:
This is exactly what I do in plugins (e.g. LV2 eg-sampler) to load
samples and such when the command to do so comes in the audio thread.
Works well.
-dr
On Mon, Feb 27, 2012 at 09:59:19AM +0100, Nick
Copeland wrote:
[SNIP]
Why not just use 2 ringbuffers: one to send pointers to the RT thread,
and a second to send them back to the low prio thread (so it can free
them). You probably need a semaphore for the return ringbuffer, but
that should be RT-safe. Both of these methods are affectively the same,
what you are trying to do is provide
a method that the low prio thread is responsible for both malloc and free.
That's a nice method, it effectively uses the LFQ to 'send back' an item
after
use by the recipient. It depends on the particular implementation of the queue,
you need one that allows to read one (or more if necessary) items without moving
the read pointer - that should be done only after the data has been used since
it signals that the data can be freed.
The alternative is to make this explicit, by having two pairs of indices
operate on the same buffer: 
3:16 p.m.
New subject: memory allocation for the real time thread, opinions wanted
On Tue, Feb 28, 2012 at 1:01 AM, Paul Coccoli <pcoccoli(a)gmail.com> wrote:
Why not just use 2 ringbuffers: one to send pointers
to the RT thread,
and a second to send them back to the low prio thread (so it can free
them)
The entire Luppp engine is based around that principle. The only downside
is that one can't prioritze the messages, they must all be handled every
process() to ensure that nothing essential is missed.. But that's something
small I can live with :)
-Harry
4439
days inactive
4443
days old
linux-audio-dev@lists.linuxaudio.org
13 comments
10 participants
participants (10)
-
Adrian Knoth -
David Robillard -
Emanuel Rumpf -
Fons Adriaensen -
Harry van Haaren -
Iain Duncan -
James Morris -
Nick Copeland -
Paul Coccoli -
Tim Goetze