Linux 核心專題: 作業系統的設計和開發

執行人: HeatCrab

任務簡述

研讀〈Operating System in 1,000 Lines 〉教學文件，理解在 RISC-V (以 RV32 為主) 如何從無到有建構作業系統核心，隨後投入 Mazu 作業系統的開發。

研讀 Operating System in 1,000 Lines 教學文件的筆記與實驗

GitHub

減少以下內容的項目縮排，用流暢的漢語書寫。

02. RISC-V 101

Calling Convention

Data Model

TYPE LP32 ILP32 LP64 ILP64 LLP64

CHAR 8 8 8 8 8

SHORT 16 16 16 16 16

INT 16 32 32 64 32

LONG 32 32 64 64 32

LONG LONG 64 64 64 64 64

POINTER 32 32 64 64 64

TYPE	LP32	ILP32	LP64	ILP64	LLP64
CHAR	8	8	8	8	8
SHORT	16	16	16	16	16
INT	16	32	32	64	32
LONG	32	32	64	64	32
LONG LONG	64	64	64	64	64
POINTER	32	32	64	64	64

RV32 and RV64

C TYPE	Description	RV32	RV64
char	Character value/byte	1	1
short	Short integer	2	2
int	Integer	4	4
long	Long integer	4	8
long long	Long long integer	8	8
void*	Pointer	4	8
float	Single-precision float	4	4
double	Double-precision float	8	8
long double	Extended-precision float	16	16

RISC-V 的呼叫慣例定義了函式呼叫時暫存器的使用方式與資料型態的對應關係。RV32 和 RV64 的資料模型有所不同（參照上方表格）。在函式參數傳遞時，若參數大小超過指標長度（pointer-word）的兩倍，會以參照（reference）方式傳遞。例如，函式 foo(int, double, long double) 在 RV32 中，int 使用暫存器 a0，double（64 位元）使用 a2-a3（跳過 a1 以符合奇偶暫存器對齊（even-odd　register pair）），而 long double（128 位元）因過大，改以指標存於 a4。在 RV64 中，double 與 long double 的配置更為直接，分別使用 a1 與 a2-a3。

特權指令（Privileged instructions）與 CSR （控制與狀態暫存器）

CSR

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

RISC-V 的特權指令用於管理核心功能，核心操作 CSR 。常見指令包括：

CSRRW（Atomic Read/Write CSR）：交換 CSR 與整數暫存器的值。
CSRRS（Atomic Read and Set Bits in CSR）：讀取 CSR 並根據位元遮罩設置特定位元。
CSRRC（Atomic Read and Clear Bits in CSR）：讀取 CSR 並清除特定位元。

這些指令根據目標暫存器（rd）與來源暫存器（rs1）是否為 x0，決定是否讀取或寫入 CSR。此外，立即數（Immediate）版本的指令（如 CSRRWI、CSRRSI、CSRRCI）使用 5 位元無符號立即數（uimm[4:0]）取代暫存器值。

Register operand

Instruction rd is x0 rs1 is x0 Reads CSR Writes CSR

CSRRW Yes - No Yes

CSRRW No - Yes Yes

CSRRS/CSRRC - Yes Yes No

CSRRS/CSRRC - No Yes Yes
Immediate operand

Instruction rd is x0 uimm = 0 Reads CSR Writes CSR

CSRRWI Yes - No Yes

CSRRWI No - Yes Yes

CSRRSI/CSRRCI - Yes Yes No

CSRRSI/CSRRCI - No Yes Yes

Instruction	rd is x0	rs1 is x0	Reads CSR	Writes CSR
CSRRW	Yes	-	No	Yes
CSRRW	No	-	Yes	Yes
CSRRS/CSRRC	-	Yes	Yes	No
CSRRS/CSRRC	-	No	Yes	Yes

Instruction	rd is x0	uimm = 0	Reads CSR	Writes CSR
CSRRWI	Yes	-	No	Yes
CSRRWI	No	-	Yes	Yes
CSRRSI/CSRRCI	-	Yes	Yes	No
CSRRSI/CSRRCI	-	No	Yes	Yes

讀到後面章節回來查文件發現，沒有找到 CSRR 跟 CSRW 的定義，雖然可以理解這兩個 ~~ISA~~ 的用法語作用。

SRET

ISA-privilged P.58 3.3.2 Trap-Return Instructions

用於從監督者模式（S-mode）返回，通常在例外處理後恢復執行。

內嵌展開組合語言指令（Inline assembly）

內嵌展開組合語言指令允許在 C 程式碼中直接撰寫 RISC-V 組合語言，格式為：

__asm__ __volatile__(
    "assembly" 
    : output operands 
    : input operands 
    : clobbered registers
);

讓我們可以直接操作暫存器或執行特權指令等。

virt

使用 QEMU 的 virt 虛擬平台模擬 RISC-V 環境，支援 RV32 與 RV64，提供標準化的硬體介面，便於作業系統開發與測試。

04. Boot

連結器腳本（Linker Script）

定義了核心的記憶體佈局，確保程式碼、資料與堆疊正確放置。主要內容包括：

基底位址（base address）：設定核心起始位址為 0x80200000，透過 llvm-objdump -d kernel.elf 可驗證程式碼從此位址開始執行。

kernel.elf:	file format elf32-littleriscv

Disassembly of section .text:

80200000 <boot>: <- kernal 的確由 0x80200000 開始執行
80200000: 37 05 22 80  	lui	a0, 0x80220
80200004: 13 05 c5 04  	addi	a0, a0, 0x4c
80200008: 2a 81        	mv	sp, a0
8020000a: 6f 00 a0 01  	j	0x80200024 <kernel_main>
...

.text 區段：使用 KEEP(*(.text.boot)) 保留啟動程式碼（boot 函式），確保其位於 .text 區段開頭，防止連結器在最佳化時丟棄此區段。
.bss 區段：記錄未初始化資料的起始位址（__bss），在 C 中以 extern char[] 定義。
核心堆疊：配置 128KB 空間（. += 128 * 1024），並記錄堆疊頂部位址（__stack_top），供 boot 函式初始化堆疊指標（sp）。
對齊（align）：使用 ALIGN(4) 將目前位址（由位置計數器 . 表示）調整到最接近的下一個 4 位元組對齊的位址，確保所有區段對齊到 4 位元組，符合 RISC-V 架構需求。

參考資料：

__attribute__((naked))

使用 __attribute__((naked)) 定義的函式，編譯器不會產生 prologue 與 epilogue 程式碼，僅包含內嵌展開組合語言。這確保啟動流程完全由開發者控制，適用於低階初始化。

The naked attribute tells the compiler not to generate any other code than the inline assembly. –- 10. Process
Compiler-specific Function, Variable, and Type Attributes

05. Hello World!

SBI

RISC-V Supervisor Binary Interface Specification
SBI is an "API for OS".

ECALL（Environment Call）

ISA-privilged P.57 3.3.1 Environment Call and Breakpoint

核心透過 ecall 指令觸發 SBI 功能，參數由暫存器 a0 至 a7 傳遞：

EID：指定 SBI 的某個 Extension ，儲存在暫存器 a7 。
FID：指定某個 EID Extension下的具體功能，儲存在暫存器 a6 。

例如，函式 putchar 透過 SBI 的 Console Putchar 功能（EID=0, FID=1）輸出字元：

void putchar(char ch) {
    sbi_call(ch, 0, 0, 0, 0, 0, 0, 1);
}

執行 ecall 後，CPU 跳躍至機器模式（M-mode）的例外處理程式（由 mtvec 暫存器指定），OpenSBI 負責處理並輸出字元至除錯控制台。

wfi（Wait for Interrupt）

ISA-privilged P.58 3.3.3 Wait for Interrupt

作用是讓硬體執行緒（hardware thread，hart）進入等待狀態，暫停執行指令，以降低功耗並等待中斷或特定條件來觸發恢復。它適用於所有特權模式，包括機器模式（M-Mode）、監督者模式（S-Mode）及使用者模式（U-Mode），不過若 mstatus 暫存器的 TW 位（Timeout Wait）設為 1，較低特權模式可能引發例外非法指令。作為一 32 位指令，WFI 結構簡單，無需額外參數，透過內嵌展開組合語言嵌入核心程式碼，確保執行時不被編譯器優化移除。

在作業系統中，WFI 常見於核心的閒置迴圈，使用在無任務處理時讓 CPU 進入低功耗狀態。一旦啟用且待處理的中斷發生，例如 Timer 或外部裝置觸發，CPU 會跳躍至陷阱處理器（由 mtvec 暫存器指定），處理完畢後從 WFI 後的下一指令繼續執行。值得注意的是，WFI 的行為不受全局中斷位（mstatus.MIE 或 SIE）或委派暫存器（mideleg）的直接限制，即使中斷被禁用，它仍能檢測本地啟用的待處理中斷，展現高度靈活性。硬體實現上，部分系統可能將 WFI 視為無操作（NOP），不進入等待狀態，因此軟體需檢查中斷暫存器（mip 或 sip），並在無中斷時重新執行 WFI，以確保正確運作。

在教學文件中，WFI 出現於 kernel_main 的無限迴圈，位於初始化輸出（"Hello World!"）之後

for (;;) {
    __asm__ __volatile__("wfi");
}

此設計使核心在完成初步任務後進入閒置狀態，避免 CPU 空轉，同時保持對中斷的反應能力。在 QEMU 模擬環境中，WFI 模擬等待中斷的行為，降低模擬器資源消耗。

在 common.h 中定義的 printf 函式支援可變參數：

void printf(const char *fmt, ...);

... 表示接受任意數量的參數， fmt 決定參數的解釋方式。並使用 #pragma once 防止標頭檔重複包含，提升編譯效率。

Variadic function builtins：Clang Language Extensions

06. C Standard Library

strcpy 的風險
strcpy 函式將來源字串（含結尾空字元）複製到目標緩衝區，但不檢查目標緩衝區大小。若來源字串過長，可能導致緩衝區溢位，引發程式錯誤或安全漏洞。因此，教學文件建議改用更安全的替代函式。

WARNING
The strcpy function continues copying even if src is longer than the memory area of dst. This can easily lead to bugs and vulnerabilities, so it's generally recommended to use alternative functions instead of strcpy. Never use it in production!
For simplicity, we'll use strcpy in this book, but if you have the capacity, try implementing and using an alternative function (strcpy_s) instead.

strcpy_s 的優勢

strcpy_s 是一個邊界檢查函式，需指定目標緩衝區大小（destsz），具備以下優點：

防止緩衝區溢位，確保複製不超過指定大小，保護記憶體安全。
若參數無效（如空指標或緩衝區過小），返回返回非零值，並將目標緩衝區的第一個字元設為零（除非指標無效）。
strcpy_s 明確禁止截尾，如果來源字串過長，它會拒絕複製並返回錯誤，從而避免未終止字串的問題。

strcpy_s 實作

以下是 common.c 中 strcpy_s 的實作，包含參數檢查與安全複製邏輯：

errno_t strcpy_s(char *dst, size_t dstsz, const char *src) {
    if (!dst || !src || dstsz == 0) {
        if (dst && dstsz) dst[0] = '\0';
        return EINVAL;
    }
    size_t src_len = 0;
    const char *s = src;
    while (*s) src_len++, s++;
    src_len++; /* 包含空字元 */
    if (src_len > dstsz) {
        dst[0] = '\0';
        return ERANGE;
    }
    memcpy(dst, src, src_len);
    return 0;
}

此實作先檢查參數有效性，計算來源字串長度（含空字元），確認目標緩衝區足夠大後進行複製，並在錯誤時清空目標緩衝區。

07. Kernal Panic

巨集設計技巧

巨集常用 do {} while(0) 結構封裝多行程式碼，確保巨集展開後行為如同單一語句。這種設計有幾個好處：

統一語法：巨集使用時需加分號，與一般語句一致。
避免語法錯誤：在條件語句（如 if-else）中，展開後不會因缺少大括號導致錯誤，即 dangling else
範圍隔離：巨集內的變數不會與外部衝突。

例如，若未使用 do-while，巨集展開可能導致語法錯誤：

#define MY_MACRO() { printf("Line 1\n"); printf("Line 2\n"); }
if (condition) MY_MACRO(); else printf("Else block\n");

展開後，else 會錯誤地綁定到第二個 printf，造成語法問題。使用 do {} while(0) 可避免此問題。
另外，巨集支援多行定義時，透過反斜線（\）將程式碼連續起來，忽略換行符號，確保程式碼清晰。

08. Exception

例外處理流程（Life of an exception）

檢查與委派暫存器：CPU 檢查 medeleg 暫存器，決定由哪個模式（通常是監督者模式 S-mode 或機器模式 M-mode）處理例外。OpenSBI 預設將使用者模式（U-mode）和 S-mode 的例外轉交給 S-mode 處理。`
保存狀態：CPU 將目前執行狀態（例如程式計數器 PC 與暫存器值）保存到特定的 CSR 中，包括 scause（例外原因）、stval（附加資訊）、sepc（例外指令位址）與 sstatus（狀態）。
跳躍處理程式：CPU 將 PC 設置為 stvec 暫存器中的位址，跳躍至核心的例外處理程式。
處理例外：例外處理程式保存通用暫存器至堆疊（形成 trap frame），然後呼叫 handle_trap 函式，根據 scause 和 stval 分析並處理例外。
恢復狀態並繼續執行：處理完成後，恢復保存的暫存器，執行 sret 指令，從例外發生點繼續執行。

委派暫存器

ISA-privilged P.40 3.1.8 Machine Trap Delegation (medeleg and mideleg) Registers

medeleg 和 mideleg 暫存器控制例外與中斷的委派，支援將特定例外或中斷從 M-mode 轉交給 S-mode 處理。medeleg 管理同步例外，每個位元對應一種例外類型，設為 1 表示轉交給 S-mode。mideleg 則管理中斷，類似地控制委派行為。這兩個暫存器為 WARL（Write Any, Read Legal）類型，硬體只接受合法值。

其中，在文件中提到：

CPU checks the medeleg register to determine which operation mode should handle the exception. In our case, OpenSBI has already configured to handle U-Mode/S-Mode exceptions in S-Mode’s handler.

這表示 OpenSBI 已預先配置 medeleg，將 U-Mode 和 S-Mode 的例外委派到 S-Mode 處理。也就是說， medeleg 的某些位元被設為 1，對應的例外會由 stvec 指向 S-Mode 的 exception handler。

關鍵 CSR

ISA-privilged Ch 12

stvec：儲存 S-mode 例外處理程式的基底位址，需 4 位元組對齊（透過 __attribute__((aligned(4))) 達成）。
scause：記錄例外或中斷原因，高位區分中斷（1）或例外（0），低位為具體原因編碼。
stval：儲存與例外或中斷相關的附加資訊，內容因例外或中斷類型而異。
sepc：記錄例外發生時的 PC 值。
sstatus：決定例外發生後要恢復的操作模式（例如從 S-Mode 返回 U-Mode）。

sscratch：用於臨時儲存堆疊指標（sp），在 kernel_entry 中保存與恢復堆疊狀態。

__asm__ __volatile__(
    "csrw sscratch, sp\n"  // 保存 sp 到 sscratch
    "addi sp, sp, -4 * 31\n"  // 配置 stack space
    ...
    "csrr a0, sscratch\n"  // 從 sscratch 恢復 sp
    "sw a0, 4 * 30(sp)\n"  // 將原始 sp 存入 trap_frame
);

09. Memory Alloctation

在連結器腳本中， . += 64 * 1024 * 1024; 配置 64MB 的記憶體空間，並使用 . = ALIGN(4096) 確保起始位址對齊到 4KB。

. = ALIGN(4096);
__free_ram = .;
. += 64 * 1024 * 1024; /* 64MB */
__free_ram_end = .;

__free_ram 記錄可用記憶體的起始位址，__free_ram_end 標記結束位址。此空間用於動態配置記憶體頁面。

函式 alloc_pages(uint32_t n) 負責配置指定數量的記憶體頁面（每頁 4KB），目前採用簡單的 Bump Allocator 演算法。該演算法從 __free_ram 開始，依序配置連續頁面，並更新目前位址指標。雖然簡單，但無法釋放記憶體，容易造成記憶體浪費。作者建議未來改進為支援記憶體回收的演算法，如 free list。

此 "free" 不是「自由」，而是「空閒」和「有效的空間」

10. Process

行程控制塊（PCB）
透過 struct 定義 PCB 的細節

struct process {
    int pid;             // Process ID
    int state;           // Process state: PROC_UNUSED or PROC_RUNNABLE
    vaddr_t sp;          // Stack pointer
    uint8_t stack[8192]; // Kernel stack (獨立，用於保存 CPU 暫存器、
                         // 返回位址和局部變數，支援上下文切換)
};

行程管理設計

#define PROCS_MAX 8       // Maximum number of processes
struct process procs[PROCS_MAX]; // All process control structures.

透過靜態陣列配置行程控制結構，實現簡化的行程管理。在程式碼中，定義最大行程數量 PROCS_MAX 為 8，並使用全域陣列 struct process procs[PROCS_MAX] 儲存所有行程控制結構。這種設計類似 Linux 核心早期版本採用 NR_TASK 定義任務數量上限並以陣列配置的方式，旨在避免使用動態堆積（heap）配置。透過靜態陣列，行程控制結構的記憶體在編譯時配置於核心的資料分段，無需運行時的動態記憶體管理，簡化了分頁表設置與記憶體保護的複雜性，確保記憶體使用的可預測性與高效性。

上下文切換

Callee-saved registers are registers that a called function must restore before returning.

上下文切換在 switch_context 函式中達成，負責保存與恢復行程的執行狀態。RISC-V 中，callee-saved 暫存器（s0 至 s11）由被呼叫函式負責保存，因此切換時僅需處理這些暫存器。caller-saved 暫存器（如 a0）由呼叫者保存至堆疊，無需額外處理。在 create_process 中，初始化新行程的核心堆疊，預設保存 callee-saved 暫存器與返回位址（ra）。

    // Stack callee-saved registers. These register values will be restored in
    // the first context switch in switch_context.
    uint32_t *sp = (uint32_t *) &proc->stack[sizeof(proc->stack)];
    *--sp = 0;                      // s11
    *--sp = 0;                      // s10
    *--sp = 0;                      // s9
    *--sp = 0;                      // s8
    *--sp = 0;                      // s7
    *--sp = 0;                      // s6
    *--sp = 0;                      // s5
    *--sp = 0;                      // s4
    *--sp = 0;                      // s3
    *--sp = 0;                      // s2
    *--sp = 0;                      // s1
    *--sp = 0;                      // s0
    *--sp = (uint32_t) pc;          // ra

例外處理調整

為支援行程切換，異常處理程式進行了以下改進：

在 yield 函式中，在上下文切換前，將下一個行程的核心堆疊位址寫入 sscratch 暫存器。因為當例外或中斷發生時，系統需要使用可信任的核心堆疊，而不是使用者堆疊（可能指向無效位址，如 0xdeadbeef）。透過預先設置 sscratch，確保例外處理程式能正確切換到下一個行程的核心堆疊。
在 kernel_entry 中，使用 csrrw 指令交換 sp 與 sscratch，立即切換至核心堆疊，保存原始堆疊指標以便恢復。處理完成後，重置 sscratch 為核心堆疊底部，確保後續異常處理的堆疊一致性。

11. Page Table

The table that maps virtual addresses to physical addresses is called a page table. By switching page tables, the same virtual address can point to different physical addresses.

使用 SV32 構成分頁表

SV32 是 RISC-V 指令集架構（ISA）為 32 位元系統設計的虛擬記憶體管理機制，透過分頁表達成虛擬位址到實體位址的映射。它主要應用於監督者模式（Supervisor Mode），確保應用程式與核心的記憶體空間隔離，提升系統安全性和穩定性。SV32 支援記憶體保護與隔離，讓每個行程擁有獨立的虛擬定址空間。

SV32 將 32 位元虛擬位址分為三部分（視覺化程式）：

VPN[1]	VPN[0]	Offset
10 bits	10 bits	12 bits
10 bits	10 bits	12 bits

除了 SV32 ，RISC-V 還提供適用於 64 位元系統的虛擬記憶體模式，例如 Sv39 和 Sv48。Sv39 使用三級分頁表，支援 39 位元虛擬位址，能處理更大的定址空間，適合需要更高記憶體容量的應用場景。Sv48 則進一步擴展至四級分頁表，支援 48 位元虛擬位址，提供更廣泛的記憶體管理能力，適用於高效能伺服器或複雜系統。SV32 的設計在簡化結構與降低複雜度的同時，確保高效的位址轉換與記憶體隔離，特別適合嵌入式系統或輕量級作業系統。

man_page 函式實作

首先，函式根據權限需求設置旗標（flags），指定頁面是否可讀（PAGE_R）、可寫（PAGE_W）或可執行（PAGE_X）。在第一級分頁表中，函式使用第一級索引（vpn1）定位項，將第二級分頁表的實體位址（pt_paddr）轉換為實體頁碼（PPN），方法是除以頁面大小（PAGE_SIZE = 4KB），然後左移 10 位以符合分頁表項（page table entry，PTE）格式，再附加有效位（PAGE_V）標記項可用。接著，函式從第一級項提取 PPN，右移 10 位後乘以頁面大小，轉換為第二級分頁表的實體位址，並將其轉為指標以存取第二級分頁表。在第二級分頁表中，函式根據第二級索引（vpn0）設置目標頁面的映射，將實體位址（paddr）轉為 PPN，結合權限旗標與有效位，完成映射。由於分頁表儲存的是 PPN 而非完整實體位址，所有位址轉換均需除以頁面大小，確保映射精確無誤。

上下文切換中的分頁表同步

為達成行程間的記憶體隔離，核心在 yield 函式中改進上下文切換邏輯，同步交換行程的分頁表，確保每個行程使用獨立的虛擬定址空間。改進的程式碼透過內嵌展開組合語言達成關鍵操作：

__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），避免舊分頁表項干擾後續位址轉換，防止分頁錯誤（page fault）。接著，程式碼將新行程的分頁表位址寫入 satp 暫存器（Supervisor Address Translation and Protection），啟用新分頁表的位址轉換。satp 的值由 Sv32 模式標誌（SATP_SV32）與新行程第一級分頁表位址（next->page_table）組成，後者除以頁面大小轉換為實體頁碼（PPN）。切換分頁表後，再次執行 sfence.vma，確保轉譯後備緩衝區完全更新，後續指令基於新分頁表進行位址轉換，防止不一致行為。最後，程式碼將新行程的核心堆疊頂部位址寫入 sscratch 暫存器，確保例外發生時，核心使用正確的堆疊保存狀態，無需手動查找堆疊位置。

此改進達成了多項功能：

透過分頁表切換確保行程間的記憶體隔離，防止資料混淆與安全漏洞
透過轉譯後備緩衝區同步保證位址轉換一致性；支援例外處理，讓核心在例外發生時使用正確堆疊
啟用 Sv32 分頁模式，為虛擬記憶體管理提供硬體基礎。

若不切換分頁表，所有行程將共用同一記憶體映射，導致嚴重的安全與穩定性問題。

Examining page table contents

(qemu) info registers 

CPU#0
 V      =   0
 pc       80000530
 mhartid  00000000
 ...
 satp     80080255
 ...

計算第一層實體位址：
得到 PPN = (0x80080255 & 0x03FFFFF) * 4096 = 0x80255000
又 VPN[1] = 0x80200000 >> 22 = 512

(qemu) xp /x 0x80255000+512*4
0000000080255800: 0x20095801

計算第二層實體位址：
(0x20095801 >> 10) * 4096 = 0x80256000
接著 VPN[0] = (0x80200000 >> 12) & 0x3ff = 512

(qemu) xp /x 0x80256000+512*4
0000000080256800: 0x2008004f

最後得 PPN = 0x2008004f >> 10 = 0x80200000

接著列出整個第一層級：

(qemu) xp /1024x 0x80255000
0000000080255000: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080255010: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080255020: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080255030: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080255040: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080255050: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080255060: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080255070: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080255080: 0x00000000 0x00000000 0x00000000 0x00000000
...
0000000080255800: 0x20095801 0x20095c01 0x20096001 0x20096401
0000000080255810: 0x20096801 0x20096c01 0x20097001 0x20097401
0000000080255820: 0x20097801 0x20097c01 0x20098001 0x20098401
0000000080255830: 0x20098801 0x20098c01 0x20099001 0x20099401
0000000080255840: 0x20099801 0x00000000 0x00000000 0x00000000
...

在 0000000080255800 開始，也就是第512個，因為核心基底是 0x80200000，且他的 VPN[1] 是 0x200 。

最後檢視一下生成出的分頁表：

(qemu)info mem
vaddr    paddr            size     attr
-------- ---------------- -------- -------
80200000 0000000080200000 00001000 rwx--a-
...

attr：

V（Valid）：分頁表項是否有效。
R（Readable）：允許讀取。
W（Writable）：允許寫入。
X（Executable）：允許執行。
U（User）：允許使用者模式存取。
A（Accessed）：分頁是否被存取過。
D（Dirty）：分頁是否被寫入過。

12. Application

核心使用 llvm-objcopy 將二進位檔案 shell.bin 轉換為目的碼 shell.bin.o，以便鏈結至核心：

$OBJCOPY -Ibinary -Oelf32-littleriscv shell.bin shell.bin.o

透過程式碼，我們可以知道，_binary_shell_bin_start 作為指向 shell.bin 二進位內容的指標和 _binary_shell_bin_size 取得 shell.bin 的大小。

extern char _binary_shell_bin_start[];
extern char _binary_shell_bin_size[];

void main(void) {
    uint8_t *shell_bin = (uint8_t *) _binary_shell_bin_start;
    printf("shell_bin size = %d\n", (int) _binary_shell_bin_size);
    printf("shell_bin[0] = %x (%d bytes)\n", shell_bin[0]);
}

透過 llvm-nm 命令檢查 shell.bin.o：

$ llvm-nm shell.bin.o
00010260 D _binary_shell_bin_end
00010260 A _binary_shell_bin_size
00000000 D _binary_shell_bin_start

接著驗證 _binary_shell_bin_size：

$ llvm-nm shell.bin.o | grep _binary_shell_bin_size
00010260 A _binary_shell_bin_size

$ ls -al shell.bin
-rwxrwxr-x 1 heatcrab heatcrab 66144  6月  2 19:33 shell.bin

$ python3 -c 'print(0x10260)'
66144

最後透過 llvm-objdump 命令確認 .text.start 的確在 0x1000000

$ llvm-objdump -d shell.elf

shell.elf:	file format elf32-littleriscv

Disassembly of section .text:

01000000 <start>:
 1000000: 37 05 01 01  	lui	a0, 0x1010
 1000004: 13 05 05 26  	addi	a0, a0, 0x260
 1000008: 2a 81        	mv	sp, a0
 100000a: 11 20        	jal	0x100000e <main>
 100000c: 11 20        	jal	0x1000010 <exit>

0100000e <main>:
 100000e: 01 a0        	j	0x100000e <main>

01000010 <exit>:
 1000010: 01 a0        	j	0x1000010 <exit>

13. User Mode

行程創建改進

更新 create_process 函式，新增傳入參數，以支援載入二進位映像：

struct process *create_process(const void *image, size_t image_size)

image 指向二進位資料（如 _binary_shell_bin_start），image_size 為資料大小。核心初始化行程的核心堆疊，將返回位址（ra）設為 user_entry，負責切換至使用者模式。

使用者模式切換

接著設置 user_entry 的初始 sp：

*--sp = (uint32_t) user_entry;  // ra

它主要負責切換到使用者模式並跳躍到 USER_BASE

在 kernel.h 中定義：

#define SSTATUS_SPIE (1 << 5)

這個定義是，在 08. Exception 中提到過的 sstatus 這個 CSR 暫存器中的 SPIE 這個位元。它屬於 sstatus 暫存器中的第五位，所以透過左移五位定義。它的目標是處理從 supervisor mode 回到 low-privilaged mode 。它將會在 user_entry 中被使用到。

接著在 kernel.c 中定義 user_entry ：

__attribute__((naked)) void user_entry(void) {
    __asm__ __volatile__(
        "csrw sepc, %[sepc]        \n"
        "csrw sstatus, %[sstatus]  \n"
        "sret                      \n"
        :
        : [sepc] "r" (USER_BASE),
          [sstatus] "r" (SSTATUS_SPIE)
    );
}

csrw sepc, %[sepc] ：將 USER_BASE（0x1000000）的值寫入 sepc 暫存器。

sepc 暫存器指定了當執行 sret 指令時，將跳躍到的 PC 位址。而 USER_BASE 是使用者應用程式的虛擬起始位址（即 shell.bin 的載入位址），確保進入使用者模式後，從應用程式的入口點（0x1000000）開始執行。
csrw sstatus, %[sstatus] ：將 SSTATUS_SPIE 寫入 sstatus 暫存器。

設置 SPIE 為 1 表示在進入使用者模式後，允許恢復之前的監督者模式中斷狀態。

In this book, we don't use hardware interrupts but use polling instead, so it's not necessary to set the SPIE bit. However, it's better to be clear rather than silently ignoring interrupts.
sret ：執行「Supervisor Return」指令，從 S-Mode 返回到 U-Mode 。

最後 create_process 新增一個 for 迴圈來管理使用者分頁。

關於 volatile

在 C 語言中，volatile 關鍵字用於指示編譯器不要對特定變數或記憶體操作進行最佳化，確保程式碼行為符合開發者的意圖。在使用者程式範例中，程式碼透過 volatile 存取特定記憶體位址：

#include "user.h"

void main(void) {
    *((volatile int *) 0x80200000) = 0x1234;
    for (;;);
}

這段程式碼將值 0x1234 寫入記憶體位址 0x80200000，並使用 volatile 修飾指標，保證寫入操作實際執行。volatile 的作用在於防止編譯器因最佳化而移除或重排這一寫入操作，因為該位址可能對應記憶體映射的輸入輸出（memory-mapped I/O）設備，寫入行為必須精確執行以與硬體交互。無限迴圈 for (;;); 確保程式在寫入後持續運行，避免結束。

volatile 的行為與其禁止編譯器最佳化的特性密切相關。編譯器通常會假設變數值不會在程式控制流之外改變，因此可能移除看似無用的讀寫操作。然而，volatile 明確告知編譯器，該變數可能由外部因素修改，必須保留所有讀寫操作並按程式碼順序執行。這對於記憶體映射 I/O 至關重要，因為硬體設備的行為依賴特定的寫入時序與順序。

然而，使用 volatile 存取記憶體映射 I/O（如範例中的 0x80200000）具有平台依賴性，屬於非可攜性用法。該位址在 RISC-V 與 QEMU 環境中可能對應特定設備，但在其他平台或硬體上可能無效或導致未定義行為。因此，開發者需深入了解目標平台的記憶體映射與 C/C++ 實作細節，確保程式碼正確性。

14. System Call

系統呼叫實作

核心定義 syscall 函式，處理使用者程式的系統呼叫請求。使用者程式將系統呼叫編號（sysno）存入暫存器 a3，參數存入 a0、a1、a2，執行 ecall 觸發異常。核心的異常處理程式接管後，根據 a3 執行對應服務，並將返回值存入 a0 傳回使用者程式。

~~Shell 與 Kernel 的比較~~

特性	Shell	Kernel
定義	Shell 是一個使用者介面程式，提供使用者與作業系統（核心）交互的環境。	Kernel 是作業系統的核心，負責管理硬體資源和提供系統服務。
位置	user space 作為使用者與核心之間的橋樑。	kernel space 直接與硬體交互。
功能	1. 接受使用者輸入的命令並解釋執行 2. 提供命令列介面（CLI）或腳本執行 3. 呼叫系統呼叫與核心交互	3. 管理行程、記憶體、硬體設備 2. 處理系統呼叫 2. 排程任務和中斷管理
執行環境	作為使用者行程運行，透過系統呼叫請求核心服務。	運行在 S-mode ，直接控制硬體或透過 SBI 與 M-mode 交互。
類型	多種類型（如 Bourne Shell、Bash、C Shell），內文簡單自定義 shell。	可分為微核心、整塊性核心、混合式核心等設計，教學文件實作的較偏向於整塊性核心。
與硬體的關係	間接，透過核心存取硬體資源。	直接，管理 CPU、記憶體、I/O 設備等硬體資源。
教學文件中的交互	使用者輸入命令（如 `hello`），透過 `getchar` 讀取，`putchar` 輸出結果。	處理系統呼叫，呼叫 `sbi_call` 輸出到 debug console 與硬體交互。

特性 Shell Kernel

定義 Shell 是一個使用者介面程式，提供使用者與作業系統（核心）交互的環境。 Kernel 是作業系統的核心，負責管理硬體資源和提供系統服務。

位置 user space
作為使用者與核心之間的橋樑。 kernel space
直接與硬體交互。

功能 1. 接受使用者輸入的命令並解釋執行
2. 提供命令列介面（CLI）或腳本執行
3. 呼叫系統呼叫與核心交互 3. 管理行程、記憶體、硬體設備
2. 處理系統呼叫
2. 排程任務和中斷管理

執行環境 作為使用者行程運行，透過系統呼叫請求核心服務。運行在 S-mode ，直接控制硬體或透過 SBI 與 M-mode 交互。

類型多種類型（如 Bourne Shell、Bash、C Shell），內文簡單自定義 shell。可分為微核心、整塊性核心、混合式核心等設計，教學文件實作的較偏向於整塊性核心。

與硬體的關係 間接，透過核心存取硬體資源。直接，管理 CPU、記憶體、I/O 設備等硬體資源。

教學文件中的交互 使用者輸入命令（如 hello），透過 getchar 讀取，putchar 輸出結果。處理系統呼叫，呼叫 sbi_call 輸出到 debug console 與硬體交互。

monolithic kernel 不能翻譯為「宏核心」，參見淺談 Microkernel 設計和真實世界中的應用

shell 和 kernel 層級差異太大，沒有比較的必要。

參考 wikipedia ，將 monolithic kernel 的翻譯更正為「整塊性核心」。

根據淺談 Microkernel 設計和真實世界中的應用與 wikipedia 等資料，簡單對 microkernal 與 monolithic kernel 做比較。

特性	Monolithic Kernel (整塊性核心)	Microkernel (微核心)
結構與設計	所有功能運行於 kernel space ，作為單一二進位執行檔以監管者模式執行，應用程式透過系統呼叫交互	核心僅負責基本功能（如定址空間管理、執行緒管理、行程間通訊），服務運行於 user space，透過訊息傳遞交互
設計理念	整合所有組件為單一核心，強調簡單性與高效能	最小化核心功能，模組化服務，強調穩定性與彈性
示例作業系統	GNU/Linux、FreeBSD、Solaris、OpenVMS	QNX（黑莓 10）、L4 家族（seL4）、MINIX 3、Mach（GNU Hurd、Mac OS X 基礎）
優點	設計簡單，通訊成本低，函式呼叫高效，能動態載入或解除安裝模組以提升靈活性	耦合度低，易於除錯與移植，單一組件失效不影響整體，程式碼精簡（如 MINIX 3 小於 6000 行）
缺點	移植性差，模組錯誤可能導致系統崩潰，程式碼高度耦合	行程間通訊（IPC）耗時，涉及環境切換導致延遲，造成效能不如整塊性核心
應用場景	桌面與伺服器系統（如 Linux），適合高性能需求	即時系統（如 QNX 汽車系統）、嵌入式設備、高安全性場景（如 seL4 軍事應用）
運作方式	單一核心空間處理所有系統呼叫，硬體直接交互	多行程結構，核心作為中介，服務獨立運行，支援分散式系統
效能與穩定性	執行速度快，但穩定性依賴設計完善，硬體複雜性增加挑戰	第二代微內核（如 L4）優化 IPC 提升效能，數學驗證（如 seL4）確保穩定性
發展趨勢	主流地位穩固，支援動態模組化，混合核心（如 Windows NT、Mac OS X）融合其特性	在虛擬化、雲端、嵌入式領域崛起，第一代（如 Mach）較「胖」，第二代（如 QNX、L4）更精簡
程式碼規模	較大，依賴模組化減少核心空間大小	通常小於 10,000 行，減少潛在 Bug

15. Disk I/O

virtio specification

Virtqueue 結構與運作

Virtqueue 是 VirtIO 的核心資料結構，用於管理磁碟請求（request），包含描述子域（Descriptor Area）、可用環（Available Ring）與已用環（Used Ring）。運作流程如下：

驅動程式在描述子域中填寫描述子，指定請求的記憶體位址（例如讀寫的緩衝區）、長度（通常為 512 bytes，扇區（Sector）大小）和其他屬性（例如是否可寫）。一個請求可能由多個描述子組成，形成一個連鎖描述子（descriptor chain），以支援 Scatter-Gather I/O 。
驅動程式將連鎖描述子的頂部描述子索引（head descriptor index）加入可用環的 ring 陣列。接著更新可用環的 index ，表示有新請求。
驅動程式寫入 virtio 的 MMIO 暫存器（VIRTIO_REG_QUEUE_NOTIFY），通知裝置有新的請求等待處理。
裝置從可用環讀取連鎖描述子的頂部描述子索引，並根據描述子的資訊，存取指定的記憶體區域（例如讀取或寫入資料）。處理完成後，裝置將連鎖描述子的頂部描述子索引寫入已用環的 ring 陣列，並更新 index。
驅動程式檢查已用環的 index ，確認請求是否完成（在教學文件中透過忙碌等待實做），最後根據已用環的資訊，處理結果（例如檢查狀態或複製讀取的資料）。

Virtqueue 程式碼實現

在 kernel.h 中定義的 Virtqueue 結構使用 __attribute__((packed)) 確保與裝置記憶體布局一致，並設定 VIRTQ_ENTRY_NUM 為 16，限制每個 Virtqueue 最多支援 16 個描述子。

初始化 Virtqueue 的 virtq_init 函式負責配置記憶體並確保對齊頁面大小。函式將 Virtqueue 的索引初始化為 0，並透過 virtio_reg_write32 函式寫入記憶體映射輸入輸出（MMIO）暫存器，設置 Virtqueue 的參數，包括根據索引選擇目標佇列、寫入 VIRTIO_REG_QUEUE_NUM 定義佇列大小、確保佇列對齊，以及設置佇列的實體位址。最後，函式返回 Virtqueue 結構的指標，供後續輸入輸出操作使用。

提交請求的 virtq_kick 函式將描述子索引加入可用環，使用模運算防止陣列溢位。為確保記憶體操作順序，函式呼叫 __sync_synchronize()，避免編譯器或 CPU 重排指令。隨後，函式寫入 VIRTIO_REG_QUEUE_NOTIFY 暫存器，通知裝置處理新請求。

檢查請求狀態的 virtq_is_busy 函式透過比較 last_used_index 與 used_index，判斷裝置是否仍在處理請求，若索引不同則表示處於忙碌狀態。

處理輸入輸出請求的 read_write_disk 函式首先透過 virtio_blk_req 結構建立請求，指定目標扇區編號與讀寫類型。接著，函式構建描述子鏈，包含三個描述子：第一個描述子指向唯讀的請求（type、reserved、sector），佔 16 位元組（4 + 4 + 8），設置 VIRTQ_DESC_F_NEXT 旗標表示後續還有描述子；第二個描述子指向資料緩衝區（data），長度為 512 位元組（SECTOR_SIZE），位址從請求結構偏移 16 位元組計算，若為讀取操作則設置 VIRTQ_DESC_F_WRITE 旗標允許裝置寫入，否則保持唯讀，並附加 VIRTQ_DESC_F_NEXT；第三個描述子指向狀態欄位（status），長度為 1 位元組，位址偏移 528 位元組（4 + 4 + 8 + 512），設置 VIRTQ_DESC_F_WRITE 旗標允許裝置寫入完成狀態（0 表示成功）。函式透過 virtq_kick 提交請求，採用忙碌等待監控處理進度，完成後檢查 status 欄位，並在讀取操作時將資料複製到指定緩衝區。

執行之後，發現 .txt 檔案可以被完整寫入，但是 capacity 總是表示為 0

$ ./run.sh

virtio-blk: capacity is 0 bytes
first sector: Lorem ipsum dolor sit amet, consectetur adipiscing ...

$ head lorem.txt 
hello from kernel!!!
amet, consectetur adipiscing elit. In ut magna consequat, cursus velit ...

16. File System

基於 Tar 格式的檔案系統

在 kernel.c 中實作了一個基於 tar 格式的簡單檔案系統，將檔案內容儲存於記憶體，並透過系統呼叫提供應用程式存取。該檔案系統以 tar 檔案作為儲存媒介，利用其簡單的結構模擬檔案系統功能，適合教學用途。核心透過 fs_init 函式在系統啟動時從磁碟讀取 tar 檔案，逐一解析並儲存至 files 陣列。該函式走訪所有磁區，使用 read_write_disk 函式將磁碟內容載入 disk 的緩衝區，並透過偏移量 off 追蹤當前位置，將 disk[off] 轉為 tar_header 結構以存取檔案標頭。檔案大小由 oct2int 函式從八進位字串解析，隨後設置 files 陣列中的檔案狀態（in_use 為真）、檔名、內容及大小，並將偏移量推進至下一個檔案標頭，確保與磁區大小對齊。fs_flush 函式將 files 陣列中的檔案內容重新格式化為 tar 檔案並寫回磁碟。首先，生成空的 disk 緩衝區，走訪有效檔案，為每個檔案生成 tar_header 後，設置檔名、權限（"000644"）、格式（"ustar"）、版本（"00"）及檔案類型（'0' 表示普通檔案）。檔案大小轉為八進位字串，檢查碼初始為空格字元的 ASCII 值乘以欄位長度，再計算開頭所有位元總和，最後更新檢查碼。檔案內容複製至開頭後的資料區，偏移量依磁區對齊推進，最後透過 read_write_disk 函式將緩衝區寫回磁碟。fs_lookup 函式根據檔名在 files 陣列中查找檔案，逐一比較檔名，若匹配則返回檔案指標，否則返回空指標。oct2int 函式將 tar 開頭的八進位字串轉為十進位整數，支援檔案大小的解析。

系統呼叫與使用者指標存取

檔案系統透過 readfile 和 writefile 命令，系統呼叫支援應用程式存取檔案，分別對應 SYS_READFILE 和 SYS_WRITEFILE ，用來接受檔名、緩衝區指標及長度作為參數。藉由 handle_syscall 函數處理這些呼叫，並呼叫 fs_lookup 函式查找檔案，若未找到則返回錯誤。讀取時，核心將檔案內容複製至使用者緩衝區；寫入時，將使用者緩衝區內容複製至檔案並呼叫 fs_flush 函式來更新磁碟。為確保安全，核心需處理使用者指標存取，因為直接引用使用者提供的指標（如檔名或緩衝區）可能導致存取核心記憶體的風險。

在 RISC-V 中，監督者模式（S-mode）預設無法存取使用者模式（U-mode）分頁，除非設置 sstatus 暫存器的 SUM 位元（Supervisor User Memory access）。核心在 user_entry 函數中設置 SSTATUS_SUM，允許監督者模式存取使用者分頁，解決分頁錯誤問題，但需謹慎驗證指標有效性以避免安全漏洞。

注意用語，務必採用本課程規範之詞彙及針對語境進行調整

06-12 課程討論筆記

Timer：作業系統的心臟

Linux 核心設計: Timer 及其管理機制

Timer 與排程器（Scheduler）的關係

Timer 是作業系統的主體元件（core component），常被喻為作業系統的心臟，因其驅動排程器運作，確保系統資源的有效配置與多工處理。作業系統仰賴排程器決定行程的執行順序與時間配置，而排程器的運作依賴 Timer 提供定期的時間中斷，觸發行程切換與資源重新配置。在 Linux 核心中， Timer 透過硬體時鐘產生固定週期的时间中斷，稱為系統嘀嗒（system ticks），每次中斷促使排程器檢查當前行程的執行狀態，決定是否切換至其他行程，實現分時多工（time-sharing multitasking）。 Timer 還支援行程的超時處理與延遲操作，例如喚醒處於睡眠狀態的行程或處理逾時事件，確保系統即時響應。若無 Timer 的驅動，排程器將無法有效運作，行程可能長期佔用 CPU，導致系統停滯。因此， Timer 作為時間管理的基礎，支撐作業系統的動態運行，猶如心臟為系統提供節奏。

OS Tick 與節拍器角色

OS tick 是作業系統用於計量時間的基本單位，透過硬體 Timer 產生的週期性中斷達成，猶如節拍器為系統提供穩定的時間節奏。在 Linux 核心中，OS tick 通常以固定頻率（例如每毫秒一次）觸發，驅動排程器更新行程的執行時間、檢查系統資源狀態，並執行時間相關的操作，如 Timer 超時或延遲任務的處理。每個 tick 代表一個時間片（time slice），作業系統利用這些時間片配置 CPU 資源，確保多行程公平執行。OS tick 的頻率影響系統的即時性與開銷：較高的頻率提升響應速度，但增加中斷處理的負擔；較低的頻率則降低效能。

記憶體配置策略

連續記憶體配置中的 first-fit 與 best-fit 策略

作業系統在動態記憶體配置中常採用 first-fit 與 best-fit 兩種連續配置策略，以從可用記憶體區塊中選擇合適區塊（Block）滿足行程需求。first-fit 從可用區塊清單開頭開始搜索，選取第一個大小足以滿足需求的區塊進行配置。其簡單的實現方式確保快速搜索，一旦找到合適區塊即停止，減少計算開銷。然而，first-fit 可能過早分割較大區塊，產生較多小碎片，降低記憶體利用效率。相較之下，best-fit 走訪所有可用區塊，選擇大小最接近需求的最小區塊，旨在減少分割後的剩餘空間，保留較大區塊供後續使用。此策略有助於提升記憶體利用率，但因需檢查整個清單，時間開銷較高，效率在區塊數量多時下降。

外部碎片（External Fragmentation）的產生、影響與解決方案

外部碎片是指連續記憶體配置中，可用記憶體區塊分散於已配置區塊之間，儘管總可用記憶體足夠，但因不連續而無法滿足較大記憶體需求的現象。first-fit 策略從清單開頭配置，易將大區塊分割成小片段，增加外部碎片。best-fit 雖選擇最小合適區塊，但頻繁配置與釋放仍可能生成分散的小區塊，累積外部碎片。外部碎片降低記憶體利用率，限制系統配置較大連續記憶體的能力，影響效能。為解決外部碎片，作業系統可採用記憶體壓縮，透過重新排列已配置區塊合併分散的可用區塊，形成較大連續空間，但此過程需暫停行程並耗費 CPU 資源，適用性受限。另一常見方法是使用分頁機制，將記憶體分割為固定大小的分頁，行程的虛擬位址透過分頁表映射至非連續的實體分頁，徹底消除外部碎片，儘管可能引入內部碎片。進階策略包括記憶體池或伙伴系統（buddy system），透過預配置固定大小的區塊或合併相鄰空閒區塊，減少碎片產生。這些解決方案在複雜度與效能間權衡，需根據系統需求選擇適宜方法，以提升記憶體利用效率並維持穩定性。

記憶體管理單元（MMU）與寫入時才複製（Copy-on-Write, CoW）機制

記憶體管理單元（MMU）

是電腦硬體中負責處理 CPU 記憶體存取請求的主體元件，透過將程式使用的虛擬位址映射至實體記憶體位址，實現高效的記憶體管理。它利用分頁或分段機制，將虛擬記憶體空間分割成小單位（通常為分頁），確保不同程式或行程的記憶體存取互不干擾。MMU 管理 CPU 快取與匯流排仲裁（bus arbitration），在較簡單的架構中也負責儲存裝置切換。其記憶體保護功能為每個行程配置獨立的虛擬定址空間，透過作業系統管理的分頁表與 MMU 的權限檢查，防止行程直接存取彼此記憶體，提升安全性，阻擋惡意或錯誤程式危害敏感資料。若行程因存取無效位址引發分頁錯誤，MMU 通知作業系統終止該行程，確保其他行程不受影響，維持系統穩定性。這種隔離支援多工處理（multitasking），讓多個程式同時運行，每個程式認為自己獨占記憶體，提高系統效率。MMU 利用分頁表項或轉譯後備緩衝區設置讀、寫、執行權限，防止存取未配置記憶體，保護核心記憶體免受使用者程式修改，同時支援虛擬記憶體，讓程式無需關心實體記憶體位置，簡化設計並提升記憶體使用效率。

寫入時才複製（Copy-on-Write, CoW）機制

一種延遲複製的記憶體管理策略，旨在減少不必要的記憶體複製，提升實體記憶體使用效率。當多個行程共享同一記憶體分頁時，作業系統不會立即複製分頁，而是等到某行程嘗試修改時才進行複製。例如，執行 fork() 操作時，子行程（child process）繼承親代行程（parent process）的記憶體，初始共享相同的實體分頁，這些分頁被標記為唯讀。當任一行程試圖寫入共享分頁時，作業系統檢測到違反唯讀權限，觸發分頁錯誤，隨即複製分頁到新的實體記憶體位置，更新寫入行程的分頁表，授予寫入權限，其他行程繼續使用原始分頁。CoW 的優勢在於節省記憶體，僅在必要時配置新頁面，適用於行程創建場景，如 fork() 操作中的親代行程與子行程共享記憶體，或多行程共享唯讀資料，僅需一份實體副本。CoW 常與需求分頁（demand paging）結合，進一步最佳化虛擬記憶體管理。

MMU 與 CoW 的關係

MMU 與 CoW 機制搭配可達成高效的虛擬記憶體管理與行程隔離。MMU 透過分頁表項將 CoW 的共享分頁標記為唯讀，確保行程無法直接修改共享記憶體。當行程嘗試寫入時，MMU 因權限違反觸發分頁錯誤，其硬體分頁錯誤訊號快速通知作業系統，啟動 CoW 的複製流程。作業系統的分頁錯誤處理程式複製頁面到新的實體記憶體，更新寫入行程的分頁表，授予寫入權限，確保其他行程不受影響。MMU 的轉譯後備緩衝區加速虛擬位址轉換，分頁表項記錄權限資訊，支援 CoW 的精確權限檢查。這種協同減少記憶體複製開銷，僅在寫入時配置新頁面，節省實體記憶體，同時保證行程間的記憶體隔離，修改後的頁面僅對寫入行程可見，維護系統安全與穩定。

避免非必要的 ** (粗體字標示) 和 ---，使行文流暢且清晰。
注意 parent 的翻譯，見 Linux 核心的紅黑樹

收到，已將 parent process 用語更改為「親代行程」。

轉譯後備緩衝區（TLB）與 TLB miss

轉譯後備緩衝區（TLB）機制

轉譯後備緩衝區（TLB）是 MMU 中的一種高效硬體快取（cache），專為加速虛擬位址到實體位址的轉換而設計。快取是一種位於 CPU 內部的高速記憶體，用於儲存頻繁存取的資料，以減少對較慢主記憶體的存取次數，從而提升系統效能。TLB 作為快取，儲存最近使用的分頁表項，包含虛擬頁碼（virtual page numbers，VPN）與實體頁框號（physical frame numbers）的映射，以及讀、寫、執行等權限資訊，顯著降低查詢主記憶體分頁表的時間成本。TLB 位於 CPU 內部，靠近 MMU，採用全關聯（fully associative）或集合關聯（set-associative）的記憶體結構，支援快速查找。當 CPU 發出虛擬位址的存取請求時，MMU 檢查 TLB，若找到對應的分頁表項（即 TLB hit），即可直接獲取實體頁框號，結合偏移量計算實體位址，實現高效轉換。這種快取機制大幅提升分頁系統的地址轉換效率，對虛擬記憶體的效能至關重要。TLB 項由作業系統或 MMU 硬體管理，在行程切換或分頁表修改時更新，確保映射資訊的正確性。

TLB miss

當 TLB 無法提供虛擬位址的對應分頁表項時，發生 TLB miss 。MMU 需查詢主記憶體中的分頁表以獲取映射資訊。此過程涉及多級分頁表的逐層查詢，造成多次存取記憶體，導致較高的延遲。查詢完成後，MMU 將找到的分頁表項載入 TLB，必要時根據特定策略替換舊項，隨後完成位址轉換。若分頁表中無有效映射，例如分頁尚未載入記憶體， MMU 會觸發分頁錯誤，交由作業系統處理。作業系統可能從磁碟載入所需分頁，更新分頁表，並重新載入 TLB，確保後續存取順利進行。為降低 TLB miss 的開銷，現代 CPU 支援定址空間識別碼（Address Space Identifiers），允許不同行程的 TLB 項共存，減少行程切換時的清除需求。

proncons problem fix

為什麼需要兩組 sem
sem 改成 mutex
執行解釋運作

proncons 出現第二個消費者

Linmo

相傳宋太祖年間，福建莆田有個女孩出生時沒哭，父親便取名「默」，稱林默。因當時習俗，女孩單名常加個「娘」字，所以又叫「林默娘」。她就是後來人們熟知的媽祖，天上聖母。本專案取名 Linmo，以致敬天上聖母在凡間的姓氏。

Linmo 目前支援 RV32I，特徵:

Minimal kernel footprint
Lightweight task model where all tasks share the same memory region
Preemptive and cooperative scheduling based on priority round-robin and a user-defined real-time scheduler
Task synchronization and communication via semaphores, pipeline channels, or message queues
Software timers with callback support
Dynamic memory allocation
A small C library bundled with a data structures library

筆記

程式碼的設計

在 kernel/task.c 中，對於 yeild 相關程式碼的定義如下：
```
void yield(void);

...

void _yield(void) __attribute__((weak, alias("yield")));

...

/* Cooperative context switch, called by a task voluntarily. */
void yield(void)
{
    ...
    stack_check();
    ...
}

...

void mo_task_yield(void)
{
    _yield();
}

...
```
先定義了核心層的 yield 函式負責協作式上下文切換，操作核心控制塊（kcb）與工作控制塊（tcb），透過呼叫 setjmp 和 longjmp 保存與恢復上下文，實現任務間的切換。接著以弱別名（weak alias）定義 _yield 函式，允許特定平台在編譯時提供客製化的上下文切換流程，例如針對特定暫存器或中斷機制的處理，而無需修改核心程式碼。若平台未提供自訂 _yield ，系統則回退至核心的 yield 函式實作，保證通用情況下的正常運作。這種靈活性讓核心程式碼保持平台無關，同時為硬體適配提供彈性。最後， mo_task_yield 函式作為公開 API，進一步保護核心邏輯，防止應用程式直接操作敏感的工作列表或上下文切換機制，降低誤用風險。它簡化使用者介面，與其他工作管理 API（如 mo_task_spawn、mo_task_delay）保持一致的命名風格，提升易用性。

在 yield 函式的實作中，執行上下文切換前，yield 會呼叫 stack_check 函式，檢查當前工作堆疊是否損壞，方法是驗證堆疊兩端的「金絲雀值」（STACK_CANARY），這是一種用於檢測堆疊溢出或記憶體損壞的魔術數字。透過這一核心級保護機制，系統能在潛在問題影響穩定性前及早發現異常，確保上下文切換的可靠性。

canary testing
magic number
靜態內嵌展開函式是 C 語言中常用於標頭檔的技術，旨在提升性能並保持模組化。

inline 屬性建議編譯器將函式程式碼直接嵌入呼叫處，取代傳統的函式跳躍，從而消除堆疊操作與呼叫開銷。例如，list_is_empty() 這樣的簡單檢查函式若每次呼叫都產生開銷，會影響效率；內嵌後，它直接展開為 return !list || list->length == 0U; 的高效檢查。static 則限制函式可見性，僅在包含標頭檔的編譯單元內有效，避免多檔案包含時的多重定義錯誤，減少連結器負擔。

在 include/lib/list.h 中，使用靜態內嵌展開函式（static inline function）定義與設計鏈結串列操作與相關函式，每個函式（如 list_create()、list_pushback()、list_pop()）遵循單一職責原則，專注於單一功能，保持程式碼清晰且易於維護，內嵌展開後也不會過於膨脹。為確保健壯性，函式內置錯誤檢查，處理無效輸入或記憶體分配失敗的情況，返回合理值（如 NULL）。鏈結串列採用頭尾哨兵節點設計，簡化邊界條件處理，減少條件檢查，使靜態內嵌展開函式更高效。同時，串列儲存 void * 資料指標，支援任意資料類型，確保函式的通用性與靈活性。

TODO：支援 MMU

SATP

Exception occurs in condition variable application #6

透過程式報錯確認：

[EXCEPTION] code=1 (Instruction access fault), epc=80000538

這意味著異常是由於嘗試存取無效的指令記憶體位址（或記憶體權限問題）引起的。 epc=80000538 是異常發生時的程式計數器（PC），指向引發異常的指令，但目前無法直接映射到具體程式碼行

調整 mutex_tester() 函式，提供更好的除錯資訊，以及藉由 kernel/task.c 中的 mo_task_cancel() 函式，增加條件判斷式，檢查任務是否持有互斥鎖或在條件變數等待列表中，並執行命令後得到：

Linmo is starting...
...
produced 126
consumed 126
produced 127
trylock busy – OK
[EXCEPTION] code=1 (Instruction access fault), epc=80000538

並在少數情況下得到：

Linmo is starting...
...
consumed 128
produced 129
consumed 129
trylock succeeded – unlocking
timedlock succeeded – unlocking
cannot cancel self – entering idle loop
[EXCEPTION] code=1 (Instruction access fault), epc=80000538

為了測試 mutex_tester() 函式是否為造成問題的主因，我先將其自 app_main() 中進用，結果發現依舊會報錯 [EXCEPTION] ，可以確認問題與 mutex_tester() 函式以及其內使用的函式無關。

接著我將視角轉至 app_main() 末端的程式碼 return 。透過將回傳的數值由 1 更改為 0 ，也就是從搶佔模式變成非搶佔模式後發現，程式碼不再報錯。綜合以上的推論，猜測問題是發生在上下文切換或是中斷處理（定時器）的過程中。

首先，我嘗試修復 longjmp 函式中，未回傳 mepc 的狀況，並透過 _panic() 函式增加回傳mepc 與堆疊指標（sp）的日誌輸出，得到以下資訊：

Linmo is starting...
heap_init(), 130013020 bytes free
task 0: entry=80000334 stack=800029c0 size=4096
task 1: entry=80000288 stack=80003a40 size=4096
task 2: entry=8000022c stack=80004ac0 size=4096
task 3: entry=80000200 stack=80005b40 size=4096
Task 0 produced 0
Task 0 (producer) signaling

*** STACK CORRUPTION: task 0 base=800029c0 size=u

*** KERNEL PANIC (4294950924) – stack corruption
Panic: mepc=0, sp=80003970

接著，我對 kernel/mutex.c 中的 mo_cond_wait() 函式新增 while 迴圈 while (mo_mutex_trylock(m) != ERR_OK) 確保函式在 CRITICAL_ENTER/CRITICAL_LEAVE 之間不會被定時器中斷打斷後。

修復後的通過命令測試顯示，*** STACK CORRUPTION 問題消失，輸出如下：

Linmo is starting...
...
Task 0 produced 35
Task 0 (producer) signaling
Task 1 consumed 35
Task 1 (consumer) signaling
Task 3 (idle) yielding
Task 0 produced 36
Task 0 (producer) signaling
Task 1 consumed 36
Task 1 Task 3 (idle) yielding
(consumer) signaling
trylock busy – OK
Task 2 (mutex_tester) yielding
Task 3 (idle) yielding
[EXCEPTION] code=1 (Instruction access fault), epc=80000544

根據測試結果，修復 longjmp 、 mo_cond_wait 函式有效解決了 *** STACK CORRUPTION 問題，但例外非法指令需進一步測試。

已被老師解決
commit e708a4a
commit a96b267

程式碼改進整理與分析

cond.c 的改進

mutex_tester 函式在任務取消後使用 for (;;) mo_task_wfi()，確保終止任務進入低功耗等待（wfi），避免影響排程器。idle_task 函式也從呼叫 mo_task_yield 改為 mo_task_wfi，藉此減少不必要的上下文切換，提升搶占效率。
mutex.c 在條件變數邏輯的改進

藉由改進條件變數邏輯，在 mo_cond_wait 函式中，移除 mo_task_wfi 和多次 mo_mutex_trylock 的呼叫，改成使用 mo_task_yield 主動觸發上下文切換，並以單次 mo_mutex_lock 確保鎖獲取的確定性。任務設為 TASK_BLOCKED 後立即釋放鎖並切換，喚醒後重新獲取鎖。cv_wake_one 則使用 list_pop 取代 list_foreach，簡化喚醒流程，降低臨界區段（CRITICAL_ENTER／CRITICAL_LEAVE）的競爭風險。此外，還新增 cv_wake_all 支援廣播喚醒（broadcast wakeup），並新增判斷式檢查（if (!c || !m)），確保任務狀態的（TASK_BLOCKED／TASK_READY）正確切換，減少中斷造成的影響。
問題解決原理

例外非法指令由 _panic 觸發，原因在於原始 mo_cond_wait 函式使用 mo_task_wfi ，在搶佔式排程下可能導致任務卡在 TASK_BLOCKED 狀態，無法及時切換至 mo_cond_signal 喚醒的 TASK_READY 任務。Timer 中斷觸發 dispatch 時，若 schedule 找不到 READY 任務，則呼叫 panic(ERR_NO_TASKS)。藉由 mo_cond_wait 函式改用 mo_task_yield，確保任務狀態轉換後立即呼叫 schedule，避免 wfi 指令的時機問題。簡化的 cv_wake_one 和單次 mo_mutex_lock 減少臨界區段的競爭，來確保獲取鎖的穩定性。在 app/cond.c 中，mo_task_wfi 降低 mutex_tester 和 idle_task 的切換頻率，防止無效的上下文去干擾排程器。

Unexpected stall in message queue application #8

根據 mqueues 程式碼，我們預期它應該依以下原理運作：

app_main 創建四個訊息佇列（mq1 ~ mq4），並向 mq1 入佇列（enqueue）一條虛設訊息（payload 為 0），觸發 task1 執行，隨後返回 1 啟用搶占式排程。
task1 開始忙碌等待 mq1 訊息，直到收到回覆訊息後將其列印出，並移除佇列（dequeue）。接著將計數器 val（初始 0，逐次遞增）作為 payload 入佇列至 mq2，並格式化字串 str（例如 "hello 0 from t1…"）入佇列至 mq3，最後讓出 CPU。

將整數 val 轉換為 void *（(void *) (size_t) val）
task2 檢查 mq2 訊息，收到後輸出訊息與 task1 的計數器（例如 "message 0"），然後將自己的計數器 val（初始 200，逐次遞增）入佇列至 mq4，並讓出 CPU。
task3 檢查 mq3 訊息，收到後輸出訊息與 task1 的字串（例如 "message: hello 0 from t1…"），然後將自己的計數器 val（初始 300，逐次遞增）入佇列至 mq4，並讓出 CPU。
task4 等待 mq4 至少兩條訊息，收到後輸出 task2 和 task3 的計數器（例如 "messages: 200 300"），延遲 100 毫秒後向 mq1 回送虛設訊息，觸發 task1 下一次迭代，形成任務間訊息循環，最後讓出 CPU。

但根據輸出結果，當執行到步驟5時，整個程式運作停止進展（stall），推測是在上下文切換時出問題，導致無法順利回送訊息給 mq1 進而觸發 task1 所造成的。

task 1 enters...
task 2 enters...
message 0
task 3 enters...
message: hello 0 from t1...
task 4 enters...
messages: 200 300
(stall)

經過老師提示，問題核心在於上下文切換時，並沒有正確的儲存與恢復 mstatus 暫存器。通過觀察 arch/riscv/hal.c 與 arch/riscv/hal.h 程式碼發現， setjmp 函式保存了 18 個欄位的上下文，包括通用暫存器、 mcause 和 mepc 等，但未保存 mstatus 暫存器。此外， longjmp 函式在恢復上下文時同樣未處理 mstatus 的恢復，導致恢復的工作可能處於錯誤的中斷狀態或特權模式。為解決此問題，修補程式碼在 setjmp 和 longjmp 中新增對 mstatus 暫存器的處理。

首先藉由在 setjmp 函式新增讀取 mstatus 暫存器並保存至 jmp_buf 的第 18 個欄位，並將 jmp_buf 大小從 18 擴展至 19 以容納新欄位。在 longjmp 函式中，則使用 csrw 指令恢復 mstatus，確保中斷狀態和其他系統狀態在通用暫存器恢復前正確設置。

commit 762cb7c

在經過以上的修復後， app/mqueues.c 可以順利運行：

...
task 1 enters...
task 2 enters...
message 44
task 3 enters...
message: hello 44 from t1...
task 4 enters...
messages: 244 344

TODO：完善 mstatus 筆記

mstaus（Machine status）

ISA-privilged P.29 3.1.6. Machine Status Registers