[LAD] LV2 realtime safe memory pool extension

[David Olofson]

On Saturday 10 November 2007, Stefano D'Angelo wrote:
[...]
> > > 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?

No, I wasn't very clear there. The pre-allocation I'm talking about is 
from the TLSF POV; that is, one would tell TLSF that these areas are 
not to be touched (as they're in used by code that got it through 
stdlib malloc()). Or, you just don't add these areas to the pool; you 
just add the blocks you actually get from stdlib malloc().

Depends on how the pool is managed; whether you can actually have N 
blocks with independent stand and end addresses, or if you you need 
to define the pool as a single memory range. In the latter case, 
you'd have to fake it by somehow implementing "holes".

Example:

You have some audio plugin host or something, where you initialize 
TLSF with 256 KB of memory. Eventually, the host realizes you're 
about to run out of memory, and has some background thread grab 
another 256 KB.

Of course, when the audio thread gets that memory block, it turns out 
that the host GUI nicked some memory in between, so there's a 128 KB 
hole between the end of the current TLSF pool and the new memory 
block. Now, what do you do?

Well, if you can't just threw the new block in the appropriate "sub 
pool", you'll have to do something like this:

	1) Extend the pool block to 256 + 128 + 256 KB, so
	   that it covers the two blocks, and the hole
	   between them.

	2) Somehow remove (or don't add) the memory in the
	   area of the hole to the TLSF. The hole will just
	   be ignored, as if it was allocated right away
	   and never released.

(Technical detail: You need to make sure the block header lands within 
the pool memory *before* the start of the hole, as you obviously 
can't have TLSF mess with the first few bytes of the hole area, where 
the header would normally be.)


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

In short, you don't! :-)

The best you can do is figure out some sensible start value based on 
available memory, CPU power and maybe other stuff that might be 
relevant.

If you can't scale dynamically, there *will* be trouble in some cases; 
that's just the way it is. The only solution to that is to 
allow "advanced users" to configure the application manually, or at 
least allow them to give the application some suggestions


[...]
> > 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".

Yeah, the core of the algorithm is a two-level bitmap based construct 
that is used for quickly finding the right "bin" of memory blocks; 
the one that's most likely to give you a suitably sized block - large 
enough, and usually not too large, forcing you to split it.

However, the actual pool is a separate construct, concisting of a 2D 
array of pointers to LIFO stacks of free blocks. Each block has a 
header struct. (Part of that - the "prev" pointer and a flag field - 
is actually still there in allocated blocks, right before the address 
returned from malloc_ex().)

So, unless I'm missing something, there's no strict relation between 
the TLSF structure and the physical locations of blocks. Physical 
location is only relevant when freeing blocks, which is when the 
allocator checks if the previous and/or next block is free, and if 
so, merges the blocks before throwing the result back in the suitable 
(size dependent) LIFO stack of free blocks.


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

BTW, it does indeed compile and work out of the box on Gentoo/AMD64 
with GCC 4.1.2.


[...]
> > > [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" :-)

Well, I suppose so, but it seems like a different way of adding some 
extra information to the memory block. Basically, you offload it to 
plugins/applications instead of hiding it in the allocator 
internals - which doesn't seem like a big win to me. ;-)


[...]
> > 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?

Yep, 32 bytes, IIRC. (Or was it 16 bytes, before it supported 64 bit 
platforms...?) The fixed size is why you get away with a single LIFO 
stack and no overhead for allocated blocks.

(Well, there *are* ways of doing that for mixed size blocks too, if 
you use some pointer arithmetic - but then it gets *really* tricky, 
if at all possible, to resize the pool dynamically.)


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

Not quite sure in what way it could be of use here, but sure... :-)


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