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

2 个月前(已编辑)
/ ,
898
3
AI 生成的摘要
本文是对 CSAPP 中 Malloclab 实验的详细解析,共花费 23 小时完成。实验目标是在 `mm.c` 中实现一个动态内存分配器,包括初始化、分配、释放、重分配和检查堆正确性等功能。详细介绍了堆的结构、分配器的实现策略(如隐式空闲链表、显式空闲链表等)、分配块和空闲块的结构设计。通过优化空闲链表和分配算法,实现高内存利用率和吞吐量,最终达到满分评价。同时,提供了一些调试技巧和优化策略,帮助理解和完成实验。

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 分的风格分。

表现分

表现分的计算方式为:

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

由式子看出,我们想要收获满分,就需要使得 U(内存利用率)≥ 0.90T(吞吐量)≥ 14000

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

注意,有些测试的 trace 是并不计入统计的:

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

handout 中给了两个示例程序:

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

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

测试分

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

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

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

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

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

风格分

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

代码禁令

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

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

关于数据

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

测试指令

测试所有得分:

测试单 trace 得分:

存储结构设计

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

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

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

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

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

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

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

在这个例子中,有如下对应:

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

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

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

堆的结构

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

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

堆结构

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

  • 每个长条横块代表双字(DSIZE,8 字节)
  • 每半个长条横块代表一个字(WSIZE,4 字节)

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

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

  • 桶(bucket):桶代表一类大小的空闲链表,其头指针存储在堆底
  • 分离空闲链表(free_lists):所有桶的头指针构成的指针数组,其存储在堆底
分离空闲链表的堆存储

分离空闲链表的堆存储

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

块的结构

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

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

元数据

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

  • 0 位,最低位:是否分配
  • 1 位,次低位:前一个块是否分配
  • 2 位:保留不用
  • 31~3 位:块大小
元数据格式

元数据格式

块的精细结构

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

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

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

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

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

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

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

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

块结构

块结构

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

堆整体结构

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

分离空闲链表整体结构

分离空闲链表整体结构

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

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

实现

自定义宏 #define

几点说明:

  • 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指针

bp指针

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

初始化 mm_init()

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

分配块 malloc(size)

释放块 free(bp)

重新分配块 realloc(bp, size)

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

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

抄就完了(逃)。

扩展堆 extend_heap(words)

合并块 coalesce(bp, size)

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

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

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

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

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

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

获得分界范围 get_range(index)

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

调整分配大小 adjust_alloc_size(size)

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

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

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

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

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

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

这会生成一个 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

binary2-bal

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

查找空闲块 find_fit(asize)

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

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

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

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

分配块 place(bp, size)

插入空闲块 insert_node(bp, size)

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

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

删除空闲块 delete_node(bp)

检查堆的正确性 mm_checkheap(lineno)

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

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

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

同上。

测试结果与评分

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

实际 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),以降低优化等级,从而方便调试。

参考链接

评论区加载中...