[linux-audio-dev] malloc() in RT code considered not-so-harmful?

[Benno Senoner]

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
>
>