httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Dean Gaudet <>
Subject Re: Making pool allocation functions smarter
Date Fri, 27 Jun 1997 01:21:01 GMT
On Thu, 26 Jun 1997, Stanley Gambarin wrote:
> 	Note that this approach would provide less fragmentation
> 	(in theory) than the curent one, where the first block of 
> 	suitable size is taken (even though it might be too big, since no
> 	sorting is done on the free list).

I don't have a reference handy, but it's been shown that best fit choice
of memory block doesn't help fragmentation to be worth the effort.
First fit is essentially good enough.  There's a whole lot of research
out there on dealing with pools of memory.

The power-of-2 thing is cute... but doesn't it waste like 1/4 of the RAM
you get from the system?

I think we're getting into some confusion here between the external
structure of the blocks that are carved up to satisfy individual palloc()
requests and the internal structure of the blocks themselves.  Probably
because we're calling the palloc() results blocks as well :)

I don't see much of a reason to change the external structure of the
blocks.  But that's probably because I believe the first-fit heuristic
I mentioned above.  The internal structure should also be kept as it is
for most code.  But some code may want to do pfree() and such, and I'd
prefer that code be required to allocate a subpool to do it in.

I really think you'd be hard pressed to optimize the current alloc.c
system very much.  After all, the most common code path amounts to:

    return_value = p->first_free_byte;
    p->first_free_byte += size;

Everything else is just checking there's room, and if there isn't it
either has to malloc or scan a linked list to find the first fit.

If you add the ability to do free() then you have an internal first-fit
scan as well as a possible external first-fit scan.  In other words
you're always doing a first-fit.  But there's no reason that pools can't
have both techniques, and have it selected at creation time.

It's quite easy to coalesce on free or realloc if your internal structure
uses a doubly linked list.  Each block needs to know its own size, from
which you can derive the next block.  And it needs to know the size
of it's predecessor, from which you derive the ptr to the predecessor.
Blocks are always going to be even sized (due to alignment constraints) so
you've got a bunch of spare bits in the low ends of the sizes, so use
them to indicate if a block is free or allocated.

Coalescing amounts to:  check the next block, if free then coalesce.
Then check the prev block, if free then coalesce.

There are already existing malloc() library implementations that we could
borrow or steal to avoid rewriting them.


View raw message