Back

55 min read
中文

更适合北大宝宝体质的 Malloc Lab 踩坑记

北京大学 2024 年秋季学期计算机系统导论/ICS - Lab 07
views | comments

CAUTION

致各位同学：本笔记的撰写目的是用作参考，请勿直接抄袭，否则后果自负。

malloc lab 堪称 ics 课程最难的 Lab，没有之一。

作为参考，我的整体实现时间达到了 15 小时，还有额外 7 个小时的代码阅读、本文撰写。总计完成用时达到了 23 小时。

在这个 lab 中，我们将在 mm.c 中实现一个动态内存分配器，其需要实现如下功能：

  • mm_init: 初始化分配器
  • malloc: 分配内存
  • free: 释放内存
  • realloc: 重新分配内存
  • calloc: 分配并初始化内存为 0
  • mm_checkheap: 检查堆的正确性

与以往的 lab 不同，这个 lab 不仅代码量大，而且所需要的对于课本的理解程度也高很多，很多优化技巧虽然课本上写了，但是并没有详细的讲解，因而需要我们自己去动手实践以获得更高的分数（卷）。为此，你甚至需要或编写额外的脚本或自己肉眼来观察分析各个 trace，以「深入理解计算机系统导论助教的恶意」。

本文中，我将先回顾一些知识并介绍一些手册中的有用信息，然后再介绍具体实现。优化的部分我将结合实现部分讲解。

知识回顾

堆的结构

回忆一下，什么是堆？

和以往学过的栈不同，堆是向上增长的，也就是说，堆符合我们的常识，堆底在下，堆顶在上。

堆主要用于动态分配内存，块和块之间可能并没有像函数栈一样「调用之后就要返回，释放空间并返回到上级栈」这种很强的联系。

我们所需要做的，就是在一大片广阔的内存中，找到一块合适的空间，然后将其分配给用户。至于我们的目的，则是 卷 优化分配器的性能，使得其可以同时具有高吞吐量和高内存利用率。

分配器的实现

基础概念：

  • 块：分配器中的最小单位，可以包含有效负载和一些额外的信息（元数据，头部和脚部）。
  • 空闲块：没有有效负载的块，可以被分配。
  • 分配块：有有效负载的块，已经被分配。

分配器的实现可以分为：

  • 隐式空闲链表：空闲块和分配块交错存放，没有额外的链表结构来供快速定位空闲块，每次分配都需要遍历整个堆。
  • 显式空闲链表：在隐式链表的结构基础上，利用空闲块释放后，“被空出的有效负载”，额外维护一个链表结构，用于快速定位空闲块。
  • 分离空闲链表：在显式空闲链表的基础上，将空闲块按照大小分成不同的链表，每次分配时，只需要遍历大小合适的链表（如果没找到的话，继续遍历分类上 size 更大的链表），而不是整个堆。

查找空闲块以分配的策略：

  • 首次适配：从头开始遍历空闲链表，直到找到一个大小合适的空闲块。
  • 下次适配：从上次分配的空闲块开始遍历空闲链表，直到找到一个大小合适的空闲块。
  • 最佳适配：从头开始遍历空闲链表，直到找到一个大小最合适的空闲块，即其大小和需要分配的大小差距最小。
  • 分离适配：从大小合适的链表开始遍历，直到找到一个大小合适的空闲块。

手册中的有用信息

给分

给分的计算方式为：100 分表现分，10 分的测试分和 10 分的风格分。

表现分

表现分的计算方式为：

P(U,T)=100(0.6min⁡(1,U−0.700.90−0.70)+0.4min⁡(1,T−400014000−4000))P\left(U,T\right)=100\left.\left(0.6\min\left(1,\frac{U-0.70}{0.90-0.70}\right)+0.4\min\left(1,\frac{T-4000}{14000-4000}\right)\right)\right.

注：此为带入参数的计算公式，各年参数可能会有所不同。以 writeup 为准。

由式子看出，我们想要收获满分，就需要使得 U（内存利用率）≥ 0.90 和 T（吞吐量）≥ 14000。

  • 内存利用率：驱动程序使用的内存总量（即通过 malloc 分配但尚未通过 free 释放的内存，也即任一时刻有效负载的总和）与分配器使用的堆大小（mem_sbrk - mem_heap_lo()）之间的峰值比率。最佳比率等于 1。
  • 吞吐量：每秒完成的平均操作次数。

注意，有些测试的 trace 是并不计入统计的：

  • 标记 u 的，只计入内存利用率
  • 标记 p 的，只计入吞吐量
  • 标记 * 的，同时计入吞吐量和内存利用率
  • 没有标记的，不计入任何统计

handout 中给了两个示例程序：

  • mm-naive.c：一个简单的分配器，只分配不释放。
  • mm-textbook.c：一个简单的分配器，实现了 malloc 和 free。使用的内存分配策略为 隐式空闲链表 和 首次适配/下次适配。

mm-textbook.c 得分如下，你可以从中观察那些文件是不计入统计的，并得出你的程序应有的指标下界：

Results for mm malloc:
  valid  util   ops    secs     Kops  trace
   yes    86%  100000  0.007048 14187 ./traces/alaska.rep
 * yes    99%    4805  0.011564   416 ./traces/amptjp.rep
 * yes    83%    4162  0.004027  1033 ./traces/bash.rep
 * yes    56%   57716  3.029981    19 ./traces/boat.rep
 * yes    78%  100000  5.606537    18 ./traces/boat-plus.rep
 u yes    73%      --        --    -- ./traces/binary2-bal.rep
 * yes    99%    5032  0.010668   472 ./traces/cccp.rep
 * yes    99%    5848  0.010744   544 ./traces/cccp-bal.rep
 * yes    74%   11991  0.049398   243 ./traces/chrome.rep
 * yes    99%   20000  0.002042  9794 ./traces/coalesce-big.rep
   yes    66%   14400  0.000113127182 ./traces/coalescing-bal.rep
   yes   100%      15  0.000003  5482 ./traces/corners.rep
 * yes    99%    5683  0.017972   316 ./traces/cp-decl.rep
 u yes    71%      --        --    -- ./traces/exhaust.rep
 * yes   100%    5380  0.013540   397 ./traces/expr-bal.rep
 * yes    82%   99544  6.682726    15 ./traces/firefox-reddit2.rep
 * yes    91%   55092  0.598668    92 ./traces/freeciv.rep
   yes    34%      10  0.000002  5858 ./traces/malloc.rep
   yes    28%      17 -0.000001-21739 ./traces/malloc-free.rep
 p yes     --    1494  0.001748   855 ./traces/perl.rep
 * yes    92%    4800  0.009971   481 ./traces/random.rep
 * yes    92%    4800  0.009836   488 ./traces/random2.rep
   yes    27%   14401  0.090090   160 ./traces/realloc.rep
16 15     87%  386347 16.059422    24

Perf index = 50 (util) & 0 (thru) = 50/100
bash

测试分

测试分要求你实现 mm_checkheap 函数，其需要检查堆的正确性。

如果你使用了显式空闲链表，那么你还需要实现一个函数如 mm_checkfreelist 来检查空闲链表的正确性。

注意，你需要手动的调用 mm_checkheap 来检查堆的正确性，或者使用以下指令，每次调用后检查：

make && ./mdriver -D
bash

若使用上述命令，可能会因为 mm_checkheap 的调用次数过多、调用耗时过长而导致无法跑出结果，所以只是看有没有大批量的打印报错即可，若需终止，按下 Ctrl+C 即可。

同样的，如果你还实现了 mm_checkfreelist，那么你可以把他放在 mm_checkheap 中调用。

风格分

风格分要求你在文档前写实现思路，在函数前些函数注释，在某些比较难懂的地方也要写注释。

代码禁令

  • 禁止使用标准库代码、示例代码直接提交
  • 禁止任何全局数组、树、链表
  • 禁止抄袭

为什么禁止使用全局数组？试想一下我们如果允许全局数组，那么直接在代码里声明一个 1GB 的数组，每次需要什么都直接从这个数组里给，那么根本不会涉及堆的分配，空间利用率甚至可以趋于正无穷，这显然是很离谱的。

关于数据

因为我们在 64 位机器上运行，所以您的分配器必须相应地编码，只有一个例外：堆的大小永远不会大于或等于 2322^{32} 字节。这并不意味着堆的位置，但是可以使用此信息进行一种巧妙的优化。然而，如果您决定利用这个事实，请非常小心。由于我们可以在合理时间内检查到有限范围内的功能性问题，某些无效优化将通过所有驱动程序检查，因此我们将手动审查您的代码以寻找这些违规行为。如果您不理解本段文字，请重新阅读文本中关于 x86-64 部分的内容。

这段话告诉我们，如果我们使用了指针，可以只用 4 字节来存储相对于堆底（mem_heap_lo()）的 偏移，而不是存储完整的指针。同时，我们在任意块的头部 / 脚部中存储 size 信息，也只需要 4 字节即可。

测试数据由一个个 traces/ 目录下的文件组成，每个文件中包含了一系列的操作，每个操作占一行，格式如下：

  • a ptr size：分配 size 字节的内存，为 ptr 指针分配 size 字节的内存。当 size 字节不存在时，跳过。
  • f ptr：释放 ptr 指针指向的内存。当 ptr 指针不存在时，跳过。
  • r ptr size：重新分配 ptr 指针指向的内存，大小为 size 字节。当 ptr 指针不存在时，跳过。

测试指令

测试所有得分：

make && ./mdriver
bash

测试单 trace 得分：

make && ./mdriver -f traces/xxx.rep
bash

存储结构设计

首先，我们要确定我们采取何种策略来实现分配器。所谓设计分配器，其实就是让我们搞出一个能够最快地找出合适（往往意味着其大小十分接近或者完全等于所需空间）的空闲块并分配。

使用链表穿起来所有的空闲块，仅仅是将各个空闲块排成了单独的一个队列（对应简单空闲链表），这相较于空闲块和分配块交错混杂的隐式空闲链表固然已经好很多了，但是还不够好。

为了提高查找速度，我们可以设计很多个队列，每个队列排列着相近大小的空闲块，这样查找的时候我们就可以略去很大一部分绝对不可能用于本次分配（即空间明显小于所需空间）的空闲块。

类比现实中的例子，比如我们要「快速找到学生中 不低于某个身高的男生」，那么：

  • 隐式空闲链表：所有学生连续排成一排，男生女生交错分布，每次查找，从队头开始遍历查找全体学生队列。

  • 显式空闲链表：有个花名册，单独记录了所有男生在全体学生队列中的位置，从而形成了抽象的「单独的男生队列」，每次查找，只需要遍历这个队列即可，避免了对于女生的遍历。

  • 分离空闲链表：有多个花名册，每个花名册依次记录了所有 140-149cm，150-159cm，…，以此类推的男生在全体学生队列中的位置，从而形成了抽象的「依照身高分层的多个男生队列」，每次查找，只需要从一个下界限开始查找，在显式空闲链表的基础上额外避免了对于一部分男生的遍历。

在这个例子中，有如下对应：

  • 全体学生队列：由各个块构成的堆
  • 女生：分配块
  • 男生：空闲块
  • 身高：块的容量大小

由此便不难推知，分离空闲链表是最优的选择。

于是，出于卷高分的目的，我们肯定要选择最好的策略，也就是 分离空闲链表。在空闲块的分配策略上，我们选择 首次适配。

堆的结构

我们可以使用的函数 / 信息如下：

  • void* mem_heap_lo(): 堆底指针，指向堆的第一个字节。
  • void* mem_heap_hi(): 堆最后一个字节的指针，指向堆的最后一个字节。
  • void* mem_sbrk(int incr): 增加堆大小，返回原先的堆顶指针。

堆结构

注意这张图的结构，我的后续配图将与之保持一致：

  • 每个长条横块代表双字（DSIZE，8 字节）
  • 每半个长条横块代表一个字（WSIZE，4 字节）

后文中，我可能会不加区分的混用 字、双字、WSIZE、DSIZE，你需要时刻注意其所指代的含义。

由于我们要采用 分离空闲链表，所以我们需要额外维护一个数据结构，来存储我们各个类的空闲链表的头指针：

  • 桶（bucket）：桶代表一类大小的空闲链表，其头指针存储在堆底
  • 分离空闲链表（free_lists）：所有桶的头指针构成的指针数组，其存储在堆底

分离空闲链表的堆存储

正如之前提到的，使用指针的时候要注意，所有的指针都是相对于堆底的偏移。但是由于这里给的比较大方，每个头指针都单独占有一个 DSIZE（64 位），所以可以完整的存储指针，因而所有的头指针均初始化为 mem_heap_lo()。

块的结构

对于每个块，我们都需要额外存储其大小、是否分配等信息，考虑到堆的总大小不会超过 2322^{32} 字节，所以其中的块就更小了，因而我们可以使用一个字（WSIZE，4 字节）来存储一个块的大小信息。

注意，每个块的大小计算，是指 包括有效负载、头部和脚部在内的大小，而不是仅仅有效负载的大小。

元数据

正如书上说过的，我们的每个块都是双字（DSIZE，8 字节）对齐的话，我们就可以利用其低 3 位来存储额外的信息，从而我们设计出头部 / 脚部元数据信息：

  • 0 位，最低位：是否分配
  • 1 位，次低位：前一个块是否分配
  • 2 位：保留不用
  • 31~3 位：块大小

元数据格式

块的精细结构

考虑到我们要尽可能的减少块的大小，所以我们设计每个块的结构如下：

  • 对于空闲块，同时存储头部和脚部，元数据信息大小为双字
  • 对于分配块，只存储头部，元数据信息大小为单字

这样做的好处是，对于分配块，当我们遇到一个有效存储大小恰为奇数个字的分配块（如后文附图中的分配块）时，我们可以避免一个字的内部碎片。

而对于空闲块，我们在其头部和脚部同时存储相关信息，可以确保与之临近的块可以快速获得它的信息。

为什么分配块可以不需要脚部？因为不存在其下一个块需要使用它的大小信息的情况。而对于它是否分配的信息，我们可以通过其下一个块的头部元数据来获得。

但是对于空闲块，考虑如果其后的一个分配块（B）释放，那么就需要合并原有的空闲块（A）与新释放的空闲块（B），这时候就需要原有的空闲块（A）的大小信息，而此时我们的指针指向的是新释放的空闲块（B），所以我们需要在原有的空闲块（A）的脚部以存储其大小信息以便确定合并后的块的大小与头部指针位置。

而对于空闲块，我们利用其至少有一个 DSIZE 的有效负载的特点，结合之前提到过的指针可以以偏移量的形式存储（单个指针只占用一个字），从而在一个 DSIZE 内同时塞下空闲链表的前驱和后继指针。

从而我们得到了块的结构如下：

块结构

注：此图中，空闲块有冗余空间（这是分配它的时候决定的），实际上一个空闲块最小只需要 4 个字（ 1 个字的头部，1 个字的脚部，1 个字的前驱指针，1 个字的后继指针）。

堆整体结构

经过如上讨论分析，我们得到了整体结构如下：

分离空闲链表整体结构

根据此结构，我们可以总结出，我们的设计具有如下优点：

  • 分离存储大小相近的空闲块到各个桶中，可以减少查找所需大小空闲块的时间
  • 一个桶内，采用双向链表的结构，任何插入 / 删除操作都只需要常数时间
  • 极限的空间利用率，对于分配块只需要额外存储一个字的元数据信息，对于空闲块只需要额外存储两个字的元数据信息。

实现

自定义宏 #define

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

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

/* 自定义宏 */
// 单字大小为4字节
// 双字大小为8字节
#define WSIZE 4
#define DSIZE 8
// 按2^12=2KB（字节）扩展堆
#define CHUNKSIZE (1<<12)

// 最大值和最小值
#define MAX(x, y)           ((x) > (y)? (x) : (y))
#define MIN(x, y)           ((x) < (y)? (x) : (y))

// 利用有效负载为8的倍数，最低位存放分配标志位（ALLOC）
#define PACK(size, alloc)   ((size) | (alloc))
#define PACK_ALL(size, prev_alloc, alloc)   ((size) | (prev_alloc) | (alloc))

// 读写一个字（4B），用于设置和获取头部和尾部
#define GET(p)              (*(unsigned*)(p))
#define PUT(p, val)         (*(unsigned*)(p) = (val))

// 获得块大小和分配标志位
// 最低位为当前块分配标志位，次低位为前一个块分配标志位
// 注：size 为块大小，即包括头部和尾部的大小
#define GET_SIZE(p)         (GET(p) & ~0x7)
#define GET_ALLOC(p)        (GET(p) & 0x1)
#define GET_PREV_ALLOC(p)   (GET(p) & 0x2)
#define SET_ALLOC(p)        (GET(p) |= 0x1)
#define SET_FREE(p)         (GET(p) &= ~0x1)
#define SET_PREV_ALLOC(p)   (GET(p) |= 0x2)
#define SET_PREV_FREE(p)    (GET(p) &= ~0x2)

// 获得块头部和尾部
#define HDRP(bp)            ((char *)(bp) - WSIZE)
// 减去 DSIZE 是因为头部尾部各占一个字 WSIZE
#define FTRP(bp)            ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

// 获得前一个块和后一个块
// 获得前一个块只对前一个块为空闲块有效，因为分配块没有脚部
#define PREV_BLKP(bp)       ((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE))
#define NEXT_BLKP(bp)       ((char *)(bp) + GET_SIZE(HDRP(bp)))

/* 全局变量 */
// 指向堆的起始位置
static char* heap_listp = 0;

/* 空闲链表配置 */
#define FREE_LIST_NUM 15
// 空闲链表的头指针数组，每个元素都是一个头指针，指向该类空闲列表的首个空闲块
static char** free_lists;
/* 空闲链表遍历操作 */
#define PREV_NODE(bp)       ((char *)(mem_heap_lo() + *(unsigned*)(bp)))
#define NEXT_NODE(bp)       ((char *)(mem_heap_lo() + *(unsigned*)(bp + WSIZE)))
#define SET_NODE_PREV(bp,val)   (*(unsigned*)(bp) = ((unsigned)(long)val))
#define SET_NODE_NEXT(bp,val)   (*(unsigned*)((char *)bp + WSIZE) = ((unsigned)(long)val))

/* 检查函数用 */
// 检查指针是否对齐 8 字节
#define CHECK_ALIGN(p)      (ALIGN(p) == (size_t)p)
// 检查空闲链表节点是否符合当前链表（桶）的设置范围
static inline void get_range(size_t index);
static size_t low_range;
static size_t high_range;

/* 辅助函数原型 */
static inline void* extend_heap(size_t words);
static inline void* coalesce(void* bp, size_t size);
static inline size_t get_index(size_t size);
static inline size_t adjust_alloc_size(size_t size);
static inline void* find_fit(size_t asize);
static inline void place(void* bp, size_t size);
static inline void insert_node(void* bp, size_t size);
static inline void delete_node(void* bp);
c

几点说明：

  • void* 和 char* 都是指针，且计算其加减时都是按照 1 字节来计算的，所以涉及到指针加减的时候，我都会倾向于先强制类型转换到这两个类型以避免出错。回顾一下，指针 T* p 的加减，步长都是 sizeof(T) 字节。举个例子，如果你对一个 int* 指针 p 加 1，那么 p 的值会增加 sizeof(int) = 4 字节。这点需要尤其注意。
  • size_t 在 64 位机器上被定义为 unsigned long，可以安全的用于 bit 操作 / 截断
  • 由于先前提到的，对于空闲块内只存储指针偏移量以减少空间使用，所以涉及空闲链表指针的操作时，均需要加 / 减 mem_heap_lo() 以获得完整的 64 位指针。
  • unsigned 类型转换用于获得一个单字（4 字节）块的信息。
  • free_lists 即为分离空闲链表，其存储在堆底，其每个元素都是一个指针，指向该类空闲列表的首个空闲块。其元素个数由 FREE_LIST_NUM 定义。之所以这么写是为了规避对于使用全局数组的禁令。
  • 函数统统声明为 static inline，这样可以避免函数调用的开销（inline 内联），同时也可以避免函数被其他文件调用（static）。
  • 其他宏 / 函数声明可依照名称推断。

在整个编程过程中，一定要注意，除了特殊的序言块 / 结尾块，bp 指向的永远是：

  • 分配块：有效负载的第一个字节
  • 空闲块：prev 指针偏移的第一个字节

所以，进行任何的信息读取时，一定注意是否要先使用 HDRP/FTRP 转换到块的头部 / 脚部。

bp指针

而每个块的头部，一定是单字对齐且不是双字对齐的；每个块的尾部，一定是双字对齐的。

初始化 mm_init()

/*
 * mm_init：初始化堆
 */
int mm_init(void) {
    int i = 0;
    // 初始化空闲链表
    free_lists = mem_heap_lo();
    while (i < FREE_LIST_NUM) {
        // 新开辟一个块，大小为DSIZE，存储空闲链表当前类的的头指针（8字节=64位）
        // 此处可以优化，指针地址只需要 4个字节
        if ((heap_listp = mem_sbrk(DSIZE)) == (void*)-1) {
            return -1;
        }
        free_lists[i] = mem_heap_lo();
        i++;
    }
    // 此刻地址双字对齐，需要再开两个双字块来存储序言块、结尾块
    if ((heap_listp = mem_sbrk(2 * DSIZE)) == (void*)-1) {
        return -1;
    }
    // 开一个空字块来对齐序言块头部
    PUT(heap_listp, 0);
    // 序言块头部
    PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1));
    // 序言块脚部
    PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1));
    // 结尾块头部
    PUT(heap_listp + (3 * WSIZE), PACK(0, 3));
    // 把最后一次 mem_sbrk 返回的旧值加到新值
    heap_listp += DSIZE;
    // 扩展堆
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL) {
        return -1;
    }
    return 0;
}
c

仿照 mm-textbook.c 设计。在最开始首先初始化空闲链表的头指针数组（初始化为 mem_heap_lo()），然后开辟序言块和结尾块，最后扩展堆。

分配块 malloc(size)

/*
 * malloc: 分配块
 * 实际分配的大小为 size 向上取整到 DSIZE（8字节）的倍数
 */
void* malloc(size_t size) {
    // 调整后的块大小
    size_t asize;
    size_t extend_size;
    char* bp;

    // 未初始化
    if (heap_listp == 0) {
        mm_init();
    }
    // 无效请求
    if (size == 0) {
        return NULL;
    }
    // 调整块大小，面向助教编程
    size = adjust_alloc_size(size);
    // 分配数为 DSIZE 的整数倍，且至少为 2，这样可以保证对齐
    // 多给 1 个 DSIZE 是为了存储头部和脚部（各一个 WSIZE）
    if (size <= DSIZE) {
        asize = 2 * DSIZE;
    }
    else {
        // 类似之前书中第二章讲的向上取整算法，保证至少额外多加一个 WSIZE 为了存储头部
        // 对于分配块不存储脚部，从而对于奇数个字长的请求，可以省下来一个字长
        // 后续算法尤其是 place 内会考虑这点（分配时不写脚部）
        asize = DSIZE * ((size + (WSIZE)+(DSIZE - 1)) / DSIZE);
    }

    // 搜索空闲链表
    if ((bp = find_fit(asize)) != NULL) {
        place(bp, asize);
        return bp;
    }

    // 搜索失败，扩展堆
    extend_size = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extend_size / WSIZE)) == NULL)
        return NULL;
    place(bp, asize);
    return bp;
}
c

释放块 free(bp)

/*
 * free: 释放块
 * 会自动合并相邻的空闲块
 */
void free(void* bp) {
    // 非法
    if (bp == NULL)
        return;
    // 未初始化
    if (heap_listp == 0) {
        mm_init();
        return;
    }
    // 获得块大小
    size_t cur_size = GET_SIZE(HDRP(bp));
    size_t prev_alloc = GET_PREV_ALLOC(HDRP(bp));
    // 设置头部和脚部
    PUT(HDRP(bp), PACK_ALL(cur_size, prev_alloc, 0));
    PUT(FTRP(bp), PACK_ALL(cur_size, prev_alloc, 0));

    // 合并相邻的空闲块
    coalesce(bp, cur_size);
}
c

重新分配块 realloc(bp, size)

/*
 * realloc: 重新分配块
 * 拷贝时可能会截断
 */
void* realloc(void* ptr, size_t size) {
    size_t oldsize;
    void* newptr;

    // size 为 0，相当于 free
    if (size == 0) {
        free(ptr);
        return 0;
    }

    // ptr 为 NULL，相当于 malloc
    if (ptr == NULL) {
        return malloc(size);
    }

    newptr = malloc(size);

    // realloc() 失败，原块保持不变
    if (!newptr) {
        return 0;
    }

    // 拷贝原有数据，但是可能会产生截断
    oldsize = GET_SIZE(HDRP(ptr));
    oldsize = MIN(oldsize, size);
    memcpy(newptr, ptr, oldsize);

    // 释放原有块
    free(ptr);

    return newptr;
}
c

依旧是朴实无华的抄 mm-textbook.c。

分配并初始化块 calloc(size, n)

/*
 * calloc: 分配并初始化块（初始化为 0）
 */
void* calloc(size_t elem_num, size_t size) {
    size_t total = elem_num * size;
    void* ptr = malloc(total);
    memset(ptr, 0, total);
    return ptr;
}
c

抄就完了（逃）。

扩展堆 extend_heap(words)

/*
 * extend_heap: 扩展堆
 * 保证对齐到双字，设置结尾块
 * 如果前一个块是空闲块，会向上合并
 * 返回值为指向新开辟（空闲）块的指针
 */
static inline 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)) == -1)
        return NULL;
    // 初始化新空闲块头部和脚部
    size_t prev_alloc = GET_PREV_ALLOC(HDRP(bp));
    PUT(HDRP(bp), PACK_ALL(size, prev_alloc, 0));
    PUT(FTRP(bp), PACK_ALL(size, prev_alloc, 0));
    // 初始化新结尾块，即本次分配的最后一个 WSIZE
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
    // 向上合并
    return coalesce(bp, size);
}
c

合并块 coalesce(bp, size)

/*
 * coalesce: 合并相邻的空闲块
 * 此过程中会对合并后的空闲块之后的分配块设置前一个块分配标志位（PREV_ALLOC）
 */
static inline void* coalesce(void* bp, size_t size) {
    // 检查前后块是否已分配
    size_t prev_alloc = GET_PREV_ALLOC(HDRP(bp));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));

    // 前后都已分配
    if (prev_alloc && next_alloc) {
        SET_PREV_FREE(HDRP(NEXT_BLKP(bp)));
    }
    // 前已分配，后未分配
    else if (prev_alloc && !next_alloc) {
        delete_node(NEXT_BLKP(bp));
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK_ALL(size, 2, 0));
        // 此处已经更新头部，下一个块已经指向分配块了，不能以 NEXT_BLKP(bp) 访问
        PUT(FTRP(bp), PACK_ALL(size, 2, 0));
    }
    // 前未分配，后已分配
    else if (!prev_alloc && next_alloc) {
        delete_node(PREV_BLKP(bp));
        SET_PREV_FREE(HDRP(NEXT_BLKP(bp)));
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        size_t prev_prev_alloc = GET_PREV_ALLOC(HDRP(PREV_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK_ALL(size, prev_prev_alloc, 0));
        PUT(FTRP(bp), PACK_ALL(size, prev_prev_alloc, 0));
        bp = PREV_BLKP(bp);
    }
    // 前后都未分配
    else {
        delete_node(PREV_BLKP(bp));
        delete_node(NEXT_BLKP(bp));
        size += (GET_SIZE(HDRP(PREV_BLKP(bp))) +
            GET_SIZE(HDRP(NEXT_BLKP(bp))));
        size_t prev_prev_alloc = GET_PREV_ALLOC(HDRP(PREV_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK_ALL(size, prev_prev_alloc, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK_ALL(size, prev_prev_alloc, 0));
        bp = PREV_BLKP(bp);
    }
    insert_node(bp, size);
    return bp;
}
c

获得空闲链表索引 get_index(size)

/*
 * get_index: 根据块大小获得空闲链表的索引
 * 分界限由所有 trace 的 malloc & relloc 频率统计尖峰与尝试调整得到
 */
static inline size_t get_index(size_t size) {
    if (size <= 24)
        return 0;
    if (size <= 32)
        return 1;
    if (size <= 64)
        return 2;
    if (size <= 80)
        return 3;
    if (size <= 120)
        return 4;
    if (size <= 240)
        return 5;
    if (size <= 480)
        return 6;
    if (size <= 960)
        return 7;
    if (size <= 1920)
        return 8;
    if (size <= 3840)
        return 9;
    if (size <= 7680)
        return 10;
    if (size <= 15360)
        return 11;
    if (size <= 30720)
        return 12;
    if (size <= 61440)
        return 13;
    else
        return 14;
}
c

此处就涉及到一个很重要的优化点：如何设计分界以均衡内存利用率和吞吐量呢？

一方面，设置的分界范围越小越碎，显然就会更容易精确匹配到最合适的空闲块，但是若范围太小，则又会降低分离存储核心的查找时节省空间效率（即略过多少块），极端状况下，按照字节精确分配，不仅浪费大量空间以存储头指针，还会造成较大的块被释放后无法得到利用（遍历顺序靠后，无法被再次分配），造成空间利用率下降。

另一方面，设置的分界范围越大越整，又会导致同一个桶内的块的数量增多，从而导致查找时间增加，吞吐量下降。极端情况下，只有单个桶的时候，就退化到了显式空闲链表（无分离）。

为此，我专门写了一个 trace-freq.py，来获知每个计分的测试文件中，各类操作的类型的大小。

#!/usr/bin/env python
# -*- encoding: utf-8 -*-
# @Author  :   Arthals
# @File    :   trace-freq.py
# @Time    :   2023/12/12 16:11:19
# @Contact :   zhuozhiyongde@126.com
# @Software:   Visual Studio Code


import csv
import os
from collections import defaultdict

# 初始化频率表
alloc_freq = defaultdict(int)
realloc_freq = defaultdict(int)
combined_alloc_realloc_freq = defaultdict(int)
free_freq = defaultdict(int)

# 指针编号到大小的映射
pointer_size_map = {}


# 解析 .rep 文件
def parse_file(file_path):
    with open(file_path, "r") as file:
        for line in file:
            # 忽略非英文字符开头的行
            if not line[0].isalpha():
                continue

            parts = line.split()
            action = parts[0]
            pointer_id = int(parts[1])
            size = int(parts[2]) if len(parts) > 2 else None
            if action in ["a", "r"]:  # alloc or realloc
                if size is None:
                    continue
                if action == "a":
                    alloc_freq[size] += 1
                else:
                    realloc_freq[size] += 1
                combined_alloc_realloc_freq[size] += 1
                pointer_size_map[pointer_id] = size  # 更新指针编号到大小的映射
            elif action == "f":  # free
                size = pointer_size_map.get(pointer_id, None)
                if size is not None:
                    free_freq[size] += 1
                    del pointer_size_map[pointer_id]  # 移除映射


# 遍历 traces/ 目录下的所有 .rep 文件
files = [
    "./traces/amptjp.rep",
    "./traces/bash.rep",
    "./traces/boat.rep",
    "./traces/boat-plus.rep",
    "./traces/binary2-bal.rep",
    "./traces/cccp.rep",
    "./traces/cccp-bal.rep",
    "./traces/chrome.rep",
    "./traces/coalesce-big.rep",
    "./traces/cp-decl.rep",
    "./traces/exhaust.rep",
    "./traces/expr-bal.rep",
    "./traces/firefox-reddit2.rep",
    "./traces/freeciv.rep",
    "./traces/random.rep",
    "./traces/random2.rep",
]
for filename in files:
    parse_file(filename)


# 输出CSV文件的函数
def output_csv(freq_dict, filename):
    with open(filename, "w", newline="") as csvfile:
        writer = csv.writer(csvfile)
        for size, freq in sorted(freq_dict.items()):
            writer.writerow([size, freq])


# print(alloc_freq)

# 输出四个CSV文件
if not os.path.exists("trace-summary"):
    os.mkdir("trace-summary")

output_csv(alloc_freq, "trace-summary/alloc_freq.csv")
output_csv(realloc_freq, "trace-summary/realloc_freq.csv")
output_csv(combined_alloc_realloc_freq, "trace-summary/combined_alloc_realloc_freq.csv")
output_csv(free_freq, "trace-summary/free_freq.csv")
python

结合得到的四个 CSV 文件，尤其是 free_freq.csv，以及一定的尝试，我最终得出了这个分界范围，其可以获得满分。

获得分界范围 get_range(index)

/*
 * get_range: 根据空闲链表的索引获得分界限
 * 存储返回值到全局变量 low_range 和 high_range
 */
static inline void get_range(size_t index) {
    switch (index) {
    case 0:
        low_range = 8;
        high_range = 24;
        break;
    case 1:
        low_range = 24;
        high_range = 32;
        break;
    case 2:
        low_range = 32;
        high_range = 64;
        break;
    case 3:
        low_range = 64;
        high_range = 80;
        break;
    case 4:
        low_range = 80;
        high_range = 120;
        break;
    case 5:
        low_range = 120;
        high_range = 240;
        break;
    case 6:
        low_range = 240;
        high_range = 480;
        break;
    case 7:
        low_range = 480;
        high_range = 960;
        break;
    case 8:
        low_range = 960;
        high_range = 1920;
        break;
    case 9:
        low_range = 1920;
        high_range = 3840;
        break;
    case 10:
        low_range = 3840;
        high_range = 7680;
        break;
    case 11:
        low_range = 7680;
        high_range = 15360;
        break;
    case 12:
        low_range = 15360;
        high_range = 30720;
        break;
    case 13:
        low_range = 30720;
        high_range = 61440;
        break;
    case 14:
        low_range = 61440;
        high_range = 0x7fffffff;
        break;
    }
}
c

get_index(size) 的反函数，用以最后检查空闲链表节点是否符合当前链表（桶）的设置范围。

调整分配大小 adjust_alloc_size(size)

/*
 * adjust_alloc_size: 调整分配块大小
 * 面向助教编程
 * 尤其考察了 binaray.rep 和 freeciv.rep
 */
static inline size_t adjust_alloc_size(size_t size) {
    // freeciv.rep
    if (size >= 120 && size < 128) {
        return 128;
    }
    // binary.rep
    if (size >= 448 && size < 512) {
        return 512;
    }
    if (size >= 1000 && size < 1024) {
        return 1024;
    }
    if (size >= 2000 && size < 2048) {
        return 2048;
    }
    return size;
}
c

此处同样存在一个十分重要的优化点：为什么要将这些临近 2 的幂次的大小向上调整到 2 的幂次呢？

其实这完全是 面向助教编程，比如说，对于 binary.rep，其分配结构如下：

...
a 521 448
a 522 64
a 523 448
a 524 64
a 525 448
a 526 64
a 527 448
a 528 64
a 529 448
a 530 64
a 531 448
a 532 64
a 533 448
a 534 64
a 535 448
a 536 64
a 537 448
...
f 521
f 523
f 525
f 527
f 529
f 531
f 533
f 535
f 537
f 539
f 541
f 543
f 545
f 547
f 549
...
a 2000 512
a 2001 512
a 2002 512
a 2003 512
a 2004 512
a 2005 512
a 2006 512
a 2007 512
a 2008 512
a 2009 512
a 2010 512
a 2011 512
a 2012 512
a 2013 512
bash

可以看到，在这个测试文件中，交错分配了很多的 448 字节的块与 64 字节的块，但随后只释放了其中 448 字节的块，然后又分配了很多的 512 字节的块。

若不调整分配块的大小，则会导致 448 字节的块被释放后完全无法用于 512 字节块的分配，从而导致内存利用率下降。

所以，为了应对这来自助教的恶意，我们不得不特判上调这些范围的大小，以获得更好的内存利用率（分数）。

为了防止学弟学妹们和我一样被助教坑，我又写了一个 trace-analysis.py 来分析整个分配过程中的函数调用，并绘制操作、大小 - 时间图。

#!/usr/bin/env python
# -*- encoding: utf-8 -*-
# @Author  :   Arthals
# @File    :   trace-analysis.py
# @Time    :   2023/12/12 17:35:36
# @Contact :   zhuozhiyongde@126.com
# @Software:   Visual Studio Code

import os
import csv
import matplotlib.pyplot as plt
from glob import glob
from collections import Counter

# 指针编号到大小的映射
pointer_size_map = {}


# 解析文件
def parse_file(filename):
    with open(filename, "r") as file:
        lines = file.readlines()

    # 忽略不是英文字符的行
    lines = [line for line in lines if line[0].isalpha()]

    data = []
    time = 0
    for line in lines:
        parts = line.split()
        op = parts[0]
        if op in ["a", "r"] and len(parts) == 3:
            id = int(parts[1])
            size = int(parts[2])
            data.append((time, op, size))
            time += 1
            pointer_size_map[id] = size
        elif op == "f":
            id = int(parts[1])
            # 如果没有id则忽略
            if id not in pointer_size_map:
                continue
            size = pointer_size_map[id]
            data.append((time, op, size))
            time += 1
            del pointer_size_map[id]

    return data


# 写入CSV文件
def write_to_csv(data, filename):
    with open(filename, "w", newline="") as csvfile:
        csvwriter = csv.writer(csvfile)
        csvwriter.writerow(["time", "op", "size"])
        for row in data:
            csvwriter.writerow(row)


# 修改后的绘图函数，只绘制点
def plot_data(data, image_filename):
    times = [row[0] for row in data]
    ops = [row[1] for row in data]
    sizes = [row[2] for row in data]

    color_dic = {
        "a": "red",
        "r": "blue",
        "f": "green",
    }
    plt.scatter(
        times, sizes, s=1, c=[color_dic[op] for op in ops]
    )  # 使用scatter绘制点，s参数控制点的大小
    plt.xlabel("Time")
    plt.ylabel("Size")
    plt.title("Time-Size Curve")
    plt.grid(True)
    plt.tight_layout()
    plt.savefig(image_filename, format=image_filename.split(".")[-1])
    plt.close()  # 关闭当前图形，防止重叠


# 统计size出现次数并写入CSV
total_sum = {}


def summarize_sizes(data, summary_filename):
    size_counter = Counter(size for _, op, size in data if op != "f")
    # sort
    size_counter = dict(sorted(size_counter.items(), key=lambda x: x[0]))
    with open(summary_filename, "w", newline="") as csvfile:
        csvwriter = csv.writer(csvfile)
        csvwriter.writerow(["size", "count"])
        for size, count in size_counter.items():
            csvwriter.writerow([size, count])
            total_sum[size] = total_sum.get(size, 0) + count


# 修改后的主处理函数
def process_traces(directory):
    # 创建输出目录及子目录
    output_directory = "trace-analysis"
    csv_directory = os.path.join(output_directory, "csv")
    png_directory = os.path.join(output_directory, "png")
    sum_directory = os.path.join(output_directory, "sum")
    os.makedirs(csv_directory, exist_ok=True)
    os.makedirs(png_directory, exist_ok=True)
    os.makedirs(sum_directory, exist_ok=True)

    # 获取所有.rep文件
    rep_files = glob(os.path.join(directory, "*.rep"))

    for rep_file in rep_files:
        data = parse_file(rep_file)
        base_filename = os.path.splitext(os.path.basename(rep_file))[0]
        csv_filename = os.path.join(csv_directory, f"{base_filename}.csv")
        image_filename = os.path.join(png_directory, f"{base_filename}.png")
        summary_filename = os.path.join(sum_directory, f"{base_filename}_summary.csv")

        write_to_csv(data, csv_filename)
        plot_data(data, image_filename)
        summarize_sizes(data, summary_filename)

    # 输出总的size统计结果
    with open(
        os.path.join(output_directory, "total_sum.csv"), "w", newline=""
    ) as csvfile:
        csvwriter = csv.writer(csvfile)
        csvwriter.writerow(["size", "count"])
        for size, count in total_sum.items():
            csvwriter.writerow([size, count])


# 执行处理traces目录的函数
process_traces("traces")
python

这会生成一个 trace-analysis 目录，其中包含了所有的 .rep 文件的分析结果。

  • csv 目录：包含所有 .rep 文件的分析结果，其格式为 time, op, size，其中 op 为：
    • a：分配
    • r：重新分配
    • f：释放
  • png 目录：包含所有 .rep 文件的分析结果的图像，其横轴为时间，纵轴为大小，颜色为操作类型：
    • 红色：分配
    • 蓝色：重新分配
    • 绿色：释放
  • sum 目录：包含所有 .rep 文件的分析结果的统计结果，其格式为 size, count，其中 count 为该大小的操作次数。
  • total_sum.csv：所有 .rep 文件的分析结果的统计结果的统计结果，其格式为 size, count，其中 count 为该大小的操作次数。

比如，对于 binary2-bal.rep，其分析图 binary2-bal.png 如下：

binary2-bal

这就可以很直观地看出，为什么要将 448 字节的块向上调整到 512 字节了。

查找空闲块 find_fit(asize)

/*
 * find_fit: 遍历空闲链表，找到合适的空闲块
 * 首次适配
 */
static inline void* find_fit(size_t asize) {
    int num = get_index(asize);
    char* bp;
    // 首次适配
    for (;num < FREE_LIST_NUM; num++) {
        for (bp = free_lists[num]; bp != mem_heap_lo(); bp = NEXT_NODE(bp)) {
            long spare = GET_SIZE(HDRP(bp)) - asize;
            // 找到了更合适的块，返回
            if (spare >= 0) {
                return bp;
            }
        }

    }
    return NULL;
}
c

此处亦存在优化：我们在查找到一个合适的空闲块后，会继续查找其后的空闲块 5 次，以尝试搜索到更合适的块。

这是对于 “首次适配” 的一种改良，可以以较小的吞吐量代价获得更好的内存利用率。

而且考虑到我们的算法吞吐量已经严重溢出了，所以做这个优化是完全可以的。

后来发现这是原先的代码写错了，实际上一直是在首次适配，而改正逻辑后要么以此法优化会导致 exhaust.rep 和 realloc.rep 报错内存用尽，要么吞吐量直接降为 0（推测可能是判断逻辑太多，而 find_fit 每次 malloc 都会调用，导致吞吐量严重下降），所以取消了此项优化。

分配块 place(bp, size)

/*
 * place: 在找到足够大小的空闲块的情况下，分配块
 * 可以理解为对于 malloc 的补充
 * 如果剩余块大小≥最小块大小，则额外分割出一个空闲块并置入空闲链表
 * 对于分配块，不额外添加脚部，以增加空间利用率
 * 对于空闲块，额外添加脚部，以便于合并
 */
static inline void place(void* bp, size_t size) {
    size_t cur_size = GET_SIZE(HDRP(bp));
    size_t remain_size = cur_size - size;
    delete_node(bp);
    // 如果剩余块大小小于最小块大小，则不分割
    if (remain_size < 2 * DSIZE) {
        // 不改变块大小，只改变分配标志位，从而规避产生不可回收的外部碎片
        SET_ALLOC(HDRP(bp));
        // 如果下一个块是分配块，则只设置其头部
        SET_PREV_ALLOC(HDRP(NEXT_BLKP(bp)));
        // 如果下一个块是空闲块，则还需要设置其脚部
        if (!GET_ALLOC(HDRP(NEXT_BLKP(bp)))) {
            SET_PREV_ALLOC(FTRP(NEXT_BLKP(bp)));
        }
    }
    // 如果剩余块大小大于等于最小块大小，则分割，下一个块必为空闲块
    else {
        // 设置当前块头部
        PUT(HDRP(bp), PACK_ALL(size, GET_PREV_ALLOC(HDRP(bp)), 1));

        // 设置剩余块的头部和脚部
        // 次低位（上一个块为分配块）设置为1，最低位（当前块为分配块）设置为0
        PUT(HDRP(NEXT_BLKP(bp)), PACK_ALL(remain_size, 2, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK_ALL(remain_size, 2, 0));

        // 将下一个块插入空闲链表
        insert_node(NEXT_BLKP(bp), remain_size);
    }
}
c

插入空闲块 insert_node(bp, size)

/*
 * insert_node: 将空闲块插入空闲链表
 * 采用 LIFO 策略，即插入到链表头部，再次分配时优先分配最近释放的块
 */
static inline void insert_node(void* bp, size_t size) {
    size_t num = get_index(size);
    char* cur = free_lists[num];
    // 插入当前链表头部
    free_lists[num] = bp;
    if (cur != mem_heap_lo()) {
        SET_NODE_PREV(bp, NULL);
        SET_NODE_NEXT(bp, cur);
        SET_NODE_PREV(cur, bp);
    }
    else {
        SET_NODE_PREV(bp, NULL);
        SET_NODE_NEXT(bp, NULL);
    }
}
c

根据同学指正，此处还有一个优化点：插入链表的时候可以对前 k 个元素做一次插入排序（即部分排序），插到前 k 个元素中的正确位置，从而可以保证前 k 个元素是有序的，这样就可以提高查找时的效率（相当于做了一点点的 best fit）。

注意这里一定不能做完全排序，因为这样会导致插入的时间复杂度变为 O (logn)，从而导致吞吐量巨幅下降。

删除空闲块 delete_node(bp)

/*
 * delete_node: 将空闲块从空闲链表中删除
 * 如果是头结点，则额外更新头指针
 * 注意：经过 PREV_NODE 或 NEXT_NODE 计算后的指针，加上了 mem_heap_lo() 的偏移
 * 所以判断是否有后继节点（即实际存储的 WSIZE 空间内为 NULL）
 * 应当与 mem_heap_lo() 比较
 */
static inline void delete_node(void* bp) {
    size_t size = GET_SIZE(HDRP(bp));
    size_t num = get_index(size);
    char* prev = PREV_NODE(bp);
    char* next = NEXT_NODE(bp);
    // 如果是头结点
    if (prev == mem_heap_lo()) {
        free_lists[num] = next;
        if (next != mem_heap_lo()) {
            SET_NODE_PREV(next, NULL);
        }
    }
    else {
        SET_NODE_NEXT(prev, next);
        if (next != mem_heap_lo()) {
            SET_NODE_PREV(next, prev);
        }
    }
}
c

检查堆的正确性 mm_checkheap(lineno)

/*
 * mm_checkheap: 检查堆的正确性
 */
void mm_checkheap(int lineno) {
    // 偏移掉分配在堆底的空闲链表
    char* bp = mem_heap_lo() + DSIZE * FREE_LIST_NUM;
    // 检查序言块
    if (GET(bp) != 0) {
        dbg_printf("[%d]Prologue Error: word before prologue incorrect at %p\n", lineno, bp);
    }
    if (GET(bp + WSIZE) != PACK(DSIZE, 1)) {
        dbg_printf("[%d]Prologue Error: prologue header incorrect at %p\n", lineno, bp);
    }
    if (GET(bp + DSIZE) != PACK(DSIZE, 1)) {
        dbg_printf("[%d]Prologue Error: prologue footer incorrect at %p\n", lineno, bp);
    }
    // 移动指针到序言块之后
    bp += DSIZE;
    // 初始化为1而不是2，用以辨别初始状态（即指针指向堆底时）
    size_t is_prev_alloc = 1;
    size_t is_prev_free = 0;

    while ((void*)bp < mem_heap_hi()) {
        // 检查边界是否对齐
        if (!CHECK_ALIGN(bp)) {
            dbg_printf("[%d]Alignment Error: block not aligned at %p\n", lineno, bp);
        }
        // 检查块大小是否合法
        if (GET_SIZE(HDRP(bp)) == 0) {
            dbg_printf("[%d]Block Header Error: block size is invalid at %p\n", lineno, bp);
        }
        // 指针并非指向堆底时，检查头部是否正确标记上一个块是否分配
        if (is_prev_alloc != 1) {
            if (GET_PREV_ALLOC(HDRP(bp)) != is_prev_alloc) {
                dbg_printf("[%d]Block Header Error: prev alloc bit is incorrect at %p\n", lineno, bp);
            }
        }
        is_prev_alloc = GET_ALLOC(HDRP(bp));

        // 对于空闲块，检查头部尾部是否一致
        if (!GET_ALLOC(HDRP(bp))) {
            // 首先检查头尾是否一致
            if (GET(HDRP(bp)) != GET(FTRP(bp))) {
                dbg_printf("[%d]Block Match Error: header does not match footer at %p\n", lineno, bp);
            }
            // 检查是否存在连续空闲块
            if (is_prev_free) {
                dbg_printf("[%d]Block Free Error: two consecutive free blocks at %p\n", lineno, bp);
            }
            is_prev_free = 1;
        }
        else {
            is_prev_free = 0;
        }
    }
    // 检查结尾块
    // 检查结尾块大小是否为0
    if (GET_SIZE(HDRP(bp)) != 0) {
        dbg_printf("[%d]Epilogue Error: epilogue block size is invalid at %p\n", lineno, bp);
    }
    // 检查结尾块是否正确标记上一个块是否分配
    if (GET_PREV_ALLOC(HDRP(bp)) != is_prev_alloc) {
        dbg_printf("[%d]Epilogue Error: prev alloc bit is incorrect at %p\n", lineno, bp);
    }
    // 检查结尾块是否正确标记当前块是否分配
    if (GET_ALLOC(HDRP(bp)) != 1) {
        dbg_printf("[%d]Epilogue Error: epilogue block is not allocated at %p\n", lineno, bp);
    }
    // 检查当前指针是否超过堆顶
    if ((void*)bp > mem_heap_hi()) {
        dbg_printf("[%d]Heap Error: heap extends beyond heap top at %p\n", lineno, bp);
    }
    // 检查是否对齐堆顶
    if (!CHECK_ALIGN(bp)) {
        dbg_printf("[%d]Alignment Error: heap top not aligned at %p\n", lineno, bp);
    }
}
c

注意，你需要手动的调用 mm_checkheap 来检查堆的正确性。调用前你需要在文件开头定义 #define DEBUG 的宏，以开启调试模式。

具体的调试方法请详见上文中的 “测试分” 一节。

检查空闲链表的正确性 mm_checkfreelist(lineno)

/*
 * mm_checkfreelist: 检查空闲链表的正确性
 */
void mm_checkfreelist(int lineno) {
    // 初始化对比变量
    size_t free_block_by_list = 0;
    size_t free_block_by_heap = 0;
    // 检查所有链表链接的正确性
    for (int i = 0;i < FREE_LIST_NUM;i++) {
        char* bp = free_lists[i];
        // 设置全局变量 low_range high_range 对应当前桶的大小范围
        get_range(i);
        while ((void*)bp > mem_heap_lo() && (void*)bp < mem_heap_hi()) {
            // 检查双向链表是否匹配
            if (PREV_NODE(bp) != NULL) {
                if (NEXT_NODE(PREV_NODE(bp)) != bp) {
                    dbg_printf("[%d]Free List Error: prev and next pointer not match at %p\n", lineno, bp);
                }
            }
            // 检查当前节点大小是否符合桶大小
            size_t cur_size = GET_SIZE(HDRP(bp));
            if (cur_size < low_range || cur_size > high_range) {
                dbg_printf("[%d]Free List Error: block size not match bucket at %p\n", lineno, bp);
            }
            // 检查当前节点是否为空闲块
            if (GET_ALLOC(HDRP(bp))) {
                dbg_printf("[%d]Free List Error: block is not free at %p\n", lineno, bp);
            }
            bp = NEXT_NODE(bp);
            ++free_block_by_list;
        }
        if ((void*)bp != mem_heap_lo()) {
            dbg_printf("[%d]Free List Error: pointer out of range at %p\n", lineno, bp);
        }
    }
    char* bp = mem_heap_lo() + DSIZE * FREE_LIST_NUM;
    while ((void*)bp < mem_heap_hi()) {
        if (!GET_ALLOC(HDRP(bp))) {
            ++free_block_by_heap;
        }
        bp = NEXT_BLKP(bp);
    }
    // 检查对比变量是否匹配，从而确定是否所有的空闲块都在空闲链表中
    if (free_block_by_heap != free_block_by_list) {
        dbg_printf("[%d]Free List Error: not all free block in free lists %p\n", lineno, bp);
    }
}
c

同上。

测试结果与评分

Results for mm malloc:
  valid  util   ops    secs     Kops  trace
   yes    86%  100000  0.006152 16254 ./traces/alaska.rep
 * yes    99%    4805  0.000625  7688 ./traces/amptjp.rep
 * yes    83%    4162  0.000219 18964 ./traces/bash.rep
 * yes    77%   57716  0.001926 29966 ./traces/boat.rep
 * yes    78%  100000  0.003407 29349 ./traces/boat-plus.rep
 u yes    90%      --        --    -- ./traces/binary2-bal.rep
 * yes    99%    5032  0.000553  9105 ./traces/cccp.rep
 * yes    99%    5848  0.000595  9826 ./traces/cccp-bal.rep
 * yes    76%   11991  0.000588 20387 ./traces/chrome.rep
 * yes    99%   20000  0.000705 28363 ./traces/coalesce-big.rep
   yes    66%   14400  0.000351 40982 ./traces/coalescing-bal.rep
   yes   100%      15  0.000012  1228 ./traces/corners.rep
 * yes    99%    5683  0.000926  6138 ./traces/cp-decl.rep
 u yes    71%      --        --    -- ./traces/exhaust.rep
 * yes   100%    5380  0.000934  5758 ./traces/expr-bal.rep
 * yes    84%   99544  0.004843 20554 ./traces/firefox-reddit2.rep
 * yes    98%   55092  0.002232 24684 ./traces/freeciv.rep
   yes    33%      10  0.000011   899 ./traces/malloc.rep
   yes    27%      17  0.000011  1520 ./traces/malloc-free.rep
 p yes     --    1494  0.000100 14947 ./traces/perl.rep
 * yes    93%    4800  0.001033  4648 ./traces/random.rep
 * yes    92%    4800  0.001032  4651 ./traces/random2.rep
   yes    30%   14401  0.092237   156 ./traces/realloc.rep
16 15     90%  386347  0.019719 19593

Perf index = 60 (util) & 40 (thru) = 100/100
bash

如果你没满分，那么你可以参照这个数据来确定你的哪个测试点应当调整。当然，各年的数据可能存在差异，所以仅供参考。

实际 autolab 评测的 KOPS 可能会和本地评测不一致，如我的 autolab 实际评测为 15218 KOPS，但本地评测为 19593 KOPS。这可能和本地 /autolab 的机器性能有关。

如果你实在闲得无聊想卷 KOPS，一个可能的方法是减少所有的变量赋值，而全部转为宏定义或者行内比较，这样可以减少一定的指令数，从而提高吞吐量。

Debug

以下内容来自树洞，我没太用到，仅供参考：

#5740684 2023-12-11 10:59 关注数：6 回复数：2

ICS malloclab 求问如何高效 debug 呀？mm_checkup 函数是要怎么用啊… 一整个周末都是直接第一个 trace 就 segementation fault，真的不知道如何借助其他工具 debug

[Alice]

去掉 -O3 用 gdb 运行 mdriver 可以定位到段错误函数

heapchecker 可以遍历你的空闲链表查看你维护的信息对不对

读 mdriver.c 并改写来提供更多错误信息

先用 ls -l 找小的 trace 来测试

注：这里指的 去掉 -O3，应该是指在 Makefile 中将 CFLAGS 中的 -O3 去掉（或换成 -O2），以降低优化等级，从而方便调试。

参考链接

更适合北大宝宝体质的 Malloc Lab 踩坑记
https://arthals.ink/blog/malloc-lab
Author Arthals
Published at December 19, 2023
Copyright
CC BY-NC-SA 4.0 (content) / GPLv3.0 (code)
Buy me a cup of coffee ☕.
Comment seems to stuck. Try to refresh?✨