感谢hankeke303大佬 提供的思路！
实验目的
在这个实验中，我们将编写一个用于C程序的动态存储分配器，即实现malloc、free和realloc函数。鼓励以创造性的方式进行探索设计，并实现一个正确、高效和快速的分配器。
以下四个函数是需要实现的函数，它们在mm.h中声明并在mm.c中定义。
| 函数 | 简要作用 |
|---|---|
mm_init() |
调用mm_init执行任何必要的初始化，例如分配初始堆区域。如果在执行初始化时出现问题，则返回值应为-1，否则为0。 |
mm_malloc() |
mm_malloc例程返回一个指向至少大小为size字节的分配块有效负载的指针。 |
mm_free() |
mm_free例程释放ptr指向的块。它不返回任何内容。只有当传递的指针（ptr）是由先前的mm_malloc或mm_realloc调用返回的，并且尚未被释放时，此例程才保证可工作。 |
mm_realloc() |
mm_realloc例程返回一个指向至少大小为size字节的分配区域的指针。 |
测试程序通过计算性能指数 $P$ 来计算分配器的性能，该指数是空间利用率和吞吐量的加权和。
$$ P = wU + (1 − w) \cdot \mathrm{min} \left\{ 1, \ \frac{T}{T_{\mathrm{libc}}} \right\} $$其中，$U$ 是空间利用率，$T$ 是吞吐量，$T_{\mathrm{libc}}$ 是在默认
trace下libc的malloc吞吐量，$w$ 的默认值为 $0.6$。性能指标更倾向于空间利用率而不是吞吐量。
宏定义
大致和书上使用的宏定义相同，不过最后有几个和分离适配的链表相关，LIST_PRE和 LIST_NEXT表示这个块上存储上一块和下一块的位置的指针，LIST_HEAD表示第 $i$ 个大小类的头指针，GET_XXX是这三个宏定义的解引用版本。
操作空闲链表的基本常数和宏
1/* $begin mallocmacros */
2/* Basic constants and macros */
3#define WSIZE 4 /* Word and header/footer size (bytes) */ //line:vm:mm:beginconst
4#define DSIZE 8 /* Double word size (bytes) */
5#define CHUNKSIZE (1<<12) /* Extend heap by this amount (bytes) */ //line:vm:mm:endconst
6
7#define MAX(x, y) ((x) > (y)? (x) : (y))
8
9/* Pack a size and allocated bit into a word */
10#define PACK(size, alloc) ((size) | (alloc)) //line:vm:mm:pack
11
12/* Read and write a word at address p */
13#define GET(p) (*(unsigned int *)(p)) //line:vm:mm:get
14#define PUT(p, val) (*(unsigned int *)(p) = (unsigned int)(val)) //line:vm:mm:put
15
16/* Read the size and allocated fields from address p */
17#define GET_SIZE(p) (GET(p) & ~0x7) //line:vm:mm:getsize
18#define GET_ALLOC(p) (GET(p) & 0x1) //line:vm:mm:getalloc
19
20/* Given block ptr bp, compute address of its header and footer */
21#define HDRP(bp) ((char *)(bp) - WSIZE) //line:vm:mm:hdrp
22#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) //line:vm:mm:ftrp
23
24/* Given block ptr bp, compute address of next and previous blocks */
25#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE))) //line:vm:mm:nextblkp
26#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) //line:vm:mm:prevblkp
27
28/* 分离适配链表相关 */
29#define LIST_PRE(bp) (bp)
30#define LIST_NEXT(bp) ((void *)((char *)bp + WSIZE))
31#define LIST_HEAD(x) ((void *)((char *)(heap) + WSIZE * (x)))
32#define GET_PRE(bp) ((void *)GET(LIST_PRE(bp)))
33#define GET_NEXT(bp) ((void *)GET(LIST_NEXT(bp)))
34#define GET_HEAD(x) ((void *)GET((char *)(heap) + WSIZE * (x)))
35/* $end mallocmacros */
需要注意的是，在这一段进行了如下的修改：
1- #define PUT(p, val) (*(unsigned int *)(p) = (val))
2+ #define PUT(p, val) (*(unsigned int *)(p) = (unsigned int)(val))
如果采用书上的方案，编译时将会出现warning: assignment to ‘unsigned int’ from ‘void *’ makes integer from pointer without a cast [-Wint-conversion]。这个警告是因为在 C 语言中，直接将void*指针赋值给unsigned int类型会导致类型不匹配。
如果不更改，编译时将会警告很多次（表现为报错数十行，虽然不影响运行结果）。
这样，我们可以写出一个确定大小类编号的函数：
1int getlist(size_t size) {
2 for (int i = 0; i < 19; ++i) {
3 if (size <= (1 << (i + 4))) {
4 return i;
5 }
6 }
7 return 19;
8}
函数实现
初始化
在书上 P600 提供了一个简易版本：
初始化空闲块
1int mm_init(void)
2{
3 if ((heap = mem_sbrk(24 * WSIZE)) == (void*)-1) {
4 return -1;
5 }
6
7 // 申请 (20+4)*4 个字节的空间
8 for (int i = 0; i < 20; ++i) {
9 PUT(LIST_HEAD(i), NULL);
10 }
11
12 PUT(LIST_HEAD(20), 0);
13 PUT(LIST_HEAD(21), PACK(DSIZE, 1));
14 PUT(LIST_HEAD(22), PACK(DSIZE, 1));
15 PUT(LIST_HEAD(23), PACK(0, 1));
16
17 // 将堆扩展`CHUNKSIZE`字节，并且创建初始的空闲块
18 if (extend_heap(CHUNKSIZE / WSIZE) == NULL) {
19 return -1;
20 }
21 return 0;
22}
其中，extend_heap函数用来将堆扩展CHUNKSIZE字节，并且创建初始的空闲块。此刻，分配器已初始化了，并且准备好接受来自应用的分配和释放请求。
extend_heap函数
1void *extend_heap(size_t size) {
2 size = ((size % 2) ? size + 1 : size) * WSIZE;
3 void *bp = mem_sbrk(size);
4
5 if (bp == (void *)-1) {
6 return NULL;
7 }
8
9 PUT(HDRP(bp), PACK(size, 0));
10 PUT(FTRP(bp), PACK(size, 0));
11 PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
12
13 return coalesce(bp);
14}
内存块管理
插入
这里，我们确保了每个大小块中，所有空闲块都是按照大小排序的，头指针指向的为最小的块，越向后大小越大。
因此，在插入的时候，我们要在链表中找到合适的位置才能插入。
1// 链表插入
2void ins(void *bp) {
3 // 根据大小选择链表
4 size_t size = GET_SIZE(HDRP(bp));
5 int list = getlist(size);
6 // 若链表为空
7 if (GET_HEAD(list) == NULL) {
8 // 直接作为链表第一个元素
9 PUT(LIST_NEXT(bp), NULL);
10 PUT(LIST_HEAD(list), bp);
11 PUT(LIST_PRE(bp), NULL);
12 }
13 else {
14 void *p, *q;
15 for (p = GET_HEAD(list), q = NULL; p; q = p, p = GET_NEXT(p)) {
16 if (GET_SIZE(HDRP(p)) >= size) {
17 if (q == NULL) {
18 PUT(LIST_HEAD(list), bp);
19 }
20 else {
21 PUT(LIST_NEXT(q), bp);
22 }
23 // 插入链表
24 PUT(LIST_NEXT(bp), p);
25 PUT(LIST_PRE(p), bp);
26 PUT(LIST_PRE(bp), q);
27 return;
28 }
29 }
30
31 // 当前块最大
32 if (q == NULL) {
33 PUT(LIST_HEAD(list), bp);
34 }
35 else {
36 PUT(LIST_NEXT(q), bp);
37 }
38 PUT(LIST_NEXT(bp), p);
39 if (p) {
40 PUT(LIST_PRE(p), bp);
41 }
42 PUT(LIST_PRE(bp), q);
43 }
44}
删除
删除部分就简单了，不需要区分是哪种适配，只需要修改原本的前驱、后继的相关指针即可。
1// 链表删除
2void del(void *bp) {
3 // 根据块大小选择链表
4 size_t size = GET_SIZE(HDRP(bp));
5 int list = getlist(size);
6 // 删除的就是头结点
7 if (GET_PRE(bp) == NULL) {
8 PUT(LIST_HEAD(list), GET_NEXT(bp));
9 }
10 else {
11 // 前驱节点的 next 指向当前节点的后继
12 PUT(LIST_NEXT(GET_PRE(bp)), GET_NEXT(bp));
13 }
14 // 更新后继节点的前驱指针
15 if (GET_NEXT(bp)) {
16 // 后继的前驱指针指向删除结点的前驱
17 PUT(LIST_PRE(GET_NEXT(bp)), GET_PRE(bp));
18 }
19}
合并与切割
合并的过程是将连续的空闲块合成一个。因为我们采用了立即合并的思路，只要有新的空闲块诞生就立刻合并，保证了任意时刻空闲块都是不连续的。
具体的方法是判断新的空闲块的前一个块和后一个块是不是空闲的，将相邻的空闲块在原来的链表中删除，合并在一起，插入新的链表。
1// 合并空闲块
2void *coalesce(void *bp) {
3 // fprintf(stderr, "coalesce %#p begin\n", bp);
4 size_t pre_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
5 size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
6 size_t size = GET_SIZE(HDRP(bp));
7 // fprintf(stderr, "coalesce %#p middle %d %d %lu\n", bp, prea, nexta, size);
8
9 // 若需要合并，先删除原来的 bp 内存块，重新分配大小后再插入链表中
10
11 // 前后内存块均已分配
12 if (pre_alloc && next_alloc) ;
13 // 前面块已分配，后面块空闲
14 else if (pre_alloc && !next_alloc) {
15 del(NEXT_BLKP(bp));
16 size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
17 PUT(HDRP(bp), PACK(size, 0));
18 PUT(FTRP(bp), PACK(size, 0));
19 }
20 // 前面块空闲，后面块已分配
21 else if (!pre_alloc && next_alloc) {
22 del(PREV_BLKP(bp));
23 size += GET_SIZE(HDRP(PREV_BLKP(bp)));
24 bp = PREV_BLKP(bp);
25 PUT(HDRP(bp), PACK(size, 0));
26 PUT(FTRP(bp), PACK(size, 0));
27 }
28 // 前后内存块均空闲
29 else if (!pre_alloc && !next_alloc) {
30 del(NEXT_BLKP(bp));
31 del(PREV_BLKP(bp));
32 size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(HDRP(NEXT_BLKP(bp)));
33 bp = PREV_BLKP(bp);
34 PUT(HDRP(bp), PACK(size, 0));
35 PUT(FTRP(bp), PACK(size, 0));
36 }
37
38 // 插入更新后的 bp 内存块
39 ins(bp);
40 // fprintf(stderr, "coalesce %#p end\n", bp);
41 return bp;
42}
切割就是在需要使用空闲块的时候，将一个空闲块切割成需要的已分配块，和新的空闲块。因为空闲块的大小至少为4，因此如果空闲块大小和需要分配的大小之差小于4，我们直接将整个空闲块分配掉，否则需要切割出来。
1// 分割块
2void place(void *bp, size_t size) {
3 size_t bsize = GET_SIZE(HDRP(bp));
4 del(bp);
5 if (bsize - size >= 4 * WSIZE) {
6 PUT(HDRP(bp), PACK(size, 1));
7 PUT(FTRP(bp), PACK(size, 1));
8 bp = NEXT_BLKP(bp);
9 PUT(HDRP(bp), PACK(bsize - size, 0));
10 PUT(FTRP(bp), PACK(bsize - size, 0));
11 ins(bp);
12 }
13 else {
14 PUT(HDRP(bp), PACK(bsize, 1));
15 PUT(FTRP(bp), PACK(bsize, 1));
16 }
17}
寻找空闲块
1// 寻找空闲块
2void *find_fit(size_t size) {
3 for (int list = getlist(size); list < 20; ++list) {
4 for (void *bp = GET_HEAD(list); bp; bp = GET_NEXT(bp)) {
5 // 找到第一个满足条件的块
6 if (GET_SIZE(HDRP(bp)) >= size) {
7 return bp;
8 }
9 }
10 }
11 return NULL;
12}
核心
动态内存分配的核心函数包括mm_malloc，mm_free和mm_realloc。
分配
mm_malloc函数
1void *mm_malloc(size_t size)
2{
3 // 忽略异常请求
4 if (size == 0) {
5 return NULL;
6 }
7
8 // 分配器必须调整请求块的大小，从而为头部和脚部留有空间，
9 // 满足双字对齐的要求
10
11 if (size <= DSIZE) {
12 size = 2 * DSIZE;
13 }
14 else {
15 size = size + DSIZE;
16 }
17 size = (size + DSIZE - 1) / DSIZE * DSIZE;
18
19 // 寻找空闲块
20 void *bp = find_fit(size);
21 if (bp != NULL) {
22 place(bp, size);
23 return bp;
24 }
25
26 // 未找到空闲块，则分割新的内存空间
27 if ((bp = extend_heap(MAX(size, CHUNKSIZE) / WSIZE)) == NULL) {
28 return NULL;
29 }
30 place(bp, size);
31 return bp;
32}
释放
mm_free函数比较简单，将这个块的头部、脚部标记为空闲块，调用coalesce合并空闲块并插入链表即可。
mm_free函数
1void mm_free(void *ptr)
2{
3 // 忽略异常请求
4 if (ptr == NULL) {
5 return;
6 }
7 size_t size = GET_SIZE(HDRP(ptr));
8
9 // 将这个块的头部、脚部标记为空闲块
10 PUT(HDRP(ptr), PACK(size, 0));
11 PUT(FTRP(ptr), PACK(size, 0));
12
13 // 释放后检查能否合并
14 coalesce(ptr);
15}
再分配
1void *mm_realloc(void *ptr, size_t size)
2{
3 void *oldptr = ptr;
4 void *newptr;
5 size_t copySize;
6
7 newptr = mm_malloc(size);
8 if (newptr == NULL)
9 return NULL;
10 copySize = GET_SIZE(HDRP(ptr));
11 if (size < copySize)
12 copySize = size;
13 memcpy(newptr, oldptr, copySize);
14 mm_free(oldptr);
15 return newptr;
16}
总结
本次的动态内存分配实验是对链表这种数据结构的一次具体应用，让我体会到链表和指针在执行内存管理任务时的巨大作用，同时我也感受到C语言因具有指针这种特殊数据类型而相较于其他高级语言展现出无可比拟的优势。
在实验中，我多次参考了书本上的案例，但同时也发现其代码存在的不健壮性。这提醒我在编写程序时应学会与时俱进，及时修改可能出现的漏洞和错误，才能保证程序在多种条件下依然能够正常运行。