Posted on 2009-09-27 14:50
浩毛 閱讀(6399)
評論(5) 編輯 收藏 引用 所屬分類:
C & C++
上一篇內存池的實現其實更像一個后備列表的實現。使用上來說不是很方便，要申請的內存塊是一個BLOCK結構的一個個成員，而且每次從系統內存堆中申請都是一小塊一小塊，也沒有考慮字節對齊。因此讓我們來看看新的一個內存池的實現吧。
這個內存池是根據《c++應用程序性能優化》書里的固定尺寸的內存池原理做了一些改動用C語言寫的。大家有興趣可以去看看，里面說的最詳細。
簡單說下這個內存池的原理，內存池里由N個memblock以一個雙向鏈表組成，每個memblock的組成是一個HEAD塊+M個固定長度的memchunk組成，memchunk就是你將來要從池中申請的內存塊。
我們來看下如下幾個情況：
1.內存池初始化后，內存池的memblock鏈表頭是NULL。
2.第一次從池中申請一個memchunk，內存池根據initsize和chunksize從系統內存堆中申請一個（memblock head）+ chunksize*initsize的內存塊，對block head部分數據字段進行初始化，并將每個chunk的頭4個字節來存放該memblock里下個可用chunk的編號，因為是固定長度的chunk，所以，可以很容易根據編號和chunk長度計算出chunk的地址。創建了memblock后，將第一個chunk (設為A) 返回給用戶，并將block head的first字段設置為chunk A頭4個字節的值（也就是下個可用chunk編號）。同時將創建的block加入到鏈表頭中。
3.下次申請memchunk的時候，遍歷鏈表，找出有空閑chunk的BLOCK，對BLOCK進行和第一次申請時類似的處理。
同時檢查該BLOCK里還有多余的空閑chunk不，有的話就將該block移動到鏈表頭部。以提高下次申請時遍歷鏈表的速度。
如果遍歷完鏈表也沒有找到有空閑chunk的block，就從系統內存堆中申請一個BLOCK,將之加入到鏈表頭。
4.將申請的memchunk （假設為A）歸還給池的時候，遍歷memblock鏈表，根據A的地址來找出A所在的block。
找到后根據這個 memchunk A 的地址計算出它的編號；
將block->first 的編號存入A的頭4個字節中; 將block->first更改為A的編號。（就是chunk的鏈表操作）
最后，將A所在的這個memblock移動到鏈表頭（因為有空閑chunk），以提高申請chunk時的速度。（鏈表只需遍歷一次）。在書中，這里還有個處理：如果該block的chunk都是空閑的，就把block釋放了(歸還給系統內存堆)，我沒有這樣做，打算單獨寫個清理的操作。
大概原理就是這樣，考慮到和64位機兼容，chunk和block都按8字節對齊。代碼中的memheap就是mempool。只是名稱我該成heap了。。
在后面的代碼中，對內存池實現有比較詳細的注釋。
回顧下這個內存池的原理，明顯的優點是減少了內存碎片，字節對齊，但是有個顯而易見的問題是，如果內存池中有大量(成千上萬)個memblock的話，對block的遍歷檢索將是一個性能瓶頸，申請chunk的操作還好點，內部做了一些優化處理，歸還chunk時查找鏈表的速度將比較慢，最壞的情況是有多少個memblock就檢索多少次。。可以考慮對這里做一些檢索上的優化和更改，不用雙向鏈表，用其他方式來做。最簡單的優化就是用游戲粒子系統里普遍使用的一種算法，將有空閑chunk的block放一個鏈表，沒有空閑chunk的block放另外一個鏈表，再做一些分配上的改動，也許能提高一些速度。
mempool.h
/**//*********************************
* mempool
********************************/
#define MEMPOOL_ALIGNMENT 8//兼容64位系統，按8字節對齊
struct memblock
{
uint32_t size;//該Block下chunk內存總長度;
uint32_t free;//空閑chunk數
uint32_t first;//第一個空閑chunk id
uint32_t dumpalign;//按8字節對齊，只是占位用
struct memblock* next_block;//指向下個Block
struct memblock* prev_block;//指向上個Block
char data[1];//chunk區首地址
};
struct memheap
{
struct memblock* block_header;//Block雙向鏈表頭
uint32_t chunk_size;//chunk大小
uint32_t init_size;//第一次創建Block時的chunk數
uint32_t grow_size;//之后創建Block時的chunk數
// uint32_t max_size;//最大memory使用
// uint32_t blocknum;
};
//create and init struct memheap，返回memheap指針
void* memheap_init(uint32_t chunksize,uint32_t initsize,uint32_t growsize);
//destruct memheap
void memheap_dealloc(struct memheap* pool);
//從內存池申請一塊長度為chunk_size的內存
inline
void* memheap_alloc(struct memheap* pool);
//向內存池歸還一塊內存,成功則返回NULL
inline
void* memheap_free(struct memheap* pool,void* p);
//清理內存池多余的內存
void memheap_clean(struct memheap* pool,void* p);
mempool.c
/**//*********************************
* mempool
********************************/
//將一個block從鏈表中移動到首部
#define MEMBLOCK_MOVE_TO_HEAD(HEAD,BLOCK) \
if ((BLOCK) != (HEAD)) { \
struct memblock* prev=(BLOCK)->prev_block; \
struct memblock* next=(BLOCK)->next_block; \
if (prev) prev->next_block=next;\
if (next) next->prev_block=prev;\
(BLOCK)->prev_block=NULL;\
(BLOCK)->next_block=(HEAD);\
(HEAD)->prev_block=(BLOCK); \
(HEAD)=(BLOCK); }
//-----------------declare-----------------
//創建一個Block
static inline void* memblock_create(uint32_t chunksize,uint32_t num);
//------------------implement---------------
static inline void*
memblock_create(uint32_t chunksize,uint32_t num)
{
//memblock長度
uint32_t length=sizeof(struct memblock) -sizeof(char*) + num * chunksize;
struct memblock* block=G_MALLOC(length);
if (block==NULL){
L_WARN("%s,malloc error.",__func__);
return (NULL);
}
block->size=num * chunksize;
block->free=num-1;//因為創建后就分配出去，所以空閑chunk數num-1
block->first=1;//同上，指向第二個chunk
block->next_block=NULL;
block->prev_block=NULL;
//初始化chunk編號，每個chunk頭4個字節存放下個可用chunk的編號。
char* offset=block->data;
uint32_t i=num-1;
for (i=1;i<num;i++){
*((uint32_t*)offset)=i;
offset += chunksize;
}
return (block);
}
inline void*
memheap_alloc(struct memheap* pool)
{
struct memblock* block=pool->block_header;
if (block==NULL){
//鏈表頭為空,第一次創建一個Block;并返回該block的第一個chunk
block=memblock_create(pool->chunk_size , pool->init_size);
pool->block_header=block;
return (block->data);
}
//查找有空閑chunk的Block
while (block!=NULL && block->free==0)
block=block->next_block;
if (block){
//找到一塊block，根據block->first計算出空閑chunk的地址
char* mem=block->data + (block->first*pool->chunk_size);
//更改first為找到的chunk的開始4個字節存放的編號
block->first=*((uint32_t*)mem);
block->free--;//空閑chunk數減一
//將有空閑chunk的Block移動到鏈表頭部
if (block!=pool->block_header && block->free>pool->block_header->free) {
MEMBLOCK_MOVE_TO_HEAD(pool->block_header,block)
}
return (mem);//分配出去的chunk的開始4個字節的內容無用了
}
else {
//沒有找到有空閑chunk的block。創建一個Block，并將之加入到鏈表頭
block=memblock_create(pool->chunk_size , pool->grow_size);
block->next_block=pool->block_header;
pool->block_header->prev_block=block;
pool->block_header=block;
return (block->data);
}
}
inline void*
memheap_free(struct memheap* pool,void* p)
{
struct memblock* block=pool->block_header;
//更加p地址值找出p所在的Block
while (block && (p<(void*)block->data ||
p>= (void*)block->data+block->size))
block=block->next_block;
if (block==NULL) {
L_WARN("%s,no memblock find",__func__);
return (p);
}
uint32_t offset=p -(void*) block->data;
#ifndef NDEBUG
//檢查p是否指向一個合法的chunk首地址
// chunk_size肯定是偶數，使用與運算實現取模
// offset % pool->chunk_size
if ((offset & (pool->chunk_size-1))>0) {
L_ERROR("%s,invalid pointer for free.",__func__);
return (p);
}
#endif
//設置Block
block->free++;//空閑chunk數加一
*((uint32_t*)p)=block->first;//修改歸還的chunk的頭4個字節的值
block->first=(uint32_t)(offset/pool->chunk_size);//first指向歸還的chunk
//將Block移動到鏈表頭部
MEMBLOCK_MOVE_TO_HEAD(pool->block_header,block)
return (NULL);
}
void*
memheap_init(uint32_t chunksize,uint32_t initsize,uint32_t growsize)
{
if (!initsize || !growsize) return (NULL);
struct memheap* pool=G_MALLOC(sizeof(struct memheap));
//保證chunk size最小能存放一個uint32_t大小的數
if (chunksize<sizeof(uint32_t)) chunksize=sizeof(uint32_t);
//更改chunk size字節對齊(8字節)
pool->chunk_size=(chunksize+(MEMPOOL_ALIGNMENT-1)) & ~(MEMPOOL_ALIGNMENT-1);
pool->block_header=NULL;
pool->init_size=initsize;
pool->grow_size=growsize;
// pool->max_size=0;
// pool->blocknum=0;
return (pool);
}
void
memheap_dealloc(struct memheap* pool)
{
struct memblock* block=pool->block_header;
struct memblock* temp=NULL;
while (block){
temp=block;
block=block->next_block;
G_FREE(temp);
}
G_FREE(pool);
}