httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Stanley Gambarin <stanl...@cs.bu.edu>
Subject Re: Making pool allocation functions smarter
Date Thu, 26 Jun 1997 15:38:32 GMT


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.


Mime
View raw message