CS:APP Malloc Lab实验

本文是CS:APP学习笔记的一部分：

• Data Lab
• Bomb Lab
• Attack Lab
• Architecture Lab
• Cache Lab
• Shell Lab
• Malloc Lab
• Proxy Lab

相关的代码都放在了GitHub下了：RayZhang13/CSAPP-Labs

关于学习资源和视频等问题可以参考第一次写的Data Lab开头中提及的相关问题。

最近几个星期突击了一下毕业设计和论文，花了不少时间，浪费了不少心情，为了凑字数写了亿句废话。总而言之，一份完美的学术垃圾出炉了，完美的通过了查重审核，就差到时候答辩道歉了😂加油加油

内存管理这块的内容在突击论文前就在看了，都快看完了突然插进来了个论文，也是挺扫兴的。Anyway，现在算是接上了，还补回来了…

这次的实验是Malloc Lab，在本次试验中，我们要自己建立一个动态内存分配方案，也就是自己写一个malloc、free和realloc函数，这次试验需要我们充分发挥想象力，创建一个正确、高效并且快速的分配器。（日常硬核）

准备

对应课程

这次的Malloc Lab作业，如果是自学，在B站课程中，应该大致需要完成P17~P20的学习，也就是书中第9章的内容，大致理解虚拟内存和动态内存分配的相关概念。

P. S. 中间还夹了一个P16，却是系统级I/O的内容… 应该是第10章的，这个顺序有点迷惑，学还是要学的😂保不准以后用得到

课程文件

相关的作业还是在CMU的官网上，相同位置：

Lab Assignments

在Malloc Lab一栏中，我们可以查看相关文件，例如：

• README文档

• Writeup PDF说明材料

• 自学材料 最重要的作业文件Self-Study Handout

下载后并解压的文件如图所示：

使用环境

如下为我的Linux版本和GCC版本：

使用建议

作业区域

作业需要的所有修改和处理都集中在mm.c文件中，这里内部包含了我们的需要完成的多个核心方法：

测试程序

通过mdriver.c我们可以对我们最终完成的代码进行性能的检测，我们可以通过make命令来生成相关的代码。

P. S. 在编译过程中，如果遇到/usr/include/gnu/stubs.h:7:11: fatal error: gnu/stubs-32.h: No such file or directory相关的问题，应该是32位兼容的问题… 目测前往Makefile中，将编译选项中的-m32修改为-m64即可，接下来执行make clean; make即可。

这个mdriver文件的检测行为是由一系列的trace文件所控制的，关于何为trace文件，可以参考在Cache Lab中的相关部分。

在文件夹中，留下了两个示例文件，分别是short1-bal.rep和short2-bal.rep，打开一个观察我们看到：

猜测a和f打头的相关操作代表了分配和释放内存的操作序列…（通过阅读mdriver.c的源程序我们肯定能理解其意图，这也应该是作者本意）

mdriver通过读入一系列的指令序列，以此作为评价标准对我们所写代码进行评价。在此，感谢Ethan-Yan27在GitHub上提供了完善的trace文件用例，下文中我们就使用这些样例，这里我也留一份作为备份可以下载：

mdriver.c的使用有如下参数：

• -t <tracedir>：通过此参数，我们将指定trace文件所在的目录，而非使用默认的文件夹，默认的目录被定义在了config.h中，我们看到有

  #define TRACEDIR "/afs/cs/project/ics2/im/labs/malloclab/traces/"

  显然要么改config.h内部的配置，要么运行的时候自己定义路径… 我们又不是CMU的学生，这些trace文件我们也没有…

• -f <tracefile>：或者我们干脆直接指定某一个trace文件，而非config.h中的记录的默认文件

  #define DEFAULT_TRACEFILES \
    "amptjp-bal.rep",\
    "cccp-bal.rep",\
    "cp-decl-bal.rep",\
    "expr-bal.rep",\
    "coalescing-bal.rep",\
    "random-bal.rep",\
    "random2-bal.rep",\
    "binary-bal.rep",\
    "binary2-bal.rep",\
    "realloc-bal.rep",\
    "realloc2-bal.rep"

• -h：打印命令行参数使用帮助

• -l：同时测试我们的mm_malloc和libc标准库中的对应函数，并进行比较

• -v：在一个紧凑的表格中打印出每个跟踪文件的性能表现

• -V：更多的中间过程输出，在处理每个跟踪文件时打印额外的诊断信息。在调试过程中很有用，我们可以通过打印的信息确定是哪个跟踪文件导致你的malloc失败

杂项

在mm.c中，有一个名字为team的结构体，用于填入个人信息方便老师查看…

/*********************************************************
 * NOTE TO STUDENTS: Before you do anything else, please
 * provide your team information in the following struct.
 ********************************************************/
team_t team = {
    /* Team name */
    "ateam",
    /* First member's full name */
    "Harry Bovik",
    /* First member's email address */
    "bovik@cs.cmu.edu",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""
};

Emmm… 应该和我们没啥大关系，想填一下也没啥，就是调用mdriver.c打印的时候能看到相关内容。

题目

作业要求

主体部分

我们需要实现的函数有如下四个：

int mm_init(void);
void* mm_malloc(size_t size);
void mm_free(void *ptr);
void* mm_realloc(void* ptr, size_t size);

需要指出的是在mm.c文件中，已经预先提供了一个最简单的但是功能正确的malloc方法。在PDF中，作者推荐我们尝试去以此为基础对函数进行修改，使得他们满足如下要求：

• mm_init：在调用 mm_malloc，mm_realloc 或 mm_free 之前，调用 mm_init 进行初始化，正确返回 0，有问题则返回-1

• mm_malloc：在堆区域分配至少size大小的空间，返回的指针应该是 8 字节对齐的。同时确保分配的内存空间不会与其他已分配的内存块重叠

• mm_free：释放ptr所指向的内存块。

• mm_realloc：返回指向一个大小至少为size的区域指针，满足以下条件：

  • 如果ptr为NULL，则调用相当于mm_malloc(size)

  • 如果size大小为0，则调用相当于mm_free(ptr)

  • 如果ptr不为NULL，且ptr为之前某次调用mm_malloc或者mm_realloc返回的指针。本次调用将改变ptr指向的内存块的大小，将其变为size个字节，并返回新内存块的地址。

    P. S. 注意到新内存块的地址可以和旧内存块的地址一致，也可以不同，取决于你的实现、旧内存块内部碎片大小和本次realloc请求的size大小。

    新内存块内部存储的内容应当和旧内存块一致，取决于新旧大小的最小值。

    例如，原来有一个8字节的旧内存块，现在我们将其变为12字节，则有前8字节保持不变而后4字节未初始化。

    或者，原来有一个8字节的旧内存块，现在将其大小变为4字节，则新内存块中的头部4字节应当和旧内存块一致。

内存检查器

除了主要的内存分配器需要我们进行实现之外，我们需要实现内存一致性的检查器。在运行时，该检查器将对整个堆内存空间进行扫描，例如需要检查的问题包括但不限于：

• 是否在空闲列表中的每一个内存块均被标记为空闲状态？
• 是否存在连续的空闲内存块忘记被合并了？
• 空闲列表在每次操作后是否包含了所有的空闲内存块？
• 空闲列表中的指针是否指向了有效的空闲内存块？
• 已分配的内存块之间有没有出现重叠的异常状况？
• 在堆内存块中的指针是否指向了有效的对内存地址？

PDF中希望我们将内存检查器写作int mm_check(void)，一并写在mm.c文件中，并希望当内存通过检查时，该方法返回一个非0值。当内存检查未通过时，也可打印对应的错误信息方便排查。

P. S. 最终对mm.c进行性能测试时，务必将mm_check内存检查器的相关调用加上注释，以避免不必要的性能损失。

理解示例

在默认的示例mm.c程序中，我们被给到了两个功能正确的方法，分别是mm_malloc和mm_realloc。

首先看内部预置的宏定义：

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

可以看到ALIGN(size)目的为将size进行双字对齐操作，而SIZE_T_SIZE进一步使用了此操作，可以认为是代表了内存块头部的大小（内存头部块中主要记录了内存块的大小）。

因此在我们正式计算一个内存块的大小时，应当是头部大小对齐后的值加上有效载荷的大小后再进行对齐的值。在本示例中，分配器实现的更像是一个隐式的空闲链表，如下两图仅供参考（和代码还是有部分出入的），来自于书P592：

接下来我们观察预置的mm_malloc函数：

/*
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */
void *mm_malloc(size_t size) {
    int newsize = ALIGN(size + SIZE_T_SIZE); //需要申请的空间大小
    void *p = mem_sbrk(newsize); //传给mem_sbrk的incr参数，申请扩大堆空间
    if (p == (void *)-1) //申请失败，返回NULL
        return NULL;
    else { //申请成功
        *(size_t *)p = size;  //在内存块头部中写入大小信息
        return (void *)((char *)p + SIZE_T_SIZE); //加上头部大小偏移量，返回指向有效载荷的指针
    }
}

P. S. 可以看到这里面申请的size看起来应该就是有效载荷的大小，并不计入头部块大小等内容，和上文中给出的图还是有一点小出入的，需要注意一下。

由于使用了size_t作为头部块大小的描述方式，在32位系统下为4字节，在64位下应当为8字节，再加上头部和有效载荷均应该是8字节对齐的（第一个内存块的头部是落在堆内存空间的头部，而堆内存空间是通过malloc分配的，自然也应当是8字节对齐的，详情见下文）

也许应该画成下面这个样子比较合适？

有兴趣的话还可以去memlib.c中了解一下mem_sbrk是如何实现的：

/* private variables */
static char *mem_start_brk; /* points to first byte of heap */
static char *mem_brk;       /* points to last byte of heap */
static char *mem_max_addr;  /* largest legal heap address */

/*
 * mem_init - initialize the memory system model
 */
void mem_init(void) {
    /* allocate the storage we will use to model the available VM */
    if ((mem_start_brk = (char *)malloc(MAX_HEAP)) == NULL) {
        fprintf(stderr, "mem_init_vm: malloc error\n");
        exit(1);
    }

    mem_max_addr = mem_start_brk + MAX_HEAP; /* max legal heap address */
    mem_brk = mem_start_brk;                 /* heap is empty initially */
}

/*
 * mem_sbrk - simple model of the sbrk function. Extends the heap
 *    by incr bytes and returns the start address of the new area. In
 *    this model, the heap cannot be shrunk.
 */
void *mem_sbrk(int incr) {
    char *old_brk = mem_brk;

    if ((incr < 0) || ((mem_brk + incr) > mem_max_addr)) { 
      //如果预计修改后的堆内存超过上限或者想要收缩堆大小，则报错
        errno = ENOMEM;
        fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\n");
        return (void *)-1;
    }
    mem_brk += incr;
    return (void *)old_brk; //否则返回原堆内存上界指针
}

注意到mem_brk是已经使用的堆内存的上限指针，而非堆内存的最大地址。模型如下所示，注意指针指向的位置：

简单的说，该函数根据传入的incr大小，修改堆已使用内存的大小（堆内存本身的大小被固定为MAX_HEAP，查询config.h可知默认为20MB），将堆已使用内存的上限指针移动，如果成功则返回修改前的堆上限位置的指针，否则返回-1。

在上面mm_malloc的例子中，完成扩容后，我们修改的位置指向了刚申请的新内存空间，在刚申请的内存空间中进行处理没有数据污染的风险。

接下来，我们看mm_realloc函数，其功能为修改指向的内存块的大小：

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *ptr, size_t size) {
    void *oldptr = ptr;
    void *newptr;
    size_t copySize;

    newptr = mm_malloc(size); //先开辟相应的空间
    if (newptr == NULL) return NULL; //如果申请内存失败，直接返回NULL
    copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE); //确定原内存块的大小（通过读取其头部块实现）
    if (size < copySize) copySize = size; //如果修改后内存还不如当前块内存大，将复制的数据量控制为size
    memcpy(newptr, oldptr, copySize); //使用memcpy将原内存块中的东西拷贝到现内存块地址下
    mm_free(oldptr); //释放原内存块空间
    return newptr;
}

emmm… 挠头，他甚至只在头部嵌进去了块大小，也没见加入已分配的标记位… 也不知道这么搞怎么区分空闲块和已分配块…

不管怎么说，示例代码就分析到这里了…

隐式空闲链表（书中）

在书中P599页开始，非常详细的描述了基于空闲链表的一种实现，如下为P598上的隐式空闲链表的恒定形式：

其中，第一个字是一个双字边界对齐的不使用的填充字，填充后面紧跟一个特殊的序言块（prologue block），这是一个8字节的已分配块，只由一个头部和一个脚步组成。序言块是在初始化时创建的，并且永不释放。在序言块后面紧跟着的是零个或者多个由malloc或者free调用创建的普通块。堆总是以一个特殊的结尾块（epilogue block）来结束，这个块是一个大小为零的已分配块，只由一个头部组成。序言块和结尾块是一种消除合并时边界条件的技巧。分配器使用一个单独的私有全局变量heap_listp，他总是指向序言块。

在这里的例子中，直接使用一个字的大小，用unsigned int来描述块的大小和标志，放置在头部中。（居然没有用前面的size_t…），另外这里头部和脚部的标记反而又是记录了头部、脚部和有效负载等部分全部的大小，请不要误会。

宏定义

正如书中所说，使用良好的宏定义可以较好地提高编程效率，我们可以使用如下的宏定义：

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

/* Basic constants and macros */
#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) */

#define MAX(x, y) ((x) > (y) ? (x) : (y))

/* 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 previous blocks */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

WSIZE代表了一个字的大小即4字节，DSIZE代表了一个双字的大小即8字节。初始空闲块的大小和扩展堆时的默认大小为CHUKSIZE。

PACK通过位运算，将块大小和分配标识符结合，生成一个字，可以将其存储在头部和脚部中。

GET用于读取参数p引用的字，PUT用于存放在参数p指向的字。更进一步的，通过适当的位运算，使用GET_SIZE，可以将p引用的字中的块内存大小信息提取出来，使用GET_ALLOC可以将分配标识提取出来。

假设bp指向的是有效载荷首地址，则我们通过对应的偏移量，使用HDRP可以确定头部指针，使用FTRP可以确定脚步指针。

相似的，我们通过偏移量（这也就是隐式空闲链表的精髓，并没有指针链接各个节点，一切都是通过偏移量实现的）可以确定后面的块和前面的块的指针，通过NEXT_BLKP和PREV_BLKP来实现，(char *)(bp) - WSIZE指向的是当前块内存的头部，而(char *)(bp) - DSIZE指向的是前一块内存块的脚部。

创建初始空闲链表

很显然，在初始化堆时，按照书中所给的模型，我们首先应当划出序言块、结尾块以及起始位置的空间（图中用蓝色标出，共4个字），这部分内存需要调用mem_sbrk进行申请。

接下来，我们再将对应内容填入即可，正如上图中所示的，第一个字是一个双字边界对齐的不使用的填充字，用0填充即可，序言块中头部脚部分别是8/1和8/1，结尾块为0/1的头部。

最后我们还将调用extend_heap，将堆扩展CHUNKSIZE字节，并创建初始的空闲块。

因此我们有：

/*
 * mm_init - initialize the malloc package.
 */
int mm_init(void) {
    /* Create the initial empty heap */
    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 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 / WSIZE) == NULL) {
        return -1;
    }
    return 0;
}

关于extend_heap是如何实现的，可以看到：

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

    /* Allocate an even number of words to maintain alignment */
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size)) == -1) return NULL;

    /* Initialize free block header/footer and the epilogue header */
    PUT(HDRP(bp), PACK(size, 0));         /* Free block header */
    PUT(FTRP(bp), PACK(size, 0));         /* Free block footer */
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header*/

    return coalesce(bp);
}

这个函数应该是每次空闲空间不足时，向堆内存申请更多内存用的。每次申请偶数个字的内存空间，以确保内存是对齐的，随后我们将新分配的内存按照空闲块的标准进行头部和脚部的标记。

值得注意的是，我们直接将bp定为新申请空闲内存的有效载荷，因此写其头部的时候会直接覆盖刚才的结尾块，妙啊～以后循环往复，我们创建新的空闲块，抹掉上次的结尾块改成头部，自己再最后加一块结尾块上去…

当然新申请的空闲内存块可能和前面的空闲块有需要合并的情形，有可能前一个堆以一个空闲块结束，因此我们需要调用coalesce函数合并两个空闲块，并最终返回合并后的块的指针。关于合并的具体细节，留到下一部分再聊…

释放和合并块

在堆内存的释放中，会出现以下四种情形：

• 前面的块和后面的块都是已分配的
• 前面的块是已分配的，后面的块是空闲的
• 前面的块是空闲的，后面的块是已分配的
• 前面的块和后面的块都是空闲的

因此关键不在释放的时候把块的头部脚部标记改一下那么简单，更重要的是合并的coalesce操作。

首先如果我们要释放块ptr，其中ptr指向的是其有效载荷，我们可以修改其头部尾部，把标识位改为0即可，所以有：

/*
 * mm_free - Freeing a block does nothing.
 */
void mm_free(void *ptr) { 
    size_t size = GET_SIZE(HDRP(ptr));

    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));
    coalesce(ptr);
}

更关键部分自然在空闲内存块合并的部分，下面为代码内容，加了相关注释：

static void *coalesce(void *ptr) {
    //获取前后内存块的分配标识位
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(ptr)));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr)));
    //初始化新空闲块的大小为当前块大小，后续视情况添加
    size_t size = GET_SIZE(HDRP(ptr));

    if (prev_alloc && next_alloc) { /* Case 1 */
        return ptr;  //前后都已分配，什么都不做，返回ptr
    }

    else if (prev_alloc && !next_alloc) { /* Case 2 */
        //后面一块空闲，前面一块不空闲
        size += GET_SIZE(HDRP(NEXT_BLKP(ptr)));  //更新新空闲块大小
        PUT(HDRP(ptr), PACK(size, 0));  //修改头部大小，作为两块的头部
        PUT(FTRP(ptr), PACK(size, 0));  //顺着刚修改的大小找到尾部，修改尾部
    }

    else if (!prev_alloc && next_alloc) { /* Case 3 */
        //前面一块空闲，后面一块不空闲
        size += GET_SIZE(HDRP(PREV_BLKP(ptr)));  //更新新空闲块大小
        PUT(FTRP(ptr), PACK(size, 0));  //修改此块的脚部，作为两块的脚部
        PUT(HDRP(PREV_BLKP(ptr)),PACK(size, 0));  //顺着本块未更新的头部信息，找到前块的头部，对其进行修改
        ptr = PREV_BLKP(ptr);  //并将返回的新空闲块指针修改为前块的
    }

    else { /* Case 4 */
        //前后块都空闲
        size += GET_SIZE(HDRP(PREV_BLKP(ptr))) + GET_SIZE(FTRP(NEXT_BLKP(ptr)));  //更新空闲块大小
        PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));  //修改前块的头部，作为三块的头部
        PUT(FTRP(NEXT_BLKP(ptr)), PACK(size, 0));  //修改后块的脚部，作为三块的脚部
        ptr = PREV_BLKP(ptr);  //并将返回的新空闲块指针修改为前块的
    }
    return ptr;
}

分配块

在此部分中，我们将实现mm_malloc部分功能，mm_malloc将向内存申请一个size字节的块。

而我们在分配时需要考虑对齐的相关问题，因此必须要考虑调整块的大小问题。在本模型中，一个内存块至少需要16字节的空间，其中8字节留给头部和脚部，另外8字节作为满足对齐的最低要求。而对于超过8字节的请求，我们一律需要向上对齐到8的整数倍。

确定了需要的空间大小后，我们就需要在空闲链表中进行查找，查看是否有大于等于该要求的空闲内存块，这里会使用到一个简单分配器也就是find_fit方法，如果没有找到那么我们可能需要向堆内存申请更多的空间。

最后，我们将在分配的空闲块上进行截断等操作，并对截出来的空闲块重新进行头部和脚部标记，这块功能我们将在place方法中处理。

mm_malloc的实现大致如下：

/*
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */
void *mm_malloc(size_t size) { 
    size_t asize; /* Adjust block size */
    size_t extendsize; /* Amount to extend heap if no fit */
    char *ptr;

    /* Ignore spurious requests */
    if(size == 0){
        return NULL;
    }

    /* Adjust block size to include overhead and alignment reqs. */
    if(size <= DSIZE){
        asize = 2 * DSIZE; //至少16字节
    } else {
        asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE); //向上与8字节对齐
    }

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

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

还是比较好理解的，接下来就该处理find_fit方法了，我们要通过它来实现对空闲链表的搜索，根据请求的内存块大小asize取出足够大的空闲列表。

众所周知，匹配的时候有三种不同的方法，分别是：

• 从头遍历，寻找第一个满足大小要求的块（First fit）
• 从上次搜索结束的位置开始搜索（Next fit）
• 完整遍历空闲链表，寻找最适合的空闲内存块，即最少字节剩余的（可以认为是寻找大小大于等于asize的最小块）（Best fit）

在这里，我试着用最佳匹配的做法去做一下：

static void *find_fit(size_t asize) {
    void *ptr;
    void *res = NULL;
    size_t min_size = 0xffffffff;
    for (ptr = heap_listp; GET_SIZE(HDRP(ptr)) > 0; ptr = NEXT_BLKP(ptr)) { //遍历列表
        if (GET_ALLOC(HDRP(ptr))) {
            continue; //跳过已分配块
        }
        size_t block_size = GET_SIZE(HDRP(ptr)); //获取当前空闲块大小
        if (block_size >= asize && block_size < min_size) { //和记录的最小值比较，若更小则替换
            min_size = block_size;
            res = ptr;
        }
    }
    return res; //返回大于等于asize的最小块指针
}

此外，还有一个place方法需要处理，要求我们将某个空闲内存块截断，前段设置为分配块，后半段调整为空闲块。

我们的基本原则就是，如果空闲块的大小和需要分配的空间大小之差超过了一个空闲块的最低需求大小（也就是16字节，8字节留给头部和脚部，另外8字节作为满足对齐的最低要求），那么就是有必要做截断的，否则直接将整块记为已分配即可：

static void place(void* ptr, size_t asize){
    size_t block_size = GET_SIZE(HDRP(ptr));
    if((block_size - asize) >= (2 * DSIZE)){ //需要截断
        PUT(HDRP(ptr), PACK(asize, 1)); //修改头部
        PUT(FTRP(ptr), PACK(asize, 1)); //顺着刚修改的头部，找到前块已分配块的脚部修改
        ptr = NEXT_BLKP(ptr); //顺着修改后的头部，找到后块未分配块的有效载荷
        PUT(HDRP(ptr), PACK(block_size - asize, 0)); //修改后块未分配块的头部尾部，大小为差值
        PUT(FTRP(ptr), PACK(block_size - asize, 0));
    } else { //不需要截断，修改头部脚部即可
        PUT(HDRP(ptr), PACK(block_size, 1));
        PUT(FTRP(ptr), PACK(block_size, 1));
    }
}

重分配块大小

我们直接参考要求标准，分情况讨论即可。

• 如果size为0，等同于mm_free；
• 如果ptr为NULL，等同于mm_malloc；
• 否则，分配新内存空间，将本内存块中的内容转移过去之后，再将本块销毁；

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
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)) - DSIZE;
    if (size < oldsize) oldsize = size;
    memcpy(newptr, ptr, oldsize);

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

    return newptr;
}

内存检查器

由于隐式链表的特殊性，我觉得把检测内容放在以下几点就好：

• 能够从堆内存头部遍历到尾部，即从heap_listp到结尾块可以做到一遍覆盖
• 每个内存块的有效载荷都与8字节对齐
• 每个内存块的头部脚部信息一致
• 不存在两个连续的空闲内存块

int mm_check(void) {
    void *ptr, *prev_ptr;
    size_t prev_alloc = 1;
    for (ptr = heap_listp; GET_SIZE(HDRP(ptr)) > 0; ptr = NEXT_BLKP(ptr)) {  //遍历内存块
        if ((size_t)(ptr)&0x7) {  //检查对齐
            printf("Block pointer %p not aligned.\n", ptr);
            return 0;
        }
        size_t header = GET(HDRP(ptr));
        size_t footer = GET(FTRP(ptr));
        if(header != footer) { //检查头部和脚部是否一致
            printf("Block %p data corrupted, header and footer don't match.\n", ptr);
            return 0;
        }
        size_t cur_alloc = GET_ALLOC(HDRP(ptr));
        if (!prev_alloc && !cur_alloc) {  //检查是否连续空闲块未合并
            printf("Contiguous free blocks detected starting from %p.\n", prev_ptr);
            return 0;
        }
        prev_alloc = cur_alloc;
        prev_ptr = ptr;
    }
    if (ptr != mem_heap_hi() + 1) {  //检查是否用光了申请的堆内存
        printf("Blocks not using up the memory?\n");
        printf("Epilogue ptr: %p, Heap high ptr: %p\n", ptr, mem_heap_hi() + 1);
        printf("Heap size: %zu\n", mem_heapsize());
        return 0;
    }
    return 1;
}

在检查时，可以将mm_check()加入到各方法尾部中，例如mm_init(), mm_malloc(), mm_free(), mm_realloc()等。

经检查是可以通过的，测试时应当将相关语句注释，以免影响性能。

测试

最终的代码成型如下，注意到相关mm_check()方法已经注释：

/*
 * mm-implicit-free-list.c
 * The version from the book implemented with implicit free list...
 * No linked list involved, everything about ptr offset...
 */
#include "mm.h"

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include "memlib.h"

/*********************************************************
 * NOTE TO STUDENTS: Before you do anything else, please
 * provide your team information in the following struct.
 ********************************************************/
team_t team = {
    /* Team name */
    "ateam",
    /* First member's full name */
    "Harry Bovik",
    /* First member's email address */
    "bovik@cs.cmu.edu",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""};

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

/* Basic constants and macros */
#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) */

#define MAX(x, y) ((x) > (y) ? (x) : (y))

/* 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 previous blocks */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp)-WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp)-GET_SIZE(((char *)(bp)-DSIZE)))

static void *extend_heap(size_t words);
static void *coalesce(void *ptr);
static void *find_fit(size_t asize);
static void place(void *ptr, size_t asize);
int mm_init(void);
void *mm_malloc(size_t size);
void mm_free(void *ptr);
void *mm_realloc(void *ptr, size_t size);
int mm_check(void);

static char *heap_listp = 0;

/*
 * mm_init - initialize the malloc package.
 */
int mm_init(void) {
    /* Create the initial empty heap */
    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 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 / WSIZE) == NULL) {
        return -1;
    }
    // mm_check();
    return 0;
}

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

    /* Allocate an even number of words to maintain alignment */
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size)) == -1) return NULL;

    /* Initialize free block header/footer and the epilogue header */
    PUT(HDRP(bp), PACK(size, 0));         /* Free block header */
    PUT(FTRP(bp), PACK(size, 0));         /* Free block footer */
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header*/

    return coalesce(bp);
}

/*
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */
void *mm_malloc(size_t size) {
    size_t asize;      /* Adjust block size */
    size_t extendsize; /* Amount to extend heap if no fit */
    char *ptr;

    /* Ignore spurious requests */
    if (size == 0) {
        return NULL;
    }

    /* Adjust block size to include overhead and alignment reqs. */
    if (size <= DSIZE) {
        asize = 2 * DSIZE;  //至少16字节
    } else {
        asize =
            DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);  //向上与8字节对齐
    }

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

    /* No fit found. Get more memory and place the block */
    extendsize = MAX(asize, CHUNKSIZE);
    if ((ptr = extend_heap(extendsize / WSIZE)) == NULL) {
        return NULL;
    }
    place(ptr, asize);
    // mm_check();
    return ptr;
}

static void *find_fit(size_t asize) {
    void *ptr;
    void *res = NULL;
    size_t min_size = 0xffffffff;
    for (ptr = heap_listp; GET_SIZE(HDRP(ptr)) > 0;
         ptr = NEXT_BLKP(ptr)) {  //遍历列表
        if (GET_ALLOC(HDRP(ptr))) {
            continue;  //跳过已分配块
        }
        size_t block_size = GET_SIZE(HDRP(ptr));  //获取当前空闲块大小
        if (block_size >= asize &&
            block_size < min_size) {  //和记录的最小值比较，若更小则替换
            min_size = block_size;
            res = ptr;
        }
    }
    return res;  //返回大于等于asize的最小块指针
}

static void place(void *ptr, size_t asize) {
    size_t block_size = GET_SIZE(HDRP(ptr));
    if ((block_size - asize) >= (2 * DSIZE)) {  //需要截断
        PUT(HDRP(ptr), PACK(asize, 1));         //修改头部
        PUT(FTRP(ptr),
            PACK(asize, 1));  //顺着刚修改的头部，找到前块已分配块的脚部修改
        ptr = NEXT_BLKP(ptr);  //顺着修改后的头部，找到后块未分配块的有效载荷
        PUT(HDRP(ptr), PACK(block_size - asize,
                            0));  //修改后块未分配块的头部尾部，大小为差值
        PUT(FTRP(ptr), PACK(block_size - asize, 0));
    } else {  //不需要截断，修改头部脚部即可
        PUT(HDRP(ptr), PACK(block_size, 1));
        PUT(FTRP(ptr), PACK(block_size, 1));
    }
}

/*
 * mm_free - Freeing a block does nothing.
 */
void mm_free(void *ptr) {
    size_t size = GET_SIZE(HDRP(ptr));

    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));
    coalesce(ptr);

    // mm_check();
}

static void *coalesce(void *ptr) {
    //获取前后内存块的分配标识位
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(ptr)));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr)));
    //初始化新空闲块的大小为当前块大小，后续视情况添加
    size_t size = GET_SIZE(HDRP(ptr));

    if (prev_alloc && next_alloc) { /* Case 1 */
        return ptr;  //前后都已分配，什么都不做，返回ptr
    }

    else if (prev_alloc && !next_alloc) { /* Case 2 */
        //后面一块空闲，前面一块不空闲
        size += GET_SIZE(HDRP(NEXT_BLKP(ptr)));  //更新新空闲块大小
        PUT(HDRP(ptr), PACK(size, 0));  //修改头部大小，作为两块的头部
        PUT(FTRP(ptr), PACK(size, 0));  //顺着刚修改的大小找到尾部，修改尾部
    }

    else if (!prev_alloc && next_alloc) { /* Case 3 */
        //前面一块空闲，后面一块不空闲
        size += GET_SIZE(HDRP(PREV_BLKP(ptr)));  //更新新空闲块大小
        PUT(FTRP(ptr), PACK(size, 0));  //修改此块的脚部，作为两块的脚部
        PUT(HDRP(PREV_BLKP(ptr)),
            PACK(size,
                 0));  //顺着本块未更新的头部信息，找到前块的头部，对其进行修改
        ptr = PREV_BLKP(ptr);  //并将返回的新空闲块指针修改为前块的
    }

    else { /* Case 4 */
        //前后块都空闲
        size += GET_SIZE(HDRP(PREV_BLKP(ptr))) +
                GET_SIZE(FTRP(NEXT_BLKP(ptr)));  //更新空闲块大小
        PUT(HDRP(PREV_BLKP(ptr)),
            PACK(size, 0));  //修改前块的头部，作为三块的头部
        PUT(FTRP(NEXT_BLKP(ptr)),
            PACK(size, 0));  //修改后块的脚部，作为三块的脚部
        ptr = PREV_BLKP(ptr);  //并将返回的新空闲块指针修改为前块的
    }
    return ptr;
}

int mm_check(void) {
    void *ptr, *prev_ptr;
    size_t prev_alloc = 1;
    for (ptr = heap_listp; GET_SIZE(HDRP(ptr)) > 0;
         ptr = NEXT_BLKP(ptr)) {  //遍历内存块
        if ((size_t)(ptr)&0x7) {  //检查对齐
            printf("Block pointer %p not aligned.\n", ptr);
            return 0;
        }
        size_t header = GET(HDRP(ptr));
        size_t footer = GET(FTRP(ptr));
        if (header != footer) {  //检查头部和脚部是否一致
            printf("Block %p data corrupted, header and footer don't match.\n",
                   ptr);
            return 0;
        }
        size_t cur_alloc = GET_ALLOC(HDRP(ptr));
        if (!prev_alloc && !cur_alloc) {  //检查是否连续空闲块未合并
            printf("Contiguous free blocks detected starting from %p.\n",
                   prev_ptr);
            return 0;
        }
        prev_alloc = cur_alloc;
        prev_ptr = ptr;
    }
    if (ptr != mem_heap_hi() + 1) {  //检查是否用光了申请的堆内存
        printf("Blocks not using up the memory?\n");
        printf("Epilogue ptr: %p, Heap high ptr: %p\n", ptr, mem_heap_hi() + 1);
        printf("Heap size: %zu\n", mem_heapsize());
        return 0;
    }
    return 1;
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
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)) - DSIZE;
    if (size < oldsize) oldsize = size;
    memcpy(newptr, ptr, oldsize);

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

    // mm_check();
    return newptr;
}

分数有亿点点难看，不用上佬给的trace测试文件可能还看不出什么问题，带入了就感觉到差距了：

可以看到系统的空间利用率效果很好，但是吞吐量处理速度却崩了，觉得自己对整个堆内存的暴力扫描Best fit肯定是要负点责任的… 如果换成First fit应该会好很多

用默认自带的两个测试文件，分别能拉到80分和94分…

顺带说一句，在网课中，David O’Hallaron教授几乎没有怎么对书中解法进行解释，他在slides里面列出了好几种追踪空闲内存块的做法：

我觉得可以按照这里的分类做上几种实现…

显式空闲链表

所以跟着教授的幻灯片，我们就先做个显式链表的做法，并采用LIFO的策略进行内存释放，将每次释放出的内存块置于空闲链表头部。

显示链表组成大概如上，可以看到这次我们使用了指针进行各个空闲内存块之间的串联，此外链表中的内存块不需要按照地址顺序排列，进一步方便了我们进行内存的截断和合并等操作。另外由于链表中只包含了空闲列表，因此相比上方的隐式链表做法（需要扫描整个堆内存，包含空闲和非空闲内存块），理论上每次遍历的次数应当更少。

另外在这里，我试图解决刚才隐式空闲链表的几个痛点问题（我知道上面的代码扔给32位或者64位机器多半也能编译成功，也能跑），也是我几个比较不能接受的地方。

• 比如为什么强行把内存块的头部和脚部大小定成一个字呢，32位下一个字是够了，但是64位下呢（万一64位系统下有个小哥一次性申请了4GB+的内存呢），用默认程序中的size_t做代替岂不是更好
• 同理，在这个例子中，我们的内存块结构中除开头部和脚部，还多出了两个指针，用于实现指向链表的前后节点，那么问题来了存储一个指针地址需要多大的空间呢，32位和64位系统下地址需要的空间并不一致

我的简单想法是不如一律选择两个字的存储空间，使用这种策略同时也是为了内存对齐相关事宜的考量。就像默认程序中所展示的那样，对于32位的程序，每次我们将浪费掉一个字的空间。（感觉这样的话可能到时候内存利用率测试会难看亿点点）

看到由于所有部分都已经对齐了，大概也不需要头部额外的内存对齐块了。这样下来，我们可以估计一个序言块的大小为8个字，即32字节，而携带至少一个双字的有效载荷后，一个内存块的最小大小为10个字，即40字节。和隐式空闲链表一样，我们也设置序言块和结尾块，来标记按地址遍历的开始位置和结尾位置。其中，我们将序言块设置为空闲链表开始的根节点，而结尾块则不计入空闲链表中。

宏定义

为了后续的编程方便，我们继续使用宏定义来简化后续代码，我们尽量保持与上方类似的编码和命名风格，但是由于空间结构发生了变化，我们可能要好好改改：

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

/* Basic constants and macros */
#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) */

#define MAX(x, y) ((x) > (y) ? (x) : (y))

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

/* Read and write 1/2 word(s) at address p */
#define GET(p) (*(size_t *)(p))
#define PUT(p, val) (*(size_t *)(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, footer and prev/next ptrs */
#define HDRP(bp) ((char *)(bp)-3 * DSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - 4 * DSIZE)
#define PREV_PTR(bp) ((char *)(bp)-2 * DSIZE)
#define NEXT_PTR(bp) ((char *)(bp)-DSIZE)

/* Given block ptr bp, compute address of next and previous blocks (adjacent mem address) */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)))
#define PREV_BLKP(bp) ((char *)(bp)-GET_SIZE(((char *)(bp)-4 * DSIZE)))

/* Given block ptr bp, compute address of next and previous blocks (adjacent link list address) */
#define NEXT_LINKNODE_PTR(bp) ((char *)(GET(NEXT_PTR(bp))))
#define PREV_LINKNODE_PTR(bp) ((char *)(GET(PREV_PTR(bp))))

我们还是继续将有效负载开始的位置定义为bp，这样比较符合逻辑。

我们额外加入了几个定义，分别是读取内存块中prev和next指针内容，跳转到链表中上一个空闲块PREV_LINKNODE_PTR和下一个空闲块NEXT_LINKNODE_PTR。同时我们保留了根据内存地址寻找上下块的宏定义PREV_PTR和NEXT_PTR，方便到时候对相邻地址空闲内存块进行合并。

此外，我们对其他宏定义基本都进行了小幅度的修改，以满足我们目前的新内存块结构。

创建初始空闲链表

根据刚才的定义，初始化堆内存时需要5个双字，分别是序言块的头部、prev、next和脚部，以及结尾块的头部。随后，我们例行的将堆内存扩充，调用extend_heap，与书中写法类似。

/*
 * mm_init - initialize the malloc package.
 */
int mm_init(void) {
    /* Create the initial empty heap */
    if ((heap_listp = mem_sbrk(5 * DSIZE)) == (void *)-1) {
        return -1;
    }
    PUT(heap_listp, PACK(4 * DSIZE, 1)); /* Prologue header */
    PUT(heap_listp + (1 * DSIZE), NULL); /* Prologue prev ptr */
    PUT(heap_listp + (2 * DSIZE), NULL); /* Prologue next ptr */
    PUT(heap_listp + (3 * DSIZE), PACK(4 * DSIZE, 1)); /* Prologue footer */

    PUT(heap_listp + (4 * DSIZE), PACK(0, 1)); /* Epilogue header */

    heap_listp += (3 * DSIZE);

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

关于extend_heap，其主要有两个功能，一方面扩大堆内存空间，写入内存块头部脚部相关数据，并根据是否有连续的内存空闲块进行相应的coalesce合并操作；一方面采用书中做法，直接覆盖之前的结尾块，最后再补上一个。

注意的是，将新生成的空闲内存块置链表头部的操作，我们内置在coalesce方法中了，下文中会提及。

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

    /* Allocate an even number of words to maintain alignment */
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE; //拓展内存大小双字对齐
    if ((long)(bp = mem_sbrk(size)) == -1) return NULL;

    bp += (2 * DSIZE);
    /* Initialize free block header/footer and the epilogue header */
    PUT(HDRP(bp), PACK(size, 0)); //设置新空闲块头部
    PUT(FTRP(bp), PACK(size, 0)); //设置新空闲块脚部
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); //设置新的结尾块

    ptr = coalesce(bp); //检查是否连续空闲块需要合并
    return ptr;
}

释放和合并块

在此过程中，我们将处理堆内存的释放问题，处理当前内存的逻辑还是较为简单的，首先看如何处理当前所指向的内存块：

/*
 * mm_free - Freeing a block does nothing.
 */
void mm_free(void *ptr) {
    size_t size = GET_SIZE(HDRP(ptr));

    PUT(HDRP(ptr), PACK(size, 0)); //修改头部标记
    PUT(FTRP(ptr), PACK(size, 0)); //修改尾部标记

    coalesce(ptr);

}

更加关键的是如何处理coalesce的空闲块合并操作，即“四种情形”。在显式链表情形下，slides中较为清楚的给出了解决方案。

[{"url":"case1.png","alt":"Case 1"},{"url":"case2.png","alt":"Case 2"},{"url":"case3.png","alt":"Case 3"},{"url":"case4.png","alt":"Case 4"}]

Load More

可以看到所有的步骤可以分为两步，首先我们将有涉及合并需要的空闲内存块从双向链表中移除，我们可以在remove_node函数中解决；接下来我们执行内存块的具体合并操作，更新块大小，修改头部脚部信息；最后我们将新生成的空闲内存块加入到双向链表的头部。

static void *coalesce(void *ptr) {
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(ptr))); //获取地址前块标记
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr))); //获取地址后块标记
    size_t size = GET_SIZE(HDRP(ptr)); //初始化新空闲内存块大小

    /*coalesce the block and change the point*/
    if (prev_alloc && next_alloc) { //Case 1
        
    } else if (prev_alloc && !next_alloc) { //Case 2
        size += GET_SIZE(HDRP(NEXT_BLKP(ptr))); //更新内存块大小
        remove_node(NEXT_BLKP(ptr)); //将后块从链表中先移除
        PUT(HDRP(ptr), PACK(size, 0)); //修改新内存块的头部
        PUT(FTRP(ptr), PACK(size, 0)); //修改新内存块的脚部
    } else if (!prev_alloc && next_alloc) { //Case 3
        size += GET_SIZE(HDRP(PREV_BLKP(ptr))); //更新内存块大小
        remove_node(PREV_BLKP(ptr)); //将前块从链表中先移除
        PUT(FTRP(ptr), PACK(size, 0)); //修改新内存块的头部
        PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0)); //修改新内存块的脚部
        ptr = PREV_BLKP(ptr); //修改新内存块指针，指向两块中的前块
    } else {
        size += GET_SIZE(FTRP(NEXT_BLKP(ptr))) + GET_SIZE(HDRP(PREV_BLKP(ptr))); //更新内存块大小
        remove_node(PREV_BLKP(ptr)); //将三块中的前块移除出链表
        remove_node(NEXT_BLKP(ptr)); //将三块中的后块移除出链表
        PUT(FTRP(NEXT_BLKP(ptr)), PACK(size, 0)); //修改新内存块的脚部
        PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0)); //修改新内存块的头部
        ptr = PREV_BLKP(ptr); //修改新内存块指针，指向三块中的前块
    }
    insert_to_list(ptr); //最后将新生成的内存块插入到链表头
    return ptr;
}

将一个空闲内存块移除出双向链表的逻辑较为简单：

static void remove_node(void *ptr) {
    char *prev, *next;
    prev = PREV_LINKNODE_PTR(ptr); //获取链表前节点
    next = NEXT_LINKNODE_PTR(ptr); //获取链表后节点
    
    PUT(NEXT_PTR(prev), next); //设置前节点的下一个节点为next
    if(next){ //注意如果是null就不要做了
        PUT(PREV_PTR(next), prev); //设置后节点的前一个节点为prev
    }
}

将一个空闲内存块加入到链表头部的代码也较为简单如下所示：

static void insert_to_list(void *ptr) {
    char *next;
    next = NEXT_LINKNODE_PTR(heap_listp); //获取当前的头部节点
    if (next) { //如果为null，就不必做了
        PUT(PREV_PTR(next), ptr); //将原头部节点的前一个节点设置为ptr
    }
    PUT(NEXT_PTR(ptr), next); //将ptr下一个节点设置为next
    PUT(NEXT_PTR(heap_listp), ptr); //将哨兵root头节点的下一个节点设置为ptr
    PUT(PREV_PTR(ptr), heap_listp); //将ptr的上一个节点设置为root节点
}

分配块

分配节点的代码和书中的相似，但是需要注意到，在当前情况下含有有效载荷的一个空闲内存块大小为40字节起步，其中32字节为头部、尾部、prev和next，而另外8字节是有效载荷的最小对齐要求大小。

在确定了需要的空闲块大小后，我们使用find_fit对空闲链表进行搜索。如果找到满足大小要求的空闲块，我们考虑是否需要进行截断操作，相关代码在place函数中实现；如果没有找到，我们就向内存申请空间，使用新开辟的内存块继续操作。

/*
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */
void *mm_malloc(size_t size) {
    size_t asize;      /* Adjust block size */
    size_t extendsize; /* Amount to extend heap if no fit */
    char *ptr;

    /* Ignore spurious requests */
    if(size == 0){
        return NULL;
    }

    /* Adjust block size to include overhead and alignment reqs. */
    if(size <= DSIZE){
        asize = 5 * DSIZE; //至少40字节
    } else {
        asize = DSIZE * ((size + (4 * DSIZE) + (DSIZE - 1)) / DSIZE); //向上与8字节对齐
    }
    /* Search the free list for a fit */
    if((ptr = find_fit(asize)) != NULL) {
        place(ptr, asize);
        return ptr;
    }

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

在find_fit函数中，这次我们使用First fit策略（就是想偷懒hhh），顺着链表一路往下找是否有满足大小的空闲内存块：

static void *find_fit(size_t asize) {
    char *ptr;
    ptr = NEXT_LINKNODE_PTR(heap_listp); //从头节点开始
    while (ptr) {
        if (GET_SIZE(HDRP(ptr)) >= asize) { //比较是否满足大小要求
            return ptr;
        }
        ptr = NEXT_LINKNODE_PTR(ptr); //不满足则前往下一个链表节点
    }
    return NULL; //找不到返回null
}

在place函数中，我们考虑是否截断的问题。自然的，只有空闲块足够大的时候才需要进行截断，而又有一个空闲内存块的最小大小为40字节，因此如果超过的余量大于或者等于40字节，我们就认为应当进行截断，否则直接使用整块内存块进行分配。

另外，在处理截断问题的时候，由于当前是显式链表，因此我们需要将当前的空闲内存块从双向链表中移除，如果有截断情况的，我们需要将后部分的截断块加入到链表中。幻灯片中，教授是选择将当前块修改成空闲块的，不影响其在链表中的位置。

而我就是个懒狗，我选择直接把空闲块插到双向链表头部（

static void place(void *ptr, size_t asize) {
    size_t block_size;
    block_size = GET_SIZE(HDRP(ptr)); //获取当前块的大小
    remove_node(ptr); //将当前被使用的空闲块从链表中移除
    if((block_size - asize) >= (5 * DSIZE)) { //判断是否需要截断
        PUT(HDRP(ptr), PACK(asize, 1)); //需要，则设置新的头部脚部信息
        PUT(FTRP(ptr), PACK(asize, 1));
        ptr = NEXT_BLKP(ptr); //同时处理后半段截断块
        PUT(HDRP(ptr), PACK(block_size - asize, 0)); //设置截断块的头部脚部
        PUT(FTRP(ptr), PACK(block_size - asize, 0));
        insert_to_list(ptr); //并将截断块加入链表
    } else {
        PUT(HDRP(ptr), PACK(block_size, 1)); //不需要，则直接设置头部脚部信息
        PUT(FTRP(ptr), PACK(block_size, 1));
    }
}

重分配块大小

要求同上：

• 如果size为0，等同于mm_free；
• 如果ptr为NULL，等同于mm_malloc；
• 否则，分配新内存空间，将本内存块中的内容转移过去之后，再将本块销毁；

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
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)) - 4 * DSIZE;
    if (size < oldsize) oldsize = size;
    memcpy(newptr, ptr, oldsize);

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

    return newptr;
}

内存检查器

对于显式空闲链表，我觉得可以作如下检查：

• 按照链表遍历，确定各内存块有效载荷与8字节对齐
• 每个内存块的头部脚部信息一致
• 按照内存地址遍历，不存在两个连续的空闲内存块
• 按照内存地址遍历，能够从堆内存头部遍历到尾部，即从 heap_listp 到结尾块可以做到一遍覆盖
• 按照内存遍历和按照链表遍历，数得的空闲块数量一致

int mm_check(void) {
    void *ptr, *prev_ptr;
    size_t prev_alloc= 1;
    size_t count = 0;
    ptr = NEXT_LINKNODE_PTR(heap_listp);  //从头节点开始
    while (ptr) {
        count++; //计数+1
        ptr = NEXT_LINKNODE_PTR(ptr); 
    }
    for (ptr = NEXT_BLKP(heap_listp); GET_SIZE(HDRP(ptr)) > 0; ptr = NEXT_BLKP(ptr)) {  //遍历内存块
        if ((size_t)(ptr)&0x7) {  //检查对齐
            printf("Block pointer %p not aligned.\n", ptr);
            return 0;
        }
        size_t header = GET(HDRP(ptr));
        size_t footer = GET(FTRP(ptr));
        if(header != footer) { //检查头部和脚部是否一致
            printf("Block %p data corrupted, header and footer don't match.\n", ptr);
            return 0;
        }
        size_t cur_alloc = GET_ALLOC(HDRP(ptr));
        if(!cur_alloc) {
            count--;
        }
        if (!prev_alloc && !cur_alloc) {  //检查是否连续空闲块未合并
            printf("Contiguous free blocks detected starting from %p.\n", prev_ptr);
            return 0;
        }
        prev_alloc = cur_alloc;
        prev_ptr = ptr;
    }
    if(count) { //检测两次遍历的数量是否一致
        printf("Blocks numbers don't match...\n");
        return 0;
    }
    if(ptr != mem_heap_hi() + 1 + (2 * DSIZE)) { //检查是否用光了申请的堆内存
        printf("Blocks not using up the memory?\n");
        printf("Epilogue ptr: %p, Heap high ptr: %p\n", ptr - (2 * DSIZE), mem_heap_hi() + 1);
        printf("Heap size: %zu\n", mem_heapsize());
        return 0;
    }
    return 1;
}

测试

最终代码成型如下，注意到相关mm_check()方法已经注释：

/*
 * mm-explicit-free-list.c
 * The version implemented woth implicit free list...
 */
#include "mm.h"

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include "memlib.h"

/*********************************************************
 * NOTE TO STUDENTS: Before you do anything else, please
 * provide your team information in the following struct.
 ********************************************************/
team_t team = {
    /* Team name */
    "ateam",
    /* First member's full name */
    "Harry Bovik",
    /* First member's email address */
    "bovik@cs.cmu.edu",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""};

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

/* Basic constants and macros */
#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) */

#define MAX(x, y) ((x) > (y) ? (x) : (y))

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

/* Read and write 1/2 word(s) at address p */
#define GET(p) (*(size_t *)(p))
#define PUT(p, val) (*(size_t *)(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, footer and prev/next ptrs
 */
#define HDRP(bp) ((char *)(bp)-3 * DSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - 4 * DSIZE)
#define PREV_PTR(bp) ((char *)(bp)-2 * DSIZE)
#define NEXT_PTR(bp) ((char *)(bp)-DSIZE)

/* Given block ptr bp, compute address of next and previous blocks (adjacent mem
 * address) */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)))
#define PREV_BLKP(bp) ((char *)(bp)-GET_SIZE(((char *)(bp)-4 * DSIZE)))

/* Given block ptr bp, compute address of next and previous blocks (adjacent
 * link list address) */
#define NEXT_LINKNODE_PTR(bp) ((char *)(GET(NEXT_PTR(bp))))
#define PREV_LINKNODE_PTR(bp) ((char *)(GET(PREV_PTR(bp))))

static void *extend_heap(size_t words);
static void insert_to_list(void *ptr);
static void remove_node(void *ptr);
static void *coalesce(void *ptr);
static void *find_fit(size_t asize);
static void place(void *ptr, size_t asize);
int mm_init(void);
void *mm_malloc(size_t size);
void mm_free(void *ptr);
void *mm_realloc(void *ptr, size_t size);
int mm_check(void);

static char *heap_listp = 0;

/*
 * mm_init - initialize the malloc package.
 */
int mm_init(void) {
    /* Create the initial empty heap */
    if ((heap_listp = mem_sbrk(5 * DSIZE)) == (void *)-1) {
        return -1;
    }
    PUT(heap_listp, PACK(4 * DSIZE, 1)); /* Prologue header */
    PUT(heap_listp + (1 * DSIZE), NULL); /* Prologue prev ptr */
    PUT(heap_listp + (2 * DSIZE), NULL); /* Prologue next ptr */
    PUT(heap_listp + (3 * DSIZE), PACK(4 * DSIZE, 1)); /* Prologue footer */

    PUT(heap_listp + (4 * DSIZE), PACK(0, 1)); /* Epilogue header */

    heap_listp += (3 * DSIZE);

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

    // mm_check();
    return 0;
}

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

    /* Allocate an even number of words to maintain alignment */
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE; //拓展内存大小双字对齐
    if ((long)(bp = mem_sbrk(size)) == -1) return NULL;

    bp += (2 * DSIZE);
    /* Initialize free block header/footer and the epilogue header */
    PUT(HDRP(bp), PACK(size, 0)); //设置新空闲块头部
    PUT(FTRP(bp), PACK(size, 0)); //设置新空闲块脚部
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); //设置新的结尾块

    ptr = coalesce(bp); //检查是否连续空闲块需要合并
    return ptr;
}

static void insert_to_list(void *ptr) {
    char *next;
    next = NEXT_LINKNODE_PTR(heap_listp); //获取当前的头部节点
    if (next) { //如果为null，就不必做了
        PUT(PREV_PTR(next), ptr); //将原头部节点的前一个节点设置为ptr
    }
    PUT(NEXT_PTR(ptr), next); //将ptr下一个节点设置为next
    PUT(NEXT_PTR(heap_listp), ptr); //将哨兵root头节点的下一个节点设置为ptr
    PUT(PREV_PTR(ptr), heap_listp); //将ptr的上一个节点设置为root节点
}

static void remove_node(void *ptr) {
    char *prev, *next;
    prev = PREV_LINKNODE_PTR(ptr); //获取链表前节点
    next = NEXT_LINKNODE_PTR(ptr); //获取链表后节点
    
    PUT(NEXT_PTR(prev), next); //设置前节点的下一个节点为next
    if(next){ //注意如果是null就不要做了
        PUT(PREV_PTR(next), prev); //设置后节点的前一个节点为prev
    }
}

static void *coalesce(void *ptr) {
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(ptr))); //获取地址前块标记
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr))); //获取地址后块标记
    size_t size = GET_SIZE(HDRP(ptr)); //初始化新空闲内存块大小

    /*coalesce the block and change the point*/
    if (prev_alloc && next_alloc) { //Case 1
        
    } else if (prev_alloc && !next_alloc) { //Case 2
        size += GET_SIZE(HDRP(NEXT_BLKP(ptr))); //更新内存块大小
        remove_node(NEXT_BLKP(ptr)); //将后块从链表中先移除
        PUT(HDRP(ptr), PACK(size, 0)); //修改新内存块的头部
        PUT(FTRP(ptr), PACK(size, 0)); //修改新内存块的脚部
    } else if (!prev_alloc && next_alloc) { //Case 3
        size += GET_SIZE(HDRP(PREV_BLKP(ptr))); //更新内存块大小
        remove_node(PREV_BLKP(ptr)); //将前块从链表中先移除
        PUT(FTRP(ptr), PACK(size, 0)); //修改新内存块的头部
        PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0)); //修改新内存块的脚部
        ptr = PREV_BLKP(ptr); //修改新内存块指针，指向两块中的前块
    } else {
        size += GET_SIZE(FTRP(NEXT_BLKP(ptr))) + GET_SIZE(HDRP(PREV_BLKP(ptr))); //更新内存块大小
        remove_node(PREV_BLKP(ptr)); //将三块中的前块移除出链表
        remove_node(NEXT_BLKP(ptr)); //将三块中的后块移除出链表
        PUT(FTRP(NEXT_BLKP(ptr)), PACK(size, 0)); //修改新内存块的脚部
        PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0)); //修改新内存块的头部
        ptr = PREV_BLKP(ptr); //修改新内存块指针，指向三块中的前块
    }
    insert_to_list(ptr); //最后将新生成的内存块插入到链表头
    return ptr;
}

/*
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */
void *mm_malloc(size_t size) {
    size_t asize;      /* Adjust block size */
    size_t extendsize; /* Amount to extend heap if no fit */
    char *ptr;

    /* Ignore spurious requests */
    if(size == 0){
        return NULL;
    }

    /* Adjust block size to include overhead and alignment reqs. */
    if(size <= DSIZE){
        asize = 5 * DSIZE; //至少40字节
    } else {
        asize = DSIZE * ((size + (4 * DSIZE) + (DSIZE - 1)) / DSIZE); //向上与8字节对齐
    }
    /* Search the free list for a fit */
    if((ptr = find_fit(asize)) != NULL) {
        place(ptr, asize);
        // mm_check();
        return ptr;
    }

    /* No fit found. Get more memory and place the block */
    extendsize = MAX(asize, CHUNKSIZE);
    if((ptr = extend_heap(extendsize/WSIZE)) == NULL) {
        return NULL;
    }
    place(ptr, asize);
    
    // mm_check();
    return ptr;
}

static void *find_fit(size_t asize) {
    char *ptr;
    ptr = NEXT_LINKNODE_PTR(heap_listp); //从头节点开始
    while (ptr) {
        if (GET_SIZE(HDRP(ptr)) >= asize) { //比较是否满足大小要求
            return ptr;
        }
        ptr = NEXT_LINKNODE_PTR(ptr); //不满足则前往下一个链表节点
    }
    return NULL; //找不到返回null
}

static void place(void *ptr, size_t asize) {
    size_t block_size;
    block_size = GET_SIZE(HDRP(ptr)); //获取当前块的大小
    remove_node(ptr); //将当前被使用的空闲块从链表中移除
    if((block_size - asize) >= (5 * DSIZE)) { //判断是否需要截断
        PUT(HDRP(ptr), PACK(asize, 1)); //需要，则设置新的头部脚部信息
        PUT(FTRP(ptr), PACK(asize, 1));
        ptr = NEXT_BLKP(ptr); //同时处理后半段截断块
        PUT(HDRP(ptr), PACK(block_size - asize, 0));  //设置截断块的头部脚部
        PUT(FTRP(ptr), PACK(block_size - asize, 0));
        insert_to_list(ptr); //并将截断块加入链表
    } else {
        PUT(HDRP(ptr), PACK(block_size, 1)); //不需要，则直接设置头部脚部信息
        PUT(FTRP(ptr), PACK(block_size, 1));
    }
}

/*
 * mm_free - Freeing a block does nothing.
 */
void mm_free(void *ptr) {
    size_t size = GET_SIZE(HDRP(ptr));

    PUT(HDRP(ptr), PACK(size, 0)); //修改头部标记
    PUT(FTRP(ptr), PACK(size, 0)); //修改尾部标记

    coalesce(ptr);
    // mm_check();
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
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)) - 4 * DSIZE;
    if (size < oldsize) oldsize = size;
    memcpy(newptr, ptr, oldsize);

    /* Free the old block. */
    mm_free(ptr);
    // mm_check();

    return newptr;
}

int mm_check(void) {
    void *ptr, *prev_ptr;
    size_t prev_alloc= 1;
    size_t count = 0;
    ptr = NEXT_LINKNODE_PTR(heap_listp);  //从头节点开始
    while (ptr) {
        count++; //计数+1
        ptr = NEXT_LINKNODE_PTR(ptr); 
    }
    for (ptr = NEXT_BLKP(heap_listp); GET_SIZE(HDRP(ptr)) > 0; ptr = NEXT_BLKP(ptr)) {  //遍历内存块
        if ((size_t)(ptr)&0x7) {  //检查对齐
            printf("Block pointer %p not aligned.\n", ptr);
            return 0;
        }
        size_t header = GET(HDRP(ptr));
        size_t footer = GET(FTRP(ptr));
        if(header != footer) { //检查头部和脚部是否一致
            printf("Block %p data corrupted, header and footer don't match.\n", ptr);
            return 0;
        }
        size_t cur_alloc = GET_ALLOC(HDRP(ptr));
        if(!cur_alloc) {
            count--;
        }
        if (!prev_alloc && !cur_alloc) {  //检查是否连续空闲块未合并
            printf("Contiguous free blocks detected starting from %p.\n", prev_ptr);
            return 0;
        }
        prev_alloc = cur_alloc;
        prev_ptr = ptr;
    }
    if(count) { //检测两次遍历的数量是否一致
        printf("Blocks numbers don't match...\n");
        return 0;
    }
    if(ptr != mem_heap_hi() + 1 + (2 * DSIZE)) { //检查是否用光了申请的堆内存
        printf("Blocks not using up the memory?\n");
        printf("Epilogue ptr: %p, Heap high ptr: %p\n", ptr - (2 * DSIZE), mem_heap_hi() + 1);
        printf("Heap size: %zu\n", mem_heapsize());
        return 0;
    }
    return 1;
}

分数好看起来了，由于我们针对空闲内存块使用了链表进行整理，每次不必遍历整个堆内存了，这次拿到了81分：

默认自带的两个测试文件结果也没差太多… 测试还得看样例准不准确了

总结

总之这次做的还是很开心的，但是还没尽兴？之前一直乱背八股文，对这些概念一知半解的，还是上手写写有点成就感。

后续可能还打算补上数组空闲链表（Segregated free list）的实现，如果有可能还想整个活，撸个简单的GC出来（估计运行时间会爆炸）…