MIT 6.S081 2021 xv6 labs

汇总一下 2021 年度 MIT 6.S081 的 10 个实验。

代码：https://github.com/CH3CHOHCH3/xv6-labs-2021

问答题直接看对应的 answers-lab.txt 即可。

Lab1 Utilities

通过系统调用实现五个功能。

sleep

用 atoi 把字符串转为数字，直接调用 sleep 即可。

pingpong

注意管道是半双工通信（所以本题需要两个管道），主要用于父子进程通信：

• 读进程要及时关闭管道写端，防止所有写进程退出后 read 不能立即返回 0;
• 写进程要及时关闭管道读端，防止所有读进程退出后 write 不能触发 SIGPIPE 信号;

primes

本题有两个关键点。

1. 并发：从父进程读到数字应立即筛选并写给子进程，读完所有数字再写是错的；
2. 避免递归：fork 会复制父进程的栈空间，递归的写法会让栈越来越小。

综上，可以使用 goto 直接让子进程跳转到 fork 之前，在这个框架下进行素数筛。

find

参考 user/ls.c 中递归目录的写法即可，注意不要递归搜索 . 和 ..。

xargs

题意是读标准输入文件，每读完一行把该行内容作为附加参数，通过 fork + exec 传给目标程序，执行完之后读下一行。

例如 echo "1\n2" | xargs echo hello 等价于顺序执行 echo hello 1 和 echo hello 2。

Lab2 System Calls

给 xv6 增加两个系统调用。需要知道 xv6 系统调用的用户侧接口是 user/usys.pl 实现的汇编代码（核心指令是 ecall），内核的处理是通过 kernel/trap.c 中调用的 syscall 函数（位于 kernel/syscall.c）, 而该函数通过 a7 寄存器（值位于 trapframe）获取系统调用号，并在一个函数指针数组中找到对应的处理函数。

tracing

这个系统调用把一个 int 型 32 位掩码作为参数，要求内核输出该进程及其子进程使用的系统调用号对应掩码位为 1 的所有系统调用名。

可以在 proc 结构体中定义一个默认为 0 的 mask 成员，trace 系统调用的功能就是设定 proc->mask，在 syscall 函数中顺手检查掩码并输出系统调用的名字即可（记得在 fork 中传递 mask 的值）。

sysinfo

这个系统调用以一个 sysinfo 指针为参数，希望内核将当前的空闲内存（以 byte 为单位）和所有处于非 UNUSED 状态的进程数写到目标地址。本题有三个关键点：

1. 获取空闲内存：可以遍历 kernel/kalloc.c 中记录所有空闲页物理地址的链表 freelist，乘以 PGSIZE 即为答案；
2. 获取非 UNUSED 状态进程数：可以遍历 kernel/proc.c 中的 proc 数组，通过 p->state 判断进程状态并计数；
3. 获取参数并写回答案：获取参数通过 argaddr 实现（本质上还是读寄存器 a0 - a5），写回答案通过 copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len) 实现，其作用为将 src 处的 len 字节内容复制到 pagetable 根页表下的 dstva 处。

Lab3 Page Tables

2021 的页表实验比 2020 简单一些。

Speed up system calls

题目要求把进程 pid 写入一个单独的物理页，然后把进程地址空间的一个只读页映射到该物理页，进程就可以不通过系统调用直接读取进程号。

这个题已经在 kernel/memlayout.h 中定义好了 USYSCALL 这个虚拟地址，我们可以直接参考 kernel/proc.c 中对 trampframe 页的处理：

1. 在 allocproc 中用 kalloc 分配物理页，在 proc_pagetable 中完成映射；
2. 在 freeproc 中用 kfree 释放物理页，在 proc_freepagetable 中清空页表；

这样进程就可以直接访问 USYSCALL 这个虚拟地址来读取进程号了。

Print a page table

打印 init 进程的页表，直接参考 freewalk 怎么递归处理三级页表即可。

注意 freewalk 的功能是清空页表自身占用的物理页，它要求叶页表项的映射必须事先已经被 uvmunmap 清空；而 vmprint 不需要考虑这个问题，遇到非 0 的叶页表项直接输出即可。

Detecting which pages have been accessed

实现系统调用 pgaccess(void *base, int len, void *mask)，用于统计从起始虚拟地址起若干连续页面的访问情况。参数含义：

1. base：表示检测起点的虚拟地址；
2. len：表示检测页的数目；
3. mask：表示以掩码形式返回结果的地址；

这个题实现功能并不难，直接遍历所有页，用 walk 找到每个虚拟地址的 pte 然后看 PTE_A 即可（记得看完要置0）。一个需要思考的地方在于，不能预先知道统计多少页；所以我直接用一个 char 存答案，每统计 8 个页面写回一个 byte，熟悉指针的话并不难实现。

Lab4 Traps

异常控制流的内容，核心机制就是 stvec 寄存器存着 kernel/trampoline.S 的 uservec 函数地址，用户态要陷入或者 CPU 接收到中断就保存 PC，然后跳转到这个用户态中断向量处，它会负责保存现场然后跳转到 kernel/trap.c 的 usertrap 处，然后 usertrap 就根据 scause 寄存器进行处理。

xv6 的中断处理流程和王道操作系统给的一般流程基本一致：

• 硬件完成：关中断$\rightarrow$保存断点$\rightarrow$中断服务程序寻址；
• 中断程序完成：保存现场和屏蔽字$\rightarrow$开中断$\rightarrow$中断服务$\rightarrow$关中断$\rightarrow$恢复现场和屏蔽字$\rightarrow$开中断$\rightarrow$返回。

RISC-V assembly

一些简单的 QA，值得一提的就是最后一问 printf("x=%d y=%d", 3); 的输出。只要知道 RISC-V 传参是通过 a0-a7 寄存器传参就知道最终 y 的值应该是 a2 寄存器的值。

Backtrace

在 kernel/printf.c 里实现一个函数来输出目前栈中的函数调用链。实现思路就是先用内联汇编写一个函数 r_fp 从 s0 寄存器读取当前函数的栈帧地址 fp，然后根据 xv6 的栈帧结构，fp - 8 就是函数返回地址（要输出的内容），fp - 16 就是上一个函数栈帧的地址，一直迭代到 fp 所在页的最高地址（xv6 栈从高到低生长）。

Alarm

真正用到 trap 机制的题目，要求实现一个系统调用 sigalarm(int ticks, void (*handler)())，进程调用后每经过 ticks 个时钟中断就跳转到 handler，执行完之后再返回跳转前的位置。

这个题目的第一个关键点在于知道 kernel/trap.c 的 usertrap 中

if(which_dev == 2)
    yield()

是处理时钟中断的内容，那么我们给每个进程增加 ticks、interval 这些 field 用于判断何时应该调用 handler 即可。

第二个关键点是如何实现 handler 的跳转和返回。前面提到硬件在跳转时负责保存 PC，保存的位置就是 sepc 寄存器；而 usertrap 函数会把 sepc 的值写到进程的 trapframe->epc 中，所以我们直接修改 p->trapframe->epc 就能实现返回用户态时跳转到 handler。

为了实现从 handler 中返回，题目提供了一种机制：即每个 handler 都需要在最后调用系统调用 sigreturn。基于此，我们只需要把修改前的 trapframe 做一个备份（直接存在 p->trapframe 所在页即可，因为本来他就只占了 280 多 byte），然后在 sigreturn 中把备份的 trapframe 覆写回来。

Lab5 Copy-on-Write Fork

实验五要求实现写时复制的 fork。为了实现这个机制，要完成以下几个工作：

1. 使用 RISC-V PTE 的 RSW 位为 cow 造成的缺页作标识；
2. 为每个物理页记录一个引用数（可以直接存到数组中），目的是防止出现类似父进程退出之后子进程的物理页也被释放的情况；
3. 在 fork 调用的 uvmcopy 中，不再为子进程分配新的物理页并复制父进程的物理页，而是直接将子进程的虚拟地址映射到父进程的物理页，并更新 PTE_W，PTE_COW，引用数；
4. 在 usertrap 中，scause 的值为 12，13，15 时说明出现缺页，此时检查 PTE_COW 位，若缺页则分配新物理页、复制原有内容并修改页表映射、引用数；
5. 在 copyout 中内核也可能访问 COW 页面，此时的处理逻辑和 usertrap 是一样的；

结合上面的总结，我们有以下几点需要注意：

1. 对物理页引用数组的更新需要谨慎设计加锁逻辑，不要出现父进程创建新物理页之后还没更新引用数组，又切换到子进程让它以为还需要创建新物理页的情况；
2. 把一个 cow 页处理为能够正常访问的页面的功能在两个地方都要调用，可以封装为一个函数；这个函数会修改原有 pte 映射的物理地址，不用调用 mappages ，直接改 pte 即可。

Lab6 Multithreading

这个实验涉及的核心内容是 xv6 如何实现进程切换。总结起来，每个时钟中断后无论是内核态还是用户态，最后都会调用 yield 函数来让当前进程放弃 CPU 并将控制权交给 kernel 中本来运行着的调度线程，调度线程选一个新进程之后再把控制权交给它。

所谓控制权的交换，就是上下文的切换，即寄存器内容的切换。通过修改寄存器 ra 的值，函数的返回地址就能改变。

switching between threads

在 xv6 中实现线程切换。和进程切换的逻辑没有任何区别，给每个线程定义一个 context 成员，保存该线程的现场，然后用汇编代码直接交换 context 即可。

using threads

本题要求用 pthread 库提供的互斥锁实现多线程操作哈希表。题目的哈希表用了头插法，如果不用锁会导致表头指针未指向新元素时切换线程，新线程再插入元素导致内存泄漏。为了加快速度，可以降低锁的粒度，即根据哈希值使用锁。

barrier

本题要求用 pthread 库提供的条件变量实现 barrier：执行到 barrier 的线程会阻塞直到所有线程都执行到这里。这个特性是通过

pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
pthread_cond_broadcast(&bstate.barrier_cond);

这一对函数来实现的：前者要求已获得锁 bstate.barrier_mutex，它会原子地释放锁并阻塞在条件变量 bstate.barrier_cond；后者会唤醒所有等待在 bstate.barrier_cond 上的线程，同时该线程会尝试重新获取它之前释放的锁。

Lab7 networking

在 xv6 中为 E1000 网卡写驱动。看起来相当复杂，但实验基础架构都已经被实现完毕，只要求完成网卡的发送和接收函数。

完成本实验首先需要知道 E1000 发送接收数据包使用的数据结构是所谓的 tx_desc 和 rx_desc。每个 descriptor 会保存一个 mubf 结构的地址、长度、是否发送/接收完毕等信息。在此基础上，以发送函数为例，我们根据指导书知道 regs[E1000_TDT] 记录着下一个发送 descriptor 的索引，而 tx_mbufs 会保存该 descriptor 对应的 mbuf 链表，我们只需要根据指导书提示及时释放、分配 mbuf 并修改命令字段即可。

注意发送函数存在竞争，需要加锁；接收函数位于中断处理程序中，没有竞争，但为了及时处理所有块，需要用 while(1) 将函数体包裹。

Lab8 Lock

memory allocator

内核通过 kalloc 从 kmem 保存的空闲物理页链表中分配内存，而所有 CPU 共用一个 kmem 的代价是锁的竞争非常激烈，导致并行性的下降。题目要求我们为每个 CPU 单独维护一个空闲物理页链表，当前 CPU 的物理页不够用时从其他 CPU 窃取。

本题每个 CPU 仅在自己空白页不够用时才会访问其他 CPU 的物理页链表，注意不要在持有锁的同时尝试窃取其他 CPU 的物理页以避免死锁；如果本 CPU 没有空白页，可以直接获取其他 CPU 的锁然后返回它们的空白页，本 CPU 运行 kfree 时会把空白页加到自己的链表。

buffer cache

本题比上题难得多。首先需要对文件系统有一定了解：内核在内存中为 NBUF 个磁盘块实现了缓存，缓存块被定义在 kernel/buf.h 中；每个 buf 除了保存磁盘块的内容，还记录了设备号、磁盘块号等信息；同时，当某 CPU 想要访问特定块号的磁盘块时，若缓存未命中，则根据 LRU 链表来实现磁盘块替换，因此 buf 还要保存 LRU 链表的指针；此外，读写磁盘块内容时必须加锁，所以 buf 还包含一个睡眠锁。

内核通过 bread 和 bwrite 来实现对特定磁盘块的读写，其中 bread 会通过 bget 函数获取保存着目标磁盘块的 buf（若缓存未命中则将其替换进内存）；当 CPU 不需要读写该磁盘块时，通过 brelse 释放相应 buf 的锁，并判断是否需要更新其在 LRU 中的位置。为了保持每个 buf 中信息被原子的修改、读取，xv6 采用一个大锁 bcache.lock，而本实验的任务就是将其拆分为若干个小锁以提高并行度，要修改的也就是 bget 和 brelse。

在上题中给每个 CPU 分配物理页的方式行不通，因为不同于空白物理页用谁的都一样，每个 CPU 都可能不得不访问某个特定的磁盘块。根据 hints，我们将 buf 依据 blockno 拆分为 13 个桶，每个桶单独维护一个链表和一个锁。本题的难点在于，在某个桶中找不到特定磁盘块时，我们需要在已获取当前桶的锁后，去请求其他桶的锁来尝试驱逐页面，这就很可能造成死锁。

如果规定顺序获取每个桶的锁，那么效率估计还不如大锁，所以缓存未命中时，我们可以先放弃当前桶的锁，然后挨个申请其他桶的锁来驱逐页面。但是这样做引出了新的问题：多个 CPU 对同一个磁盘块进行 bget 时，驱逐过程不加锁可能会导致为了一个页面进行了多次驱逐。考虑到题目 hint 强调：

It is OK to serialize eviction in bget.

所以可以定义一个驱逐锁，同时间只允许一个 CPU 进行驱逐；同时获取该锁后马上检查其他 CPU 是否已经完成了驱逐，若是则直接返回即可。具体的驱逐过程编写也是颇有技巧，但是不在此赘述，只要记得将目标 buf 从原来的桶移入当前桶时，两个桶的锁都必须保持在手中，同时不要忘记释放驱逐锁即可。

Lab9 File system

文件系统是一个很大的模块，本实验也只是涉及到了其中的一小部分。总的来说，完成本实验大致要了解这些概念：

• inode：磁盘上的 inode 记录着一个文件的类型、（硬）链接数、大小和所有数据块（包括直接块和各级索引块）对应的块号等信息；内存中的 inode 还会额外记录文件的设备号、inode 编号、内存中的引用数、合法性等信息；
• dirent：一个目录项对应一个文件或目录，dirent 中记录着文件名和 inode 编号，目录型文件的 inode 记录的数据块保存着目录中所有文件的 dirent；
• 给定文件路径，想要找到其对应的 inode，需要从进程的工作目录或根目录 inode 开始寻找对应名字的 dirent；

Large files

xv6 文件系统定义的 inode 中包含 12 个直接块和 1 个一级索引块，因此能支持的最大文件可以有 $12 + 256 = 268$ 个磁盘块；本题要求将其改为 11 个直接块、1 个一级索引块、1 个二级索引块，这样修改后的文件系统支持最大文件块数为 $11 + 256 + 256^2=65803$。

xv6 中 bmap 函数负责读取 inode 的索引块，返回 inode 的第 bn 个数据块对应的磁盘块号。这个题目只需要仿照原版 bmap 对一级索引块的处理，关键的 api 是通过 bread 把指定块号读入内存，二级索引只不过是需要再读一次。记得修改 itrunc 使其能够释放 inode 的所有数据块。

Symbolic links

这个题目会略难一些，要求在 xv6 中实现软链接。首先要知道软链接是一个独立的文件，有自己的 inode（硬链接则是不同 dirent 指向同一个 inode）；软链接的 inode 中保存其文件类型（xv6 中是 T_SYMLINK）和指向文件的路径（建立软链接时建议用绝对路径，否则移动软链接会找不到指向的文件）。在进程 open 一个软链接时，内核会自动递归寻找其指向的文件（用户进程可以通过指定 O_NOFOLLOW 参数来打开软链接本身）。

题目通过实现一个系统调用 symlink(char *target, char *path) 在 path 处创建一个指向 target 的软链接。这里完全可以参考 sys_mknod 创建设备文件的思路，通过 create 在指定路径创建一个 T_SYMLINK 类型的 inode，再调用 writei 向 inode 中写入目标路径。接下来需要修改 open，获取到目标 inode 后判断其是否为软链接类型，如果是则递归寻找其指向文件的 inode，这里的关键 api 是：

• readi：用于读取软链接的文件内容以确定其指向文件的路径；
• namei：根据路径返回 inode 指针。

如果软链接之间形成了环，可以在递归层数超过 10 时直接报错；记得关注 inode 的锁是否在递归中及时释放了。

Lab10 mmap

本实验要求为 xv6 实现一个系统调用 mmap。整个实验并没有太多难点，但是代码量比较大，调试也会有一定难度。实验只要求实现 mmap 的一个（玩具）功能，即将进程的一段虚拟地址空间映射到一个打开的文件中，并通过读写这段地址来间接访问文件。这样做可以方便多个进程对同一个文件的共享（尤其是只读的代码段等），也可以加速一个进程对文件的读写（不必通过 read 和 write 频繁进入内核空间并访问缓冲区等）。

值得一提的是，常用的 malloc 作为一个用户态库函数，其底层也依赖系统调用 mmap （或是 sbrk）。

整个实验的核心是指导书中提示的 VMA 结构，它保存着一块被映射虚拟地址的起点、长度、文件描述符、读写权限、是否共享等关键信息，每个进程都应当有自己的 VMA 数组（或链表）。本实验的核心问题在于如何为进程寻找未被使用的虚拟地址。事实上我们可以直接从进程的 sz 成员开始分配，虽然在 munmap 后会导致内存泄漏，且释放进程内存时会出现很多为 0 的 pte，但足以满足本实验的要求。

在 sys_mmap 中设置好 VMA 后，下一步是在 usertrap 中完成对缺页异常的处理（因为采用了懒分配），也就是判断是否为 mmap 导致的缺页，如果是则分配新物理页，将文件相应位置内容读进来，并且完成用户进程的页面映射。接下来需要实现 munmap，思路就是清空 pte，释放页面，并根据页面是否为 shared 决定是否需要写回原文件。至于 fork 和 exit 的修改不必赘述。