本篇博客主要参考了csapp中9.9节《动态存储器分配》

在前面的博客中介绍了堆块结构及堆中潜在的漏洞类型，但要能深入理解这些内容，了解动态存储器是如何分配/释放堆的就至关重要了，本文就详细地剖析分配器实现的一些基础且核心的部分，并按照书上实现了一个简单原型（见github）。

分配器主要涉及这几个方面：

• 空闲块的组织：如何记录空闲块，空闲块间如何串联起来？
• 放置：malloc时如何选择合适的空闲块来放置要分配的块？
• 分割：将新分配的块放置在某个空闲块了，那该空闲块剩下部分该如何处理？
• 合并：若无法为新请求进行分配了，但堆中存在若干个空闲块，那是否可以将其合并后再分配？这涉及到如何处理一个释放的块？

空闲块组织 —— 隐式空闲链表

如何组织空闲块是这里最核心的问题，因为后面的放置、分割、合并都要取决于空闲块是如何组织的从而决定对应的策略。

首先是块的结构，它最基本的需要有数据区以及存储大小的头部（用来区别块边界），其次为了区分是已分配的还是空闲块还需要有个标志位；

那这样在堆内存空间中就是一个个已分配块和空闲块的序列/数组，这种结构就称为隐式空闲链表。为什么叫隐式呢？因为并没有使用实际的链表数据结构去将空闲块通过next指针连接起来，而是通过块头部的大小字段以及空闲块的标志隐含地连接着的。

放置已分配块

当用户请求k字节的堆块时，分配器如何从空闲链表中选择一个进行分配放置呢？目前有三种放置策略：

• 首次适配：从头搜索空闲链表，选择第一个合适的空闲块
• 下一次适配：从上一次查询结束的地方开始搜索，直到找到第一个合适的
• 最佳适配：检查每个空闲块，选择适合所需请求的最小空闲块

每种策略各有利弊，这里不详细分析，可以参考csapp书上。本文实现的原型是采用的首次适配策略。

#define WSIZE 4             //WORD size
#define DSIZE 8             //Double word size

void *mm_malloc(size_t size) {
    if(size == 0)
        return NULL;

    void *bp;
    //Adjust block size to include overhead and alignment reqs
    size_t asize = DSIZE * ((DSIZE + size + (DSIZE-1)) / DSIZE);

    //Search the free list for a fit
    if((bp = find_fit(asize)) != NULL) {
        place(bp, asize);
        return bp;
    }

    //No fit found. Get more memory and place the block
    size_t extendsize = MAX(asize, CHUNKSIZE);
    if( (bp=extend_heap(extendsize)) == NULL)
        return NULL;
    place(bp, asize);
    return bp;
}

其中：findfit()即为通过某一放置策略来搜索到满足要求的空闲块：若能找到则调用place()放置；若不能找到则调用 extend_heap()去扩展堆（即将brk指针增加一个大数，从而新添了一个大的空闲块，以便之后不断地分配切割），然后直接在扩展堆中放置。

static void *find_fit(size_t asize) {
    //First fit search
    void *bp;
    size_t size;
    for(bp = heap_listp; size = GET_SIZE(HDRP(bp)); bp = NEXT_BP(bp)) {
        if(!GET_ALLOC(HDRP(bp)) && (size >= asize))
            return bp;
    }
    return NULL; //Not fit
}

find_fit()：这里采用的是首次适配策略，因此就是从头顺序遍历空闲堆块，当第一次找到>=申请size的空闲块时即返回。

分割空闲块

由于不同的放置策略选出的空闲块不一定相同，且找到的空闲块的大小也不一定就是请求的大小，因此我们不能直接把整个空闲块都分配出去（很明显降低了存储利用率，但若放置策略选择的块比较合适的话可以这么做），需要对空闲块进行分割。分割的话也比较简单，唯一的原则就是若分割剩下的空闲块还能用于分配的话（至少数据区能存放一个对齐单位的内容），那么我们就分割；否则分割就没有意义，即直接把当前空闲块整体分配出去。

static void place(void *bp, size_t asize) {
    size_t size = GET_SIZE(HDRP(bp));
    if((size - asize) >= 2*DSIZE) { //Need to split
        PUT(HDRP(bp), PACK(asize,1));
        PUT(FTRP(bp), PACK(asize,1));
        bp = NEXT_BP(bp);
        PUT(HDRP(bp), PACK(size-asize,0));
        PUT(FTRP(bp), PACK(size-asize,0));
    }
    else {  //Allocate the whole free chunk
        PUT(HDRP(bp), PACK(size,1));
        PUT(FTRP(bp), PACK(size,1));
    }
}

合并空闲块

前面已经说了，当存在两个相邻的空闲块时，若直接就这么存储的话可能会存在这两个块均不能满足分配请求大小，但两个块大小之和能满足要求的情况，因此为了能够充分利用空闲块，解决假碎片的问题，我们需要将相邻空闲块进行合并。

那么应该何时进行合并呢？目前有2种策略：

• 立即合并：每次一个块被释放时，就合并所有的相邻块（即看它前后块是否可以合并；若可合并再看合并后的前后块是否可以合并；如此反复直到不能合并或到堆内存边界了为止）
• 推迟合并：等到稍晚的时候再合并，例如直到某个分配请求失败后再扫描整个堆合并所有空闲块，然后再分配

立即合并简单明了，可在常数时间内完成，但可能会产生一种形式的抖动，即块被反复地合并，然后马上分割。这里即采用了立即合并的策略，但实际的分配器中通常会选择某种形式的推迟合并。

合并下一个空闲块很容易，直接通过当前块的大小就能找到下一块；但如何合并前一块呢？在目前的模型中只能通过从堆头顺序搜索，直到某一块的下一个块为当前块时结束，这样的话需要的时间就与堆大小呈线性关系了。因此，牛人提出了一种叫做边界标记的方法，即在每个块的结尾处添加一个脚部，它是头部的一个副本（包含块大小和标志位），这样的话要释放的当前块只需访问前面一个字的距离处存储的内容即可找到前一个块的首地址。

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);
}

static void *coalesce(void *bp) {
    int next_alloc = GET_ALLOC(HDRP(NEXT_BP(bp)));
    int prev_alloc = GET_ALLOC(FTRP(PREV_BP(bp)));
    size_t size = GET_SIZE(HDRP(bp));

    if(next_alloc && prev_alloc)
        return bp;

    else if(next_alloc && !prev_alloc) {
        size += GET_SIZE(FTRP(PREV_BP(bp)));
        PUT(HDRP(PREV_BP(bp)), PACK(size,0));
        PUT(FTRP(bp), PACK(size,0));
        bp = PREV_BP(bp);   //block ptr points to the previous block
    }

    else if(!next_alloc && prev_alloc) {
        size += GET_SIZE(HDRP(NEXT_BP(bp)));
        PUT(HDRP(bp), PACK(size,0));
        PUT(FTRP(bp), PACK(size,0));  //Attention! Size of block bp has been changed!
    }

    else {
        size += GET_SIZE(FTRP(PREV_BP(bp))) + GET_SIZE(HDRP(NEXT_BP(bp)));
        PUT(HDRP(PREV_BP(bp)), PACK(size,0));
        PUT(FTRP(NEXT_BP(bp)), PACK(size,0));
        bp = PREV_BP(bp);   //block ptr points to the previous block
    }

    return bp;                                                                          
}

合并的过程就如上面代码所示，分为4种情况，分别对应着前后块是否空闲。这里面主要的就是需要修改合并后块的头部和脚部，即用合并后的大小去填充，同时返回合并后的堆指针。

其实现在的堆结构就是从这种结构改进来的。脚部中的大小信息实际上只对空闲块有用（用于找到空闲块的首地址），对于已分配块只需获取到脚部中的标志位信息，如果已分配的则不合并，因此是不需要大小信息的，所以这个空间对于已分配块来说是浪费掉的。因此是否可以考虑将脚部的4个字节给已分配块存放有效载荷呢？当然是可以的。那其中的分配/释放的标志位存在哪呢？要知道块大小是8字节对齐，因此头部的后3位是空着的，目前已经有一位被用于标记当前块是空闲的还是分配的，那么可以再使用一位来标记上一块是空闲还是分配的，这样的话堆结构就变成了我们所知道的那样：

• footer（若前一块是分配的，则为前一块的数据；若前一块空闲的，则为前一块的大小）

• 4字节的头部（当前块大小、CUR_INUSE、PREV_INUSE）

• 当前块的数据区

再总结下，这里的堆结构是以 (header, data, footer) 为单位考虑的；现在的堆结构是以(footer, header, data) 为单位考虑的，本质上是类似的。

好了，至此为止一个简单的分配器的原型已经出来了，它包括边界标记的堆结构设计、隐式空闲链表的思想、首次适配的放置策略、空闲块的分割、空闲块的立即合并策略。

综合：实现一个简单的分配器

在具体实现部分中，首先为了不干涉已存在的系统层malloc包，我们通过在mem_init()函数里调用malloc()先从实际的堆内存中分配一块大的、双字对齐的空间，之后的操作都在这块堆内存中进行（将我们的分配器和实际的分配器对比考虑，这里的一大块堆内存空间，就对应着实际虚拟地址空间中的整个堆空间）。

#define MAX_HEAP (1<<17)    //0x20000

void mem_init() {
   mem_heap = (char*)malloc(MAX_HEAP);
   mem_brk = mem_heap;
   mem_max_addr = mem_heap+MAX_HEAP;
}

我们将meminit()函数定义在memlib.c文件中，该文件用于提供一个存储器系统模型，那么它还需要能够提供调整brk指针的函数，以供在自定的malloc()函数中使用，即mem_sbrk()：

void *mem_sbrk(int incr) {
    char *old_brk = mem_brk;
    if(incr<0 || mem_brk+incr>mem_max_addr) {
        fprintf(stderr, "ERROR: mem_sbrk failed.\n");
        return (void*)-1;
    }
    mem_brk += incr;
    return (void*)old_brk;
}

分配器包含在源文件mm.c中，用户可以静态链接这个源文件到他们的应用中（即我们后面所使用的测试文件test.c），并使用mm.c提供的外部函数：

• mm_init() 初始化分配器，这里主要在堆的头和尾各设置了1个已分配的边界堆块，用于在合并时不需另外考虑边界条件（若前面/后面是已分配块的话，就不需合并那一侧了）；同时还先初始化了一个大空闲块，以便于后面分配时不断分割（实际堆分配器也是这么做的，只要用户请求大小<132KB，就会先调用sbrk(132KB)来分配一个大空间）
• mm_malloc() 分配函数，上面已经讲过了，即包括如何放置及分割
• mm_free() 释放函数，上面也讲过了，主要涉及如何合并的问题

#define CHUNKSIZE (1<<12)

int mm_init() {
    if((heap_listp = mem_sbrk(4*WSIZE)) == (void*)-1)
       return -1;
    PUT(heap_listp, 0);                           //Aligment padding
    PUT(heap_listp + (1*WSIZE), PACK(DSIZE,1));   //Prologue header
    PUT(heap_listp + (2*WSIZE), PACK(DSIZE,1));   //Prologue footer
    PUT(heap_listp + (3*WSIZE), PACK(0,1));       //Epilogue header
    heap_listp += (2*WSIZE);

    //Extend the empty heap with a free block of CHUNKSIZE bytes
    if(extend_heap(CHUNKSIZE) == NULL)
        return -1;
    return 0;
}

static void *extend_heap(size_t size) {
    char *bp;
    size_t word = size / WSIZE;
    //Allocate an even number of words to maintain alignment
    if(word % 2 == 1)
        size += WSIZE;
    if((long)(bp = (char*)mem_sbrk(size)) == -1)
        return NULL;

    PUT(HDRP(bp), PACK(size,0));            //Current free block header
    PUT(FTRP(bp), PACK(size,0));            //Current free block footer
    PUT(HDRP(NEXT_BP(bp)), PACK(0,1));      //Move epilogue header to the end of heap

    //Coalesce if previous block is free
    return coalesce(bp);
}

测试

这里我写了一个test.c，通过调用mmmalloc()和mm_free()来分配和释放，源码我就不贴了，大家可以去github上看。

编译：gcc -static -m32 test.c memlib.c mm.c -o test

运行：