OldJiang.com

浩毛的博客

OldJiang.com
posts - 14, comments - 81, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

一个简单实用的内存池实现之二 (C实现)

Posted on 2009-09-27 14:50 浩毛 阅读(6182) 评论(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
=-(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);
}

Feedback

# re: 一个简单实用的内存池实现之二 (C实现)[未登录]  回复  更多评论   

2009-09-27 19:35 by kkk
举个范例就更好了
不知道我是不是太傻了

# re: 一个简单实用的内存池实现之二 (C实现)  回复  更多评论   

2009-09-27 20:59 by 浩毛
C++ 应用程序性能优化,第 6 章:内存池
http://www.ibm.com/developerworks/cn/linux/l-cn-ppp/index6.html

# re: 一个简单实用的内存池实现之二 (C实现)[未登录]  回复  更多评论   

2009-09-30 12:51 by megax
>有的话就将该block移动到链表头部。以提高下次申请时遍历链表的速度。
直接一个指针保存最后一次分配的block不就行了?loki里面有个内存池,非常非常棒。

# re: 一个简单实用的内存池实现之二 (C实现)  回复  更多评论   

2009-10-02 22:37 by 凡客诚品
loki里面有个内存池,非常非常棒

# re: 一个简单实用的内存池实现之二 (C实现)[未登录]  回复  更多评论   

2010-07-06 00:39 by Lu
请问博主怎么实现代码折叠的功能呢?

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


OldJiang.com