Lab 1: Allocator
负责助教：徐厚泽
本实验中，我们将初步了解内核启动过程中对物理内存的初始化、内核启动后对物理内存的管理，并实现一个简单的物理内存分配器供后续使用。值得注意的是，从本实验开始，我们将考虑 SMP 架构下的并发问题。
1. 代码下载
运行以下命令进行代码的拉取与合并
# 拉取远端仓库
git fetch --all
# 提交你的更改
git add .
git commit -m "your commit message"
# 切换到新lab的分支
git checkout lab1
# 新建一个分支，用于开发
git checkout -b lab1-dev
# 引入你在上个lab的更改
git merge lab0-dev如果合并发生冲突，请参考错误信息自行解决。
2. 物理内存管理
TIP
相关背景知识可自行回顾 计算机系统基础 和 计算机组成与体系结构 。若本节内容难以理解，可先行跳过，随着实验的深入我们将逐步理解。
2.1 AArch64 地址翻译
在 AArch64 架构中，EL1 异常级别（类比于 RISC-V 的 Supervisor Mode，后文也称内核态）存在两个页表基址寄存器（ttbr：Translation Table Base Register）：ttbr0_el1 和 ttbr1_el1，分别用于虚拟地址空间低地址和高地址的翻译。
那么，什么地址范围称为“低地址”，什么地址范围称为“高地址”呢？这由翻译控制寄存器（tcr：Translation Control Register）进行配置，由其指出当虚拟地址高 X 位为 0 时，使用 ttbr0_el1 指向的页表进行翻译，当虚拟地址高 X 位为 1 时，使用 ttbr1_el1 指向的页表进行翻译。
在本实验框架中，我们将 tcr_el1 配置为高低地址各 48 位的虚拟地址空间（X = 16），即 0x0000_0000_0000_0000 到 0x0000_FFFF_FFFF_FFFF 为低地址空间，0xFFFF_0000_0000_0000 到 0xFFFF_FFFF_FFFF_FFFF 为高地址空间。
在地址翻译过程中，虚拟地址的划分如下图所示：
63 48 47 39 38 30 29 21 20 12 11 0
+-----------+----------+----------+----------+----------+--------+
| FFFF/0000 | L0 index | L1 index | L2 index | L3 index | offset |
+-----------+----------+----------+----------+----------+--------+在了解了上述背景知识后，你现在应该能看懂 src/start.S 中有关于内核页表配置的代码了。
_start:
/**
* Set up the user and kernel page tables.
* Higher and lower half map to same physical memory region.
*/
adrp x9, kernel_pt_level0
msr ttbr0_el1, x9
msr ttbr1_el1, x9
ldr x9, =TCR_VALUE
msr tcr_el1, x9
...2.2 内核虚拟地址
有了 AArch64 地址翻译的前置知识后，接下来我们引入内核虚拟地址的概念。
通常来说，我们会将操作系统内核配置在虚拟内存的高地址空间（也即 0xFFFF_0000_0000_0000 之后的虚拟地址），我们的实验框架也是如此。
INFO
请回顾 src/linker.ld 中的内核链接地址，即
SECTIONS
{
. = 0xFFFF000040000000;
...
}此外，我们在 src/start.S 中启用了 MMU（Memory Management Unit），这意味着我们的内核代码在访问内存时，必须使用内核虚拟地址，而不能直接使用物理地址。
为此，我们在 src/aarch64/mmu.h 定义了 K2P 和 P2K 两个宏，用于内核虚拟地址和物理地址的相互转换。
2.3 物理内存
在 src/driver/memlayout.h 中，给出了我们实验中内存空间的布局。
EXTMEM 至 PHYSTOP 这段物理地址内的空间即为我们的物理内存。但考虑到我们的内核代码也会置于内存中，实际可供分配的物理内存空间为 end 至 PHYSTOP 。
INFO
请回顾 src/linker.ld 中给出的 end 符号，它是整个链接完的内存映像（.text + .rodata + .data + .bss）的结束位置。
为方便后续使用，我们需要将完整的物理内存切分为 PAGE_SIZE 大小并按 PAGE_SIZE 对齐的物理页，以物理页为单位管理物理内存。
INFO
PAGE_SIZE 是内存页的大小，定义在 src/aarch64/mmu.h ，在这个头文件中，还提供了一些你可能会用到的宏定义。
3. 内存分配器
操作系统是内存资源的管理者，其管理内存的场景包括但不限于：
- 响应用户态程序的 malloc / free（通过 brk / mmap 等系统调用）：负责进程虚拟地址空间与物理页的映射与回收，支持大块分配、按需映射与换出策略。
- 内核自身对象的动态分配（主要场景）：例如 task_struct、VFS 组件（inode、dentry）、文件表项、管道 / 缓冲区、网络缓冲（sk_buff）、定时器、workqueue 元素等。该场景要求低延迟、高并发并尽量减少碎片，通常使用 slab / 对象缓存与 per-CPU cache 以降低锁竞争。
- 页级分配与 DMA：按页或按 order 分配物理内存，满足页表、DMA 及需要物理连续或特定对齐的场景。
- vmalloc / 虚拟连续分配：需要虚拟地址连续但物理不连续的场景（例如大内核缓冲区、模块映射）。
我们知道，现代计算机系统一般以一定大小的页为单位管理内存（如果以 byte 为单位管理内存，操作系统需要为每个内存地址维护一系列状态用于内存管理，造成巨量的资源消耗，因此操作系统会打包一段内存统一管理，即为页）。在本实验中，页的大小是 4096 byte。
为了响应用户的内存请求，操作系统可以将内存页分配给特定用户。然而，对于常见的内存需求而言，完整的物理页还是太大了。例如，若用户仅仅请求 1 byte 的内存，而我们以一个 4096 byte 的内存页响应此请求，这会造成其中 4095 byte 的浪费。因此，本实验中，我们将进一步实现细粒度的内存分配，以避免上述内存浪费。
WARNING
分配的内存块地址必须与大小对齐，即：
- 如果分配的内存大小是
2的倍数，则地址也要是2的倍数 - 如果大小是
4的倍数，地址也要是4的倍数 - 如果大小是
8的倍数，则地址也要是8的倍数 - 不需要
16字节以上的对齐，也即，如大小是16的倍数，则地址只需是8的倍数。
与 C 语言中的 free 相同，我们实现的内存分配器不要求程序在释放内存块时告知内存块的大小。所以你需要在合适的地方保存内存块大小。
NOTE
在 glibc 的 malloc 实现里，每个分配给用户的内存块前面都会有一小段隐藏的头部信息，用来记录这个块的大小和状态。用户得到的指针指向数据区的起始位置，看不到这部分元数据。当调用 free 时，glibc 会把指针往前偏移，找到头部，从里面读取块的大小，然后用这个信息来回收内存、做相邻空闲块合并等操作。这样就不需要用户告诉 free 释放多少字节。
此外，我们保证框架代码或要求大家完成的代码中需要通过内存分配器分配的内存大小均在 1 - PAGE_SIZE/2 之间，即我们不会要求你实现大页分配。
4. 并发问题
本实验中，我们要求大家考虑并发安全问题。测试时，4个核会同时分配和释放内存，你编写的内存分配器必须考虑到这种情况。
如下面代码，我们希望这段代码找到处于 AVAILABLE 状态的元素，并将其标记为 USING 。
for (int i = 0 ; i < N; i++) {
if (mem[i] == AVAILABLE) {
mem[i] = USING;
return i;
}
}容易看出，当两个核同时执行这段代码时，可能两个核会返回同一个元素，导致重复分配。
解决并发问题的常用办法是为代码加锁，锁的设计保证同时只能有一个CPU取得锁，也就只能有 一个CPU执行锁保护下的代码。
acquire_spin_lock(mem_lock);
for (int i = 0 ; i < N; i++) {
if (mem[i] == AVAILABLE) {
mem[i] = USING;
return i;
}
}
release_spin_lock(mem_lock);另一种思路是为不同CPU维护不同的数据结构
for (int i = 0 ; i < N; i++) {
if (mem[cpuid()][i] == AVAILABLE) {
mem[cpuid()][i] = USING;
return i;
}
}NOTE
上面举例用的代码与本实验并没有太大关联。
讨论：这里我们介绍了 SMP 背景下的内存分配器的两种设计思路（1）统一内存池，但加锁保证并发安全；（2）每个核心维护自己的内存池，无需加锁。两种方案各有优缺点：
- 锁竞争的开销：当系统中有大量线程或进程同时发出内存请求时，方案（1）由于加锁以保证并发安全，内核的内存分配器同一时刻只能处理一个请求，其他请求需要在
acquire_spin_lock处排队等待，这造成了大量的锁竞争开销。早期版本的 glibc malloc 面临类似的问题，其在高并发内存请求场景下性能欠佳。后来，开发人员引入了 tcache，在每个线程处维护一定的缓存，内存请求可以由这些缓存响应，而无需竞争全局内存池。这种方法从一定程度上避免了锁竞争，提高了高并发场景下的性能。 - 负载均衡：虽然每个核心维护自己的内存池的方案极大地减少了锁竞争的开销，但我们仍需注意各核心的内存池大小是否均衡，可用内存是否充足。负载不均同样会导致内存资源利用效率降低，不利于系统的整体性能。
5. 实验任务
IMPORTANT
任务 1
我们为大家提供了一份编写好的 main.c 文件，请将这份文件与你的代码进行 merge，也可以直接用它替换你的代码。如果选择 merge，请确保得到的代码可以正确完成你此前所实现的数据结构初始化，并在其后让所有 CPU 进入 idle_entry。
任务 2
请在 kernel/mem.c 中编写代码，完成下面函数：
void kinit()：初始化内存分配器，这个函数会在内核启动时被调用（你可以在main.c中看到它）。注意：请勿移除其中关于kalloc_page_cnt的初始化，你可以在其后添加你的初始化代码。void* kalloc_page()：分配以PAGE_SIZE对齐的PAGE_SIZE大小内存（即分配一整个物理页）。void kfree_page(void*)：释放kalloc_page分配的物理页。
任务 3
借助前面实现的kalloc_page函数，请继续完成下面函数：
void* kalloc(unsigned long long)：使用你的分配器分配指定大小的物理内存块。我们保证所需物理内存块的大小符合内存分配器一节中的约定，也请注意其中的对齐要求。void kfree(void*)：释放kalloc分配的物理内存块。
本实验所需的简易的内存分配器就由上述 4 个函数组成。要求算法复杂度为
NOTE
例如，对于页的分配，不应使用遍历来查找空闲的页。
上述四个函数的定义已经在 kernel/mem.c 中给出。
INFO
因为我们的测试使用 kalloc_page 和 kfree_page 中的统计代码记录分配器所用物理页的数量，因此要求大家的分配器使用上述两个函数获取内存资源。
我们保证测试时大小超过 PAGE_SIZE / 20 的内存块不超过
一些可能有用的提示：
- 测试时会用4个核同时分配和释放内存，请务必关注并发安全问题。
- 也许你会用上
common/list.h里提供的数据结构。 - 我们不要求在
kfree中调用kfree_page释放物理页，只要保证kfree释放的内存块能被kalloc再分配即可完成要求。如果你实现了释放物理页，可以将其作为你的创新点写进报告里。
idle_entry 中已经编写了测试代码。如果测试通过，你将看到 PASS 和你的物理页用量。
物理页用量受随机因素和测试数据影响，不能完全代表大家的分配器好坏。我们设定如下起评分标准（测试方法为连续运行三次取最小值）：
| # Pages | Score |
|---|---|
| 1200 - 1400 | 100 |
| 1400 - 1500 | 90 |
| 1500 - 1600 | 80 |
| 1600 - 1700 | 70 |
| > 1700 | 60 |
6. 提交
提交方式：将实验报告提交到 elearning 上，格式为学号-lab1.pdf。
截止时间：10月8日23:59
DANGER
逾期提交将扣除部分分数
计算方式为
报告中可以包括下面内容
- 代码运行效果展示
- 实现思路和创新点
- 对后续实验的建议
- 其他任何你想写的内容 (
你甚至可以再放一只可爱猫猫)
报告中不应有大段代码的复制。如有使用本地环境进行实验的同学，请联系助教提交代码（提供 git 仓库）。使用服务器进行实验的同学，助教将在服务器上检查，无需另外提交代码。
IMPORTANT
提交操作：
# 提交最后的代码
git add .
git commit -m "your final commit message"从本次实验开始，我们会在不晚于你提交实验报告时间的最后一次 commit 上批改你的代码，如果你有新的 commit，请在 elearning 上重新提交实验报告。
fduTristin