浩毛的博客

    上一篇內(nèi)存池的實現(xiàn)其實更像一個后備列表的實現(xiàn)。使用上來說不是很方便，要申請的內(nèi)存塊是一個BLOCK結(jié)構(gòu)的一個個成員，而且每次從系統(tǒng)內(nèi)存堆中申請都是一小塊一小塊，也沒有考慮字節(jié)對齊。因此讓我們來看看新的一個內(nèi)存池的實現(xiàn)吧。
    這個內(nèi)存池是根據(jù)《c++應(yīng)用程序性能優(yōu)化》書里的固定尺寸的內(nèi)存池原理做了一些改動用C語言寫的。大家有興趣可以去看看，里面說的最詳細(xì)。
    簡單說下這個內(nèi)存池的原理，內(nèi)存池里由N個memblock以一個雙向鏈表組成，每個memblock的組成是一個HEAD塊+M個固定長度的memchunk組成，memchunk就是你將來要從池中申請的內(nèi)存塊。
    我們來看下如下幾個情況：

    1.內(nèi)存池初始化后，內(nèi)存池的memblock鏈表頭是NULL。

    2.第一次從池中申請一個memchunk，內(nèi)存池根據(jù)initsize和chunksize從系統(tǒng)內(nèi)存堆中申請一個（memblock head）+ chunksize*initsize的內(nèi)存塊，對block head部分?jǐn)?shù)據(jù)字段進(jìn)行初始化，并將每個chunk的頭4個字節(jié)來存放該memblock里下個可用chunk的編號，因為是固定長度的chunk，所以，可以很容易根據(jù)編號和chunk長度計算出chunk的地址。創(chuàng)建了memblock后，將第一個chunk (設(shè)為A) 返回給用戶，并將block head的first字段設(shè)置為chunk A頭4個字節(jié)的值（也就是下個可用chunk編號）。同時將創(chuàng)建的block加入到鏈表頭中。

    3.下次申請memchunk的時候，遍歷鏈表，找出有空閑chunk的BLOCK，對BLOCK進(jìn)行和第一次申請時類似的處理。
同時檢查該BLOCK里還有多余的空閑chunk不，有的話就將該block移動到鏈表頭部。以提高下次申請時遍歷鏈表的速度。
如果遍歷完鏈表也沒有找到有空閑chunk的block，就從系統(tǒng)內(nèi)存堆中申請一個BLOCK,將之加入到鏈表頭。

     4.將申請的memchunk （假設(shè)為A）歸還給池的時候，遍歷memblock鏈表，根據(jù)A的地址來找出A所在的block。
      找到后根據(jù)這個 memchunk A 的地址計算出它的編號；
      將block->first 的編號存入A的頭4個字節(jié)中; 將block->first更改為A的編號。（就是chunk的鏈表操作）
      最后，將A所在的這個memblock移動到鏈表頭（因為有空閑chunk），以提高申請chunk時的速度。（鏈表只需遍歷一次）。在書中，這里還有個處理：如果該block的chunk都是空閑的，就把block釋放了(歸還給系統(tǒng)內(nèi)存堆)，我沒有這樣做，打算單獨寫個清理的操作。
      
      大概原理就是這樣，考慮到和64位機兼容，chunk和block都按8字節(jié)對齊。代碼中的memheap就是mempool。只是名稱我該成heap了。。
      在后面的代碼中，對內(nèi)存池實現(xiàn)有比較詳細(xì)的注釋。

      回顧下這個內(nèi)存池的原理，明顯的優(yōu)點是減少了內(nèi)存碎片，字節(jié)對齊，但是有個顯而易見的問題是，如果內(nèi)存池中有大量(成千上萬)個memblock的話，對block的遍歷檢索將是一個性能瓶頸，申請chunk的操作還好點，內(nèi)部做了一些優(yōu)化處理，歸還chunk時查找鏈表的速度將比較慢，最壞的情況是有多少個memblock就檢索多少次。。可以考慮對這里做一些檢索上的優(yōu)化和更改，不用雙向鏈表，用其他方式來做。最簡單的優(yōu)化就是用游戲粒子系統(tǒng)里普遍使用的一種算法，將有空閑chunk的block放一個鏈表，沒有空閑chunk的block放另外一個鏈表，再做一些分配上的改動，也許能提高一些速度。

mempool.h

/**//*********************************
 * mempool
 ********************************/
#define MEMPOOL_ALIGNMENT 8//兼容64位系統(tǒng)，按8字節(jié)對齊

struct memblock
{
    uint32_t        size;//該Block下chunk內(nèi)存總長度;
    uint32_t        free;//空閑chunk數(shù)
    uint32_t        first;//第一個空閑chunk id
    uint32_t        dumpalign;//按8字節(jié)對齊，只是占位用
    struct memblock*    next_block;//指向下個Block
    struct memblock*    prev_block;//指向上個Block
    char        data[1];//chunk區(qū)首地址
};

struct memheap
{
    struct memblock*    block_header;//Block雙向鏈表頭
    uint32_t        chunk_size;//chunk大小
    uint32_t        init_size;//第一次創(chuàng)建Block時的chunk數(shù)
    uint32_t        grow_size;//之后創(chuàng)建Block時的chunk數(shù)
  //  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);

//從內(nèi)存池申請一塊長度為chunk_size的內(nèi)存
inline
void*    memheap_alloc(struct memheap* pool);

//向內(nèi)存池歸還一塊內(nèi)存,成功則返回NULL  
inline 
void*    memheap_free(struct memheap* pool,void* p);

//清理內(nèi)存池多余的內(nèi)存
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-----------------
//創(chuàng)建一個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;//因為創(chuàng)建后就分配出去，所以空閑chunk數(shù)num-1
    block->first=1;//同上，指向第二個chunk
    block->next_block=NULL;
    block->prev_block=NULL;
   
    //初始化chunk編號，每個chunk頭4個字節(jié)存放下個可用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){
    //鏈表頭為空,第一次創(chuàng)建一個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，根據(jù)block->first計算出空閑chunk的地址
    char* mem=block->data + (block->first*pool->chunk_size);
    //更改first為找到的chunk的開始4個字節(jié)存放的編號
    block->first=*((uint32_t*)mem);
    block->free--;//空閑chunk數(shù)減一
    //將有空閑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個字節(jié)的內(nèi)容無用了
    }
    else {
    //沒有找到有空閑chunk的block。創(chuàng)建一個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肯定是偶數(shù)，使用與運算實現(xiàn)取模
    // offset % pool->chunk_size
    if ((offset & (pool->chunk_size-1))>0) {    
    L_ERROR("%s,invalid pointer for free.",__func__);
    return (p);
    }
#endif
    //設(shè)置Block
    block->free++;//空閑chunk數(shù)加一
    *((uint32_t*)p)=block->first;//修改歸還的chunk的頭4個字節(jié)的值
    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大小的數(shù)
    if (chunksize<sizeof(uint32_t)) chunksize=sizeof(uint32_t);
    //更改chunk size字節(jié)對齊(8字節(jié))
    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);
}