You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@httpd.apache.org by ra...@bellglobal.com on 1997/06/26 15:43:03 UTC
Making pool allocation functions smarter
Something to think about for 2.0 or even 1.3.
The current palloc mechanism is nice and simple, but not extremely flexible.
We might consider improving this bit of the code in 2.0. One thing that
perhaps goes against the pool-based philosophy, but one that I have wished
for a number of times is a prealloc() function. That is, being able to grow
a chunk of memory obtained from a pool or sub-pool.
This would mean a number of things. First, it effectively means we would need
a pfree() and we would need to be able to keep track of chunks of memory
within each block. Instead of just using up memory at the end of the current
block, we would scan through available free'ed chunks within the blocks and
pick the first that was large enough.
We currently keep a free block list. Each block on this list has a start
pointer, an end pointer and a first available pointer. We check if the
end pointer minus the first available is large enough to hold the requested
size. This mechanism makes sure chunks at the end of each block do not
go completely unused.
Given the fact that we already have this free block mechanism, it is
conceivable that a pfree() would simply convert a chunk that is currently
part of a block and convert the chunk into a separate block and add it to
the free block list.
ie.
A sub-pool at some instant may look like this:
A linked list of blocks where * indicates used memory and - free:
block A block B block C
********--- ******-- ******----
Say we wanted to make a chunk in the middle of block A available again.
ie:
block A block B block C
***---**--- ******-- ******----
This would end up being:
block A block A1 block A2 block B block C
*** --- **--- *****-- ******----
A quick optimization check could be added which in the case where the
first chunk in A2 might get free'ed. block A1 and A2 being contiguous
memory could be collapsed into a single block.
>From a performance point of view, there should be little or no impact.
If pfree() is never called, there is no impact. This doesn't add any
extra checks. If pfree() is called a lot, we could end up with a lot of
fragmentation and thus a lot of small block on the block freelist. Adding
a minimum size before a free'ed chunk can be turned into a separate block
should hopefully take care of that. It's not the little chunks that worry
me anyway. It's the larger chunks I would like to have some way to re-use
without clearing the pool.
Ok, I hope I explained that well enough. It looks like it could be done
cleanly, and it would be a big win in situations where you can't clear a
sub-pool, but you know you are leaving orphan chunks of memory around.
And yes, I am volunteering to write and test this unless there are serious
objections to the concept.
-Rasmus
Re: Making pool allocation functions smarter
Posted by Dean Gaudet <dg...@arctic.org>.
The current code performs extremely well ... because it doesn't allow
realloc or free there is no bookkeeping within a block. For many servers
and modules this is all they need. I'm happy with what you're saying
provided you really can prevent it from costing more unless free/realloc
are used.
In my experience you need to at least store the length of each returned
object s at ((unsigned *)s)[-1], or something like that. You always make
sure an allocation is large enough to fit your free-list structure in it.
And coalescing is an absolute must.
There are some cute tricks you can do when your "input sizes" are random
... tricks looking like skip lists. They might be used in some of the
existing free allocators out there (i.e. gnu, perl, freebsd, linux).
Dean
On Thu, 26 Jun 1997 rasmus@bellglobal.com wrote:
> Something to think about for 2.0 or even 1.3.
>
> The current palloc mechanism is nice and simple, but not extremely flexible.
> We might consider improving this bit of the code in 2.0. One thing that
> perhaps goes against the pool-based philosophy, but one that I have wished
> for a number of times is a prealloc() function. That is, being able to grow
> a chunk of memory obtained from a pool or sub-pool.
>
> This would mean a number of things. First, it effectively means we would need
> a pfree() and we would need to be able to keep track of chunks of memory
> within each block. Instead of just using up memory at the end of the current
> block, we would scan through available free'ed chunks within the blocks and
> pick the first that was large enough.
>
> We currently keep a free block list. Each block on this list has a start
> pointer, an end pointer and a first available pointer. We check if the
> end pointer minus the first available is large enough to hold the requested
> size. This mechanism makes sure chunks at the end of each block do not
> go completely unused.
>
> Given the fact that we already have this free block mechanism, it is
> conceivable that a pfree() would simply convert a chunk that is currently
> part of a block and convert the chunk into a separate block and add it to
> the free block list.
>
> ie.
>
> A sub-pool at some instant may look like this:
>
> A linked list of blocks where * indicates used memory and - free:
>
> block A block B block C
> ********--- ******-- ******----
>
> Say we wanted to make a chunk in the middle of block A available again.
> ie:
>
> block A block B block C
> ***---**--- ******-- ******----
>
> This would end up being:
>
> block A block A1 block A2 block B block C
> *** --- **--- *****-- ******----
>
> A quick optimization check could be added which in the case where the
> first chunk in A2 might get free'ed. block A1 and A2 being contiguous
> memory could be collapsed into a single block.
>
> >From a performance point of view, there should be little or no impact.
> If pfree() is never called, there is no impact. This doesn't add any
> extra checks. If pfree() is called a lot, we could end up with a lot of
> fragmentation and thus a lot of small block on the block freelist. Adding
> a minimum size before a free'ed chunk can be turned into a separate block
> should hopefully take care of that. It's not the little chunks that worry
> me anyway. It's the larger chunks I would like to have some way to re-use
> without clearing the pool.
>
> Ok, I hope I explained that well enough. It looks like it could be done
> cleanly, and it would be a big win in situations where you can't clear a
> sub-pool, but you know you are leaving orphan chunks of memory around.
>
> And yes, I am volunteering to write and test this unless there are serious
> objections to the concept.
>
> -Rasmus
>
Re: Making pool allocation functions smarter
Posted by Dean Gaudet <dg...@arctic.org>.
On Thu, 26 Jun 1997, Ambarish Malpani wrote:
> This simplifies the problem of keeping track of the freed blocks.
> Also allocations can still be very, very fast (because you keep the
> freed blocks as multiple lists, each of a particular size) and it
> works very well in cases where you keep allocating and freeing blocks
> of the same size (most data structures have a fixed size - the
> main place where you have problems is with strings).
I call the fixed-size problem "carving", for no good reason. And I use
special allocators specifically for them called carvers. If you know at
the time you create the pool that all allocations are for a fixed size you
can do far better.
I don't think Apache has many of these though. There's the table_header,
and that's about it for fixed sized, frequently allocated objects. Most
of the objects are strings. For which the size is easy to recalculate,
but I'd personally rather waste the memory than the cpu time. Memory is
usually cheaper.
But I've got code to do this sort of thing, I'll include it with this
message. Ignore the kiwi stuff, that's just the name of my "toolkit"
library.
Dean
Re: Making pool allocation functions smarter
Posted by Ambarish Malpani <am...@isecurity.com>.
Hi Rasmus,
Did something like this in a previous life. The way I did it
was slightly different. Here goes (and some of the reasons why):
Pools are meant to be used where you want to do a bunch of fast
allocations for lots of (mostly) little chunks of memory and where
you know the life of these chunks is limited, so you don't want to
go through a complicated procedure to free all of them - and you
don't want to need to worry about memory leaks.
When you are proposing to keep lists of free memory and allocate
an appropriate buffer from the free list, keep track of the buffer
size, (and potentially merge consecutive freed buffers), you are
doing a lot of the work that malloc does (except that a user
can still free everything at one shot).
What I had done (because it pained me, too, to see these little blocks
of free memory lying around unused ;->), is, I put a restriction
that the pool would NOT try and merge adjacent blocks or do very
complicated things. When you ask a pool for some memory, it will
check its free list for a block of the precise size that you
requested. If it can find one, it will give that back to you. If
it can't, it will behave like its free list was empty and give you
the memory like the pool does today. (no searching for best fits etc.)
Also, because I did not want the memory overhead of keeping track of
the size of pieces allocated from a pool (because people make a lot
of allocations of small pieces), I required a user to specify the
size of the piece he was trying to free and the pool it originally
came from.
This simplifies the problem of keeping track of the freed blocks.
Also allocations can still be very, very fast (because you keep the
freed blocks as multiple lists, each of a particular size) and it
works very well in cases where you keep allocating and freeing blocks
of the same size (most data structures have a fixed size - the
main place where you have problems is with strings).
Unfortunately, I can't give you all the code (since I had done this
work at a previous company and that was all propietary stuff), but
if you and the group is still interested, I know I want to add the
stuff to my own library, so I could develop it again....
Let me know what you think,
A
rasmus@bellglobal.com wrote:
>
> > block A block B block C
> > ***---**--- ******-- ******----
> >
> > block A block A1 block A2 block B block C
> > *** --- **--- *****-- ******----
>
> I guess where the simplicity of my suggested solution falls apart is that
> we do not track the size of individual chunks within a block. I wouldn't
> be able to determine where block A2 should start without adding some
> additional logic and chunk size tracking code.
>
> -Rasmus
--
---------------------------------------------------------------------
Ambarish Malpani
Architect (408) 738-2040
ValiCert, Inc. http://www.valicert.com
333 W. El Camino Real, Suite 270
Sunnyvale, CA 94087
Re: Making pool allocation functions smarter
Posted by Dean Gaudet <dg...@arctic.org>.
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.
Dean
Re: Making pool allocation functions smarter
Posted by Stanley Gambarin <st...@cs.bu.edu>.
On Thu, 26 Jun 1997 rasmus@bellglobal.com wrote:
>
> > block A block B block C
> > ***---**--- ******-- ******----
> >
> > block A block A1 block A2 block B block C
> > *** --- **--- *****-- ******----
>
> I guess where the simplicity of my suggested solution falls apart is that
> we do not track the size of individual chunks within a block. I wouldn't
> be able to determine where block A2 should start without adding some
> additional logic and chunk size tracking code.
>
> -Rasmus
>
I was thinking of the same idea just a week ago. As you have
correctly states, there is a problem with allocation of blocks and
size determination. One possible solution that I was thinking of is as
follows:
- set the minimum size of the block to be N
- user can configure the size of the block that is malloced,
say for example M. (M is a multiple of N).
- allocation is done my malloc(M+sizeof(header)*(M/N)), that is
we create headers for each possible block, even though we have
only one right now. Notice that header is only 12 bytes in the
current implementation and so wasted memory will be insignificant
to the overall block size.
- now, suppose a user requests a chunk of size P. We see how many
N-sized chunks are required and give them to P, marking them as
used in P.
- when freeing, we mark the block as reusable and also since P is
contiguous, if 2 neighboring headers are free, that indicates that
we have 2*N contiguous free memory.
Ideal situation would occur if N and M are the powers of 2. Then,
just for example, let N = 4K and M = 64K. The pool structure
would consists of linked lists of 64K blocks and malloc is called
with size 64K as paramemter. The freelist would actually be an
array of linker lists :
4K 8K 16K 32K 64K,
where each linked list points to the free blocks of the particular
size. 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).
Finally, a separate thread (or function call, or whatever) can
go through and periodically check if any blocks on the free list
can be concatenated together to form a larger block on the
freelist.
Stanley.
P.S. Since powers of 2 are used, most of the computations would
be reduced to shifts (very cheap). Also, above scheme provides
for sorted blocks on the freelist and in consequence less
fragmentation than the current design. Finally, separating
freelist into multiple parts would allow multiple threads
to seach for blocks of the different size in parallel (however
if we do so, we need to provide a mutex per array entry and then
we run into trouble of maxing out the mutexts, but that is
another matter). Finally, Finally: the memory subsystem is one
of the critical ones and thus optimizing the performance would
lead to a faster server overall.
PPS. The above scheme of memory allocation is described by
A. Tanenbaum in the "Modern Operating Systems" as one of the
implementation of virtual memory. Any feedback is greatly
appreciated. If anyone is interested in cooperatively
working on this, please email me, otherwise ignore the message.
Re: Making pool allocation functions smarter
Posted by ra...@bellglobal.com.
> block A block B block C
> ***---**--- ******-- ******----
>
> block A block A1 block A2 block B block C
> *** --- **--- *****-- ******----
I guess where the simplicity of my suggested solution falls apart is that
we do not track the size of individual chunks within a block. I wouldn't
be able to determine where block A2 should start without adding some
additional logic and chunk size tracking code.
-Rasmus