MIT6.S081

这篇blog是博主学习MIT6.S081操作系统课程的学习理解，博主的项目地址在:https://github.com/shenmuxin/risc_mini_os_kernel

xv6是如何实现强隔离的？

RISC-V有三种CPU可以执行指令的模式：机器模式(Machine Mode)、用户模式(User Mode)和管理模式(Supervisor Mode)。在机器模式下执行的指令具有完全特权；CPU在机器模式下启动。机器模式主要用于配置计算机。Xv6在机器模式下执行很少的几行代码，然后更改为管理模式。

一般来说user mode就是我们的用户模式，简称为U mode，而Supervisor mode就是我们所说的内核模式，简称为S mode。

操作系统必须满足三个要求：多路复用、隔离和交互。

为了实现强隔离，最好禁止应用程序直接访问敏感的硬件资源，而是将资源抽象为服务。

xv6如何实现系统调用的?

一个进程可以通过执行RISC-V的汇编指令ecall指令进行系统调用，该指令提升硬件特权级别，并将程序计数器（PC）更改为内核定义的入口点，入口点的代码切换到内核栈，执行实现系统调用的内核指令，当系统调用完成时，内核切换回用户栈，并通过调用sret/ret指令返回用户空间，该指令降低了硬件特权级别，并在系统调用指令刚结束时恢复执行用户指令。

在用户态会有一个用户态系统调用函数，通常是这么命名的systrace，xv6中有一个系统调用入口函数usys.pl，通过这个入口函数可以通过用户调用的系统调用名称来找到系统调用号SYS_trace，并且将系统调用号保存在寄存器a7中，a0-a6保存的是系统调用的参数，然后触发ecall汇编指令进入内核态（这里输属于陷入部分，ecall可以通过预先设置好的陷阱函数usertrap()，在进入内核态之后会触发trampoline.S，trampoline.S中有uservec函数来保存寄存器状态和userret函数来恢复寄存器状态，usertrap通过检查寄存器scause来判断是否是一次系统调用）然后在syscall.c:164使用函数指针进行执行内核态的系统调用sys_trace，在处理完系统调用后将结果保存在a0寄存器中，然后通过汇编指令ret（通过预先设置的usertrapret()函数）进行返回，跳到sepc寄存所指向的下一条指令。

xv6为什么需要分页机制（虚拟内存）？

分页机制（虚拟内存）可以实现

进程隔离，每个进程都有自己的从0地址开始的虚拟地址空间，这样进程就无法访问其他进程的内存区域，虚拟地址可以将内核空间与用户空间进行隔离。

按需分配，提升内存利用率，通过分页机制，和缺页故障，可以实现按需分配内存，避免了一次性分配大量的连续物理内存，提高了内存利用率。

简化内存管理，分页将内存管理单元固定为页的大小4KB，避免了内存碎片化的问题。

交换和页面置换，虚拟内存使得操作系统可以将不活动的内存也置换到硬盘上，从而在物理内存不足的时候为程序提供足够的空间。

xv6是如何实现分页机制的？

xv6原来是一级页表，将其提升为了三级页表，

xv6的一级页表采用低39位进行寻址，高27位是页表项索引，低12是页内偏移，所以决定了一个页的大小就为2^12 byte = 4KB，假如采用一级页表，在一级页表的情况下，最多寻址2^27 * 4KB = 512GB个页表，所以这样能寻址的最大物理内存大小是512GB，但是这样一次性得将这个巨大的页表加载到内存中，这是一种极大的负担。

xv6采用三级页表的结构，页表的起始地址从寄存器satp获得，高27分为L2，L1，L0，三级页表每级页表只占2^9 = 512个页表项，这样最大能寻址的物理内存大小也是512^3 * 4KB = 512GB，sfence.vma 刷新 TLB，确保页表立刻生效

walk() 函数通过递归查找或创建页表条目，实现从虚拟地址到物理地址的转换。
mappages() 则负责将虚拟地址映射到实际的物理内存页，并更新页表条目。
kalloc()该函数会从内存管理模块中分配一个空闲物理页。
kfree() 函数用于释放不再使用的物理页。

使用三级页表可以按需将页表项加载到内存中，再通过懒分配（copy-on-wirte），就是极大减少页表的占用开销。

xv6原本的设计是所有的用户进程共享一个内核页表，用户进程在用户态使用各自的用户页表，但是一旦进入内核态（例如使用了系统调用），则切换到内核页表（通过satp寄存器，trampoline.S），然而这个内核页表是全局共享的，也就是说全部进程进入内核态都共用一个内核页表。

现在需要单独为每个用户进程都分配自己的内核页表，具体的实现思路是：首先需要修改每个进程结构体所维护的数据结构struct proc，新增内核页表，并且添加内核页表的初始化逻辑等，然后在scheduler()进程调度模块中增加切换进程时切换内核页表的逻辑，并且使用sfence.vam立刻刷新TLB快表，然后在为每个内核页表都需要添加自己的内核栈（在原本的设计中，xv6 在启动过程中，会在 procinit() 中为所有可能的 64 个进程位都预分配好内核栈 kstack，具体为在高地址空间里，每个进程使用一个页作为 kstack，并且两个不同 kstack 中间隔着一个无映射的 guard page 用于检测栈溢出错误。），由于内核页表不用共享，所以我们只需要在每个内核页表的固定位置设置我们的内核栈就可以了。最后需要做的事情就是在进程结束后，释放进程独享的页表以及内核栈即可，回收资源，防止内存泄漏。

还需要完成的工作是，在进程内核态页表中维护一个用户态页表映射的副本，这样可以使得对用户态传入的指针进行解引用。

xv6是如何实现陷入机制的？

xv6中的陷入机制用于处理从用户态切换到内核态，以响应中断、异常（例如缺页异常）、或者系统调用。xv6使用RISC-V处理器的硬件来实现这一特性。陷入机制通常由以下三种事件之一触发：

中断（Interrupt）：来自外部设备（如时钟中断）的信号。
异常（Exception）：处理器在执行指令时遇到的异常情况，如除零错误、缺页异常等。
系统调用（System Call）：用户程序通过ecall指令请求内核服务。

当处理器遇到中断、异常或执行ecall指令时，会自动执行以下步骤：

保存程序计数器PC到sepc，
保存陷入的原因到scause
保存异常的虚拟地址到stval
切换到内核模式S mode
跳转到陷入处理程序，通过scause来进行不同的处理。
1. 如果是系统调用，usertrap()会调用syscall()来处理相应的系统调用。
2. 如果是异常，如缺页异常，会调用相应的异常处理程序，如uvmalloc()等。
3. 对于硬件中断，会调用设备的中断处理程序。
处理完后，通过userret()来恢复上下文进行内核态的返回。

xv6是如何实现懒分配的？

xv6中的虚拟内存是以多级页表的方式进行保存（页表是一种树状结构），空闲内存页以链表的形式进行保存。

当一个进程被创建或执行时（例如通过 exec 系统调用），操作系统会调用sbrk()立刻为该进程分配虚拟内存空间，但不分配物理内存空间。此时，这些虚拟内存页并未被映射到物理内存，即它们的页表项尚未指向任何物理页。当进程尝试访问某个尚未分配物理内存的虚拟地址时，CPU 会产生一个缺页异常（page fault）（缺页异常通过硬件捕获，并且写入scause寄存器，我们读取scause寄存器就可以知道当前是中断、缺页异常还是系统调用）。在 usertrap 函数中，xv6 捕获这个页错误并检查其原因。如果页错误是由于访问了一个合法但尚未分配物理内存的虚拟页，那么usertrap()将会进一步读取stval寄存器（其中保存了产业页面错误的虚拟地址），然后调用allocuvm()为该虚拟页分配一个新的物理页（具体的操作是kalloc()函数会从kmem.freelist中进行查找，然后使用memset将链表所指向的下一个页表地址填充满junk number，然后返回物理页表号physical address）。这一分配过程包括：

分配一个空的物理页，并将其清零。
更新页表，将这个虚拟页映射到新分配的物理页。
重新执行导致页错误的指令。

处理完页错误后，进程将继续执行，从而实现了懒分配。

还需要实现copyin()和copyout()：内核/用户态之间内容的相互拷贝

xv6是如何实现写时分配（懒fork）的？

copy on write fork旨在通过延迟实际内存复制直到真正需要时再进行，从而节省内存和提高性能。实现 fork 懒复制机制，在进程 fork 后，不立刻复制内存页，而是将虚拟地址指向与父进程相同的物理地址。在父子任意一方尝试对内存页进行修改时，才对需要修改的内存页进行复制。物理内存页必须保证在所有引用都消失后才能被释放，这里需要有引用计数机制（类似于软连接）。

首先需要修改原本的fork，实现从父进程到自进程时不立刻进行内存的复制，而是建立指向原物理页的映射，并将父子两端的页表项都设置为不可写。（当父进程或者子进程试图进入一个不可以写的内存页时就会触发一个页面异常）
然后再在usertrap()中添加对该页面异常的检测，如果检测到是由于写时分配而导致的，那么就在当前访问的地址符合写时分配条件时，对写时分配页进行复制操作。

还需要添加标志位用于判断是否是cow页

1	#define PTE_COW (1L << 8) // 是否为懒复制页，使用页表项 flags 中保留的第 8 位表示

然后我们还需要修改kalloc.c中的kalloc()和kfree()，检测内存页的引用计数，当引用计数为0时才进行释放（kfree()将当前pa所指向的物理页memset为Junk number，然后将其添加到kmem.freelist中）

xv6是如何实现线程上下文切换的？

在xv6中每个CPU core都可以执行一个进程process，每个process包含一个用户线程user thread和一个内核线程kernel thread，在原本的设计中xv6进行线程上下文切换需要先通过usertrap()陷入内核，然后使用swtch()进行内存线程的复制，再通过userret()进行返回完成线程的切换。

xv6 中的 swtch 函数用于执行上下文切换。它通过汇编代码实现了当前线程的寄存器状态保存到 struct context，并从另一个 struct context 中恢复寄存器状态。
为什么需要保护callee-saved寄存器？在 swtch 中，保存和恢复的是 callee-saved 寄存器（如 s0-s11），这些寄存器在函数调用约定中是由被调用方（callee）负责保存的。线程切换时，可能会从一个函数切换到另一个完全不同的函数，这些寄存器需要保持一致，避免因为线程切换而导致函数内部状态被破坏。
然后每个CPU core上都运行着一个scheduler()，可以从当前所允许的最大64个进程中选择一个进行运行。

引申：内核调度器无论是通过时钟中断进入（usertrap），还是线程自己主动放弃 CPU（sleep、exit），最终都会调用到 yield 进一步调用 swtch。由于上下文切换永远都发生在函数调用的边界（swtch 调用的边界），恢复执行相当于是 swtch 的返回过程，会从堆栈中恢复 caller-saved 的寄存器，所以用于保存上下文的 context 结构体只需保存 callee-saved 寄存器，以及返回地址 ra、栈指针 sp 即可。恢复后执行到哪里是通过 ra 寄存器来决定的（swtch 末尾的 ret 转跳到 ra）

而 trapframe 则不同，一个中断可能在任何地方发生，不仅仅是函数调用边界，也有可能在函数执行中途，所以恢复的时候需要靠 pc 寄存器来定位。并且由于切换位置不一定是函数调用边界，所以几乎所有的寄存器都要保存（无论 caller-saved 还是 callee-saved），才能保证正确的恢复执行。这也是内核代码中 struct trapframe 中保存的寄存器比 struct context 多得多的原因。

xv6中有什么锁、分别是如何实现的？

锁是用来管理对共享资源的并发访问，确保系统的正确性和稳定性，xv6中实现了两种类型的锁，spinlock（自旋锁）和睡眠锁（sleeplock），自旋锁是最简单的一种锁。它适用于保护短时间内的临界区资源，因为线程在等待锁时不会睡眠，而是不断地检查锁的状态。睡眠锁用于长时间的资源保护。如果持有锁的线程需要等待，睡眠锁会使线程进入睡眠状态，而不是一直占用 CPU 资源。睡眠锁通常用于涉及磁盘 I/O 或长时间操作的场景。

struct spinlock {
  uint locked;       // Is the lock held?
  char *name;        // Name of lock (for debugging).
  struct cpu *cpu;   // The CPU holding the lock.
};

struct sleeplock {
  uint locked;       // Is the lock held?
  struct spinlock lk; // Spinlock protecting this sleep lock.
  int pid;           // Process holding the lock.
};

xv6是如何减少锁争用的？

我通过优化降低了锁争用，提高了多核CPU的并行性。思路有:

使用无锁数据结构，这要求使用原子操作（要求较高）
减少锁的持有时间
必须共享时，尽量减少在关键区中停留的时间（对应“大锁化小锁”，降低锁的粒度）
只在必须共享的时候共享（对应为将资源从 CPU 共享拆分为每个 CPU 独立）

kalloc 原本的实现中，使用 freelist 链表，将空闲物理页本身直接用作链表项（这样可以不使用额外空间）连接成一个链表，在分配的时候，将物理页从链表中移除，回收时将物理页放回链表中。

在这里无论是分配物理页或释放物理页，都需要修改 freelist 链表。由于修改是多步操作，为了保持多线程一致性，必须加锁。但这样的设计也使得多线程无法并发申请内存，限制了并发效率。

具体的优化：

减少不同CPU core进程分配物理内存时的锁争用（将共享改为独立）

优化前的freelist是共享的，现在即是为每个 CPU core 分配独立的freelist，这样多个 CPU core并发分配物理页就不再会互相排斥了，提高了并行性。但由于在一个 CPU core freelist 中空闲页不足的情况下，仍需要从其他 CPU 的 freelist 中“偷”内存页，所以一个 CPU 的 freelist 并不是只会被其对应 CPU 访问，还可能在“偷”内存页的时候被其他 CPU 访问，故仍然需要使用单独的锁来保护每个 CPU 的 freelist。这里选择在内存页不足的时候，从其他的 CPU “偷” 64 个页，这里的数值是随意取的，在现实场景中，最好进行测量后选取合适的数值，尽量使得“偷”页频率低。

减少不同CPU core进行读写buffer cache时的锁争用（减小锁的粒度）

因为不像 kalloc 中一个物理页分配后就只归单个进程所管，bcache 中的区块缓存是会被多个进程（进一步地，被多个 CPU）共享的（由于多个进程可以同时访问同一个区块）。所以 kmem 中为每个 CPU 预先分割一部分专属的页的方法在这里是行不通的。在这里， bcache 属于“必须共享”的情况，所以需要用到第二个思路，降低锁的粒度，用更精细的锁 scheme 来降低出现竞争的概率。

原版 xv6 的设计中，使用双向链表存储所有的区块缓存，每次尝试获取一个区块 blockno 的时候，会遍历链表，如果目标区块已经存在缓存中则直接返回，如果不存在则选取一个最近最久未使用的，且引用计数为 0 的 buf 块作为其区块缓存，并返回

// kernel/bio.c  xv6原本的设计
struct {
  struct spinlock lock;
  struct buf buf[NBUF];

  // Linked list of all buffers, through prev/next.
  // Sorted by how recently the buffer was used.
  // head.next is most recent, head.prev is least.
  struct buf head;
} bcache;

新的改进方案，可以建立一个从 blockno 到 buf 的哈希表，并为每个桶单独加锁。这样，仅有在两个进程同时访问的区块同时哈希到同一个桶的时候，才会发生锁竞争。当桶中的空闲 buf 不足的时候，从其他的桶中获取 buf。

// bucket number for bufmap
#define NBUFMAP_BUCKET 13
// hash function for bufmap
#define BUFMAP_HASH(dev, blockno) ((((dev)<<27)|(blockno))%NBUFMAP_BUCKET)
struct {
  struct buf buf[NBUF];
  struct spinlock eviction_lock;

  // Hash map: dev and blockno to buf
  struct buf bufmap[NBUFMAP_BUCKET];
  struct spinlock bufmap_locks[NBUFMAP_BUCKET];
} bcache;

xv6的文件系统?

文件系统不使用块0（它保存引导扇区）。块1称为超级块：它包含有关文件系统的元数据（文件系统大小（以块为单位）、数据块数、索引节点数和日志中的块数）。从2开始的块保存日志。日志之后是索引节点，每个块有多个索引节点。然后是位图块，跟踪正在使用的数据块。其余的块是数据块：每个都要么在位图块中标记为空闲，要么保存文件或目录的内容。超级块由一个名为mkfs的单独的程序填充，该程序构建初始文件系统。

xv6中的buffer cache是一个用于管理磁盘块的内存的缓存系统，是磁盘内容的复制，通过缓存磁盘数据块，可以减少直接访问磁盘的次数，从而提高文件的性能。

缓存磁盘块：当需要读写磁盘上的数据块时，xv6首先会检查这个数据块是否已经在缓存中。如果是，操作就可以直接在内存中完成，而不需要访问磁盘。
减少磁盘I/O：因为访问磁盘的速度远远慢于访问内存，通过缓存，可以减少磁盘I/O操作的次数，从而提高系统的整体性能。
统一的接口：buffer cache提供了统一的接口来处理磁盘块的读取和写入操作，使得文件系统的实现更加简洁。

xv6提供两个磁盘分配器mkfs，其中的balloc()可以分配一个新的磁盘块，bfree()可以释放一个磁盘块。文件系统的元数据（meta data）都存放于索引节点inode中：

文件元数据的存储： inode 记录了文件的类型、大小、设备号、硬链接数量等元数据。文件系统中的每个文件或目录都与一个 inode 关联，inode 是文件元数据的存储中心。
文件数据的定位： inode 中的 addrs 数组存储了文件数据块的磁盘地址。通过 inode，操作系统可以知道如何在磁盘上找到并读取文件的数据。
文件系统的抽象： inode 将文件的元数据与文件数据分离，并且不同于目录项，它不包含文件名。目录项实际上是文件名到 inode 号码的映射，而 inode 则真正代表文件，负责管理与文件相关的所有信息。

扩充单个文件大小：

v6 文件系统中的每一个 inode 结构体中，采用了混合索引的方式记录数据的所在具体盘块号。每个文件所占用的前 12 个盘块的盘块号是直接记录在 inode 中的（每个盘块 1024 字节），所以对于任何文件的前 12 KB 数据，都可以通过访问 inode 直接得到盘块号。这一部分称为直接记录盘块。

对于大于 12 个盘块的文件，大于 12 个盘块的部分，会分配一个额外的一级索引表（一盘块大小，1024Byte），用于存储这部分数据的所在盘块号。

由于一级索引表可以包含 BSIZE(1024) / 4 = 256 个盘块号（每个盘块号占4B大小），加上 inode 中的 12 个盘块号，一个文件最多可以使用 12+256 = 268 个盘块，也就是 268KB。我们扩充之后是11个direct inode加上一个indirect inode（是二级inode，所以是256x256 + 11 + 256 = 65803KB）