[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:
> [...]
> > > 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.
> >
> > Ah ok, but that would mean being sure that the new pool will be
> > contiguous to the first one.
>
> No! You'd pre-allocate (or just not add) the "holes", so those areas
> are just ignored.

Maybe I'm just ignorant (probably), but doesn't preallocation mean
"allocate but don't use"? Or to better say you malloc() such areas but
 don't use them with the rt allocator?
If this is the case, why would you do that? Wouldn't it be easier and
more logical to just use all the allocated memory right from the
start?
However I was thinking about the situation in which all the allocated
memory is full, so either you just can't allocate any more memory or
resize the pool.

> > Then, if TLSF works as I remember, you
> > would have to either rearrange the bitamp (which could bring to a
> > big amount of fragmentation too) or have the second bitmap logically
> > equivalent to the first, and that is in practice what I was
> > suggesting, except for the contiguity.
>
> Well, my idea was to construct the bitmap based on the maximum pool
> size. Suboptimal if you start with a very small pool and/or set the
> max very high, but then again, I think you could keep the upper and
> lower bounds within a reasonable range in most applications. It
> doesn't make sense to start with a pool of just a few kB on a 256+ MB
> machine, and the upper bound for any RT memory management is
> obviously the amount of physical RAM available for locking.

Another newbie question: how do you know how much memory you can need
(without user intervention)?

> [...]
> > > 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.
> >
> > Yes, some clever trick should be found. :-)
> > Maybe one could make use some trick based on the particular geometry
> > of TLSF pools and relative bitmaps.
>
> Well, I'm not even sure it takes any real tricks; it all depends on
> the algorithm. I just downloaded TLSF 2.3.2 in order to find out. :-)

I meant a mathematical trick based on the algorithm ;-)
The fact is that, IIRC, memory blocks are arranged with some kind of
mathematical distribution (linear? quadratic?) by increasing size, so
with the bitmap you maybe can know with a couple of instructions
what's the maximum allocable size on the pool, or using some other
"trick".

> Oh, and that version should work on 64 bit platforms as well, so I can
> actually use it out of the box on my development system. ;-)

Glad to know that, I think I will use it in the future and portability
is one of my main concerns :-)

> > > 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...
> >
> > This is a problem as well :-\
>
> If the pool blocks have the right sizes in relation to the address
> range they're in, one could get away with grabbing a few bits of the
> pointer and look up the pool in a small table. Tricky and dangerous,
> though, as you have no real control over the allocation of new pool
> blocks...

You said that too :-P See above.

> > [heresy mode on]
> > Maybe change values passed to/returned from the
> > allocation/deallocation calls?
> > [heresy mode off]
>
> Not quite sure what you mean... Sounds dangerous, though. ;-)

Nothing very dangerous actually. I just meant that you could use some
more "non standard" parameters to use with allocator functions to do
some "trick" :-)

> [...]
> > > 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.)
> >
> > It's just that I'm a bit a "purist", however I do agree that maybe
> > your suggestion could solve the problem, at least until someone goes
> > deep into TLSF logic.
>
> Yeah... I prefer nice and clean solutions too, but sometimes you just
> have to get the job done, and worry about style in the next
> refactoring cycle. :-)

Of course.

> Oh, BTW, I just realized that my "quick hack" approach actually has a
> nice bonus: It eliminates the explicit 'mem_pool' arguments from
> free_ex() and realloc_ex(), eliminating nasty "Oops, wrong pool!"
> bugs. Maybe it's not such a bad idea, after all...

True.

> I don't like the idea of an extra pointer per block for small blacks -
> but if you deal with large numbers of small blocks (for events and
> the like), you should probably use a dedicated manager for that
> anyway. For example, in Audiality I use a per-host LIFO stack of
> blocks, which means no memory overhead at all, as "free()" doesn't
> need to know anything about the block to throw it back on the stack.

Nice solution. I guess, on the top of my ignorance, that those blocks
are fixed size, right?
(ehm... at first glance Audality seems quite interesting for my
project - http://naspro.sourceforge.net -, can I contact you privately
about that? or maybe just send me an e-mail)

> > > > 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. :-)
> >
> > Of course... but also a nice challenging task (which could let you
> > go insane) :-)
>
> Well, I'm crazy enough to design and implement a VM based
> scripting/programming language, so it's not like I'm totally unlikely
> to dive into stuff like that. :-D

Insanely excellent ;-)

[...]

Stefano