Lab1: Util

第一个实验在xv6下实现一些用户态工具，不需要对内核进行任何修改。

xv6提供的接口基本和POSIX一致，因此实现这些工具和在linux下实现区别不大。稍有难度的是prime，实现了一个素数筛流水线。

实现时注意及时关闭不再使用的文件描述符，xv6对进程的资源限制很严格，不关闭会导致新的文件打开失败。

Lab2: Syscall

第二个实验有两个编程任务：

  1. 实现一个trace程序，它类似strace，打印被追踪的程序执行的系统调用。
  2. 实现一个sysinfo程序，要求内核回报当前进程数和空闲内存大小。

trace

除被追踪的程序以外，trace还要接收一个mask作为参数。只有被这个mask标记出来的系统调用需要打印。

为了支持mask，实现trace需要修改内核，增加一个新的系统调用，将mask存进进程控制块struct proc中。打印系统调用信息也是在内核中完成的，打印语句加在syscall()中，sys_xxx()函数执行之后。

由于我们修改了struct proc，还要同步修改fork()，在创建新进程的时候把mask也进行复制。如果漏了这一步，会发现使用trace之后，不加trace的进程也会打印系统调用信息。这是因为allocproc()会复用之前结束的进程struct proc所在内存地址，导致mask读到了遗留的脏数据。

sysinfo

sysinfo同样需要新增一个系统调用，参数是一个结构体。内核需要使用copyout()函数将数据拷贝到用户态结构体中。

当前进程数和空闲内存大小分别通过遍历进程列表和分配器空闲链表获得。

Lab3: Page Tables

第三个实验主要涉及xv6的页表。实验中采用的Sv39 RISC-V采用三级页表，将39位(9+9+9+12)的虚拟地址映射为56位物理地址。页表中涉及的其他flag基本与x86-64一致。本实验难度不大。

Speed up system calls

内核创建进程时，额外只读映射一页到用户地址空间，用该页存储一些可以传递到用户态的数据（如进程号），从而使getpid()这样的系统调用不用进入内核。

Print a page table

使用一个三层递归，打印出有效页表项。

Detect which pages have been accessed

实现系统调用pgaccess(void *base, int len, void *mask)，利用页表的access位（硬件设置）判断哪些页被访问过，返回到mask中。

Lab4: Traps

本实验主要涉及xv6中trap的实现。

Backtrace

实现类似gdb中bt的功能。根据riscv的调用约定，fp(frame pointer)位于s0寄存器中，而上一个栈帧的fp和返回地址分别位于fp-16和fp-8的位置上。

注意：xv6中的栈都只有一页，所以发现一个fp和当前fp不在同一页时，就说明已经找完了所有的栈帧。

sigalarm

实现sigalarm(interval, handler)系统调用。当一个进程调用一次sigalarm()之后，内核每隔interval个tick后调用一次handler回调函数。handler中必须调用sigreturn()系统调用，handler结束后，控制流返回到进程被handler打断的位置继续执行。handler是不可重入的。

实现：

  1. sigalarm()在struct proc中设置计数器和回调函数，并在uservec()中检查时钟中断。
  2. 当计数器满足条件，并且没有handler正在执行时（防止重入），就将当前p->trapframe保存到struct proc中，修改p->trapframe->epc为handler的地址。内核会返回到handler中执行。
  3. 实验约定，在handler中一定会调用sigreturn()。此时将struct proc保存的栈帧信息（即进程原始执行流）恢复到p->trapframe中。内核会返回到进程的原始执行流。
  4. 注意sigreturn的返回值不能是0，而要返回p->trapframe->a0，因为这个返回值会被赋值给p->trapframe->a0。

Lab5: Copy-on-Write

本实验实现fork()时的CoW机制，难度要明显比之前的高出一大截。

CoW的思想比较简单，实现细节：

  1. 使用PTE中的软件预留位定义一个PTE_COW新状态，该状态表示该页需要进行CoW，或者说该页在fork()之前是一个可写的页。一个页不可能同时拥有PTE_COW和PTE_W位，但只要拥有两者其一，就说明该页“理应”拥有写入权限，fork()时应该作为可写页处理。
  2. 修改uvmcopy()，不分配新的物理页，而是将新的PTE映射到旧的物理页。如果该页有写入权限（即PTE_COW | PTE_W），则需要修改父进程和子进程的PTE，去掉PTE_W并添加PTE_COW。
  3. 添加cow_pf_handler处理CoW时的page fault，该handler只在store page fault时被触发（scause==15）。cow_pf_handler检查PTE的权限，如果既不拥有PTE_COW位，也不拥有PTE_W位，说明该页本来就是不可写的，此时应该杀死当前进程。否则，handler复制一个新的物理页，让当前进程的PTE指向新页，并移除PTE_COW位，添加PTE_W位。
  4. copyout()函数将数据从内核态拷贝到用户态，它会直接根据用户态虚拟地址，（以软件方式）走用户页表拿到物理地址，然后进行拷贝。很显然，这个过程会绕过基于page fault的CoW实现，因此我们需要把cow_pf_handler的逻辑在copyout()中也实现一遍。

做完以上的步骤，还不能够通过simple test。由于fork出的子进程和父进程使用着同样的物理页，在子进程结束后，清理其页表时会把这些物理页free掉，导致父进程触发page fault。我们还要为每个物理页维护引用计数，只当不被其他进程使用的时候才free物理页。

本实验中使用非常简化的实现，用一个大数组为整个系统中每一页维护引用计数。kalloc()时置引用计数为1，kfree()时递减引用计数，判断是否为0，只在引用计数为0时执行真正的free操作。

在uvmcopy()中，我们需要递增被fork的页面的引用计数器；在cow_pf_handler和copyout()中，我们可能会改变某些虚拟地址指向的物理页，此时要递减原先物理页的引用计数。

注意：

  1. 当某个CoW页面的引用计数为1时（先fork，然后子进程写该地址并触发了CoW，此时只有父进程引用该物理页），我们不需要再复制新的物理页了，只需要改写PTE中的权限即可。

  2. 进程的回收是在父进程wait()中进行的，会对位于该进程页表中的所有物理页调用一次kfree()操作。

  3. 本实验手册中没有提到并发问题，事实上，对页面引用计数的访问是必须拿锁的。考虑注意点1中的情景，如果两个进程几乎同时写入共享物理页，发现引用计数为2。于是他们都认为该物理页不是自己独享的，因此各自分配了新的物理页。此时原先物理页的引用计数会被减为0，即不处于任何进程的虚拟地址空间中，因此也不会在任何进程结束运行时被回收，造成了永久的内存泄漏。

Lab6: Threads

本实验实现一个xv6上的用户态线程库，以及两项对pthread库的使用练习。

Uthread

Uthread在xv6的用户态实现线程。线程的调度是在用户态完成的，每个线程需要显式通过thread_yield()出让控制权，因此属于协作式调度。

对于内核来说，该程序只是一个普通的用户程序，因此这些用户态线程底层只对应着一个内核线程，不能被调度到多个核上执行。

实验的任务是实现线程切换，比较简单。只要像内核的进程调度一样，把context（callee保存寄存器+pc+sp）保存到per thread结构体中即可。创建线程时，context的pc指向传入的待执行函数，sp指向线程栈（位于用户程序data段中）的顶部。

Using threads

实验的后两项任务在linux上完成，分别使用pthread库中的mutex和cond。

任务1是用mutex保证一个简单哈希表的正确性，只要对bucket链表操作加锁即可。

任务2用条件变量实现一个barrier，包括两次等待：

  1. 所有线程递增bstate.nthread，然后等待nthread == bstate.nthread。最后一个线程不进入wait，而是broadcast。
  2. 所有线程递减bstate.nthread，然后等待0 == bstate.nthread。最后一个线程不进入wait，而是broadcase，还要递增bstate.round。

Lab7: Networking

本实验为e1000网卡实现简单的驱动（发包和收包）。

e1000的发送、接收队列分别由tx_desc和rx_desc循环数组标识，每个descriptor包含一个指向内存地址的指针，网卡会通过DMA和内存交换数据，完成收发包操作。

e1000的发送队列由E1000_TDT和E1000_TDH标识，E1000_TDT指向队列中第一个空闲元素，用户程序是生产者，会往这里写入tx_desc，指向需要发送的网络包。E1000_TDH是网卡当前消费到的位置。因此，待发送的数据包位于区间\([TDH,TDT)\)中，初始化时\(TDH=TDT=0\)。

e1000的接收队列由E1000_RDT和E1000_RDH标识，E1000_RDT指向队列中最后一个空闲元素，因此\(RDT + 1\)才是用户程序第一个消费的位置。网卡是生产者，往E1000_RDH处写入收到的网络包。初始化时\(RDH=0, RDT=RINGSIZE - 1\)。

不管是发送还是接收，我们的驱动程序只需要关心\(RDT\)和\(TDT\)，不需要关注\(RDH\)和\(TDH\)。

注意：

  1. 虽然e1000_init()中指定e1000每收到一个包都要发一次中断，但实际观察到的情况并不是这样，因此必须在e1000_recv()中引入一个循环，这种硬件行为可能和QEMU的版本有关系。

  2. e1000会丢弃没有空间接收的报文，实验文档里虽然提及了这个问题，但并没有指出解决方法。测试用例并不会出现这种情况。

  3. e1000_recv()中，判断之后一定要将rx_desc->status清零，否则下次判断就会读到脏数据。

  4. e1000_transmit（）需要拿锁，因为它属于top部分，被操作系统网络栈使用，因此可能会被多个进程调用。e1000_recv()不需要拿锁，它属于驱动的bottom部分，只在中断处理中调用，而xv6保证一个设备的中断处理完之后，才允许它发来下一个中断（见devintr()）。同时，不同于uart驱动，网卡发包和收包使用不同的数据结构，因此不存在race condition。

Lab8: Lock

本实验对xv6的kmem分配器和buffer cache进行并发优化。

Memory allocator

kmem分配器是一个单链表，由一把锁保护，我们的任务是把它拆成per-cpu链表。大部分分配请求由cpu本地的链表处理（仍然要拿该链表锁），因此可以并发执行。当本地链表耗尽时，cpu去拿其他cpu的链表锁并偷取物理页。

注意：

  1. 必须在关中断时才能使用cpuid()的结果，否则当前进程可能被调度到其他核心上。

  2. test3测试用例创建了进程1，分配单页并写入；同时创建了一堆进程跑countfree()为分配器加压。如果进程1恰好在物理页被分完的时候尝试分配，该请求会失败并返回-1。测试代码没有处理这种情形，从而触发一个usertrap excetption。这种情况应该是正常的，未修改的原始代码也会出现这种情况。可以给kalloc()加一次retry，减少这种情况出现。

  3. 偷物理页的一种错误实现：

    1. 拿victim的锁，从victim链表上截取一段。

    2. 释放victim的锁。

    3. 拿自己的锁，将截取下的一段插入自己的链表。

    4. 释放自己的锁。

    问题在于，2和3之间是没有关中断的（拿锁也会关中断），此时可能发生调度，控制转移给另一个进程。此时第1步截取下来的那一段内存页还没有被插入任何一个链表，暂时从系统中丢失了。如果这是系统中仅有的内存，这个新进程就会发生false negative的分配失败。

    正确实现：把victim的锁一直拿到kalloc()返回之前。不用担心死锁，因为当前进程没有物理页可供分配（否则就不用偷别人了），因此别人不会来偷自己（需要有处理这种情况的逻辑），不会拿自己的锁。

Buffer cache

第二个需要优化的部分是buffer cache，它由若干个struct buf组成，每个struct buf都是某个磁盘页在内存中的缓存。和kmem分配器不同，buffer cache不能做per cpu的分割，因为每个cpu都可能访问任意的struct buf。

讲义中要求实现一个哈希表，按照bucket粒度拿锁。我的实现好像并不完全符合讲义的要求，但是稍微简单一点：

  1. 动态分配物理页作为buffer（而非原始代码中静态分配）
  2. 在bget()中如果发现该block没有缓存，则分配新buffer。
  3. brelse()时递减引用计数，如果为0则释放buffer。

Lab9: File System

本实验和xv6的文件系统相关，总体比较简单。

Bigfile

第一个任务是为inode引入二级间接引用，使单个文件可以拥有\(256^2 + 256 + 11\)个块，修改bmap()和itrunc()即可。

第二个任务实现文件的符号链接。需要引入一个symlink(char *target, char *path)系统调用，并修改sys_open()。

Lab10: mmap

最后一个实验会实现一个青春版mmap()和munmap()，满足限定条件：

  1. addr参数一定是0，由内核决定返回的虚拟地址。
  2. fd参数一定是有效的文件描述符，即一定是file-backed mmap。
  3. offset参数一定是0，一定从文件头部开始映射。
  4. prot只可能有PROT_READ和PROT_WRITE。
  5. flags只可能有MMAP_SHARED和MMAP_PRIVATE，且不要求共享映射真正共享物理页。
  6. munmap()指定的区间一定与一个mmap区域的头部或者尾部重合，即不可能取消mmap区域中间的一段映射。

实现的细节已经在实验讲义中给出了：

  1. 我指定每个进程最多拥有16个mmap区域，每个区域为1GB大小，位于虚拟地址空间中的固定位置。
  2. mmap()的length参数可能比实际文件大小更大，这种情况下要把多余部分填0。
  3. 要校验文件的读写权限和mmap()的prot参数是否匹配。要注意私有mmap映射是可以PROT_WRITE映射一个只读文件的。