M5: 并行内存分配器 (mymalloc)

⏰Soft Deadline: 2025 年 5 月 11 日 23:59:59

请注意遵守实验须知中的 AIGC Policy；在命令行中 git pull origin M5 下载框架代码。(4.19 更新了 vmalloc 参考实现，之前 pull 代码的同学再次执行 git pull origin M5 更新代码) (Online Judge 暂未开放)

⚖️M5 - mymalloc

请输入 Token 登录。

1. 背景

内存分配器 (malloc/free) 是 libc 的核心组件，负责管理程序运行时动态申请和释放内存的过程。在多处理器系统中，内存分配器面临更大的挑战：运行在多个处理器上的多个线程可能同时请求分配或释放内存，我们当然希望多个处理器上的 malloc 和 free 都可以并行执行，以获得更好的性能。与此同时，mmap 给我们的 “大段” 内存必须用合适的数据结构管理，数据结构的并发访问又需要小心的并发控制。

2. 实验描述

2.1 实现 Freestanding 环境下的多线程内存分配和回收

🗒️实验要求：mymalloc/myfree

实现多处理器安全的内存分配器，包括以下两个函数：

void *mymalloc(size_t size); // 内存分配
void myfree(void *ptr); // 内存释放

你的 malloc/free 实现允许使用以下两个函数 (我们的框架代码中提供了实现，Online Judge 评测时会覆盖你的修改过的 vmalloc/free)：

void *vmalloc(void *addr, size_t length); // length 必须是 4096 的倍数
void vmfree(void *addr, size_t length);

它们是 mmap 和 munmap 的封装，允许你申请和释放大块的内存。你可以在操作系统允许的范围内自由使用它们——vmalloc 成功会返回一段长度为 length 的可读、可写的内存；vmfree 会释放这段内存。除此之外，你提交的代码不能使用任何其他库函数 (freestanding 环境)。这样几乎 “零依赖” 的代码可以作为 libc 实现的一部分，或是用于操作系统内核 (我们不再用 vmalloc/vmfree 分配进程的虚拟内存，而是分配物理内存)。

我们要求分配和回收满足：

原子性：当多个处理器同时请求内存分配或释放时，分配器必须确保同时进行的分配/回收操作能够正确完成。注意，在一个处理器上分配的内存，可能在另一个处理器上被释放。
无重叠：分配器返回的内存块之间不能有重叠。每次调用 myalloc 时，它必须返回一个独特的内存区域，该区域在其生命周期内不与任何其他分配的内存块共享地址空间。
对齐：内存为 8 字节对齐，即 mymalloc 返回地址的低 3 位必须总是 0。
无内存泄漏：使用 myfree 释放的内存应当支持重用，而不是成为无法再分配的 “死内存”。这意味着分配器需要准确跟踪哪些内存是空闲的，哪些是已分配的。
错误处理：当无法满足内存分配请求时 (例如，因为没有足够的空闲内存)，myalloc 应该返回 NULL (0)。
最后，不必初始化返回的内存 (libc 的 malloc 为了性能并不清除内存——这个设计其实导致了一些安全问题)，当然，对返回的内存赋上初始值 (例如零) 也许是个不错的主意。

对于简单的需求，为了实现线程安全性，只要借助框架代码中实现的自旋锁，“一把大锁保平安” 就可以了。在本次实验中，你只能使用自旋的方式实现互斥，不得调用 pthreads 等库。

💡内存分配和回收

我们希望同学们在平时使用大语言模型的过程中，纠正面向 Online Judge 编程时一个不好的习惯：只管分配，不管回收。大家在做 “算法题” 时，不管是大数组 int dp[N][N]，还是 new Tree[N]，都指望操作系统在进程结束后自动回收资源。但对于长期运行的程序来说，管理对象的生存周期并不是一件简单的事情。

2.2 性能优化 (Hard Tests)

🗒️实验要求：高性能的 mymalloc/myfree

我们希望你的分配器应该尽量高效地使用内存，减少碎片，同时保持快速的分配和释放操作：

在 mymalloc/myfree 实现正确的前提下，尽可能使不同处理器上的内存分配能够并行。
受分配算法的局限，可能系统中仍然有空闲的内存，但形成了碎片的内存，或是你的算法不能找到它从而分配失败。这是允许的；但在系统内存压力很小的时候依然频繁分配失败，可能导致 hard test failure。
如果你代码的性能过低 (例如用全局的锁保护空闲链表，并用遍历链表的方式寻找可用的内存)，可能会导致 hard test failure。

回顾多处理器上的内存分配和释放带来额外的挑战：

我们希望保证分配的正确性。这意味着用一把大锁保护一个串行数据结构 (例如算法导论上的 “区间树” 就能在 $O(\log n)$ 的时间内完成分配和释放操作) 就能正确实现多处理器上的内存分配。
我们希望保证分配在多处理器上的性能和扩展性 (scalability)。这意味着不同的处理器能够并行地申请内存，尽可能减少因为同时申请而发生一个处理器等另一个处理器的情况。

上面两点需求是矛盾的，这也是本次实验的重点挑战。在这个实验里，我们通过 “system” 的方法解决问题，而不是巧妙的算法/数据结构——这不意味着算法/数据结构在计算机系统中没有应用，只是在这个问题上并不非常必要。

☕️不要使用区间树

树型的数据结构很容易在并行时遇到瓶颈——虽然不代表你不能实现高效的树型数据结构，但现代流行的内存分配器都使用了更简单、更 “system” 的方式解决问题：我们观察实际操作系统中内存分配的模式，提出最佳的算法。

3. 正确性标准

基于 vmalloc/vmfree 分配 “大区间的内存”，在可用的内存 (区间) 上实现数据结构 (抽象数据类型)，维护一个不相交区间的集合 (堆区)：

H = \big\{ [\ell_0, r_0), [\ell_1, r_1), \ldots, [\ell_n, r_n) \big\}；

初始时， $H = \varnothing$ 。对于任意时刻的当前堆区 $H$ :

mymalloc( $s$ $s$ ) 分配 $s$ $s$ 字节的内存 $[\ell, r)$ $[ℓ, r)$ 满足：
1. 分配发生在堆区中 $L \le \ell < r < R$
2. 分配的内存不与已分配内存重叠 $\forall [\ell_i, r_i) \in H.\ [\ell, r) \cap [\ell_i, r_i) = \varnothing$
3. 分配后新的堆区 $H' = H \cup \big\{ [\ell, r) \big\}$
4. 返回分配区间的左端点 $\ell$ 。
myfree( $\ell$ ) 删除一个已有区间 $[\ell, r) \in H$ ，得到新的堆区 $H' = H \setminus \big\{ [\ell, r) \big\}.$ 当 $\ell$ 不是 $H$ 中任何一个区间左端点时，产生 undefined behavior——即 myfree 的调用者有义务保证一定释放一个已分配的空间。

⚠️重视正确性

如果你的 mymalloc/myfree “几乎完全不正确”，问题反而容易排查。但如果在犄角旮旯的情况里有一个并发 bug，又恰好到生产部署以后才以非确定性的方式暴露出来，灾难就来了：这么大的系统，你可能不会想到问题出在先前实验的模块。大家毕业以后终有一天需要脱离 Online Judge，去实现 “从没人做过的东西”，所以你可能会抱怨 Online Judge 的无情拒绝和冷却时间，但也请坚持住！

🗒️实验要求：使用动态方式管理内存

为了强迫大家使用动态的方式管理大小不同的堆区，我们规定你使用的所有静态内存 (64-bit 模式下的代码、数据、bss) 不能超过 1 MiB。我们将会在运行之前对内核使用 size 命令进行检查，并拒绝过大的二进制文件。管理堆区的数据结构应当在堆区中而不是静态区中进行分配。

我们会用一些接近真实的 workload 来测试 mymalloc/myfree 的正确性和性能。

💬

Prompt: 有哪些开源的评估 malloc/free 的 workload？ 

我们建议大家尝试使用真实的 workload 来测试你的 mymalloc/myfree 的性能——配置真实 workload 时可以借助 AIGC。

3.2 Online Judge 运行测试代码的方式

4. 实验指南

(Working in Progress)

4.1 框架代码

我们要求 mymalloc 运行在没有任何库函数的 freestanding 环境——没有 libc，没有 pthreads，你想 printf 都做不到，这还怎么编程？

4.2 严肃地编程

这次我们不是在 “做作业” 了。

4.3 构建测试框架

4.4 性能调优

⚠️抛开 workload 谈优化，就是耍流氓

Premature optimization is the root of all evil. (D. E. Knuth) 要考虑好你优化的场景，否则一切都是空谈。

💬

Prompt: 给本科生第一次接触操作系统课程的同学，介绍一下性能调优的注意事项。 

如果你想要做性能调优，首先要确保你调向了正确的方向——你必须要先有一个合适的 workload 用于评估你的性能；然后，靠 “猜” 和随机修改程序以获得性能提升的方式也是不专业的表现；我们有成熟的工具体系 (trace, profiler, ...) 帮助我们理解程序性能的瓶颈。由于没有给出这次实验的背景，AI 还给了我们一些发散的思考。

这个实验给大家的剧透是：如果数据结构选择得不太差，性能瓶颈就主要在于多个线程并发访问时的互斥，由于多个线程都需要获得同一把锁，自旋浪费了多处理器的算力。正如课本上所说，现代 malloc/free 实现的主要思想就是区分 fast/slow path，使得 fast path 分配在线程本地完成，从而不会造成锁的争抢。

5. 总结

malloc/free 也是 “机制与策略分离” 的典型案例。内存的分配接口简单，但覆盖了极为广泛的应用场景。各种访问模式的程序都用同一个 API 分配，编程确实简单了——带来的代价是策略的设计变得非常困难。“自动” 一直是计算机系统实现者的终极追求——例如，free 看起来就不那么 “自动”。很多现代编程语言都运行在自动管理内存的的运行时环境上：Java, Python, Javascript, ...它们的特点是：没有 raw pointer，也没有 API 用于 “释放” 内存。当一个对象从一系列的 root objects (例如栈上的局部变量、全局变量等……) 通过引用关系不可达，它们就会自动被运行时环境回收。这真是程序员的福音——再也没有 use-after-free, double-free 等问题了，memory leak 的可能性也大大降低 (虽然依然可能会有)。

但随着系统的发展，总有一天我们会发现 “自动” 的性能难以支撑所有应用的需求，机制的实现也变得越来越复杂，到今天甚至机器学习也下场了，Rust 则希望回到一种介于手动和自动之间的管理方式。“什么是合适的抽象” 也许是一个短时间内无法解决的问题。