XV6操作系统 - mit6.S081

发表于 分类于

MIT6.S081操作系统

课程介绍 · 6.S081 All-In-One (dgs.zone)

简介 - MIT6.S081 (gitbook.io)

页表

Xv6为每个进程维护一个页表，用以描述每个进程的用户地址空间，外加一个单独描述内核地址空间的页表。内核配置其地址空间的布局，以允许自己以可预测的虚拟地址访问物理内存和各种硬件资源。图3.3显示了这种布局如何将内核虚拟地址映射到物理地址。

image-20220526105709735

内核的代码段和数据段虚拟地址是直接映射为物理地址的，否则无法进行前期内核地址空间页表的初始化。内核页表初始化，即为一些I/O硬件在内存中的映射区域建立页表项，整个操作系统代码有一个全局指针变量为内核页表页全局目录，从开始即为这个页全局目录初始化页表项，在xv6操作系统中有三级页表，首先为内核页全局目录申请一个物理页，然后对你想要建立页表映射的虚拟地址找到其页表项的位置，然后检查其是否有效，如果有效，说明这个页表项已经被分配了，那表示你代码有bug，一个物理页被分配了多次。一般来说建立页表映射对应的页表项都是无效的，接着你便可以使用对应的8字节页表项物理空间，你将其初始化，比如其对应的物理地址、可读可写可执行权限等等。若查询页表的过程中，比如查一级页表发现二级页表还不存在，就得申请一个物理内存作为二级页目录。以上就是xv6操作系统的内核页表建立与映射的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
pte_t *
walk(pagetable_t pagetable, uint64 va, int alloc)
{
  if(va >= MAXVA)
    panic("walk");

  for(int level = 2; level > 0; level--) {
    pte_t *pte = &pagetable[PX(level, va)];
    if(*pte & PTE_V) {
      pagetable = (pagetable_t)PTE2PA(*pte);
    } else {
      if(!alloc || (pagetable = (pde_t*)kalloc()) == 0)
        return 0;
      memset(pagetable, 0, PGSIZE);
      *pte = PA2PTE(pagetable) | PTE_V;
    }
  }
  return &pagetable[PX(0, va)];
}

建立内核页表后，将内核页全局目录装入对应的寄存器，比如X86系统就是CR3控制寄存器，接着便可以刷新TLB快表，开启分页模式了。

在xv6中，初始化阶段会统计所有可用的空闲物理内存，将其按每页在最前面加上指针连成一个空闲链表，用于物理内存的管理。

发现进程用户页表和内核页表的实现是分离的，并不是和我之前想的一样一体化查询。在内核态运行时装入内核页表到对应寄存器中，返回用户态时，将进程的用户页表移入寄存器。换句话说，内核态中要访问用户虚拟地址，也需要经过一次手动的用户页表映射，比如在 copyout函数中就有所体现；但用户态想访问内核的虚拟地址，会出现页表项不存在的错误，直接杀死进程。

然而在linux系统中,，进程PCB里只会放一个页表,，就是pgd指针指向的页全局目录。linux在内核态和用户态切换时不需要切换页表.

因为内核段的数据和代码的页表项不存在PTE_U标志位，表示用户代码不可访问

换句话说, 每个进程都拥有一份内核页表的拷贝. 在linux源码中有一个全局变量, 就是内核页表指针, 如你在内核中申请虚拟地址, 比如调用 vmalloc()函数, 它会直接申请对应虚拟地址的物理页, 并建立好全局变量的内核页表指针对应的页表映射, 但这里存在一个问题. 即进程页表中的内核部分并没有更新, 它还是指向一个不存在的物理空间. linux对其的处理不是每次更新全局内核页表就依次写入每个进程页表, 这样效率太低, 它利用了缺页中断, 在进程首次访问到这段自己进程页表中还没有建立映射的部分时, 缺页异常函数会读取全局内核页表, 并更新进程页表, 然后再一次访问. 以上就是linux的操作方式。

新发现：linux好像只需要让每个进程只维护一个私有的最高级的页目录，而对于二级甚至三级页目录可以共享(即进程页表和全局内核页表的顶级页目录PTE指针实际上指向的为相同的二级页目录)，这样对于二三级的页目录建立映射时实际上不会影响进程的页表，只有分配了一个新的顶级页目录的pte(页表项)时才会出现不一致。

在X86中,系统调用CPU会根据提前存好的寄存器找到内核栈的位置,自动保存用户代码返回地址RIP | 用户栈指针RSP, 但RISC-V不会,进程用户态页表和内核页表的切换需要手动执行,并且内核栈用户栈切换也需要手动执行,它只保证调用ecall指令,能够执行一段汇编代码,因此XV6操作系统是在这段汇编中更改上下文的.

ecall指令只会作最简单的代码跳转，以及保存用户层的下一条代码到寄存器中，在ecall返回值弹出到程序计数器中。寄存器保存与切换、内核栈切换、用户页表和内核页表的切换等等ecall都不会做。这些都得操作系统程序员完成，它给了最大的灵活性，因为有的操作系统比如linux在用户态和内核态切换时甚至不需要切换页表，进程在整个上下文中用的是同一个页表。这也同样为什么叫做RISC-V精简指令集。

RISC-V判断trap是异常还是syscall还是中断，通过一个scause寄存器的值判断，操作系统通过这个值走不同的逻辑

系统调用函数

exec系统调用：

首先各个操作系统的ELF格式不同，因此exec解析ELF文件的代码有所差别。

xv6操作系统实现。会清空进程原有的用户页表以及对应的物理内存，内核态页表不变。接着解析ELF文件，先解析ELF文件头部，得到段数以及每段对应的偏移，然后读每一段的头部，在xv6中会直接分配物理内存并建立对应的段页表映射，将各个段装入进程地址空间的每个部分，现代操作系统linux中此时还不会分配物理内存给段，而是首次使用时才会去读对应段并分配物理内存。接着分配用户栈内存，一般来说分配的栈大小可以由用户指定也可由内核使用默认值，比如一页或两页物理页。接着将参数argc、argv的值逐个复制到用户栈指针所指的位置，再同样复制argv指针到用户栈。所以在一般的操作系统中，Cmain函数执行时传入的参数就在栈指针sp之上。

最后设置exec的返回pc值、用户栈指针到trapframe (Tss)，供系统调用返回时能弹出到寄存器中，pc指向第一个执行的函数，比如_start，进行一系列初始化后就进入了Cmain函数。

exit系统调用：

此系统调用用于退出进程。在xv6源码中，内核大致做了以下事情

  1. 减少打开的所有文件的引用计数

  2. 将该进程的子进程全部归于init进程下，也就是所谓的孤儿进程

  3. 唤醒init进程，注意这个做法主要是防止该进程终止后会将它的子进程的父亲归于init进程，因此有可能init进程需要在wait()函数上唤醒，实际上也可能不需要唤醒导致虚假唤醒。但这是内核必须做的。

  4. 唤醒该进程的父进程，因为有可能父进程就在wait状态下等待，若确实是，则将其状态改为改为Runable。

    内核存在一种机制叫做chan，调用sleep睡眠时可以传入这个chan参数，表示睡眠到这个chan上，是因为这个原因睡眠的，当唤醒时调用wake(chan)传入chan参数，就能精确唤醒睡觉在这个原因上的进程了

    比如readline(0)向控制台UART串口读一行数据，假如当前UART串口读完对应硬件数据后没读到换行符，就需要调用sleep(chan)，睡眠在对应的UART导致的睡眠原因上，当硬件中断读取到了换行符便唤醒所有等待在这个chan上的进程，将进程状态改为runable

  5. 最后将本进程改为僵尸态，然后就可以执行调度函数了，进行进程切换

进程无法清理自己的资源，因为它还在使用对应的内核栈和页表等，因此内核需要其父进程清理

wait系统调用

当一个进程调用了wait系统调用，它会扫描进程表单，找到父进程是自己且状态是ZOMBIE的进程。它释放了trapframe，释放了page table。如果我们需要释放进程内核栈，那么也应该在这里释放。最后将进程状态状态标记为UNUSED，供下一次进程使用时可以复用。init进程的工作就是在一个循环中不停调用wait，因为每个进程都需要对应一个wait，这样它的父进程才能调用freeproc函数，并清理进程的资源。

pipe系统调用：

1
2
3
4
5
6
7
8
struct pipe {
  struct spinlock lock;
  char data[PIPESIZE];
  uint nread;     // number of bytes read
  uint nwrite;    // number of bytes written
  int readopen;   // read fd is still open
  int writeopen;  // write fd is still open
};

管道内核实现很简单, 内核分配一页物理页用于管道结构，管道结构实际上就是一个读索引、一个写索引，一个字节数组存放数据以及其管道大小，当然还有管道的一些状态，比如读端是否关闭、写端是否关闭等。一般来说，管道内部自带自旋锁，所以用管道时完全不用担心多核问题。

你向管道读，实际上就是增加读索引，读索引对管道大小取余就是其真正在字节数组中的位置。如果你读管道时，其读写索引相等了，说明管道为空，内核会睡眠对应进程，等待在对应事件上。而当往管道写，同理就是增加写索引，如果写索引等于读索引+管道大小，就表示写满了，内核也会将其睡眠。同理，唤醒也是互相在读写时唤醒对方。

kill系统调用

Unix中的一个进程可以将另一个进程的ID传递给kill系统调用，并让另一个进程停止运行。如果我们不够小心的话，kill一个还在内核执行代码的进程，会有一些我几分钟前介绍过的风险，比如我们想要杀掉的进程的内核线程还在更新一些数据，比如说更新文件系统，创建一个文件。如果这样的话，我们不能就这样杀掉进程，因为这样会使得一些需要多步完成的操作只执行了一部分。所以kill系统调用不能就直接停止目标进程的运行。实际上，在XV6和其他的Unix系统中，kill系统调用基本上不做任何事情。

它先扫描进程表单，找到目标进程。然后只是将进程的proc结构体中killed标志位设置为1。如果进程正在SLEEPING状态，将其设置为RUNNABLE。这里只是将killed标志位设置为1，并没有停止进程的运行。所以kill系统调用本身还是很温和的。

而目标进程运行到内核代码中能安全停止运行的位置时，会检查自己的killed标志位，如果设置为1，目标进程会自愿的执行exit系统调用。比如在系统调用的代码，实际进入系统调用之前，如果进程已经被kill了，进程会自己调用exit。那假如此时要杀死的进程正在用户态执行呢？我们知道，我们无法直接修改用户代码去调用exit。实际上当一个定时器中断打断了进程的运行，我们可以通过检查发现进程是killed状态，之后进程会调用exit退出。

所以kill系统调用并不是真正的立即停止进程的运行，它更像是这样：如果进程在用户空间，那么下一次它执行系统调用它就会退出，又或者目标进程正在执行用户代码，当时下一次定时器中断或者其他中断触发了，进程才会退出。所以从一个进程调用kill，到另一个进程真正退出，中间可能有很明显的延时。

symlink系统调用

创建符号链接。先分配一个inode，设置其inode类型为符号链接，接着往其文件第一个块中写入链接的路径。对原路径不会做任何检查。

但open打开它时，open需要传入其打开方式，如果是传统的文件打开方式，内核会递归查询，内核的环检测算法很简单，比如最多递归10次，10次还没有找到最终的不是符号链接的文件就直接open失败返回-1，否则就打开打开对应正确的文件。内核同样提供了宏定义让用户打开符号链接本身这个文件。

lab3页表：

修改内核使每一个进程在内核中执行时使用它自己的内核页表的副本，修改调度程序使得切换进程时也切换内核页表，内核页表中包含用户页表，使得CPU得以在内核态访问用户空间而无需操作系统手动页表转换。

然而正如上面linux的对比，这样做如果在内核中申请了新的物理页面并建立的内核页表对应的映射，会导致与其他进程的内核页表不同步。

.bss段的优化

操作系统在加载.bss未初始化的全局变量段时，做了内存优化。我们都知道内核加载程序一开始不会分配实际物理内存，而是用缺页来惰性分配。但内核实际对exec函数存在一种优化，加载.bss段时让它映射到全为0的页，因为.bss段本来最初就是0的，并且内核会将这个页表项标记为只读。这样意味着你修改.bss段的全局变量时会页错误，此时执行页错误处理程序，它会根据进程页错误的虚拟地址所在是.bss段为其分配物理内存并建立映射。这也是exec的优化。

但是很显然，.data段无法做这样的优化，但.data段和.text段可以按需分配，即一开始并不分配虚拟地址或者说建立页表映射，当访问到这段时，触发一个page fault，内核检测后发现这段为文本段，则可以从对于ELF文件中加载对应段进物理内存并建立页表映射，然后跟缺页程序一样，重新执行这个用户代码。

在之前对程序的加载只知道是惰性分配，学习了操作系统源码才知道里面的细节。

trap

  1. 实现打印函数栈帧功能
  2. 实现用户级异常(中断)，类似于时间信号alarm机制
    • 异常处理过程必须在用户态执行，但执行完后需要切换到原程序代码，但C语言不保证任何寄存器的修改，因此在进入信号处理函数前内核需要保存用户寄存器组，在出异常函数时恢复用户寄存器组，并修改程序计数器为之前代码的位置。这意味着内核需要为此功能额外提供一个trapframe来保存寄存器组(我们知道系统调用会切换寄存器组就有这样一个trapframe)。
    • 防止重复调用，因为我们内核只提供了一个用户级别的trapframe，重复调用会被覆盖，导致程序崩溃。

RISC-V硬件系统对待异常、中断、系统调用都是相同的方式，它会将程序计数器更改为我们之前设置在 stvec寄存器中的值，并保存之前的执行代码地址到另一个寄存器 sepc。在用户态trap时和内核态trap时执行的汇编代码是不同的，在用户态执行的汇编代码会处理系统调用的陷入，而内核态发现trap时如果发现是个真正的异常比如除1，内核会直接调用panic崩溃，因为在内核态执行代码中不应该出现任何的非中断异常，某种内核就应该崩溃。但如果是用户态出现这种异常，内核可以对其处理，比如直接杀死进程并切换进程。

由页面错误驱动的COW fork可以使父级和子级安全地共享物理内存。当CPU无法将虚拟地址转换为物理地址时，CPU会生成页面错误异常。Risc-v有三种不同的页面错误: 加载页面错误 (当加载指令无法转换其虚拟地址时)，存储页面错误 (当存储指令无法转换其虚拟地址时) 和指令页面错误 (当指令的地址无法转换时)。scause寄存器中的值指示页面错误的类型，stval寄存器包含无法翻译的地址。

COW fork中的基本计划是让父子最初共享所有物理页面，但将它们映射为只读。因此，当子级或父级执行存储指令时，risc-v CPU引发页面错误异常。为了响应此异常，内核复制了包含错误地址的页面。它在子级的地址空间中映射一个权限为读/写的副本，在父级的地址空间中映射另一个权限为读/写的副本。更新页表后，内核会在导致故障的指令处恢复故障进程的执行。由于内核已经更新了相关的PTE以允许写入，所以错误指令现在将正确执行。

操作系统如何判断是fork的写时复制还是真正的错误的往一个只读页写？

几乎所有的硬件都为页表项提供了多余的位，供操作系统管理，因此可以定义一个位为私有的写时复制。当然也可以定义进程内存区域结构变量，像linux的vm_area_struct一样，对不同的地区进行分别管理，这样也能知道这个页错误是不是私有的写时复制。

内存惰性分配

即用户调用sbrk()请求内存时，在内核中只修改了进程占用的空间大小，因为在xv6中进程地址空间是从0开始的，记录了进程占用空间大小也就记录了最高的地址。

那么若此时用户访问这个页面则会触发page-fault，在trap处理程序中通过scause寄存器得知是页错误，内核对页错误的虚拟地址进行检查(页错误时的虚拟地址会放到一个寄存器中)，比如它必须要大于栈的最高地址而小于进程占用内存大小。若检查无误，便给其分配一个物理内存并建立映射。在陷入程序返回时，设置其返回地址为刚刚触发缺页的用户代码，即会再执行一次该代码，这次就会成功。

在内核代码中，需要十分小心的处理对应地址，用户态下可以触发页错误并陷入处理程序，但在内核中不行，因此内核编程时所有涉及用户地址的函数都需要提前对其检查，而不能依赖于页错误处理。

归根结底，内核对自己是完全信任的，你不应该在内核中手动触发异常，这种情况内核就应该崩溃。内核代码中唯一能触发trap只能是外部中断。

fork的copy-on-write

  1. 选取PTE中的保留位定义标记一个页面是否为COW Fork页面的标志位
  2. 设置内核全局变量，记录各个物理页的引用计数，类似于linux的page结构，负责管理物理内存的一些属性
  3. 在fork时只复制页表，而对其pte指向的物理页修改PTE为只读并加上PTE_F位，表示只读的写时复制
  4. 当子进程对该虚拟地址进行写操作时，会触发page-fault，在内核处理程序中会检查pte是否有PTE_F位，若是则表示它是私有的写时复制物理页，则分配一个新物理页并建立映射，减少原来的物理页的引用计数。此时修改PTE属性为可读可写，而不是之前的只读。 (父进程在访问时若发现引用计数为1，则修改其pte可读可写即可)

在内核代码中，经常有内核空间到用户空间的复制，但此时用户代码传过来的虚拟地址很有可能还没分配物理页，内核必须对其检查，而不能依赖于page-fault的处理程序，因为内核对自己是完全信任的

  1. 当进程退出时，对于其物理内存只会减少引用计数，当然页表占用内存还是会完全回收。

注意操作物理页面时，需要加自旋锁，让各CPU都能操作

中断和设备驱动

控制台输入

驱动程序管理的UART硬件是由QEMU仿真的16550芯片。在真正的计算机上，16550将管理连接到终端或其他计算机的RS232串行链路

控制台驱动程序通过连接到RISC-V的UART串口硬件接受人们键入的字符。控制台驱动程序一次累积一行输入。用户进程，如Shell，使用 read系统调用从控制台获取输入行。

UART硬件在软件中看起来是一组内存映射的控制寄存器。也就是说，存在一些RISC-V硬件连接到UART的物理地址，以便载入(load)和存储(store)操作与设备硬件而不是内存交互。有几个宽度为一字节的UART控制寄存器。例如，LSR寄存器包含指示输入字符是否正在等待软件读取的位。这些字符（如果有的话）可用于从RHR寄存器读取。每次读取一个字符，UART硬件都会从等待字符的内部FIFO寄存器中删除它，并在FIFO为空时清除LSR中的“就绪”位。UART传输硬件在很大程度上独立于接收硬件；如果软件向THR写入一个字节，则UART传输该字节。

UART对接收到的每个字节的输入生成一个接收中断，对发送完的每个字节的输出生成一个发送完成中断。

当read读控制台时，内核会执行对应控制台读取的函数，此函数只是去读一个内核缓冲区，此内核缓冲区缓存了键盘串口发送过来的字符，内核源码就是一段while循环读满你传给read系统调用的字节数，一但读完了内核的对应键盘串口缓冲区，意味着此时键盘还没有输入足够的字节数以至于中断处理程序还没有将其拷贝到内核缓冲区，因此此时内核会调用sleep函数将对应进程睡眠。当然如果此时内核缓冲区有可读字节数，内核都会将其拷贝到用户空间并前移内核缓冲区的读索引变量表示已读完。当读够足够的字节数或者存在换行符，便会从内核中返回到用户空间，表示系统调用完毕。

当键盘也就是uart串口中断时，中断处理程序会将其字符一个一个拷贝到内核缓冲区，并最后会尝试唤醒等待在之前内核缓存区读索引位置的sleep状态进程，也就是将其改变可调用状态。

0 1 2文件描述符实际上都是控制台，它在内核源码中只是open()控制台，然后dup两次文件描述符0。

控制台输出

write系统调用最终会走到一个内核的字符写函数，在内核中会维护一个内核全局变量-输出缓冲区，这样写进程就不必等待串口发送完毕而可以通过中断来解决两者处理速度不一致的问题。

该字符写函数会将用户需要写的字符全部放入输出缓冲区，然后尝试往对应的uart串口写一个字符，能不能写一个字符的信息，可以在对应的串口控制器的一个寄存器LSR中可以读取，若当前字符设备还在处理则内核会直接sleep进程进行进程调度。若此时字符设备是准备好的，内核会将其中一个字符放入对应的硬件寄存器中，然后同样sleep进程。

对于第一个字节剩余的缓冲字节，会通过中断处理程序进行处理，当字符设备处理完了那一个内核发送的字节，它便会触发一个中断，该中断处理程序便会唤醒睡眠在发送串口的进程，让其状态变为runable也就是可调度状态等待下一次调度，进程唤醒后将下一个字节放入对应的硬件寄存器，以此反复，直到最终缓冲区的字符全部发送完毕。

通过缓冲区和中断机制将设备活动与进程活动解耦，这种解耦可以通过允许进程与设备I/O并发执行来提高性能，当设备很慢（如UART）, 这种解耦尤为重要。这种想法有时被称为I/O并发

UART实际上支持一次传输4或者16个字符，所以一个更有效的驱动会在每一次循环都传输16个字符给UART，并且中断也是每16个字符触发一次。更高速的设备，例如以太网卡通常会更多个字节触发一次中断。

线程调度

在一般的线程调度的书籍中，一般都这么描述线程切换：保留前一个线程的上下文到其内部的一个结构中，然后切换寄存器组到将调度的线程中。但这里有一些细节问题，其一，线程调度的内核代码应该在哪里执行？它还是在旧的线程上下文中吗？如果是，那意味着线程调度的代码用到了老线程的内核栈，那以后切换回来内核栈不就是已经被改变了？我们知道线程切换的汇编可不会管你内核栈有没有不应该的数据，它也没办法检测，因此这样是不安全的。因此我们需要解决这个问题。

因此xv6调度程序在每个CPU上都有一个专用的数据结构（保存寄存器和栈）。

从一个线程切换到另一个线程需要保存旧线程的CPU寄存器，并恢复新线程先前保存的寄存器；栈指针和程序计数器被保存和恢复的事实意味着CPU将切换栈和执行中的代码。

在xv6中，操作系统初始化完后的最后一个函数叫做schedule，此函数功能很简单，执行一个永不跳出无限循环，在循环中找到可以调度的进程，然后用线程切换的汇编代码切换过去。保存当前的寄存器组在CPU专用的数据结构中，然后切换到对应进程的PCB中保存的上下文中。当一个进程调用yield放弃CPU时，它的切换对象或者说函数参数并不是另一个将要切换的进程，它实际上是切换到我们之前保存到CPU专用数据结构中的上下文。这样就正确的处理了进程切换，换句话说，内核用了一个中间层的切换代码，它具有自己的栈寄存器组，所有的进程调度算法的代码都写在这里，以实现被切换进程和切换进程的隔离。

CPU专用数据在内核编程中十分有用，不仅可以存放其上下文，也可以防止CPU的ID号，表示这是第几个CPU，这在内核实现进程绑定到一个CPU上运行也发挥了重要的作用。

文件系统

底层往上层叙述

磁盘高速缓存层 buffer cache

在内核初始化代码中会初始化一定数量的缓冲区供磁盘缓存。一般来说该缓存区会有valid字样表示是否包含磁盘块副本，有disk字样表示是否交给磁盘(脏的)。

当走到buffer cache这一层时，上层会调用 bread函数，它会根据设备号和磁盘块号去buffer cache获取缓冲区。如果遍历后没有对应的磁盘缓存，内核会为其创建一个缓冲区，这意味着需要找到一个可重用的缓冲区，如果此时有没有使用的缓冲区当然最好，若每个都在使用，也就是对应缓冲区的引用计数大于0，则内核就需要使用一些替换算法来替换一个可用缓冲区，在xv6操作系统中会直接panic崩溃。

当最终获得了一个块缓存，会调用最底层的跟硬件相关的驱动去获取磁盘块放置到对应的块缓存中，一般来说这时进程会调用sleep睡眠等待对应块返回。

在使用者使用完缓冲区后，如果你进行了修改，则需要调用bread对应的bwrite将数据写入磁盘。最后调用对应的b-release释放缓冲区，实际上就是减少缓冲区的引用计数并释放对应的自旋锁让其他CPU可以访问。<它会将缓冲区移动LRU链表最前面表示最近使用的 (这取决于操作系统实现)>。

日志层和磁盘I/O调度层

实际上对磁盘写入时，内核会使用日志作为其上层。日志可以崩溃恢复，实现原子性的文件修改，而保持文件系统的一致性。换句话说，当sys_write走到发现inode类型为磁盘文件时，其在写入磁盘前会先记录日志，对于每一个内存中的buffer cache操作都会进行对应的日志记录，内核会积累一定的系统调用的次数，然后在合适的时机调用commit函数提交日志，内核首先会将日志标记为已完成并向磁盘写入，接着才会将对应的buffer cache刷入磁盘。

日志层不仅实现了crash safe，同样提高了磁盘I/O的性能，因为日志层积累了一定的I/O数量或者积累了多个系统调用的对磁盘的修改，使磁盘I/O得以批处理，比如对一个磁盘块的写入改成了对缓存的操作，实际上，内核的磁盘I/O调度算法比如著名的电梯算法就是在这实现的，这也大大增强了文件系统的性能。

一般来说这里都是文件系统最复杂的地方，也是优化最多的地方，ext3文件系统对其做了非常多的优化和研究，比如运行多日志事务并行，采取内核线程提交事务使I/O和用户线程并行等等。这也是为什么你想要真正刷盘你需要调用fsync，因为文件系统做了一系列的优化批处理提交磁盘I/O请求。

索引节点层inode

术语inode（即索引结点）可以具有两种相关含义之一。它可能是指包含文件大小和数据块编号列表的磁盘上的数据结构。或者“inode”可能指内存中的inode，它包含磁盘上inode的副本以及内核中所需的额外信息。

磁盘上的inode都被打包到一个称为inode块的连续磁盘区域中。每个inode的大小都相同，因此在给定数字n的情况下，很容易在磁盘上找到第n个inode。事实上，这个编号n，称为inode number或i-number，是在具体实现中标识inode的方式。

内核会将活动的inode集合保存在内存中，并同样设置了inode缓存结构，以减少频繁的读取磁盘上的inode。只有当C指针比如一些进程的file结构的inode指针引用某个inode时，内核才会一定在内存中存储对应的inode，否则就会被释放到磁盘或者保存在inode缓存中等待下一次读取。inode结构中有一个引用计数的变量，用于统计有多少C指针正在指向它，一般来说该指针来自于进程打开的文件描述符、进程当前工作目录等。

inode包含内容：文件权限，文件类型，文件大小，以及其在磁盘上的存储块号，存储块号的指针也分为直接块和间接块，比如小文件就可以一次查询inode就能得到其分布，而大文件在其高地址处就需要多次间接查表，类似于多级页表。

目录层

其实目录也是一种文件，它也拥有对应的inode，只不过其inode指示它的类型为目录。目录文件其存储的数据是一系列的目录条目（directory entries）。每个条目包含一个名称和一个inode编号。

路径名查找：如果是从根目录查找，根目录对应的inode结点是一直保留在内核中的，则依次顺着inode查找即可。而对于当前目录查找，在进程PCB中，会存有一个变量缓存当前工作目录的inode节点指针，便可用这个变量进行查找。

文件描述符层

Unix界面的一个很酷的方面是，Unix中的大多数资源都表示为文件，包括控制台、管道等设备，当然还有真实文件。文件描述符层是实现这种一致性的层。

每个进程PCB中提供了自己的打开文件表，文件描述符即对应的索引下标。每个打开的文件都由一个struct file表示，它是inode或管道文件的封装。具体文件类型存在file结构里还是inode结构取决于内核的实现，比如linux就是任何文件都存在inode这种结构。file结构大概有这些成员，比如其偏移量、类型、是否可读可写等等。每次调用 open都会创建一个新的打开文件（一个新的 struct file）：如果多个进程独立地打开同一个文件，那么不同的实例将具有不同的I/O偏移量。

一般来说，file结构的集合在内核中有一个全局变量全局文件表进行存储，也可以理解为一种缓存，类似于inode，只不过inode是作为磁盘的缓存，而file是作为物理页分配的缓存，否则每次进程每次创建一个file结构都得为其分配对应的物理内存。

当一个进程删除了另一个进程正在打开的文件会发生什么？

答：删除文件只是减少其link数，不会减少其引用计数ref，因为有一个进程已经打开了对应inode，其引用计数必定大于0。而内核删除对应磁盘文件只会在两者均为0时才进行，因此对应文件的目录项会消失，即目录树中将找不到对应文件，但实际上内核还维护着对应的文件，直到进程处理完毕退出时或者手动close对应文件描述符时，才会真正从磁盘删除文件。

Locks

该lab修改内核以减少内核中的锁争用，提高CPU的并行性。测试会统计自旋的次数，目标是将其尽可能降低。

Memory allocator

原实现将空闲物理页用一个单向链表管理，作为内核的全局变量，因此每个CPU并发的请求物理页时，外部需要加上自旋锁，造成物理页分配时的锁争用。

改善：为每个CPU维护一个空闲列表，每个列表都有自己的锁。因为每个CPU将在不同的列表上运行，不同CPU上的分配和释放可以并行运行。主要的挑战将是处理一个CPU的空闲列表为空，而另一个CPU的列表有空闲内存的情况；在这种情况下，一个CPU会“窃取”另一个CPU空闲列表的一部分。窃取可能会引入锁争用，但这种情况不会经常发生，代码会自动调整空闲页的分配以适用各CPU。

在空闲物理页初始化时，因为操作系统一共有四个CPU，将空闲页分为四块挂在对应CPU的空闲链表上。在一个CPU分配物理页时若发现自己的已经分配完毕，则会去其他的CPU窃取，具体实现是获取别的CPU空闲链表的自旋锁，然后从其空闲链表中获得一个物理页挂到自己的链表上。

Buffer cache

如果多个进程密集地使用文件系统，它们可能会争夺 bcache.lock。原实现将buffer cache组织为一个双向环状链表，每次去buffer cache搜寻自己需要的buf时需要加锁，它的优点在于简单并且可以用链表实现最简洁的LRU算法以从最近使用的buf中先搜索，但缺点在于若各cpu都频繁访问buffer cache链表，会出现严重的锁争用。

改善：

对LRU部分，为每个buf增加一个成员timestamp，在获取buf和释放buf时会更新其时间戳为系统时间，也就是定时器中断的tick数。对于锁争用部分，将buffer cache改为哈希表组织，使用13个哈希桶，将buf按照其磁盘块号哈希分配到对应桶中，每个桶一个自旋锁，则减少了锁争用。

在一般情况下，进程若索取一个对应磁盘块号的buf，会先在对应的哈希桶中查找是否存在对应buf缓存，若没有，则先从自己这个桶中找有没有空闲的buf，实际上就是对应引用计数为0的内核没有成员使用的buf，若找到自然最好，若没有则释放自己在这个桶上的锁，再去获取别的哈希桶的锁以需求对应的未使用buf，直到最终找到一个空闲buf用于磁盘读入的位置。

此过程可能会设计桶中buf的迁移，因此你最终会修改buf对应的磁盘块号

在遍历对应哈希桶时，会记录最小的时间戳的空闲buf，以使用最近使用的buf。

难点在于不出现死锁，并合理的计算临界区的范围，是各CPU获取一个buf是原子的，不能出现一个buf被两个cpu都选中的情况。

mmap与munmap

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

可以假设 addr始终为零，这意味着内核应该决定映射文件的虚拟地址。mmap返回该地址，如果失败则返回 0xffffffffffffffff。length是要映射的字节数；它可能与文件的长度不同。prot指示内存是否应映射为可读、可写，以及/或者可执行的；您可以认为 prot是 PROT_READ或 PROT_WRITE或两者兼有。flags要么是 MAP_SHARED（映射内存的修改应写回文件），要么是 MAP_PRIVATE（映射内存的修改不应写回文件）。您不必在 flags中实现任何其他位。fd是要映射的文件的打开文件描述符。可以假定 offset为零（它是要映射的文件的起点）。允许进程映射同一个 MAP_SHARED文件而不共享物理页面。

munmap(addr, length)应删除指定地址范围内的 mmap映射。如果进程修改了内存并将其映射为 MAP_SHARED，则应首先将修改写入文件。

mmap的操作过程中不会写入磁盘文件，进程退出时或munmap时才会写回磁盘

非常简化的来说，匿名文件映射只是文件映射的 MAP_PRIVATE的一种特殊情况，即分配物理内存时只需要分配全为0的物理页而无需读入文件，释放这段虚拟地址时也可以直接释放而不需要写回文件。

实际上内核对其花了大精力处理匿名映射时的fork写时复制，比如已经分配了物理页时和没分配复制页时的情况，linux就采取了匿名vma链表的方式才解决这棘手的问题

xv6实现：

mmap只需要创建对应的内存区域，将传入的参数全部填入内存区域，如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  // 遍历查找未使用的VMA结构体
for(int i = 0; i < NVMA; ++i) {
    if(p->vma[i].used == 0) {
        p->vma[i].used = 1;
        p->vma[i].addr = p->sz;
        p->vma[i].len = length;
        p->vma[i].flags = flags;
        p->vma[i].prot = prot;
        p->vma[i].vfile = vfile;
        p->vma[i].vfd = vfd;
        p->vma[i].offset = offset;

        // 增加文件的引用计数
        filedup(vfile);

        p->sz += length;
        return p->vma[i].addr;
    }

此时就已经拥有了对应VMA信息，但并没有分配页表项，因此首次访问该虚拟地址时会触发page-fault。

1
2
3
4
5
6
7
8
else if(cause == 13 || cause == 15) {
    // 读取产生页面故障的虚拟地址，并判断是否位于有效区间  
    uint64 fault_va = r_stval();
    if(PGROUNDUP(p->trapframe->sp) - 1 < fault_va && fault_va < p->sz) {
      if(mmap_handler(r_stval(), cause) != 0) p->killed = 1;
    } else
      p->killed = 1;
}

在页错误处理程序中，先判断是否在VMA中，如果不在VMA，又或者VMA对应的file结构记录的文件读写权限缺失，比如页错误寄存器反映的为虚拟地址读错误，而你的文件没有此权限，内核都会直接杀死进程。若权限检查没问题，内核会通过file结构内部的inode指针读取文件内容，具体来说是通过页错误时CR2寄存器中存放的页面错误的虚拟地址减去VMA中记录的此VMA的起始地址再加上你传给mmap时的偏移量得到真正的对应文件的偏移量，内核会申请一页物理页，将文件内容读取此物理页中，当然实际上是先读到buffer cache中再复制到对应空闲物理页 **(linux操作系统会直接从file结构中的页缓存指针address_space读取对应文件，因此跟文件操作并无区别，linux会将用户虚拟地址映射到文件页缓存)**。最终内核建议刚刚读入文件实际内容的物理页和进程虚拟地址的页表项映射。整个过程就处理完毕了，在页错误处理程序返回后会将程序计数器设为用户态之前陷入内核的代码地址，相当于再执行一遍。

VMA还可以用于判断页错误对应虚拟地址属于哪一种情况，比如fork导致的只读的写时复制，还是堆顶扩展导致的lazy-allocate，还是mmap的内存映射，即可进行相应的处理。

linux中VMA为 vm_area_struct，CSAPP中中文翻译它为内存区域结构

xv6 的lab要求实际上没有实现真正的共享内存，它们各自都有一个独占的物理页，在自己的物理页进行文件的修改，相当于此时其他进程改文件本进程是不知情的，但是本进程取消映射或退出时会将该物理内存写回文件相当于覆盖了之前所有的文件内容。

现代操作系统linux的实现：

fork复制页表会修改页表项为只读的写时复制，但对应的shared VMA它不会改成只读，而是保留其原本的页表项设置，这样父子进程就能访问相同的物理内存了。但如果fork前mmap的虚拟地址还没有分配物理内存，那么内核应该需要想一种办法比如链表这种数据结构将所有的进程连起来（linux就是这样做的），然后在某个进程页错误分配物理页时，可以修改所有链表上进程的用户页表来映射在同一物理页上。

内核如何感知mmap修改的文件脏页？

我们考虑这样的一个场景，用户通过mmap将文件的内容映射到自己的地址空间，访问文件中某个位置的数据，修改地方的内容。在这个过程中，第一次触发的读操作会引起操作系统的缺页异常，并导致操作系统按需将这个页面的内容读入内存，建立页面的映射，这个看起来还比较直观。但是在写入的时候呢？此时应用程序是通过内存操作的，而这个内存映射已经建立，此时并不会触发操作系统的缺页异常，这个地方真正的做到了让用户感觉到是在访问内存，并且连操作系统也有这个错觉(相当于入戏太深，最后把自己也感动了)，操作系统如果对这个写入没有任何感知的话，操作系统怎么知道这个mmap的文件内容哪里被修改(进而需要写回磁盘)了呢？

MMU单元对于这种情况在页表项中提供了支持。具体来说，当一个页面被写入时，CPU会在这个页面对应的PTE(Page Table Entry)中设置一个dirty标志位来表示对应的页面内容被修改了。

即使如此，操作系统在什么时候来识别这个寄存在PTE中的页面标志位呢？这个我想到两个场景：一个是系统需要内存页面从而尝试将某些页面换出到磁盘的时候，另一个是这个修改内容的落地问题。

1.页面回收时的处理

由于此时的页面dirty标志是放在CPU写入的PTE中，而不是放在内核的页面管理结构(struct page)中，所以通过常规的PageDirty接口并不能判断处这个文件的内容被修改了。在页面回收的时候，如果此处判断有误，那么前面例子中修改的内容将会随着页面的回收而丢失，所以说操作系统肯定会处理这种情况的。

2、进程退出时的处理

进程退出时，清理页表时，内核可以通过vma来刷回脏页，这也没有问题。

内核使用了更为复杂的策略：为了实时感知用户对于页面的写操作，在首次建立页表映射时的时候先屏蔽掉页表项可写属性，从而在写操作的时候触发一次访问异常，进而在访问异常中处理脏页面的写回问题，比如设置其文件页为脏页。

但是接下来的问题是，把页面写回磁盘之后，如果用户再次修改页面内容，此时操作系统将如何感知这个修改呢？

内核线程将页面写回磁盘之后再次把页面写保护开启，从而周而复始

网卡驱动

发送数据的流程：

CPU将IP数据包打包放入内存中，通知DMA Engine进行DMA传输，数据放入FIFO data buffer中。MAC将IP数据包拆分为最小64KB，最大1518KB的数据帧，每一帧包含了目标MAC地址、自己的MAC地址和数据包中的协议类型以及CRC校验码。目标MAC地址通过ARP协议获取。PHY接受MAC传送的数据，将并行数据转化为串行数据后进行编码，在转变为模拟信号将数据进行传输。

Ring结构：

image-20210227125455380

RAM中的tx/rx buffer是一个环形结构，有head和tail2个指针，其中head的位置由网卡控制，在进行发送时，每发送完成一个packet网卡就会自动将head向前移动一个mbuf，而需要将某个packet发送时，软件将tail向前移动一个mbuf；在进行接收时，每接收到一个packet网卡自动将head向前移动一个mbuf，软件读取tail所指向的mbuf，并向前移动。移动到最后一个mbuf后从头开始，形成一个wrap-up的结构。

descriptor结构是在网卡的寄存器中的，用于描述每一个RAM中的mbuf

1
2
3
4
5
6
7
8
9
10
11
12
// [E1000 3.3.3]
//网卡硬件手册提供了其需要的DMA在内存中的描述符结构，内核为其创建这样一个描述符
struct tx_desc
{
  uint64 addr; //指向对应的实际数据包buffer
  uint16 length; //硬件会填充对应buffer的大小
  uint8 cso;
  uint8 cmd;
  uint8 status;
  uint8 css;
  uint16 special;
};

内核调用UDP套接字写时，先根据网络协议栈逐层加上头部，然后会将其发往ring buffer的tail处，若满了则直接丢弃包。

实际上内核是取出对应的寄存器tail位置，再根据tail位置查描述符数组（由硬件填充），若描述符状态位是还未发送完毕则表示tail位置正在发送，ring buffer已经满了。否则查此状态位是已经发送完毕，内核就可以将此旧的buffer销毁，将要发送的新buffer加上去，并将tail位置前移一位并填入对应的网卡寄存器

网卡DMA放到了ring buffer并填写其描述符后（即状态位、数据包、长度等），会触发外部中断，内核会将全部ring buffer的未读数据包对应的buffer都取出来交给网络协议栈，然后为ring buffer重新申请新的buffer放上去，并更新寄存器中的tail位置。

网卡内部也有64KB的FIFO缓冲区，因此它也会批量的DMA到ring buffer中，因此ring buffer head指针前移多少是不确定的，但硬件会保证不会超过tail

在xv6中，网络协议栈实现是极其简单的，它会将整个网络协议栈解析的工作都放在中断处理程序中并没有分为中断上下部分，因此网卡读中断后会对其逐层解包并最终放于 sock结构对应的buf链表中，供应用程序取包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/* file结构中都有一个sock指针 */
struct file {
#ifdef LAB_NET
  enum { FD_NONE, FD_PIPE, FD_INODE, FD_DEVICE, FD_SOCK } type;
#else
  enum { FD_NONE, FD_PIPE, FD_INODE, FD_DEVICE } type;
#endif
  int ref; // reference count
  char readable;
  char writable;
  struct pipe *pipe; // FD_PIPE
  struct inode *ip;  // FD_INODE and FD_DEVICE
#ifdef LAB_NET
  struct sock *sock; // FD_SOCK
#endif
  uint off;          // FD_INODE
  short major;       // FD_DEVICE
};
/* 内核用链表维护着所有的sock结构 */
struct sock {
  struct sock *next; // the next socket in the list
  uint32 raddr;      // the remote IPv4 address
  uint16 lport;      // the local UDP port number
  uint16 rport;      // the remote UDP port number
  struct spinlock lock; // protects the rxq
  struct mbufq rxq;  // a queue of packets waiting to be received
};
/* 每个sock结构都有一个数据包链表，供应用取 */
struct mbufq {
  struct mbuf *head;  // the first element in the queue
  struct mbuf *tail;  // the last element in the queue
};

在xv6中，发送包时若ring buffer已满，网络协议栈会直接丢弃该包（注意xv6只有udp）。在接收包时，若ring buffer满了会直接将包丢弃，不做任何处理。

meltdown攻击

2018年引发操作系统地震的攻击手段，它几乎击碎了人们对操作系统内存隔离性的安全感。

传统的操作系统中，用户无法访问任何的内核虚拟地址，这会触发页错误，比如你读一个虚拟地址的数据，这百分百会触发页错误

image-20220606173758540

在现代操作系统的设计中，比如linux，为了节省系统调用上下文切换的页表切换开销，比如假如你有一套用户页表和一套内核页表，你在陷入内核态时你切换为内核页表，这会造成很大的开销，比如切换页表需要刷新TLB导致接下来的代码明显变慢，xv6操作系统就是这么做的。而现代操作系统为了减少这个开销，会只为进程做一个统一的页表，换句话说，此页表拥有整个操作系统地址空间的映射，包括该进程的用户虚拟地址和陷入内核时的内核虚拟地址。那么当代操作系统是如何防止用户窥探内核数据的呢？就是通过页表项的一个位，PTE_U，此位若没有设置即意味着此代码只能内核访问而用户无法访问，你访问了这个虚拟地址一定会触发页错误。

而meltdown攻击则是基于这样一个环境，用户态拥有完整的页表，只是没有对应的页表项访问位。

meltdown基于两个关键的CPU微架构技术

  • 预测执行
  • 缓存cache

预测执行：比如CPU执行到一个花费很大的指令，比如从内存中读取某个变量，这需要几百个机器周期，实际上CPU会进行预测并执行一条路径，如下，r1寄存器的值从内存取，然后基于r1的值做判断走不同的if else，实际上CPU会直接走一条路径可能提前执行了几百个机器周期，已经执行完了，等到那个判断语句真正的确定了，如果CPU预测对了，那当然CPU提前了运行了几百个周期取得了优异的性能，若错误CPU会回滚

image-20220606193236014

缓存cache：从内存读，若缓存没有，则会放在缓存中

image-20220606193031576

meltdown攻击即是运行一条很长时间的CPU指令，然而这条指令后面跟着一些非法指令，比如从内核虚拟地址中取值，我们知道正常情况下是没有权限无法取值，然而intel CPU会预测执行对内核虚拟地址取值并往后执行，并且这个取值的过程会放在缓存中，meltdown的攻击代码根据它的值最低位是1还是0放置在数组不同的位置中，然后会尝试读这不同的位置，并对其计时，很显然，时间花费少的多的就缓存在CPUcache中了，那么就能判断内核对应地址的位的值是1还是0，换句话说，我们取得了我们无权限的内核虚拟地址的值。

本质上，就是利用了CPU微架构的不完全透明进行的攻击，我们都知道CPU流水线、预测执行、Cache缓存本质上对用户是透明的，甚至对操作系统程序员也是透明的，我们在某种程度上无法感知其存在，但是实际上我们确实有办法感知它而获得信息，比如meltdown攻击利用的缓存的访问速度能让我们获得微架构信息。

因此这次的meltdown攻击当时让整个计算机系统架构蒙上了一层阴影，因为CPU这种透明与不透明之间，以及CPU微架构做的优化是否会成为计算机安全的突破口。比如meltdown攻击就打破了传统页表带来的内存隔离性。

又比如说，像当今的云计算，多人用一台机器，但是本质上还是走一个网卡，我是否可以观测网络流量？又或者是一些同样像缓存一样的延时，来得到对方的数据？比如它的密码。很显然，在meltdown这个攻击出现后，这些都有可能出现。

项目主要内容复盘

1.增加系统调用，实现用户级信号中断Alarm

增加系统调用

risk-v中系统调用函数的实际内容是一段汇编代码，其会将系统调用函数的名字对应查表找到对应的系统调用号放入a7寄存器中，接着执行ecall指令陷入内核，然后执行陷入代码，risk-v中的scause寄存器会存入此次陷入的原因，内核会通过此寄存器的内容得知为系统调用，再根据系统调用号从系统调用函数表中调用对应函数，执行真正的sys_func()。因此增加系统调用，实际上就是 1.增加用户态的系统调用函数的声明 2.给其分配一个系统调用号 3.将真正的内核函数插入系统调用函数表中

用户级信号中断Alarm

没有alarm时运行的大致过程

  1. 进入内核空间，保存用户寄存器到进程陷阱帧
  2. 陷阱处理过程
  3. 恢复用户寄存器，返回用户空间

当添加了alarm后，变成了以下过程

  1. 进入内核空间，保存用户寄存器到进程陷阱帧
  2. 陷阱处理过程
  3. 恢复用户寄存器，返回用户空间，但此时返回的并不是进入陷阱时的程序地址，而是处理函数 handler的地址，而 handler可能会改变用户寄存器

因此设置alarm的系统调用函数，需要传入触发时间，以及用户中断处理函数的入口地址。在进程pcb中增加相应的变量存储对应的传入参数。当每次定时器中断时，会根据是否设置了此触发函数，来走不同的逻辑。若设置了用户级时间中断，并且以及达到了时间，则将当前的陷阱帧再保存一份，因此进程pcb中需要两个陷阱帧，一个用于常规的用户陷入内核的寄存器保存，一个用于再一次保存用户寄存器防止执行用户时间中断处理函数时错乱。再一次保存寄存器后，将返回地址修改为之前传入的入口函数地址，那么此时内核定时器中断返回时会直接将用户设置的函数装入pc程序计数器中，然后执行用户的函数。在用户处理函数执行完后会调用sigreturn信号返回系统调用，再在内核中将原先保存的用户寄存器重新装入，然后重新返回用户空间，一切如初。

2.增加进程内核页表，允许内核直接解引用用户指针

Xv6有一个单独的用于在内核中执行程序时的内核页表。内核页表直接映射（恒等映射）到物理地址，也就是说内核虚拟地址 x映射到物理地址仍然是 x。Xv6还为每个进程的用户地址空间提供了一个单独的页表，只包含该进程用户内存的映射，从虚拟地址0开始。因为内核页表不包含这些映射，所以用户地址在内核中无效。因此，当内核需要使用在系统调用中传递的用户指针（例如，传递给 write()的缓冲区指针）时，内核必须首先将指针转换为物理地址。目标是允许内核直接解引用用户指针。

注意此时pcb中还是有两个页表，只不过进程的内核页表包括了用户的虚拟地址空间

难点：

  1. 创建进程时需要创建两个页表，维护进程页表时，如用户申请堆空间时不仅需要将映射插入用户页表也需插入内核页表。删除进程时需要清理两个页表，内核栈空间，不能重复清理物理内存等等（繁琐和易错）。
  2. 用户的虚拟地址范围不与内核用于自身指令和数据的虚拟地址范围重叠。因为重叠的话一个虚拟地址会映射到不同的物理地址，因此必须严格的规划用户虚拟地址空间和内核地址空间，在xv6中和linux一样，将内核部分置于高地址初，而用户空间置于从0开始的低地址处，严格保证分开，从而使进程在内核上下文运行时可以只使用一个页表。
  3. 页表项的访问位在不同的页表中不同。在维护页表时，用户态的页表项对应的访问位是PTE_U，即用户态时能访问此地址空间，而在内核页表中需要擦除此访问位。

3.实现用户堆内存的惰性分配，实现Copy-on-Write的fork系统调用

实现用户堆内存的惰性分配

此时调用sbrk系统调用上移堆指针扩充堆内存时，我的代码实际上不会分配实际的物理内存，而是简单移动堆顶地址值，作为一个记号表示分配了内存。因此此函数的内核实现相当简单，复杂的是页面错误时的处理。

如果此时出现了页错误，xv6从寄存器中读取为何错误的原因以及从另一个寄存器中读取错误的地址，就像X64的CR2寄存器一样存放了发生了页面错误的地址，接着内核会根据地址是否在堆空间正确的位置中，决定是当场分配一个物理页给进程还是直接因为访问了错误的地址直接杀死进程。若是之前惰性分配的内存，则分配一个物理页，重新建立内存映射即维护页表，然后将内核陷入返回的pc值设置为之前陷入时执行的指令(实际上源码啥也没干，系统调用会设置为下一条代码，这个本身就不需要进行额外操作)，如此便会返回后再执行一次对应代码，此时因为已经建立了页表，一切顺利。

那么到释放内存时，没有分配实际物理内存的虚拟地址对应的物理页面就不需要收回了，因为没有建立实际映射。

以上只是处理了用户态时的页面错误，若用户是执行了系统调用而传入了没有分配物理页面的地址，那么在内核态中执行系统调用前需要检查参数地址是否满足要求，若满足要求且没分配物理页面，则当场分配物理页面后再执行系统调用。

实现Copy-on-Write的fork系统调用

页表项是存在保留位的，因此我选用了一个保留位来表示此页表项对应的物理页表是否为fork导致的写时复制。

首先在执行fork时，若没有COW，fork的代码会复制父进程的全部资源，包括页表以及虚拟地址空间对应的物理内存。但显然很多时候fork后会执行exec函数导致白白复制了那么久。因此在fork时我不会复制实际虚拟地址空间对应的物理内存，而是公用一份，但是我将两者，即父进程和子进程对应的页表的页表项全部设置为只读即不可写，然后设置fork标志位即可用的保留位表示这是fork的页面。

再者引入了内存页的引用计数，为每一个可分配的物理页设置了一个内核全局变量数组-引用计数，表示有几个进程正在使用，这样可以在一个进程释放内存时通过引用计数得知是否需要真正释放内存，因此判断写一个fork的页面时用于判断自己是否已经是最后一个唯一在使用该物理页面的进程了，如果是，那么我便无需在复制一份，直接清楚它页表项的只读位即可。

从头理一下执行流程，若一个进程fork后，那么所有的页表项会设置只读标志位和fork标志位，若此时想修改对应物理内存的值，会触发页面错误，我在页面错误处理代码中会检测是否设置了fork标志位并检查对应的引用计数，若引用计数大于1则复制一份给自己独自占有使用，重新设置页表映射，若引用计数为1说明已经是独占了，则只需要清理只读标志位即可。

4.实现简易的协程，实现函数栈帧回溯打印功能

最简单的一部分

函数栈帧回溯： risk-v的fp寄存器存放了函数栈基地址，栈基地址处的值又存放了上一个函数的栈基地址，因此就能遍历函数了。

至于协程，lab实际上给了绝大多数代码了，只需要部分汇编的上下文切换即可。还不如云风的coroutine。

5.优化内核内部的锁争用，各CPU可独自分配空闲物理页，重新设计磁盘buffer cache数据结构

各CPU可独自分配空闲物理页

操作系统初始化时不再将所有空闲物理页挂在一个链表上，而是每个CPU一个链表，优先在自己的CPU上取，若没有，再去窃取其他CPU的物理页，用完后放在自己的物理页上。

每个CPU根据寄存器可得知自己是几号CPU从而可以区别自己的链表。

重新设计磁盘buffer cache数据结构

原来：

原来的buffer cache是单个双向链表，每个buffer修改其引用计数、对应的磁盘块号、是否已经使用等等通过一个大锁保护，因此锁争用较高，但是可以很方便的实现lru算法。

现在：

定义一个素数个数哈希桶，每个buf通过自己对应的磁盘块号来哈希处理得到自己在哪个桶内，每个桶一个锁，初始化时都挂在0号桶上。为了能同样实现lru，在buf结构中增加时间戳结构，记录每次使用的时间戳。在读某个磁盘块时，若在对应的哈希桶中没有找到缓存的buf，便取当前桶中最小时间戳表示最近最久未使用的buf，若当前桶中的buf都已经使用了，就遍历其他的桶，即窃取buf，这是可能导致锁争用的地方。

没有优化前，测试代码取buf会自旋上万次，修改后自旋不到百次。

6.扩展文件系统，实现大文件与符号链接文件

大文件

原先文件系统inode存放文件的为 12个直接块和一个一级间接块，我修改成了11个直接块和1个一级1个二级。

因此修改了从文件对应偏移量寻磁盘块的逻辑，以及在删除文件时逐层释放文件的逻辑。

符号链接

增加符号链接这种文件类型，增加创建符号链接的系统调用，其实现就是创建一个文件（即分配一个inode节点）和一个直接磁盘块，在其中写入符号链接文件的文件名即文件路径。修改open系统调用，增加打开符号链接文件的分支，即打开符号链接的文件会打开其中实际存放的文件名的文件。为了不发生符号链接的循环引用，规定递归深度大小，超过后直接open返回-1.

7. 实现简易版内存文件映射mmap与munmap，增加内存区域结构VMA。

参考上面的 mmap与mummap

8.为E1000网卡增加xv6设备驱动程序。

参考上面的 网卡驱动