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

1. 背景

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

2. 实验描述

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

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

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

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

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

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

2.2 性能优化 (Hard Tests)

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

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

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

3. 正确性标准

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

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

• mymalloc($s$) 分配 $s$ 字节的内存 $[\ell, 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 的调用者有义务保证一定释放一个已分配的空间。

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

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

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

我们会在 freestanding 的环境下运行你的代码，模拟你在实现一个操作系统内核。我们会提供与 mmap 类似的 vmalloc 和 vmfree，请你做好调试代码 (printf、线程创建等) 的隔离，它们在 freestanding 环境下将导致编译错误。注意你的分配器：

• 不能 “浪费” 过多的内存，即内存碎片的控制应当在一个合理范围内：当实际使用的内存超过申请内存的 4 倍时，Online Judge 将会判定为错误。初始阶段使用的一些合理内存不计入此项。
• 确保多处理器分配的性能，否则可能会导致 hard test failure。

4. 实验指南

4.1 框架代码

我们的框架代码几乎 “什么都没有”，而且要求你支持 freestanding 环境——没有 libc，没有 pthreads。我们提供的仅有：

typedef struct {
    atomic_int status;
} spinlock_t;

#define LOCKED   1
#define UNLOCKED 0

static inline void spin_lock(spinlock_t *lock) {
    // 不断尝试将锁从 UNLOCKED 改为 LOCKED，直到成功
    int expected;
    do {
        expected = UNLOCKED;
    } while (!atomic_compare_exchange_strong(&lock->status, &expected, LOCKED));
}

static inline void spin_unlock(spinlock_t *lock) {
    // 直接将锁状态设为 UNLOCKED
    atomic_store_explicit(&lock->status, UNLOCKED, memory_order_release);
}

当一个线程想要获取已被占用的锁时，它会一直 “自旋” (忙等) 直到锁被释放。对于等待时间较短的临界区，自旋实现互斥也不失为一种合理的选择。

start.c 里提供了两种环境的代码：对于非 freestanding 环境 (有 libc)，我们基于 mmap 和 munmap 实现了 vmalloc/vmfree，并且已经给大家实现了一些测试用的代码，包括 mymalloc, vmalloc 的 smoke testing，以及创建线程 (自旋锁) 的测试。

4.2 严肃地编程

这个作业的难度还是有一点的，大家加油！其实本身 malloc/free 的实现并不复杂，代码量在 200-300 行左右，尤其是如果你适当地使用数据结构，就会发现锁的管理相当清楚明确，在 “正常” 的 workload 下也没有性能瓶颈。但这个实验其实暗藏了 “陷阱”：

Online Judge 给了你无情的 Wrong Answer。这个时候，诊断问题就变得非常困难。你需要构建测试框架——几个简单的 unit test cases 是不够的。找到错误、调优性能，才是这个实验的真正目的。你需要构造并发的 workload，测试你的分配/回收算法是否存在逻辑错误。例如，你可以为每个 malloc/free 都打印出分配到的地址 (和释放的地址)，并且用另一个脚本来检查是否存在常见的 memory errors: use-after-free, double-allocation, ... 但你的日志会产生 “probe effect”，可能会掩盖一些在没有日志时会产生的并发问题……

这时候你就会发现测试框架非常有用了——你可以在其中实现各个种类的测试，并且一件运行。必要的时候，你可以修改 testkit.h 里的 Time Limit，使你的 workload 能运行更长的时间，执行足够的 “压力测试”。

4.4 性能调优

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

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

聪明的你想到了 thread-local 分配来优化性能——毕竟 vmalloc 是线程安全的。对于评测平台，你可以使用以下方式实现 freestanding 环境下的 gettid：

static inline pid_t gettid(void) {
    pid_t tid;
    __asm__ volatile (
        "syscall"
        : "=a" (tid)
        : "0" (SYS_gettid)
        : "rcx", "r11", "memory"
    );
    return tid;
}

5. 总结

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

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