2019-08-22

如何用Cpp实现一个内存池

文章目录

1. 简单设计
2. 注释版代码
3. 问题记录
4. 参考

当需要频繁的进行new和delete操作时，可能会导致产生很多内存碎片。
所以用一个内存池来对这些空间进行管理，可以有效地提高内存利用率。
另外也可以用内存池和placement new来一块使用。
在STL中也有一个内存池的实现，还是非常巧妙的。在此学习并模仿着写一个。

简单设计

用户申请的内存可能很小，可能很大，SGI STL中的做法是以128byte为分界线，分两种情况来处理，大于128byte的直接调用系统的malloc和free，小于128byte的统一用内存池来管理。
因为内存碎片主要是由于小块内存分割了大块内存导致的，所以把小块内存统一管理就够了。
我们把处理大于128的叫做一级空间配置器，小于128的叫做二级配置器。

先看一级配置器，将其看成一个黑盒子的话，它需要给调用者提供这样几个接口：

allocate 分配内存
deallocate 回收内存
reallocate 重新分配内存
set_new_handler 用来处理内存不足的情况(二级配置器中不用再定义此函数，转来调用这个就好)

一级配置器内部还得实现这样几个函数

1
2
3

oom_malloc malloc内存失败时的处理函数
oom_realloc realloc内存失败时的处理函数
__malloc_alloc_oom_handler 用户给制定的处理函数。

二级配置器也得有下面几个public函数

1
2
3

allocate 分配内存
deallocate 回收内存
reallocate 重新分配内存(reallocate首先会试图在原有的内存位置增加或减少内存，若失败则会重新申请一块新的内存并把原有的数据拷贝过去)

二级配置器内部的内存也分为两种，一种是用链表管理起来的，一种是空闲着备用的。所以也需要下面两个函数

1 2	refill 用来把“从空闲内存区申请到的内存”加到链表上 chunk_alloc 负责从空闲内存区取内存的工作，负责内存池最核心的工作

可以多加一个构造函数MemoryPool(size_t n)，用来预先分配一些内存。
二级配置器把内存按照8kb、16kb 24kb…128kb总共16种情况来管理，每种情况都有一个链表结构把相应大小的内存给串起来。

链表采用了下面这种结构，使用union联合体，可以尽可能的节省内存。


union obj{
    union obj *free_list_link;
    char client_data[1];
}
//这种结构的好处是，在内存空闲不用时，就把它当做obj*free_list_link来用，可以让它指向下一块内存，这样就能把空闲内存都串起来
//当内存被申请后，当client_data来对待，可以全部用来储存数据，省去了传统链表所占用的空间，有效地利用了内存。

注释版代码

defaultmalloc.h

#ifndef DEFAULT_MALLOC
#define DEFAULT_MALLOC

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;

//一级配置器，大于128的直接调用malloc和free
class DefaultMalloc{
public:
    static void * allocate(size_t n);
    static void * deallocate(void *p,size_t n);
    static void * reallocate(void *p,size_t old_sz,size_t new_sz);
    static void (*set_malloc_handler(void (*f)()))();
private:
    static void *oom_malloc(size_t n);
    static void *oom_realloc(void *p,size_t n);
    static void (* __malloc_alloc_oom_handler)();
};

//初始化函数指针(static成员变量要在类外初始化)
void (*DefaultMalloc::__malloc_alloc_oom_handler)()=0;

//分配内存，直接调用malloc
void * DefaultMalloc::allocate(size_t n){
    void *result=malloc(n);
    if(result==0) result=oom_malloc(n);
    return result;
}

//释放内存
void * DefaultMalloc::deallocate(void *p,size_t n){
    free(p);
}

//重新分配内存
void * DefaultMalloc::reallocate(void *p,size_t old_sz,size_t new_sz){
    void * result=realloc(p,new_sz);
    if(result==0) result=oom_realloc(p,new_sz);
    return result;
}

//设置内存不在时的处理函数
void (*DefaultMalloc::set_malloc_handler(void (*f)()))(){
    void (*old)()=__malloc_alloc_oom_handler;
    __malloc_alloc_oom_handler=f;
    return old;
}

//malloc失败时调用此函数
void * DefaultMalloc::oom_malloc(size_t n){
    void (*my_malloc_handler)();
    void *result;
    for(;;){
        my_malloc_handler=__malloc_alloc_oom_handler;
        if(my_malloc_handler==0) exit(-1);
        (*my_malloc_handler)();
        result=malloc(n);
        if(result) return result;
    }
}

//realloc失败时调用此函数
void * DefaultMalloc::oom_realloc(void *p,size_t n){
    void (*my_malloc_handler)();
    void *result;
    for(;;){
        my_malloc_handler=__malloc_alloc_oom_handler;
        if(my_malloc_handler==0) exit(-1);
        (*my_malloc_handler)();
        result=realloc(p,n);
        if(result) return result;
    }
    return result;
}

\#endif

memorypool.h

#ifndef MEMORY_POOL
#define MEMORY_POOL
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include "defaultmalloc.h"
using namespace std;

enum{__ALIGN=8};
enum{__MAX_BYTES=128};
enum{__NUM_FREELISTS=16};

//二级配置器，当函数小于128bytes时，使用此类来管理内存
class MemoryPool{
public:
    MemoryPool(){}; //无参构造
    MemoryPool(size_t n); //带参构造，可以先给内存池分配n个bytes
    static void * allocate(size_t n);
    static void deallocate(void *p,size_t n);
    static void * reallocate(void *p,size_t old_sz,size_t new_sz);

private:
    //链表的union，用来串联每块内存
    union obj{
        union obj *free_list_link;
        char data[1];
    };
    //向上取到8的整数倍
    static size_t ROUND_UP(size_t bytes){
        return ( (bytes+__ALIGN-1) & ~(__ALIGN-1) );
    }
    //分了16个规格来管理内存，分别是8 16...128，此函数用来判断此次申请的bytes个字节要到哪个规格的链表去申请内存
    static size_t FREELIST_INDEX(size_t bytes){
        return ( (bytes+__ALIGN-1)/__ALIGN -1 );
    }

    //当链表上的空间不足时，refill会调用chunk_alloc向内存池申请空间，连到链表上
    static void *refill(size_t n);
    //用来向内存池申请空间，执行具体的操作
    static char *chunk_alloc(size_t size,int &objs);//此处要用引用

    //长度为16的数组，每个元素都索引一条链表，用来管理相应大小内存
    static obj * volatile free_list[__NUM_FREELISTS];
    //用来标示内存池的起止位置，这里面是未被链表连起来的内存，链表上的内存不够用时，会从这块内存池中申请内存
    static char *start_free,*end_free;
    //内存池申请到的总空间大小，包括被free_list串起来的。
    static size_t heap_size; 
};

MemoryPool::obj * volatile MemoryPool::free_list[__NUM_FREELISTS]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
char* MemoryPool::start_free=0;
char* MemoryPool::end_free=0;
size_t MemoryPool::heap_size=0;

MemoryPool::MemoryPool(size_t n){
    start_free=(char*)DefaultMalloc::allocate(n);
    end_free=start_free+n;
    heap_size=n;
}

void * MemoryPool::allocate(size_t n){
    obj * volatile * my_free_list;
    obj * result;
    //当申请的内存大于128bytes或小于等于0，直接调用一级配置器，即malloc
    if(n > (size_t)__MAX_BYTES || n<=0){
        return (DefaultMalloc::allocate(n));
    }
    //找到长度为n的内存要从第几个链表上来申请
    my_free_list=free_list+FREELIST_INDEX(n);
    result=*my_free_list;
    //如果链表上没有相应大小的内存了，就调用refill从内存池申请
    if(result==0){
        void *r=refill(ROUND_UP(n));
        return r;
    }
    *my_free_list=result->free_list_link;
    return result;
}

void MemoryPool::deallocate(void *p,size_t n){
    obj * volatile * my_free_list;
    obj *q=(obj*)p;
    if(n > (size_t)__MAX_BYTES || n<=0){
        DefaultMalloc::deallocate(p,n);
        return ;
    }
    my_free_list=free_list+FREELIST_INDEX(n);
    //将p指向的内存归还到相应的链表上
    q->free_list_link=*my_free_list;
    *my_free_list=q;
}

void * MemoryPool::reallocate(void *p,size_t old_sz,size_t new_sz){
    void * result;
    size_t copy_size;
    if(old_sz > (size_t)__MAX_BYTES || new_sz<=0 || old_sz<=0){
        return (DefaultMalloc::reallocate(p,old_sz,new_sz));
    }
    if(ROUND_UP(old_sz) == ROUND_UP(new_sz)) return p;
    result=allocate(new_sz);
    copy_size=new_sz>old_sz ? old_sz : new_sz;
    //申请完新内存之后，把旧地址的数据复制到新地址
    memcpy(result,p,copy_size);
    deallocate(p,old_sz);
    return result;
}

void * MemoryPool::refill(size_t n){
    //默认每次返回20个长度为n的块，其中返回给用户一块，剩下的连到相应大小的链表上。
    int nobjs=20;
    //从内存池中申请20块大小为n的内存。
    char * chunk=chunk_alloc(n,nobjs);
    obj * volatile * my_free_list;
    obj *result,*current_obj,*next_obj;
    //上面chunk_alloc中的nobjs是引用传值，可能会改变nobjs的值。
    if(nobjs==1) return chunk;
    my_free_list=free_list+FREELIST_INDEX(n);
    result=(obj*)chunk;
    *my_free_list=next_obj=(obj*)(chunk+n);
    //把剩余的块都连到链表上
    for(int i=1;;i++){
        current_obj=next_obj;
        next_obj=(obj*)((char*)current_obj+n);
        if((i+1)==nobjs){
            current_obj->free_list_link=0;
            break;
        }else{
            current_obj->free_list_link=next_obj;
        }
    }
    return result;
}
char * MemoryPool::chunk_alloc(size_t size,int &objs){
    char *result;
    //计算要申请到内存总数
    size_t total_bytes=size*objs;
    //计算内存池中未管理的内存还有多少
    size_t bytes_left=end_free-start_free;
    //如果剩余内存足够申请20块内存
    if(bytes_left>=total_bytes){
        result=start_free;
        start_free+=total_bytes;
        return result;
    //如果不够20块，但是能提供一块或以上
    }else if(bytes_left>=size){
        objs=bytes_left/size;
        total_bytes=size*objs;
        result=start_free;
        start_free+=total_bytes;
        return result;
    //如果一块都提供不了，就需要另想办法了
    }else{
        //内存池不够了就从堆中申请，从堆中申请的数量这样计算：
        //要申请的大小的2倍+一个随申请次数增大的值
        //(heap_size一直记录申请内存总数,右移四位相当于除以16，应该是有十六个规格的原因？
        size_t bytes_to_get=total_bytes*2+ROUND_UP(heap_size>>4);
        //如果剩余内存无法提供一块size，但是还剩下一点，就先把这个块内存连到链表上
		//剩下的这点bytes_left应当保证是8的倍数，所以刚开始初始化end_free和start_free时要注意。
        if(bytes_left>0){
            obj * volatile * my_free_list=free_list+FREELIST_INDEX(bytes_left);
            ((obj*)start_free)->free_list_link=*my_free_list;
            *my_free_list=(obj*)start_free;
        }
        //向堆中再申请新的内存
        start_free=(char*)malloc(bytes_to_get);
        //如果堆中内存也没了
        if(0==start_free){
            obj *volatile * my_free_list,*p;
            //再遍历一下链表，看被管理起来的内存中有没有能够本次使用的
            for(int i=size;i<=__MAX_BYTES;i+=__ALIGN){
                my_free_list=free_list+FREELIST_INDEX(i);
                p=*my_free_list;
                if(p!=0){
                    *my_free_list=p->free_list_link;
                    start_free=(char*)p;
                    end_free=start_free+i;
                    //再递归调用自身，看刚回收的那点内存能使用不
                    return chunk_alloc(size,objs);
                }
            }
            end_free=0;
			//最后实在没有了，让malloc再尝试一下。
            start_free=(char*)DefaultMalloc::allocate(bytes_to_get);
        }
        heap_size+=bytes_to_get;
        end_free=start_free+bytes_to_get;
        //如果从堆中申请到了内存，再递归调用自身
        return chunk_alloc(size,objs);
    }
}
\#endif

test.cpp

#include <iostream>
#include <cstdlib>
#include <vector>
#include <ctime>
#include "memorypool.h"
using namespace std;
//#define USEPOOL

int main(){
    MemoryPool pool(10);
    clock_t start,end;
    int sum=0;
    vector<int> randnum(20005);
    for(int i=0;i<20000;i++){
        randnum[i]=rand()%128;
    }

#ifdef USEPOOL
    for(int i=0;i<80;i++){
        start=clock();
        for(int i=0;i<20000;i++){
            char *p=(char*)pool.allocate(randnum[i]);

            pool.deallocate(p,randnum[i]);
        }
        end=clock();
        sum+=(end-start);
    }
    cout<<"MemoryPool:20000次申请释放内存(0-128bytes)用时:"<<sum/80<<"毫秒"<<endl;
#else
    sum=0;
    for(int i=0;i<80;i++){
        start=clock();
        for(int i=0;i<20000;i++){
            char *p=(char*)malloc(randnum[i]);
            free(p);
        }
        end=clock();
        sum+=(end-start);
    }
    cout<<"原生api:20000次申请释放内存(0-128bytes)用时:"<<sum/80<<"毫秒"<<endl;

#endif

    return 0;
}

编译运行

1	g++ test.cpp defaultmalloc.h memorypool.h -o test

源码:https://github.com/TWS-YIFEI/MemoryPool

问题记录

memorypool.h文件59行需要加一个ROUND_UP()向上取整！！！
基本按照STL中的空间配置器来实现的，但测试发现不如直接调用malloc和free速度快，是否内存池主要是解决内存碎片的问题，而速度上可能不会带来多大提升?
陈硕观点1：https://www.zhihu.com/question/25254518/answer/30281159 。

陈硕观点2：

我的观点是：一般的 64-bit C/C++ Linux 服务程序现在已经无需关心所谓的“内存碎片问题”了，也不必动不动就要自己去实现内存池，只需要用一个足够好的现代 malloc 实现即可，例如 tcmalloc。这里“一般的服务程序”指的是非内存数据库这种以内存为主要资源的服务程序。另外，我说的服务程序是用户态的进程，不是内核里的东西。

在多线程环境下如何改进
了解一下tcmalloc。

参考

《STL源码剖析》

欢迎与我分享你的看法。
转载请注明出处：http://taowusheng.cn/