Please advise.


 I've implemented chunked MemPools, split it into lib/MemPool.c and

 src/MemPoolStats.c. So mempools can now be used in under lib/ also.


 Description:

 Mempools are mallocing memory from system in chunks instead of per

 each individual item. Chunk size is determined at runtime, based on

 item size, with some heuristics to find optimal chunk size for a pool.

 Minimum of 32 items must fit into single chunk, but chunk size must

 not exceed 256K. Max number of items per chunk are limited to 64K 

 (usually much less). Special api call is added to allow coders to

 hint optimal chunk size after mempool creation and first use. This

 allows huge users of pools to have less chunks and more items per

 chunk.


 Each Pool has its own linklist of chunks, and each pools has its

 own chunk parameters.


 No separate freelist is kept, free items are placed into chunk data

 area in a linklist node manner, inside freed items themselves. At

 chunk create time, all the items are inited into sequential linklist

 with first item pointed at by chunk's freelist pointer.

 When alloc is requested, first item pointed by *freelist is returned,

 and next item pointed to by that item is placed into *freelist.

 Thus allocation is fast and freelist is maintaned consistently.

 When Free is called, item is zeroed and is inserted into freelist

 by making item's first word to point at *freelist and making *freelist

 point at this freed item. So Free() is also fast. Freed() item is

 checked to belong to the chunk by making sure its pointer is within

 bounds of a chunk. If no allocated chunk accepts the item, then we

 have determined a free to a wrong pool or unallocated item.


 Each new chunk is created on demand, when all chunks are full.

 New chunk is inserted into linklist of chunks so that chunks with

 lower ram pointers are used before chunks in higher ram. This helps

 to keep higher ram free. Chunk refernce time is noted, and periodically

 cleanup handler is called, which checks all chunks that are fully free

 and unreferenced for some time, and returns those to the system.

 So, excessive idle ram is returned to the system some time after a

 spike of ram allocation. When mempool idle limit is exceeded, each chunk

 that becomes free is immediately considered to be returned to the OS.

 Thus we can maintain mem_idle_limit as well.


 I've also implemented chunk fragmentation estimation, whch can be seen

 in cachemgr (how many chunk are locked vs. how many chunk needed).

 So far, fragmentation has been pretty low.



 Problem I ask advice for.

 The problem is with robustness of mempools to misuse of freed items.

 libmalloc's free() is probably immune to multiple free() calls for

 the same item, as long as freed memory has not been given to some

 other caller. In my design, as freelist is kept as linklist,

 1) multiple Frees on the same item corrupts freelist consistency.

 2) If item is tampered with after Free(), chunk's freelist can also

    get corrupted.


 (1) is an issue with current mempool implementation also.

 (2) is something that current mempool tolerates better.


 We can add checks to make sure that freelist is not tampered with and

 that same item is freed only once, but this adds quite some overhead

 for each allocation. (for million-item pools, the overhead is huge)


 So I ask: is it ok to live with (2) and make it responsibility of a

 coder to make sure and track misuse of freed items, or should I drop

 the idea of keeping zero-ram-overhead freelist inside freed items?

 I'd rather not drop the free listnode approach, as it conserves

 quite alot of memory (or cpu overhead, if using bitmaps).


 Please comment.



 Also, is this mempool rewrite potential candidate to be included

 in 2.4 release or should it wait? Is it interesting at all?


<color><param>0100,0100,0100</param>------- Forwarded message follows -------

</color>From:           	<color><param>0000,0000,8000</param>"Andres Kroonmaa" <<andre@online.ee></color>

Organization:   	<color><param>0000,0000,8000</param>MicroLink Online</color>

To:             	<color><param>0000,0000,8000</param>Henrik Nordstrom <<hno@hem.passagen.se></color>

Date sent:      	<color><param>0000,0000,8000</param>Tue, 7 Nov 2000 22:54:22 +0200</color>

<bold>Subject:        	<color><param>0000,0000,8000</param>Re: MemPools rewrite</bold></color>

Copies to:      	<color><param>0000,0000,8000</param>squid-dev@squid-cache.org</color>

Priority:       	<color><param>0000,0000,8000</param>normal</color>


<underline><color><param>0000,8000,0000</param>[ Double-click this line for list subscription options ]</underline></color> 


On 19 Oct 2000, at 21:35, Henrik Nordstrom <<hno@hem.passagen.se> wrote:


<color><param>7F00,0000,0000</param>> Andres Kroonmaa wrote:

> 

> > both current and proposed memPools keep track of freelist with an

> > array of pointers. I guess this is done to increase the speed of

> > allocs/frees, but has quite large memory overhead for allocation

> > sizes comparable to size of pointer. On 64-bit systems pointers

> > are 8-bytes...

> 

> Which can quite easily be addressed by using the object as the list

> node. However, that makes the pool very sensitive to misuse after free..


</color> seems that I've hit exactly this issue.

 Now I wonder how should I handle it in mempools: try detect and crash,

 or try to make pool resistant to this issue. one would need cpu overhead,

 other would need to keep freelist separate, ie. memory overhead.


<color><param>7F00,0000,0000</param>> > In chunked design, it is possible to keep track of freelist with

> > bit-arrays.

> 

> In a list design you don't even need the bitmap.


</color> bitmap is looking attractive again...




------------------------------------
 Andres Kroonmaa <andre@online.ee>
 Delfi Online
 Tel: 6501 731, Fax: 6501 708
 Pärnu mnt. 158, Tallinn,
 11317 Estonia