北航操作系统实验2019：Lab4-1流程梳理
前言
操作系统的实验课实在令人头秃。我们需要在两周时间内学习相关知识、读懂指导书、读懂代码、补全代码、处理玄学bug和祖传bug，以及回答令人窒息的思考题。可以说，这门课的要求非常高，就个人感觉，远比计算机组成实验课要难受。
一方面，想要达到细致理解操作系统每个实现细节，非常困难，需要大量时间和经历的投入；但另一方面，如果我们能够理解了操作系统实现的每个细节，我们的水平也会有大幅度的提升。在这里，我记录下本次实验课下我的学习经历，如果有不对的地方，希望能够指出，以求共同进步。
一、预备知识
在前面三个Lab的实验中，我们成功的搭建起了操作系统的内核，建立了内存管理机制和进程调度机制。一般来说，进程是给用户使用的，而用户无法直接对系统内核进行存取。另一方面，进程与进程之间的虚拟地址互相独立，这使得两个进程之间的互相通信变得困难。但是，用户会在有些情况下需要使用只有内核才能进行的操作。为了解决这个问题，操作系统设计了系统调用。
指导书上已有的知识，我在此不再赘述。在进行实验之前，我们需要稍微补习一点知识，主要是关于汇编函数方面的东西。这些知识，指导书或者其他地方都有，只不过比较零碎。我稍微聚集了一下这些知识，如果想要了解的更详细，可以深入了解。
1. 汇编函数构造宏(include/asm/asm.h)
为了方便的像C语言一样构造函数，我们的操作系统事先为我们提供了函数的宏，我们可以直接使用。这个宏的代码并非由本校人员开发，应当是较为通用的定义方式。文件中为我们提供了两种函数的宏，即叶函数（LEAF）和嵌套函数(NESTED)。
我们把函数体中没有函数调用语句的函数称为叶函数，自然如果有函数调用语句的函数称为非叶函数。在MIPS 的调用规范中，进入函数体时会通过对栈指针做减法的方式为自身的局部变量、返回地址、调用函数的参数分配存储空间（叶函数没有后两者），在函数调用结束之后会对栈指针做加法来释放这部分空间，我们把这部分空间称为栈帧（Stack Frame）。
——OS指导书
下面是宏的具体实现定义。可以看到，函数定义无非是声明一个全局符号，给定一个标签用于跳转和返回。
下面是文件中部分代码的引用。有些代码后面我没有写注释，是因为我自己也弄不太清楚，不敢乱讲，怕引起误会。如果有同学明白，希望可以给我讲讲。
#define LEAF(symbol) \
.globl symbol; \声明"symbol"为全局变量
.align 2; \下一个数据的地址空间按字对齐
.type symbol,@function; \
.ent symbol,0; \告诉汇编器"symbol"函数的起始点，用于调试
symbol: .frame sp,0,ra 提供一个名为"symbol"的标签，将跳转到此处
#define NESTED(symbol, framesize, rpc) \
.globl symbol; \
.align 2; \
.type symbol,@function; \
.ent symbol,0; \
symbol: .frame sp, framesize, rpc 确定栈帧大小以及结束时的返回地址
#define END(function) \
.end function; \指出函数结尾，用于调试
.size function,.-function 在符号表中列出函数名和函数指令字节数
2.C函数和汇编函数的参数、返回值传递
有时候，我们会不可避免的在C语言中调用汇编函数，也会在汇编语言中调用C函数。根据MIPS软件标准(ABI)的定义，函数的参数传递按照如下原则：
- 如果函数参数个数≤4，则将参数依次存入a0-a3寄存器中，并在栈帧底部保留16字节的空间（即sp的值减去16），但并不一定使用这些空间。
- 如果函数参数个数>4，则前4个参数依次存入a0-a3寄存器中，从第5个参数开始，依次在前4个参数预留空间之外的空间内存储，即没有寄存器去保存这些值。
- 举例，如果一个C函数有6个参数，在汇编语言中需要调用的时候，应当将前4个参数存在a0-a3寄存器中，第5个参数存在16(sp)的位置，第6个参数存在20(sp)的位置。区间0-15的空间保留但不使用。
而关于函数的返回值，MIPS ABI规定，返回值存在$v0寄存器中。某些特殊的情况下也会用到$v1寄存器，但不常见。想了解更多关于返回值的知识，请查阅书籍See MIPS Run Linux。
3.栈帧方法宏(include/stackframe.h)
我们在进行用户态和内核态之间的切换，或者进程之间的切换时，需要保存现场。所谓现场，就是include/trap.h中所定义的trap结构体，其中包含的信息有：
- 32个寄存器的值
- CP0部分寄存器的值
- HI、LO两个乘除法寄存器的值
- 程序的指令计数器PC
但是这个文件中只有结构体的定义，没有将数据存入结构体的操作。将寄存器中的值存入内存，显然要用汇编语言去完成。stackframe.h中定义了一些汇编函数的宏，方便我们对现场进行存取操作。下面摘录了其中的宏，并作出相应的解释。
//TF_SIZE是Trapframe寄存器的字节大小
.macro STI //Set Interrupt，打开全局中断使能（允许中断）
.macro CLI //Close Interrupt，关闭全局中断使能（屏蔽中断）
.macro SAVE_ALL //保存所有现场，将数据以Trapframe结构体形式存在sp为开头的空间中
.macro RESTORE_SOME //恢复部分现场，此处的“部分”仅不包括sp的值
.macro RESTORE_ALL //恢复所有现场，包括栈顶的位置
.macro RESTORE_ALL_AND_RET //恢复现场并从内核态中返回
.macro get_sp //获取栈顶位置，此函数会判断当前的状态是异常还是中断，
//从而决定栈顶是TIMESTACK还是KERNEL_SP。
//系统调用是编号为8的异常，进程切换是时钟中断信号。
二、系统调用机制的实现
按照指导书上的思路，我们来梳理一下系统调用的流程：
- 调用一个需要内核配合才能完成的函数，该函数会调用syscall_xxx函数(user/syscall_lib.c)
- syscall_xxx函数会调用我们写的汇编函数msyscall(user/syscall_wrap.S)，该函数使用特权指令syscall
- 此时CPU触发异常，陷入内核态，异常向量分发器检测到是系统调用（异常编号为8），进入handle_sys函数(lib/syscall.S)，进行处理
- handle_sys函数会进一步读取系统调用号，进行进一步分发，分发进C函数(lib/syscall_all.c)，在C语言中进行处理。
- 在内核态中处理完毕，返回用户态，并将返回值(位于$v0寄存器)传递回去，一层层回到调用处。
需要填写的文件：
-
user/syscall_wrap.S
只需要念一句咒语：syscall就好。当然，考虑到MIPS的习惯，可以move v0, a0，这样后面取出系统调用号也可以在v0中取。
-
lib/syscall.S
TODO项有三：
- 取出EPC，计算一个合理的值，再存回去。合理的值是什么呢？如果syscall不在延迟槽里面，合理的值自然只能是顺位的下一条指令EPC+4啦。而我们写的函数里面，显然没有把syscall放在延迟槽，所以就是EPC+4。
- 将系统调用号存入寄存器a0。系统调用号是我们函数的第一个参数。根据MIPS ABI，第一个参数放在a0寄存器中。然而，a0寄存器的值从存入到使用没有发生变化。所以，只要你前面没有瞎写，这一步完全可以不用操作。如果你前面写了move v0, a0，也可以从TF_REG2中读取，但显得没有必要。
- 在当前栈指针分配6个参数的存储空间，并将6个参数安置到期望的位置。前四个参数存在a0-a3寄存器，后两个参数（预设代码已经帮你取出，存在t3、t4寄存器）存在16(sp)和20(sp)的位置就行。
注：第二、三、四个参数的值没有改变过，因而也不需要修改。系统调用号寄存器a0虽然用于计算相对位置，但是此后的调用函数根本没有用到，只是起到一个占位的作用（指导书所言），因而也可以不用修改a0的值，将错就错，不会影响。
-
lib/syscall_all.c
此处需要实现四个函数，按照文件中的函数顺序来介绍。
/* Overview:
* 这个函数允许当前进程释放CPU。
* Post-Condition:
* 取消运行当前进程。这个函数永远也不会返回。（？）
*/
void sys_yield(void)
{
// your code here
/* 直接使用我们之前写的sched_yield函数即可。
* 不过，需要在KERNEL_SP和TIMESTACK上做一点准备工作，
* 因为当前进程处于内核态，保存的现场在KERNEL_SP - sizeof(struct Trapframe)，
* 但是env_run中所使用的进程切换机制中，
* bcopy从TIMESTACK - sizeof(struct Trapframe)的位置进行复制
* 因而我们要把现场复制到TIMESTACK栈区。
*/
}/* Overview:
* 分配一页内存，并映射到进程envid空间中的虚拟地址va，加上权限perm。
* 可能的副作用是，如果va已经和一个页面p构建了映射，那么页面p就会被解除映射。
* Pre-Condition:
* perm的PTE_V（有效）位必须为1，而PTE_COW（写时复制）位必须为0。其他位随意。
* Post-Condition:
* 返回值0是成功映射，返回值小于0即是出错。
* 注意va必须小于UTOP，以及env可能会调整自己和子进程的地址空间。
*/
int sys_mem_alloc(int sysno, u_int envid, u_int va, u_int perm)
{
// Your code here.
struct Env *env;
struct Page *ppage;
int ret;
ret = 0;
/* 首先将上方注释里的所有需要判断的情况全部判断完。
* 包括va的范围，perm的部分位，envid是否合法。
* 进行页面分配(page_alloc)和页面插入(page_insert)的时候也会报错，注意返回值。
* 各种负数返回值的意义在include/mmu.h中，此后不再赘述调用函数的返回值。
* /
}/* Overview:
* 将源进程地址空间中的相应内存映射到目标进程的相应地址空间的相应虚拟内存中去，
* 并且附加保护位perm。perm的限制和sys_mem_alloc中一样。
* （也许我们应该加上只读页面不可映射为可写页面的判断？）
* Post-Condition:
* 返回值0代表成功，小于0代表报错。
* Note:
* 不能对UTOP以上的内存进行操作。
*/
int sys_mem_map(int sysno, u_int srcid, u_int srcva, u_int dstid, u_int dstva, u_int perm)
{
int ret;
u_int round_srcva, round_dstva;
struct Env *srcenv;
struct Env *dstenv;
struct Page *ppage;
Pte *ppte; ppage = NULL;
ret = 0;
round_srcva = ROUNDDOWN(srcva, BY2PG);
round_dstva = ROUNDDOWN(dstva, BY2PG);
//此处将两个虚拟地址按页进行对齐，映射时应当使用以上两个地址。 // your code here
/* 首先判断srcva，dstva，perm，srcid，dstid是否合法，
* 然后在源进程的地址空间中找到所需的页面，插入到目标进程的地址空间中。
* 主要是使用page_lookup和page_insert两个函数不能出错。
*/
return ret;
}/* Overview:
* 解除envid进程空间中虚拟地址va所绑定的页面。
* (如果va本身就没绑定页面，函数不作任何操作，算作成功)
* Post-Condition:
* 返回值0代表成功，小于0代表出错。
* 不能解除UTOP地址以上空间的映射。
*/
int sys_mem_unmap(int sysno, u_int envid, u_int va)
{
// Your code here.
int ret = 0;
struct Env *env;
/* 首先判断va，envid是否合法，然后page_remove即可，没有技术含量。
* 注意page_remove本身具有判断地址是否绑定的功能，所以无需多此一举。
*/
return ret;
}
三、进程间通信机制（IPC）
IPC 是微内核最重要的机制之一，目的是使得两个进程之间可以通讯，需要通过系统调用来实现。通讯最直观的一种理解就是交换数据。
两个进程之间之所以没法相互交换数据，是因为各个进程的地址空间相互独立。我们在之前写的函数，正是为了实现地址空间之间的沟通。而沟通两个进程，自然需要一个权限凌驾两个进程之上的存在来进行操作，即内核态。
在Lab3使用的进程控制块(struct Env)中，有部分值用于本次实验的进程间通信，代码如下：
// Lab 4 IPC
u_int env_ipc_value; // 传递的数据值
u_int env_ipc_from; // 发送者的进程id
u_int env_ipc_recving; // 进程是否阻塞，从而能够接收。0为不能接收，1为可以接收。
u_int env_ipc_dstva; // 接收物理页面的虚拟地址
u_int env_ipc_perm; // 接收页面的保护位
IPC的操作，本质是在内核态中对这些部分进行赋值。我们需要填的两个函数位于lib/syscall_all.c中。
/* Overview:
* 这个函数使得调用进程可以接收其他进程发送的信息。更准确地说，
* 这个函数可以标记当前进程，使得其他进程可以向其发送信息。
* Pre-Condition:
* dstva必须合法（NULL也是合法的）。
* Post-Condition:
* 这个系统调用函数会将当前进程状态置为NOT RUNNABLE，并释放CPU。
*/
void sys_ipc_recv(int sysno, u_int dstva)
{
/* 首先判断dstva是否合法。然后，置recving位为1，给dstva赋值，
* 设置进程状态为阻塞，并且重新调用sys_yield。
* 由于我们的算法采用了两个链表，所以当进程为阻塞时，应当从就绪链表中移出。
* 不过如果你采用了这种写法，就必须得另想办法终止当前进程。
* 因为哪怕进程不在sched_list里面，只要时间片没用光，依然可能继续运行。
* 这样程序就会出错。可以选择不删除不插入，yield函数遇到NOT RUNNABLE就跳过。
*/
}
/* Overview:
* Try to send 'value' to the target env 'envid'.
* 将value传给目标进程envid。
* 如果目标进程尚未处于可接收状态，返回值应当为-E_IPC_NOT_RECV。
* 其他情况下，发送成功后，目标进程的IPC部分数据应当按照如下规则更新：
* env_ipc_recving设置为0，防止多余的接收。
* env_ipc_from设置为发送进程的id。
* env_ipc_value设置为函数参数value。
* 目标进程需要标记为RUNNABLE，以便重新运行。
* Post-Condition:
* 返回值0代表成功，小于0代表出错。
*
* Hint: 你唯一需要调用的函数只有envid2env()。
*/
int sys_ipc_can_send(int sysno, u_int envid, u_int value, u_int srcva, u_int perm)
{
int r;
struct Env *e;
struct Page *p;
Pte *ppte;
/* 判断envid是否合法，目标进程是否处于可接收状态。
* 这个函数貌似是残缺的，srcva和perm没有使用，也没有映射物理页面。
* 只是单纯的传递一个值value而已。很迷。
* 同样需要注意，设置为就绪后是否加入就绪状态链表。取决于个人程序。
*/
return 0;
}
四、思考题分享参考
此处只是分享我的看法，不保证答案的正确性和完备性。
Thinking 4.1 思考并回答下面的问题：
-
内核在保存现场的时候是如何避免破坏通用寄存器的？
内核保存现场的方法，是将所有通用寄存器、CP0寄存器、当前PC值保存到栈里。但是，通用寄存器的值却非一成不变、完全保存。k0、k1两个寄存器由中断/自陷程序保留，这两个寄存器的值得不到保证。内核使用k0、k1两个寄存器保存用户栈、取出内核栈，再进行保存，从而维护了大多数通用寄存器的值。
-
系统陷入内核调用后可以直接从当时的a0-a3参数寄存器中得到用户调用msyscall留下的信息吗？
可以。内核保存现场的过程中没有破坏a0-a3参数寄存器的值，只改变过k0, k1, v0的值。
-
我们是怎么做到让sys开头的函数“认为”我们提供了和用户调用msyscall时同样的参数的？
参数的传递依赖于a0-a3参数寄存器和栈。只要我们保证a0-a3参数寄存器不变，栈能够以原本的样子复制到内核栈空间中，就能够让sys开头的函数认为参数相同。
-
内核处理系统调用的过程对Trapframe做了哪些更改？这种修改对应的用户态的变化是？
处理过程中，内核改变了Trapframe中寄存器v0的值，用于在用户态中传递系统调用函数的返回值。此外，内核改变了EPC的值，使得程序返回用户态后能够从正确的位置继续执行。
系统调用号 对于系统调用syscall_cgetc，它传入msyscall函数的系统调用号的数字值应该是？
打开文件user/syscall_lib.h，可以看到系统调用号的数值是常量SYS_cgetc。
打开文件include/unistd.h，可以读到__SYSCALL_BASE = 9527，SYS_cgetc = 9527+14 = 9541。
所以系统调用号的数字值应当是9541。