内存分配器详解及Ｃ语言实现

原 作者 李兆龙 | 发表于 | 分类于 2018级

引子
在有些特殊的情况下我们没有办法确定我们程序中要使用的数据大小　但我们又不想一次将数组这种数据结构开的过大　因为我们的内存毕竟是有限的　那该怎么办呢　没错　就是动态内存分配，Ｃ语言中是malloc 与 free Ｃ++中是new 与 delete ，我们还知道动态内存是在堆上分配的，而且是一条链表(怎么样的链表呢　我们后面会说)，底子更好的同学还知道malloc实际上就是调用了mmap函数与sbrk函数，但这两个函数是什么作用， 有在什么时候起作用呢，还有我们的主题　内存分配器。

什么是内存分配器

按照个人理解内存分配器其实就是根据程序的请求在堆内存中已合理的方式返回所请求的内存地址(显然是虚拟地址)

内存分配器的要求

  1. 处理任意请求　对于一个好的内存分配器我们当然要对合理范围之内的请求做出正确的返回值　对于一个错误的请求返回错误(比如请求空间甚至大于虚拟内存的全部->这只是个例子)，
  2. 立即响应请求　为了我们内存利用率的提升我们可以对请求进行阻塞(当有最佳适配是再响应请求)，但作为一个程序员你显然不想看到这一幕，难以想象一个malloc会浪费掉你大量的时间
  3. 只使用堆　我们都知道堆内存存在于数据段上方和共享库的内存映射区域之间　这之间有一大片的对齐空白　可以有效的节省宝贵的栈内存　在栈顶与堆顶之间有一个共享的映射区域　
  4. 对齐　为了cpu的效率　没什么好说的
  5. 不修改已分配的块

内存分配器目标

１. 实现最大的吞吐率　这很好理解　我们当然希望我们可以多次的分配动态内存且效率依旧很高　但要实现最大吞吐率与最大化内存利用率　一般的数据结构可无法完成

２. 最大化内存利用率　我们不希望有多数内存被浪费　这就是我们动态内存分配的初衷　所以在设计过程中减少内存碎片是我们不可忽略的一个点

内存碎片
  1. 外部碎片　我们平时说的内存碎片其实就是外部碎片　我们可以去想象一下　多次的申请内存块必然(不一定)会多次分割（下面会说），比如说我们经过多次分配后我们已映射的堆中剩下一个１６个字节与３２个字节的内存块　而我们申请了一个４８字节的块　当然会申请失败　值得说的是　错误的分配器设计在特定的情况下会导致大量的外部内存碎片
  2. 内部碎片　我们都知道在动态分配内存中有一个最小块的概念　其实就是包括头部标记，尾部标记(可选)，以及有效荷载(不为零，除序言块（开始），和结尾块以外)，为了cpu的效率　我们当然会在不满足最小块的时候进行补齐

解决方法

  1. 数据结构的选择
  • 隐式空闲链表
  • 显式空闲链表
  • 分离空闲链表
  • 分离适配(伙伴系统)

２. 放置策略

  • 首次适配
  • 下一次适配
  • 最优适配

３. 合并策略

  • 边界标记法
  • 边界标记法优化

４. 分割策略

  • 不同数据结构的选择使用的方法不尽相同　但其基本思路大致相同　先切割得到我们需要的大小　再把空闲块剩余大小与最小块进行对比　小于则进行对其(产生内部碎片　没有办法)　大于则把这一块初始化为新的空闲块

我们首先从隐式空闲链表说起
在这里插入图片描述
其实从名字我们就可以知道空闲块是隐式的　也就是空闲链表其实是与非空闲块混合在一起的　我们可以看到一个元素的头部其实是由３２个位四个字节构成的　因为我们需要字节对齐　意味着假设是一个双字八个字节的对齐(本文用到对其皆默认为八位)，也就是后三位对我们来说其实是永远不变的　均为０，这么好的三位浪费岂不暴殄天物，于是我们可以把其当做标记位　与１进行位运算便可以得到标记位，而中间部分则是我们的有效荷载　这样　一个元素的节点就完成了
隐式空闲链表的优点是什么呢
老实说　隐式空闲链表其实并不优秀　因为空闲块与非空闲块混合　意味着我们其实做了很多无用功，它的优点就在于简单

放置策略
其实很好理解　所谓放置就是去在我们的数据中去找到一个可用的数据块

  1. 首次适配　从数据的起始开始寻找，找到后放入　优点在于我们起始其实是一块整的堆内存（是不是与想的不太一样），首次适配使大的内存块保留在后面，缺点也很明显　就是会留下很多外部内存碎片　就隐式空闲链表来说　其实在搜索方面是线性的　这样做会是时间大幅提高
  2. 下一次适配　其实很好想　在一个位置找到匹配后下次也有可能在这个位置或之后找到(大的趋于后方)　下一次适配快于首次适配(不满足所有情况)
  3. 最优适配遍历　找到一个最优情况　时间换空间

合并策略
我们可以去想　如果两个外部碎片相邻　而我们还把其当做两个内存块　岂不是有点蠢，这样其实就有了合并策略　我们前面提到了数据的头部其实是size位和存在位我们可以想想　我们有两个数据块　分别叫做上和下吧　两个都是空闲块　因为size位记录了大小　我们很容易可以从上块的头地址得到下块的头地址　这样我们不就得到了下块的数据了吗　这样就轻松的得到两个数据块合并后的头与尾了　有些同学可能就会问了　那上块上面如果还有一块空的数据块该怎么办呢　好像乍一看如果我们处于上块没有办法合并这三块　其实我们还可以设置一个结尾标记　作为头部的一个拷贝　这样不就解决了吗　这就是边界标记法。

我们刚刚提到了边界标记法的优化　其实很简单　我们可以想　当数据块不为空时尾部标记块是没用的　所以当数据块不为空时我们将尾标记加入有效荷载　节省内存。
１. 推迟合并　等上一段时间统一合并

２. 立即合并　在产生空闲内存块时立即合并　
其实对于这两种方法来说各有好处　立即合并简单明了　有效的防止内存碎片　但是当多次请求一个较小的内存块是容易产生抖动　大幅降低效率(内存的知识里还有什么时候会产生抖动?文末)

分割策略
其实就是上面说的　无非是把多出来的空闲内存块进行合并

显式空闲链表
在这里插入图片描述
与隐式空闲链表相比　就是把空闲内存块单独拿出来　组成一个链表　优点显而易见　就是速度会提升很快　因为减少了很多不必要的遍历　但是相应的　最小内存块中多了两个指针域　会导致更多的内部碎片　
维护链表的两种方法：

1.LIFO 　
相当于一个栈　每次去使用最近放入的数据块　优点很明显　就是释放一个块和合并一个块显然效率很高的

２.按照地址顺序
相比于与LIFO　按照地址顺序的方法要花费时间维护顺序　但其最大的优点就是很好的内存利用率　为什么呢　因为我们之前说过　大块空闲块会趋于后方　因为每次都是从前开始寻找(堆由低地址先高地址扩展)这样就会在前方找到需要的块　也就提高了内存利用率

分离适配
一种十分高效的动态内存分配方法　其实就是一种分离存储方法　每一个空闲链表中的块都是一个大小类　怎么理解这个大小类呢　其实就是一个链表中都是大小相同的块　但是　在这个范围以内都可以进行匹配　比如说　空闲块块为1024 在512-1024这个大小类之间都可以放入　当我们需要请求一块内存的时候　在响应块的空闲链表中进行首次适配　找到后进行分割　把分割的块放入相应链表　同样的　释放时进行合并　把更大的块放入其相应的链表　这样可以保证防止与合并的快速　且内存利用率极高

伙伴系统
一种特殊的分离适配　说实话　第一次看到的时候被震惊了　确实非常巧妙　在特定情况下伙伴系统的　放置　合并　都是常数级　且对内存的利用率高的可怕，但前提也非常苛刻　不具备一般性。
伙伴系统是什么　其实就是分离适配每种大小类都是二的幂　我们所说的特定情况也就是每次申请的块都是二的幂时　为什么这种情况下效率极高呢　首先对于伙伴算法来说　放置的效率一定是极高的　因为我们的每一个块都是二的幂　找到一个大于我们所请求大小的块时都可以进行递归的二分　这很好理解　而我们Linux下i7也最多支持４８位的虚拟地址　意味着在最极端的情况下　放置也是常数级别（４８里还有系统使用的虚拟内存）　个人认为伙伴系统最巧妙的莫过于块的合并　因为每一个块都是由一个比它大一倍的块分割而来　也就是说我们其实在知道一个块的地址时可以算出它的“伙伴”，地址上差一位而已　当发现它的“伙伴”为非空闲块时把此空闲块放入响应链表。
这些意味着在我们请求几乎总接近２的幂时　伙伴系统几乎是完美的，
但是这种条件是很苛刻的　而在一般情况下伙伴系统所产生的内存碎片太多。

一个简易但巧妙的内存分配器实现，源自csapp，但书上解释较少，以我的角度来完全的解析其过程以及附上实现

Ｃ语言实现内存分配器

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<errno.h>

#define WSIZE 8 //双字数对齐 
#define DSIZE 4 //单字数对齐
#define CHUNKSIZE (1<<8) //扩展堆时的扩展的默认大小  
//开小一点当然ok了　如果开太大会导致　gdb运行成功　正常跑程序会失败
#define MAX_HEAP  (1<<12) //模拟虚拟内存大小
#define MAX(x,y) ((x)>(y)?(x):(y))
//因为此内存分配器使用边界分离法 所以第一个define实际是对边界的一个计算 分别为大小位和存在位
#define PACK(size,alloc) ((size)|(alloc)) // 

#define GET(p)     (*(unsigned int *)(p))
#define PUT(p,val) (*(unsigned int *)(p) = (val))//得到地址 从而赋值

//这里的0x7实际上就是后三位的存在位 加上~以后不就是我们的size位了吗 
#define GET_SIZE(p)  (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
//位运算得到的答案其实就是最后一位 就是边界标记上的是否存在

//bp -> block pointer 这两个宏函数通过当前指针位置计算头尾标记起始位
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

//计算next块的头 和prev块的尾
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE))) //加上get
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

static char *mem_heap;    //用一个全局变量来保存堆顶 以便后面的 放置策略可以进行
static char *mem_brk;     //heap 与 brk之间的代表已分配的虚拟内存 brk与max_addr代表未分配的
static char *mem_max_addr;//最大的模拟虚拟内存地址
void *heap_listp;        //序言块与结尾块之间靠序言块那一侧的指针
void *next_listp;         //下一次适配的全局变量

//所使用函数
void men_init();
void *mem_sbrk(int incr);
int mm_init();
static void *extend_heap(size_t word);
void mm_free(void *bp);
static void* coalesce(void *bp);
void *mm_malloc(size_t size);
void *find_fit(size_t size);
void *next_find_fit(size_t size);
void *place(void *bp,size_t size);

/*对我们的三个全局变量赋值　为了更贴近我们的实际　所以有了mem_brk 
因为虚拟内存并不是初始时全部分配的　而是一个区域的集合　也就是按片分配的　
我们可以打开/proc 中任意一个数字目录进入maps目录查看虚拟内存的映射 显然是片状分配的
*/
void men_init()
{
    mem_heap=(char*)malloc(MAX_HEAP);
    mem_brk =(char*)mem_heap;
    mem_max_addr=(char*)(mem_heap+MAX_HEAP); 
}

void *mem_sbrk(int incr)
{
    char *old_brk=mem_brk;
    
    if(incr < 0 || ((mem_brk + incr) > mem_max_addr))
    {
        errno = ENOMEM;
        perror("error:ran out of memory!\n");
        return (void*)-1;
    }
    mem_brk=mem_brk+incr;
    return (void*)old_brk;  //malloc默认返回void类型指针
}

//初始化堆　使其具有堆的头与尾　把这个作为一个范围　头：序言块　　位：结尾块
int mm_init()
{
    if((heap_listp = mem_sbrk(4*WSIZE))==(void*) - 1) //证明虚拟内存不够
    return -1;
    PUT(heap_listp,0);   //内存对齐块　处于堆刚开始时的位置
    PUT(heap_listp+WSIZE,PACK(DSIZE,1)); 
    PUT(heap_listp+2*WSIZE,PACK(DSIZE,1)); 
    //因为是堆的初始化　所以这两个边界标记构成了一个内存块　有效荷载为零
    PUT(heap_listp+3*WSIZE,PACK(0,1));
    //在整个堆里有且只有一个结尾块　很特殊　size位为0 存在位为1

    heap_listp+=(2*WSIZE); 
    next_listp=heap_listp;
    //在序言块之后　结尾块之前　创建一个带空闲块的堆 注意只有一个　意味这堆的初始往往只有一个

    if(extend_heap(CHUNKSIZE/WSIZE)==NULL)
    return -1;
}

static void *extend_heap(size_t word) //一个字四个字节
{
    char *bp;
    size_t size;

    size = (word%2)?((word+1)*WSIZE):(word*WSIZE);//字节对齐
    if(((long)(bp = mem_sbrk(size)))==-1)
    return NULL;   //当请求的内存大于虚拟内存总内存的时候　返回NULL

    PUT(HDRP(bp),PACK(size,0));
    PUT(FTRP(bp),PACK(size,0));  //代表这个大的空闲块大小为size 且为空闲块
    PUT(HDRP(NEXT_BLKP(bp)),PACK(0,1)); //更新结尾块
    return coalesce(bp); //从bp位置可以开始分配内存　把内存块的后面与新分配的内存进行合并
}

void mm_free(void *bp)
{
    size_t size=GET_SIZE(HDRP(bp));

    PUT(HDRP(bp),PACK(size,0));
    PUT(FTRP(bp),PACK(size,0));
    coalesce(bp); //很容易理解　在每次free过后进行内存合并
}

static void* coalesce(void *bp)  //合并
{
    //得到当前块前后块的存在位信息
    size_t prev_alloc=GET_ALLOC(FTRP(PREV_BLKP(bp)));
    size_t next_alloc=GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size=GET_SIZE(HDRP(bp));  //要初始化合并以后的空闲块
    //对四种合并情况进行讨论
    if(prev_alloc && next_alloc)  //不进行合并
    {
        return bp;
    }   
    else if(!prev_alloc && next_alloc) //prev可合并　next不可合并
    {
        size+=GET_SIZE(HDRP(PREV_BLKP(bp)));//这个位置头尾(第二个宏函数)都可以　都是相同的
        PUT(FTRP(bp),PACK(size,0)); //先把本身的尾部标记设置
        PUT(HDRP(PREV_BLKP(bp)),PACK(size,0)); //再把prev的头部标记设置
        bp=PREV_BLKP(bp); //感觉有点问题
    }else if (prev_alloc && !next_alloc) //prev不可合并 next可合并
    {
        size+=GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp),PACK(size,0));
        PUT(FTRP(NEXT_BLKP(bp)),PACK(size,0));
    }else  //均可合并
    {
        size=size+GET_SIZE(HDRP(PREV_BLKP(bp)))+GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(FTRP(NEXT_BLKP(bp)),PACK(size,0));
        PUT(HDRP(PREV_BLKP(bp)),PACK(size,0)); 
        //相当与把三个内存块和成了一个只需要把前面的头　与后面的尾进行设置就好
    }
    return bp;
}

void *mm_malloc(size_t size)
{
    size_t asize;
    size_t extandsizes;
    char *bp;

    if(size==0)
    return NULL;
    else if (size < 2*DSIZE) 
    asize = 2*DSIZE;
    else 
    asize = DSIZE*((size+DSIZE+DSIZE-1)/DSIZE);//进行字节对齐　加上两个标记位　一个为WSIZE

    if((bp=find_fit(asize))!=NULL) //命中　也就是说目前堆中已载入的空闲链表中有一个空闲块大于等于size
    {
        place(bp,asize);
        next_listp=NEXT_BLKP(HDRP(bp)); //更新下一次适配标记位　同下
        return bp;
    }
    extandsizes = MAX(asize,CHUNKSIZE);  //否则就是不命中的情况
    if((bp=extend_heap(extandsizes/DSIZE))==NULL)
    return NULL;   //说明虚拟内存已经消耗殆尽了
    place(bp,asize);//asize个字节 进行内存替换　
    next_listp=NEXT_BLKP(HDRP(bp));
    return bp;
}

void *find_fit(size_t size)
{
    void *bp;  //放置策略为首次适配 因为有序言块　所以从heap_listp开始寻找 而不是mem_heap
    //printf("%d\n",GET_SIZE(HDRP(bp)));
    for(bp = heap_listp;GET_SIZE(HDRP(bp))!=0;bp=NEXT_BLKP(bp)) //终止条件原因是终止块为零
    if(!GET_ALLOC(HDRP(bp)) && GET_SIZE(HDRP(bp))>=size)
    return bp; //找到匹配
    return NULL;
}

void *next_find_fit(size_t size) //放置策略为 下一次放置
{
    void *bp;  //放置策略为首次适配 因为有序言块　所以从heap_listp开始寻找 而不是mem_heap
    //printf("%d\n",GET_SIZE(HDRP(bp)));
    for(bp = next_listp;GET_SIZE(HDRP(bp))!=0;bp=NEXT_BLKP(bp)) //终止条件原因是终止块为零
    if(!GET_ALLOC(HDRP(bp)) && GET_SIZE(HDRP(bp))>=size)
    return bp; //找到匹配
    else
    {
        if(bp=find_fit(size))
        {
            next_listp=NEXT_BLKP(HDRP(bp)); //更新下一次适配位
            return bp;
        }
        return NULL;//从头开始还是没有找到的话进行从新分配块
    }
}

void *place(void *bp,size_t size)
{
    size_t asize=GET_SIZE(HDRP(bp));
    if((asize-size)>=2*DSIZE)//大于最小块 进行分离操作 这也是产生外部内存碎片的原因
    {
        PUT(HDRP(bp),PACK(size,1));
        PUT(FTRP(bp),PACK(size,1));
        *(FTRP(bp)-1)='\0';     //分配一个字符串末尾
        bp=NEXT_BLKP(bp);//头的大小位被设为size 所以bp可定位到
        PUT(HDRP(bp),PACK(asize-size,0));
        PUT(FTRP(bp),PACK(asize-size,0));
    }else
    {
        PUT(HDRP(bp),PACK(asize,1));
        PUT(FTRP(bp),PACK(asize,1));
        *(FTRP(bp)-1)='\0';
    }
}

int main()
{
    men_init(); //初始化虚拟空间
    mm_init();  //初始化堆空间
    //具体的思路是当堆空间不够的时候进行重新分配　当虚拟空间不够的时候进行报错
    char *tmp=(char*)mm_malloc(sizeof(char)*256);
    strcpy(tmp,"hello world!");
    strcat(tmp,"\0");
    printf("::%s\n",tmp);
    size_t bbb = GET_ALLOC(HDRP(tmp));
    mm_free(tmp);
    size_t aaa = GET_ALLOC(HDRP(tmp));
    printf("%s\nend\n",tmp);
    /*可以执行的原因是因为mm_free只是把标记改变而已 
    本质上内存还是在刚开始我们malloc出的那个虚拟空间上 只不过这部分内存现在可以被mm_malloc分配 
    也就是说值可以被改变　其实已经成了一个　假的“空悬指针”　*/
    free(mem_heap); //防止内存泄露　
    //写完这个程序　再看这个系统的free　真是别有一番感觉啊
    return 0;
}

其实内存的分配是可以用伙伴算法来写，那样效率极高，合并的时间复杂度是常数级的，但巧妙之处在于其只需要几个位运算式子就可以完成(内核源码中就是如此)，想要简单的实现过程其实也并不复杂，因为我们不需要像内核代码一样考虑很多隐晦繁杂的情况，但实现过程与这个框架确有些不一样，因为两者可以说不是严格意义上的实现，只是简单的模拟其中的过程而已，有时间会自己用伙伴算法完成一个类似的内存分配器。

参考资料：
Computer Systems:A Programmer’s Perspective