在百度做了两年异构硬件之后，感觉自己对计算机体系结构的理解深度有了很大程度的提升。趁着这段空闲，打算利用MIT经典的操作系统lab来为自己的知识体系做个查漏补缺，这里记录一下各个lab中的问题以及个人理解。
关于实验环境配置，macOS可以直接使用这个repo，其中包含已经patch好的gcc以及bintuils等工具链。比起《30天自制操作系统》中各种魔改的exe，MIT的这套lab采用完全开源的GNU工具链，更加有利于将相应知识技巧迁移到实际应用当中。
2023 update：MIT的这个课程在2018年之后进行了较大改动，其中包括切换到RISCV架构，因此工具链也相应有所变化。考虑到我们日常工作主要还是在x86平台搬砖，对诸如虚拟内存管理之类机制的深度理解还是很有帮助的，因此没有必要用RISCV版本。在最新的macOS上，需要使用较低版本的QEMU模拟器才能够正确模拟多核CPU，推荐自行编译官方的patch版本，会带有额外的调试支持。此外，gdb工具链也需要手动进行一些修改才能编译通过。
Lab 1
- Q：At what point does the processor start executing 32-bit code? What exactly causes the switch from 16- to 32-bit mode?
- A：
orl $CR0_PE_ON, %eax; movl %eax, %cr0设置cr0寄存器之后，使得CPU切换到32bit保护模式。 - Q：What is the last instruction of the boot loader executed, and what is the first instruction of the kernel it just loaded? Where is the first instruction of the kernel?
- A：boot loader通过
((void (*)(void)) (ELFHDR->e_entry))();这句话跳转到kernel的代码起始位置，这条语句对应的jmp是boot loader执行的最后一条指令。kernel自身的第一条指令是movw $0x1234,0x472，此时已经跳转到了kernel代码段所装载到的高位地址0xf0100000。 - Q：How does the boot loader decide how many sectors it must read in order to fetch the entire kernel from disk? Where does it find this information?
- A：这些信息都会被编码到ELF文件的相应字段中，具体来说，是
Proghdr结构体的p_filesz/p_memsz字段。 - Q：Explain the interface between printf.c and console.c. Specifically, what function does console.c export? How is this function used by printf.c?
- A：
console.c提供用于将单个字符输出到终端的方法，而printf.c则提供了格式化字符串的逻辑。 - Q：Explain the following from console.c:
1 if (crt_pos >= CRT_SIZE) {
2 int i;
3 memmove(crt_buf, crt_buf + CRT_COLS, (CRT_SIZE - CRT_COLS) * sizeof(uint16_t));
4 for (i = CRT_SIZE - CRT_COLS; i < CRT_SIZE; i++)
5 crt_buf[i] = 0x0700 | ' ';
6 crt_pos -= CRT_COLS;
7 }
A：看起来这段代码主要是用于处理换行刷新逻辑：当光标位置超出一行长度之后，就将先前所有行往上移动，然后将下一行清空并写入新的字符。对屏幕显示的控制，是通过写VGA映射内存来实现的。
Lab 2
- Q：We have placed the kernel and user environment in the same address space. Why will user programs not be able to read or write the kernel's memory? What specific mechanisms protect the kernel memory?
- A：页目录和页表项的权限位
PTE_W可以控制运行在不同级别（Ring0/3）的程序对内存的访问权限，处于用户态的程序尽管对内核代码/数据相关的页表项具有PTE_W，但缺少PTE_U依然不能修改其内容。因此，在创建新的struct Env的时候，我们可以放心地直接将位于UTOP以上的页目录直接memcpy过来。事实上，如果检查UTOP以上页目录里页表项的权限位，会发现他们不会同时设置PTE_W | PTE_U；但是对于页目录项的权限是可以放宽的，因为两者会一同被检查。
后面我们会注意到，在多进程环境下，中断陷入内核态时处理函数并不需要将页目录换成内核自己的，而是继续“借用”进程原本的即可，这就是因为用户程序的页目录在UTOP以上是原样复制了内核的页目录，本质上是一种实现上的简化——只要我们约定好内核数据代码被加载到什么地址区域，然后让用户态对其只读即可。但是，在进程切换时就需要换到目标进程的页目录，因为在UTOP之下的内存映射在进程之间是彼此隔离的，这也是操作系统为进程所创建的基本抽象。 - Q：What is the maximum amount of physical memory that this operating system can support? Why?
- Q：How much space overhead is there for managing memory, if we actually had the maximum amount of physical memory? How is this overhead broken down?
- Q：Revisit the page table setup in kern/entry.S and kern/entrypgdir.c. Immediately after we turn on paging, EIP is still a low number (a little over 1MB). At what point do we transition to running at an EIP above KERNBASE? What makes it possible for us to continue executing at a low EIP between when we enable paging and when we begin running at an EIP above KERNBASE? Why is this transition necessary?
- A：在装入页表之后，以
0xf0000000（KERNBASE）为基地址的kernel地址空间已经能够被直接访问，此时就可以让%eip直接跳转到高位的kernel地址空间，这是通过mov $relocated, %eax; jmp *%eax来完成的，其中$relocated会被链接到$0xf010002f处。在编写这样的代码时，由于初期kernel时运行在低地址空间而不是链接器的目标地址空间，因此在完成地址空间切换之前，必须保证所有代码都是地址无关的。如果不满足，就要进行地址修正。
Lab 3
Q1
What is the purpose of having an individual handler function for each exception/interrupt? (i.e., if all exceptions/interrupts were delivered to the same handler, what feature that exists in the current implementation could not be provided?)
从代码实现上面来看，其实大多数handler都复用了相同的逻辑，唯一的区别在区分处理中断是否带有error code。所以如果只能设置一个handler，那么所有中断默认就都需要压入error code。不过话又说回来，个人理解这似乎是一个兼容性方面的历史遗留问题。
2023 update: CPU在收到中断时，只会自动去IDT查表找到handler，但并不知道具体是哪个中断被触发了，因此如果所有中断都是用一个handler来处理，那么就会导致软件无法区分中断号。
Q2
Did you have to do anything to make the user/softint program behave correctly? The grade script expects it to produce a general protection fault (trap 13), but softint's code says int 14. Why should this produce interrupt vector 13? What happens if the kernel actually allows softint's int 14 instruction to invoke the kernel's page fault handler (which is interrupt vector 14)?
PAGEFAULT中断的DPL应该设置为不允许用户访问，因为缺页异常应该是访问到未映射的内存区域时才能够触发的。如果允许用户直接触发该中断，那么此时CR2寄存器并没有被正确设置，因而可能对页表产生错误的操作。
Q3
The break point test case will either generate a break point exception or a general protection fault depending on how you initialized the break point entry in the IDT (i.e., your call to SETGATE from trap_init). Why? How do you need to set it up in order to get the breakpoint exception to work as specified above and what incorrect setup would cause it to trigger a general protection fault?
取决于初始化时设置的DPL（Descriptor Privilege Level）——如果是3，则允许用户态直接以int3自陷；否则的话，触发的是保护异常。
Q4
What do you think is the point of these mechanisms, particularly in light of what the user/softint test program does?
中断服务程序是不能任意被用户程序调用的，否则会引起内核安全隐患，必须严格限制其权限。这里涉及到一个问题，就是哪些中断是允许被用户调用的，对此Intel手册有如下的规定：
The INTO, INT 3, and BOUND instructions permit exceptions to be generated in software. These instructions allow checks for exception conditions to be performed at points in the instruction stream. For example, INT 3 causes a breakpoint exception to be generated.
关于中断屏蔽位
这里一个比较难以区分的概念是设置中断向量时istrap设置成什么。爆栈上面对两者有如下的精辟总结：
A trap is an exception in a user process. It's caused by division by zero or invalid memory access. It's also the usual way to invoke a kernel routine (a system call) because those run with a higher priority than user code. Handling is synchronous (so the user code is suspended and continues afterwards). In a sense they are "active" - most of the time, the code expects the trap to happen and relies on this fact.
An interrupt is something generated by the hardware (devices like the hard disk, graphics card, I/O ports, etc). These are asynchronous (i.e. they don't happen at predictable places in the user code) or "passive" since the interrupt handler has to wait for them to happen eventually.
但事实上在xv6的代码中，可以看到除了SYSCALL之外，其他所有的中断向量都被设置成了istrap=false，也就是执行期间屏蔽中断。这是因为JOS相对于xv6做了很重要的简化——外部中断不可重入，这样我们只需要在进入和离开内核态的时候才需要关心保存和恢复EFLAGS的问题。
进一步展开话题，如果我们持续不响应任何外部硬件中断，会发生什么事情？对于时钟硬件，中断发不出去就算了，下次再尝试即可，其内部并不会为此维护什么状态。如果是复杂一些的外设比如PCIE上面的硬件加速卡，里面会有FIFO用来存储已完成任务的中断信息，那么当这个FIFO被打满之后，就会反压所有硬件单元，从而阻塞住更多任务的执行。
Exercise 9
If you now run user/breakpoint, you should be able to run backtrace from the kernel monitor and see the backtrace traverse into lib/libmain.c before the kernel panics with a page fault. What causes this page fault? You don't need to fix it, but you should understand why it happens.
因为在回溯%ebp的时候访问到了在内核态中未被映射的页——即user stack所使用的那个页。
Lab 4
Q1
Compare kern/mpentry.S side by side with boot/boot.S. Bearing in mind that kern/mpentry.S is compiled and linked to run above KERNBASE just like everything else in the kernel, what is the purpose of macro MPBOOTPHYS? Why is it necessary in kern/mpentry.S but not in boot/boot.S? In other words, what could go wrong if it were omitted in kern/mpentry.S?
Hint: recall the differences between the link address and the load address that we have discussed in Lab 1.
由于mpentry.S这段汇编代码被链接到了KERNBASE高位内核地址，但实际执行的时候是被装载到低位的物理地址，因此其中所有涉及到地址符号的指令都需要经过重新计算，也就是将其重定位到以MPENTRY_PADDR作为基地址。对于boot.S不需要，是因为它在编译脚本中本来就被装载到0x7C00。
Q2
It seems that using the big kernel lock guarantees that only one CPU can run the kernel code at a time. Why do we still need separate kernel stacks for each CPU? Describe a scenario in which using a shared kernel stack will go wrong, even with the protection of the big kernel lock.
每个core使用自己的栈的主要原因是处理中断的安全性，当多个核心上同时产生中断时，如果使用共享栈空间，会在压入相应寄存器时产生数据冒险，因为硬件的自动入栈行为并没有受到大内核锁的保护。
Q3
In your implementation of env_run() you should have called lcr3(). Before and after the call to lcr3(), your code makes references (at least it should) to the variable e, the argument to env_run. Upon loading the %cr3 register, the addressing context used by the MMU is instantly changed. But a virtual address (namely e) has meaning relative to a given address context--the address context specifies the physical address to which the virtual address maps. Why can the pointer e be dereferenced both before and after the addressing switch?
struct Env *e本质上是一个内核栈上的变量，由于用户态的地址空间映射是从内核态内存空间复制过来的，其中也复制了内核栈的映射，因此在用户态也能够以只读方式来访问该指针——但是不能修改。
Q4
Whenever the kernel switches from one environment to another, it must ensure the old environment's registers are saved so they can be restored properly later. Why? Where does this happen?
之所以需要保存上一个用户程序的上下文，是因为下一个被调度的程序会破坏掉所有的寄存器状态。用户态程序是通过int 0x30软中断来陷入内核态的，在_alltraps中会通过pushal来保存所有的用户态上下文到内核栈上，然后又会被拷贝到当前Env结构体中（curenv->env_tf = *tf），因此在env_run()中，可以通过env_pop_tf()来切换回正确的上下文。
关于UVPT
在实现用户态的fork()调用时，为了建立子进程的页表映射，我们需要能够访问当前自己进程的页表。由于这本质上是一个安全的操作，因此我们没有必要以系统调用的形式来提供这个功能，而是直接将页表映射到内核态地址空间中。
关于PTE_COW的标记顺序
Note: The ordering here (i.e., marking a page as COW in the child before marking it in the parent) actually matters! Can you see why? Try to think of a specific case where reversing the order could cause trouble.
Why do we need to mark ours copy-on-write again if it was already copy-on-write at the beginning of this function (duppage())?
如果先将父进程的页面标记为COW，那么它有可能在fork()上下文中被写入并触发page fault（例如这个页面是栈空间），为其分配了一个新页并且具有写权限，此时旧的页面引用计数-1之后就直接被回收了，我们将新页映射给了子进程，那么就会出现对于一个物理页，子进程的权限是COW而父进程却可以直接写入的错误。而如果先将页面以COW映射给子进程，那么就会增加该页面的引用计数，使其不会被错误释放。
由于相似的原因，即便当前页面在函数一开始是COW，函数执行时也可能会写入它，这导致当前页面变成了可写权限并被映射给子进程，因此在函数结束时需要重新将其标记为COW以免权限错误。
关于系统调用开销
Challange题目中提到可以用批处理的方式批量下发syscall以降低用户态-内核态切换开销。考虑到一次切换所引入的大量上下文保存/恢复以及跳转等开销还是很大的，在现代Linux系统上，实际上是会对此进行优化。另外一个值得注意的事情是QEMU只是功能模拟，并没有很好地模拟TSC相关指令，因此无法用它进行性能上的profiling，必须使用真实硬件。事实上，目前应该没有cycle-accurate级别的x86模拟器。
Lab 5
Q1
Do you have to do anything else to ensure that this I/O privilege setting is saved and restored properly when you subsequently switch from one environment to another? Why?
不需要，因为EFLAGS寄存器的管理自动地被包含在了进程上下文切换的过程中。
Q2
We implemented spawn rather than a UNIX-style exec because spawn is easier to implement from user space in "exokernel fashion", without special help from the kernel. Think about what you would have to do in order to implement exec in user space, and be sure you understand why it is harder.
这里的spawn本质上是新建了一个进程，然后给它设定了执行入口点，最后将状态改为RUNNABLE即可。如果希望实现exec的话，难点应该是如何正确覆盖当前进程的code segment：对于spawn的实现来说，进程没有在运行，可以随便覆盖掉；但对于exec的情况来说，当前还是在执行user space code，随便覆盖的话下一条指令就会出错。
Lab 6
Q1
How did you structure your transmit implementation? In particular, what do you do if the transmit ring is full?
这里我选择的实现是如果syscall不成功，就占用CPU轮询直到能够把packet发出去，因为以网卡硬件的效率，这是一个小概率发生的事件，因此可以牺牲CPU效率来降低latency。由于在TCPIP协议栈的实现中，是直接调用了阻塞式的ipc_send来发送packet给output进程，因此如果网卡驱动的ring buffer已满，导致syscall不成功，就会导致output进程这边没有进入IPC recv状态，进而导致core network进程进入sys_yield从而被挂起，直到ring buffer中有新的空闲位置能够发送数据包。进一步的优化可以是在output进程中再引入一个动态分配的buffer用来处理驱动ring buffer溢出的情况，这样就可以避免core network进程被挂起。本质上，当数据生产速度大于消费速度的时候，必然要引入额外的buffer从而避免阻塞。
Q2
How did you structure your receive implementation? In particular, what do you do if the receive queue is empty and a user environment requests the next incoming packet?
相比于发送packet，接收packet的ring buffer会更加tricky一些。首先，在硬件中只依靠RDH==RDT来判断buffer是否已满，所以重点是如何初始化RDT？考虑到硬件必须顺序写入buffer，我们假设在驱动中维护一个变量read_pos，指向buffer中第一个可读的位置，那么每次成功读取之后，我们会更新RDT = read_pos; read_pos += 1，这是因为有一个packet被读取走了，那么就可以把这个空闲descriptor放到ring buffer尾部，下次可读的descriptor一定在下一个位置。这样的更新逻辑也就意味着每次读取成功后，read_pos=RDT+1一定成立，那么只要让初始情况下该条件也成立，就可以省去在驱动中维护read_pos这个中间变量。第一次读取时显然要有read_pos=0，那么也就意味着RDT=RDLEN-1即可。
Challenge 1
Lab里这些额外的“挑战”问题虽然想一想都不太困难，但由于缺乏相应的框架代码和避雷指南，实现起来还是挺容易踩坑的。我只挑了一个比较容易测试的题目，但还是花掉了一整天时间，最终的代码是这个commit。
If the transmit queue is full or the receive queue is empty, the environment and your driver may spend a significant amount of CPU cycles polling, waiting for a descriptor. The E1000 can generate an interrupt once it is finished with a transmit or receive descriptor, avoiding the need for polling. Modify your driver so that processing the both the transmit and receive queues is interrupt driven instead of polling.
下面是一些要注意的点：
- 接收和响应PCI设备中断需要一些8259A的背景知识，在OSDev wiki上面有详细的解释以及示例代码，注意区分与中断状态相关的两个寄存器IRR和ISR的区别。
- PCI设备的IRQ line是在激活设备时分配的，但是中断向量表则是系统固定初始化的，因此需要设计某种机制将设备驱动的中断处理函数注册到IDT。
- 在网卡驱动
e1000_recv_packet的实现中，用户态进程通过syscall陷入内核态之后，如果发现要等待IO并挂起该进程，那么内核态的代码执行上下文是没有办法保存并原样恢复的，这样收到数据可读的中断之后，我们也不知道将数据写回哪里。这里我的实现采取了一个取巧的方式，通过修改eax，返回一个错误码给用户态，再设置curenv->env_status = ENV_NOT_RUNNABLE挂起进程；然后在用户态的sys_packet_recv中，如果监测到错误码就不断重试，这样当中断处理函数设置进程为ENV_RUNNABLE恢复其执行之后，虽然直接返回了用户态一个错误码，但是数据已经可读并且用户态看到错误后发起重试，这样就自然地返回了数据，并且也避免了在内核态保存执行上下文的复杂逻辑。 - 在interrupt handler上下文中如何知道哪个是要唤醒的input进程呢？我这里的做法比较简单粗暴：反正就只有一个进程负责网络输入，那直接拿静态变量存一下它的env ID好了。严格意义上来讲，应该也是网卡驱动程序负责维护一个数据结构来记录挂起的进程。