10 Nov
2007
10 Nov
'07
5:01 a.m.
2007/11/9, David Olofson <david(a)olofson.net>et>:
Another newbie question: how do you know how much memory you can need
(without user intervention)?
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.
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" :-)
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
On Friday 09 November 2007, Stefano D'Angelo
wrote:
[...]
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.
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. 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. [...]
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".
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. 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 :-\ [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. ;-) [...]
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.
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. 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. :-)