Chapter 2 - Page Tables

概念

• 讓 process 透過一個「中間人」來存取資料，以能安全、彈性的使用記憶體空間。

功能

• 將「 Virtual Address 」對應到「 Physical Address 」。

  • Virtual Address -> process 執行的過程中存取資料的地方 / process在看的記憶體

  • Physical Address -> 電腦實際儲放資料的地方 / 真正的記憶體位置

• 當 process 要從 virtual address 讀取資料時，會透過 page table 來找到對應的 physical address，再傳回資料。

  • 每個 process 都有自己的 page table。

  • 切換 process 時，也會切換至該 process 對應的 page table。

  • 不同的 process 可以存取同一個 virtual address，卻互不影響，是因為它們透過了不同的 page table，對應到不同的 physical address。

  • 比起直接存取實際記憶體的資料，使用 page table 存取資料更安全且彈性多了。

Page Table Entry

• 1 個 page table 是由 2^20 個 page table entrys 組成。

  • Page Table Entry = PTE。

• PTE 是用來指向一塊 physical address 的工具。

  • 「一塊」： 大小為 4096 Bytes。

• PTE 由 physical page number (20-bit) 和 flags (12-bit) 組成。

  • Physical Page Number = PPN。

  • PPN 即該 PTE 指向的 physical address 區塊的前 20-bit。

  • flag 紀錄了該區塊 physical address 的狀態。

    • ex： 是否能被 process 使用、是否能執行 write 操作 …。

• 從 virtual address 對應到 physical address 的流程

  1. 每個 virtual address 的前 20-bit 都會對應到一個 PPN。

  2. 從 page table 中找到 virtual address 對應 PPN 的 PTE。

  3. PTE 會指向一個區塊 (4096 Bytes) 的 physical address。

  4. 由 virtual address 的後 12-bit 直接對應到 physical address 的後 12-bit。

  5. 最後對應到的 physical address 即 virtual address 之對應。

Two-Level Tree

• 為了讓 virtual address 可以有效率地找到 PTE，page table 採用 Two-Level Tree 的結構。

• Two-Level： Page Directory + Page Table Pages

• page directory 的作用類似目錄。

• 1 個 Page directory 有 1024 個 entry。

• 每個 entry 指向 1 個 page table page。

  • 所以一個 page table 有 1024 個 page table pages。

• 1 個 page table page 有 1024 個 PTE。

  • 所以一個 page table 有 「1024 (PTEs) x 1024 (pages) = 2^20 (PTEs)」 個 PTEs。

• virtual address 用前 20-bit 來找 PTE：

  • 用前 10-bit 來對應 page directory 中的一個 entry。

  • 如果沒有對應的 entry，page table hardware 就會回報錯誤。

  • 如果有對應的 entry，則進入該 entry 對應的 page table page。

  • 再用後 10-bit 來對應到 page table page 中的 PTE。

• 這樣的 two-level tree 結構，即可大幅減少要搜尋的 PTE。

Address Space

• virtual address 有 32-bit，理論上一個 process 能使用 4GB (2^32) 的空間。

• 但實際上 process 只能使用其中 2GB 的記憶體空間，剩餘的 2GB 空間是給 kernel 使用。

• process 所用的 virtual address 範圍為 0 - KERNBASE (2GB)。

• kernel 所用的 virtual address 範圍則是 KERNBASE 以上的部分。

• 每個 process 的 page table 也可供 kernel 使用。

• 這樣在 process 進行中突然要轉入 kernel 就無需切換 page table。

• virtual address 和 physical address 的空間使用分布概況如下圖。

Physical Memory Allocation

• kernel 需要分配 physical memory 給 page table 、 process 、 kernel stacks …。

• 每次分配出去的記憶體大小為 4096 Bytes。

• 分配記憶體時會透過一個 free list，由未被使用 (free) 的記憶體組成的 linked list。

  • 調用 physical memory 時將其移出 free list。

  • 不被用到的 physical memory 會被加入 free list。

程式流程

• 建立一個 address space 的程式流程如下圖。

  

• 初始化 free list 的程式流程如下圖。

  

資料結構

• kmap 的資料結構。

  • kmap 在 setupkvm 中用來建立 kernel 所需的 address 對應。

static struct kmap {
    void *virt;       // virtual address 起始位置
    uint phys_start;  // physical address 起始位置
    uint phys_end;    // physical address 結束位置
    int perm;         // flag
} kmap[] = {
    { (void*)KERNBASE, 0, EXTMEM, PTE_W},            // I/O space
    { (void*)KERNLINK, V2P(KERNLINK), V2P(data), 0}, // kern text+rodata
    { (void*)data, V2P(data), PHYSTOP, PTE_W},       // kern data+memory
    { (void*)DEVSPACE, DEVSPACE, 0, PTE_W},          // more devices
};

• free list 的資料結構。

struct run {
    struct run *next;      // free 的空間
};

struct {
    struct spinlock lock;  // lock
    int use_lock;          // 是否使用
    struct run *freelist;  // free list (head)
} kmem;