13 Jul
2004
13 Jul
'04
3:25 a.m.
Maged Michael from IBM, who is publishing lots of practical lock-free
algorithms these days, has just published a paper describing a
lock-free memory allocation algorithm:
http://www.research.ibm.com/people/m/michael/pldi-2004.pdf
It seems plausible that you could use this to safely allocate memory
from RT threads. The only questions I have about its practicality are:
1. how easy/possible is it to use two malloc() implementations in the
same program? My brief research suggests that mixing system malloc(3)
and sbrk(2) (the latter is the underlying mechanism for obtaining more
memory from the OS) is not guaranteed to be safe. A possible solution
I have encountered is to obtain memory from the OS by mmap(/dev/zero)
instead of using sbrk(2).
2. When your lock-free malloc needs more memory from the OS it will
still take a system call to do it. I believe I have heard it said in
the past that system calls of any sort are unacceptable in RT code, but
isn't this a bit a of a hard-line position?
Josh
13 Jul
13 Jul
8:24 a.m.
On Mon, Jul 12, 2004 at 10:15:05 -0700, Joshua Haberman wrote:
It seems plausible that you could use this to safely
allocate memory
from RT threads. The only questions I have about its practicality are:
Its not my experieince that you usually need to allocate memory in RT
threads, the times when I've seen it done are mostly <generalisation>
bacuase of bad design, excessive OO-ness or lack of knowledge of
alloca(3) </generalisation>.
- Steve
3:29 p.m.
Steve Harris wrote:
On Mon, Jul 12, 2004 at 10:15:05 -0700, Joshua
Haberman wrote:
One reason I can think of is that you want to be sure to never, ever
drop a captured buffer when you are recording. You need buffers to send
the captured audio data to a disk thread, but without being able to call
malloc() from the audio thread, you have to pre-allocate a fixed amount
of memory for this purpose. No guess is high enough to guarantee that
you will never drop buffers, and the more you allocate in advance the
higher your overhead.
You could use a lock-free malloc as an emergency memory store for when
your pre-allocated buffers run out.
Josh
It seems plausible that you could use this to
safely allocate memory
from RT threads. The only questions I have about its practicality are:
Its not my experieince that you usually need to allocate memory in RT
threads, the times when I've seen it done are mostly <generalisation>
bacuase of bad design, excessive OO-ness or lack of knowledge of
alloca(3) </generalisation>. 
4:09 p.m.
On Tue, Jul 13, 2004 at 10:21:23AM -0700, Joshua Haberman wrote:
You could use a lock-free malloc as an emergency
memory store for when
your pre-allocated buffers run out.
There's no such thing as a lock free malloc() that calls brk(), unless I
am confused. brk() is a syscall that can block the caller.
To make a lock-free malloc(), you have to malloc() a big chunk of memory,
then run your own allocator against it. You don't reduce your overhead at
all.
Or am I confused? Allocators never were my focus.. :)
7 p.m.
On Tue, Jul 13, 2004 at 10:21:23 -0700, Joshua Haberman wrote:
Thats true, but that problem (running out of disk buffer) only happens in
extreme conditions, soft RT systems fail under lots of extreme conditions
awyway.
- Steve
Its not my
experieince that you usually need to allocate memory in RT
threads, the times when I've seen it done are mostly <generalisation>
bacuase of bad design, excessive OO-ness or lack of knowledge of
alloca(3) </generalisation>.
One reason I can think of is that you want to be sure to never, ever
drop a captured buffer when you are recording. You need buffers to send
the captured audio data to a disk thread, but without being able to call
malloc() from the audio thread, you have to pre-allocate a fixed amount
of memory for this purpose. No guess is high enough to guarantee that
you will never drop buffers, and the more you allocate in advance the
higher your overhead. 
14 Jul
14 Jul
3:12 a.m.
Am Dienstag, 13. Juli 2004 22:50 schrieb Steve Harris:
On Tue, Jul 13, 2004 at 10:21:23 -0700, Joshua
Haberman wrote:
> >Its not my experieince that you usually need to allocate memory in RT
> >threads, the times when I've seen it done are mostly <generalisation>
> >bacuase of bad design, excessive OO-ness or lack of knowledge of
> >alloca(3) </generalisation>.
>
malloc does not guarantee, that the allocated memory is locked into physical
memory.
To say it short: A RT thread must NEVER call a function that might block!!
3:28 a.m.
On Wed, Jul 14, 2004 at 05:58:25AM +0200, Ralf Beck wrote:
Am Dienstag, 13. Juli 2004 22:50 schrieb Steve
Harris:
The point was that an RT-safe malloc() could be safe, but it indicates a
bad design.
If your app starts up, does malloc(1024*1024*32); walks through that
memory to page it in, then mlock()s it, you can write a "safe" malloc to
allocate from that memory. But yuck.
Tim
On Tue, Jul 13, 2004 at 10:21:23 -0700, Joshua
Haberman wrote:
> >Its not my experieince that you usually need to allocate memory in RT
> >threads, the times when I've seen it done are mostly <generalisation>
> >bacuase of bad design, excessive OO-ness or lack of knowledge of
> >alloca(3) </generalisation>.
>
malloc does not guarantee, that the allocated memory is locked into physical
memory.
To say it short: A RT thread must NEVER call a function that might block!! 
13 Jul
13 Jul
10:22 a.m.
Joshua Haberman wrote:
2. When your lock-free malloc needs more memory from the OS it will
still take a system call to do it. I believe I have heard it said in
the past that system calls of any sort are unacceptable in RT code, but
isn't this a bit a of a hard-line position?
Is msgrcv() unacceptable as well, then ?
--
Olivier
1:48 p.m.
On Tue, Jul 13, 2004 at 02:12:21PM +0200, Olivier Guilyardi wrote:
If you want to be careful, then yes. You can ask msgrcv to not block, but
I'd personally double check the kernel code. :)
Tim
2. When your
lock-free malloc needs more memory from the OS it will
still take a system call to do it. I believe I have heard it said in
the past that system calls of any sort are unacceptable in RT code, but
isn't this a bit a of a hard-line position?
Is msgrcv() unacceptable as well, then ?
2:19 p.m.
Tim Hockin wrote:
On Tue, Jul 13, 2004 at 02:12:21PM +0200, Olivier
Guilyardi wrote:
What do you usually use then to talk with a RT thread ? The JACK doc
talks about rwlocks, but message queues happen to elegantly suit my code...
--
og
Is msgrcv() unacceptable as well, then ?
If you want to be careful, then yes. You can ask msgrcv to not block, but
I'd personally double check the kernel code. :)
3:12 p.m.
On Tue, Jul 13, 2004 at 06:09:57PM +0200, Olivier Guilyardi wrote:
You can do IPC without syscalls, if you have atomic ops on a platform.
See the various lock-free FIFO implementations floating around.
If you want to
be careful, then yes. You can ask msgrcv to not block, but
I'd personally double check the kernel code. :)
What do you usually use then to talk with a RT thread ? The JACK doc
talks about rwlocks, but message queues happen to elegantly suit my code... 
10:49 a.m.
Depending from your particular needs, the fastes real time safe/ lock
free allocator is using an allocator that
manages a list of equal sized elements (of any type, tanks to C++
templates).
We use such an allocator in LinuxSampler and it's really fast, all
inlined and an alloc() usually takes only a few machine instructions,
no jumps etc.
see: http://www.linuxsampler.org
file common/RTELMemoryPool.h
It uses a preallocated memory pool of elements of type T with a maximum
pool size of N, thus the memory usage is about
(sizeof(T)+overhead)*N
The overhead of such lists is 8 byte (prev and next elem ptrs) if you
don't need that the allocated element can be inserted in a doubly linked
list without requiring
additional list structures (and thus wasting lots of memory too).
In our case we use the latter form thus the overhead ist 16bytes per
allocated element.
Of course this is not ideal when you want to allocate an extremely large
number of elements of very small size (eg 1-4 bytes) but for other
purposes it's quite
handy. We use it to keep track of the sustained (active) notes in the
voice rendering routines and it works really well, the performance on
2GHz CPUs
is in the range of 100's of millions of alloc/free per second.
Of course if you need to allocate consecutive segments of arbitrary
sizes then a malloc() style algorithm is needed but I think in most
cases you can easily
rewrite/change your code and data structs so that they can take
advantage of the above RT allocator.
cheers,
Benno
Joshua Haberman wrote:
Maged Michael from IBM, who is publishing lots of
practical lock-free
algorithms these days, has just published a paper describing a
lock-free memory allocation algorithm:
http://www.research.ibm.com/people/m/michael/pldi-2004.pdf
It seems plausible that you could use this to safely allocate memory
from RT threads. The only questions I have about its practicality are:
1. how easy/possible is it to use two malloc() implementations in the
same program? My brief research suggests that mixing system malloc(3)
and sbrk(2) (the latter is the underlying mechanism for obtaining more
memory from the OS) is not guaranteed to be safe. A possible solution
I have encountered is to obtain memory from the OS by mmap(/dev/zero)
instead of using sbrk(2).
2. When your lock-free malloc needs more memory from the OS it will
still take a system call to do it. I believe I have heard it said in
the past that system calls of any sort are unacceptable in RT code,
but isn't this a bit a of a hard-line position?
Josh
7235
days inactive
7236
days old
linux-audio-dev@lists.linuxaudio.org
12 comments
6 participants
participants (6)
-
Benno Senoner -
Joshua Haberman -
Olivier Guilyardi -
Ralf Beck -
Steve Harris -
Tim Hockin