2|virtual memory:page table 與 user space

自製 RISC-V OS 系列第 2 篇:用「讓 shell 跑起來」這件事把 virtual memory 走一遍。virtual address 是 link 時決定的、shell 的內容怎麼包進 kernel、kernel 用哪三步把它接到 0x1000000、Sv32 兩層 page table 怎麼查,以及 satp 怎麼決定現在用哪張表。

發布
字數
2,945
閱讀
約 7 分鐘
瀏覽
0
系列與本頁目錄
  1. 總覽
  2. 1|開機流程與 memory layout
  3. 2|virtual memory:page table 與 user space
  4. 3|process、context switch 與 system call
  5. 4|virtio-blk driver
  6. 5|把 disk 當信箱:OS 怎麼跟 LLM 講話
  1. 為什麼需要 virtual memory
  2. shell 用的位址是哪來的
  3. shell 的內容一開始在哪
  4. 把 shell 接到它以為的位址上
  5. 怎麼拿一個空的 page
  6. 做完之後,shell 執行時發生什麼
  7. 整個 shell:同樣的事做 17 次
  8. page table 實際上長怎樣(Sv32)
  9. 為什麼要兩層
  10. 表裡的一格(PTE)
  11. map_page:寫下一格的那個函式
  12. shell 的 page table 裡還有什麼
  13. 為什麼 shell 的表裡要有 kernel
  14. 為什麼 kernel 的位址要一模一樣
  15. 誰決定現在用哪張表:satp
  16. 兩個 process 都用 0x1000000,不會撞在一起嗎
  17. 這一篇的重點

上一篇結束時,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)一開頭就寫:

Text
. = 0x1000000;

意思是「這個程式從位址 0x1000000 開始排」。linker 照這個起點,算出 shell 裡每個函式、每個變數的位址。編好之後可以直接看:

Text
$ 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 裡。

shell.cuser.ccommon.cclanglink 到0x1000000shell.elfobjcopyshell.bin純二進位objcopyshell.bin.o包成一個 .okernel.c、mm.cvirtio.c、common.cclanglink 到 0x80200000kernel.elf一起 link 進去
編譯時就把 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 為例,下面的數字是我開機時實際印出來的:

shell 用的位址0x1000000link 時就決定了shell 的 page table⋯0x1000000 → 0x8026c000⋯沒寫在表裡的位址碰不到physical page0x8026c000裡面是 shell 的前 4 KB查表去這裡拿kernel 事先做的:1alloc_pages:拿一個空的 page2memcpy:放進 shell 的內容3map_page:在表裡寫下這一格
「接上」就是 page table 裡的一格。上面是 shell 執行時 CPU 怎麼找;下面是 kernel 事先做的三件事。
  1. alloc_pages(1):拿一塊 4 KB 的空記憶體(叫一個 page)。這次拿到的在 physical address 0x8026c000。
  2. memcpy:把 shell 的前 4 KB 從 kernel 的 .data 複製進去。
  3. 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 就往後推幾個。

usedusedusedused還沒用過__free_ram__free_ram_end下一次從這裡開始拿
最簡單的 allocator:記住下一個還沒用過的位置,只往前、不回收。

拿出來的 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:

kernel 的 .data 裡free RAM 裡的 physical pageshell 的 virtual addressshell.bin 的內容第 1 個 4 KB0x8026c0000x1000000memcpymap_page第 2 個 4 KB0x8026e0000x1001000⋯⋯⋯
開機後 create_process 把 shell 一個 page 一個 page 搬出來,再 map 到 0x1000000 起的位址。位址是我這次開機印出來的。

我這次編出來的 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 被切成三段:

VPN[1]10 bitsVPN[0]10 bitsoffset12 bits31222112110第一層表的第幾格第二層表的第幾格page 裡的第幾個 byte
一個 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。

查的過程:

第一層表(1024 格)[VPN[1]]第二層表(1024 格)[VPN[0]]physical page(4 KB)要存取的 bytesatpregister第一層表在哪下一層在哪page 在哪VPN[1]VPN[0]offsetvirtual address第幾格第幾格第幾個 byte
查兩次表。往上的箭頭:virtual address 的每一段決定要看那張表的第幾格。往右的箭頭:那一格裡記著下一張表(或 page)在哪。
  1. CPU 從 satp 這個 register 知道第一層表在哪(這一篇最後會講 satp)。
  2. 用 VPN[1] 當索引,從第一層表拿到一格,裡面寫著第二層表在哪。
  3. 用 VPN[0] 當索引,從第二層表拿到一格,裡面寫著 physical page 在哪。
  4. 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:

PPN22 bits保留D7A6G5U4X3W2R1V031109 8physical page 的編號權限和狀態
page table 裡的一格(PTE)。亮起來的五個 flag 是這個 OS 有用到的。

這個 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 的核心在這裡:

C
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
virtual addressphysical addresskernel + free RAM0x80200000 起shell 的程式和資料0x1000000 起UART、virtio-blk0x10000000、0x10001000kernel + free RAM0x80200000 起配給 shell 的幾個 pageUART、virtio-blk0x10000000、0x10001000位址相同位址不同位址相同
shell 這個 process 的 page table 裡有什麼。kernel 和 device 的位址不變,只有 shell 自己的部分被搬到別的地方。

為什麼 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())。

satpregisterprocess A 的 page table0x1000000 → A 的 pageprocess B 的 page table0x1000000 → B 的 pageA 的 physical pageB 的 physical page現在輪到 A換到 B 時,kernel 改寫 satp
CPU 只有一個 satp。它指著誰的 page table,0x1000000 查到的就是誰的 page。

所以同一個位址 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 改寫。
最後更新 2026.11.18

Comments

留言

支援 Markdown、程式碼高亮(```cpp)與 LaTeX($E=mc^2$),Ctrl + Enter 送出。頭像會用你的 e-mail 去 Gravatar 找,e-mail 本身不會公開。

載入留言中…

Esc

輸入關鍵字,例如「線段樹」「Makefile」「面試」。

↑ ↓ 選擇Enter 開啟