Yanyan's wiki
 for 

L1: 物理内存管理 (pmm)

⏰Soft Deadline: 2024 年 5 月 5 日 23:59:59

在命令行中 git pull origin L1 下载框架代码。我们总是在 kernel 目录下工作，因此如果你遇到了 Git 冲突 (合并问题)，请以我们的新版本为准。在获取到框架后，请把你 L0 的代码手工从 kernel 目录中移除。

本实验需要提交以学号命名的 .pdf 格式实验报告 (保存在 kernel/ 目录下)，之后的 OSLabs 将不断在此实验报告基础上添加。此外，我们提倡拒绝内卷。除非特殊情况，本次实验的实验报告不建议超过 2 页 A4 纸。请在实验报告中描述你在实验中遇到的特别值得一提的事件，例如你代码的架构设计、特别精巧的实现、遇到印象深刻的 bug 等。

因为之后的实验会使用同一个 repo；你需要修改 Makefile，设置 export MODULE := L1，确保你提交到 L1 的 Online Judge。
⚖️L1 - pmm

请输入 Token 登录。

1. 背景

如果你希望实现任何稍稍复杂一些的程序，对象 (内存) 的动态分配和回收几乎都是难以避免的。同时，作为一个多处理器编程 (互斥) 的练习，我们实现多处理器上的物理内存管理，完成物理内存的分配和回收。

💡内存分配和回收
在从今往后的实验里，我们会逐步帮助大家纠正在面向算法竞赛的 Online Judge 编程时一个不好的习惯：只管分配，不管回收。大家在做 “算法题” 时，不管是大数组 int dp[N][N]，还是 new Tree[N]，都指望操作系统在进程结束后自动回收资源。但在《操作系统》课上你不能这么做，因为你就是操作系统的实现者！

    2. 实验描述

    2.1 实现多处理器安全的内存分配和回收

    🗒️实验要求：kalloc/kfree

    框架代码 (实际上是 AbstractMachine) 会在 main 函数调用前初始化 heap 变量，[heap.start, heap.end) 标记了一段操作系统内核可用的物理内存。所有操作系统内核所需的动态内存，以及所有应用程序所需的内存都来自 heap。因此，你需要实现允许多个处理器并发地申请或释放内存的分配器，包括以下两个函数：

    static void *kalloc(size_t size) {
    // 内存分配
}

static void kfree(void *ptr) {
    // 内存释放
}

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

    • 原子性：当多个处理器同时请求内存分配或释放时，分配器必须确保同时进行的分配/回收操作能够正确完成。注意，在一个处理器上分配的内存，可能在另一个处理器上被释放。
    • 无重叠：分配器返回的内存块之间不能有重叠。每次调用 kalloc 时，它必须返回一个独特的内存区域，该区域在其生命周期内不与任何其他分配的内存块共享地址空间。
    • 对齐：对于大小为 ss 的内存分配请求，返回的内存地址必须对齐到 2i2^i，其中 ii 是最小的正整数满足 2i≥s2^i \ge s。例如，4 KiB 的内存分配请求返回的地址必须是 4,096 的整数倍 (页面边界)。例如，分配 17 字节内存返回的地址必须是 32 的整数倍。看似浪费，但这个实验要求简化了大家的实现。
    • 无内存泄漏：当内存不再需要时，应该通过 kfree 正确释放。分配器需要确保所有释放的内存都可以被重新分配，不应该有任何内存泄漏。这意味着分配器需要准确跟踪哪些内存是空闲的，哪些是已分配的。
    • 错误处理：当无法满足内存分配请求时（例如，因为没有足够的空闲内存），kalloc 应该返回 NULL (0)。
    • 最后，不必初始化返回的内存，当然，对返回的内存赋上初始值 (例如零) 也许是个不错的主意。不必初始化返回的内存，当然，对返回的内存赋上初始值 (例如零) 也许是个不错的主意。
    • 由于我们在自制的操作系统内核中使用，你可以直接拒绝超过 16 MiB 的内存分配。

    2.2 性能优化 (Hard Tests)

    🗒️实验要求：高性能的 kalloc/kfree

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

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

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

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

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

    ☕️不要使用区间树

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

    2.3 实现 AbstractMachine 中 klib 中缺失的函数

    在 Lab0 中，我们已经提出了这个实验要求。这个实验建议大家实现 klib 里缺失的函数——没有 printf, sprintf 等函数，你根本就是在用汇编语言写操作系统，你无法活到最后。我们不会检查大家的 klib 实现，但也请大家不要抄袭——虽然互联网上有很多代码，但自己写一遍依然是掌握这些库函数原理的最好方式。

    3. 正确性标准

    这个实验维护一个数据结构 (抽象数据类型)，维护一个不相交区间的集合 (堆区)：

    H={[ℓ0,r0),[ℓ1,r1),…,[ℓn,rn)}；H = \big\{ [\ell_0, r_0), [\ell_1, r_1), \ldots, [\ell_n, r_n) \big\}；

    初始时，H=∅H = \varnothing。假设 heap.start =L\ = L, heap.end =R\ = R，对于任意时刻的当前堆区 HH:

    • kalloc(ss) 分配 ss 字节的内存 [ℓ,r)[\ell, r) 满足：
      1. 分配发生在堆区中 L≤ℓ<r<RL \le \ell < r < R
      2. 分配的内存不与已分配内存重叠 ∀[ℓi,ri)∈H. [ℓ,r)∩[ℓi,ri)=∅\forall [\ell_i, r_i) \in H.\ [\ell, r) \cap [\ell_i, r_i) = \varnothing
      3. 分配后新的堆区 H′=H∪{[ℓ,r)}H' = H \cup \big\{ [\ell, r) \big\}
      4. 返回分配区间的左端点 ℓ\ell。
    • kfree(ℓ\ell) 删除一个已有区间 [ℓ,r)∈H[\ell, r) \in H，得到新的堆区 H′=H∖{[ℓ,r)}.H' = H \setminus \big\{ [\ell, r) \big\}. 当 ℓ\ell 不是 HH 中任何一个区间左端点时，产生 undefined behavior——即 kfree 的调用者有义务保证一定释放一个已分配的空间。
    ⚠️重视正确性

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

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

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

    3.1 测试用例说明

    ⚠️如果设置 smp 不能正确启动多处理器

    abstract-machine 和 xv6 都通过读 MP tables 来得到 CPU 核心数的值，这个值对应 QEMU 中的 sockets 数量。如果发现 AbstractMachine 只找到了一个核，在 scripts/platform/qemu.mk 里面的 QEMU_FLAGS 里把 -smp 设置成 -smp “cores=1.sockets=$(smp)” 即可。

    我们会使用来自类似于真实操作系统系统内核的多处理器内存分配/回收 workload 来测试大家的程序。我们的内存分配：

    • 不超过 8 个处理器、不少于 64 MiB、不多于 4 GiB 内存的堆区；
    • 大量、频繁的小内存分配/释放；其中绝大部分不超过 128 字节；
    • 较为频繁的，以物理页面大小为单位的分配/释放 (4 KiB)；
    • 非常罕见的大内存分配。

    我们预期你的 kalloc/kfree 具有足够的 robustness，足以承载操作系统内核的实现:

    1. Safety: 我们预期你的 kalloc/kfree 实现是正确的。一旦以下情况发生，将被立即被 Online Judge 判定为错误：
      • 虚拟机重启、crash、测试代码中的 assert fail 等 (通常由 undefined behavior 触发，例如数据竞争)
      • kalloc 的返回值不满足 API 规约，例如分配的内存不位于堆区、错误的内存对齐等
      • kalloc 返回一段尚未被 kfree 的内存
    2. Liveness: 我们还需要系统有一定的 liveness，即系统中有充足剩余内存时，内存分配不应过于频繁的频繁失败。这是为了防止你为了 safety 进行一些 “投机取巧”：对所有 kalloc 都返回 NULL，safety trivially 被满足。
      • liveness 并不是一个 “硬性” 的要求。在合理的 workload 上，你程序的表现只要不比一个 (实现得非常一般) 的 baseline 差太多 (你依然允许在某些你认为无法满足的 kalloc 上返回 NULL)，就会被判定为正确

    与 L0 类似，我们会链接我们 klib 的参考实现，因此你不必担心你的 klib 有些许问题；但你要保持 klib 库函数的行为与 libc 一致。注意 native 会链接系统本地的 glibc (而非 klib)。

    ⚠️难度、策略与 Academic Integrity

    首次接触并发编程的同学会感到高性能的实现有一定难度——不用着急，从 “总是正确” 的实现开始慢慢改进。甚至，如果你觉得能力实在有限，可以从 “不实现” kfree 开始:

    static void kfree(void *ptr) {}

    这样 kalloc 的实现就非常简单了——简单到只需要维护一个指针即可，依然能确保有 easy tests 通过，并且可以继续后续的实验，获得后续实验的部分分数。我们不严格禁止这样的实现，而且你会发现，如果内存充足，你之后编写的操作系统依然是可以运行的 (只是运行一段时间以后，就会 out of memory 无法再运行下去，会影响后续实验测试用例的得分)。

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

    ⚠️framework/ 代码会被我们替换

    我们会使用我们 framework/main.c 的代码，但保持你 src/ 目录下的文件不变。测试时，我们会改变 mpe_init 的入口 (不再从 os->run 开始执行，而是直接运行测试的 workload)。因此你必须在 os->init() 中完成所有必要的初始化，例如调用 pmm->init()。

    以下是一个我们测试代码的例子，它会不断生成随机的 kalloc/kfree 请求 (你可以假设我们的生成器总是生成合法的请求，例如不会发生 double-free 等)，并且检查 kalloc/kfree 返回结果的合法性；当检测到问题后会 assert fail 退出，然后你可能会得到 “Runtime Error”。

    #include <common.h>
#include <klib.h>

enum ops { OP_ALLOC = 1, OP_FREE };

struct malloc_op {
    enum ops type;
    union {
        size_t sz;  // OP_ALLOC: size
        void *addr; // OP_FREE: address
    };
};

void stress_test() {
    while (1) {
        // 根据 workload 生成操作
        struct malloc_op op = random_op();

        switch (op.type) {
            case OP_ALLOC: {
                void *ptr = pmm->alloc(op.sz);
                alloc_check(ptr, op.sz);
                break;
            }
            case OP_FREE:
                free(op.addr);
                break;
        }
    }
}

int main() {
    os->init();
    mpe_init(stress_test);
}

    我们鼓励你参考上面的方式 (或者用你想到的任何方式)，实现自己的压力测试。

    4. 实验指南

    TBD

    Creative Commons License: BY-NC 4.0
    苏 ICP 备 2020049101 号