Malloc Lab全过程纪实

完整代码见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) \mathrel{\&} (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