[LAD] LV2 realtime safe memory pool extension

[David Olofson]

On Friday 09 November 2007, Stefano D'Angelo wrote:
[...]
> > Well, not really; you could just wrap the memory manager, adding
> > a 'manager' field to every chunk. Then you can just throw in
> > another TLSF manager instance when you need more memory.
> > The 'manager' field will point the free() wrapper to the correct
> > manager instance. 
> 
> Argh!

Nice, eh? ;-)


[...]
> > Maybe hack TLSF to take a "maximum address span" init argument, so
> > you can extend the pool as needed up to that limit? You'd just
> > allocate new blocks with malloc() and instruct the hacked TLSF to
> > extend to the end of that block, while pre-allocating (throwing
> > away) any holes caused by unrelated malloc()s.
> 
> Maybe I just don't understand, but however doesn't this mean, in
> practice, allocating all of the memory right from the start?

No, you'd just construct the manager's internal structures as if you 
were going to allocate a pool of the maximum size - but you actually 
give it a smaller initial amount of memory.

Provided the allocator actually *works* without a fully populated pool 
(I'm not sure about that...), this would allow new memory blocks to 
added to the pool later, as long as they're within the address range 
defined by the start of the pool and the "maximum address span" that 
the allocator was initialized for.


> > > And even if you have some background thread doing it when it's
> > > needed, I think it's very hard to do that while plugins are 
running,
> > > and so allocating and modifying on that memory.
> >
> > Yes, that's why you can't realloc() the pool. You really have to
> > add new blocks of memory to it.
> 
> Mmmm... in my opinion someone could contact the TLSF authors and see
> what can be done.

Yeah, or just read the code (again), for starters.

(I started hacking an RT memory manager for EEL, then found and 
studied TLSF a bit, but that must have been one or two years ago... 
Got away with a small RTAI kernel driver + "firm" real time scripting 
for that application, and then I've been working on other stuff.)


> I was thinking that when the memory is "near to saturation", the
> allocator could malloc() a new pool whose size is equal to that of
> the first pool (maybe using a background thread) so that the bitmap
> for the new pool is actually the same.

As I understand it, the bitmap represents the current state of the 
pool, so if you allocate a new pool, you'd need a new bitmap to go 
with it, or weird things will happen.


> Now the address resolving algorithm 
> should know in some way that the first pool is full for blocks of
> that size or bigger, so the adress should be resolved in the second
> pool, and so on.

Wiring additional pools to the out-of-memory condition indeed avoids 
overhead when dealing with the initial pool, but it multiplies 
overhead when you need to deal with additional pools instead.

Also, how do you know where a free()d block belongs? Checking the 
address against each pool isn't exactly efficient, but perhaps no 
disaster for small number of pools...

Basically, without somehow piggy-backing on the existing logic of 
TLSF, I have a hard time seeing how you could get away with less 
overhead than the "wrapped manager" solution I first suggested. 
(That "only" adds one pointer per allocated block, and an extra level 
of indirection to use the right manager. Not great, but at least it's 
simple, lets you add pools of any size, and scales to any number of 
pools.)


> This is just a thought... I never really wrote or worked on an
> allocator :-) 

I did, but only enough to realize that coming up with something really 
nice and efficient is a lot of work. :-)


> Anyway, getting back to the initial question, I think that we should
> have two separate extensions, one for RT fixed size allocators and
> one for "real" RT-safe allocators.

Yes, that probably does make sense after all, considering that it's 
quite likely that a lot of plugins will deal only with a small number 
of different block sizes, and the fact that a "real" RT allocator 
(even a really good one) has quite a bit more overhead than a simple 
LIFO pool.


//David Olofson - Programmer, Composer, Open Source Advocate

.-------  http://olofson.net - Games, SDL examples  -------.
|        http://zeespace.net - 2.5D rendering engine       |
|       http://audiality.org - Music/audio engine          |
|     http://eel.olofson.net - Real time scripting         |
'--  http://www.reologica.se - Rheology instrumentation  --'