深入理解计算机系统之实现动态存储分配器Permalink

简介Permalink

本实验需要用 C 语言实现一个动态的存储分配器，也就是你自己版本的 malloc，free，realloc 函数。我们需要修改的唯一文件是 mm.c，包含如下几个需要实现的函数：

int mm_init(void); 在调用 mm_malloc，mm_realloc 或 mm_free 之前，调用 mm_init 进行初始化，正确返回 0
void *mm_malloc(size_t size); 在堆区域分配指定大小的块，分配的空间，返回的指针应该是 8 字节对齐的
void mm_free(void *ptr); 释放指针指向的 block
void *mm_realloc(void *ptr, size_t size) 返回指向一个大小为size的区域指针，满足一下条件

动态内存申请Permalink

使用动态内存分配器，可为在程序运行时确定并申请虚拟内存空间。动态内存分配器管理的区域被称作堆。每个进程的内存分布如下：

动态内存申请器将堆这块区域当作一系列大小不同的块来管理，块或者已分配的，或者是空闲的。

malloc & freePermalink

通常，有关内存管理， Linux 提供的系统调用主要有两种：第一个是 sbrk() 函数：

#include <unistd.h>
// brk的作用是将堆顶指针设置为addr，失败返回0，成功返回1
int brk(const void *addr);
// sbrk的作用是将堆顶指针增加incr个字节，成功返回新的堆顶地址
void *sbrk(intptr_t incr);

第二种方法使用的是 mmap() 函数

#include <sys/mman.h>
// start 指针表示想要映射的内存区域的起始地址，length为映射的大小，prot是保护标志，flags是映射的类型(匿名映射使用MAP_ANONYMOUS参数)，offset是偏移量
void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);
// munmap则是将映射的空间还给操作系统
int munmap(void *start, size_t length);

值得注意的是，mmap() 还有另一个重要的作用就是实现快速的 I/O，它通过直接将文件映射到虚拟内存，可以直接对其进行读写操作，而不需要使用系统调用 read/write，大幅度提高了速度。

但在实际的使用中，我们不可能每次需要内存的时候，都用 sbrk 或 mmap 函数(系统调用速度很慢)，这会大幅度降低我们程序的效率。通常我们采用的是一种类似于缓存的思想：先使用 sbrk 函数向内核索取一大片的内存空间，然后再使用一定的手段对这段空间进行管理。只有当这段空间不够用时，再向内核拿，这样就提高了效率。这也正是 malloc 函数库所起到的作用。

简单来说，malloc 函数主要是通过维护一个空闲列表来实现内存的管理的，具体涉及到的数据结构就是链表。对每一个内存块，我们使用链表将它们串在一起，当需要使用的时候，我们从链表中寻找大小适合的内存块，并且从空闲链表中删除，拿给用户。当用户用完某个内存块的时候，我们就将其重新插入回空闲链表，这样就实现了简单的内存分配和释放。

数据结构Permalink

首先介绍实验中的内存分配块的数据结构，我使用边界标记的堆块的格式区分块的边界。其中，头部 (header) 和脚部 (footer) 分别占 4 字节大小，块地址双字对齐，大小为8的整数倍。这样做的好处是，如果用 32 位来存储块大小，低 3 位肯定都为0，相当于低 3 位可以预留出来，用作指示该块是否是一个空闲块。

块的数据结构确定后，需要一个空闲链表来管理空闲块，参考书本上关于空闲链表的表述，也采用下图方式管理。

具体实现Permalink

宏定义Permalink

对于这个实验来说，良好的宏定义可提高编程效率，方便阅读书写代码。下面列出部分关键宏，并加以解释。

#define WSIZE 4             /* Word and header/footer size (bytes) */
#define DSIZE 8             /* Double word size (bytes) */
#define CHUNKSIZE (1<<12)   /* Extend heap by this amount (bytes) */

/* Pack a size and allocated bit into a word */
#define PACK(size,alloc)    ((size) | (alloc))

/* Read and Write a word at address p */
#define GET(p)  (*(unsigned int *)(p))
#define PUT(p,val)  (*(unsigned int *)(p) = (val))

/* Read the size and allocated fields from address p */
#define GET_SIZE(p)  (GET(p) & ~0x7)
#define GET_ALLOC(p)    (GET(p) & 0x1)

/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp)    ((char *)(bp)-WSIZE)
#define FTRP(bp)    ((char *)(bp)+GET_SIZE(HDRP(bp))-DSIZE)

/* Given block ptr bp, compute address of next and prev blocks */
#define NEXT_BLKP(bp)   ((char *)(bp)+GET_SIZE(((char *)(bp)-WSIZE)))
#define PREV_BLKP(bp)   ((char *)(bp)-GET_SIZE(((char *)(bp)-DSIZE)))

GET 宏读取和返回指针 p 的引用，这里强制转换是非常重要的，类似地，PUT 宏将 val 存放到 p 指向的字中。GET_SIZE 宏和 GET_ALLOC 宏从 p 处的获得块的大小和分配标识位，注意到，这里的指针 p 应该指向整个块。

之后的指针 bp 指向的就是块的有效负载。HDRP 宏和 FTRP 宏分别指向这个块的头部和脚部，因为有效载荷紧挨着头部，头部大小为 4 字节，所以 (char *)bp-WSIZE 就是指向头部，脚部大小也是 4 字节，且 GET_SIZE 宏指的是整个块大小，因此要减去 8 个字节才是指到了脚部。而对于 NEXT_BLKP 宏和 PREV_BLKP 宏，情况更加复杂，程序需要读到上个块（下个块）的脚部（头部），才能通过加上块大小偏移量来获得下一个块的指针。

创建空闲块链表Permalink

在调用 mm_malloc 和 mm_free 函数之前，必须要调用 mm_init 进行初始化。mm_init 函数创建了一个空的空闲块链表，然后调用 extend_heap 函数，做最初的堆空间扩展。

参见上图空闲链表，mm_init 首先创建了一个不使用的填充字，然后创建 8 个字节的序言块，它只有头部和脚部，但它永不释放，类似于实现单链表时的链表头。最后创建一个结尾块，用于标识空闲链表的结束。加上了填充块后，开头的这几个块一共占用 16 个字节，正好是空闲链表所要求的的最小字节。

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

static void *extend_heap(size_t words) {
    char *bp;
    size_t size;

    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size)) == (void *)-1)
        return NULL;

    PUT(HDRP(bp), PACK(size, 0));           /* header */
    PUT(FTRP(bp), PACK(size, 0));           /* footer */
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));   /* New epilogue header */

    return coalesce(bp);
}

其中 extend_heap() 函数用于堆拓展，每次拓展的大小都应该为 8 的倍数。在拓展完成后，需要注意到，如果堆顶端是一个空闲块，那么就需要调用 coalesce() 函数将空闲块合并。

合并块Permalink

coalesce() 函数是对书上所述的合并块方式的简单实现。注意到，引入序言块和结尾块的好处就是，我们可以少考虑一些复杂的边界情况，因为所有要处理的块都位于链表的“中间”。这样做可以减少编码复杂度，更不容易出错。然后，宏定义也帮助我们很多。比如获取上一个块（下一个块）的分配位和大小时，只需要使用 GET_ALLOC(FTRP(PREV_BLKP(bp))) 即可，代码更具可读性（虽然好像还是很麻烦）。

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){
        	size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
            PUT(HDRP(bp), PACK(size,0));
            PUT(FTRP(bp), PACK(size,0));
    }
    // 合并上块
    else if(!prev_alloc && next_alloc){
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp),PACK(size,0));
        PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));
        bp = PREV_BLKP(bp);
    }
    // 合并上下块
    else {
        size +=GET_SIZE(FTRP(NEXT_BLKP(bp)))+ GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(NEXT_BLKP(bp)),PACK(size,0));
        PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));
        bp = PREV_BLKP(bp);
    }
    return bp;
}

除了之前提到的，在 extend_heap 函数中需要调用 coalesce 函数来合并空闲块，在 mm_free 中也需要调用。事实上，只要有操作可以多出一个空闲块，都需要调用 coalesce 函数来合并。

void mm_free(void *bp) {
    if(bp == 0)
		return;
    
    size_t size = GET_SIZE(HDRP(bp));
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    coalesce(bp);
}

分配块Permalink

使用 mm_malloc 函数来分配块，首先必须要调整分配大小，因为用户传入的数据是有效负荷需要的大小，不包括头部和脚部，而且没有实现 8 字节对齐。因此，必须先加上 8 字节后再对齐，才能进行分配。

调整完后，需要使用 find_fit 函数找到适合的链表空闲块，如果找到了，就放置在空闲块中，如果没有足够大的空闲块，那就需要调用 extend_heap 函数从堆中取出更多的内存了。

void *mm_malloc(size_t size) {
    size_t asize;
    size_t extendsize;
    char *bp;
    if (size == 0)
        return NULL;

    if (size <= DSIZE) {
        asize = 2 * (DSIZE);
    }
    else {
        asize = (DSIZE) * ((size + (DSIZE) + (DSIZE - 1)) / (DSIZE));
    }
    if ((bp = find_fit(asize)) != NULL) {
        place(bp, asize);
        return bp;
    }
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize / WSIZE)) == NULL) {
        return NULL;
    }
    place(bp, asize);
    return bp;
}

对于 find_fit 函数，这里实现的是 first-fit 函数，从链表头开始搜索，只要找到了足够大的空闲块，就返回。

static void *find_fit(size_t size) {
    void *bp;
    for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
        if (!GET_ALLOC(HDRP(bp)) && (size <= GET_SIZE(HDRP(bp)))) {
            return bp;
        }
    }
    return NULL;
}

放置函数 place 实现如下，特别注意，只有剩下的空间多于 16 字节时，才能组成一个空闲块。这意味着较小的碎片已经被我抛弃了。

static void place(void *bp, size_t asize) {
    size_t csize = GET_SIZE(HDRP(bp));
    if ((csize - asize) >= (2 * DSIZE)) {
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(csize - asize, 0));
        PUT(FTRP(bp), PACK(csize - asize, 0));
    }
    else {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

reallocPermalink

最后来关注一下 realloc 函数。这里由于时间关系，先实现了一个初步版本。排除了一些可能的极端情况后，先调用 mm_malloc 函数分配一个新的块。然后，就将旧数据从旧的地址移动到新的地方，并释放旧地址空间。

void *mm_realloc(void *ptr, size_t size) {
    size_t oldsize;
    void *newptr;

    /* If size == 0 then this is just free, and we return NULL. */
    if (size == 0) {
        mm_free(ptr);
        return 0;
    }
    /* If oldptr is NULL, then this is just malloc. */
    if (ptr == NULL) {
        return mm_malloc(size);
    }
    newptr = mm_malloc(size);
    /* If realloc() fails the original block is left untouched  */
    if (!newptr) {
        return 0;
    }
    /* Copy the old data. */
    oldsize = GET_SIZE(HDRP(ptr));
    if (size < oldsize)
        oldsize = size;
    memcpy(newptr, ptr, oldsize);

    /* Free the old block. */
    mm_free(ptr);
    return newptr;
}

事实上，realloc 函数有很多可以优化的点。首先，如果 realloc 传入的 size 比之前还小，显然我们不需要进行拷贝，直接可以考虑对当前块进行分割。其次，如果下一块是一个空闲块的话，我们可以直接将其占用。这样的话可以很大程度上减少外部碎片，充分地利用了空闲的块。接着，如果下一个块恰好是堆顶，我们也可以考虑直接拓展堆，这样的话就可以避免再去搜索空闲链表，提高效率。

实验结果Permalink

由于时间关系，本次实验仅仅实现了一个非常简陋的 malloc 版本，因此得分较低。

深入理解计算机系统之动态存储分配器实现

深入理解计算机系统之实现动态存储分配器Permalink

简介Permalink

动态内存申请Permalink

malloc & freePermalink

数据结构Permalink

具体实现Permalink

宏定义Permalink

创建空闲块链表Permalink

合并块Permalink

分配块Permalink

reallocPermalink

实验结果Permalink

Recommend

Side project retro in 2019 and future plan

充电桩利好频出，售后宝助力挚达科技以服务为动力，蓄能飞驰！

速览WETV流媒体出海产品

MIT researchers develop a paper thin loudspeaker

GitHub - githubtraining/merge-conflict-template-repo: Template repo for Learning...

LinkedIn Publishes New Guide on How to Make Best Use of its Lead Gen Form Ads

Scrambled eggs on toast

Web实战·方糖简历原生PHP版本

加密艺术复兴，NFT 真的「破圈」了吗？

Amazon State Language

About Joyk