[C] 從 XV6 OS 學 C

Learning C from XV6 Operating System

取得固定大小陣列的元素個數

#define NELEM(x) (sizeof(x)/sizeof((x)[0]))

• sizeof(x)：取得整個陣列的大小（以 byte 為單位）
• sizeof((x)[0])：取得陣列中單一元素的大小
• 相除後就得到陣列的元素數量

宣告函式指標陣列

static uint64 (*syscalls[])(void) { //... }

• (void): 每個函式 (system call) 都是無參數
• Return uint64
• 未明確指定的索引會被初始化為 NULL

E.g.

// 假設 SYS_fork = 1, SYS_exit = 2, SYS_trace = 22
static uint64 (*syscalls[25])(void) = {
  [1]  sys_fork,
  [2]  sys_exit,
  // [3] 到 [21] 未指定
  [22] sys_trace,
};

// 編譯後實際狀態：
syscalls[0]  = NULL   // 未指定
syscalls[1]  = sys_fork
syscalls[2]  = sys_exit
syscalls[3]  = NULL   // 未指定
syscalls[4]  = NULL   // 未指定
// ...
syscalls[21] = NULL   // 未指定
syscalls[22] = sys_trace
syscalls[23] = NULL   // 未指定
syscalls[24] = NULL   // 未指定

變數名稱

sz : size, 記憶體區塊的大小（byte）== PGSIZE 4096 // bytes per page

Macro

#define PTE2PA(pte) (((pte) >> 10) << 12)

從 Page Table Entry 提取對應的 Physical Page Address

44 bits + 12 bits offset = real physical address

在 RISV-V 的 SV39 架構中， 一個 PTE 是 64 bit，其中低 10 bit 是 flag，因此右移後得到 Physical Page Number (PPN) ，再左移 12 bit 就是 Physical Page Base Address

#define PGROUNDUP(sz) (((sz)+PGSIZE-1) & ~(PGSIZE-1))

將任意大小 sz 向上對齊到最近的 page 大小倍數，一般是 4096 bytes

E.g.

sz = 1000 → PGROUNDUP(1000) = 4096

sz = 4096 → PGROUNDUP(4096) = 4096

sz = 4100 → PGROUNDUP(4100) = 8192

// fs.h
#define MAXFILE (NDIRECT + NINDIRECT)

Max file capacity in blocks (default: 268)

記憶體存取

存取 return address 的值

假設 frame pointer = 0x80004F00

In memory:
┌─────────────────────────┐
│ 0x80004F00: [局部變數]   │ ← fp
├─────────────────────────┤
│ 0x80004EF8: 0x80001234  │ ← fp - 8 (返回地址)
├─────────────────────────┤
│ 0x80004EF0: 0x80004E00  │ ← fp - 16 (上一層 fp)
└─────────────────────────┘

uint64* saved_ra_addr = (uint64*)(fp - 8); // get 0x80004EF8
uint64 saved_ra_val = *saved_ra_addr; // get 0x80001234

XV6 System Calls

sys_sbrk

調整「程式的 heap（program break）」大小。

• 讀取使用者傳入的第一個參數 n（要增減的位元組數）
• 回傳「調整前」的 break（舊的 sz）。因此使用者端可把回傳值當成指標起點使用。

XV6 functions

In trap.c

usertrap

void usertrap(void)

1. Determine the cause of the trap
2. process trap: uservec — > kernelvec,
3. return (call usertrapret)

usertrapret

void usertrapret(void)

1. It sets up the RISC-V control register to prepare for a future trap from user space: setting stvec to uservec and preparing the trapframe fields that uservec relies on.
2. It sets sepc to the previously saved user program counter
3. Finally, it calls userret on the trampoline page

Assembly code in userret will switch page tables

In proc.c

allocproc: 建立一個新的行程

In vm.c

管理虛擬位址空間與 page table

freewalk

void
freewalk(pagetable_t pagetable)

Recursively free page-table pages. All leaf mappings must already have been removed.

mappages

int mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm)

為從虛擬位址 va 開始的虛擬地址建立 page table entry (PTE)，使其對應從實體位址 pa 開始的實體地址。

va 和 size 必須是 page-aligned

c成功時回傳 0，若 walk() 無法分配所需的 page-table page 則回傳 -1

uvmalloc

uint64 uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz, int xperm)

為一個行程增加記憶體空間，將其大小從 oldsz 擴展到 newsz ，oldsz 是行程當前的 virtual memory 的大小，也是行程的界線。

Returns new size or 0 on error.

Two steps:

1. 分配實體記憶體（使用 kalloc）
2. 建立虛擬位址到實體位址的映射（使用 mappages），並更新 pagetable

walk

pte_t* walk(pagetable_t pagetable, uint64 va, int alloc)

遍歷行程的 Page Table，以找到對應特定虛擬位址的 level 0 PTE 的位址。

如果沿途有任何需要的 Page Table Page 不存在，並且 alloc 參數為真，它就會分配並創建它們。

Return: 找到的 PTE 的位址；如果找不到且不允許分配，則回傳 0。

uvmcopy

int uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)

• old :父行程的 page table
• new:子行程的 page table (new)

uvmunmap

void uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)

移除一個程式 pagetable中從 va 開始的連續 npages 個虛擬頁面的映射。它還允許選擇性地釋放這些虛擬頁面所對應的物理記憶體。

保留物理記憶體的原因之一是另一個行程，例如父行程可能還需要使用

In bio.c (block I/O)

brelse (block release)

void brelse(struct buf *b)

It must be called after using the buffer.

In fs.c

bmap (block map)

static uint bmap(struct inode *ip, uint block_number)

功能：找到或者建立 logical block 在磁碟上的 physical block number

Logical block: virtual contiguous block (檔案視角)

itrunc (truncate inode)

void itrunc(struct inode *ip)

將一個 inode 對應的所有資料全部清除，釋放磁碟空間，並將檔案大小歸零。

XV6 Data Structures

In file.h

struct inode

// Copy of disk inode in memory
struct inode {
// ... other fields
short nlink;
uint addrs[NDIRECT+1];
}

一個檔案只有一個 inode ，由於檔案的「內容」是分散存放在不同的 Block，inode 就是負責儲存這些 block 的位置。

設計哲學：檔案的「身份」與「內容」是分開的

nlink: number of directory entries (dirent)

• 若 nlink 不為 0，檔案不會被刪除
• 通常 directory 的 nlink 是 2: parent/curr_dir and .

addrs[NDIRECT+1]: 區塊編號

他決定了一個檔案可以有的最大區塊數目，NDIRECT 的 default 是 12 (kernel/fs.h)，+1是指一個 singly-indirect block number，他可以再容納 256 block。因此，總共可以有 12 個直接區塊 + 256 間接區塊 = 268 blocks。

Default block size is 1024 bytes (BSIZE)

Directory Entry

(X) 迷思： 目錄（Directory）是一個特殊的容器，把檔案裝在裡面。

(O) 真相： 目錄只是一個特殊的檔案，它的「內容」不是文字，而是一張「對照表」。

這張對照表裡的每一行，就叫做 Directory Entry。

// Directory is a file containing a sequence of dirent structures.
#define DIRSIZ 14

struct dirent {
  ushort inum; // Inode 編號
  char name[DIRSIZ]; // 檔名
};

Directory Entry 的核心功能： 它負責將 「人類讀得懂的字串 (name)」 映射到 「電腦讀得懂的編號 (inum)」。