trap執(zhí)行流程
- write通過執(zhí)行ECALL指令來執(zhí)行系統(tǒng)調(diào)用。ECALL指令會切換到具有supervisor mode的內(nèi)核中。
- 內(nèi)核中執(zhí)行的第一個指令是一個由匯編語言寫的函數(shù),叫做uservec。
- 在這個匯編函數(shù)中,代碼執(zhí)行跳轉(zhuǎn)到了由C語言實現(xiàn)的函數(shù)usertrap中,這個函數(shù)在trap.c中。
- 在usertrap這個C函數(shù)中,我們執(zhí)行了一個叫做syscall的函數(shù)。
- 這個函數(shù)會在一個表單中,根據(jù)傳入的代表系統(tǒng)調(diào)用的數(shù)字進行查找,并在內(nèi)核中執(zhí)行具體實現(xiàn)了系統(tǒng)調(diào)用功能的函數(shù)。對于我們來說,這個函數(shù)就是sys_write。
- sys_write會將要顯示數(shù)據(jù)輸出到console上,當它完成了之后,它會返回給syscall函數(shù),再返回給usertrap函數(shù)
- usertrap()會調(diào)用一個函數(shù)叫做usertrapret,它也位于trap.c中,這個函數(shù)完成了部分方便在C代碼中實現(xiàn)的返回到用戶空間的工作
- 匯編函數(shù)中會調(diào)用機器指令返回到用戶空間,并且恢復ECALL之后的用戶程序的執(zhí)行
ecall 指令
我們是通過ecall走到trampoline page的,而ecall實際上只會改變?nèi)虑椋?br>
第一,ecall將代碼從user mode改到supervisor mode。
第二,ecall將程序計數(shù)器的值保存在了SEPC寄存器。我們可以通過打印程序計數(shù)器看到這里的效果,
第三,ecall會跳轉(zhuǎn)到STVEC寄存器指向的指令。
接下來:
- 我們需要保存32個用戶寄存器的內(nèi)容,這樣當我們想要恢復用戶代碼執(zhí)行時,我們才能恢復這些寄存器的內(nèi)容。
- 因為現(xiàn)在我們還在user page table,我們需要切換到kernel page table。
- 我們需要創(chuàng)建或者找到一個kernel stack,并將Stack Pointer寄存器的內(nèi)容指向那個kernel stack。這樣才能給C代碼提供棧。
- 我們還需要跳轉(zhuǎn)到內(nèi)核中C代碼的某些合理的位置。
uservec函數(shù)
為了能執(zhí)行更新page table的指令,我們需要一些空閑的寄存器,這樣我們才能先將page table的地址存在這些寄存器中,然后再執(zhí)行修改SATP寄存器的指令。
對于保存用戶寄存器,XV6在RISC-V上的實現(xiàn)包括了兩個部分:
第一個部分是,XV6在每個user page table映射了trapframe page,這樣每個進程都有自己的trapframe page。
trapframe page第一個數(shù)據(jù)保存了kernel page table地址,這將會是trap處理代碼將要加載到SATP寄存器的數(shù)值。
第二部分是把trapframe page的地址加載到a0,也就是0x3fffffe000, 這是個常量。原來用戶空間的A0會被寫到sscratch這個寄存器中。所以,下面SD是存儲質(zhì)量,讓每個寄存器被保存在了偏移量+a0的位置。
csrw sscratch, a0
li a0, TRAPFRAME
sd ra, 40(a0)
sd sp, 48(a0)
sd gp, 56(a0)
一直到
csrr t0, sscratch
sd t0, 112(a0)
把用戶態(tài)原來A0寄存器的值,存到p->trapframe->a0中
ld sp, 8(a0)
這條指令正在將a0指向的內(nèi)存地址往后數(shù)的第8個字節(jié)開始的數(shù)據(jù)加載到Stack Pointer寄存器。第8個字節(jié)開始的數(shù)據(jù)是內(nèi)核的Stack Pointer(kernel_sp)。
trapframe中的kernel_sp是由kernel在進入用戶空間之前就設(shè)置好的,它的值是這個進程的kernel stack
ld tp, 32(a0)
XV6會將CPU核的編號也就是hartid保存在tp寄存器, 這個寄存器表明當前運行在多核處理器的哪個核上
# load the address of usertrap(), from p->trapframe->kernel_trap
ld t0, 16(a0)
# fetch the kernel page table address, from p->trapframe->kernel_satp.
ld t1, 0(a0)
# install the kernel page table.
csrw satp, t1
上面3條指令執(zhí)行完成之后,當前程序會從user page table切換到kernel page table。
最后一條指令是jr t0。執(zhí)行了這條指令,我們就要從trampoline跳到內(nèi)核的C代碼中。這條指令的作用是跳轉(zhuǎn)到t0指向的函數(shù)中。
usertrap函數(shù)
// send interrupts and exceptions to kerneltrap(),
// since we're now in the kernel.
w_stvec((uint64)kernelvec);
struct proc *p = myproc();
// save user program counter.
p->trapframe->epc = r_sepc();
- 在內(nèi)核中執(zhí)行任何操作之前,usertrap中先將STVEC指向了kernelvec變量,這是內(nèi)核空間trap處理代碼的位置,而不是用戶空間trap處理代碼的位置。
- 我們通過調(diào)用myproc函數(shù)來得到當前運行的是什么進程 。myproc函數(shù)實際上會查找一個根據(jù)當前CPU核的編號索引的數(shù)組,CPU核的編號是hartid,如果你還記得,我們之前在uservec函數(shù)中將它存在了tp寄存器
- 我們要把SEPC寄存器中的用戶程序計數(shù)器保存到進程的數(shù)據(jù)結(jié)構(gòu)中
接下來我們需要找出我們現(xiàn)在會在usertrap函數(shù)的原因。根據(jù)觸發(fā)trap的原因,RISC-V的SCAUSE寄存器會有不同的數(shù)字。數(shù)字8表明,我們現(xiàn)在在trap代碼中是因為系統(tǒng)調(diào)用.
存儲在SEPC寄存器中的程序計數(shù)器,是用戶程序中觸發(fā)trap的指令的地址。但是當我們恢復用戶程序時,我們希望在下一條指令恢復,也就是ecall之后的一條指令。所以對于系統(tǒng)調(diào)用,我們對于保存的用戶程序計數(shù)器加4,這樣我們會在ecall的下一條指令恢復。
最后會進入usertrapret
usertrapret函數(shù)
它首先關(guān)閉了中斷。我們之前在系統(tǒng)調(diào)用的過程中是打開了中斷的,這里關(guān)閉中斷是因為我們將要更新STVEC寄存器指向用戶空間的trap代碼,而之前在內(nèi)核中的時候,我們指向的是內(nèi)核空間的trap代碼。
設(shè)置了STVEC寄存器指向user trampoline代碼。 之前我們指向內(nèi)核的代碼,現(xiàn)在需要指回USER TRAP代碼。
intr_off();
// send syscalls, interrupts, and exceptions to uservec in trampoline.S
uint64 trampoline_uservec = TRAMPOLINE + (uservec - trampoline);
w_stvec(trampoline_uservec);
下面把kernal要用到的一些變量寫進trapframe。因為當用戶態(tài)再次執(zhí)行ECALL或中斷時,還需要用這里的值去恢復。
p->trapframe->kernel_satp = r_satp(); // kernel page table
p->trapframe->kernel_sp = p->kstack + PGSIZE; // process's kernel stack
p->trapframe->kernel_trap = (uint64)usertrap;
p->trapframe->kernel_hartid = r_tp(); // hartid for cpuid()
接下來我們要設(shè)置SSTATUS寄存器,這是一個控制寄存器。這個寄存器的SPP bit位控制了sret指令的行為,該bit為0表示下次執(zhí)行sret的時候,我們想要返回user mode而不是supervisor mode。這個寄存器的SPIE bit位控制了,在執(zhí)行完sret之后,是否打開中斷。因為我們在返回到用戶空間之后,我們的確希望打開中斷,所以這里將SPIE bit位設(shè)置為1。修改完這些bit位之后,我們會把新的值寫回到SSTATUS寄存器。
unsigned long x = r_sstatus();
x &= ~SSTATUS_SPP; // clear SPP to 0 for user mode
x |= SSTATUS_SPIE; // enable interrupts in user mode
w_sstatus(x);
我們在trampoline代碼的最后執(zhí)行了sret指令。這條指令會將程序計數(shù)器設(shè)置成SEPC寄存器的值,所以現(xiàn)在我們將SEPC寄存器的值設(shè)置成之前保存的用戶程序計數(shù)器的值。
// set S Exception Program Counter to the saved user pc.
w_sepc(p->trapframe->epc);
接下來,我們根據(jù)user page table地址生成相應的SATP值,這樣我們在返回到用戶空間的時候才能完成page table的切換。把它當作函數(shù)的第一參數(shù)傳給一會的匯編。因為只有trampoline中代碼是同時在用戶和內(nèi)核空間中映射。但是我們現(xiàn)在還沒有在trampoline代碼中,我們現(xiàn)在還在一個普通的C函數(shù)中,所以這里我們將page table指針準備好。這個參數(shù)會存在a0寄存器中
// tell trampoline.S the user page table to switch to.
uint64 satp = MAKE_SATP(p->pagetable);
倒數(shù)第二行的作用是計算出我們將要跳轉(zhuǎn)到匯編代碼的地址。我們期望跳轉(zhuǎn)的地址是tampoline中的userret函數(shù),這個函數(shù)包含了所有能將我們帶回到用戶空間的指令。
倒數(shù)第一行,將trampoline_userret指針作為一個函數(shù)指針,執(zhí)行相應的函數(shù)(也就是userret函數(shù))并傳入?yún)?shù),參數(shù)存儲在a0寄存器中, 也就是page table指針。
uint64 trampoline_userret = TRAMPOLINE + (userret - trampoline);
((void (*)(uint64))trampoline_userret)(satp);
userret 函數(shù)
第一件事就是把之前a0存的pagetable指針放到satp寄存器中,隨后把trapframe的地址放進a0;
csrw 用于將一個值寫入到控制和狀態(tài)寄存器(CSR)
li 用于將一個立即數(shù)(即直接編碼在指令中的數(shù)值)加載到一個寄存器中
sfence.vma zero, zero
csrw satp, a0
sfence.vma zero, zero
li a0, TRAPFRAME
下面就是從TRAPFRAME開始恢復之前用戶態(tài)的寄存器的值了.
最后我們把TRAPFRAME里存的函數(shù)返回值a0放進a0寄存器
# restore user a0
ld a0, 112(a0)
# return to user mode and user pc.
# usertrapret() set up sstatus and sepc.
sret
sret是我們在kernel中的最后一條指令,當我執(zhí)行完這條指令:
程序會切換回user mode
SEPC寄存器的數(shù)值會被拷貝到PC寄存器(程序計數(shù)器)
重新打開中斷
利用虛擬內(nèi)存可以做的有趣的事
虛擬內(nèi)存有兩個主要的優(yōu)點
- 隔離性。虛擬內(nèi)存使得操作系統(tǒng)可以為每個應用程序提供屬于它們自己的地址空間。所以一個應用程序不可能有意或者無意的修改另一個應用程序的內(nèi)存數(shù)據(jù)。
- 一層抽象.trampoline page,它使得內(nèi)核可以將一個物理內(nèi)存page映射到多個用戶地址空間中。guard page,它同時在內(nèi)核空間和用戶空間用來保護Stack。
關(guān)鍵思想:在page fault時改變頁表
通過page fault,內(nèi)核可以更新page table,這是一個非常強大的功能.
什么樣的信息對于page fault是必須的?
- 出錯的虛擬內(nèi)存地址,或者是觸發(fā)page fault的源
- 出錯的原因(存在SCAUSE寄存器中)
- 13表示是因為load引起的page fault;
- 15表示是因為store引起的page fault;
-
12表示是因為指令執(zhí)行引起的page fault
image.png
- 引起page fault時的程序計數(shù)器值(tf->epc)
這表明了page fault在用戶空間發(fā)生的位置.因為在page fault handler中我們或許想要修復page table,并重新執(zhí)行對應的指令。理想情況下,修復完page table之后,指令就可以無錯誤的運行了。
Lazy page allocation

在XV6中,sbrk的實現(xiàn)默認是eager allocation。這表示了,一旦調(diào)用了sbrk,內(nèi)核會立即分配應用程序所需要的物理內(nèi)存。設(shè)想自己寫了一個應用程序,讀取了一些輸入然后通過一個矩陣進行一些運算。你需要為最壞的情況做準備,比如說為最大可能的矩陣分配內(nèi)存,但是應用程序可能永遠也用不上這些內(nèi)存.使用虛擬內(nèi)存和page fault handler,我們完全可以用某種更聰明的方法來解決這里的問題,這里就是利用lazy allocation.
sbrk系統(tǒng)調(diào)基本上不做任何事情,唯一需要做的事情就是提升p->sz.之后在某個時間點,應用程序使用到了新申請的那部分內(nèi)存,這時會觸發(fā)page fault,因為我們還沒有將新的內(nèi)存映射到page table。所以,如果我們解析一個大于舊的p->sz,但是又小于新的p->sz(注,也就是舊的p->sz + n)的虛擬地址,我們希望內(nèi)核能夠分配一個內(nèi)存page,并且重新執(zhí)行指令。
Zero Fill On Demand
當你查看一個用戶程序的地址空間時,存在text區(qū)域,data區(qū)域,同時還有一個BSS區(qū)域(注,BSS區(qū)域包含了未被初始化或者初始化為0的全局或者靜態(tài)變量)。當編譯器在生成二進制文件時,編譯器會填入這三個區(qū)域。text區(qū)域是程序的指令,data區(qū)域存放的是初始化了的全局變量,BSS包含了未被初始化或者初始化為0的全局變量。
我只需要分配一個page,這個page的內(nèi)容全是0。然后將所有虛擬地址空間的全0的page都map到這一個物理page上。這樣至少在程序啟動的時候能節(jié)省大量的物理內(nèi)存分配。
在寫入時復制頁面,并在應用地址空間中映射它為讀/寫

Copy On Write Fork
xv6 fork從父進程復制所有頁面(參見fork());但fork經(jīng)常緊接著執(zhí)行exec, 就會直接丟棄那些復制了的頁面.
解決方案是在父子進程之間共享地址空間,修改標志位為只讀.

要寫的時候,復制出來一份,2邊都改成讀寫.

使用PTEs中額外可用的系統(tǒng)位(RSW)
當內(nèi)核在管理這些page table時,對于copy-on-write相關(guān)的page,內(nèi)核可以設(shè)置相應的bit位,這樣當發(fā)生page fault時,我們可以發(fā)現(xiàn)如果copy-on-write bit位設(shè)置了,我們就可以執(zhí)行相應的操作了。
需要對物理頁面進行引用計數(shù)
父進程退出時我們需要更加的小心,因為我們要判斷是否能立即釋放相應的物理page。如果有子進程還在使用這些物理page,就不能釋放.
困難重重: https://lwn.net/Articles/849638/
Demand Paging
程序的二進制文件可能非常的巨大,將它全部從磁盤加載到內(nèi)存中將會是一個代價很高的操作。又或者data區(qū)域的大小遠大于常見的場景所需要的大小,我們并不一定需要將整個二進制都加載到內(nèi)存中。
按需從文件中加載頁面
- 分配 page table entries,但將它們標記為on-demand
- 在錯誤時,從文件中讀入page并更新pagetable
- 需要保留一些元信息,說明頁面在磁盤上的位置
- 這些信息通常在稱為virtual memory area(VMA)的結(jié)構(gòu)中
- 如果文件大過物理內(nèi)存, 把最遠使用過的page置換進磁盤. the A(cess) bit 在PTE 幫助 kernel 實現(xiàn) LRU.
Memory Mapped Files
將完整或者部分文件加載到內(nèi)存中,這樣就可以通過內(nèi)存地址相關(guān)的load或者store指令來操縱文件.
為了支持這個功能,一個現(xiàn)代的操作系統(tǒng)會提供一個叫做mmap的系統(tǒng)調(diào)用。
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
下面開始講解這次的LAB
Alarm
test 0的核心就是修改EPC.
EPC(Exception Program Counter)寄存器扮演著重要的角色,特別是在異常處理和中斷處理中。EPC存儲了發(fā)生異?;蛑袛鄷r程序的地址,這允許處理器在處理完異常或中斷后返回到正確的位置繼續(xù)執(zhí)行程序。
p->trapframe->epc = (uint64)p->alarmhandler;
test1/2/3
what registers do you need to save and restore to resume the interrupted code correctly?
因為我們要再次回到最開始用戶態(tài)執(zhí)行的地方.中間我們跳到了用戶態(tài)alarmhandler的地方.這里面的代碼執(zhí)行,會修改掉用戶態(tài)的寄存器的值.所以我們需要把之前用戶態(tài)的寄存器都要存下來.
*p->alarmtrapframe = *p->trapframe;
Prevent re-entrant calls to the handler
增加一個isalarming的狀態(tài),如果是true,就不做跳轉(zhuǎn)
if (p->tickspassed >= p->alarminterval && !p->isalarming) {
....
}
Make sure to restore a0. sigreturn is a system call, and its return value is stored in a0
把之前在用戶態(tài)保存下來的實際返回值,當作sys_sigreturn的返回值,就可以達到這個效果.
uint64
sys_sigreturn(void)
{
struct proc *p = myproc();
p->isalarming = 0;
*p->trapframe = *p->alarmtrapframe;
return p->trapframe->a0;
}
Print the names of the functions and line numbers in backtrace() instead of numerical addresses
核心思路: 首先修改make文件, 結(jié)合生成的asm文件提取所有命令的內(nèi)存地址,然后調(diào)用addr2line 獲得方法名 和 行號. 寫進一個文件,并且讓文件系統(tǒng)映射這個文件進xv6. 隨后在內(nèi)核啟動的時候, 讀取文件內(nèi)容, 把地址和對應的方法名和行號,存進2個數(shù)組.
當調(diào)用backtrace() 函數(shù)的時候,可以用地址,在數(shù)組里做2分查找,找到對應的方法名和信息,就可以實現(xiàn)這個功能.

生成出來的文件大概長這樣:

隨后就是讀取文件, 加載進數(shù)組. 我新建了一個debugtbl.c
這里用了一個緩存讀文件的技巧,來減少readi的調(diào)用次數(shù). 我是1次讀了一個PGSIZE. 如果cache里還有行,就直接從cache里讀出下一行.
2分查找的代碼,是找到最大的小于等于當前輸入地址的那個索引,隨后去debugtbl_info 讀取方法名和行號.
#include "types.h"
#include "riscv.h"
#include "defs.h"
#include "param.h"
#include "stat.h"
#include "spinlock.h"
#include "proc.h"
#include "sleeplock.h"
#include "fs.h"
#include "buf.h"
#include "file.h"
#define MAX_LINE_LENGTH 96
#define MAX_ROW_LENGTH 4096
uint debugtbl_addr[MAX_ROW_LENGTH];
char debugtbl_info[MAX_ROW_LENGTH][MAX_LINE_LENGTH];
int debugtbl_row = 0;
char cache[PGSIZE];
int cache_idx = 0;
int cache_cnt = 0;
int readline(struct inode *ip, uint *off, char *buf) {
int i = 0, n;
while (i < MAX_LINE_LENGTH) {
while (i < MAX_LINE_LENGTH && cache_cnt > cache_idx) {
buf[i] = cache[cache_idx++];
if (buf[i] == '\n') {
buf[i] = 0;
return i;
}
i++;
}
if (i == MAX_LINE_LENGTH) {
panic("line char overflow");
return -1;
}
n = readi(ip, 0, (uint64)cache, *off, PGSIZE);
if (n <= 0) break; // Error or end of file
*off += n;
cache_cnt = n;
cache_idx = 0;
}
return i; // Return the length of the line
}
int readfile(struct inode *ip) {
uint off = 0; // Offset in the file
int n;
char buf[MAX_LINE_LENGTH];
while ((n = readline(ip, &off, buf)) > 0) {
uint addr = 0;
if (n < 8) {
panic("debugtbl format error");
}
for(int i = 0; i < 8; i++) {
char c = buf[i];
if (c >= '0' && c <= '9') c = c - '0';
else if (c >= 'a' && c <= 'f') c = c - 'a' + 10;
else panic("invalid address content");
addr = (addr << 4) | c;
}
debugtbl_addr[debugtbl_row] = addr;
memmove(debugtbl_info[debugtbl_row++], buf + 9, n);
}
return n < 0 ? -1 : 0;
}
int initdebugtbl(){
struct inode *ip;
begin_op();
if((ip = namei("/debugtbl")) == 0){
end_op();
return -1;
}
ilock(ip);
if (readfile(ip) < 0)
goto bad;
iunlockput(ip);
end_op();
ip = 0;
return 0;
bad:
if(ip){
iunlockput(ip);
end_op();
}
return -1;
}
int get_debuginfo(uint64 address) {
uint left = 0;
uint right = debugtbl_row - 1;
while(left <= right){
int mid = (left + right) >> 1;
if(address < debugtbl_addr[mid]){
right = mid - 1;
}else{
left = mid + 1;
}
}
return left - 1;
}
void backtrace()
{
int idx;
printf("backtrace:\n");
uint64 fp = r_fp(); // get the frame pointer value
for (uint64 i = fp; PGROUNDDOWN(fp) == PGROUNDDOWN(i); i = *(uint64*)(i - 16)) {
uint64 addr = *(uint64*)(i - 8);
if ((idx = get_debuginfo(addr)) < 0)
printf("%p\n", addr);
else
printf("%p %s\n", addr, debugtbl_info[idx]);
}
}
這里關(guān)于initdebugtbl 什么時候去調(diào)用,我做了一些DEBUG. 一開始我是打算放在main.c中各種初始化時.但是發(fā)現(xiàn)始終不能work,根本原因時那時還沒有進程的結(jié)構(gòu)體維護在cpu, 第一個進程是在初始化完后,在scheduler()方法里 要去執(zhí)行userinit被創(chuàng)建出來. 這里會切到用戶態(tài),然后調(diào)用exec的系統(tǒng)調(diào)用,去執(zhí)行userinit命令.
那么我們可以在內(nèi)核態(tài)的exec處,判斷當前proc->pid是不是為1 (第一個進程), 是的話,就initdebugtbl; 來在內(nèi)核態(tài)完成初始化debug table的工作.
隨后exec userinit 后,創(chuàng)建出來的shell進程, pid為2了.

測試效果

