[LAD] LV2 realtime safe memory pool extension

[Stefano D'Angelo]

2007/11/9, David Olofson <david at olofson.net>:
> On Friday 09 November 2007, Stefano D'Angelo wrote:
> [...]
> > > Yes, that's exactly my point, but I think it needs to deal with
> > > arbitrary size chunks to actually be able to serve that purpose in
> > > real applications.
> >
> > IIRC the TLSF allocator can do that.
>
> Yes, that's what it does - which is why I suggested it. ;-)
>
>
> [...]
> > > Wouldn't it be more useful with some interface that allows plugins
> > > to request memory in a non-blocking manner, and if instant
> > > allocation fails, have the host notify the plugin when the memory
> > > is available?
> > > Basically, a malloc() call that means "If I can't have this memory
> > > right away, please expand the pool so I can have it later!"
> >
> > Mmmm.. I guess it's not easy to resize the pool in a rt-safe way.
>
> 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!

> However, a nice, clean, efficient solution might be a bit harder to
> come up with, I think. IIRC, the current TLSF implementations scale
> various internal structures and stuff to fit the pool size, so you
> can't just bump the "brk limit" later.

I remember this way too.

> 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? In such
case, why should you do something like that?

> > 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.
However, I was thinking something like this: IIRC the TLSF allocator
uses a bitmap with chunks of different size, covering the whole pool,
which is built when the allocator is instantiated. Then, when you
request some piece of memory, it starts looking for it from the block
of minimum size which could be used, and then continues looking for
the next block available (which is by construction equal or bigger in
size then the first).
The address of the first block can be resolved with a O(1) algorithm.
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. 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.
This is just a thought... I never really wrote or worked on an allocator :-)

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.

Stefano