系列與本頁目錄
上一篇結束時,kernel 開機了,手上有 64 MB 還沒用的記憶體。這一篇講怎麼讓 shell 這個程式跑起來,而且只碰得到自己的記憶體。
順序是:shell 用的位址哪來的、它的內容放在哪、kernel 怎麼把兩邊接起來、page table 長怎樣、誰決定現在用哪一張。
為什麼需要 virtual memory
如果每個程式都直接用真正的記憶體位址(physical address),會有兩個問題:
- 程式 A 寫錯一個指標,就可能改到程式 B 或 kernel 的資料。
- 每個程式編譯時都要知道自己會被放在記憶體的哪裡,而且不能跟別人重疊。
virtual memory 的做法是:程式用的位址都是假的。CPU 每次存取記憶體時,照一張表把假的位址(virtual address)換成真的位址(physical address)。這張表叫 page table,由 kernel 準備。
每個 process 有自己的一張 page table。表裡沒寫的位址,那個 process 就碰不到。
概念就這樣。接下來用 shell 當例子,看實際上要做哪些事。
shell 用的位址是哪來的
shell 和 kernel 是分開編譯的兩個程式,各有自己的 linker script。
很容易以為 virtual address 是程式執行的時候,kernel「發」給它的。其實不是:是 link 的時候就決定好的,比程式開始跑還早。
shell 的 linker script(user.ld)一開頭就寫:
. = 0x1000000;意思是「這個程式從位址 0x1000000 開始排」。linker 照這個起點,算出 shell 裡每個函式、每個變數的位址。編好之後可以直接看:
$ llvm-nm -n shell.elf
01000000 T start
01000120 T llm_mode
01000378 T main
01000564 T putchar
01000656 T printf這些數字會直接寫進機器碼。例如 start 裡面呼叫 main,編出來就是「跳到 0x1000378」。
所以 shell 一開始跑,就會理所當然地去用 0x1000000 附近的位址。它不知道、也不需要知道實際的記憶體在哪。
kernel 的工作是反過來的:位址已經定了,kernel 要讓這些位址「真的有東西」。shell 去讀 0x1000378 的時候,那裡要剛好是 main 的機器碼。
為什麼是 0x1000000?只要不跟 kernel 和 device 用的位址重疊就可以,這個數字本身沒有特別的意義。
shell 的內容一開始在哪
位址定了,但 shell 的機器碼總要先存在某個地方。
一般的作業系統把程式放在 disk 上,要執行時再讀進記憶體。這個 OS 沒有 file system,所以用了一個取巧的方法:編譯時就把 shell 整個包進 kernel 裡。
第二次 objcopy 把整個 shell.bin 當成一塊資料包成 .o,並且自動產生兩個 symbol:_binary_shell_bin_start(這塊資料從哪開始)和 _binary_shell_bin_size(多大)。kernel 把這個 .o 一起 link 進去之後,shell 的內容就躺在 kernel 的 .data 裡,kernel 用這兩個 symbol 找得到它。
所以開機之後,狀況是這樣:
| 在哪 | |
|---|---|
| shell 的內容實際在 | kernel 的 .data 裡,0x802xxxxx 的某個地方 |
| shell 以為自己在 | 0x1000000 |
兩邊對不上。下一節就是在處理這件事。
把 shell 接到它以為的位址上
kernel 要做三件事。以 shell 的第一個 4 KB 為例,下面的數字是我開機時實際印出來的:
alloc_pages(1):拿一塊 4 KB 的空記憶體(叫一個 page)。這次拿到的在 physical address0x8026c000。memcpy:把 shell 的前 4 KB 從 kernel 的.data複製進去。map_page(page_table, 0x1000000, 0x8026c000, ...):在 shell 的 page table 寫下一格:「0x1000000開始的這 4 KB,實際在0x8026c000」。
把兩邊接起來的,就是第 3 步在 page table 裡寫的那一格。
為什麼要複製一份,不直接把 0x1000000 指到 kernel 裡原本那一份?因為 shell 執行時會改自己的變數和 stack。每個 process 要有自己的一份,原本那份要保持乾淨。
怎麼拿一個空的 page
記憶體以 4 KB 為一個單位,叫一個 page。page table 也是以 page 為單位在對照的,所以 kernel 拿記憶體都是一個 page 一個 page 拿。
這個 OS 的做法是最簡單的一種:記住下一個還沒用過的位址,要幾個 page 就往後推幾個。
拿出來的 page 會先填成 0。這種做法只會往前、不會回收,process 結束了記憶體也拿不回來。64 MB 對這個 OS 來說用不完,所以先這樣做;能回收的 allocator 是之後想做的。
拿到的是哪一個 page 要看當時用到哪,事先不知道。這也是為什麼需要 map_page:位置是臨時決定的,要有地方記下來。
做完之後,shell 執行時發生什麼
shell 要執行 0x1000378(main)時:
- CPU 查 page table,知道
0x1000000這個 page 在0x8026c000。 - 加上 page 裡面的位置
0x378,實際去讀的是0x8026c378。 - 那裡放的正是第 2 步複製進去的
main。
三步少一步都不行:
- 沒做第 3 步:內容放好了,但 shell 用
0x1000000找不到它。 - 沒做第 2 步:找得到那個 page,但裡面是空的。
如果 shell 去碰一個 page table 裡沒寫的位址,CPU 會發出 page fault,跳進 kernel。這個 OS 的處理方式很簡單,直接印 PANIC 停下來。
整個 shell:同樣的事做 17 次
上面只看了第一個 4 KB。create_process 對 shell 的每 4 KB 都做一次同樣的三步,virtual address 每次往後 0x1000:
我這次編出來的 shell.bin 是 69,264 bytes,所以是 17 個 page。裡面真正的程式碼大約 2 KB、字串大約 1.7 KB,剩下的 64 KB 是預留給 shell 自己的 stack。
page table 實際上長怎樣(Sv32)
前面一直說「查表」「寫一格」,這一節講那張表長什麼樣子。
RISC-V 32 位元用的 paging 方式叫 Sv32。一個 32 位元的 virtual address 被切成三段:
拿 main 的位址 0x1000378 來切:
| 段 | 怎麼算 | 結果 |
|---|---|---|
| VPN[1] | 0x1000378 >> 22 |
4 |
| VPN[0] | (0x1000378 >> 12) & 0x3ff |
0 |
| offset | 0x1000378 & 0xfff |
0x378 |
意思是:第一層表的第 4 格 → 第二層表的第 0 格 → 那個 page 裡的第 0x378 個 byte。
查的過程:
- CPU 從
satp這個 register 知道第一層表在哪(這一篇最後會講satp)。 - 用 VPN[1] 當索引,從第一層表拿到一格,裡面寫著第二層表在哪。
- 用 VPN[0] 當索引,從第二層表拿到一格,裡面寫著 physical page 在哪。
- physical page 的位置加上 offset,就是真正的 physical address。
前面說的「在 page table 寫下一格」,寫的就是上面第 3 步在第二層表查到的那一格。
為什麼要兩層
32 位元的 address space 有 4 GB,一個 page 4 KB,總共約一百萬個 page。只用一層的話,每個 process 都要一張一百萬格的表(4 MB)。
分成兩層之後,沒用到的範圍連第二層表都不用建,一個小程式只要幾張表就夠了。
表裡的一格(PTE)
表裡的每一格叫 PTE(page table entry),32 bits:
這個 OS 用到其中五個 flag:
| flag | 意思 |
|---|---|
| V | 這一格有效 |
| R | 可以讀 |
| W | 可以寫 |
| X | 可以當程式執行 |
| U | user mode 可以存取(沒有這個 flag 就只有 kernel 能碰) |
順帶一提:PPN 有 22 bits,加上 12 bits 的 offset 是 34 bits,所以 Sv32 的 physical address 其實可以到 34 位元,比 virtual address 還大。
map_page:寫下一格的那個函式
前面那三件事的最後一件就是這十幾行,整個 virtual memory 的核心在這裡:
void map_page(uint32_t *table1, uint32_t vaddr, paddr_t paddr, uint32_t flags) {
uint32_t vpn1 = (vaddr >> 22) & 0x3ff;
if ((table1[vpn1] & PAGE_V) == 0) {
// 第二層表還不存在:拿一個 page 來當第二層表
uint32_t pt_paddr = alloc_pages(1);
table1[vpn1] = ((pt_paddr / PAGE_SIZE) << 10) | PAGE_V;
}
uint32_t vpn0 = (vaddr >> 12) & 0x3ff;
uint32_t *table0 = (uint32_t *) ((table1[vpn1] >> 10) * PAGE_SIZE);
table0[vpn0] = ((paddr / PAGE_SIZE) << 10) | flags | PAGE_V;
}(原始碼裡還有兩行檢查位址有沒有對齊到 4 KB,這裡省略。)
中間那個 if 的意思是:第二層表用到才建。這在實際的數字上看得出來。shell 的第一個 page 在 0x8026c000,第二個卻在 0x8026e000,中間跳過了 0x8026d000。那個 page 就是 map 第一個 page 的時候,發現第二層表還不存在,當場拿去當第二層表了。
page table 自己也要佔記憶體,用的是同一個 allocator、同一塊 free RAM。
shell 的 page table 裡還有什麼
到目前為止,表裡只有 shell 自己的 17 個 page。但光這樣 shell 還不能跑,表裡還要有 kernel 和 device(實際的程式是先放這些、再搬 shell,順序不影響結果):
| 範圍 | virtual address | map 到 | 權限 |
|---|---|---|---|
| kernel 和 free RAM | 0x80200000 起 |
一模一樣的 physical address | R W X,沒有 U |
| UART | 0x10000000 |
一模一樣的 physical address | R W,沒有 U |
| virtio-blk | 0x10001000 |
一模一樣的 physical address | R W,沒有 U |
| shell 的程式和資料 | 0x1000000 起 |
free RAM 裡拿出來的 page | R W X U |
為什麼 shell 的表裡要有 kernel
shell 發出 system call 時,CPU 會跳進 kernel 的程式,但 page table 不會自動換。如果 shell 的表裡沒有 kernel,一跳過去就找不到 kernel 的程式了。
所以每張表都有 kernel 那一段,只是沒有 U flag:shell 在 user mode 時碰不到,進了 kernel 才看得到。這就是一開始說的「它只碰得到自己的記憶體」。
為什麼 kernel 的位址要一模一樣
kernel 的位址也是 link 時決定的,kernel.ld 寫的是 . = 0x80200000。跟 shell 不一樣的是,kernel 真的就被放在 0x80200000(上一篇講過 OpenSBI 會跳到那裡)。開機之後、切到 shell 之前,paging 還沒開,kernel 一直是直接用 physical address 在跑。
開啟 paging 只是寫一個 register 的事,寫下去馬上生效。那一刻 CPU 正在執行 kernel 的程式,program counter 指著 0x802xxxxx 的某個地方。
如果新的 page table 裡 0x802xxxxx 不是對到原本那塊記憶體,下一條指令就會從錯的地方讀出來,系統馬上壞掉。所以 kernel 那一段用「virtual address = physical address」的方式來 map(叫 identity mapping),開 paging 前後看到的東西完全一樣。
誰決定現在用哪張表:satp
表準備好了,最後一件事是告訴 CPU「用這一張」。kernel 在要切到 shell 的那一刻做這件事。
CPU 上有一個 register 叫 satp,裡面記的是「第一層表在哪個 physical page」。它指著哪張表,CPU 就照哪張表在查。
以 shell 為例,它的第一層表在 0x80259000,所以輪到它跑的時候,satp 的值是 0x80080259:
| 值 | |
|---|---|
| 第一層表的位置 | 0x80259000 |
| 除以 4096,得到 page 編號 | 0x80259 |
| 最高位設成 1,代表開啟 Sv32 | 0x80000000 |
寫進 satp 的值 |
0x80080259 |
兩個 process 都用 0x1000000,不會撞在一起嗎
不會。每次 create_process 都會拿一張新的 page table 和一批新的 physical page。如果開兩個 shell,兩邊的 0x1000000 寫在各自的表裡,指到的是不同的 page。
CPU 只有一個 satp。kernel 換 process 的時候,會把 satp 改成下一個 process 的表(下一篇的 yield())。
所以同一個位址 0x1000000,輪到誰跑,查到的就是誰的 page。反過來說,如果換了 process 卻忘了換 satp,B 就會讀到 A 的記憶體。
這個 OS 實際上只開了一個 shell,平常看不到這件事,但機制是有的:idle process 和 shell 各有一張自己的 page table。
這一篇的重點
- 程式用 virtual address,CPU 照 page table 換成 physical address;表裡沒有的位址碰不到。
- virtual address 是 link 的時候決定的,寫死在程式裡。shell 是
0x1000000。 - shell 的內容在編譯時就包進 kernel。開機後 kernel 用三步把它接上:拿一個 page、複製內容、用
map_page在表裡寫一格。 - Sv32 把位址切成 10、10、12 三段,查兩層表;第二層表用到才建。
- 每張表裡都有 kernel 和 device,位址跟 physical address 一樣,但 user mode 碰不到。
satp指著現在用的那張表;每個 process 一張,換 process 時由 kernel 改寫。
載入留言中…