因为其实一直都没有好好读过 OSTEP,所以我在最近一周一口气把这本书读完了,但还是感觉不够,因为我知道要学会这玩意必须要 make hands dirty。于是准备快速的把 6.S081 过完,然后把 lab 做掉,再配合读 xv6 的代码。
System call
Syscall system call
第一个 lab 没什么好记录的,只不过用 system call 小打小闹而已,从第二个 lab 开始才是真的对 kernel 做事情。
遇到的一些疑问
英语太垃,看不懂这句话:
Add a
sys_trace()
function inkernel/sysproc.c
that implements the new system call by remembering its argument in a new variable in the proc structure (seekernel/proc.h
). The functions to retrieve system call arguments from user space are inkernel/syscall.c
, and you can see examples of their use inkernel/sysproc.c
.
龙鸣翻译:要加一个新的函数,这个函数通过在 proc
结构中增加的一个新的变量来实现系统调用,从用户空间拿到系统调用参数的函数在 syscall.c
中。确实没怎么看懂,那就先看看代码。
一个很关键的汇编文件:usys.S
sleep:
li a7, SYS_sleep
ecall
ret
.global uptime
uptime:
li a7, SYS_uptime
ecall
ret
.global trace
trace:
li a7, SYS_trace
ecall
ret
这个文件可以看到调用 system call 的一些指令,其中 a7
是 RISC-V 的一个寄存器,再看 kernel/syscall.c
当中的一个关键的函数:
void
syscall(void)
{
int num;
struct proc *p = myproc();
num = p->trapframe->a7;
if(num > 0 && num < NELEM(syscalls) && syscalls[num]) {
p->trapframe->a0 = syscalls[num]();
} else {
printf("%d %s: unknown sys call %d\n",
p->pid, p->name, num);
p->trapframe->a0 = -1;
}
}
这个函数应该就是用户态和系统调用的接口,首先获取当前进程的 a7
寄存器,如果这个寄存器中的系统调用号存在(也就是 num > 0 && num < NELEM(syscalls) && syscalls[num]
语句为真),那就调用它并返回(把 a0
寄存器设置为返回值),否则就返回 -1
。
递归学习:看不太懂下面这个函数指针数组到底是什么玩意:
static uint64 (*syscalls[])(void) = {
[SYS_fork] sys_fork,
[SYS_exit] sys_exit,
[SYS_wait] sys_wait,
[SYS_pipe] sys_pipe,
[SYS_read] sys_read,
[SYS_kill] sys_kill,
[SYS_exec] sys_exec,
[SYS_fstat] sys_fstat,
[SYS_chdir] sys_chdir,
[SYS_dup] sys_dup,
[SYS_getpid] sys_getpid,
[SYS_sbrk] sys_sbrk,
[SYS_sleep] sys_sleep,
[SYS_uptime] sys_uptime,
[SYS_open] sys_open,
[SYS_write] sys_write,
[SYS_mknod] sys_mknod,
[SYS_unlink] sys_unlink,
[SYS_link] sys_link,
[SYS_mkdir] sys_mkdir,
[SYS_close] sys_close,
};
其实就是看不懂 uint64 (*syscalls[])(void)
的意思,参考之前知乎上看到的一个回答,把这个东西翻译成英文: an array of pointers to a function that returns uint64,也就是一个函数指针的数组,这个初始化的方式也确实给我整麻了,但无所谓看懂了就行,不纠结语法。
其实还有一个终极问题:当调用系统调用的时候,真正的流程到底是什么?很遗憾这可能需要用 gdb 目力调试才能知道,但其实在不知道这个事情的流程下也能够完成这个实验,只需要观察一下 sys_exit
的代码:
uint64
sys_exit(void)
{
int n;
if(argint(0, &n) < 0)
return -1;
exit(n);
return 0; // not reached
}
它调用了 argint(0, &n)
来获取了进程退出时的状态号,再看到 syscall.c
中对于 argint
函数的注释:// Fetch the nth 32-bit system call argument.
就可以知道这个函数就是用来获取系统调用的参数的,那直接先拿来用就好了(拿来主义)。
最终增加的关键代码如下:(还有一些杂七杂八的东西要加,比如系统调用的打印)
uint64
sys_trace(void)
{
uint mask;
if(argint(0, (int *)&mask) < 0)
return -1;
myproc()->trace_mask = mask;
return 0;
}
RISC-V 系统调用的一些规则摘录
- syscall number is passed in
a7
- syscall arguments are passed in
a0
toa5
- unused arguments are set to
0
- return value is returned in
a0
Sysinfo system call
差不多和前面的 system call 一样,需要把一些信息拷贝到 user 空间,要用到 copyout()
函数。
// Copy from kernel to user.
// Copy len bytes from src to virtual address dstva in a given page table.
// Return 0 on success, -1 on error.
int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
uint64 n, va0, pa0;
while(len > 0){
va0 = PGROUNDDOWN(dstva);
pa0 = walkaddr(pagetable, va0);
if(pa0 == 0)
return -1;
n = PGSIZE - (dstva - va0);
if(n > len)
n = len;
memmove((void *)(pa0 + (dstva - va0)), src, n);
len -= n;
src += n;
dstva = va0 + PGSIZE;
}
return 0;
}
其实也很简单,直接拿到当前进程的 pagetable,然后虚拟地址其实就是第一个参数,其他的直接传进去用就好了。
至于活跃进程数量和空闲内存数:
- xv6 中的进程比较简单,是一个固定的数组(64个)。遍历一遍,剔除
UNUSED
的数量就好了; - 先获取空闲的页数,然后乘以 4K 就可以得到空闲字节数。
uint64
sys_sysinfo(void)
{
// printf("hello\n");
struct sysinfo info;
uint64 user_addr;
struct proc *p = myproc();
if(argaddr(0, &user_addr) < 0)
return -1;
info.freemem = free_memory_number();
info.nproc = process_number();
if(copyout(p->pagetable, user_addr, (char*)&info, sizeof(struct sysinfo))<0)
return -1;
return 0;
}
Page table
每个进程的 kernel page table
说实话,做到这一步的时候,我很莫名其妙为什么要去修改内核的这个机制,也就是「内核拥有一个自己的页表」机制。
读了一下 xv6 的 rec-book,这个 lab 的意思大致就是因为 xv6 的内核采用的是 direct-mapping 机制,所以可以让「内核拥有一个自己的页表」,但这样的话在运行内核代码的时候,就要用一个「转换机制」来访问用户的数据,接下来几个事情就是为了改变这个事情,至于改了之后到底有什么好处,我也不知道,做了再说。
大致的思路是这样:
- 首先是需要给每个 process 维护一个 kernel_pagetable 域。
- 需要给每个 process 创建时(也就是在函数
allocproc
中)填充这个 process 的 kernel_pagetable ,目前来说每个进程的内核页表是和内核独有的页表是一模一样的。 - 除了上面和内核独有页表的内容一样以外,每个进程都要在自己的页表里再增加自己的内核 stack 映射。而这个映射原本在未修改的 xv6 中是由内核提前为所有的预备进程做好的(
procinit
函数),现在需要把这个事情延迟到在每个进程被创建的时候再做。 - 在调度函数中确保在切换到某个进程的之前,使用该进程的内核页表(也就是在
swtch(&c->context, &p->context)
之前),在重新回到调度程序后,再切换回内核自己的页表。 - 在进程被 free 的时候,顺便把 kernel_pagetable 也删了,但不用删除页表的叶结点,只需要删前两层的索引。
在差不多做完这些事情后,还遇到了一些问题。
- 改完之后
make qemu
直接报panic: kvmpa
。
kvmpa
函数的用处是「将内核的一个虚拟地址转换为一个物理地址」,而 xv6 的内核地址大多都是 direct-mapping 的,换言之其实就是转换内核栈的地址而已,而在改完之后,进程的内核栈的地址已经不属于内核的页表了,而属于每个进程自己的内核页表,因此需要修改 pte = walk(kernel_pagetable, va, 0)
为 pte = walk(myproc()->kernel_pagetable, va, 0)
。(调用 myproc()
需要加两个头文件)
- 进程内核栈的内存泄漏问题
要注意,每个进程被 free 的时候,即使不用释放进程内核页表绝大多数的叶子 page ,但是进程内核栈的 page 是必须要释放的,不然跑 usertests 的时候会在 sbrkfail 处报 kvmmap 的 panic ,我没有用 gdb 去调试出到底出了什么差错。但在我添加了对内核栈的手动释放后,就不报错了,所以很大可能的原因就是内存泄漏了,每当创建一个进程就浪费掉 1 个 page,free 的时候又不回收,最后就导致内存用尽没得用了。
if(p->kstack)
uvmunmap(p->kernel_pagetable, p->kstack, 1, 1);
p->kstack = 0;
if(p->kernel_pagetable)
proc_freekernelpagetable(p->kernel_pagetable);
p->kernel_pagetable = 0;
Trap
一些关键的寄存器:
stvec
用于存储 trap handler 的地址,由内核写入sepc
来保存进入 trap 前的pc
scause
保存 trap 的原因sccratch
在调用 trap handler 的时候会用到这个寄存器sstatus
中的 SIE 位表示是否阻塞设备中断,SPP 位表示 trap 来自于用户态还是内核态
当 RISC-V CPU 要开始一个 trap 的时候依次做如下的事情:
- 如果是一个设备终端且
sstatus
中的 SIE 位是空的,就不往下走了; - 清楚 SIE 位(保证原子性);
- 将当前的
pc
复制到sepc
; - 将当前的 mode 复制到
sstatus
的 SPP 位; - 设置
scause
; - 将 mode 设置为 supervisor mode;
- 将
stvec
复制到pc
; - go on 运行指令。
User mode 下的 trap
流程是
trampoline.S
中的uservec
函数,这个函数被stvec
所指- 转到
trap.c
中的usertrap
函数 - trap 结束后转到
trap.c
中的usertrapret
函数 - 然后转到
trampoline.S
中的userret
函数
首先,硬件并不会在发生 trap 时切换页表,因此用户的页表需要存在一个虚拟地址映射到 uservec
;同时 uservec
函数必须显示将 satp
切换到内核的页表(不然不能直接访问物理内存)。xv6 用了一个 TRAMPOLINE
的虚拟地址和 trampoline
页来映射 trampoline.S
的代码,并且不管是用户空间还是内核空间,虚拟地址都是一样的。也就是说,当 trap 发生时,首先从 stvec
中读到 uservec
的虚拟地址,也就是 TRAMPOLINE
然后经过页表映射到 trampoline
。
trampoline.S
的部分代码:
Xv6 还开辟了另外一个 page (就在 trampoline
下面)用来保存发生 trap 时被打断的指令的寄存器值,这个 page 叫做 trapframe
。一开始,寄存器 sscratch
保存着映射到 trapframe
页的虚拟地址,也就是 TRAPFRAME
。(想想这里为什么是虚拟地址而不是物理地址,因为运行到这的时候仍然没有切换页表,所以用户空间页表也需要保证好 TRAPFRAME
的映射)
csrrw a0, sscratch, a0
这个时候,a0
的值和 sscratch
就被交换了。
sd ra, 40(a0)
sd sp, 48(a0)
sd gp, 56(a0)
sd tp, 64(a0)
sd t0, 72(a0)
sd t1, 80(a0)
sd t2, 88(a0)
sd s0, 96(a0)
sd s1, 104(a0)
sd a1, 120(a0)
sd a2, 128(a0)
sd a3, 136(a0)
sd a4, 144(a0)
sd a5, 152(a0)
sd a6, 160(a0)
sd a7, 168(a0)
sd s2, 176(a0)
sd s3, 184(a0)
sd s4, 192(a0)
sd s5, 200(a0)
sd s6, 208(a0)
sd s7, 216(a0)
sd s8, 224(a0)
sd s9, 232(a0)
sd s10, 240(a0)
sd s11, 248(a0)
sd t3, 256(a0)
sd t4, 264(a0)
sd t5, 272(a0)
sd t6, 280(a0)
这里把除了 a0
以外的寄存器都保存到了 trapframe
中。
csrr t0, sscratch
sd t0, 112(a0)
这里把 a0
也保存到了 trapframe
中。
而注意到,这里的指令是从 40(a0)
开始的,说明 trapframe
里面原本还存了 5 个值,其中包括了内核的页表、进程的内核栈、usertrap()
的地址和当前 CPU 的 hartid
。为什么还缺一个呢,我也不知道缺了什么,反正代码里看不出来。为了进入 usertrap()
,需要恢复这些值。
# restore kernel stack pointer from p->trapframe->kernel_sp
ld sp, 8(a0)
# make tp hold the current hartid, from p->trapframe->kernel_hartid
ld tp, 32(a0)
# load the address of usertrap(), p->trapframe->kernel_trap
ld t0, 16(a0)
# restore kernel page table from p->trapframe->kernel_satp
ld t1, 0(a0)
csrw satp, t1
sfence.vma zero, zero
注意到,运行完最后的指令(也就是切换到内核页表)后,a0
中保存的 TRAPFRAME
虚拟地址已经失效了。
最后,跳转到 usertrap()
。
jr t0
读到这里,我仍然有些许的疑问,因为 xv6 的文档上说其实用户空间涉及到了 32 个寄存器,但这里其实只保存了 31 个寄存器,我的疑惑是缺了哪一个?
进入 usertrap()
后
首先,验证是不是从 user mode 来的,然后修改了 stvec
的值(为什么?)。因为如果这个时候再次发生一些 trap ,就需要内核的 handler 来解决了,所以将这个入口改为了内核的 handler 的函数地址。然后根据 trap 的成因(scause
寄存器)来决定是系统调用、设备中断还是一个单纯的异常,做完这些事情后调用 usertrapret()
。
usertrapret()
干了什么
首先,关闭了中断(保证不被打断)。
然后重新设置了 stvec
的值,让它重新指向 TRAPOLINE
。
w_stvec(TRAMPOLINE + (uservec - trampoline));
再重新设置 trapframe
中的一些值,包括 satp
(这是页表)、内核栈指针等。
我这里其实没有明白为什么要重新设置,之前的行为会修改这些值吗?因为我只看到从
trapframe
中读取这些值。
再设置好 sepc
后(从之前保存的 trapframe
中),就调用 userret
函数。这里也值得思考的是,userret
函数是在 trampoline
页里的,这个时候仍然是内核页表,因此对于 TRAMPOLINE
虚拟地址的映射是用户页表和内核页表都做了的,而 TRAPFRAME
的映射只有用户页表。
userret()
在进入这个函数之前,usertrapret()
函数传了两个参数:当前进程的用户空间页表和虚拟地址 TRAPFRAME
,C 代码如下。
// tell trampoline.S the user page table to switch to.
uint64 satp = MAKE_SATP(p->pagetable);
// jump to trampoline.S at the top of memory, which
// switches to the user page table, restores user registers,
// and switches to user mode with sret.
uint64 fn = TRAMPOLINE + (userret - trampoline);
((void (*)(uint64,uint64))fn)(TRAPFRAME, satp);
进入之后,首先当然是切换页表(因为所有有用的东西都在用户页表才能翻译的地址里)。
# switch to the user page table.
csrw satp, a1
sfence.vma zero, zero
然后把所有的寄存器都还原,这里用到了 sscratch
这个寄存器,使得一系列操作完成之后 sscratch
的值又恢复到了 TRAPFRAME
后执行了 sret
指令,皆大欢喜地回到了用户的程序中。
Syscall 中如何传递参数
由于在进入系统调用之前,所有的寄存器都被存在了 trapframe
页中,因此 syscall 函数只需要从当前进程的 trapframe
中获取寄存器内容。
static uint64
argraw(int n)
{
struct proc *p = myproc();
switch (n) {
case 0:
return p->trapframe->a0;
case 1:
return p->trapframe->a1;
case 2:
return p->trapframe->a2;
case 3:
return p->trapframe->a3;
case 4:
return p->trapframe->a4;
case 5:
return p->trapframe->a5;
}
panic("argraw");
return -1;
}
Kernel mode 下的 trap
CPU 处于 kernel mode 的时候, stvec
寄存器的值指向的是 kernelvec
函数,这个函数的行为和 uservec
很相似,存下当前的所有寄存器(31个),然后调用 kerneltrap
。
注意这里的机制需要两个东西来帮助:
- 内核的页表需要保证某个虚拟地址到
kernelvec
的映射; - 需要内核 stack 帮忙保存寄存器。
Kernel mode 下的 trap 只有两类:设备中断和异常,xv6 的异常处理比较简单,直接报错。
设备中断中有一个特殊的中断叫做时钟中断,这个时候会调用 yield
来挂起自己。(这个机制和调度函数 scheduler
有关系)
在某个时间点,kerneltrap
准备返回后,它会重新设置回之前保存在内核栈上的 sepc
、sstatus
(这里是在 kerneltrap
函数里保存的),然后再回到 kernelvec
,恢复之前的那 31 个寄存器,然后运行 sret
指令,恢复原本的执行流。
Trap lab
Trap 的东西快读完了,还剩一个 COW 没读,先做做看 lab 吧。
首先是要加一个 backtrace
来追踪 function calls ,这其实很简单,因为大致就能知道要怎么办了,先用一个实例代码来看看 RISC-V 的函数调用。首先看一段简单的 C 代码。
int g(int x) {
return x+3;
}
翻译成汇编是这样:
0: 1141 addi sp,sp,-16
2: e422 sd s0,8(sp)
4: 0800 addi s0,sp,16
6: 250d addiw a0,a0,3
8: 6422 ld s0,8(sp)
a: 0141 addi sp,sp,16
c: 8082 ret
首先,进入函数后将栈指针(sp
)减 16(我也不知道为什么是 16,我猜是为了对齐),然后把旧的 s0
存到了前 8 个字节中,再把旧的 sp
(减 16 之前的)存到了 s0
当中;
在函数返回的时候,先把刚刚进入这个 stack frame 时保存在栈上的旧值返回到 s0
中,再重置 sp
,运行 ret
指令。
可以想象一下函数 A 调用函数 B 再调用函数 C 的过程:
这里假设函数 A 是这个进程最初最初的函数,也就是说它的栈是从新分配的栈页的最高地址开始的。
- 一开始在函数 A 中,
s0
保存的是 A 的 stack frame 的首指针(高地址); - 进入函数 B 后,A 的 frame pointer 被保存到了 B 的 stack 的前八个字节中,此时
s0
保存的是 B 的 frame pointer; - 进入 C 后,B 的 pointer 被保存在了 C 的 stack 上,
s0
保存 C 的 pointer。
如果想要回溯,那只需要在函数 C 中取出 s0
的值,然后用这个值取到 B 的 frame pointer,然后层层循环,直到取到 0 为止。注意循环的终止条件:pointer 如果等于这个 pointer 所在的 page 的最高地址,那就停止,因为这意味着这是最最最初始的一个函数调用。
void
backtrace(void)
{
uint64 s0 = r_fp();
uint64 last_s0 = *(uint64*)(s0 - 16);
uint64 ra = *(uint64*)(s0 - 8);
printf("backtrace:\n");
while (s0 != PGROUNDUP(s0)) {
printf("%p\n", ra);
s0 = last_s0;
last_s0 = *(uint64*)(s0 - 16);
ra = *(uint64*)(s0 - 8);
}
}
然后要加一个简易的 signal 机制,其实很简单。
- 首先要知道
sigalarm
和sigreturn
都是属于 syscall ,也就是说这些函数的调用和返回中间都会和当前进程的trapframe
域打交道。 - 对于
sigalarm
只要在proc
结构体中保存相应的alarm_ticks
和handler
的地址就好了。同时在保存一个ticks
让它每产生一次时钟中断就自增,如果在时钟中断发生时既设置了alarm_ticks
、ticks
又超过了alarm_ticks
就修改返回的指令地址,让它跳转到handler
。 - 接下来的问题就是如何让
handler
结束后再返回到原本被打断的指令。根据 MIT 的提示,只需要在修改pc
为handler
之前,把整个trapframe
保存下来就好了(在proc
结构体中再开一个域用来保存)。因为sigreturn
也是一个 syscall ,在它返回之前再把之前的整个saved_trapframe
覆盖当前的trapframe
,然后再返回交给操作系统,就能顺利回到原本的指令。 - 最后需要注意的是,需要一个
flag
来表明此时该进程已经进入signal_handler
,来避免 signal 的重入问题。
Lazy page allocation
起因很简单,假如说用户要求内核分配很多很多的页,内核需要花很多时间来分配,所以产生了 lazy allocation 的概念。值得注意的是,这里的 allocation 是针对用户的 heap ,没有涉及到 stack 。但其实这里我有一个疑惑,为什么对栈不实现一个 lazy allocation 呢?虽然这其实显得很反常,因为栈的增长其实是不可控的。
追溯 panic
首先很简单,由于用户申请堆实际上只能通过 system call sbrk()
,那实现懒加载的第一步就是不加载,修改这个系统调用对应的函数 sys_sbrk(void)
。
uint64
sys_sbrk(void)
{
int addr;
int n;
if(argint(0 &n)<0)
return -1;
addr = myproc()->sz;
/**
* 删除对于 growproc() 的调用
*/
myproc()->sz += n;
return addr;
}
这样改了之后当然会 panic ,因为其实压根就没有没有分配空间,所以对于这些用户以为已经分配了空间的虚拟地址的访问会触发一个用户态下的 page fault 。但我此时在想的是,在调用了 echo
程序后,到底在哪一步调用了 sys_sbrk()
呢?这个事情其实很难去追溯,因为操作系统在背后做了太多的事情。我用 gdb 看了一下。
最后发现了几件事情:
- 在用户输入命令
echo hi
后、 Shell 调用 exec 之前,就已经进入了 trap 并导致 panic 。 sys_sbrk
的调用是在输入命令之后,但是也在 Shell 调用 exec 之前。- 其实自始自终只调用了一次
sys_sbrk
。 - 上面的那次
sys_sbrk
的调用是触发了 trap 的关键 。
我用 gdb 追踪到的事情:
首先 xv6 非常正常的启动,直到进入到终端,也就是
sh
程序被加载进来。c/** * sh 程序的部分代码 */ int main(void) { ... if(fork1() == 0) runcmd(parsecmd(buf)); wait(0); ... } struct cmd* parsecmd(char *s) { ... cmd = parseline(&s, es); ... } struct cmd* parseline(char **ps, char *es) { struct cmd *cmd; cmd = parsepipe(ps, es); ... } struct cmd* parsepipe(char **ps, char *es) { struct cmd *cmd; cmd = parseexec(ps, es); ... } struct cmd* parseexec(char **ps, char *es) { ... ret = execcmd(); ... } struct cmd* execcmd(void) { struct execcmd *cmd; cmd = malloc(sizeof(*cmd)); memset(cmd, 0, sizeof(*cmd)); cmd->type = EXEC; return (struct cmd*)cmd; }
经过了一个下午的目力 gdb,我终于发现了这个非常非常恶心的调用栈:在用户输入了任何命令后,终端程序(也就是
sh
)的执行流是这样走的:main -> parsecmd -> parseline -> parsepipe -> parseexec -> execcmd
,最后到达了execcmd
函数中的malloc
调用,这里的malloc
函数定义在另一个文件user/umalloc.c
中。很操蛋的是,gdb 似乎没有办法识别umalloc.c
的符号,因此执行流进入到这个函数后,我只能对着看不懂的 RISCV 汇编纯猜了,不过也大致猜到了:malloc
函数调用了同一个文件中定义的morecore
函数,该函数如下:cstatic Header* morecore(uint nu) { char *p; Header *hp; if(nu < 4096) nu = 4096; p = sbrk(nu * sizeof(Header)); if(p == (char*)-1) return 0; hp = (Header*)p; hp->s.size = nu; free((void*)(hp + 1)); return freep; }
这里才得知,是
morecore
函数真正正正的调用了系统调用sbrk
(在汇编曾经调用了ecall
)。从调试的过程中发现,实际上sbrk
调用是成功的,ecall
和eret
都没有出差错,真正出问题的地方在hp->s.size = nu;
这句 C 程序上。从汇编的层面上看,机器在运行指令sw s6, 8(a0)
后直接报了 panic 。也就是说,在操作系统仅仅修改了进程的一个字段而没有真正的分配一个页给它后,当该进程试图去写(这里sw
指令就是写内存)时,触发了用户态的 trap 。
解决 panic
2021 年 8 月 10 日,此时我已经做完了 lazy lab 和 cow lab。由于对并发的 lab 并不感兴趣,持久化的内容准备下学期在 CSE 上再学,因此 6.S081 的学习到这里暂时结束,有空再补上 lazy 和 cow 的思考,开了个新坑:6.824 。