Malloc Lab：编写动态存储分配器

Malloc Lab：编写动态存储分配器

原文：官方实验说明
实验包：malloclab-handout.tar

自学包说明：运行配置与原说明的差异

课程信息

CS 213，2001 年秋季

Malloc Lab：编写动态存储分配器

布置：11 月 2 日（星期五）；截止：11 月 20 日（星期二）晚上 11:59

Cory Williams（cgw@andrew.cmu.edu）是本作业负责人。

1 引言

在本实验中，你将为 C 程序编写一个动态存储分配器，也就是实现自己的 malloc、free 和 realloc 例程。鼓励你创造性地探索设计空间，实现一个正确、高效且快速的分配器。

2 事务安排

你最多可以与另一名同学组队。任何澄清和作业修订都会发布在课程网页上。

3 发放说明

SITE-SPECIFIC： 此处应插入说明学生如何下载 malloclab-handout.tar 文件的段落。（译注：这是供任课教师填写的课程占位符，原样保留其用途。）

首先，将 malloclab-handout.tar 复制到你计划工作的受保护目录中。然后执行命令 tar xvf malloclab-handout.tar。这会将若干文件解包到该目录。你唯一需要修改并提交的文件是 mm.c。mdriver.c 程序是一个驱动程序，可用于评估解决方案的性能。使用命令 make 生成驱动程序代码，并使用 ./mdriver -V 运行它。（-V 标志会显示有帮助的摘要信息。）

查看 mm.c 文件，你会注意到其中有一个名为 team 的 C 结构体；你应在其中填写组成编程团队的一名或两名成员的身份信息。马上完成这件事，以免忘记。

完成实验后，你只需提交一个文件（mm.c），其中包含你的解决方案。

4 如何完成实验

你的动态存储分配器由以下四个函数组成，它们在 mm.h 中声明并在 mm.c 中定义：

int mm_init(void);
void *mm_malloc(size_t size);
void mm_free(void *ptr);
void *mm_realloc(void *ptr, size_t size);

我们提供的 mm.c 实现了我们能想到的最简单但仍然功能正确的 malloc 包。以此为起点，修改这些函数（也可以定义其他私有 static 函数），使其遵守以下语义：

  • mm_init：应用程序（即用于评估实现的跟踪驱动程序）在调用 mm_malloc、mm_realloc 或 mm_free 前，会调用 mm_init 执行必要的初始化，例如分配初始堆区域。初始化遇到问题时返回 -1，否则返回 0。

  • mm_malloc：mm_malloc 返回一个已分配块的有效载荷指针，至少包含 size 个字节。整个已分配块应位于堆区域内，且不得与任何其他已分配块重叠。

    我们会将你的实现与标准 C 库（libc）提供的 malloc 进行比较。由于 libc malloc 总是返回按 8 字节对齐的有效载荷指针，你的 malloc 实现也必须如此，并且始终返回 8 字节对齐的指针。

  • mm_free：mm_free 释放 ptr 指向的块，不返回任何值。只有当传入的指针 ptr 是此前调用 mm_malloc 或 mm_realloc 返回的、且尚未被释放时，该例程才保证有效。

  • mm_realloc：mm_realloc 返回一个至少包含 size 个字节的已分配区域指针，并遵守以下约束：

    • 如果 ptr 为 NULL，调用等价于 mm_malloc(size)；

    • 如果 size 等于零，调用等价于 mm_free(ptr)；

    • 如果 ptr 不为 NULL，它必须是此前调用 mm_malloc 或 mm_realloc 返回的指针。

      mm_realloc 调整 ptr 所指内存块（旧块）的大小为 size 字节，并返回新块地址。注意，新块地址可能与旧块相同，也可能不同，这取决于你的实现、旧块的内部碎片数量以及 realloc 请求的大小。

      新块内容与旧 ptr 块的内容相同，范围截至旧大小和新大小中的较小者。其余内容未初始化。例如，如果旧块为 8 字节、新块为 12 字节，则新块前 8 字节与旧块前 8 字节相同，后 4 字节未初始化。同样，如果旧块为 8 字节、新块为 4 字节，则新块内容与旧块前 4 字节相同。

这些语义与相应的 libc malloc、realloc 和 free 例程的语义相匹配。在 shell 中输入 man malloc 可查看完整文档。

5 堆一致性检查器

动态内存分配器出了名地难以正确、高效地编程。之所以难以正确实现，是因为其中包含大量无类型指针操作。编写一个扫描堆并检查其一致性的堆检查器会很有帮助。

堆检查器可以检查的内容例如：

  • 空闲列表中的每个块是否都标记为空闲？
  • 是否有某些连续的空闲块没有被合并？
  • 每个空闲块是否确实位于空闲列表中？
  • 空闲列表中的指针是否指向有效的空闲块？
  • 是否有已分配块相互重叠？
  • 堆块中的指针是否指向有效的堆地址？

你的堆检查器由 mm.c 中的函数 int mm_check(void) 组成。它应检查你认为合适的任何不变量或一致性条件；当且仅当堆一致时返回非零值。你不受上述建议限制，也不要求检查全部项目。鼓励在 mm_check 失败时打印错误消息。

该一致性检查器用于开发期间自行调试。提交 mm.c 时，确保删除所有对 mm_check 的调用，否则它们会降低吞吐量。mm_check 函数会计入风格分；务必添加注释并记录所检查的内容。

6 支持例程

memlib.c 包模拟动态存储分配器的内存系统。你可以调用 memlib.c 中的以下函数：

  • void *mem_sbrk(int incr)：将堆扩展 incr 字节，其中 incr 是正的非零整数，并返回新分配堆区域第一个字节的通用指针。其语义与 Unix sbrk 函数相同，但 mem_sbrk 只接受正的非零整数参数。
  • void *mem_heap_lo(void)：返回堆中第一个字节的通用指针。
  • void *mem_heap_hi(void)：返回堆中最后一个字节的通用指针。
  • size_t mem_heapsize(void)：返回堆当前的字节数。
  • size_t mem_pagesize(void)：返回系统页大小，以字节为单位（Linux 系统中为 4K）。

7 跟踪驱动程序

malloclab-handout.tar 发行包中的驱动程序 mdriver.c 会测试你的 mm.c 包的正确性、空间利用率和吞吐量。驱动程序由发行包中包含的一组跟踪文件控制。每个跟踪文件都包含一系列分配、重新分配和释放指令，指示驱动程序按某种顺序调用你的 mm_malloc、mm_realloc 和 mm_free 例程。我们会使用同一套驱动程序和跟踪文件，为你提交的 mm.c 文件评分。

驱动程序 mdriver.c 接受以下命令行参数：

  • -t <tracedir>：在 tracedir 目录中查找默认跟踪文件，而不是在 config.h 定义的默认目录中查找。
  • -f <tracefile>：使用一个指定的跟踪文件测试，而不是使用默认跟踪文件集合。
  • -h：打印命令行参数摘要。
  • -l：除学生的 malloc 包外，同时运行并测量 libc malloc。
  • -v：详细输出，以紧凑表格打印每个跟踪文件的性能分解。
  • -V：更详细的输出。处理每个跟踪文件时打印额外诊断信息。调试时可用于确定哪个跟踪文件导致 malloc 包失败。

8 编程规则

  • 不应修改 mm.c 中的任何接口。
  • 不应调用任何与内存管理有关的库调用或系统调用。这包括代码中使用 malloc、calloc、free、realloc、sbrk、brk 或其任何变体。
  • 不允许在 mm.c 程序中定义任何全局或 static 的复合数据结构，例如数组、结构体、树或列表。但是，可以在 mm.c 中声明全局标量变量，例如整数、浮点数和指针。
  • 为与返回按 8 字节边界对齐块的 libc malloc 包一致，你的分配器必须始终返回按 8 字节边界对齐的指针。驱动程序会检查这一要求。

9 评分

如果违反任何规则，或代码有错误并导致驱动程序崩溃，你将得零分。否则，评分如下：

  • 正确性（20 分）。 如果解决方案通过驱动程序执行的正确性测试，将获得满分；每个正确跟踪可获得部分分数。
  • 性能（35 分）。 使用两个性能指标评估解决方案：
    • 空间利用率：驱动程序使用的内存总量（即通过 mm_malloc 或 mm_realloc 分配、但尚未通过 mm_free 释放的内存）与分配器所用堆大小之比的峰值。最优比值为 1。应找到良好的策略来减少碎片，使该比值尽可能接近最优值。
    • 吞吐量：每秒完成的平均操作数。

驱动程序通过计算性能指数 P 总结分配器性能，该指数是空间利用率和吞吐量的加权和：

P = wU + (1 − w) min(1, T / Tlibc)

其中 U 是空间利用率，T 是吞吐量，Tlibc 是在默认跟踪上测得的系统 libc malloc 估计吞吐量。¹ 性能指数更偏重空间利用率，默认 w = 0.6。

考虑到内存和 CPU 周期都是昂贵的系统资源，我们采用此公式鼓励在内存利用率和吞吐量之间进行平衡优化。理想情况下，性能指数达到 P = w + (1 − w) = 1，即 100%。由于两个指标对性能指数的贡献分别最多为 w 和 1 − w，你不应只极端优化内存利用率或只极端优化吞吐量。要获得好成绩，必须在利用率和吞吐量之间取得平衡。

  • 风格（10 分）。
    • 代码应分解为函数，并尽量少使用全局变量。
    • 代码开头应有头部注释，描述空闲块和已分配块的结构、空闲列表的组织方式，以及分配器如何操作空闲列表。每个函数前都应有头部注释，描述该函数的作用。
    • 每个子程序都应有头部注释，描述它做什么以及如何实现。
    • 堆一致性检查器 mm_check 应彻底且文档齐全。一个良好的堆一致性检查器得 5 分，良好的程序结构和注释得 5 分。

¹ Tlibc 的值是驱动程序中的常量（600 Kops/s），由教师在配置程序时确定。

10 提交说明

SITE-SPECIFIC： 此处应插入说明学生如何提交解决方案 mm.c 文件的段落。（译注：这是课程占位符，原文未提供本课程实例内容。）

11 提示

  • 使用 mdriver -f 选项。在开发初期，使用很小的跟踪文件可以简化调试和测试。我们提供了两个这样的跟踪文件（short1,2-bal.rep），可用于初始调试。
  • 使用 mdriver -v 和 -V 选项。-v 会为每个跟踪文件提供详细摘要；-V 还会指出读取每个跟踪文件的时刻，有助于定位错误。
  • 使用 gcc -g 编译并使用调试器。调试器可以帮助你定位并识别越界内存引用。
  • 理解教材中 malloc 实现的每一行。教材详细介绍了一个基于隐式空闲列表的简单分配器。把它作为出发点。在理解简单隐式列表分配器的全部内容之前，不要开始编写自己的分配器。
  • 将指针运算封装在 C 预处理器宏中。内存管理器中的指针运算令人困惑且容易出错，因为必须进行大量类型转换。为指针操作编写宏可以显著降低复杂度。教材中有示例。
  • 分阶段实现。前 9 个跟踪包含 malloc 和 free 请求；最后 2 个跟踪包含 realloc、malloc 和 free 请求。建议先让 malloc 和 free 在前 9 个跟踪上正确且高效地工作，然后再处理 realloc。开始时，可以在已有的 malloc 和 free 实现之上构建 realloc；但要获得很好的性能，需要构建独立实现的 realloc。
  • 使用性能分析器。gprof 工具可能有助于优化性能。
  • 尽早开始！只用几页代码就可能写出高效的 malloc 包。然而，我们可以保证，这是你迄今为止职业生涯中写过的最困难、最复杂的代码之一。因此要尽早开始，祝好运！