# OS in 1,000 Lines 閱讀筆記
參考書：[OS in 1,000 Lines](https://operating-system-in-1000-lines.vercel.app/tw/)、[SWOS (struggle with OS)](https://hackmd.io/@buobao/1000os)
## Environment
```shell
$ brew install llvm lld qemu
$ export PATH="$PATH:$(brew --prefix)/opt/llvm/bin"
```
## RISC-V 101
### CPU 模式（CPU Modes）
CPU 有多種運作模式，每種模式擁有不同的權限。在 RISC-V 架構中，共有三種主要模式
|Modes|概要|
|---|---|
|M-mode|系統上電後的預設模式，處理器初始化、硬體控制所有暫存器與記憶體空間。OpenSBI (似 BIOS) 在這模式下運行|
|S-mode|作業系統核心（Kernel）在此模式運行，虛擬記憶體管理 (MMU)，系統呼叫 (System call) 、中斷處理、管理應用程式的排程與資源。|
|U-mode|運行應用程式 (App)，只能透過系統呼叫請求 OS 服務，記憶體與指令受限，避免誤用系統資源|
### CSR 暫存器
> [DAY2: RISC-V: 不懂 CSR 那就放棄吧(一)](https://ithelp.ithome.com.tw/m/articles/10289643)
CSR（Control and Status Registers）不是單一暫存器，而是一大群「特殊用途暫存器」的統稱。在 RISC-V 裡，所有跟 CPU 狀態控制、例外/中斷處理、計數器、記憶體管理有關的資訊，都透過 CSR 來管理。例如：中斷控制（mstatus, mie, mip）、Trap 處理（mepc, mcause）、計數器（cycle, time, instret）、記憶體管理（satp）、硬體資訊（misa, mhartid）等。
### 特權指令 (Privileged Instructions
## 嵌入式組合語言（Inline assembly）
## 核心啟動流程
### Linker Script
> [【嵌入式放牛班】Bare-metal Linking](https://www.youtube.com/watch?v=OyiOlvSHRjc&t=1s)
Linker Script 是告訴 Linker（連結器）如何將編譯後的目標檔案 (object file: 原始碼經編譯後的機器碼) 組織成最終的可執行檔案（ELF檔）。
首先，先在建立實驗檔案 main.c :
```c
char cVer[] = "111";
const char ccVer[] = "222";
const char * const ccpcVer = "333";
const char * cpVer = "444";
static unsigned int gBSS_uninit[4];
static unsigned int gBSS_init[] = {1, 2, 3, 4};
static unsigned int tmp = 100;
__attribute__((section(".text.boot")))
int main() {
int ret = 0;
tmp = gBSS_uninit[0] + gBSS_init[0];
return ret;
}
```
其中，以下兩個宣告的差別在於：
```c
const char * const ccpcVer = "333";
// 第一個 const：指標指向的資料是常數，第二個 const：指標本身是常數
const char * cpVer = "444";
// 只有一個 const：指標指向的資料是常數
```
連結器腳本 (Linker Script) `go_linking.ld` :
```txt
ENTRY(main)
SECTIONS {
. = 0x80200000;
.text :{
KEEP(*(.text.boot));
*(.text .text.*);
}
.rodata : ALIGN(4) {
*(.rodata .rodata.*);
}
.data : ALIGN(4) {
*(.data .data.*);
}
.bss : ALIGN(4) {
__bss = .;
*(.bss .bss.* .sbss .sbss.*);
__bss_end = .;
}
}
```
:::warning
- .text：程式碼區段
- .rodata：唯讀資料區段
- .data：已初始化資料區段
- .bss (Block Started by Symbol)：未初始化的全域/靜態變數區段（需要清零的變數）。
:::
編譯器腳本 `go_linking.sh`：
```bash
#!/bin/bash
set -xue
# Path to clang and compiler flags
CC=/opt/homebrew/opt/llvm/bin/clang
CFLAGS="-std=c11 -O0 -g3 -Wall -Wextra --target=riscv32-unknown-elf -fno-stack-protector -ffreestanding -nostdlib -fuse-ld=lld"
# Build the kernel
$CC $CFLAGS -Wl,-Tgo_linking.ld -Wl,-Map=main.map -o main.elf main.c
```
:::warning
`set -xue`: 顯示執行過的每個命令(-x), 未定義變數報錯(-u), 有命令失敗就退出(-e)。
`-O0`: 表示不做編譯器優化，保留已宣告但未使用的變數，來觀察各個變數在記憶體中的區段。
:::
運行 `go_linking.sh` :
```bash
$ chmod +x go_linking.sh
$ ./go_linking.sh
```
會產生 `main.map` 檔：
```txt
VMA LMA Size Align Out In Symbol
0 0 80200000 1 . = 0x80200000
80200000 80200000 34 2 .text
80200000 80200000 34 2 /var/folders/_h/j9cm2q0s4n9_46bqgyjdzr3w0000gn/T/main-91e5d9.o:(.text.main)
80200000 80200000 0 1 .L0
80200000 80200000 0 1 .L0
80200000 80200000 0 1 $x
80200000 80200000 0 1 .L0
80200000 80200000 34 1 main
80200008 80200008 0 1 .L0
8020000a 8020000a 0 1 .L0
8020000e 8020000e 0 1 .L0
80200016 80200016 0 1 .L0
8020001e 8020001e 0 1 .L0
80200020 80200020 0 1 .L0
80200028 80200028 0 1 .L0
8020002c 8020002c 0 1 .L0
80200034 80200034 0 1 .L0
80200034 80200034 0 1 .L0
80200034 80200034 0 2 /var/folders/_h/j9cm2q0s4n9_46bqgyjdzr3w0000gn/T/main-91e5d9.o:(.text)
80200034 80200034 10 4 .rodata
80200034 80200034 8 4 /var/folders/_h/j9cm2q0s4n9_46bqgyjdzr3w0000gn/T/main-91e5d9.o:(.rodata)
80200034 80200034 0 1 $d
80200034 80200034 4 1 ccVer
80200038 80200038 4 1 ccpcVer
8020003c 8020003c 8 1 <internal>:(.rodata.str1.1)
80200044 80200044 1c 4 .data
80200044 80200044 1c 4 /var/folders/_h/j9cm2q0s4n9_46bqgyjdzr3w0000gn/T/main-91e5d9.o:(.data)
80200044 80200044 0 1 $d
80200044 80200044 4 1 cVer
80200048 80200048 4 1 cpVer
8020004c 8020004c 10 1 gBSS_init
8020005c 8020005c 4 1 tmp
80200060 80200060 10 4 .bss
80200060 80200060 0 1 __bss = .
80200060 80200060 10 4 /var/folders/_h/j9cm2q0s4n9_46bqgyjdzr3w0000gn/T/main-91e5d9.o:(.bss)
80200060 80200060 10 1 gBSS_uninit
80200060 80200060 0 1 $d
80200070 80200070 0 1 __bss_end = .
```
其中，Size 的單位是 Byte 以**十六進制**表示，可以發現在 rodata（read-only data） 區段的變數有 `ccVer`, `ccpcVer` 這兩個 `const` 變數，以及一個由編譯器自動建立的字串池（.rodata.str1.1）區段，用來存放字串常量：
```
8020003c 8020003c 8 1 <internal>:(.rodata.str1.1)
```
> <internal>: 編譯器內部產生
其中，字串池會存放所有不管是指標指向，還是用來初始化陣列的 string literals：
:::warning
- String literals：程式碼中用雙引號括起來的字串，如："hello", "333"。
- 初始化字元陣列，如：`char cVer[] = "111";`。
:::
實際字串池的內容其實只有 8 Bytes：
```txt
.rodata.str1.1 區段（字串池）：
8020003c: "333\0" (4 bytes) <- ccpcVer 指向這裡
80200040: "444\0" (4 bytes) <- cpVer 指向這裡
```
:::info
那為什麼在 Linker Map 中 rodata 區段輸出的字串池大小只有 8 Bytes 呢？不是應該有 12 Bytes 嗎？
:::
這就要說到編譯器的處理策略了！當編譯器看到 string literals 時，它會：
- 步驟一：每個 string literals 都會被放到某個唯讀區段（通常是 .rodata.str1.1）
- 步驟二：然後看這些字串怎麼被使用：
- 情境 A：用來初始化陣列，如：
```c
char cVer[] = "111";
const char ccVer[] = "222";
```
那麼編譯器就會去優化，認為這個字串（`"111"`, `"222"`）是用來初始化陣列的，直接把字串內容拷貝到陣列定義的地方(.data 或 .rodata)，就不需要保留獨立的字串常量了。
- 情境 B：被指標引用，如：
```c
const char * const ccpcVer = "333";
const char * cpVer = "444";
```
編譯器會將這些字串（"333", "444"）視為需要有實際記憶體位址的資料，因為指標必須指向一個有效的記憶體位置。因此，編譯器會將這些字串常量保留在記憶體中，並放置於 `.rodata.str1.1` 區段。
### 核心啟動
連結器腳本 (Linker Script) `kernel.ld` :
```
ENTRY(boot)
SECTIONS {
. = 0x80200000; /* 設定載入位址，0x80000000 是 RAM 起始，0x80200000 留給 OpenSBI 使用 */
.text :{
/* KEEP() 確保不會被連結器優化掉 */
KEEP(*(.text.boot)); /* 啟動程式碼，CPU 開始執行的地方 */
*(.text .text.*); /* 其他所有程式碼 */
}
.rodata : ALIGN(4) { /* Read-only data */
*(.rodata .rodata.*);
}
.data : ALIGN(4) {
*(.data .data.*);
}
.bss : ALIGN(4) {
__bss = .;
*(.bss .bss.* .sbss .sbss.*);
__bss_end = .;
}
. = ALIGN(4);
. += 128 * 1024; /* 128KB */
__stack_top = .;
}
```
Makefile：編譯核心並啟動 QEMU
```bash
QEMU := qemu-system-riscv32
CC := /opt/homebrew/opt/llvm/bin/clang
CFLAGS := -std=c11 -O0 -g3 -Wall -Wextra \
--target=riscv32-unknown-elf \
-fno-stack-protector -ffreestanding \
-nostdlib -fuse-ld=lld
# =========== Build + Run (default) ===========
all:
$(CC) $(CFLAGS) -Wl,-Tkernel.ld -Wl,-Map=kernel.map -o kernel.elf kernel.c
$(QEMU) -machine virt -bios default -nographic -serial mon:stdio --no-reboot \
-kernel kernel.elf
# =========== Build + Debug ===========
debug:
$(CC) $(CFLAGS) -Wl,-Tkernel.ld -Wl,-Map=kernel.map -o kernel.elf kernel.c
$(QEMU) -machine virt -bios default -nographic -serial mon:stdio --no-reboot \
-kernel kernel.elf -s -S
gdb:
riscv64-elf-gdb kernel.elf -ex "target remote :1234"
# =========== Clean ===========
clean:
rm -f *.o *.elf *.map *.bin
```
第一個「最小化」核心：
```c
typedef unsigned char uint8_t;
typedef unsigned int uint32_t;
typedef uint32_t size_t;
extern char __bss[], __bss_end[], __stack_top[];
void *memset(void *buf, char c, size_t n) {
uint8_t *p = (uint8_t *) buf;
while (n--) {
*p++ = c;
}
return buf;
}
void kernel_main(void) {
memset(__bss, 0, (size_t) __bss_end - (size_t) __bss);
for (;;);
}
__attribute__((section(".text.boot")))
__attribute__((naked))
void boot(void) {
__asm__ __volatile__(
"mv sp, %[stack_top]\n" // Set the stack pointer
"j kernel_main\n" // Jump to the kernel main function
:
: [stack_top] "r" (__stack_top) // Pass the stack top address as %[stack_top]
);
}
```
使用 `memset(__bss, 0, (size_t) __bss_end - (size_t) __bss);` 將 .bss 區段清成 0。雖然有些 bootloader（開機載入器）會自動將 .bss 清 0，但我們還是自己做一次保險。若 .bss 區段沒有清零，則**置於 bss 區段的變數會包含隨機的垃圾值**，導致程式行為不可預測。
另外，Linker 實際上建立的是符號（symbol），如 `__bss`，但單寫 `__bss` 代表的是「.bss 區段第一個位元組（Byte）的值」，而不是「取得 .bss 區段的起始位址」。而陣列名稱在大多數情況下會自動退化（decay）為指向第一個元素的指標，因此加上 `[]` 使 `__bss` 自動退化為 `.bss` 區段第一個位元組（Byte）的位址（起始位址）。
:::info
`naked` 屬性告訴編譯器不要產生任何除了 inline assembly 以外的其他程式碼。即使不加這個屬性也可能運作正常，但當你需要手動操作堆疊指標時，加上 naked 是一種良好習慣，可以避免預期外的行為。
:::
## 06. Hello World!
參考 RISC-V SBI [riscv-sbi.pdf](https://github.com/riscv-non-isa/riscv-sbi-doc/releases/download/v3.0/riscv-sbi.pdf) Chapter 3 提到：All SBI functions share a single binary encoding, which facilitates the mixing of SBI extensions. The SBI specification follows the below calling convention.
- An `ECALL` is used as the control transfer instruction between the supervisor and the SEE (Supervisor Execution Environment).
- `a7` encodes the SBI extension ID (EID).
- `a6` encodes the SBI function ID (FID) for a given extension ID encoded in `a7` for any SBI extension defined in or after SBI v0.2.
- `a0` through `a5` contain the arguments for the SBI function call. Registers that are not defined in the SBI function call are not reserved.
- All registers except `a0` & `a1` must be preserved across an SBI call by the callee.
- SBI functions must return a pair of values in `a0` and `a1`, with `a0` returning an error code. This is analogous to returning the C structure：
```c
struct sbiret {
long error; // a0
union { // a1
long value;
unsigned long uvalue;
};
};
```
根據上述，sbi_call 可以寫成：
```c
struct sbiret sbi_call(long arg0, long arg1, long arg2, long arg3, long arg4,
long arg5, long fid, long eid) {
register long a0 __asm__("a0") = arg0;
register long a1 __asm__("a1") = arg1;
register long a2 __asm__("a2") = arg2;
register long a3 __asm__("a3") = arg3;
register long a4 __asm__("a4") = arg4;
register long a5 __asm__("a5") = arg5;
register long a6 __asm__("a6") = fid; // function ID
register long a7 __asm__("a7") = eid; // extension ID
__asm__ __volatile__("ecall"
: "=r"(a0), "=r"(a1)
: "r"(a0), "r"(a1), "r"(a2), "r"(a3), "r"(a4), "r"(a5),
"r"(a6), "r"(a7)
: "memory");
return (struct sbiret){.error = a0, .value = a1};
}
```
注意到 `a0` & `a1` 暫存器是可以寫入（"=r"）的，其餘 `a2` ~ `a5` 暫存器為唯讀（"r"），即第五點公約（convention）。
:::info
待證明：
其中，`"memory"` clobber 在這裡代表的意義為：這段 inline asm（ecall）會對記憶體產生不可預期的副作用，因此禁止在 ECALL 前後做任何 memory load/store 重排序或最佳化。
:::
## 07. 核心錯誤處理
以下 PANIC 巨集（macro）就是我們的 kernel panic 實作：
```c
#define PANIC(fmt, ...) \
do { \
printf("PANIC: %s:%d: " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__); \
while (1) {} \
} while (0)
```
> 這段巨集會印出發生 panic 的位置，然後進入一個無窮迴圈來停止後續執行。我們之所以把它寫成巨集，是因為這樣才能正確顯示發生 panic 的原始檔名（\_\_FILE\_\_）與行號（\_\_LINE\_\_）。如果你把它寫成一般函式，那麼 __FILE__ 和 \_\_LINE\_\_ 只會顯示該函式定義的地方，而不是你實際呼叫 PANIC 的位置。
這個巨集用了兩個常見技巧：
1. `do-while` 敘述：
由於條件是 `while(0)`，代表這個區塊只會執行一次。這是 C 語言中定義多行巨集時的常見寫法。如果你沒有用 `do...while(0)` 包起來，在某些情況下（例如搭配 if 使用）可能會造成語法邏輯錯誤。
例如：我們定義一個 SWAP 巨集
```c
#define SWAP(x, y) \
tmp = x; \
x = y; \
y = tmp
```
一般來說，在使用 if 語法中，若只有執行一行指令的話，可以省略大括號，如：
```c
if (x > y)
SWAP(x, y);
```
:::warning
但是 `SWAP` 為巨集，這個巨集展開後如下：
```c
if (x > y)
tmp = x;
x = y;
y = tmp;
```
當 if 的條件成立時，只會執行到 `tmp = x;`，很明顯與程式設計的意圖不同。
:::
2. `##__VA_ARGS__` 的技巧：
這是 GCC 提供的語法擴充，用來撰寫接受不定參數的巨集（參見 GCC 官方說明）。其中 ## 是為了在沒有傳入任何額外參數時，自動移除前面的逗號，這樣如 PANIC("booted!"); 這種只傳一個參數的寫法也能被正確編譯。
## 08. 例外處理
下列關於例外處理的分類摘自：[The RISC-V Instruction Set Manual Volume I](https://docs.riscv.org/reference/isa/_attachments/riscv-unprivileged.pdf) 1.6. Exceptions, Traps, and Interrupts | Page 20
- Trap
>We use the term trap to refer to the transfer of control to a trap handler caused by either an Exception or an Interrupt.
- Exception
> We use the term exception to refer to an unusual condition occurring at run time associated with an instruction in the current RISC-V hart.
- Interrupt
> We use the term interrupt to refer to an external asynchronous event that may cause a RISC-V hart to experience an unexpected transfer of control.
可以得知，不管發生 Interrupt 或 Exception 皆會觸發 Trap，透過 Trap 來切換到 Supervisor Mode (kernel) 來處理 Interrupt 或 Exception。
### 例外處理常式
`stvec` 是 Supervisor Trap Vector Register，決定在 supervisor mode 發生 trap 時，要跳去執行哪個 handler。
:::spoiler 作者設計的 handler
```c
void handle_trap(struct trap_frame *f) {
uint32_t scause = READ_CSR(scause);
uint32_t stval = READ_CSR(stval);
uint32_t user_pc = READ_CSR(sepc);
PANIC("unexpected trap scause=%x, stval=%x, sepc=%x\n", scause, stval, user_pc);
}
__attribute__((naked))
__attribute__((aligned(4)))
void kernel_entry(void) {
__asm__ __volatile__(
"csrw sscratch, sp\n"
"addi sp, sp, -4 * 31\n"
"sw ra, 4 * 0(sp)\n"
"sw gp, 4 * 1(sp)\n"
"sw tp, 4 * 2(sp)\n"
"sw t0, 4 * 3(sp)\n"
"sw t1, 4 * 4(sp)\n"
"sw t2, 4 * 5(sp)\n"
"sw t3, 4 * 6(sp)\n"
"sw t4, 4 * 7(sp)\n"
"sw t5, 4 * 8(sp)\n"
"sw t6, 4 * 9(sp)\n"
"sw a0, 4 * 10(sp)\n"
"sw a1, 4 * 11(sp)\n"
"sw a2, 4 * 12(sp)\n"
"sw a3, 4 * 13(sp)\n"
"sw a4, 4 * 14(sp)\n"
"sw a5, 4 * 15(sp)\n"
"sw a6, 4 * 16(sp)\n"
"sw a7, 4 * 17(sp)\n"
"sw s0, 4 * 18(sp)\n"
"sw s1, 4 * 19(sp)\n"
"sw s2, 4 * 20(sp)\n"
"sw s3, 4 * 21(sp)\n"
"sw s4, 4 * 22(sp)\n"
"sw s5, 4 * 23(sp)\n"
"sw s6, 4 * 24(sp)\n"
"sw s7, 4 * 25(sp)\n"
"sw s8, 4 * 26(sp)\n"
"sw s9, 4 * 27(sp)\n"
"sw s10, 4 * 28(sp)\n"
"sw s11, 4 * 29(sp)\n"
"csrr a0, sscratch\n"
"sw a0, 4 * 30(sp)\n"
"mv a0, sp\n"
"call handle_trap\n"
"lw ra, 4 * 0(sp)\n"
"lw gp, 4 * 1(sp)\n"
"lw tp, 4 * 2(sp)\n"
"lw t0, 4 * 3(sp)\n"
"lw t1, 4 * 4(sp)\n"
"lw t2, 4 * 5(sp)\n"
"lw t3, 4 * 6(sp)\n"
"lw t4, 4 * 7(sp)\n"
"lw t5, 4 * 8(sp)\n"
"lw t6, 4 * 9(sp)\n"
"lw a0, 4 * 10(sp)\n"
"lw a1, 4 * 11(sp)\n"
"lw a2, 4 * 12(sp)\n"
"lw a3, 4 * 13(sp)\n"
"lw a4, 4 * 14(sp)\n"
"lw a5, 4 * 15(sp)\n"
"lw a6, 4 * 16(sp)\n"
"lw a7, 4 * 17(sp)\n"
"lw s0, 4 * 18(sp)\n"
"lw s1, 4 * 19(sp)\n"
"lw s2, 4 * 20(sp)\n"
"lw s3, 4 * 21(sp)\n"
"lw s4, 4 * 22(sp)\n"
"lw s5, 4 * 23(sp)\n"
"lw s6, 4 * 24(sp)\n"
"lw s7, 4 * 25(sp)\n"
"lw s8, 4 * 26(sp)\n"
"lw s9, 4 * 27(sp)\n"
"lw s10, 4 * 28(sp)\n"
"lw s11, 4 * 29(sp)\n"
"lw sp, 4 * 30(sp)\n"
"sret\n"
);
}
```
:::
>
執行下列指令：
```c
WRITE_CSR(stvec, (uint32_t) kernel_entry);
```
將 `kernel_entry` 函數的起始位址註冊到 `stvec` 暫存器，設定為 Trap 處理的入口點，當發生中斷或例外（Trap）時，CPU 就會跳到 kernel_entry 開始執行。
### scause、stval、sepc 暫存器介紹與用途
- `scause`：例外或中斷的原因（Supervisor Cause Register）
這個暫存器記錄了觸發 trap（Exception 或 Interrupt）的類型，例如非法指令、存取違規、系統呼叫等。
- `stval`：Exception 或 Interrupt 相關的數值（Supervisor Trap Value Register）
這個暫存器通常存放與 Exception 或 Interrupt 有關的額外資訊，例如發生錯誤的記憶體位址（像是 page fault 時的位址），或是非法指令的內容。
- `sepc`：發生 Exception 時的程式計數器（Supervisor Exception Program Counter）
這個暫存器記錄了發生例外時，CPU 正在執行的指令位址。處理完例外後，通常會根據這個值決定要不要回到原本的程式繼續執行。
### `sscratch` 暫存器
sscratch 的功能就是讓 OS trap handler 可以安全、快速取得或交換 kernel context 指標，最常用來保存 kernel stack base address（sp）。
sscratch 暫存器在這裡是被作者用來暫存例外發生當下的 sp 值（stack pointer），因為一旦執行了 `addi sp, sp, -4 * 31` 之後，原來的 sp 值就丟失了。
```asm
csrw sscratch, sp # 將當前 sp 暫存到 sscratch
addi sp, sp, -4 * 31 # 調整 sp 分配堆疊空間
... # 存放必要通用暫存器至堆疊
csrr a0, sscratch # 從 sscratch 讀回原始的 sp 值
sw a0, 4 * 30(sp) # 將原始 sp 存到堆疊上
... # 還原通用暫存器
lw sp, 4 * 30(sp) # 從堆疊讀回原始 sp (而非從 sscratch)
sret
```
### 測試 Exception
利用 RISC-V 的 pseudo-instruction：`unimp` 來觸發非法指令例外（illegal instruction exception）。
```c
__asm__ __volatile__("unimp");
```
:::info
組譯器會將 unimp 轉換為以下指令：
```asm
csrrw x0, cycle, x0
```
這行指令試圖將 cycle 暫存器的值寫入 x0，同時從 x0 讀出。但由於 cycle 是唯讀（read-only）暫存器，CPU 會判定這是無效指令，並觸發非法指令例外。
:::
## 10. 行程（Process）
:::info
補充：在 C 語言中，函數名稱就是該函數的地址，所以可以直接使用函數名來取得它的地址。
:::
### Create Process
:::info
這邊建立的 Process 它實際的記憶體位址在哪裡？
> 其實最一開始已經將所有行程以陣列 (procs) 的方式宣告在 kernel memory 了，所以 create_process 其實只是在分配這些已宣告好的空間給對應的 proc。
:::
1. 尋找可用的行程槽位：在全域的 procs 陣列中搜尋,找到一個未使用的行程控制區塊。
2. 堆疊初始化：將此 Process 的堆疊指標 (sp) 指向預先配置給此 Process 堆疊的頂端（因為堆疊是由高位址向低位址成長的）。
3. 儲存被呼叫者保存的暫存器 (Callee-saved registers)：在堆疊上預先配置空間並初始化暫存器（ra, s0-s11）。這些值會在**第一次進行 context switch 時被恢復** (指 lw 指令的部分)。
:::info
使用 *-\-sp 表示先遞減指標再寫入，因為堆疊是向低位址成長，所以必須先「騰出空間」(遞減 sp 指標)，才能寫入資料。
:::
4. 初始化 Process 的其他成員。
### Switch Context
假設 proc_a 呼叫 `switch_context`：
1. **保存當前 Process（proc_a）的暫存器**：當 proc_a 呼叫 `switch_context` 時，`switch_context` 就是被呼叫者 (Callee)，所以要保存呼叫 `switch_context` 的函數（proc_a）(Caller) 的 Saved-registers。
2. **切換堆疊指標**：
- `sw sp, (a0)`：保存當前 Process（proc_a）更新後的堆疊指標。
因為 CPU 只有一個 sp 暫存器，但我們有多個 Process，因此需要記錄每個 Process 的堆疊位置 `sp`。這行指令會將當前 Process（proc_a）更新後的 sp 值寫入 `proc_a->sp` 變數中保存，當下次切回 proc_a 時，就能從 `proc_a->sp` 恢復 proc_a 的堆疊位置。
- `lw sp, (a1)`：載入下個 Process （proc_b）的堆疊指標。
此時 CPU 的 sp 已經指向下個 Process （proc_b）的堆疊（proc_b 上次被暫停時的位置）。
3. **恢復下個 Process （proc_b）的暫存器**：後續的 lw 指令從堆疊中恢復下個 Process （proc_b）的 ra, s0-s11 暫存器，最後執行 `ret` 跳轉至下個 Process （proc_b）的 `ra` 指向之位址，繼續下個 Process （proc_b）的執行。
根據上述的說明就可以發現當執行完 `switch_context` 後，就順利切換到另一個 Process 執行了。
目前做到這邊的 `kernel_main` 函數應該長這樣：
```c
void kernel_main(void) {
memset(__bss, 0, (size_t) __bss_end - (size_t) __bss);
WRITE_CSR(stvec, (uint32_t) kernel_entry);
proc_a = create_process((uint32_t) proc_a_entry);
proc_b = create_process((uint32_t) proc_b_entry);
proc_a_entry();
PANIC("unreachable here!");
}
```
可以觀察到是由 `kernel_main()` 去呼叫 `proc_a_entry()` 來測試 Context Switch，不過實際上是由 kernel 與 proc_b 這兩個行程在做 Context Switch。仔細追蹤程式碼發現 proc_a 使用的堆疊 `proc_a->sp` 其實與 kernel 使用的堆疊是同一個區塊，proc_a 完全沒有使用到自己的堆疊空間。
原因就是「由 `kernel_main()` 去呼叫 `proc_a_entry()`」，在本質上 `kernel_main()` 與 `proc_a_entry()` 皆是屬於 kernel 的行程。當 `proc_a_entry()` 呼叫 `switch_context()` 時，保存的是 kernel 的堆疊狀態（因為它們共用同一個堆疊），而非 proc_a 在 `create_process()` 時初始化的獨立堆疊空間。這導致 proc_a 實際上沒有作為一個獨立的行程運作，而是寄生在 kernel 上執行並與 kernel 共用同一個 Context。
### Scheduler 排程器
由於上述因素，我們需要在 `kernel_main()` 建立一個代表 kernel 本身的行程 (idle_proc)，idle_proc 會在開機時建立，並作為 pid 為 0 的特殊行程，然後透過 `switch_context()` 將執行權切換給 proc_a，而不是直接呼叫 `proc_a_entry()`。
在 `switch_context(&idle_proc->sp, &proc_a->sp)` 的過程中：
1. 保存 kernel 的 callee-saved registers (ra, s0~s11) 狀態到 kernel 的堆疊，並將當前的 sp 值儲存到 idle_proc->sp，記錄 kernel 的堆疊狀態。
2. 從 proc_a->sp 載入堆疊指標，切換到 proc_a 的堆疊。
3. 從 proc_a 的堆疊中恢復事先在 `create_process()` 初始化的暫存器值（ra, s0-s11），其中 ra 指向 `proc_a_entry()`。執行 ret 跳轉到 `proc_a_entry()` 開始執行。
這樣 proc_a 就能使用自己獨立的堆疊空間（proc_a->stack），真正作為獨立的行程運作，而非共用 kernel 的堆疊。
為了管理多個行程的切換，我們需要實作一個簡單的排程器。排程器的主要職責就是決定下一個要執行的行程，並透過 `switch_context()` 完成行程切換，如下所示。
`yield()` 就是排程器的實作：
```c
struct process *current_proc; // Currently running process
struct process *idle_proc; // Idle process
void yield(void) {
// Search for a runnable process
struct process *next = idle_proc;
for (int i = 0; i < PROCS_MAX; i++) {
struct process *proc = &procs[(current_proc->pid + i) % PROCS_MAX];
if (proc->state == PROC_RUNNABLE && proc->pid > 0) {
next = proc;
break;
}
}
// If there's no runnable process other than the current one, return and continue processing
if (next == current_proc)
return;
// Context switch
struct process *prev = current_proc;
current_proc = next;
switch_context(&prev->sp, &next->sp);
}
```
:::info
這樣寫會有什麼問題？
```c
void yield(void) {
struct process *next = idle_proc;
for (int i = 0; i < PROCS_MAX; i++) {
if (procs[i].state == PROC_RUNNABLE && procs[i].pid > 0) {
next = &procs[i];
break;
}
}
if (next == current_proc)
return;
struct process *prev = current_proc;
current_proc = next;
switch_context(&prev->sp, &next->sp);
}
```
這樣寫會讓 pid 較大的行程無法被執行到，導致 starvation。
:::
```c
void kernel_main(void) {
memset(__bss, 0, (size_t) __bss_end - (size_t) __bss);
WRITE_CSR(stvec, (uint32_t) kernel_entry);
// create and init idle process
idle_proc = create_process((uint32_t) NULL);
idle_proc->pid = 0; // idle
current_proc = idle_proc;
proc_a = create_process((uint32_t) proc_a_entry);
proc_b = create_process((uint32_t) proc_b_entry);
yield();
PANIC("switched to idle process");
}
```
### 例外處理更新
:::info
sscratch 是 RISC-V 架構中的一個 CSR（Control and Status Register），專門用於在 user mode 和 kernel mode 之間切換時，保存和交換堆疊指標。
:::
作者到目前實作的 process 都是 kernel process。考慮當未來有 user process 時的情境，user process 在 user mode 運行時觸發 trap，此時 `sp` 指向 user stack。而 CPU 需要執行 kernel 的 trap handler 來處理，但在切換到 kernel mode 的過程 (kernel_entry) 中，「**系統並不知道 `kernel sp` 在哪裡**」。
因此，在進行 kernel process 的 context switch 時，需要將即將執行的 kernel process 的 `sp` 更新到 `sscratch` 暫存器中。如此一來，當 user mode 發生 trap 時，系統就可以透過交換當前（User mode）的 `sp` 和 `sscratch` （kernel sp）的值，快速切換到 kernel 的 sp，並將原本發生 Trpa 時的 `user sp` 保存在 `sscratch` 中：
```c
__asm__ __volatile__(
"csrw sscratch, %[sscratch]\n"
:
: [sscratch] "r" ((uint32_t) &next->stack[sizeof(next->stack)])
);
```
另外，在 `kerenl_entry()` 中，kernel 需要將當前 user process 的暫存器狀態傳給 `handle_trap()` 處理。為此，必須將 user process 的暫存器狀態保存到 kernel stack 中，而不是 user stack。
kernel_entry 的處理流程如下：
> The picture was drawn by [buobao](https://hackmd.io/@buobao/1000os).
## 09. 記憶體配置
為接下來 Sv32 Paging 做鋪陳，在 Sv32 分頁機制中，每個 `PAGE_SIZE` 為 4KB（4096 bytes），這是硬體規定的最小記憶體管理單位，所有的記憶體分配和映射都必須以 page 為單位進行，之後會細說 Sv32 分頁機制。因此以 4 KB 為單位使用 `alloc_pages()` 分配 kernel memory (`__kernel_base` ~ `__free_ram_end`)。
使用 `static` 來宣告 `next_paddr` 的目的是要讓它能夠不斷地累加下去，不會被重置回 `__free_ram`。使用以下程式驗證 static 的特性：
```c
#include <stdio.h>
void test_static() {
static int a = 0;
printf("%d, ", a);
a++;
printf("%d, ", a);
}
int main(int argc, const char * argv[]) {
test_static();
test_static();
}
```
預期輸出：0, 1, 1, 2,
## 11. Sv32 分頁機制
> [The RISC-V Instruction Set Manual: Volume II](https://docs.riscv.org/reference/isa/_attachments/riscv-privileged.pdf) Page 133.
> [來聽 Harry H. Porter III 解說 Sv32](https://www.youtube.com/watch?v=oXKg351zd84=1050s)
作者採用 RISC-V 的 Sv32 分頁機制。Sv32 採用兩層分頁表 (Two-level Page Table) 架構，頁框大小為 4 KB [圖一]，而 Virtual Address 與 Physical Address 的寬度分別為 32 Bits 與 34 Bits [圖二]：
圖一：
圖二：
在查表的過程中，虛擬位址被劃分為三個欄位，分別是 `VPN[1]`, `VPN[0]`, `page offset` (頁內偏移) 。首先，使用 `VPN[1]` 作為索引，在第一層分頁表 (根分頁表) 中查找對應的 Entry。接著，根分頁表 Entry 會指向第二層分頁表的位址。然後，使用 `VPN[0]` 作為索引，在第二層分頁表中查找，最終得到該行程對應的實體頁框（Data Page）位址。最後，將實體頁框位址與 `page offset` 組合得到完整的實體位址。而每個分頁表中的 Entry 內容如下 [圖三]：
圖三：
其中，`PPN[1]` 與 `PPN[0]` 組合即為下一層分頁表或實體頁框的頁碼^[1]^，由 `X`, `W`, `R` 位元可以判斷索引到下一層的頁是分頁表或實體頁框，若為全 0，則表示該 Page Table Entry (PTE) 指向的 Page 仍為 Page Table；反之，則為實體頁框 (Data Page)。
> - [1] 頁碼（Page Number）：即「頁起始位址 $\div$ 頁大小」的值。因為每一頁皆以 4096 位元為單位對齊，因此將「頁碼 $\times$ 頁大小」即可得該頁的起始位址。
另外，在 [圖一] 中有部分的 Pages 是灰白的，表示這些 Pages 暫時不在實體位址空間中，也就是說，它們目前沒有對應的實體頁框，可能存放在磁碟上的 swap 空間。當 CPU 試圖存取這些灰白 Pages 時，會觸發 Page Fault，作業系統會再將對應的資料從磁碟上的 swap 空間載入到實體位址空間中，並更新 Page Table 以建立虛擬位址與實體位址的映射關係。
:::info
為什麼 Sv32 要設計兩層 Page Table？
> - 如果使用一層的話：
每個 PTE 記錄 4KB 的 Virtual Page，而一個行程的虛擬位址空間有 4GB，表示一個行程的 Page Table 就要有 4G / 4K = 1M 個 PTE，又一個 PTE 的 size 為 4 Bytes，因此系統對每個行程都要保留 4MB 的空間來存 Page Table，非常浪費 kernel 的記憶體空間。
> - 如果使用三層或更多的話：
對 32-bit 的 Virtual Address 來說太多層，反而增加查表開銷。查一次表等於做一次記憶體 I/O。
:::
### 實作
:::warning
Linker Script 中定義的位址屬於連結階段的「虛擬位址」配置，這些位址僅用於描述程式各段（如 .text、.data、.bss）在虛擬位址空間中的位置，並不代表它們在執行時實際對應的實體記憶體位置。
:::
首先，前面有提到作業系統會為每個行程都建立個別的 Page Table，因此在 Process 的結構體中新增 `Page Table` 的指標，並在 `create_process` 階段中配置行程的根頁表：
```diff
struct process {
int pid;
int state;
vaddr_t sp;
+ uint32_t *page_table;
uint8_t stack[8192];
};
```
```diff
struct process *create_process(uint32_t pc) {
// ...
// Map kernel pages.
+ uint32_t *page_table = (uint32_t *) alloc_pages(1);
// Initialize fields.
proc->pid = i + 1;
proc->state = PROC_RUNNABLE;
proc->sp = (uint32_t) sp;
+ proc->page_table = page_table;
return proc;
}
```
---
#### 定義 PTE
接著，定義 PTE 的結構如下圖 [圖三]：
```c
#define SATP_SV32 (1u << 31)
#define PAGE_V (1 << 0) // "Valid" bit (entry is enabled)
#define PAGE_R (1 << 1) // Readable
#define PAGE_W (1 << 2) // Writable
#define PAGE_X (1 << 3) // Executable
#define PAGE_U (1 << 4) // User (accessible in user mode)
```
其中，`PAGE_V` 表示目前 page table entry (PTE) 指向的 Page 資料是可用還是不可用。`PAGE_R`, `PAGE_W`, `PAGE_X` 是用來辨識 PTE 指向的 Page 是否為 Data Pages，若為全 0，則表示該 PTE 指向的 Page 仍為 Page Table；反之，則為 Data Pages。`PAGE_U` 是用來決定該 page 是否允許 user mode 存取，若為 0，則表示此 page 允許 S-mode 與 M-mode 存取；反之，此 page 僅允許 M-mode 存取。
另外，下圖為 RV32 中的 `satp` 暫存器，將 MODE bit 設為 1，表示啟用 Sv32 分頁機制，而右邊 22 bits 為「當前行程」的根頁表之實體頁碼 (PPN)。**實體頁碼 (PPN) = 實體頁位址 $\div$ PAGE_SIZE**。
因為 `satp` 是保存當前行程的根頁表之**實體頁碼**，所以當在做 Context Switch 之前，應將下一個行程的根頁表之**實體頁碼**寫入 `satp` 中：
```diff
__asm__ __volatile__(
+ "sfence.vma\n"
+ "csrw satp, %[satp]\n"
+ "sfence.vma\n"
"csrw sscratch, %[sscratch]\n"
:
+ : [satp] "r" (SATP_SV32 | ((uint32_t) next->page_table / PAGE_SIZE)),
[sscratch] "r" ((uint32_t) &next->stack[sizeof(next->stack)])
);
```
其中，`sfence.vma` 指令的目的是清除 TLB Cache：
> TLB（Translation Lookaside Buffer）是一個快取記錄，用來儲存「最近使用過的虛擬頁對應到實體頁的轉譯結果」。在位址轉譯過程中，MMU（Memory Management Unit）會先查詢 TLB，若命中則直接取得實體頁碼，不需要再去存取分頁表所在的記憶體，因此能大幅減少記憶體存取成本並提升效能。
>
>然而，由於目前的實作並未使用 ASID，因此 TLB 無法識別不同行程的虛擬位址對應關係。為避免新行程誤用前一行程的 TLB 映射，我們必須在 Context Switch 前後執行 sfence.vma，清除或使 TLB 失效，以確保每次位址轉譯都會依照當前行程的 Page Table 重新進行，維持記憶體隔離與系統正確性。
:::info
MMU 是一個電路嗎？他是怎麼存取 Page Table 的（運作方式）？
:::
---
#### Mapping
接下來，會將行程的根分頁表之 PTEs 映射到第二層對應的分頁表，而第二層分頁表之 PTEs 再映射到對應的實體頁表（Data Page）。還記得我們在實作的一開始只配置了行程的根分頁表所需的空間，尚未填入第二層分頁表的實體頁碼，也尚未配置第二層實體頁。
因此，我們接著就要來配置第二層頁表並==將第二層頁表的「實體位址」映射至第一層頁表，同時將 kernel 實體頁（Data Page）的起始位址（`paddr / PAGE_SIZE`）映射至第二層頁表==：
:::warning
**注意：** 在實作中，作者採用讓核心的**虛擬位址與實體位址相同**的設計，位址寬度當然也相同，因此在程式中看到 `paddr == vaddr` 的情況是刻意安排的，使用時需特別留意區分。這樣的設定可以讓分頁機制啟用後，原本核心的程式碼與資料繼續照常運作。
:::
```c
void map_page(uint32_t *table1, vaddr_t vaddr, paddr_t paddr, uint32_t flags) {
if (!is_aligned(vaddr, PAGE_SIZE))
PANIC("unaligned vaddr %x", vaddr);
if (!is_aligned(paddr, PAGE_SIZE))
PANIC("unaligned vaddr %x", paddr);
// Extract VPN[1] (bits 31-22) for first level page table index
uint32_t vpn1 = (vaddr >> 22) & 0x3ff;
if ((table1[vpn1] & PAGE_V) == 0) {
// Create the 2nd page table if it doesn't exist.
uint32_t pt_paddr = alloc_pages(1); // return physical address of the new page table
table1[vpn1] = ((pt_paddr / PAGE_SIZE) << 10) | PAGE_V; // Set first level PTE: PPN (bits 31-10) and Valid bit
}
// Set the 2nd page table entry to map the physical (Data) page.
uint32_t vpn0 = (vaddr >> 12) & 0x3ff;
uint32_t *table0 = (uint32_t *) ((table1[vpn1] >> 10) * PAGE_SIZE);
// Set 2nd PTE: PPN (bits 31-10) and set it as Data page
table0[vpn0] = ((paddr / PAGE_SIZE) << 10) | flags | PAGE_V;
}
```
接著，我們希望能==依據目前行程的虛擬位址空間大小來建立所需的第二層分頁表==，不過到目前為止，我們只實作了 kernel space 的功能，而==我們為了要讓 Kernel Code 可以在任何一個行程中執行==，因此每個行程的核心「虛擬位址空間」（`__kernel_base` 至 `__free_ram_end`）會映射到同一個「實體位址空間」。
根據 Sv32 分頁機制，我們將這段虛擬位址空間劃分成多個虛擬頁框，並映射到對應的實體頁框：
```diff
struct process *create_process(uint32_t pc) {
// ...
// Map kernel pages.
uint32_t *page_table = (uint32_t *) alloc_pages(1);
+ for (paddr_t paddr = (paddr_t) __kernel_base; paddr < (paddr_t) __free_ram_end; paddr += PAGE_SIZE)
+ // fill this process' root page table entry
+ map_page(page_table, paddr, paddr, PAGE_R | PAGE_W | PAGE_X);
// Initialize fields.
// ...
}
```
### 驗證
#### 使用 GDB
1. 修改 `run.sh`：
```diff
# Start QEMU
- $QEMU -machine virt -bios default -nographic -serial mon:stdio --no-reboot -kernel kernel.elf
+ $QEMU -machine virt -bios default -nographic -serial mon:stdio -s -S --no-reboot -kernel kernel.elf
```
> -s: 簡寫形式，等同於 `-gdb tcp::1234`，在 TCP port 1234 上開啟 GDB server，讓 GDB 可以透過這個 port 連接到 QEMU 進行遠端除錯。
>
> -S: 啟動時暫停 (Suspend/Stop at startup)，QEMU 啟動後不會立即執行程式，CPU 會停在第一條指令之前，等待 GDB 連接並下達 continue 指令後才開始執行。
2. 於終端機執行以下命令，64 位元的 GDB 可以除錯 32 位元程式，不會有問題：
```shell
$ riscv64-elf-gdb kernel.elf
```
3. 再新開一個終端機，並執行 `run.sh`，預期會暫停。
4. 將 GDB 連線到本地端的 1234 Port，已開啟遠端除錯，因為目標機器是 QEMU 中的 virt 所以要用遠端除錯：
```shell
(gdb) target remote :1234
```
5. 接著就可以開始追蹤程式碼了！可以參考以下常用命令：
| 指令 | 說明 | 範例 |
|------|------|------|
| `help` | 顯示說明（GDB 內建手冊） | `help breakpoints` |
| `continue` 或 `c` | 繼續執行直到中斷 | |
| `stepi` 或 `si` | 單步執行一條「指令」 | |
| `next` 或 `n` | 單步執行一行「C 程式碼」 | |
| `break` 或 `b` | 設定中斷點 | `b boot`、或 `b 0x80000000` 或 `b kernel.c:50` 跑到 kernel.c 第 50 行停下來、或 `b kernel.c:240 if paddr + 4096 >= 0x84231000` 設暫停條件 |
| `delete` | 移除中斷點 | `delete 1` |
| `info breakpoints` | 列出中斷點 | |
| `info registers` | 顯示暫存器內容 | |
| `x/NFMT address` | 檢查記憶體內容 | `x/16x 0x80000000` |
| `info locals` | 顯示目前函式的區域變數 | |
| `print <變數>` | 顯示變數值 | `p i` 或 `p/x i` 以十六進制表示|
| `set var i=10` | 修改變數 | |
| `quit` 或 `q` | 離開 GDB | |
---
#### 一個行程的「虛擬位址空間」有多少？
我們來計算出一個行程的虛擬位址空間大小，我是用 GDB 查看 `__kernel_base` 與 `__free_ram_end` 的值：
```bash
(gdb) info address __kernel_base
Symbol "__kernel_base" is at 0x80200000 in a file compiled without debugging.
(gdb) p/x (uint32_t) &__kernel_base
$1 = 0x80200000
(gdb) info address __free_ram_end
Symbol "__free_ram_end" is at 0x84231000 in a file compiled without debugging.
(gdb) p/x (uint32_t) &__free_ram_end
$2 = 0x84231000
```
得虛擬位址空間大小為：`0x84231000` - `0x80200000` = `0x4031000` = 67,309,568 Bytes
=> 虛擬位址空間有 67,309,568 $\div$ 4096 = 16,433 個 Pages。
:::info
在 free ram 中，為什麼行程跟行程之間的 Page Table 位址差了 12000~16~ ?
> Sv32 為 Two-Levels Page Tables，而一個行程有 16,433 張 Pages，又一張 Page Table 可以存 1024 張 Data Pages 的索引，所以一個行程共需要 $\lceil$ 16,433 $\div$ 1024 $\rceil$ = 17 張 Leaf Page Tables，再加上一張 Root Page Table，共 18 張 Page Table，而這些 Page Table 都配置在 free ram 中，共佔了 18 $\times$ 4096 = 73,728 = 12000~16~ Bytes
:::
#### 實際追蹤一次虛擬位址：0x80200000 映射到的實體位址
首先，得到當前行程的根分頁表起始位址，使用 GDB 查看 `satp`：
```shell
(qemu) info registers
```
`satp` 的值為 `0x80080255`，根據規格，當前行程的根分頁表起始位址為 `(0x80080255 & 0x3fffff) * 4096 = 0x80255000`。接著，求出 VPN[1] => `(0x80200000 >> 22) & 0x3ff = 512`，用 VPN[1] 索引行程的根分頁表：
```shell
(qemu) xp /x 0x80255000 + 512*4
0000000080255800: 0x20095801
```
根分頁表的 PTE 內容為 `0x20095801`，根據規格，計算出第二層分頁表的起始位址 `(0x20095801 >> 10) * 4096 = 0x80256000`，繼續算出 VPN[0] => `(0x80200000 >> 12) & 0x3ff = 512`，用 VPN[0] 索引第二層分頁表：
```shell
(qemu) xp /x 0x80256000 + 512*4
0000000080256800: 0x2008004f
```
第二層分頁表的 PTE 內容為 `0x2008004f`，根據規格，計算出實體頁框的起始位址 `(0x2008004f >> 10) * 4096 = 0x80200000`，又 page offset => `0x80200000 & 0xfff` 為零，由此可知虛擬位址 `0x80200000` 映射到的實體位址為 `0x80200000`，符合作者所設計的虛實位址相等 `vaddr == paddr` 的映射方式。
## 12. 應用程式
:::info
為什麼 user.ld 的 stack 區段會在 bss 區段中？
> 在一般的作業系統中，分配出來的記憶體區域通常也都會被清成 0。否則，這些記憶體可能還殘留著來自其他程序的敏感資訊（例如憑證），這樣會造成嚴重的安全性問題。
:::
`#pragma once` 是一個預處理器指令，用來防止標頭檔被重複 include。
### 建制應用程式
ELF (Executable and Linkable Format) 是 Linux/Unix 系統上的標準可執行檔格式，包含程式碼、資料以及如何載入和執行的資訊。
> 參考：[The ELF Format](https://ics.uci.edu/~aburtsev/238P/hw/hw3-elf/hw3-elf.html#top)
the ELF file provides two separate views on the data inside the ELF file: a linker view with several details (Sections), and a loader view, a higher level view with less details (Segments).
```bash
# Build the shell (application)
$CC $CFLAGS -Wl,-Tuser.ld -Wl,-Map=shell.map -o shell.elf shell.c user.c common.c
$OBJCOPY --set-section-flags .bss=alloc,contents -O binary shell.elf shell.bin
$OBJCOPY -Ibinary -Oelf32-littleriscv shell.bin shell.bin.o
# Build the kernel
$CC $CFLAGS -Wl,-Tkernel.ld -Wl,-Map=kernel.map -o kernel.elf \
kernel.c common.c shell.bin.o
```
在 Shell Script 中：
- 第一行：編譯 shell 程式
```bash
$CC $CFLAGS -Wl,-Tuser.ld -Wl,-Map=shell.map -o shell.elf shell.c user.c common.c
```
將 shell.c、user.c、common.c 編譯並連結成一個 shell.elf 可執行檔（ELF 格式）。使用 user.ld 作為 linker script，指定程式從 `0x1000000` 開始。
- 第二行：提取 raw binary
```bash
$OBJCOPY --set-section-flags .bss=alloc,contents -O binary shell.elf shell.bin
```
使用 `OBJCOPY` 將 `shell.elf` 轉換成純二進位格式 `shell.bin`，保留 user program 實際的指令與資料（.text, .rodata, .data），移除 ELF 中的 metadata（如 ELF Header、符號表、除錯資訊等）。
:::info
為什麼要 `--set-section-flags .bss=alloc,contents`？
> 正常情況下，`.bss` 段在 ELF 檔案中**不佔實際空間**，因為它只是「未初始化的變數」，載入記憶體時才分配並清零。但在這裡，我們需要把 `.bss` 也包含在 shell.bin 裡，因為：
>1. **簡化 kernel loader**：如果 .bss 不在 shell.bin 中，kernel 就需要「知道」.bss 的位置和大小，然後手動清零。
>2. **統一處理**：把 .bss 也變成「有內容」（全為 0），kernel 就可以「整包複製」shell.bin 到記憶體，不需要額外處理 .bss。
>
> `alloc`：這個 section 需要分配記憶體
`contents`：這個 section 有實際內容（強制 objcopy 把 .bss 當作「有內容」，即使都是 0）
:::
- 第三行：重新包裝成 object file (Binary -> ELF object file)
```bash
$OBJCOPY -Ibinary -Oelf32-littleriscv shell.bin shell.bin.o
```
將上一步萃取出的 shell.bin（純二進制檔）重新包裝成一個「可被 linker 連結的物件檔 `shell.bin.o` 」，並自動生成三個符號：
- `_binary_shell_bin_start` - 指向 shell.bin 開頭
- `_binary_shell_bin_end` - 指向 shell.bin 結尾
- `_binary_shell_bin_size` - shell.bin 檔案的大小
上述提及的「可被 linker 連結的物件檔」是指透過工具（例如 llvm-objcopy）將 raw binary 轉換成 ELF 格式的物件檔，使二進位資料可用符號的方式在程式中引用，這種物件檔會自動產生三個符號，分別表示資料的起點（start）、終點（end）和大小（size）。這樣做的目的是讓 `shell.bin` 可以被 Linker 連結至 kernel，且 kernel 可以透過這些符號來存取嵌入的 shell 程式。使用 `llvm-nm` 命令來查看 shell.bin.o 中的符號表：
```bash
$ llvm-nm shell.bin.o
00010400 D _binary_shell_bin_end
00010400 A _binary_shell_bin_size
00000000 D _binary_shell_bin_start
```
使用 `llvm-readelf -S shell.bin.o` 命令來查看 `shell.bin.o` 的所有 Sections：
```bash
$ llvm-readelf -S shell.bin.o
There are 4 section headers, starting at offset 0x104d0:
Section Headers:
[Nr] Name Type Address Off Size ES Flg Lk Inf Al
[ 0] NULL 00000000 000000 000000 00 0 0 0
[ 1] .strtab STRTAB 00000000 000034 00005c 00 0 0 1
[ 2] .symtab SYMTAB 00000000 000090 000040 10 1 1 4
[ 3] .data PROGBITS 00000000 0000d0 010400 00 WA 0 0 1
Key to Flags:
W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
L (link order), O (extra OS processing required), G (group), T (TLS),
C (compressed), x (unknown), o (OS specific), E (exclude),
R (retain), p (processor specific)
```
使用 `llvm-readelf -s shell.bin.o` 命令來查看符號在哪個 Section：
```bash
$ llvm-readelf -s shell.bin.o
Symbol table '.symtab' contains 4 entries:
Num: Value Size Type Bind Vis Ndx Name
0: 00000000 0 NOTYPE LOCAL DEFAULT UND
1: 00000000 0 NOTYPE GLOBAL DEFAULT 3 _binary_shell_bin_start
2: 00010400 0 NOTYPE GLOBAL DEFAULT 3 _binary_shell_bin_end
3: 00010400 0 NOTYPE GLOBAL DEFAULT ABS _binary_shell_bin_size
```
其中，`Ndx` 欄位表示符號所在的 Section，可以發現 <start>, <end> 都在 .data section，而其 Value 值則表示該符號在其對應區段中的相對位址。
:::info
那些如 `_binary_<filename>_<副檔名>_start` 等三個的符號是怎麼產生的？
> 這要從 `OBJCOPY` 這個指令說起，作者使用的是 [llvm-objcopy](https://rocm.docs.amd.com/projects/llvm-project/en/docs-7.0.2/LLVM/llvm/html/CommandGuide/llvm-objcopy.html?utm_source=chatgpt.com)，它不只是單純的**格式轉換**工具，它還具備多種功能，包括 **section 操作**、**符號處理**（如：第二行）、**載入位址調整**等。==當使用 objcopy -Ibinary -Oelf<format> 將純二進位轉換成 ELF object file 時，objcopy 就會自動生成三個符號==：
>- \_binary\_<檔名>\_<副檔名>\_start
>- \_binary\_<檔名>\_<副檔名>\_end
>- \_binary\_<檔名>\_<副檔名>\_size
>
> 這些符號遵循命名規則：\_binary\_<檔名>\_<副檔名>_<start/end/size>，檔名中的 `.` 會被替換成 `_`。另外，==<format>== 可以參考 [llvm-objcopy](https://rocm.docs.amd.com/projects/llvm-project/en/docs-7.0.2/LLVM/llvm/html/CommandGuide/llvm-objcopy.html?utm_source=chatgpt.com#supported-formats) 列出的格式。
:::
- 第四行：編譯並連結 kernel
```bash
$CC $CFLAGS -Wl,-Tkernel.ld -Wl,-Map=kernel.map -o kernel.elf \
kernel.c common.c shell.bin.o
```
將 `kernel.c`、`common.c` 和 `shell.bin.o` 編譯並連結成最終的 `kernel.elf`，此時 `shell.bin` 的內容就會被嵌入在 `kernel.elf` 中，kernel 可以用 `_binary_shell_bin_start` 來找到並載入 shell 程式。
## 13. 使用者模式
書中提到的「應用程式執行映像」實際上是指在應用程式章節中，從 shell.elf 擷取出應用程式的純指令和資料的部分，也就是由 shell.elf 反組譯出來的純程式碼和資料的部分，不包含 ELF header 及 metadata。
接下來，獲取這個應用程式映像的「起始位址」以及「大小」，以便在建立行程時能夠讓行程知道要運行的使用者程式是從哪裡開始的：
```c
extern char _binary_shell_bin_start[], _binary_shell_bin_size[];
```
其中，`_binary_shell_bin_start` 為嵌入在 `kernel.elf` 裡的 `shell.bin`（映像）之起始位址。核心程式透過 `_binary_shell_bin_<start/end/size>` 符號取得映像的範圍和內容，接著我們用 gdb 查看 `_binary_shell_bin_start` 的位址（位址會因程式碼的長度不同而有所不同）：
```shell
(gdb) p /x &_binary_shell_bin_start
$1 = 0x802009c8
```
:::info
為什麼在 shell.bin 中，從 `0x80200c18` 位址開始以下都是零？
```shell
(gdb) x /2048x 0x802009c8
0x802009c8: 0x01010537 0x25050513 0x2011812a 0xa0012011
0x802009d8: 0x8082a001 0x962aca11 0x871386aa 0x80230016
0x802009e8: 0x86ba00b6 0xfec71be3 0xce098082 0x86aa962a
0x802009f8: 0x0005c703 0x87930585 0x80230016 0x86be00e6
0x80200a08: 0xfec798e3 0xc6038082 0x86aa0005 0x0585ce01
0x80200a18: 0x0023872a 0xc60300c7 0x06930005 0x05850017
0x80200a28: 0xfa658736 0x00068023 0x46038082 0xca190005
0x80200a38: 0xc6830505 0x17630005 0x460300d6 0x05850005
0x80200a48: 0xfa650505 0x0005c503 0x40a60533 0x711d8082
0x80200a58: 0xdc22de06 0xd84ada26 0xd452d64e 0xd05ad256
0x80200a68: 0xcc62ce5e 0xc86aca66 0x842ac66e 0xccc2cabe
0x80200a78: 0xc2aecec6 0xc6b6c4b2 0x00c8c8ba 0x02500a13
0x80200a88: 0x07200913 0x4aa54c29 0xccccd5b7 0x07300b13
0x80200a98: 0x07800b93 0x8d13c42a 0x0cb7ccd5 0x8c930100
0x80200aa8: 0xa021238c 0x12050763 0x45030405 0x07630004
0x80200ab8: 0x03630145 0x3f311205 0xbfc50405 0x00144503
0x80200ac8: 0x44630405 0x08e302a9 0x0593ff45 0x1be30640
0x80200ad8: 0x4522fcb5 0x00450593 0x2d83c42e 0xc8630005
0x80200ae8: 0x45050a0d 0x0d8de563 0x0063a85d 0x1de30965
0x80200af8: 0x4522fb75 0x00450593 0x4104c42e 0x01c4d513
0x80200b08: 0x45039566 0x35f10005 0x00449513 0x95668171
0x80200b18: 0x00054503 0x95133d7d 0x81710084 0x45039566
0x80200b28: 0x3d450005 0x00c49513 0x95668171 0x00054503
0x80200b38: 0x9513354d 0x81710104 0x45039566 0x3d510005
0x80200b48: 0x01449513 0x95668171 0x00054503 0x95133559
0x80200b58: 0x81710184 0x45039566 0x3da50005 0x94e688bd
0x80200b68: 0x0004c503 0x040535bd 0x4522b789 0x00450593
0x80200b78: 0x4104c42e 0x0004c503 0xf20508e3 0x75130485
0x80200b88: 0x3d810ff5 0x0004c503 0xf9750485 0x0513bf31
0x80200b98: 0x358102d0 0x41b00db3 0xea634505 0x1593018d
0x80200ba8: 0x050e0015 0xd5b3952e 0xeae302ad 0x84aafeba
0x80200bb8: 0x02add9b3 0x03098513 0x0ff57513 0x85333d19
0x80200bc8: 0x8db30299 0xb53340ad 0x810d03a4 0xff84f1e3
0x80200bd8: 0x0513bde1 0x3bf50250 0x546250f2 0x594254d2
0x80200be8: 0x5a2259b2 0x5b025a92 0x4c624bf2 0x4d424cd2
0x80200bf8: 0x61254db2 0x00008082 0x33323130 0x37363534
0x80200c08: 0x62613938 0x66656463 0x00000000 0x00000000
0x80200c18: 0x00000000 0x00000000 0x00000000 0x00000000
0x80200c28: 0x00000000 0x00000000 0x00000000 0x00000000
0x80200c38: 0x00000000 0x00000000 0x00000000 0x00000000
0x80200c48: 0x00000000 0x00000000 0x00000000 0x00000000
0x80200c58: 0x00000000 0x00000000 0x00000000 0x00000000
......
```
> 那些零為 user program 的 Stack 段，可以用 `_binary_shell_bin_end` 與 Stack Size 回推得知：
> ```shell
>(gdb) p /x &_binary_shell_bin_end
>$2 = 0x80210c18
>```
> 又 user program 的 stack 大小為 64KB (`0x10000` Bytes)，所以 stack 的起始位址為 `0x80210c18 - 0x10000 = 0x80200c18`，可以在記憶體 dump 中觀察到從 `0x80200c18` 開始就都是全零，這段正是 Zero-initialized 的 stack 區段。
>
>另外，在 `0x80200c18` 前一個 Word（`0x80200c08`）後 8 Bytes 也是零，這些是 Linker 為了確保 Stack 16-Byte Alignment 而產生的 Padding Bytes.
:::
有了使用者程式映像（shell.bin）在 kernel.elf 中的起始位址與大小後，當我們在建立行程時，我們就可以使用 `memcpy` 將使用者程式映像「複製」到實體記憶體（free ram）中，完成使用者程式的載入步驟。
:::info
為什麼要將 user process 嵌入在 kernel process 中？
> 之所以要把使用者程式嵌入 kernel.elf，是因為目前的作業系統尚未具備檔案系統，無法從外部儲存設備讀取獨立的可執行檔。因此，將 user program 打包進 kernel 便成為最簡單的方式。Kernel 可以藉此取得使用者程式的原始內容，並在建立新行程時複製一份副本到對應的行程實體位址空間中，讓每個行程都能有自己的使用者程式映像。
:::
對於 CPU 而言，使用者程式的起始位址必須出現在 user.ld 所定義的位置（`0x1000000`），而為了讓行程的實體頁框對應到這個虛擬位址，我們需要先定義 `USER_BASE` 如下：
```c
// The base virtual address of an application image.
// This needs to match the starting address defined in `user.ld`.
#define USER_BASE 0x1000000
```
在 Mapping User page 時，先在實體記憶體（free ram）中配置實體頁框，並將位於 kernel.elf 中的使用者程式映像「複製」到這些新配置的實體頁框中。接著，將這些實體頁框映射到以 `USER_BASE` 為起點的「使用者虛擬位址空間」：
```c
for (uint32_t off = 0; off < image_size; off += PAGE_SIZE) {
paddr_t page = alloc_pages(1);
// Handle the case where the data to be copied is smaller than the
// page size.
size_t remaining = image_size - off;
size_t copy_size = PAGE_SIZE <= remaining ? PAGE_SIZE : remaining;
// Fill and map the page.
memcpy((void *) page, image + off, copy_size);
map_page(page_table, USER_BASE + off, page,
PAGE_U | PAGE_R | PAGE_W | PAGE_X);
}
```
:::warning
如果直接映射使用者程式映像（shell.bin）而沒有進行複製，那麼執行相同應用程式的多個行程將會共用相同的實體頁面，這會破壞記憶體的隔離機制。
:::
最後，修改呼叫 `create_process` 的函式 kernel_main，讓它在建立行程時能取得使用者程式映像的起始位址與大小：
```diff
void kernel_main(void) {
memset(__bss, 0, (size_t) __bss_end - (size_t) __bss);
WRITE_CSR(stvec, (uint32_t) kernel_entry);
+ idle_proc = create_process(NULL, 0);
idle_proc->pid = 0;
current_proc = idle_proc;
+ create_process(_binary_shell_bin_start, (size_t) _binary_shell_bin_size);
yield();
PANIC("switched to idle process");
}
```
接著我嘗試建立兩個行程，我想知道這兩個行程在實體記憶體中的 layout 長什麼樣：
```diff
void kernel_main(void) {
// ...
create_process(_binary_shell_bin_start, (size_t) _binary_shell_bin_size);
+ create_process(_binary_shell_bin_start, (size_t) _binary_shell_bin_size);
yield();
PANIC("unreachable here!");
}
```
首先，會先建立 idle process，它並沒有 user program，所以就只有配置 17 + 1 個頁表給它 Mapping kernel，於分頁表那章提過了。接著，建立第一個行程，一樣會先配置 kernel
### 切換使用者模式
首先，先了解 sstatus 這個 CSR 中的 SPP (Supervisor Previous Privilege) bit，參考 RISC-V 規格書 [12.1.1. Supervisor Status Register (sstatus)](https://riscv.github.io/riscv-isa-manual/snapshot/privileged/#sstatus:~:text=When%20an%20SRET%20instruction%20(see%20Section%203.3.2)%20is%20executed%20to%20return%20from%20the%20trap%20handler%2C%20the%20privilege%20level%20is%20set%20to%20user%20mode%20if%20the%20SPP%20bit%20is%200)：
> When an `SRET` instruction is executed to return from the trap handler, the privilege level is set to user mode if the SPP bit is 0, or supervisor mode if the SPP bit is 1; SPP is then set to 0.
由此可知，作者透過 `SRET` 指令來完成模式的轉換，那在切換模式前，需要寫入兩個 CSR：
- 設定 `sepc` 暫存器，指定切換到 U-Mode 時的程式計數器（program counter）位置。也就是說，這是 sret 執行後會跳躍到的位址。
- 設定 `sstatus` 暫存器中的 SPIE 位元。啟用這個位元表示進入 U-Mode 時會允許硬體中斷，並在發生中斷時跳躍到 stvec 中指定的中斷處理函式（kernel_entry）。
:::info
- 當在 user mode 發生 trap 時，是怎麼切換成 supervisor mode？
參考：[rv32emu -> _trap_handler](https://github.com/sysprog21/rv32emu/blob/master/src/emulate.c#L1369)
> 由硬體自動完成，硬體會：
>- 將 sepc 改成 user mode 發生中斷時的 PC
>- 記錄跟 Exception 或 Interrupt 種類與錯誤有關的值到 scause 與 stval 暫存器。
>- 將 sstatus.SPP bit 設為 0，表示 trap 來自 U-mode。
>- 將 PC 改為註冊在 stvec 中的 trap handler。
- 那硬體是怎麼知道現在是 U-mode 還是 S-mode ?
https://stackoverflow.com/questions/60285195/how-the-risc-v-hw-can-determine-the-privilege-level
- 換成 supervisor mode 後，又是怎麼將 PC 改成在 user mode 被中止時的下個指令位址？
> 參考規格書 [12.1.7. Supervisor Exception Program Counter (sepc) Register](https://riscv.github.io/riscv-isa-manual/snapshot/privileged/#:~:text=When%20a%20trap%20is%20taken%20into%20S%2Dmode%2C%20sepc%20is%20written%20with%20the%20virtual%20address%20of%20the%20instruction%20that%20was%20interrupted%20or%20that%20encountered%20the%20exception.%20Otherwise%2C%20sepc%20is%20never%20written%20by%20the%20implementation%2C%20though%20it%20may%20be%20explicitly%20written%20by%20software.)：When a trap is taken into S-mode, sepc is written with the virtual address of the instruction that was interrupted or that encountered the exception.
- 為甚麼在 S-mode 時，無法使用 `(gdb) x /10wx 0x1000000` 來看 virtual space 所存資料?
> 因為 `0x1000000` 這個虛擬位址在經過查表後，對應到的 Page Table Entry 的 U bit 為 1，表示該 Page 僅允許 U-mode 存取，因此在 S-mode 時無法存取。仔細觀察在 create process 函式中傳入 map_page 的 flag 參數有 `PAGE_U`。
```c
// Map user pages.
for (uint32_t off = 0; off < image_size; off += PAGE_SIZE) {
paddr_t page = alloc_pages(1);
// Handle the case where the data to be copied is smaller than the
// page size.
size_t remaining = image_size - off;
size_t copy_size = PAGE_SIZE <= remaining ? PAGE_SIZE : remaining;
// Fill and map the page.
memcpy((void *) page, image + off, copy_size);
map_page(page_table, USER_BASE + off, page,
PAGE_U | PAGE_R | PAGE_W | PAGE_X);
}
```
- 切換成 U-mode 之後，`sstatus` 為 `0x22`，為甚麼 SIE bit 會是 1 ? 我們明明只有在 user_entry 設 SPIE bit 為 1
> user_entry 在執行 `SRET` 之前，有先將 sstatus.SPIE bit 設為 1。參考 RISC-V 規格書 [12.1.1. Supervisor Status (sstatus) Register](https://riscv.github.io/riscv-isa-manual/snapshot/privileged/#:~:text=The%20SIE%20bit,set%20to%201.)：When an `SRET` instruction is executed, SIE is set to SPIE, then SPIE is set to 1.
:::
```bash
(gdb) add-symbol-file
add-symbol-file takes a file name and an address
(gdb) add-symbol-file shell.elf 0x1000000
add symbol table from file "shell.elf" at
.text_addr = 0x1000000
(y or n) y
Reading symbols from shell.elf...
(gdb) b user_entry
Breakpoint 1 at 0x802000f2: file kernel.c, line 123.
(gdb) c
Continuing.
Breakpoint 1, user_entry () at kernel.c:123
123 __asm__ __volatile__(
(gdb) info registers $sstatus
sstatus 0x80006000 -2147459072
(gdb) s
start () at user.c:16
16 __asm__ __volatile__(
(gdb) s
main () at shell.c:3
3 void main(void) {
(gdb) s
4 *((volatile int *) 0x80200000) = 0x1234;
(gdb) info registers $ra
ra 0x100000c 0x100000c <start+12>
(gdb) info registers $sstatus
sstatus 0x22 34
(gdb) info registers $stvec
stvec 0x80200054 -2145386412
(gdb) info registers $sepc
sepc 0x1000000 16777216
(gdb) info registers $pc
pc 0x1000018 0x1000018 <main+10>
(gdb) s
kernel_entry () at kernel.c:41
41 __asm__ __volatile__(
(gdb) info registers $pc
pc 0x80200054 0x80200054 <kernel_entry>
(gdb) info registers $sepc
sepc 0x1000018 16777240
(gdb)
```
## 14. 系統呼叫
### System call 運作流程
在 U-mode 執行 ecall (Environment call) 指令觸發 trap 進入 S-mode 時，硬體會將：
- `sstatus.SPP` 設為 0，表示前一個發生 trap 的 mode 是 U-mode。
> 參考 [12.1.1. Supervisor Status (sstatus) Register](https://riscv.github.io/riscv-isa-manual/snapshot/privileged/#:~:text=When%20a%20trap%20is%20taken%2C%20SPP%20is%20set%20to%200%20if%20the%20trap%20originated%20from%20user%20mode)
- `sstatus.SPIE` 設為 `sstatus.SIE` 且 `sstatus.SIE` 設為 0，用來 disable interrupt。
> 參考 [12.1.1. Supervisor Status (sstatus) Register](https://riscv.github.io/riscv-isa-manual/snapshot/privileged/#:~:text=When%20a%20trap%20is%20taken%20into%20supervisor%20mode%2C%20SPIE%20is%20set%20to%20SIE%2C%20and%20SIE%20is%20set%20to%200.)
- `scause` 設為 8，表示 trap 為 Environment call from U-mode。
> 參考 [12.1.8. Supervisor Cause (scause) Register](https://riscv.github.io/riscv-isa-manual/snapshot/privileged/#scause)
- `pc` 設為 `stvec.field` 中的值，這邊我們實作的是 Direct Mode，也就是當發生 trap 時，就跳轉到註冊在 BASE field 中的 kernel_entry 位址。
> 參考 [12.1.2. Supervisor Trap Vector Base Address (stvec) Register](https://riscv.github.io/riscv-isa-manual/snapshot/privileged/#:~:text=When%20MODE=Direct%2C%20all%20traps%20into%20supervisor%20mode%20cause%20the%20pc%20to%20be%20set%20to%20the%20address%20in%20the%20BASE%20field.)
接著，kernel_entry 的處理流程於行程章節討論過了，就直接到呼叫 handle_trap：
```diff
void handle_trap(struct trap_frame *f) {
uint32_t scause = READ_CSR(scause);
uint32_t stval = READ_CSR(stval);
uint32_t user_pc = READ_CSR(sepc);
+ if (scause == SCAUSE_ECALL) {
+ handle_syscall(f);
+ user_pc += 4;
+ } else {
+ PANIC("unexpected trap scause=%x, stval=%x, sepc=%x\n", scause, stval, user_pc);
+ }
+ WRITE_CSR(sepc, user_pc);
}
```
判斷是 System Call 的 trap，就呼叫 handle_syscall，並傳入 user 的暫存器狀態，此時 handle_syscall 會看 `a3` 暫存器存的 sysno，並呼叫對應的處理函式：
```c
void handle_syscall(struct trap_frame *f) {
switch (f->a3) {
case SYS_PUTCHAR:
putchar(f->a0);
break;
case SYS_GETCHAR:
while (1) {
long ch = getchar();
if (ch >= 0) {
f->a0 = ch;
break;
}
yield();
}
break;
case SYS_EXIT:
printf("process %d exited\n", current_proc->pid);
current_proc->state = PROC_EXITED;
yield();
PANIC("unreachable");
default:
PANIC("unexpected syscall a3=%x\n", f->a3);
}
}
```
Flowchart of System Call Processing：
:::info
為什麼 `getchar` 是回傳 `ret.error` ?
> 參考 RISC-V SPI 文件 [riscv-sbi.pdf](https://github.com/riscv-non-isa/riscv-sbi-doc/releases/download/v2.0/riscv-sbi.pdf)：
>- Chapter 5 Legacy Extension 提到：
> - Nothing is returned in `a1` register.
> - All registers except `a0` must be preserved across an SBI call by the callee.
> - The value returned in `a0` register is SBI legacy extension specific.
>
>而 SBI functions must return a pair of values in a0 and a1, with a0 returning an error code：
>```c
>struct sbiret {
> long error; // a0
> union { // a1
> long value;
> unsigned long uvalue;
> };
>};
>```
> Chapter 5.3. Extension: Console Getchar (EID `#0x02`) 提到：The SBI call returns the byte on success, or -1 for failure.
>
>
> 所以回傳值 sbiret.error 就會是讀取到的字元。
:::
#### 撰寫一個 shell
原本的 shell 並沒有 Backspace 的功能，使用起來有點彆扭，因此我新增了 Backspace 的功能：
```c
#include "user.h"
void main(void) {
while (1) {
prompt:
printf("> ");
char cmdline[128];
int i = 0;
while (true) {
char ch = getchar();
if (ch == '\b' || ch == 127) { // accept Backspace (0x08) and DEL (0x7f)
if (i != 0) {
cmdline[--i] = '\0';
// erase last char on terminal: move back, overwrite with space, move back
putchar('\b');
putchar(' ');
putchar('\b');
}
} else if (i == sizeof(cmdline) - 1) {
printf("\ncommand line too long\n");
goto prompt;
} else if (ch == '\r') {
printf("\n");
cmdline[i++] = '\0';
break;
} else {
cmdline[i++] = ch;
putchar(ch);
}
}
if (strcmp(cmdline, "hello") == 0)
printf("Hello world from shell!\n");
else if (strcmp(cmdline, "exit") == 0)
exit();
else
printf("unknown command: %s\n", cmdline);
}
}
```
## 15. 虛擬磁碟 I/O (VirtIO-blk)
> VirtIO 規格書：[Virtual I/O Device (VIRTIO) Version 1.1](https://docs.oasis-open.org/virtio/virtio/v1.1/virtio-v1.1.html)
VirtIO 有支援模擬多種 IO 裝置，可參考 [5 Device Types](https://docs.oasis-open.org/virtio/virtio/v1.1/cs01/virtio-v1.1-cs01.html#x1-1930005)，作者使用 Block Device 來模擬磁碟。
### VirtIO 裝置簡介
每一種 VirtIO 裝置皆由以下部分組成：
#### Device status field
> 參考 [2.1 Device Status Field](https://docs.oasis-open.org/virtio/virtio/v1.1/virtio-v1.1.html#x1-100001)
Virtio 裝置初始化時，會使用**裝置狀態暫存器**表示初始化的進度。裝置狀態暫存器有以下六個欄位：
- `ACKNOWLEDGE` (1): bit-0
表示 OS 已經找到該設備，並將其識別為有效的 VirtIO 設備。
- `DRIVER` (2): bit-1
表示 OS 知道如何驅動這個設備。（也就是有對應的 Driver）
- `FAILED` (128): bit-7
表示 Guest 端發生了問題，已經放棄該設備。可能的原因包括：內部錯誤、驅動程式因某些原因不喜歡該設備，或者在設備操作期間發生致命錯誤。
- `FEATURES_OK` (8): bit-3
表示驅動程式已經確認了所有它理解的功能特性，功能協商已完成。
- `DRIVER_OK` (4): bit-2
表示驅動程式已經設定完成，準備好驅動該設備。
- `DEVICE_NEEDS_RESET` (64): bit-6
表示設備遇到了無法恢復的錯誤。
驅動程式設計的要求：
- 驅動程式在初始化裝置的過程中，必須根據啟動步驟逐步設定 device status 欄位的對應位元，來標示目前完成了哪些初始化步驟。
- 驅動程式不能清除已設定的 status 位元（除了 reset 時），例如不能把已完成的步驟標成未完成。
- 當驅動程式設定 `FAILED` 位元時，表示初始化失敗，之後若要重新啟動，必須先對裝置重設。
- 當 `DEVICE_NEEDS_RESET` 位元被設備設定後，驅動程式不能確定正在執行中的請求是否完成。良好的實作做法是執行重設來恢復。
virtio 裝置設計的要求：
- 設備在被重設（reset）後，必須將 device status 欄位初始化為 0。
- 初始化進度未達 `DRIVER_OK` 前，設備不得消耗緩衝區（consume buffer）或通知驅動程式任何已使用的 buffer。
- 當設備遇到錯誤且需要重設時，應設定 `DEVICE_NEEDS_RESET` 位元。若 `DRIVER_OK` 已被設定，設備還必須對驅動程式發送「裝置組態變更」通知。
#### Feature Bits
每個 Virtio 裝置會宣告所有支持的 Feature Bits，表示它擁有的功能。
- 在初始化階段，驅動程式（driver）會讀取這些 bits，並回報它願意接受的子集合。若要重新協商則必須重設設備。
> 這裡所說的「子集合」，是指驅動程式根據自身需求，從裝置所提供的所有功能中挑選出要啟用的一部分功能組合，也就是驅動所需功能是裝置宣告功能的子集合。
- 這設計有助於前向和後向的兼容：（前向，對於驅動來說）裝置新功能以新的 bit 發布，舊驅動無法識別，也就不會回報新的 bit；同理，（後向，對於裝置而言）支持新功能的驅動可發現設備沒支援而不啟用。
- Feature Bits 的配置
- 0~23：每種裝置類型專用的功能 bit。
- 24~37：保留給隊列/協商機制的擴充 bit。
- 38 以上：保留給未來擴充使用。
總之，Feature Bits 的設計是為了確保 Virtio 設備與驅動能兼容，不斷演進而不影響既有設備或驅動。
#### Notifications
通知（無論是驅動程式通知設備還是設備通知驅動程式）扮演重要角色。通知分為三種類型：
- Configuration change notification（配置變更通知）
- Available buffer notification（可用緩衝區通知）
- Used buffer notification（已用緩衝區通知）
「配置變更通知」和「已用緩衝區通知」由裝置發送給驅動程式。配置變更通知表示裝置設定空間的內容發生變化；已用緩衝區通知表示某個 Virtqueue 上有 buffer 已被裝置使用（Used Ring）。
「可用緩衝區通知」則由驅動程式發送給裝置，用來告知裝置有新的可用 buffer 已經放入對應的 Virtqueue（Avail Ring）。
#### Device Configuration space
待更新...
#### Virtqueues
在 Virtio 設備上，批次資料傳輸的機制稱為 Virtqueue。每個設備可以有零個或多個 Virtqueue。For example, the simplest network device has one virtqueue for transmit and one for receive.
Virtqueue 運作機制：
- 驅動程式透過將「Available buffer」（描述請求的 buffer，每種裝置描述請求的格式都不同）加入 virtqueue (Avail Ring) 來發送請求給 virtio 設備，並可以選擇觸發「驅動程式事件（Driver Event）」發送「Available buffer notification」給設備。
- virtio 設備在執行請求後，會將「Used buffer」加入 virtqueue (Used Ring)，標記 buffer 為已使用，當然設備也可以選擇觸發「裝置事件（Device Event）」發送「Used buffer notification」給驅動程式。
- 設備會記錄每個它使用過的 Used Buffer（Descriptor Table index），以及記錄裝置寫入 Buffer 的 byte 數量（used length），這兩個資訊會記錄在 Used Entry 中。
- 每個 Virtqueue 含三個部分：
- Descriptor Area：用來描述緩衝區
- Driver Area：驅動程式額外供給設備的資料
- Device Area：設備額外回報給驅動程式的資料
> 在早期規範中，這些部分的名稱分別是 Descriptor Table、Available Ring、Used Ring。
Virtqueue 提供兩種格式：Split Virtqueues 和 Packed Virtqueues。設備及驅動程式可支援其中一種或兩種格式。而在這裡作者使用的是 ==Splite Virtqueue==。
Split virtqueue 由以下三個部分組成：
- Descriptor Table - a.k.a. Descriptor Area
- Available Ring - a.k.a. Driver Area
- Used Ring - a.k.a. Device Area
```c
// Virtqueue.
struct virtio_virtq {
struct virtq_desc descs[VIRTQ_ENTRY_NUM];
struct virtq_avail avail;
struct virtq_used used __attribute__((aligned(PAGE_SIZE)));
int queue_index;
volatile uint16_t *used_index;
uint16_t last_used_index;
} __attribute__((packed));
```
並只允許驅動程式「或」裝置寫入 Virtqueue，不允許兩者同時都在寫入。作者將 Queue Size（VIRTQ\_ENTRY\_NUM）設為 16。而 Split Virtqueue 的最大 Queue Size 值為 32768 Bytes。（參考 [2.6 Split Virtqueues](https://docs.oasis-open.org/virtio/virtio/v1.1/csprd01/virtio-v1.1-csprd01.html#:~:text=The%20maximum%20Queue%20Size%20value%20is%2032768.)）
##### Descriptor Table
> [2.6.5 Descriptor Table](https://docs.oasis-open.org/virtio/virtio/v1.1/csprd01/virtio-v1.1-csprd01.html#x1-320005)
```clike
// Virtqueue Descriptor Table Entry.
struct virtq_desc {
uint64_t addr;
uint32_t len;
uint16_t flags;
uint16_t next;
} __attribute__((packed));
```
*addr* 為實體地址，即描述子指向的 buffer 的實體記憶體位址。buffer 可以透過 *next* 進行鏈結，變成 descrpitor chain，也就是將 buffer 合併為一個大的 buffer。*len* 表示這個 descriptor 描述的 Buffer 大小，而 *flags* 用來說明裝置應如何使用此描述子：
- 是否串接到下一個描述子（VIRTQ\_DESC\_F\_NEXT）
- Buffer 是否可寫（VIRTQ\_DESC\_F\_WRITE）
- 是否使用間接描述子表（VIRTQ\_DESC\_F\_INDIRECT）
```clike
/* This marks a buffer as continuing via the next field. */
#define VIRTQ_DESC_F_NEXT 1 // bit-0
/* This marks a buffer as device write-only (otherwise device read-only). */
#define VIRTQ_DESC_F_WRITE 2 // bit-1
/* This means the buffer contains a list of buffer descriptors. */
#define VIRTQ_DESC_F_INDIRECT 4 // bit-2
```
這邊作者並沒有有使用間接描述子，所以只需定義 NEXT 和 WRITE 即可。
##### Available Ring (Driver Area)
驅動程式使用 available ring 來將 buffer 提供給裝置讀取：環中的每個 entry 都指向一個描述子鏈（descriptor chain）的 head。這個結構僅由驅動程式寫入、裝置讀取。
```clike
// Virtqueue Available Ring.
struct virtq_avail {
uint16_t flags;
uint16_t index;
uint16_t ring[VIRTQ_ENTRY_NUM];
}
```
> 以下欄位只有驅動程式能寫入，裝置只能讀取。
- index 欄位表示驅動程式在環中放入下一個描述子項目的位置（以 queue size 為模取餘數循環），它就像是用來走訪 circular array 的 index。這個欄位從 0 開始，並持續遞增循環。
- 而 flags 的 Least Significant Bit（bit-0）表示 Driver 是否想要被通知。（這個 bit 為 `VIRTQ_AVAIL_F_NO_INTERRUPT`）
> Note: The legacy [Virtio PCI Draft](https://ozlabs.org/~rusty/virtio-spec/virtio-0.9.5.pdf) referred to this structure as `vring_avail`, and the constant as `VRING_AVAIL_F_NO_INTERRUPT`, but the layout and value were identical.
> 參考：[Virtio PCI Draft](https://ozlabs.org/~rusty/virtio-spec/virtio-0.9.5.pdf) | Page 20
- *ring* 就是用來存放 descriptor index 的環形陣列。
驅動程式規範：驅動程式「不可」將 virtq_avail 的 index 欄位遞減（表示沒有辦法「取消」已曝光給裝置的 buffers）。
##### Used Ring (Device Area)
Used ring 是裝置在完成操作後，把 buffer「歸還」給驅動程式的地方，這個結構只由裝置寫入、由驅動程式讀取。
```clike
// Virtqueue Used Ring entry.
struct virtq_used_elem {
uint32_t id;
uint32_t len;
};
// Virtqueue Used Ring.
struct virtq_used {
uint16_t flags;
uint16_t index;
struct virtq_used_elem ring[VIRTQ_ENTRY_NUM];
};
```
環中的每個 entry（`virtq_used_elem`）是一對值（*id*, *len*）：
- *id* 指向已用描述子鏈的 head（這個對應到之前驅動程式放在 available ring 的 entry）。
- *len* 則代表 buffer 實際被寫入的位元組總數。
:::info
virtio 規格書提到：
>Note: len is particularly useful for drivers using untrusted buffers: if a driver does not know exactly how much has been written by the device, the driver would have to zero the buffer in advance to ensure no data leakage occurs.
關於 “untrusted buffers” 是指什麼呢？
> 例如，網路驅動可能會直接將收到的 buffer 交給非特權的使用者應用程式。如果網路裝置沒有覆寫掉原 buffer 內的位元組，就可能將其他程序釋放的記憶體內容泄露給應用程式。
:::
接著，說明 Used Ring 結構：
- index 欄位標示裝置在環中放入下一個描述子條目的位置（以 queue size 為模循環），這個欄位從 0 開始，並持續遞增循環。
- flags
> 參考：[Virtio PCI Card Specication](https://ozlabs.org/~rusty/virtio-spec/virtio-0.9.5.pdf) | Page 20
驅動程式規範：驅動程式對於 device-writable（裝置會寫進去的）buffer，只能信任前 *len*（裝置在 used ring 回報的那個總長度）個 bytes，其後的內容一律不能有任何假設，最好當垃圾資料一樣看待並忽略。
### Block Device
參考 [VirtIO Spec 5.2.2 Virtqueues](https://docs.oasis-open.org/virtio/virtio/v1.1/cs01/virtio-v1.1-cs01.html#x1-2410002) 表示在最基本的配置下，virtio-blk 使用一個編號 0 的 Virtqueue（`requestq`）來處理所有讀寫請求。
參考 [VirtIO Spec 5.2.6 Device Operation](https://docs.oasis-open.org/virtio/virtio/v1.1/cs01/virtio-v1.1-cs01.html#x1-2500006) 說明，使用 `virtio_blk_req` 發送請求到 Virtqueue：
```c
struct virtio_blk_req {
le32 type;
le32 reserved;
le64 sector;
u8 data[];
u8 status;
};
```
- *type*：請求的類別，告訴設備要做什麼操作。
| 值 | 名稱 | 說明 |
|-----|--------------------------|--------------------------|
| 0 | VIRTIO_BLK_T_IN | 讀取：從磁碟讀到記憶體 |
| 1 | VIRTIO_BLK_T_OUT | 寫入：從記憶體寫到磁碟 |
| 4 | VIRTIO_BLK_T_FLUSH | 刷新：確保資料寫入持久儲存 |
| 8 | VIRTIO_BLK_T_GET_ID | 取得設備 ID |
| 11 | VIRTIO_BLK_T_DISCARD | 丟棄：告訴 SSD 這些 sector 不再使用 |
| 13 | VIRTIO_BLK_T_WRITE_ZEROES | 寫零：將指定範圍填零 |
- *reserved*：目前沒有用途，為未來擴充保留。
- *sector*：指定要讀 / 寫磁碟的哪個位置，現代硬碟輕鬆超過 32-bit 能定址的最大值 2TB，所以使用 64-bit。
>sector = 0 -> 磁碟的第 0-511 bytes
>sector = 1 -> 磁碟的第 512-1023 bytes
>sector = $N$ -> 磁碟的第 $N \times 512$ 到 $(N+1)\times512-1$ bytes
- *data*：要讀 / 寫的資料內容，大小需為 512 的倍數，因為磁碟 I/O 的最小單位就是 sector。
- *status*：Driver 須知道操作是否成功，因此 Device 在處理請求後填入的狀態碼。
| 值 |名稱 | 說明 |
|-----|----------|--------------------|
| 0 | VIRTIO_BLK_S_OK | 操作成功 |
| 1 | VIRTIO_BLK_S_IOERR | I/O 錯誤（磁碟損壞、超出範圍等） |
| 2 | VIRTIO_BLK_S_UNSUPP | 不支援的操作類型 |
根據 [5.2.6.4 Legacy Interface: Framing Requirements](https://docs.oasis-open.org/virtio/virtio/v1.1/cs01/virtio-v1.1-cs01.html#:~:text=MUST%20use%20a%20single%208%2Dbyte%20descriptor%20containing%20type%2C%20reserved%20and%20sector%2C%20followed%20by%20descriptors%20for%20data%2C%20then%20finally%20a%20separate%201%2Dbyte%20descriptor%20for%20status.) 對 Legacy Interface 訊息框架的要求，使用傳統介面在做磁碟讀寫時，需將 `virtio_blk_req` 拆成 3 個 Descriptors 來描述請求：
|Descriptor|內容 (來自 virtio_blk_req)| 寫入操作 (OUT) | 讀取操作 (IN) |
|------------|------------------------|------------|-----------|
| Header | type, reserved, sector | Device 讀 | Device 讀|
| Data | data[512] | Device 讀 | Device 寫|
| Status | status | Device 寫 | Device 寫|
:::info
為什麼請求要分成三個 Descriptors？且順序是 Header -> Data -> Status？
>1. **讀寫權限不同**：每個 Descriptor 的存取權限依操作類型而異。
>2. 排序要求：根據 [2.6.4.2 Driver Requirements: Message Framing](https://docs.oasis-open.org/virtio/virtio/v1.1/cs01/virtio-v1.1-cs01.html#:~:text=The%20driver%20MUST%20place%20any%20device%2Dwritable%20descriptor%20elements%20after%20any%20device%2Dreadable%20descriptor%20elements.) 規範，可寫描述符必須放在可讀描述符之後。這解釋了為什麼順序是 Header -> Data -> Status。
:::
#### Block Device Driver 提供資料給 VirtIO-blk
#### Driver 接收來自 Device 的資料
---
### 實作
首先，將 virtio-blk 裝置掛載到 QEMU 上：
```diff
$(QEMU) -machine virt -bios default -nographic -serial mon:stdio --no-reboot \
+ -drive id=drive0,file=lorem.txt,format=raw,if=none \
+ -device virtio-blk-device,drive=drive0,bus=virtio-mmio-bus.0 \
-kernel kernel.elf
```
#### 定義巨集
定義所需巨集，如：裝置的 MMIO Control Registers、初始化用的裝置狀態欄位等等：
- 定義磁區大小：
>依照 [5.2.4 Device configuration layout](https://docs.oasis-open.org/virtio/virtio/v1.1/cs01/virtio-v1.1-cs01.html#:~:text=The%20capacity%20of%20the%20device%20(expressed%20in%20512%2Dbyte%20sectors)%20is%20always%20present.%20The%20availability%20of%20the%20others%20all%20depend%20on%20various%20feature%20bits%20as%20indicated%20above)：Block Device 的容量，以 sector 的大小 512 bytes 為單位。
```clike
#define SECTOR_SIZE 512
```
- 定義 Queue Size：
依照 [2.6 Split Virtqueues](https://docs.oasis-open.org/virtio/virtio/v1.1/cs01/virtio-v1.1-cs01.html#:~:text=Queue%20Size%20corresponds%20to%20the%20maximum%20number%20of%20buffers%20in%20the%20virtqueue4.%20Queue%20Size%20value%20is%20always%20a%20power%20of%202.%20The%20maximum%20Queue%20Size%20value%20is%2032768.) Queue Size 需為 2 的冪，且最大值為 32768。
```clike
#define VIRTQ_ENTRY_NUM 16
```
這表示同時最多可以有 16 個 I/O 請求在處理中，如果送出第 17 個請求，就必須等前面的請求完成並釋放後才能送出。
- 定義 Device Type：
> 依照 [5 Device Types](https://docs.oasis-open.org/virtio/virtio/v1.1/cs01/virtio-v1.1-cs01.html#x1-1930005) 定義 VirtIO 裝置類型的 ID 編號，這邊使用的是 block device。
```clike
#define VIRTIO_DEVICE_BLK 2
```
- 定義 Virtio 裝置在 QEMU virt 中的實體記憶體映射區域：
> 依照 [qemu/hw/riscv/virt.c](https://github.com/qemu/qemu/blob/master/hw/riscv/virt.c#L82) 將 virtio 裝置定義在 `0x10001000` 且大小為 `0x1000` bytes，這塊記憶體區域用於 VirtIO 裝置的 MMIO（Memory-Mapped I/O）控制暫存器訪問，Driver 或 Device 會通過讀寫這個地址範圍來控制 VirtIO 裝置。
```clike
#define VIRTIO_BLK_PADDR 0x10001000
```
- 定義 MMIO Control Registers：
> 依照 virtio 規格書 [4.2.4 Legacy interface](https://docs.oasis-open.org/virtio/virtio/v1.1/cs01/virtio-v1.1-cs01.html#x1-1560004) 的表格查看對應 MMIO 裝置控制暫存器相對 `VIRTIO_BLK_PADDR` 的 Offset：
```clike
#define VIRTIO_REG_MAGIC 0x00
#define VIRTIO_REG_VERSION 0x04
#define VIRTIO_REG_DEVICE_ID 0x08
#define VIRTIO_REG_QUEUE_SEL 0x30
#define VIRTIO_REG_QUEUE_NUM_MAX 0x34
#define VIRTIO_REG_QUEUE_NUM 0x38
#define VIRTIO_REG_QUEUE_ALIGN 0x3c
#define VIRTIO_REG_QUEUE_PFN 0x40
#define VIRTIO_REG_QUEUE_READY 0x44
#define VIRTIO_REG_QUEUE_NOTIFY 0x50
#define VIRTIO_REG_DEVICE_STATUS 0x70
#define VIRTIO_REG_DEVICE_CONFIG 0x100
```
這邊只定義 Driver 會用到的 MMIO 裝置控制暫存器。
- 定義初始化用的裝置狀態欄位：
>依照 virtio 規格書 [2.1 Device Status Field](https://docs.oasis-open.org/virtio/virtio/v1.1/cs01/virtio-v1.1-cs01.html#x1-100001)
```clike
#define VIRTIO_STATUS_ACK 1
#define VIRTIO_STATUS_DRIVER 2
#define VIRTIO_STATUS_DRIVER_OK 4
#define VIRTIO_STATUS_FEAT_OK 8
```
這邊也只定義 Driver 會用到的裝置狀態。
- 定義 Available Ring 及 Descriptor Table Entry 會用到的 flags：
>依照 virtio 規格書：
>- [2.6.5 The Virtqueue Descriptor Table](https://docs.oasis-open.org/virtio/virtio/v1.1/cs01/virtio-v1.1-cs01.html#x1-320005)
>- [2.6.6 The Virtqueue Available Ring](https://docs.oasis-open.org/virtio/virtio/v1.1/cs01/virtio-v1.1-cs01.html#x1-380006)
```clike
#define VIRTQ_DESC_F_NEXT 1
#define VIRTQ_DESC_F_WRITE 2
#define VIRTQ_AVAIL_F_NO_INTERRUPT 1
```
- 定義驅動程式發送的請求種類：
>依照 virtio 規格書 [5.2.6 Device Operation
](https://docs.oasis-open.org/virtio/virtio/v1.1/cs01/virtio-v1.1-cs01.html#:~:text=The%20type%20of%20the%20request%20is%20either%20a%20read%20(VIRTIO_BLK_T_IN)%2C%20a%20write%20(VIRTIO_BLK_T_OUT))
```clike
#define VIRTIO_BLK_T_IN 0
#define VIRTIO_BLK_T_OUT 1
```
#### 新增讀取 MMIO 控制暫存器的輔助函數
```c
uint32_t virtio_reg_read32(unsigned offset) {
return *((volatile uint32_t *) (VIRTIO_BLK_PADDR + offset);
}
uint64_t virtio_reg_read64(unsigned offset) {
return *((volatile uint64_t *) (VIRTIO_BLK_PADDR + offset);
}
void virtio_reg_write32(unsigned offset, uint32_t value) {
*((volatile uint32_t *) (VIRTIO_BLK_PADDR + offset)) = value;
}
void virtio_reg_fetch_and_or32(unsigned offset, uint32_t value) {
virtio_reg_write32(offset, virtio_reg_read32(offset) | value);
}
```
傳入的參數為裝置控制暫存器（MMIO）相對 `0x10001000` 的偏移量，volatile 能確保每一次讀寫都去存取記憶體，而非 Cache 或避免被編譯器優化、合併、重排、省略。
:::info
為什麼會有讀取 64 暫存器的輔助函數？是用來讀什麼的呢？
> 在初始化 `virtio-blk` 時，會需要取得磁碟的總容量。根據 [VirtIO Spec 5.2.4 Device configuration layout](https://docs.oasis-open.org/virtio/virtio/v1.1/cs01/virtio-v1.1-cs01.html#:~:text=The%20capacity%20of%20the%20device%20(expressed%20in%20512%2Dbyte%20sectors)%20is%20always%20present.) 規範，裝置容量資訊存放於 Device Configuration Space 的起始 64-bit 欄位（以 512-byte sector 為單位）。由於現代磁碟容量動輒超過 2TB（2^32^ sectors × 512 bytes = 2TB），32-bit 已不敷使用，因此規範採用 64-bit 來表示容量。
:::
#### 將 MMIO 區域的起始位址映射到 Page Pable 中
在啟用分頁後，CPU 的所有記憶體存取都必須經由「虛擬位址」轉譯為實體位址，即使程式要存取的虛擬位址與 MMIO 的實體位址相同，但只要 Page Table 中沒有對應的映射，硬體仍會在查表階段找不到實體位址而觸發 Page Fault，無法存取 MMIO 的控制暫存器。
因此，須將 MMIO 區域的控制暫存器映射進 Page Table，使 CPU 可以透過一般的讀寫指令操作這些暫存器：
```diff
struct process *create_process(const void *image, size_t image_size) {
// ...
// Map kernel pages.
uint32_t *page_table = (uint32_t *) alloc_pages(1); // alloc this process' root page table
// printf("Proc root PT located at: %x\n", page_table);
for (paddr_t paddr = (paddr_t) __kernel_base; paddr < (paddr_t) __free_ram_end; paddr += PAGE_SIZE)
// fill this process' root page table entry
map_page(page_table, paddr, paddr, PAGE_R | PAGE_W | PAGE_X);
+ map_page(page_table, VIRTIO_BLK_PADDR, VIRTIO_BLK_PADDR, PAGE_R | PAGE_W);
// ...
}
```
#### 定義 Virtqueue 結構體
依照之前提到的 Virtqueue 運作機制建立其所需的資料結構：
```c
// Virtqueue Descriptor Table Entry.
struct virtq_desc {
uint64_t addr; // 8 bytes
uint32_t len; // 4 bytes
uint16_t flags; // 2 bytes
uint16_t next; // 2 bytes
} __attribute__((packed));
// Virtqueue Available Ring.
struct virtq_avail {
uint16_t flags; // 2 bytes
uint16_t index; // 2 bytes
uint16_t ring[VIRTQ_ENTRY_NUM]; // 16 * 2 bytes
} __attribute__((packed));
// Virtqueue Used Ring Entry.
struct virtq_used_elem {
uint32_t id; // 4 bytes
uint32_t len; // 4 bytes
} __attribute__((packed));
// Virtqueue Used Ring.
struct virtq_used {
uint16_t flags; // 2 bytes
uint16_t index; // 2 bytes
struct virtq_used_elem ring[VIRTQ_ENTRY_NUM]; // 16 * 8 bytes
} __attribute__((packed));
// Virtqueue.
struct virtio_virtq {
struct virtq_desc descs[VIRTQ_ENTRY_NUM]; // Descriptor Table 16 * 16 bytes
struct virtq_avail avail;
struct virtq_used used __attribute__((aligned(PAGE_SIZE)));
int queue_index;
volatile uint16_t *used_index;
uint16_t last_used_index;
} __attribute__((packed));
```
因為作者並沒有啟用 `VIRTIO_F_EVENT_IDX` 這個功能，因此這與規格書中 [2.6 Split Virtqueues](https://docs.oasis-open.org/virtio/virtio/v1.1/cs01/virtio-v1.1-cs01.html#:~:text=requirements.-,The%20memory%20alignment%20and,8∗(Queue%20Size)) 總結的 Virtqueue 每個部分的大小有點不一樣，省略了 `used_event` 和 `avail_event`。
另外，根據規格書 [1.4 Structure Specifications](https://docs.oasis-open.org/virtio/virtio/v1.1/cs01/virtio-v1.1-cs01.html#:~:text=Many%20device%20and,__attribute__((packed))%20syntax.) 的要求，所有結構都要假設沒有額外的 padding，這是為了避免編譯器在結構成員之間自動插入隱藏的 padding bytes，導致驅動程式與裝置看到的資料格式不一致，進而發生錯誤，因此使用 GNU C 的 `__attribute__((packed))` 編譯器擴充標記來強制結構體以無填充的方式排列。
#### Virtio-blk 裝置初始化
根據 [4.2.3.1.1 Driver Requirements: Device Initialization](https://docs.oasis-open.org/virtio/virtio/v1.1/cs01/virtio-v1.1-cs01.html#:~:text=4.2.3.1.1%20Driver%20Requirements,3.1%C2%A0Device%20Initialization.) 對於 Driver 的規範：
>The driver MUST start the device initialization by reading and checking values from `MagicValue` and `Version`. If both values are valid, it MUST read `DeviceID` and if its value is zero (`0x0`) MUST abort initialization and MUST NOT access any other register.
應先檢查上述的控制暫存器的值來啟動初始化：
```c
void virtio_blk_init(void) {
if (virtio_reg_read32(VIRTIO_REG_MAGIC) != 0x74726976)
PANIC("virtio: invalid magic value");
if (virtio_reg_read32(VIRTIO_REG_VERSION) != 1)
PANIC("virtio: invalid version");
if (virtio_reg_read32(VIRTIO_REG_DEVICE_ID) != VIRTIO_DEVICE_BLK)
PANIC("virtio: invalid device id");
}
```
:::info
不清楚為什麼作者不是檢查 `DeviceID` 是否為零？
:::
參考 [3.1.1 Driver Requirements: Device Initialization](https://docs.oasis-open.org/virtio/virtio/v1.1/cs01/virtio-v1.1-cs01.html#:~:text=Initialization-,The%20driver%20MUST%20follow,the%20device%20is%20“live”.,-If) 初始化裝置：
```c
void virtio_blk_init(void) {
// ... omitted
// 1. Reset the device.
virtio_reg_write32(VIRTIO_REG_DEVICE_STATUS, 0);
// 2. Set the ACKNOWLEDGE status bit: the guest OS has noticed the device.
virtio_reg_fetch_and_or32(VIRTIO_REG_DEVICE_STATUS, VIRTIO_STATUS_ACK);
// 3. Set the DRIVER status bit.
virtio_reg_fetch_and_or32(VIRTIO_REG_DEVICE_STATUS, VIRTIO_STATUS_DRIVER);
// 5. Set the FEATURES_OK status bit.
virtio_reg_fetch_and_or32(VIRTIO_REG_DEVICE_STATUS, VIRTIO_STATUS_FEAT_OK);
// 7. Perform device-specific setup, including discovery of virtqueues for the device
blk_request_vq = virtq_init(0);
// 8. Set the DRIVER_OK status bit.
virtio_reg_write32(VIRTIO_REG_DEVICE_STATUS, VIRTIO_STATUS_DRIVER_OK);
}
```
:::info
其中少了一些初始化步驟，我參考 [3.1.2 Legacy Interface: Device Initialization](https://docs.oasis-open.org/virtio/virtio/v1.1/cs01/virtio-v1.1-cs01.html#:~:text=Initialization-,Legacy%20devices%20did%20not,before%20the%20step%208.,-3.2) 不確定是否因為作者是使用 Legacy Interface 的關係？且規格書也說到 Legacy Interface 不支援 FEATURES_OK，因此我發了 issue [#119](https://github.com/nuta/operating-system-in-1000-lines/issues/119) 詢問作者。
>等待作者回覆中...
:::
另外，第 7 個步驟是初始化 Virtqueue，並將 Virtqueue 在記憶體中的位置告訴裝置：
```c
struct virtio_virtq *virtq_init(unsigned index) {
// Allocate a region for the virtqueue.
paddr_t virtq_paddr = alloc_pages(align_up(sizeof(struct virtio_virtq), PAGE_SIZE) / PAGE_SIZE);
struct virtio_virtq *vq = (struct virtio_virtq *) virtq_paddr;
vq->queue_index = index;
vq->used_index = (volatile uint16_t *) &vq->used.index;
// 1. Select the queue writing its index (first queue is 0) to QueueSel.
virtio_reg_write32(VIRTIO_REG_QUEUE_SEL, index);
// 5. Notify the device about the queue size by writing the size to QueueNum.
virtio_reg_write32(VIRTIO_REG_QUEUE_NUM, VIRTQ_ENTRY_NUM);
// 6. Notify the device about the used alignment by writing its value in bytes to QueueAlign.
virtio_reg_write32(VIRTIO_REG_QUEUE_ALIGN, 0);
// 7. Write the physical number of the first page of the queue to the QueuePFN register.
virtio_reg_write32(VIRTIO_REG_QUEUE_PFN, virtq_paddr);
return vq;
}
```
:::info
這裡發現作者直接將 Virtqueue 的實體位址寫入 `QueueFPN`，但根據 [VirtIO specification 4.2.4 Legacy interface](https://docs.oasis-open.org/virtio/virtio/v1.1/cs01/virtio-v1.1-cs01.html#x1-1560004) 提到：
>- GuestPageSize (0x028): "used by the device to calculate the Guest address of the first queue page (see QueuePFN)"
>- QueuePFN (0x040): "Reading from this register returns the currently used page number of the queue"
這表示 Device 應透過 `QueuePFN` $\times$ `GuestPageSize` 計算出 Virtqueue 的起始位址，因此 `QueuePFN` 應存入 Virtqueue 的 PPN，而非直接寫入實體位址。
那為什麼作者的程式仍可正常執行？
>先釐清 QEMU 是如何取得 Virtqueue 的實體位址。參考 QEMU [virtio-mmio.c](https://github.com/qemu/qemu/blob/master/hw/virtio/virtio-mmio.c)：
>QEMU 透過 `ctz32` (Count Trailing Zero) 將 `GuestPageSize` 轉換為 shift 值。例如 `ctz(4096)` 計算尾部零的數量得到 12 (4096 = 2^12^)。
>```c
>// VIRTIO_MMIO_GUEST_PAGE_SIZE handler
>proxy->guest_page_shift = ctz32(value);
>if (proxy->guest_page_shift > 31) {
> proxy->guest_page_shift = 0;
>}
>```
>隨後將 `QueuePFN` 左移 `guest_page_shift` 位來取得 Virtqueue 的實體位址。
>```c
>// VIRTIO_MMIO_QUEUE_PFN handler
>virtio_queue_set_addr(vdev, vdev->queue_sel,
> value << proxy->guest_page_shift);
>```
> 作者程式能正常執行的關鍵在於當未設定 `GuestPageSize`（即寫入 0）時，`ctz32(0)` 回傳 32，觸發保護條件使 `guest_page_shift` 被設為 0。此時左移 0 位等同於不做任何轉換，`QueuePFN` 的值直接被當作實體位址使用，這正是作者的寫法恰好能運作的原因。
已發送 PR [#120](https://github.com/nuta/operating-system-in-1000-lines/pull/120) 給作者。
:::
Sign in with Wallet
Connect another wallet