浩毛的博客

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

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

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

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

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

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

mempool.h

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

struct memblock
{
    uint32_t        size;//該Block下chunk內(nèi)存總長(zhǎng)度;
    uint32_t        free;//空閑chunk數(shù)
    uint32_t        first;//第一個(gè)空閑chunk id
    uint32_t        dumpalign;//按8字節(jié)對(duì)齊，只是占位用
    struct memblock*    next_block;//指向下個(gè)Block
    struct memblock*    prev_block;//指向上個(gè)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時(shí)的chunk數(shù)
    uint32_t        grow_size;//之后創(chuàng)建Block時(shí)的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)存池申請(qǐng)一塊長(zhǎng)度為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
 ********************************/
//將一個(gè)block從鏈表中移動(dòng)到首部
#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)建一個(gè)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長(zhǎng)度 
    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;//因?yàn)閯?chuàng)建后就分配出去，所以空閑chunk數(shù)num-1
    block->first=1;//同上，指向第二個(gè)chunk
    block->next_block=NULL;
    block->prev_block=NULL;
   
    //初始化chunk編號(hào)，每個(gè)chunk頭4個(gè)字節(jié)存放下個(gè)可用chunk的編號(hào)。
    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)建一個(gè)Block;并返回該block的第一個(gè)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計(jì)算出空閑chunk的地址
    char* mem=block->data + (block->first*pool->chunk_size);
    //更改first為找到的chunk的開始4個(gè)字節(jié)存放的編號(hào)
    block->first=*((uint32_t*)mem);
    block->free--;//空閑chunk數(shù)減一
    //將有空閑chunk的Block移動(dòng)到鏈表頭部
    if (block!=pool->block_header && block->free>pool->block_header->free) {
        MEMBLOCK_MOVE_TO_HEAD(pool->block_header,block)  
    }
    
    return (mem);//分配出去的chunk的開始4個(gè)字節(jié)的內(nèi)容無用了
    }
    else {
    //沒有找到有空閑chunk的block。創(chuàng)建一個(gè)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是否指向一個(gè)合法的chunk首地址 
    // chunk_size肯定是偶數(shù)，使用與運(yùn)算實(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個(gè)字節(jié)的值
    block->first=(uint32_t)(offset/pool->chunk_size);//first指向歸還的chunk

    //將Block移動(dòng)到鏈表頭部
    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最小能存放一個(gè)uint32_t大小的數(shù)
    if (chunksize<sizeof(uint32_t)) chunksize=sizeof(uint32_t);
    //更改chunk size字節(jié)對(duì)齊(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);
}