Operating System CSE 506 Lab2 - E820 Memory Map & Page Translation (1)

  Operating System  Comments

前言

之前是看 COMP790 的課程，但是實作起來發現有點問題，而且題目跟實際 source code 說明不太一樣。在花了很多時間釐清之後，發現原課程內容可能來自於 CSE 506: Lecture from Stony Brook University，仔細看了一下 CSE 506 的 Lab 課程，發現題目與 source code 相符程度較高，因此後續會改看 CSE 506 這系列課程。

這次 Lab 花了大概 20 小時來實作，主要原因是有些 source code 的註解是錯誤的，所以單看註解會產生很多疑問，必須實作和觀察才能釐清。這次實驗也讓我體會到，如果覺得哪邊有不太理解的地方，就直接做實驗來驗證，而不要單看註解來去試圖理解它上面的意思，因為如果註解不是正確的，那這些時間也就浪費了。

因為這次實驗要整理的內容蠻多的，擔心文章太長，所以會分成數篇來貼！

Lab 實驗介紹

Lab 2 是實作 physical memory allocator 和 virtual memory allocator，其中最重要的是清楚 physical memory 與 virtual memory 之間的轉換，以及如何運用 Lab 2 的 PageInfo c structure 把兩者 mapping 起來。

預前知識

  1. AMD64 Architecture Programmer’s Reference Manual: Chapter 5 Page Translation and Protection JOS 大量使用 paging 進行 virtual memory 與 physical memory 轉換，因此首要知識就是要了解 processor 的 page translation 規則，尤其是 long mode page translation。另外，flag 解釋也要先行看過，這樣在看 source code 的時候可以更快進入狀況。

  2. GNU Multiboot Specification 在 boot loader 階段，會透過 BIOS function 來取得當前 physical memory 的配置狀態(Getting an E820 Memory Map)，其中我們需要解讀回傳後的 buffer 的資訊，而 GNU Multiboot Specification 提供完整的解讀說明。

問題

在進入實驗之前，有幾個問題需要先釐清：

  1. 文件說明提到 JOS kernel 在執行時，是以 0x8004000000 位置開始執行，那這麼 address 是在哪裡設置的？又，processor 是如何知道該怎麼解析這個 virtual address？
  3. 我們可以使用的 physical memory 上限？

為了瞭解這些問題，就要先從 bootloader / bootstrap source code 著手。

1. Get E820 Memory Map

首先，在 bootloader 階段，JOS 透過 x86 的 BIOS function 來取得目前記憶體配置狀態。

 1.set multiboot_info, 0x7000 // After the boot block
 2.set e820_map, multiboot_info + 52
 3.set e820_map4, multiboot_info + 56
 4	
 5.set MB_flag, multiboot_info
 6.set MB_mmap_len, multiboot_info + 44
 7.set MB_mmap_addr, multiboot_info + 48
 8
 9do_e820:
10  movl $0xe820, %eax
11  movl $e820_map4, %edi # e820_map4 = buffer address of destination
12  xorl %ebx, %ebx
13  movl $0x534D4150, %edx # 0x534D4150 = ASCII for 'SMAP'
14  movl $24, %ecx # 24bytes = the size of destination buffer
15  int $0x15
16  jc failed
17  cmpl %eax, %edx # %eax will be set to 0x534D4150 if succeed
18  jne failed
19  testl %ebx, %ebx
20  je failed
21  movl $24, %ebp # %ebp records the length of result
22
23next_entry:
24  #increment di
25  movl %ecx, -4(%edi)
26  addl $24, %edi
27  movl $0xe820, %eax
28  movl $24, %ecx
29  int $0x15
30  jc done
31  addl $24, %ebp
32  testl %ebx, %ebx
33  jne next_entry
34
35done:
36  movl %ecx, -4(%edi)
37  movw $0x40, (MB_flag) # the flag value for multiboot_info
38  movl $e820_map, (MB_mmap_addr)
39  movl %ebp, (MB_mmap_len)

每次執行 e820 BIOS function 會得到一條 memory map entry 的資訊(%ebx value 表示 entry 的 index，所以在一開始執行時先將 %ebx index 設置為 0)，透過 loop 的方式來獲得所有的 entries。

Note 1: The address of multiboot_info

在 code 會看到關於 multiboot_info address 設定：

1.set multiboot_info, 0x7000 // After the boot block
2.set e820_map, multiboot_info + 52
3.set e820_map4, multiboot_info + 56
4	
5.set MB_flag, multiboot_info
6.set MB_mmap_len, multiboot_info + 44
7.set MB_mmap_addr, multiboot_info + 48

multiboot_info 的起始 address 被設定在0x7000，根據 Memory Map (x86) ，0x7C00 是 bootloader sector 位置，而 BIOS data 後的 0x00000500 - 0x00007BFF 這段 30 KiB 記憶體位置可供使用，因此才設定在 0x7000 此位置，只要有足夠的 buffer 來放 multiboot_info 資訊，那麼將 0x7C00 調整成其他位址也可以。

有了 multiboot_info 起始位址之後，就可以根據 GNU Multiboot Specification 中的 multiboot information structure 來推算 e820_map、MB_mmap_len、MB_mmap_addr 的位址，所以+52、+56 等看似 magic number 的數字，其實只是 multiboot information structure 的對應位置。

2. Switch from bootloader to kernel bootstrap

取得 e820 memory map 資訊後，還有幾個步驟需要執行，包含：

  1. Load e820 map -> 目前完成階段
  2. Switch from real mode to protcted mode (這樣才能使用 1MB 以上的 memory)
  3. Load kernel (ELF)
  4. Execute the entry point of ELF and pass multiboot_info to kernel

其中，processor 在執行 code 時是使用哪些記憶體區段，是值得注意的地方。

x86 BIOS 會將 bootloader load 到 0x7C00 - 0x7DFF 記憶體區段，那麼 kernel code 會是在哪個記憶體區段呢？我們查看 GNU JOS 的 GNU link script kernel.ld 得到解答。

 1SECTIONS
 2{
 3    . = 0x100000;
 4
 5    .bootstrap : {
 6        obj/kern/bootstrap.o (.text .data .bss)
 7    }
 8    
 9    /* Link the kernel at this address: "." means the current address */
10    . = 0x8004200000;
11
12    .text : AT(0x200000) {
13        *(EXCLUDE_FILE(obj/kern/bootstrap.o) .text .stub .text.* .gnu.linkonce.t.*)
14    }
15
16    PROVIDE(etext = .);	/* Define the 'etext' symbol to this value */
17
18    .rodata : {
19        *(EXCLUDE_FILE(obj/kern/bootstrap.o) .rodata .rodata.* .gnu.linkonce.r.*)
20    }
21
22    /* Adjust the address for the data segment to the next page */
23    . = ALIGN(0x1000);
24
25    /* The data segment */
26    .data : {
27        *(EXCLUDE_FILE(obj/kern/bootstrap.o) .data)
28    }
29
30    PROVIDE(edata = .);
31
32    .bss : {
33        *(EXCLUDE_FILE(obj/kern/bootstrap.o) .bss)
34    }
35}

上面 code 可以看到兩個關鍵 address 0x100000 與 0x8004200000。

透過 script 可以知道，bootstrap.o 的 start address 為 0x100000，而 0x100000 還在 256 MB 實體記憶體的範圍，只要該記憶體段是可被使用的，那 processor 就可以正常執行 code。不過 0x8004200000 可就超出實體記憶體範圍，所以可以猜想在 bootstrap 階段，勢必要進行一些配置，才能讓 processor 正確地處理 0x8004200000 位址。

了解 excute code 和 data 被放在哪些記憶體區段，對於看 asm code 來說很重要。舉例來說，上面有提及我們要把 multiboot_info 位址 pass 到 kernel 中，在 bootstrap.S 可以看到這段：

1# Save multiboot_info addr passed by bootloader
2	
3movl $multiboot_info, %eax # the address of multiboot_info is 0x107000
4movl %ebx, (%eax) # %ebx value is 0x7000

要注意，bootloader boot.S 中定義的 multiboot_info 位址和 bootstrap.S 中定義的 multiboot_info 位址是不一樣的，因為 bootstrap.S 經過 linker re-location，multiboot_info 的位址會以 0x100000 為基準點。因此，上述這段 code 的解釋會變成：在 0x107000 記憶體位址的值是 0x7000，而 0x7000 才是我們真正儲存 multiboot_info 資訊的位址。

3. Setup page translation in bootstrap stage

在真正進入 kernel main function 之前，我們還有一些事情需要先做，而 bootstrap 階段就是用來進行這些準備任務，包含：

  1. setup page translation
  2. switch from protected mode to long mode

其中 page translation 是重點，bootstrap 階段的 page translation 設置是讓 kernel code 可以正確被執行，而我們在 kerel code 中會再根據需求來配置新的 page translation (就是 Lab 2的實作內容)，最後切換到我們所配置的 page translation。

所以，我們可以先透過觀察 bootstrap 的 page translation 配置方式，搭配 AMD64 Architecture Programmer’s Reference Manual，來實際理解 page translation 的運作流程，有助於我們後續實作。

Setup page translation

首先，來看一下 long mode 如何進行 page translation (image source)。

從圖中可以看到，long mode 的 page translation 被分成四個階層的 page table：

  1. Level 4 - PML4
  2. Level 3 - PDPT
  3. Level 2 - PDT
  4. Level 1 - PT

而 processor 透過 CR3 register 來獲得 PML4 位址，接著解析 virtual address 來取得各階層 table 的 offset，最後逐步得到實體記憶體位置。

有了這個概念之後，再來看 bootstrap.S 的 code：

起初，配置 PML4、PDPT 和 PDT ，每個 table 大小為 4096 bytes。

1.set pml4, pml4phys
2.set pdpt1,  pml4 + 0x1000
3.set pdpt2,  pml4 + 2*0x1000
4.set pde1, pml4 + 3*0x1000
5.set pde2, pml4 + 4*0x1000

再將這些 table 的 entry 初始化為 0。

1movl $pml4,%edi
2xorl %eax,%eax
3movl $((4096/4)*5),%ecx
4rep stosl # 將 eax 的值儲存到 edi 中，重複 (4096/4)*5 次，每次 edi 增加 4

接著配置 PML4 table 的 entry，從下方 code 可以知道有兩個 PML4 entry 指向 pdpt1 和 pdpt2，其權限 PTE_P(present) 和 PTE_W (write)。

 1movl $pml4,%eax
 2movl $pdpt1, %ebx
 3orl $PTE_P,%ebx
 4orl $PTE_W,%ebx
 5movl %ebx,(%eax)
 6
 7movl $pdpt2, %ebx
 8orl $PTE_P,%ebx
 9orl $PTE_W,%ebx
10movl %ebx,0x8(%eax)

再來配置 PDPT 的 entry。

 1movl $pdpt1,%edi
 2movl $pde1,%ebx
 3orl $PTE_P,%ebx
 4orl $PTE_W,%ebx
 5movl %ebx,(%edi)
 6
 7movl $pdpt2,%edi
 8movl $pde2,%ebx
 9orl $PTE_P,%ebx
10orl $PTE_W,%ebx
11movl %ebx,(%edi)

接下來到比較核心的配置。 上面提到，kernel 的 start address 是 0x8004000000，我們根據 page translation 的格式，將 0x8004000000 拆解開來，會發現 0x8004000000 是指：

  • PML4 table offset 1
  • PDPT table offset 0
  • PD table offset 32

這也就是為什麼下方 code addl $256,%ebx 的原因，因為 256/8(一個 entry 佔 8 bytes) = 32 entry offset。我們需要配置 32th PDE 才能夠讓 processor 解讀 0x8004000000 位址。

 1movl $128,%ecx
 2movl $pde1,%edi
 3movl $pde2,%ebx
 4addl $256,%ebx 
 5# PTE_P|PTE_W|PSE
 6movl $0x00000183,%eax
 71:
 8 movl %eax,(%edi)
 9 movl %eax,(%ebx)
10 addl $0x8,%edi
11 addl $0x8,%ebx
12 addl $0x00200000,%eax
13 subl $1,%ecx
14 cmp $0x0,%ecx
15 jne 1b

此外，code 中也額外配置 128 個 PDE ($128,%ecx，然後跑 loop)，其中重點是 PDE 的 flag 設定：PTE_P|PTE_W | PSE，PSE 是特殊 flag，根據手冊說明：

PS bit in the page directory entry (PDE.PS) selects between 4-Kbyte and 2-Mbyte page sizes。

因此， page translation 會變成下圖，取消 Level 1 PT 這層級 (image source)：

配置好各階層的 table 之後，最後把 PML4 table 位址記錄在 CR3 register 上。

1movl $pml4,%eax
2movl %eax, %cr3

如此一來就完成 page translation 的重點配置，最後再 enable paging 功能，processor 就會根據這些配置來查找出實體記憶體位址。

1movl %cr0,%eax
2orl $CR0_PE,%eax
3orl $CR0_PG,%eax
4orl $CR0_AM,%eax
5orl $CR0_WP,%eax
6orl $CR0_MP,%eax
7movl %eax,%cr0

4. Switch From bootstrap to kernel main function and parse multiboot_info

Page translation 設置好後，就可以進入到 kernel main function 並且使用定義好的 c multiboot_info structure 解析 e820 memory map 的資料，解析完的資料會如下：

1size: 20, address: 0x0000000000000000, length: 0x000000000009fc00, type: USABLE
2size: 20, address: 0x000000000009fc00, length: 0x0000000000000400, type: RESERVED
3size: 20, address: 0x00000000000f0000, length: 0x0000000000010000, type: RESERVED
4size: 20, address: 0x0000000000100000, length: 0x000000000fefe000, type: USABLE
5size: 20, address: 0x000000000fffe000, length: 0x0000000000002000, type: RESERVED
6size: 20, address: 0x00000000feffc000, length: 0x0000000000004000, type: RESERVED
7size: 20, address: 0x00000000fffc0000, length: 0x0000000000040000, type: RESERVED

可以看到起始位址為 0x100000 的記憶體區段（Extended Memory），而這會是我們主要用來執行 code 的區段。

另外，透過 MIT 特製的 qemu monitor 來查看 page translation 配置情況，驗證是否與我們所推想的一致（正常版本的 qemu 沒有此功能）：

 1(qemu) info pg
 2VPN range             Entry         Flags            Physical page
 3[000000000-000000000] PML4[000]     ----A---WP
 4  [000000000-00003ffff]  PDP[000]     ----A---WP
 5    [000000000-0000001ff]  PDE[000]     -GSDA---WP 0000000000-00000001ff
 6    [000000200-0000003ff]  PDE[001]     -GS-A---WP 0000000200-00000003ff
 7    [000000400-00000ffff]  PDE[002-07f] -GS-----WP 0000000400-000000ffff
 8[008000000-008000000] PML4[001]     ----A---WP
 9  [008000000-00803ffff]  PDP[000]     ----A---WP
10    [008004000-0080043ff]  PDE[020-021] -GSDA---WP 0000000000-00000003ff
11    [008004400-008013fff]  PDE[022-09f] -GS-----WP 0000000400-000000ffff

問題解答

1. 文件說明提到 JOS kernel 在執行時，是以 0x8004000000 位址開始執行，那這麼 address 是在哪裡設置的？又，processor 是如何知道該怎麼解析這個 virtual address？

0x8004000000 位址是在 JOS 的 linker script 中定義的，而在進入 kernel main function 之前，先配置好 page translation (PML4, PDPT, PDT, PT 等)並且 enable page translation 功能，就能讓 processor 解讀 virtual memory address。

2. 我們可以使用的 physical memory 上限？

根據 e820 memory map 資訊，可以得知 USABLE 的記憶體空間約為 256 MiB。