Process

一个process本质上就是一段代码加一段数据。

对于process最重要的三个是 page table, kernel stack, run state，
其他两个都好理解，这个kernel stack是process enters kernel（system call or interrupt)的时候，kernel code就在这个stack里面运行，
这个stack user process是无法访问的。

pagetable

地址映射

系统将地址分成了一个一个page大小，一个page大小是2的12次方，也就是4096 bytes
page table是一个柜子，每个柜子512个抽屉，每个抽屉最大空间64bit 也就是8个byte.
也就是一个page table其实也是一个page的大小

在这个系统中，一个process拥有一个page table.也就是它可以拥有512*4096 bytes（2G）大小的虚拟空间

虚拟地址转物理地址

做个比喻

每一个pagetable就像一个有着512个抽屉的柜子，第一个柜子就是root pagetable

每个抽屉的编号就是PTE，盒子里有两张纸条，一张写的是下一个柜子地址编号(ppn)，一张写的是当前这个抽屉的权限，例如这个柜子里面的纸条是否有效，哪些应用能打开看等等(flag)。
有个叫做”satp”的寄存器存了第一个root柜子的地址

整个地址转换流程

你会拿着四张纸条，第一张是一个二进制9bit数，首先根据satp的寄存器地址找到到底是哪个柜子
然后呢根据第一个9bit数算一下是第几个抽屉，例如0x03是第三个抽屉，打开第三个抽屉，看看flag纸条这个抽屉是否
有效，有效的话呢，拿出ppn纸条，找下一个柜子在哪。一直找到第三个柜子。

当我们找到第三个柜子的时候，拿到ppn纸条，和最开始拿到的四张纸条的最后一张拼一起
就是一个真正的物理地址

walk

这是pagetable里面最重要的函数。

它的核心本质上就是走了一遍上面的地址转换，先给你四张纸，你拿四张纸，一个一个去找。
如果没找到就创建一个新的page

mappages

这是pagetable里第二重要的函数

它调用walk将va的地址存进walk返回的PTE里面，也就是你手上有一个物理地址，有一个虚拟地址。
简单比喻就是：你首先用walk函数将va转换，最后返回第三个柜子的一个抽屉，然后你将物理地址放进去

A kernel page table per process(HARD)

背景

Kernel的虚拟地址和物理地址一一对应，也就是Kernel是整块映射的。但是每一个process只有page table，
用于映射user space，如果process调用了System Call，传递了一个user address过去，问题是这个address只有
user page table可以翻译，所以要user page table先翻译成物理地址才可以

做法

  1. 每一个user process多保存一个kernel_pagetable
  2. allocproc会给每一个process分配空间，在这里面帮kernel_pagetable分配空间
  3. kvminit调用了mappages将kernel的虚拟和物理一一对应
  4. procinit专门用来给一个一个的kernel stack初始化，这里初始化就是个地址
  5. 这样做和之前的区别是什么？不用进入supervisor mode?
    原因可能因为:”Each process has two stacks: a user stack and a kernel stack (p->kstack). When the process is
    executing user instructions, only its user stack is in use, and its kernel stack is empty,When the
    process enters the kernel (for a system call or interrupt), the kernel code executes on the process’s
    kernel stack; while a process is in the kernel, its user stack still contains saved data, but isn’t actively used.”
    也就是说kernel stack和user stack不能同时使用
  6. 整个核心流程就是每个proc保存多一个kernel_pagetable.但是这个page table用于存什么东西呢？
  7. 每一个process的kernel_pagetable要和global的一样，那么是怎么copy的呢？好像只需要copy root table就行了。用什么copy呢？memmove?
    在哪copy呢？scheduler()?
  8. process的kernel_pagetable要留一分map给p->kstack，这个kstack在procinit已经赋值成VA了，那么如果要再映射一次，用walkaddr拿到pa,提供一个新VA然后用mappages
    建立新映射? 这一步失败了，因为walkaddr只能用于拿user space的。

惊天大BUG!!!!!!!!

我写的时候一直出现 panic(‘remap’),重新梳理了好多次，陷入深深自我怀疑。
拖了半天终于对比他人做法发现我是：

script
1
mappages(kpt, UART0, UART0, PGSIZE, PTE_R | PTE_W);

而mappages的参数是

script
1
mappages(pagetable, va, sz, pa, perm)

我参数都摆错顺序了呀！！！！！！！！！！！ 什么低级错误缠了了我这么久！！！！！！

函数使用错误

我尝试用kalloc()为proc->kernel_pagetable开辟空间，uvmcreate其实也是调用这个函数为UserSpace开辟空间，但是它有memset()，这一步漏掉可不行

理解错误

  1. each per-process kernel page table should be identical to the existing global kernel page table

我一直想的是，user_kernel_table 和 kernel_table 是不是需要用memcpy拷贝，这是因为我对walk并没有真的理解，虽然我将它用非递归的方式重写了，
当我为user_kernel_table 写了kvminit2并调用，这时候后,user_kernel_table和kernel_table都存了一样的信息，因为我用的是一样的va去存储pa

  1. Make sure that each process’s kernel page table has a mapping for that process’s kernel stack

has a mapping，意思就是将kernel stack记在user_kernel_table上，我之前就有一个问题，在procinit里面，每个process的kernel stack
记在kernel_page上，lab要我全部拷贝到allocproc，并且给user_kernel_table记，那么还需不需要给kernel_page记了。实际上不需要了，
因为调用kernel stack时，都是用的process自己的user_kernel_table

  1. You’ll need a way to free a page table without also freeing the leaf physical memory pages

leaf physical memory pages, 不是指第三个page table,而是指第三个page指向的physical page!!!
每个user kernel page table本质上指向的是同一个地址，你肯定不能free掉啊！

非常重要：kfree和kalloc都是以一个page为最小单位，而且是对齐的，也就是随便拿一个PTE，里面的地址被释放，这个地址所在的整个page都会被释放
所以根本不需要va的最后offset，walk返回的pte通过pte2pa拿到的就是那一块page的开头地址

在xv6里面，先用uvmunmap,调用walk找到所有的mapping释放掉，然后再调用freewalk释放掉所有的pagetable

复盘

9/1完成speedup开始做2020的per process kernel page，每个星期算两个小时，也做了近十个小时了。
实际操作中，我被很多Debug卡住了，例如我尝试写kvminit，用mappages的时候，没看到和kvmmap的参数的顺序有差别，再比方说，我全部写完后，
一直有kvmap的panic错误，但是我只是去检查我自己的代码，其实这时需要改动kvmap那里，将kernel_pagetable改为user_kernel_pagetable就行了

为什么我会遇到这种坎坷呢，核心还是我没有完全的熟透这个pagetable的每一个细节，具体行动上，我并没有严格按照Lab的instruction 将要求的vm.c全部代码看一遍，
过一遍，其实如果我将每个代码重新写一下，就像写walk()函数一样，后面就会清晰很多，而不是遇到问题又重新去看。

遇到问题再查资料也可以，但问题是，会更痛苦，更曲折，如果已经有instruction，是可以尝试follow一下的。

很多时候，book里面也已经给了所有信息，例如我遇到的问题书上其实已经说了“Functions starting with kvm manipulate
the kernel page table; functions starting with uvm manipulate a user page table”。 但是当时看的时候并没当回事，所以也不用妄自菲薄，
学而时习之，过了一遍再来复习，肯定又有完全不一样的理解。

Simplify (HARD)

背景

上一个task已经创建了一个user kernel page table,但是依旧没有能够做到调用kernel直接dereference user pointers，因为这时user_kernel_page_table
只存了kernel的map，还有user data的map没做

task已经提供了copyin_new，这里去掉了将va转为pa，然后再memmove，直接从src(va)拷贝到dest(pa)，

以下为错误理解！！！
等于说src(va)这里就是真正的物理地址。user_data和kernel一样都是va=pa，map在user_kernel_pgtb上

所有的user_data都存在了user page table里面，那么要”add user mappings to process’s kernel page table” 应该要遍历user_page_table
拿到所有的物理地址，并且映射到user_kernel_page_table(va=pa)
于是函数逻辑就是：先遍历user page table,拿到了物理地址，然后将物理地址和一样数值的va一对一map在user kernel page table

！！！以上为错误理解

解析

参考了其他人的解法，发现是将user_page_table从0到proc->sz全部遍历一边，取出里面的pa，映射到user_kernel_pgtb.
copyin_new()后，kernel拿到的是user_kernel_pgtb可以解析的虚拟地址。之前拿到的是copyin用walk解析后的实际地址。

我最大的疑问是，kernel是什么做dereference呢，walk()？

是paging hardware做的解析，你只要提供pagetable它就能解析，有一句很重要的话没看到：walk mimics the RISC-V paging hardware
walk只是用来模拟page hardware的

但依旧有个疑问,kernel在什么情况下做的

读到一句话：copyout and copyin copy data to and from user virtual addresses provided as
system call arguments; they are in vm.c because they need to explicitly translate those addresses
in order to find the corresponding physical memory
也就是copyin的explicitly translate是不应该的，也只要satp握着的pgtb含有这个va，它就会自动转换

参考下面这一段
Early in the boot sequence, main calls kvminit (kernel/vm.c:22) to create the kernel’s page
table. This call occurs before xv6 has enabled paging on the RISC-V, so addresses refer directly to
physical memory

对于user page table来说，它的虚拟地址是连续的

uvmalloc代码揭示了，每一次growproc，都是从oldsz -> newsz, 地址是连续的

Detecting which pages have been accessed (HARD)

几个问题：

  1. 怎么从Manual里选到底用哪个数值作为PTE_A?
    这里在riscv-privileged里面有图表

  2. 在哪里设置PTE_A?
    Risc-V自己设置的 Each leaf PTE contains an accessed (A) and dirty (D) bit. The A bit indicates the virtual page has
    been read, written, or fetched from since the last time the A bit was cleared. The D bit indicates
    the virtual page has been written since the last time the D bit was cleared

Trap

只有三种情况会触发Trap

  1. System call, user executes the ecall
  2. Exception
  3. Device interrupt

Trap的特点

  1. transparent
  2. Three distinct case trap: user space / kernel space /timer interrupt

Trap 流程

  1. hardware action by cpu, Vector Assembly
  2. C Trap handler
  3. system call & driver

Kernel will do instead of CPU

  1. switch to kernel page table
  2. switch to a stack in the kernel
  3. save register

寄存器说明

这些寄存器只能在supervisor mode读取和存储

  • stvec: Trap handler的地址
  • sepc: 存PC指针的地方，trap完后，调用sret重新将spec写入pc
  • scause: 存放为什么调用trap
  • sscratch: ?
  • sstatus: SIE为1才会允许device interrupts, SSP用于指明trap来自哪个Mode
  • stval: 存储无法被translate的地址

Trap from user space流程(with register)

  1. 如果是device interrupt 且 sstatus的SIE未set，Stop
  2. 清掉SIE bit
  3. copy pc sepc 存储pc指针
  4. 存储当前mode在sstatus
  5. set scause number
  6. 换到supervisor mode
  7. pc = stvec
  8. 开始执行

Trap from user space流程（with code)

  1. trampoline.S/uservec
    汇编，stvec指向处，这个user trap和kernel trap都会用到，但是RISC-V的机制不会改satp从user_pgtb到kernel_pgtb
    所以uservec需要同时map同一地址的user_pgtb和kernel_pgtb
    开头这段代码会将寄存器存在trampframe这片地址（每一个user_pgtb都存了，在地址TRAPEFRAME）
    然后从tramframe的最前面提取存好的kernel_pgtb等数据进入下一个函数

  2. trap.c/usertrap
    首先就将stvec换成kernelvec，也就是这个trap可以继续被打断？
    判断是哪种trap System Call / Devices / execption
    其中exception会杀掉错误process

  3. trap.c/usertrapret
    这个就是重新恢复环境，stvec恢复uservec，sepc恢复到pc等等，然后userret回去，这里注意userret会switch page table

  4. trampoline.S/userret
    和uservec对比完全反过来，上一层调用的时候传入两个参数分别是Trapframe和pagetable

Trap from kernel流程（with code)

  1. kernelvec.S
    存一些寄存器之类的

  2. trap.c/kerneltrap
    如果是device就call devintr,如果是exeption就直接panic
    如果是timer interrupt，就call yield让CPU

System Call(with Code)

前面的lab已经添加过system call了，现在来真实了解一下system call怎么调用的

  1. kernel/syscall.c
    有一个数组，存储各个syscall地址,从a7寄存器取offset，然后直接调用了对应的sys_function.
    然后将返回值放在p->trapframe->a0

stvec 是什么寄存器，为什么很重要？

The kernel writes the address of its trap handler here; the RISC-V jumps here to
handle a trap。只要进入trap，就会调用这个地址的函数。
如果不这么做，那么Then a trap could switch to supervisor mode while still running user instructions

trapline是什么,trapframe又是什么

trampline是一段汇编代码，里面用于将硬件的Trap信号导到C代码上，trampoline这个page在每个pagetable都有，而且都是同样的virtual address
方便切换时好继续执行
trapframe是一段内存空间，process拥有的，用于在Trap的时候存寄存器等值
这些东西的产生，核心是因为user_page里面没有kernel memory，如果用Simplify (HARD)的方法，就可以去掉这些东西，并且更高效

COW(copy on write)

Fork后child不会复制parent的PA，而是指向它，到真的要用的时候，才通过page fault触发并创建新的page,
为了区分COW和非法访问，PTE里面存了一个bit用来区分。同时要有一个ref count,这个存在内存里，用来说明此page是否没人引用了。

lazy allocation

sbrk()用于开辟内存，而且是eager allocation,但是呢：applications often ask for more memory than they need
所以真实情况是，最开始并不给application真实的空间，等真的开始访问对应地址的时候，会触发page fault trap，这时kernel才帮忙创建并分配
page table地址

zero fill on demand

全局变量都置为0，这些变量其实都指向了同一个pa,然后都只有只读权限，当尝试写的时候，会触发page fault并且开新空间

Demand paging

这个是在Exec的时候，做lazy allocation

Lab Trap : Backtrace(moderate)

问题1：offset(-8)，这个负八单位是多少？1Byte? 1bit? 4Byte?
这里是一个Byte，系统都是一个Byte一个Byte的操作。

问题2：怎么判断什么时候停止往回回溯backtrace?
每个kernel stack都是一页,所以拿到第一个framepointer的地址，然后通过PGROUNDDOWN和UP分别拿到栈头和栈尾，通过判断地址是否是在这个page下就可知道什么时候停下了。