Malloc Lab 全过程纪实

本文最后更新于 1 年前，文中所描述的信息可能已发生改变。

完整代码见 Elkeid-me/csapp-3e-malloc-lab

前言 ​

众所周知：

1. ICS 是 P 大信科最充实的一门课，5 学分的课程中蕴含着 10 学分的知识；
2. 传言称 Malloc Lab 是最难的 lab；
3. 在 2022 年的秋季学期，P 大又特意增加了难度，某位助教去年满分的代码在今年只能拿到 94 分（悲）。

我想，开一篇博客记录 Malloc Lab 的全过程，是极有必要的。

什么是 Malloc Lab？ ​

你需要在一个虚拟堆上构建动态内存分配器。虚拟堆从 0x8'0000'0000 起始。最大大小为 4GB。你分配的指针必须是 8 字节对齐的。

11 月 26 日之前 ​

这段时间主要看教材 CS: APP 第九章，以及网上的教程。尝试从 Github 复制了几份代码，包括然而跑不起来（悲）。

11 月 26 日 ~ 11 月 30 日 ​

本来 27 号要去参加 Linux 社的 TeXmacs 沙龙（然后批判一番 TeXmacs），然而被史纲的短剧耽误了。这几天主要做全局的设计，间或写点测试的代码。主要讨论以下的问题：

1. 使用什么方案？显式空闲链表+分离适配。（原计划是写完链表版本之后搞个红黑树版本，但是鸽了）。
2. 块的布局是什么样的？
   • 首先是 4 字节的块大小，即块的头部. 即便 Malloc Lab 运行在 x86-64 处理器上，但是根据 Write up，总的堆大小和每次申请的块大小不会超过 4 GB，显然 32 位整数足矣。
   • 鉴于块大小都是 8 字节对齐的，块的头部可以空出 3 位，用于标记。标记位有三：
     1. flag 1：标志这个块是否空闲
     2. flag 2：标志上一个块是否空闲
     3. flag 3：备用
   • block_ptr 指向上述头部之后。也就是说，如果要将某个空闲块分配出去，那么 return block_ptr 即可。
   • prev offset 和 next offset。实际上就是链表中的前驱和后继指针。那为什么叫 offset 呢？
     • 原本的计划是，这两个 offset 存储前驱和后继节点的 block_ptr 相对自己 block_ptr 的偏移。例如，块 A 的地址是 0x8'0000'0008，块 B 的地址是 0x8'0000'0018，且 B 是 A 的后继。那么，A 的 next offset 就是 0x8'0000'0018 - 0x8'0000'0008 = 0x10。
     • 但是这样比较难实现，因为偏移量不一定是正数。这意味着我要在 4 字节空间里存储 $-2^{32}$ ~ $2^{32}$ 的整数。当然，这个整数是对齐到 8 的。不是不能做，但是难做。
     • offset 直接存储相对堆的基址针的偏移。对于上述的 A 和 B，A 的 next offset 直接存储 0x8'0000'0018。
   • 块的尾部。只存储 size。剩余 3 个标记位备用。
   • 可以看到，块的大小一定是 8 字节的倍数，且块最小为 16 字节。

          +----------------------+
          | 31 30 29 ... 3 2 1 0 |
     ---- +---------------+------+
      ^   |     size      | flag |
      |   +---------------+------+  <-- A block_ptr, aligned to 8 bytes.
      |   |     prev offset      |      It's the return value of malloc.
      |   +----------------------+
     size |     next offset      |
      |   +----------------------+
      |   |       ......         |
      |   +---------------+------+
      v   |     size      | flag |
     ---- +---------------+------+

3. 链表如何分类？按大小分类废话。但是具体的分类方式是什么？
   • 曾有大佬以统计学方法分析测试样例后，给出了一个非常复杂的分类方法：
     c

     size_t get_index(unsigned int size)
     {
         if (size < ...)
             return ...;
         else if (size < ...)
             return ...;
         ...
         else
             return ...;
     }

   • 我使用直接按 2 的次幂分类。即 16 ~ 31 分一类，32 ~ 63 分一类……我只分 16 类，那么最后一类是 $2^{19}$ ~ $2^{32} - 1$。
   • 上述分类是倒着的，即链表 15 对应块大小 16 ~ 31，链表 14 对应块大小 32 ~ 63……链表 0 对应 $2^{19}$ ~ $2^{32} - 1$
   • 如何根据块的大小 $S$ 找到对应的链表？这其实是一个从整数 $\\{16, 17, \dots, 2^{32} - 1\\}$ 到链表 $\\{0, 1, \dots, 15\\}$ 的映射问题。我使用了两阶段的查找方法。
     1. 第一阶段，计算 $i(S) = 31 - \lfloor \log_2 S \rfloor$。这个映射的值域为 $\\{0, 1, \dots, 27\\}$。这个式子看似复杂，实际上就是 $S$ 的 32 位二进制表示的前导零个数，可以直接通过一条 lzcnt 指令计算，速度非常快。
     2. 第二阶段，根据 $i(S)$ 查表 void *list_ptrs[28]。其中：
     c

     list_ptrs[0] = 指向链表 0 的指针;
     list_ptrs[1] = 指向链表 0 的指针;
     ......
     list_ptrs[12] = 指向链表 0 的指针;
     
     list_ptrs[13] = 指向链表 1 的指针;
     list_ptrs[14] = 指向链表 2 的指针;
     ......
     list_ptrs[25] = 指向链表 13 的指针;
     list_ptrs[26] = 指向链表 14 的指针;
     list_ptrs[27] = 指向链表 15 的指针;

   • 例如，对于 $S = 114$，我们计算出 $i(114) = 25$，然后查表得到 114 对应的链表为链表 13。
   • 记上述查找方法为 $\mathrm{getlist}(S)$
4. malloc 和 free 的时候做什么？
   • $\mathrm{malloc}(S)$
     1. 因为块包含了 4 字节的头部，块的大小一定是 8 字节的倍数。所以，需要对 $S$ 加 4，并向上对齐到 8 的倍数，即 $f(s) = \mathrm{bitnot}(8) \& (s + 4 + 7)$。又因为块最小为 16 字节，最终得出 align(s) = f(s) > 16? f(s), 16。
     2. 从链表 $\mathrm{getlist}(\mathrm{align}(S))$ 开始查找，寻找第一个比 align(s) 大的块。如果这个链表找不到，那么去寻找含有更大块的链表。如果所有链表里都没有，那么在堆尾申请一块空闲块。申请空闲块的大小是一个特殊参数，记为 CHUNK_SIZE。
     3. 记 2. 中找到的空闲块，或者堆尾申请的空闲块大小为 $Z$。在 $Z$ 中切分出 $\mathrm{align}(S)$ 大小的空闲块 block，修改 block 的 flag 1，返回其 block_ptr。而剩余 $Z - \mathrm{align}(S)$ 空间插入到恰当的空闲链表。
   • $\mathrm{free}(p)$
     1. 对于指针 $p$，查找其对应头部中的大小 $s$。
     2. 根据 $p + s$ 找到位置上相邻的下一个块。通过下一个块的 flag 1 判断其是否空闲。
     3. 根据 flag 2 判断位置上相邻的上一个块是否空闲。如果上一个块空闲，那么 *(unsigned int *)((char *)p - 8) 对应着上一个块的大小。
     4. 将上述所有空闲块合成一个大的空闲块，插入到恰当的链表中。
5. malloc 和 free 都提到了插入链表的过程。那怎么插入呢？
   • 一开始我希望按大小排序，但是性能堪忧。
   • 后来直接 FIFO 摆烂了。

12 月 1 日 ​

写了第一个版本，然后炸掉了。

12 月 4 日 ​

重构后的版本。

下面我会列出每一次提交。注意所有的 util 和 kops 是取整的，这就导致有些时候 util 看起来完全相同，但分数不同。

1. 单个显式链表，插入时按大小排序。util 90%，kops 452
2. 单个显式链表，插入时 FIFO。89%，10262。
3. 显式分离链表。90%，13494.
4. 相比上一次提交去掉了运行时断言，把所有的 char * 改为 void * 规避编译器警告，写完了 checkheap（对，之前的版本都没有 checkheap……）。90%，13448.

12 月 5 日 ​

1. 相比上一次提交把 CHUNK_SIZE 从 512 减小为 256 以尝试提高 util，但是失败。90%，10954。
2. 代码与上一次提交完全相同。90%，10953。
3. 这次又把 CHUNK_SIZE 从 256 改回 512。90%，13433。
4. 把 CHUNK_SIZE 从 512 改为 960，意外发现 util 和 kops 都有提高。90%，15594。这证明 CHUNK_SIZE 是一个玄学参数。

12 月 9 日 ​

1. CHUNK_SIZE 从 960 改为 528。malloc 时，从大空闲块切分出小空闲块的算法有更改。原本是在大空闲块头部划分小空闲块；现在是第一次在头部，第二次在尾部，以此类推……这是尝试对某个测试样例做特化。91%，12749。
2. 基本一样的版本。受到评测机性能波动影响。91%，12565。

12 月 10 日 ​

1. CHUNK_SIZE 从 528 改为 1056，直接崩掉。
2. CHUNK_SIZE 从 1056 改为 3704，直接崩掉。
3. 回到 12 月 5 日第 4 次提交的代码。90%，15602。
4. CHUNK_SIZE 从 960 改为 4096，align(size) 增加特化（传入 448 直接返回 520）。91%，18376。
5. 精简代码。91%，18548。

12 月 24 日 ​

修复了 bug。91%，18731

2023 年 1 月 2 日 ​

1. 交错文件了，0 昏
2. 移动了一行代码。91%，18788