Xv6 OS

Problem xv6 中的 fork() 系统调用会将父进程的所有用户空间内存复制到子进程中，如果父进程很大，复制过程可能会花费很长时间。 更糟糕的是，这项工作通常是多余的：子进程 fork() 后面通常跟着 exec()，会丢弃复制的内存，通常不会使用其中的大部分。 另一方面，如果父进程和子进程都使用复制的页面，并且其中一个或两个都对其进行了写入，则复制确实是必要的。 Analysis 实现 copy-on-write (COW) fork() 的目标是推迟 allocating 和 copying 物理内存页面，直到实际需要复制为止（如果有的话）。 COW fork() 只会为子进程创建一个页表，其中用户内存的 PTE 指向父进程的物理页面。COW fork() 将父进程和子进程中的所有用户 PTE 标记为只读。当任何一个进程尝试写入其中一个 COW 页面时，CPU 都会强制触发 page fault。内核 page fault handler 会检测到这种情况，为发生错误的进程分配 a page of physical memory，将 original page 复制到 new page 中，并修改发生错误的进程中相关的 PTE 指向 new page，此时 PTE 标记为可写。当 page fault handler 返回时，用户进程将能够写入 page。 这边父进程和子进程都需要将 pte 标记为只读，这样在写任意一个进程发生 page fault 时，内核都会分配一个新页，并复制原始页的内容到新页，做到进程隔离。 如果只标记子进程的 pte 为只读，那么如果父进程先写入，则不会触发 page fault，从而不会分配新页，而在原来的页上修改。而此时子进程的 virtual address 还指向原来的页，内容也被修改了。...

graph TD A[用户进程运行] --> B{时间片到期/系统调用/中断} B --> C[进入内核态 usertrap] C --> D[保存用户寄存器到trapframe] D --> E{需要切换进程?} E -->|是| F[调用yield函数] E -->|否| G[处理完毕返回用户态] F --> H[获取进程锁 p->lock] H --> I[设置进程状态为RUNNABLE] I --> J[调用sched函数] J --> K[检查锁状态和中断状态] K --> L[保存中断状态] L --> M[调用swtch函数进行上下文切换] M --> N[保存当前进程的callee-saved寄存器到p->context] N --> O[恢复调度器的callee-saved寄存器从cpu->context] O --> P[返回到scheduler函数] P --> Q[scheduler循环查找RUNNABLE进程] Q --> R{找到可运行进程?} R -->|否| Q R -->|是| S[设置进程状态为RUNNING] S --> T[再次调用swtch函数] T --> U[保存调度器寄存器到cpu->context] U --> V[恢复新进程寄存器从p->context] V --> W[返回到新进程的内核栈] W --> X[释放进程锁] X --> Y[恢复中断状态] Y --> Z[返回到usertrapret] Z --> AA[恢复用户寄存器从trapframe] AA --> BB[切换到用户页表] BB --> CC[返回用户态继续执行] G --> AA style A fill:#e1f5fe style CC fill:#e8f5e8 style M fill:#fff3e0 style T fill:#fff3e0 style P fill:#f3e5f5 style Q fill:#f3e5f5 重要的数据结构： // 保存内核上下文切换时的寄存器 struct context { uint64 ra; // 返回地址 uint64 sp; // 栈指针 // callee-saved 寄存器 s0-s11 uint64 s0, s1, s2, s3, s4, s5, s6, s7, s8, s9, s10, s11; }; // 每个进程的状态 struct proc { struct spinlock lock; enum procstate state; // 进程状态 struct context context; // 上下文切换时保存的寄存器 struct trapframe *trapframe; // 用户态寄存器保存区 // ....

Q1 RISC-V assembly C 代码： int g(int x) { return x+3; } int f(int x) { return g(x); } void main(void) { printf("%d %d\n", f(8)+1, 13); exit(0); } 生成的汇编代码： 000000000000001c <main>: void main(void) { 1c: 1141 addi sp,sp,-16 // 分配栈空间 1e: e406 sd ra,8(sp) // 保存 main 的返回地址，因为接下来要调用 printf 20: e022 sd s0,0(sp) // 保存前一个函数的 frame pointer 22: 0800 addi s0,sp,16 // 现在 frame pointer 要增加 16Bytes printf("%d %d\n", f(8)+1, 13); 24: 4635 li a2,13 26: 45b1 li a1,12 28: 00000517 auipc a0,0x0 2c: 7a050513 addi a0,a0,1952 # 7c8 <malloc+0xe8> // "%d %d\n"字符串地址 30: 00000097 auipc ra,0x0 // ra=pc=0x30 34: 5f8080e7 jalr 1528(ra) # 628 <printf> // 0x30 + 0x5f8 = 0x628 exit(0); 38: 4501 li a0,0 // exit 的参数，传入 0 3a: 00000097 auipc ra,0x0 3e: 274080e7 jalr 628(ra) # 2ae <exit> 1....

Lecture gdb调试shell write函数的syscall过程： (gdb) b *0xdec # 在0xde8地址设置断点 (gdb) c (gdb) delete 1 # 删除断点 (gdb) print $pc $1 = (void (*)()) 0xdec (gdb) info r (gdb) x/3i 0xde8 # 打印0xdfe开始的三条指令 0xdfe: li a7,16 0xe00: ecall 0xe04: ret (gdb) p/x $stvec $2 = 0x3ffffff000 # user space virtual address顶部一个page，trampoline page对应kernel trap handler. (gdb) stepi warning Book Traps： system call. 通过ecall进入kernel exception. 除0，invalid virtual address. interrupt. 进入kernel device driver. 根据处理代码不同，可分为三种traps： traps from user space traps from kernel space timer interrupts 4....

caller: not preserved across fn call. 需要调用函数来保存寄存器。参考下面例子中的 ra 寄存器值。 callee: preserved across fn call. 被调用函数来保存寄存器。

环境安装 https://pdos.csail.mit.edu/6.828/2023/tools.html $ sudo apt-get update && sudo apt-get upgrade sudo apt-get install git build-essential gdb-multiarch qemu-system-misc gcc-riscv64-linux-gnu binutils-riscv64-linux-gnu 测试环境: $ riscv64-unknown-elf-gcc --version $ qemu-system-riscv64 --version 在 ubuntu22.04 上的输出 log 为: ~ ❯ qemu-system-riscv64 --version QEMU emulator version 6.2.0 (Debian 1:6.2+dfsg-2ubuntu6.24) Copyright (c) 2003-2021 Fabrice Bellard and the QEMU Project developers ~ ❯ riscv64-linux-gnu-gcc --version riscv64-linux-gnu-gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0 Copyright (C) 2021 Free Software Foundation, Inc. This is free software; see the source for copying conditions....

Q1 Speed up system call 这个实验的目的是将用户程序的虚拟地址USYSCALL映射到保存有进程pid的物理地址。 这样不用通过系统调用getpid()的方式，直接通过ugetpid()访问虚拟地址就可以直接得到映射的进程pid。 #define USYSCALL (TRAPFRAME - PGSIZE) // USYSCALL位于虚拟地址顶部Trapframe下面一个page int ugetpid(void) { struct usyscall *u = (struct usyscall *)USYSCALL; // 直接访问虚拟地址 return u->pid; } 在struct proc进程结构体中增加struct usyscall *usyscall, 在分配进程函数allocproc中初始化, 分配p->pid给p->usyscall->pid： if ((p->usyscall = (struct usyscall *)kalloc()) == 0) { freeproc(p); release(&p->lock); return 0; } p->usyscall->pid = p->pid; 在给进程分配页表的函数proc_pagetable()中映射指定的虚拟地址。 注意要加上PTE_U p->pagetable = proc_pagetable(p); pagetable_t proc_pagetable(struct proc *p) { // ... // map the USYSCALL just below trapframe....

3.1 Paging hardware xv6 runs on Sv39 RISC-V, 使用低39位来表示虚拟内存, 高25位没有使用。 39位中27位用作index来寻找PTE(Page table entry), 低12位表示在某个页表中的偏移地址, 正好对应4KB。每个PTE包含44bits的PPN(physical page number)和一些控制位。 实际的RISC-V CPU翻译虚拟地址到物理地址使用了三层。每层page table存储512个PTE，分别使用9个bit来索引。上一层的一个PTE的PPN对应下一层Page table地址。所以总共有512*512*512=2^27 PTE。每个pte占8bytes，所以需要占用的内存最多是2^30=1G， 因为没有访问到的pte是不会分配pagetable的，所以实际占用的内存会更少。 每个CPU需要把顶层的page directory物理地址加载到 satp 寄存器中, 第一个Page Directory的地址是已知的。 然后通过L2索引到第一个Page directory的PTE，读出PTE的PPN, 即第二个Page directory的起始物理地址。再根据L1索引到第二个Page directory的PTE, 以此类推。 只有最后一级pte会设置除了PTE_V以外的其他位，其他层级的pte只设置PTE_V。 3.2 Kernel address space // TODO: replace this image 上图PHYSTOP为0x88000000, 见memlayout.h QEMU模拟RAM从0x80000000物理地址开始，至多到0x80000000+128*1024*1024=0x88000000，xv6称这个地址为PHYSTOP。 Kernel使用RAM和device registers是直接映射的，虚拟地址和物理地址相等。 不过有一部分kernel虚拟地址不是直接映射的： Trampoline page. 在虚拟地址的最顶部。这边有意思的是物理内存中的trampoline code被映射到了两个地方，一个对应直接映射的虚拟内存中的kernel text，另一个是虚拟地址最顶部地址的一个page size。有关Trampoline page请参考第四章。 Kernel stack pages. 每个进程都有自己的kernel stack。如果访问超过了自己的kernel stack。会有guard page保护，guard page的PTE valid位置为0，导致访问异常。 3.3 Code: creating an address space TLB....

2.1 Abstracting physical resources 2.2 User mode, supervisor mode, and system calls 2.3 Kernel Organization monolithic kernel vs microkernel xv6 和 Unix-like OS 属于 monolithic kernel. 2.4 Code: xv6 organization kernel 接口都在 def.h 中声明. 2.5 Process overview 进程的地址空间: RISC-V 64 只使用 64 位地址中的 39 位, 所以用户空间和内核空间各占 2^39 字节. xv6 只使用 39 位地址中的 38 位, 所以最大地址为 2^38 - 1 = 0x3fffffffff, MAXVA 在 riscv.h 中定义. 每个进程都有两个栈, 一个是内核栈, 一个是用户栈. 2.6 Code: starting xv6, the first process and system call bootloader 把 xv6 kernel code 加载到内存 0x80000000 地址, 首先执行的代码为entry....

Trace 实现系统调用int trace(int mask);, 当调用mask中包含的系统调用号，打印出来。 在Makefile中增加trace用户程序的编译 UPROGS=\ ... $U/_trace 在user/user.h中增加函数声明 int trace(int); 在usys.pl中增加user space trace函数的入口。可以看到user space调用的系统调用, 是由这个脚本生成的函数。 以trace为例, 提供了trace函数的入口.global trace, 随后将定义在syscall.h中的SYS_trace编号存入寄存器a7, 通过ecall命令进入内核态。 sub entry { my $name = shift; print ".global $name\n"; print "${name}:\n"; print " li a7, SYS_${name}\n"; print " ecall\n"; print " ret\n"; } entry("trace"); 在syscall.c的syscall函数中通过获取a7寄存器中的编号，找到我们添加的系统调用函数，sys_trace。 函数具体实现如下: // 在proc结构体中增加mask成员 struct proc { //... int mask; } // 将user space传入的mask，传递给当前进程的mask变量 uint64 sys_trace(void) { if(argint(0, &myproc()->mask) < 0) return -1; return 0; } // 随后执行的系统调用number如果 (1 << num == mask), 则打印 syscall(void) { // ....