Re: [LAD] LV2 realtime safe memory pool extension

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 --'
_______________________________________________
Linux-audio-dev mailing list
Linux-audio-dev@email-addr-hidden
http://lists.linuxaudio.org/mailman/listinfo/linux-audio-dev
Received on Sat Nov 10 20:15:01 2007