# 「[MIT6.S081](https://pdos.csail.mit.edu/6.S081/2020/index.html)」 筆記
# 參考資料
## [MIT 6.S081 Lecture Notes](https://fanxiao.tech/posts/2021-03-02-mit-6s081-notes/#24-starting-the-first-process)
內容大致從上面這篇筆記來的，他已經寫得蠻完整的了，我只是簡略統整一下，再補一些view code的過程，順便以防被支語入侵用繁體中文寫了這篇筆記
## [xv6-book](https://pdos.csail.mit.edu/6.1810/2022/xv6/book-riscv-rev3.pdf)
這是最原始的參考資料，這個課程的指定用書
# Operating System Interfaces (2024/06/25)
## 常用syscall
- `int fork()`
建立一個子進程，從fork()的那一行開始執行，在父進程中回傳子進程的pid，在子進程中回傳0
- `int exit(int)`
輸入一個狀態碼，退出這個進程，0代表沒問題，1代表有問題
- `int wait(int*)`
等待子進程的退出，如果沒有子進程就回傳-1，輸入一個int指標，子進程退出的狀態會存在裡面
- `exec(char*, char *argv[])`
執行檔案
```cpp
int pid = fork();
if(pid == 0){
printf("child");
exit(0); // 退出子進程
}else{
printf("parent");
wait(0); // 等待子進程退出
printf("Done")
}
```
以下分別分析父子進程的行為：
- 父進程
fork()是子進程的pid，所以會進入下面輸出parent，並且等待子進程退出。
- 子進程
fork()是0，所以會進入上面輸出child，並且正常退出。
xv6執行shell指令主要是掀開一個子進程，在裡面去parsecmd()和runcmd()，唯一的例外是cd，因為它必須要改變執行shell的那個資料夾位置，所以它會在父進程裡去執行。
## 讀檔案的方式
開啟檔案的時候，kernel會分配給它一個file descripter，通常越早開啟的他的file descripter就越小，其中，通常0是標準輸入，1是標準輸出。
```cpp
int fd = open("001.txt", O_RDWR); //fd是file descripter
close(fd); //關閉這個文件描述符
```
然後我們可以用read()和write()去對fd做讀寫。
```cpp
char buf[100];
read(fd, buf, 10); //從fd指向的檔案向buf讀10個bytes
write(fd, buf, 10); //從buf向fd指向的檔案寫10個bytes
```
我們可以用`int dup(int fd)`去分配一個新的file descripter去指向一個相同的檔案
```cpp
int newfd = dup(int fd); //分配一個新的file descripter去指向fd指向的那個檔案
```
他有個應用，就是因為file descripter的分配是從最小的開始分配，所以如果我們把標準輸入或標準輸出close掉，再dup一個fd，那麼就可以讓標準輸入或標準輸出指向那個file descripter指向的檔案，這在待會的輸入輸出重導向裡會用到
## pipes
有個長度為2的陣列p[2]，pipe會分配給這個陣列兩個file descripter，p[0]代表讀端p[1]代表寫端，我們可以對p[1]寫東西，再從p[0]讀出來，以實現兩個進程中的互相溝通。
以下以從導向為例子，看一下xv6怎麼實現重導向的：
```cpp
int p[2];
pcmd = (struct pipecmd*)cmd;
if(pipe(p) < 0)
panic("pipe");
if(fork() == 0){
// in child process
close(1); // close stdout
dup(p[1]); // make the fd 1 as the write end of pipe
close(p[0]);
close(p[1]);
runcmd(pcmd->left); // run command in the left side of pipe |, output redirected to the write end of pipe
}
if(fork() == 0){
// in child process
close(0); // close stdin
dup(p[0]); // make the fd 0 as the read end of pipe
close(p[0]);
close(p[1]);
runcmd(pcmd->right); // run command in the right side of pipe |, input redirected to the read end of pipe
}
close(p[0]);
close(p[1]);
wait(0); // wait for child process to finish
wait(0); // wait for child process to finish
break;
```
他首先建立了一個子進程，這個進程拿來讓1指向p的寫端，然後把p[0]和p[1]都關掉。這裡只是把這兩個文件描述符關掉，不是把這個文件關掉，而因為1還指向p的寫端，所以對1寫東西還是會進入pipe裡面。然後在讀端也做一樣的事情。最後，父進程把他的p關掉，等待子進程結束就可以結束了。
:::warning
:warning: 注意
- 把沒用到的p[0]和p[1]關掉是至關重要的，尤其是要讀之前要把所有指向寫端的文件描述符關掉，因為如果pipe的寫端傳過去的東西是空的而且它沒有被關掉的話，那麼讀端會無從判斷是否對方式沒有要傳東西而一直卡在read()的狀態。
- 父進程和子進程中p是要分別關掉的，因為雖然指向同個檔案，但文件描述符沒有共用
:::
## Lab 1 Unix Utilities
過了那麼久，終於到lab的部份了，這份lab其實挺簡單，就是讀文件讀比較久
lab的部份主要是在user.h中提供了許多的syscall，然後我要用他們來實現一些功能
### sleep
就輸入一個數字，然後sleep一下
```cpp
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
int main(int argc, char* argv[]){
if(argc != 2){
fprintf(2, "sleep: argument error");
exit(1);;
}
int t = atoi(argv[1]);
if(sleep(t) != 0){
fprintf(2, "sleep: execution error");
}
exit(0);
}
```
### pingpong
父進程向子進程傳一個東西，然後子進程收到的時候說一下，再傳個東西給父進程，收到也說一下，然後分用getpid()回報一下自己的pid
```cpp
#include<kernel/types.h>
#include<kernel/stat.h>
#include<user/user.h>
int main(int argc, char* argv[]){
if(argc != 1){
fprintf(2, "error");
exit(1);
}
int p[2];
pipe(p);
if(fork() == 0){
char buf[1];
read(p[0], buf, 1);
close(p[0]);
fprintf(1, "%d: received ping\n", getpid());
write(p[1], buf, 1);
close(p[1]);
}else{
char buf[1];
buf[0] = 'a';
write(p[1], buf, 1);
close(p[1]);
read(p[0], buf, 1);
close(p[0]);
fprintf(1, "%d: received pong\n", getpid());
}
exit(0);
}
```
### primes
用pipe去實現一個質數篩法，父進程把2到35的數字送進去，對於每個進程，它接到的最小數字一定是質數。然後它再把其他數過篩後傳往下一個進程，一直作到pipe不傳東西就結束
```cpp
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
void next_stage(int* pl){
int prime;
close(pl[1]);
int stat = read(pl[0], &prime, sizeof(int));
if(stat == 0){
exit(0);
}
fprintf(1, "prime %d\n", prime);
int p[2];
pipe(p);
if(fork() == 0){
close(pl[0]);
next_stage(p);
}else{
close(p[0]);
int num;
while(read(pl[0], &num, sizeof(int)) != 0){
if(num % prime != 0){
write(p[1], &num, sizeof(int));
}
}
close(pl[0]);
close(p[1]);
wait(0);
}
exit(0);
}
int main(){
int p[2];
pipe(p);
if(fork() == 0){
next_stage(p);
}else{
for(int i = 2; i <= 35; i++){
close(p[0]);
write(p[1], &i, sizeof(int));
}
close(p[1]);
wait(0);
}
// wait(0);
exit(0);
}
```
### find
去遞迴的遊歷整個資料夾，看裡面有沒有某個檔案
```cpp
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"
void find(char *path, char* pattern){
int fd;
char buf[512], *p;
struct dirent de;
struct stat st;
if((fd = open(path, 0)) < 0){
fprintf(2, "find: cannot open %s\n", path);
return;
}
if(fstat(fd, &st) < 0){
fprintf(2, "find: cannot stat %s\n", path);
return;
}
if(st.type != T_DIR){
fprintf(2, "find: %s is not a directory\n", path);
return;
}
if(strlen(path) + 1 + DIRSIZ + 1 > sizeof(buf)){
return;
}
while(read(fd, &de, sizeof(de)) == sizeof(de)){
if(de.inum == 0){
continue;
}
strcpy(buf, path);
p = buf+strlen(buf);
*p++ = '/';
strcpy(p, de.name);
if(!strcmp(de.name, ".") || !strcmp(de.name, "..")){
continue;
}
if(stat(buf, &st) < 0){
continue;
}
if(!strcmp(de.name, pattern)){
fprintf(1, "%s\n", buf);
}
if(st.type == T_DIR){
find(buf, pattern);
}
}
}
int main(int argc, char* argv[]){
if(argc != 3){
fprintf(2, "find: argument number error\n");
exit(1);
}
find(argv[1], argv[2]);
return 0;
}
```
### xargs
pipe會把東西送到stdin裡面，xargs會把他們讀進來，送進後面的command去執行。要做的就是把輸進來的東西以換行分隔，在以空格分割參數，開一個子進程去執行它。這個我自己卡的地方是忘記exec()的argv要把command也塞進去。
```cpp
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/param.h"
int main(int argc, char *argv[]){
char buf;
if(argc < 2){
fprintf(2, "xargs: too few args");
exit(1);
}
while(1){
char* command = argv[1];
char args[MAXARG][100];
int cnti = 0;
int cntj = 0;
for(int i = 1; i < argc; i++){
strcpy(args[cnti++], argv[i]);
}
int res;
int b = 0;
while((res = read(0, &buf, 1)) > 0 && buf != '\n'){
if(buf == ' ' && b == 1){
args[cnti][cntj] = 0;
cntj = 0;
cnti++;
b = 0;
continue;
}
b = 1;
args[cnti][cntj++] = buf;
}
if(res <= 0)
break;
args[cnti][cntj] = 0;
cnti++;
char* input[MAXARG];
for(int i = 0; i < cnti; i++){
input[i] = args[i];
}
input[cnti] = 0;
if(fork() == 0){
exec(command, input);
exit(0);
}
wait(0);
}
exit(0);
}
```
# Operating System Organization(2024/06/26)
## C 語言中 RAM 的分配
- heap
可以透過malloc()和free()使用或釋放，記憶體位置從低到高
- stack
存區域變數或函數參數的地方，執行完會自動銷毀，記憶體位置從高到低
- static
全域的變數
## User mode 和 Supervisor mode
RISC-V CPU上有三個模式: machine mode, supervisor mode, user mode
- machine mode
權限最高，只有啟動cpu的時候會用到
- supervisior mode
權限次高，可以直接對暫存器進行讀寫、執行syscall，執行在其中的稱作kernel space
- user mode
權限最低，執行util function
## Kernel organization
由此可以將kernel分為兩種：
- monolithic kernel
所有syscall都在supervisior mode中執行
- micro kernel
將在supervisior mode中執行的程式降到最少，以增加安全性
## Process
作業系統想實現進程間的隔離，也就是進程間不能互相破壞或監聽，也不能破壞kernel。所以xv6提供給每個進程一個address space，讓他們以為自己是一台機器。
## Starting the first process in xv6
- 執行`bootloader`
執行儲存在ROM中的`kernel.ld`，把xv6 kernel載入到暫存記憶體裡面，位置從0x80000000開始，因為前面有一些I\O裝置。
- 執行`start.c`
`_entry`中設定了一個初始的`stack0`來執行`kernel/start.c`，到這裡都還是在machine mode裡面執行。然後`start`用RISC-V提供的指令`mret`切換到supervisor mode，開始執行main。
- 執行`main.c`
呼叫`kernel/proc.c`中的`userinit`來建立第一個使用者進程。
- 執行`userinit()`
他會執行`initcode.S`，在裡面呼叫`exec`來執行`init`
- 執行`init`
他會把console的標準輸入輸出和錯誤用0,1,2開啟，然後開啟一個shell，就開機了
## Lab 2 System Calls
### Using gdb
它叫我用gdb去看它開機的時候呼叫的那個syscall
```shell
(gdb)layout src #用原始碼呈現
(gdb)layout split #用原始碼加組合語言
```
```cpp
void syscall(void)
{
int num;
struct proc *p = myproc();
num = p->trapframe->a7;
if(num > 0 && num < NELEM(syscalls) && syscalls[num]) {
// Use num to lookup the system call function for num, call it,
// and store its return value in p->trapframe->a0
p->trapframe->a0 = syscalls[num]();
} else {
printf("%d %s: unknown sys call %d\n",
p->pid, p->name, num);
p->trapframe->a0 = -1;
}
}
```
其中，我們可以去觀察那個num的值：
可以發現a7是0x7，然後它會去那個syscall table去找到第7個syscall，也就是`exec`，它這個時候應該是被拿來呼叫`user/init`
### trace
他給我了一個`user/trace.c`叫我把那個syscall寫出來。
- makefile
這個之前每次都有做，只是我忘記提了，把在user中要編譯的東西放進去
- user space
在`user.h`中要宣告一個抽象的syscall，然後在`usys.pl`中也加一個，稍微看一下它就是把它變成一個組合語言的程式碼，去呼叫kernel中的syscall
- sys_trace
去`kernel/sysproc.c`裡面寫一個`sys_trace()`函式
```cpp
uint64 sys_trace(void){
int n;
argint(0, &n);
myproc()->tracemask = n;
return 0;
}
```
在`proc.c`中定義的`proc`中，加入一個tracemask，代表的是trace時輸入的mask，而這個函式做的事就是去設定這個mask。另外，我們希望用`fork()`開的新進程也可以有相同的tracemask，所以要在`fork()`中加入下面這行程式碼：
```cpp
np->tracemask = p->tracemask;
```
- syscall
首先，我們會在這裡宣告`extern uint64 sys_trace(void);`讓它去抓我們在`sysproc.c`中寫好的函式。然後在syscall table中加入這個函式，給它一個編號。然後去稍微修改`syscall()`，讓他在每次被呼叫的時候都輸出我們想要的東西
```cpp
void syscall(void)
{
int num;
struct proc *p = myproc();
num = p->trapframe->a7;
char* names[22] = {
"fork",
"exit",
"wait",
"pipe",
"read",
"kill",
"exec",
"fstat",
"chdir",
"dup",
"getpid",
"sbrk",
"sleep",
"uptime",
"open",
"write",
"mknod",
"unlink",
"link",
"mkdir",
"close",
"trace"
};
if(num > 0 && num < NELEM(syscalls) && syscalls[num]) {
// Use num to lookup the system call function for num, call it,
// and store its return value in p->trapframe->a0
p->trapframe->a0 = syscalls[num]();
if(((p->tracemask)>>num) & 1){
printf("%d: syscall %s -> %d\n", p->pid, names[num - 1] ,p->trapframe->a0);
}
} else {
printf("%d %s: unknown sys call %d\n",
p->pid, p->name, num);
p->trapframe->a0 = -1;
}
}
```
### sysinfotest
一樣是給我一個user space中的指令，要去實做syscall。實作流程大致和上面差不多，不一樣的是我要傳一個struct出來，還有要去獲得剩下的memory空間和正在使用的線程數量。
- sys_sysinfo.h
```cpp
#include "types.h"
#include "defs.h"
#include "sysinfo.h"
uint64 systeminfo(uint64 addr){
struct proc *p = myproc();
struct sysinfo info;
info.freemem = memorycount();
info.nproc = proc_count();
if(copyout(p->pagetable, addr, (char *)&info, sizeof(info)) < 0)
return -1;
return 0;
}
uint64 sys_sysinfo(void){
uint64 st;
argaddr(0, &st);
// return systeminfo(st);
// return 0;
return systeminfo(st);
}
```
- proc_count
```cpp
uint64 proc_count(){
struct proc *p;
uint64 ret = 0;
for(p = proc; p < &proc[NPROC]; p++) {
if(p->state != UNUSED){
ret++;
}
}
return ret;
}
```
- memorycount
```cpp
uint64 memorycount(void){
struct run *r = kmem.freelist;
uint64 ret = 0;
while(r){
ret += PGSIZE;
r = r->next;
}
return ret;
}
```
然後把proc_count()和memorycount()都加進`defs.h`裡面，讓其他地方只要include它就能使用他們了。
# Page Tables(2024/06/27)
## Paging Hardware
在xv6中，對於每個虛擬的64bits記憶體位置，其中低的39bits代表的是他的記憶體位置。27bits是一個index，會映射到page table中的一個元素，也稱page table entry(PTE)。每個PTE有44位的physical page number(PPN)和12位的flag，flag可以表示這個PTE的一些屬性。而虛擬記憶體位置的最低位12bits代表的是offset，和在真正的記憶體位置的offset是一樣的。然後我們每個PTE都用8bytes去存它。
另外，每個PTE代表的就是一個page，因為他有12bit的offset，每個位置代表一個byte，所以一個page有4096bytes。
然而，實際上我們不會用開一個 $2^{27}$ 大小的page table，而是開三個page table。
- 第一層
他是一個page，有4096bytes，一個PTE佔8bytes，所以在這裡放512個PTE。它可以處理9位的記憶體位置。
- 第二層
對於每個在第一層對應到的PPN，在第二層中都可以對應到一個page table，然後我在用虛擬記憶體位置的第二組9個bits去對應到令一個PPN。因為在第一層有512種可能的PPN，所以第二層要開512個page table
- 第三層
同樣的用第二層的PPN去在第三層對應page table，要開512 * 2個page table，而查出他的PPN
- 合併
把前三層查出的PPN合併起來，並加上offset就是它在機器中真正的記憶體位置
## Kernel Address Space
每個進程都有一個user address space和一個kernel address space，對於user address space有自己一組自己的page table，而對於kernel address space，所有進程共用一個page table。
## 開機時的記憶體分配
接下來是去看main.c的原始碼，以下是開機時做的動作：
- kinit()
從end開始到PHYSTOP做`kfree()`，釋放出空間，它就是維護一個freelist，把可以用的空間一直加到前面
- kvminit()
它會去呼叫`kvmmake()`來初始化`kernel_pagetable`，而`kvmmake()`做的是就是開一個page table，然後去對於每個kernel space的部份都用`kvmmap()`映射一個物理記憶體位置給它。值得注意的是，大部分的東西本來就已經指定好page的空間了，只有分配進程的部份需要`kalloc()`。
- kvminithart()
它會把`kernel)pagetable`寫進cpu的暫存器裡面
- userinit()
它是在開啟user的第一個進程，首先用`allocproc`分配一個新的進程。它做的事情其實是去前面分配好的進程中找一個沒被使用的出來，然後用`proc_pagetable()`分配一個page table給它。接下來把initcode塞進去一個新分配的物理記憶體位置中，並在page table中建立一個映射
## exec()
- load elf
它會先檢查讀進來的檔案是不是elf，然後把程式讀進記憶體裡面，方法是用`uvmalloc()`把能用的記憶體分配到我們設定的大小，然後用`loadseg()`去把程式碼讀進去記憶體。
- user stack
接下來，它會去多分配兩個page的空間，其中一個是stack guard，防止溢位而影響到下面的東西。另一個是user stack。接下來把輸入的參數push進去user stack裡面。
- set page table
最後，它會把page table弄給新的進程的page table，並把那個進程舊的page table釋放掉
## Lab3 Page Tables
### Speed up system calls
它叫我弄出一段唯讀的記憶體，user可以訪問，讓它可以不用進入kernel就能獲得這個進程的pid。
每次呼叫這個函數的時候，user都會去一個固定的記憶體位置的東西，我要做的是建立一個記憶體映射，然後物理記憶體存東西。當我在user space去查虛擬記憶體位置時就會查到這個東西。
- allocproc()
```cpp
if((p->usyscallpage = (struct usyscall *)kalloc()) == 0){
freeproc(p);
release(&p->lock);
return 0;
}
p->usyscallpage->pid = p->pid;
```
在`proc`裡加了一個`usyscallpage`，裡面有`pid`，我分配了一個記憶體位置給它。要注意的是在`freeproc`裡要記得把他釋放掉。
- proc_pagetable()
```cpp
if(mappages(pagetable, USYSCALL, PGSIZE, (uint64)(p->usyscallpage), PTE_R | PTE_U) < 0){
uvmfree(pagetable, 0);
return 0;
}
```
建立記憶體映射，另外注意的是在`proc_freepagetable`要去解除`USYSCALL`的記憶體映射。
### Print a page table
就把page table印出來，用前面那個三層的結構
```cpp
void vmprint(pagetable_t pagetable1){
printf("page table %p\n", pagetable1);
for(int i = 0; i < 512; i++){
pte_t pte1 = pagetable1[i];
if(pte1 != 0){
printf("..%d: pte %p pa %p\n", i, pte1, pte1 >> 10 << 12);
if((pte1 & PTE_V) && (pte1 & (PTE_R|PTE_W|PTE_X)) == 0){
pagetable_t pagetable2 = (pagetable_t)PTE2PA(pte1);
for(int j = 0; j < 512; j++){
pte_t pte2 = pagetable2[j];
if(pte2 != 0){
printf(".. ..%d: pte %p pa %p\n",j, pte2, pte2 >> 10 << 12);
if((pte2 & PTE_V) && (pte2 & (PTE_R|PTE_W|PTE_X)) == 0){
pagetable_t pagetable3 = (pagetable_t)PTE2PA(pte2);
for(int k = 0; k < 512; k++){
pte_t pte3 = pagetable3[k];
if(pte3 != 0){
printf(".. .. ..%d: pte %p pa %p\n",k , pte3, pte3 >> 10 << 12);
}
}
}
}
}
}
}
}
```
### Detect which pages have been accessed
用flag去判斷哪個記憶體位置有被訪問過，就是用walk去找到他最後一層的那個pte，他的第六個bit代表的就是有沒有被access過，最後把結果用`copyout()`複製出來，也算是常規操作了。
```cpp
int sys_pgaccess(void)
{
pagetable_t pagetable = myproc()->pagetable;
uint64 ret = 0;
uint64 va;
int num;
uint64 addr;
vmprint(pagetable);
argaddr(0, &va);
argint(1, &num);
argaddr(2, &addr);
for(int i = 0; i < num; i++){
pte_t* pte = walk(pagetable, va + i * PGSIZE, 0);
if(*pte & (1 << 6)){
ret |= (1 << i);
*pte ^= (1 << 6);
}
}
struct proc *p = myproc();
if(copyout(p->pagetable, addr, (char*)&ret, sizeof(ret)) < 0){
return -1;
}
return 0;
}
```
# Traps and System Calls(2024/06/29)
CPU中斷當前執行的指令而去處理當前事件的情況稱為trap，以下是幾種情況：
- system call
- exception
- device interrupt
它會有transparent的特性，也就是說user只看得到抽象化的system call，不會去關注實際上發生了什麼。
## RISC-V trap machinery
首先是一些寄存器：
- stvec
trap handler放在這裡(像是uservec和kernelvec)，也就是trap要執行的那些東西。
- sepc
存原本執行的程式的位置，在sret(從trap返回)的時候，pc會到sepc存的東西開始執行
- scause
放一個數字來代表trap的原因
- sscratch
存trapframe的記憶體位置，而trapframe是拿來存程式原本的各種狀態的
- sstatus
拿來存trap的狀態的，其中的SIE bit控制允不允許device interrupt，SPP控制這個trap是在user mode還是supervisor mode執行的。
- satp:
存page-table root的記憶體位置
- stval
存page-fault的記憶體位置
這些東西都要在supervisor mode才能操作。
### User Trap
會發生user trap的情況有三種：
- system call
- exception
- interrupt
接下來看一下原始碼：
- uservec
當user trap發生的時候，會先進到`trmpoline.S`中的`uservec`中。然後它會把暫存器裡面的東細都放進進程的trapframe裡面，然後呼叫`usertrap()`
- usertrap()
它首先先判斷trap是不是從user mode來的，接下來因為它進入supervisior mode了，所以會把`stvec`設成`kernelvec`
```cpp
w_stvec((uint64)kernelvec);
```
然後它會把pc存到`p->tramframe->epc`裡面，它代表的是原本程式執行到的位置。
```cpp
p->trapframe->epc = r_sepc();
```
然後接下來它會用`r_scause()`去判斷trap的原因，去執行相應的動作。
```cpp
if(r_scause() == 8){
//syscall
}else ...
```
如果是syscall的話，那就會把interrupt打開，然後呼叫`syscall()`。
```cpp
intr_on();
syscall();
```
另外，它還會把pc的位置往後移4，因為它回傳的位置要是執行完syscall的位置。
```cpp
p->trapframe->epc += 4;
```
最後，它會呼叫`usertrapret()`
- usertrapret()
到這裡，這個trap已經執行完了，首先它會把interrupt關掉，然後把`stvec`切回`uservec`。
```cpp
w_stvec(trampoline_uservec);
```
接下來把一些必要的參數塞給`trapframe`，然後把`pc`的位置恢復，最後就去呼叫`trampoline.S`中的`userret`，然後它就是把所有暫存器都恢復。
```cpp
//設定一些參數
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()
//恢復pc位置
w_sepc(p->trapframe->epc);
//呼叫userret
uint64 trampoline_userret = TRAMPOLINE + (userret - trampoline);
((void (*)(uint64))trampoline_userret)(satp);
```
## Kernel Trap
會發生kernel trap的情況有兩種：
- exception
- interrupt
因為它本來就在kernel裡面，所以syscall不需要trap。
然後大致流程和user trap差不多
## Lab4 Traps
### backtrace
它叫我去追蹤執行sleep的時候從哪裡跳過來的。
首先，照著它講的在`riscv.h`裡面加上`r_fp()`這個函數：
```cpp
static inline uint64 r_fp()
{
uint64 x;
asm volatile("mv %0, s0" : "=r" (x) );
return x;
}
```
它可以幫我們找到`s0`的位置，也就是stack的底部。`ret address`會存在`s0 - 8`的位置，而`s0 - 16`存的會是return之後的stack底部。所以我們只要一直去輸出`s0 - 8`那個位置存的值，然後再去`s0 - 16`看下一個底部在哪裡，直到它已經不在這個page裡面了。
```cpp
void backtrace(void){
uint64 fp = r_fp();
uint64 low = PGROUNDDOWN(fp);
uint64 up = PGROUNDUP(fp);
printf("backtrace:\n");
while(fp > low && fp < up){
printf("%p\n", *(uint64*)(fp - 8));
fp = *(uint64*)(fp - 16);
}
}
```
### Alarm
實作一個system call，`int sigalarm(int ticks, void (*handler)())`，讓它每經過幾個tick就執行一次函式。做syscall的部份前面作業就做過了，不加贅述，在此著重在函式的實做。
我們會在進程的struct中加入一些參數，然後要在`allocproc()`中初始化。
```cpp
struct proc{
...
int ticks; // 幾個ticks執行一次，ticks==-1代表不要在執行handler了
void (*handler)(); // 就是handler
int cnt; // 共經過多少個tick
uint64 bk[36]; // 拿來存暫存器東西的
int handling; // 是否在執行handler，如果在執行函數時就不再去呼叫handler了
}
```
- sys_sigalarm
設定這個進程的handler和ticks
```cpp
uint64 sys_sigalarm(void){
int ticks;
uint64 addr;
void (*handler)();
argint(0, &ticks);
argaddr(1, &addr);
if(ticks == 0 && addr == 0){
myproc()->ticks = -1;
return 0;
}
handler = (void(*)())addr;
struct proc* p = myproc();
p->handler = handler;
p->ticks = ticks;
p->cnt = 0;
return 0;
}
```
- trap.c
在裡面要去`usertrap()`中處理time interrupt，當有handler在需要被執行的情況下，而且時間到了，我們會把這個進程的trapframe存起來，然後把這個進程的`epc`送到要執行的函數的記憶體位置，它就會開始執行。題外話，原本寫的比較丑，把`bk`宣告成一個`trapframe`，在複製的時候就一長串的一個一個複製，這個直接宣告陣列複製記憶體的方法是網路上查到的。
```cpp
...
else if((which_dev = devintr()) != 0){
if(myproc()->ticks == -1){
goto yield;
}
if(which_dev == 2 && myproc()->ticks){
myproc()->cnt++;
if(myproc()->cnt == myproc()->ticks && !myproc()->handling){
myproc()->cnt = 0;
memmove(myproc()->bk, myproc()->trapframe, sizeof(myproc()->bk));
myproc()->handling = 1;
myproc()->trapframe->epc = (uint64)(myproc()->handler);
}
}
// ok
}
...
```
- sys_sigreturn
那個handler會去呼叫它，它會把之前存起來的trapframe恢復回來。
```cpp
uint64 sys_sigreturn(void){
if(myproc()->ticks == -1){
return 0;
}
memmove(myproc()->trapframe, myproc()->bk, sizeof(myproc()->bk));
myproc()->handling = 0;
return 0;
}
```
# Interrupts(2024/07/01)
## 一些硬體接口
他們都可以在讀完時發送interrupt
- UART
一些設備的driver，像是console。他的程式碼放在`kernel/uart.c`中
- PLIC
拿來接一些外部設備，他的程式碼放在`kernel/plic.c`
## Code Review
### main.c
- `consoleinit`
它先初始化 `uart` ，然後把裝置中 `read` 和 `write` 的函式設定好。
```cpp
uartinit();
devsw[CONSOLE].read = consoleread;
devsw[CONSOLE].write = consolewrite;
```
- `plicinit`
開啟 `plic` 對於 `uart` 和 `virtio` 的 `interrupt`
- `plicinithart`
讓cpu表示它對於 `uart` 和 `virtio` 的 `interrupt` 的接受
- `scheduler`
雖然順序不對，不過先講這個，它會一直去呼叫 `intr_on()` 讓它去接受interrupt
- `init`
下面繼續
### init.c
- 讓0、1、2代表標準輸入、輸出、錯誤
首先把console打開，然後打開輸入，接下來指派兩個新的文件描述符，剛好是1和2
```cpp
if(open("console", O_RDWR) < 0){
mknod("console", CONSOLE, 0);
open("console", O_RDWR);
}
dup(0); // stdout
dup(0); // stderr
```
- 開啟shell
它會一直用子進程開shell，關掉了就再開一個
### sh.c
shell的部份在這裡值得一題的應該是如何去讀和寫，讀的部份它會去呼叫 `gets` ， `gets` 會一直呼叫 `read` 讀一個字元直到讀完一行或者到極限。接下來就是去kernel裡面找那個syscall，發現它又呼叫了`fileread`，然後我們就會看到熟悉的東西：
```cpp
devsw[f->major].read(1, addr, n);
```
這不就是我們在 `consoleinit` 裡面設定的 `consoleread` 嗎?這裡我們按照順序來，從鍵盤輸入那課開始講起。
- trap.c
當有個device interupt發生之後，如果他是 `uart` 的話，就會呼叫 `uartintr()`，然後它會把所有讀到的每個東西都當作參數去呼叫 `consoleintr`，然後它會把讀到的東西塞進console的buffer裡面。直到讀到換行或是到達極限的值後把`consoleread`叫醒，細節上它會維護兩個指針代表這個時候讀到哪和我現在最多可以讀到哪。另外，它讀東西進來時候其實會直接輸出一個東西，那就是為什麼我們打鍵盤的時候會在terminal上面顯示東西。
- `consoleread`
如果說buffer是空的，那它會先sleep，等待被叫醒。
當有東西可以圖的時候，它就會讀一個東西進來。
接下來講個 `write` ，它一樣會呼叫到 `consolewrite` ，然後 `uart` 那裡也有一個buffer，呼叫 `uartputc` 會往裡面賽塞東西，一樣是滿了之後會睡覺，等有空間了再被叫醒。塞東西進去後會去呼叫`uartstart`，它會向裝置塞東西，塞完之後會把`uartputc`叫醒，叫它繼續把東西送進buffer裡面。
# Lab5 Copy-on-Write Fork for xv6(2024/07/04)
原本如果呼叫 `fork()`，系統會把父進程的所有東西都複製給子進程。而為了增加效率與節省記憶體，Copy-on-Write Fork 就是不去複製東西，而是讓兩個虛擬記憶體指向同一個物理記憶體，且把它寫的權限去掉，當它需要修改的時候會發生page fault，這個時候才去複製。
## refc
我們要統計有多少的虛擬記憶體指向那個物理記憶體，當沒有東西指向它的時候將它釋放。
```cpp
struct {
struct spinlock lock;
struct run *freelist;
} kmem;
struct{
struct spinlock lock;
int cnt[PGROUNDUP(PHYSTOP)/PGSIZE];
}refc;
void refcinit(){
initlock(&refc.lock, "refc");
for(int i = 0; i < PGROUNDUP(PHYSTOP)/PGSIZE; i++){
refc.cnt[i] = 1;
}
}
void refcincr(void *pa){
acquire(&refc.lock);
refc.cnt[PA2IDX(pa)]++;
release(&refc.lock);
}
void refcdecr(void *pa){
acquire(&refc.lock);
refc.cnt[PA2IDX(pa)]--;
release(&refc.lock);
}
void kinit(){
initlock(&kmem.lock, "kmem");
refcinit();
freerange(end, (void*)PHYSTOP);
}
void kfree(void *pa){
...
refcdecr(pa);
if(refc.cnt[PA2IDX(pa)] > 0){
return;
}
...
}
void *kalloc(void)
{
...
refcincr(r);
return (void*)r;
}
```
## uvmcopy
`fork()`會去呼叫`uvmcopy()`，所以我們讓他不去分配新的物理記憶體，在他的PTE flags中去掉可寫的flag，增加COW的flag。
```cpp
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
pte_t *pte;
uint64 pa, i;
uint flags;
// char *mem;
for(i = 0; i < sz; i += PGSIZE){
if((pte = walk(old, i, 0)) == 0)
panic("uvmcopy: pte should exist");
if((*pte & PTE_V) == 0)
panic("uvmcopy: page not present");
pa = PTE2PA(*pte);
if(*pte & PTE_W){
*pte = (*pte & ~PTE_W) | PTE_C;
}
flags = PTE_FLAGS(*pte);
if(mappages(new, i, PGSIZE, pa, flags) != 0){
goto err;
}
refcincr((void*)pa);
}
return 0;
err:
uvmunmap(new, 0, i / PGSIZE, 1);
return -1;
}
```
## usertrap
處理page fault的情況
```cpp
usertrap(void){
...
}else if(r_scause() == 13 || r_scause() == 15){
uint64 va = r_stval();
if(va >= MAXVA || (va <= PGROUNDDOWN(p->trapframe->sp) && va >= PGROUNDDOWN(p->trapframe->sp) - PGSIZE)){
setkilled(p);
}else if(cowalloc(p->pagetable, va) != 0){
setkilled(p);
}
}
...
}
```
## cowalloc
為COW page分配新的物理記憶體，並且將原本存的東西複製過去。
```cpp
int cowalloc(pagetable_t pagetable, uint64 va){
pte_t *pte;
uint64 pa;
char* mem;
uint flags;
if((pte = walk(pagetable, va, 0)) == 0){
return -1;
}
if((pa = PTE2PA(*pte)) == 0){
return -1;
}
if((*pte & PTE_V) == 0){
return -1;
}
if(*pte & PTE_W){
return 0;
}
if((*pte & PTE_C) == 0){
return -1;
}
if((mem = kalloc()) == 0){
return -1;
}
flags = (PTE_FLAGS(*pte) & ~PTE_C) | PTE_W;
memmove(mem, (char*)pa, PGSIZE);
*pte = PA2PTE(mem) | flags;
kfree((void*)pa);
return 0;
}
```
## copyout
另外copyout也要改
```cpp
int copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
uint64 n, va0, pa0;
while(len > 0){
va0 = PGROUNDDOWN(dstva);
if(va0 >= MAXVA || cowalloc(pagetable, va0) != 0){
return -1;
}
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;
}
```
# Scheduling(2024/07/08)
我們會有幾個 cpu ，和幾個需要執行的進程，一個 cpu 一次只能執行一個進程，scheduling 就是一直讓閒置的 cpu 去尋找它可以執行的進程。以下直接開始 view code:
## scheduler
從一開始的 `main` ，每個cpu都會去呼叫這個函數。
它做的事情就是一直找 `RUNNABLE` 的進程去跑。
```cpp
void scheduler(void)
{
struct proc *p;
struct cpu *c = mycpu();
c->proc = 0;
for(;;){
intr_on();
for(p = proc; p < &proc[NPROC]; p++) {
acquire(&p->lock);
if(p->state == RUNNABLE) {
p->state = RUNNING;
c->proc = p;
swtch(&c->context, &p->context);
c->proc = 0;
}
release(&p->lock);
}
}
}
```
## swtch
他是一個組合語言的函數，寫在 `swtch.S` 裡面，功能是把一邊的 `context` 存起來，把另一邊的 `context` 讀取進來， `context` 裡面存的是 callee register。暫存器依誰有責任維護它分為 caller register 和 callee register ， caller register 在進入一個函數的時候會被推進 stack 裡面，由呼叫別人的函數進行維護， callee register 則是由被呼叫的函數進行維護，譬如說 stack pointer 這種東西。
## shed
它會讓 cpu 從一個進程中回到 cpu scheduler 裡面。
```cpp
void sched(void)
{
int intena;
struct proc *p = myproc();
if(!holding(&p->lock))
panic("sched p->lock");
if(mycpu()->noff != 1)
panic("sched locks");
if(p->state == RUNNING)
panic("sched running");
if(intr_get())
panic("sched interruptible");
intena = mycpu()->intena;
swtch(&p->context, &mycpu()->context);
mycpu()->intena = intena;
}
```
## exit and wait
這裡只著重於和 scheduling 有關的東西上。
- wait
它會找到自己的子進程然後如果他的狀態是 `ZOMBIWE` 的話就把它釋放，沒有兒子的話救回傳 -1，如果還不是 `ZOMBIWE` 的話就先睡覺，它等下會被 `exit` 叫醒。另外為了讓 exit 和它不會同時被處理，他有加了一個 wait 的鎖。
```cpp
int
wait(uint64 addr)
{
struct proc *pp;
int havekids, pid;
struct proc *p = myproc();
acquire(&wait_lock);
for(;;){
// Scan through table looking for exited children.
havekids = 0;
for(pp = proc; pp < &proc[NPROC]; pp++){
if(pp->parent == p){
// make sure the child isn't still in exit() or swtch().
acquire(&pp->lock);
havekids = 1;
if(pp->state == ZOMBIE){
// Found one.
pid = pp->pid;
if(addr != 0 && copyout(p->pagetable, addr, (char *)&pp->xstate,
sizeof(pp->xstate)) < 0) {
release(&pp->lock);
release(&wait_lock);
return -1;
}
freeproc(pp);
release(&pp->lock);
release(&wait_lock);
return pid;
}
release(&pp->lock);
}
}
// No point waiting if we don't have any children.
if(!havekids || killed(p)){
release(&wait_lock);
return -1;
}
// Wait for a child to exit.
sleep(p, &wait_lock); //DOC: wait-sleep
}
}
```
- exit
它會把他的爸爸叫醒，然後把自己的狀態變成 `ZOMBIE` ，然後呼叫 `shed`。
```cpp
void exit(int status)
{
struct proc *p = myproc();
...
acquire(&wait_lock);
// Give any children to init.
reparent(p);
// Parent might be sleeping in wait().
wakeup(p->parent);
acquire(&p->lock);
p->xstate = status;
p->state = ZOMBIE;
release(&wait_lock);
// Jump into the scheduler, never to return.
sched();
panic("zombie exit");
}
```
接下來有些東西諸如 `sleep` 和 `wakeup` 的實做也都大同小異，這裡以 `yield` 來講一下關於進程鎖的東西。
## yield
它就是把自己的狀態變成 `RUNNABLE`， 然後回到 cpu scheduler。值得注意的是它 `acquire` 的這個鎖其實會在 cpu scheduler 的地方去 `release`，而在 cpu scheduler 裡 `acquire` 的那個鎖則會用下面那個 `release`，因為他在呼叫 `sched` 的時候他的 return address 會是 `sched` 的下一行，所以它會繼續執行下面的東西。
```cpp
void yield(void)
{
struct proc *p = myproc();
acquire(&p->lock);
p->state = RUNNABLE;
sched();
release(&p->lock);
}
```
另外，當一個進程被創建的時候， `allocproc` 會把他的 `context` 中的 `ra` 設成 `forkret` 的位置，而裡面也會有一個 `release`。
## Lab6 Multithreading
### Uthread
它會有3個線程在跑（實際上市只有一個線程，但讓那三個線程以為自己是獨立的線程），要去修改 `thread_create` 、 `thread_schedule` 和 `thread_switch` 讓它可以運作。
首先我先在 `struct thread` 中加入一個 `context` ，存的東西和 `proc` 裡面的 `context` 是一樣的。
- thread_create
把 `ra` 和 `sp` 存起來
```cpp
t->context.ra = (uint64)func;
t->context.sp = (uint64)(t->stack + STACK_SIZE - 1);
```
- thread_switch
把暫存器內容存到前面的 `context` 裡面，把後面的 `context` 塞進去。
```asm
.globl thread_switch
thread_switch:
sd ra, 0(a0)
sd sp, 8(a0)
sd s0, 16(a0)
sd s1, 24(a0)
sd s2, 32(a0)
sd s3, 40(a0)
sd s4, 48(a0)
sd s5, 56(a0)
sd s6, 64(a0)
sd s7, 72(a0)
sd s8, 80(a0)
sd s9, 88(a0)
sd s10, 96(a0)
sd s11, 104(a0)
ld ra, 0(a1)
ld sp, 8(a1)
ld s0, 16(a1)
ld s1, 24(a1)
ld s2, 32(a1)
ld s3, 40(a1)
ld s4, 48(a1)
ld s5, 56(a1)
ld s6, 64(a1)
ld s7, 72(a1)
ld s8, 80(a1)
ld s9, 88(a1)
ld s10, 96(a1)
ld s11, 104(a1)
ret
```
- thread_schedule
它會去呼叫 `thread_switch`
```cpp
thread_switch(&t->context, &next_thread->context);
```
### Using Threads
它有個多線程的 hash table ，但是它沒有上鎖所以多線程會出問題，所以要在應該要上鎖的地方上鎖，並且還要發揮多線程的優勢。我可以在每個 put 都上同一個鎖，但是這樣會變成一次只能執行一個線程。所以，我們把 key 去做分組，每一個組別裡面有一個鎖，這樣只要是不同組別的就可以平行處理。
```cpp
static void put(int key, int value)
{
int i = key % NBUCKET;
// is the key already present?
struct entry *e = 0;
pthread_mutex_lock(lock + i);
...
pthread_mutex_unlock(lock + i);
}
```
### barrier
它會用多線程去執行某個函式，但是每次遇到 `barrier` 就會等待所有其他線程都到達這個函式。首先是它給了兩個函式， `pthread_cond_broadcast` 會把所有因為某個狀況而睡覺的線程都叫起床， `pthread_cond_wait` 會讓它因為某個情況睡覺，並且把某個鎖解開。然後鎖的部份是細節處理，想清楚就好。
```cpp
static void barrier()
{
pthread_mutex_lock(&bstate.barrier_mutex);
cnt++;
if(cnt == nthread){
cnt = 0;
bstate.round++;
pthread_cond_broadcast(&bstate.barrier_cond);
pthread_mutex_unlock(&bstate.barrier_mutex);
}else{
pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
pthread_mutex_unlock(&bstate.barrier_mutex);
}
}
```
# Lab8 Locks(2024/07/09)
## Memory allocator
原本 xv6 的 `kalloc` 是所有 cpu 共用一個 list，共用一個鎖，所以一次只能有一個 cpu 去使用它。我們希望去減少這種資源競爭的情況，於是方法是給每個 cpu 一個 list，每個 list 都有一個鎖，當自己的 list 還有空間的時候就只鎖自己的，否則就去搶別人的。
### kmem
```cpp
struct {
struct spinlock lock;
struct run *freelist;
} kmem[NCPU];
```
### kinit
`kinit` 會去初始化所有的鎖，另外這是由第0個 cpu 去執行的，它會先把所有的空間都放到編號是 0 的 freelist 裡面，其他的 cpu 就會自然的去搶它。
### kfree
它會把這個物理記憶體插在自己 cpu 為編號的 freelist 前面。
```cpp
void kfree(void *pa)
{
struct run *r;
if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
panic("kfree");
// Fill with junk to catch dangling refs.
memset(pa, 1, PGSIZE);
r = (struct run*)pa;
push_off();
int id = cpuid();
acquire(&kmem[id].lock);
r->next = kmem[id].freelist;
kmem[id].freelist = r;
release(&kmem[id].lock);
pop_off();
}
```
### kalloc
它會去看自己還有沒有空間，不然就去偷別人的。要注意的是在呼叫 `cpuid` 的時候要 `push_off` 來關閉中斷。
```cpp
void *kalloc(void)
{
struct run *r;
push_off();
int id = cpuid();
acquire(&kmem[id].lock);
r = kmem[id].freelist;
if(r){
kmem[id].freelist = r->next;
release(&kmem[id].lock);
}else{
release(&kmem[id].lock);
for(int i = 0; i < NCPU; i++){
if(i != id){
acquire(&kmem[i].lock);
r = kmem[i].freelist;
if(r){
kmem[i].freelist = r->next;
release(&kmem[i].lock);
break;
}
release(&kmem[i].lock);
}
}
}
pop_off();
if(r)
memset((char*)r, 5, PGSIZE); // fill with junk
return (void*)r;
}
```
## Buffer Cache
這個快取是拿來維護一些被使用的資料，如果這個資料沒有被使用就會被釋放，拿來裝有用的東西。然而，這裡沒有需要做到 LRU Cache，不需要對沒有使用的資料依使用頻率分優劣。這裡要處理的問題是希望將這些 bcache 分成幾個 buckets，每個 bucket 使用一個鎖，讓它可以發揮多核心的優勢，降低資源競爭的頻率。
具體來講，我們會將 buf 依據他的內容經過一個 hash 之後塞進不同的 bucket 裡面。
### bcache
```cpp
#define NBUCKET 13
struct {
struct spinlock lock[NBUCKET];
struct buf buf[NBUF];
struct buf head[NBUCKET];
} bcache;
```
### binit
首先初始化每一個 bucket，然後把所有的 buffer 都分配給編號為 0 的 bcache，其他的 bcache 到時候會去它那裡搶。
```cpp
void
binit(void)
{
struct buf *b;
for(int i = 0; i < NBUCKET; i++){
initlock(&bcache.lock[i], "bcache");
// Create linked list of buffers
bcache.head[i].prev = &bcache.head[i];
bcache.head[i].next = &bcache.head[i];
}
for(b = bcache.buf; b < bcache.buf+NBUF; b++){
b->next = bcache.head[0].next;
b->prev = &bcache.head[0];
initsleeplock(&b->lock, "buffer");
bcache.head[0].next->prev = b;
bcache.head[0].next = b;
}
}
```
### bget
這算是這個 lab 裡面最核心的函數了。
首先，它會先去找在這個 bcache 裡有沒有這個東西，如果有就直接回傳。
```cpp
struct buf *b;
int id = (blockno + dev) % NBUCKET;
acquire(&bcache.lock[id]);
// Is the block already cached?
for(b = bcache.head[id].next; b != &bcache.head[id]; b = b->next){
if(b->dev == dev && b->blockno == blockno){
b->refcnt++;
release(&bcache.lock[id]);
acquiresleep(&b->lock);
return b;
}
}
release(&bcache.lock[id]);
```
沒找到的話就開始在所有 bcache 裡面去找，這裡關於鎖有幾個需要注意的點。當我在其他 bcache 找到沒有被引用的 buffer 的時候，要對 `id` 的那個 bcache 去做操作，所以必須要獲得他的鎖。然而不可能在裡面獲得他的鎖，因為這個時候我身上有另一個鎖，可能會造成 dead lock，所以我在裡面做的事情就只有把那個 buffer 從原本的 bcache 裡去掉。當出來的時候可能會遇到另一個問題，因為我在遊歷所有 bcache 的時候，編號 `id` 的鎖是被解開的狀態，所以另一個 cpu 完全就可以也進來找到另一個可以用的 buffer，然後如果我直接處理就會造成這個 bcache 裡有兩個編號相同的 buffer。這樣會造成 buffer 被重複釋放而跳出 `panic("freeing free block")`。我看網路上文章的解決方法是加一個全域的鎖，讓搶別人東西這一步變成單個進程的。然而我不想要犧牲效率，於是我的解決方法是再去搜一次這個 bcache 裡面的東西看看有沒有對應的 cache，沒有的話再用找到的那一個 buffer。然後不管怎樣這個 buffer 都會被插在最前面，只是差別在要不要用它而已。然後另外記得要在 `acquiresleep` 之前把其他鎖釋放，因為在跳回去 cpu scheduling 進程的時候只會允許有他的進程鎖，否則會跳出 `panic("shed locks")`。
``` cpp
for(int i = 0; i < NBUCKET; i++){
if(i == id){
continue;
}
acquire(&bcache.lock[i]);
for(b = bcache.head[i].next; b != &bcache.head[i]; b = b->next){
if(b->refcnt == 0){
b->prev->next = b->next;
b->next->prev = b->prev;
release(&bcache.lock[i]);
goto found;
}
}
release(&bcache.lock[i]);
}
found:
// found in global buffer
acquire(&bcache.lock[id]);
b->next = bcache.head[id].next;
b->prev = &bcache.head[id];
b->refcnt = 0;
bcache.head[id].next->prev = b;
bcache.head[id].next = b;
struct buf *tmp = b;
// check if there is a new buffer
for(b = bcache.head[id].next; b != &bcache.head[id]; b = b->next){
if(b->dev == dev && b->blockno == blockno){
b->refcnt++;
release(&bcache.lock[id]);
acquiresleep(&b->lock);
return b;
}
}
// if not, give it a new buffer
b = tmp;
b->dev = dev;
b->blockno = blockno;
b->valid = 0;
b->refcnt = 1;
release(&bcache.lock[id]);
acquiresleep(&b->lock);
return b;
panic("bget: no buffers");
```
剩下的部份就是照著原本的 code 把東西改掉就好。
Sign in with Wallet
Connect another wallet