系列文章 : [6.1810] 跟著 MIT 6.1810 學習基礎作業系統觀念
kernel/vm.c : https://github.com/mit-pdos/xv6-riscv/blob/riscv/kernel/vm.c
kernel/kalloc.c : https://github.com/mit-pdos/xv6-riscv/blob/riscv/kernel/kalloc.c
因為 xv6-riscv 是使用 Sv39 的 page table 模式，所以這邊簡單複習一下。
在 riscv-privileged spec 的 12.1.11 有講述 satp，在 12.4 有講述 Sv39 相關的內容 ( 12.4. Sv39: Page-Based 39-bit Virtual-Memory System )。
{ satp 的 layout }
其中 Mode 可以讓我們設定我們想要使用哪一種模式。
這邊簡述一下怎麼進行 virtual address 到 physical address 的轉換
Sv39 顧名思義，就是 virtual address 會有 39 個 bits。
這邊先定義幾個簡寫
從這裡開始我們 page table walk
wtommy_fdgkhdkgh
Sv39 page table entry ( pte[2] ) 的 physical address
kalloc.c 裡面的 function 是用來分配物理記憶體 ( physical memory )，最細緻的分配粒度是一個頁 ( page, 4096 bytes )。也就是說，當你使用 kalloc.c 裡面去拿 ( kalloc ) 一個 page，或是釋放 ( kfree ) 一個 page，都需要以 page ( 4096 bytes ) 為單位。
你不能拿 2048 bytes，也不能釋放 128 bytes，在這裡通通都要以 page ( 4096 bytes ) 為單位。
kalloc.c 裡面，有一個 kinit，這個 function 會在開機時，在 M-mode 的時候，由 hart-id == 0 的 CPU 所執行。
在 kinit 裡面的 end，是在 kernel.ld 裡面的 end，這個符號代表了 kernel 的結尾。
在 kinit 裡面的 PHYSTOP 指的是 physical memory 的盡頭，我們所能觸及的最遠最遠的 physical memory。在 xv6-riscv 這個作業系統，我們預設這個值是 128 * 1024 * 1024 ( 128 MB )。這代表了，假如我們的硬體 裡的 RAM 少於 128 MB 的話，可能會在 kinit 的時候出現問題。假如我們的硬體裡的 RAM 大於 128MB 的話，則沒辦法利用到 128 MB 之後的記憶體了。
void
kinit()
{
initlock(&kmem.lock, "kmem");
freerange(end, (void*)PHYSTOP);
}
freerange 這個 function 可以去 free 一個區間的 physical memory。
第一次看的時候，我覺得很怪，在 boot 的時候，我根本沒有 allocate 任何 page，怎麼在這裡突然就要 free 了呢 ?
其實這裡的 freerange 是為了進行初始化，把所有可利用的 physical memory 的資訊都在進一個 linked list ( kmem ) 進行管理。
void
freerange(void *pa_start, void *pa_end)
{
char *p;
// 對 pa_start 值向上取整
p = (char*)PGROUNDUP((uint64)pa_start);
// 把每一個 page free 掉，這樣子可以讓每一個可以用的 physical memory
// 用一個 linked-list 給串起來
for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE)
kfree(p);
}
// Free the page of physical memory pointed at by pa,
// which normally should have been returned by a
// call to kalloc(). (The exception is when
// initializing the allocator; see kinit above.)
void
kfree(void *pa)
{
struct run *r;
if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
panic("kfree");
// 當我們把一個 physical memory free 掉的時候，順便把它初始化成一個特別的值
// 這樣子當有 pointer 指向一個已經被 free 掉的 memory，並使用的時候，希望
// 更有機會抓到錯誤。
// Fill with junk to catch dangling refs.
memset(pa, 1, PGSIZE);
r = (struct run*)pa;
// 把 free 掉的 page 丟進 linked-list ( kmem ) 裡面
acquire(&kmem.lock);
r->next = kmem.freelist;
kmem.freelist = r;
release(&kmem.lock);
}
// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
void *
kalloc(void)
{
struct run *r;
// 從 linked-list 裡面抓出可以使用的 page
acquire(&kmem.lock);
r = kmem.freelist;
if(r)
kmem.freelist = r->next;
release(&kmem.lock);
// 把抓出來的 page 初始化成一個奇怪的值
// 讓我們更有機會抓到 “使用沒有初始化的值” 的錯誤
if(r)
memset((char*)r, 5, PGSIZE); // fill with junk
return (void*)r;
}
這邊簡單介紹這個 function 會用到的 MACRO
{ https://github.com/TommyWu-fdgkhdkgh/xv6-riscv/blob/xv6-riscv-rev5/kernel/vm.c#L97-L115 }
pte_t *
walk(pagetable_t pagetable, uint64 va, int alloc);
已經被 allocate 記憶體的 root page table{ https://github.com/TommyWu-fdgkhdkgh/xv6-riscv/blob/xv6-riscv-rev5/kernel/vm.c#L146 }
// Create PTEs for virtual addresses starting at va that refer to
// physical addresses starting at pa.
// va and size MUST be page-aligned.
// Returns 0 on success, -1 if walk() couldn't
// allocate a needed page-table page.
int
mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm)
將 pa ~ pa + size - PGSIZE 的範圍，映射到 pagetable 的 va ~ pa + size - PGSIZE
walk function，輸入 pagetable 以及 va，找出該 va 所代表的 leaf PTE。{ https://github.com/TommyWu-fdgkhdkgh/xv6-riscv/blob/xv6-riscv-rev5/kernel/vm.c#L54C1-L62C2 }
void
kvmmap(pagetable_t kpgtbl, uint64 va, uint64 pa, uint64 sz, int perm)
在 root kernel page table 上，新增一個 size 為 sz，權限為 perm的， va —> pa 映射。
這個 function 只有在開機階段會被使用。
{ https://github.com/TommyWu-fdgkhdkgh/xv6-riscv/blob/xv6-riscv-rev5/kernel/vm.c#L20-L22 }
配置 kernel 的 page table
trampoline，這會在之後 trace trap 的時候好好地看一下。 // uart registers
kvmmap(kpgtbl, UART0, UART0, PGSIZE, PTE_R | PTE_W);
把 pa : UART0 ( 0x10000000 ) 映射到 va。
這裡 pa 跟 va 都一樣，並且有著 read/write 權限，讓 S-mode 可以對 uart 的 CSR 進行讀寫。
儘管 pa 跟 va 都一樣，但這邊還是需要走過三個 pagetable
// virtio mmio disk interface
kvmmap(kpgtbl, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);
把 pa : VIRTIO0( 0x10001000 ) 映射到 va ( 0x10001000 )。
// PLIC
kvmmap(kpgtbl, PLIC, PLIC, 0x4000000, PTE_R | PTE_W);
把 pa : PLIC ( 0x0c000000L ) 映射到 va ( 0x0c000000L )。
// map kernel text executable and read-only.
kvmmap(kpgtbl, KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);
把 pa : KERNBASE ( 0x80000000L ) 映射到 va ( 0x80000000L )。
把 kernel 的 .text section 設定為 可讀/可執行，且不可寫入，這樣攻擊者就不能隨意的改寫 kernel space 的 .text section。
.text section 的終點 // map kernel data and the physical RAM we'll make use of.
kvmmap(kpgtbl, (uint64)etext, (uint64)etext, PHYSTOP-(uint64)etext, PTE_R | PTE_W);
將整塊 memory，除了 kernel .text section 以外，都設為 可讀 / 可寫。
.text section 的終點 // map the trampoline for trap entry/exit to
// the highest virtual address in the kernel.
kvmmap(kpgtbl, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
把 pa : trampoline 映射到 va : TRAMPOLINE。
// allocate and map a kernel stack for each process.
proc_mapstacks(kpgtbl);
這會為每個 process 配置 kernel stack。
每個 process 會有一個可用的 page，以及一個 guard page，所以每個 process 的 kernel stack 會需要兩個 page 的空間。
可用的 page 會配置為可讀/可寫，而 guard page 則什麼權限都沒有。這樣當我們在使用太多 kernel stack 的空間，超過了一個 page 的時候，就會碰觸到 guard page 並 page fault。
這可以保護其他 process 的 kernel stack 不被無意或惡意的竄改。
kernel/vm.c/proc_mapstacks
{ https://github.com/TommyWu-fdgkhdkgh/xv6-riscv/blob/xv6-riscv-rev5/kernel/proc.c#L32-L44 }
// map kernel stacks beneath the trampoline,
// each surrounded by invalid guard pages.
#define KSTACK(p) (TRAMPOLINE - ((p)+1)* 2*PGSIZE)
→ 這邊可以看到，明明每個 process 的 stack 都只有 PGSIZE，為什麼這邊會出現 2 * PGSIZE 呢 ? 這就是上面所提到的 可使用的 page，以及 guard page 了。
{ https://github.com/TommyWu-fdgkhdkgh/xv6-riscv/blob/xv6-riscv-rev5/kernel/proc.c#L41 }
在這邊可以看到一個有趣的寫法
KSTACK((int) (p - proc));
這邊可以用一個更簡單的程式碼來呈現。
#include <stdio.h>
int a[10];
int main(int argc, char *argv[]) {
printf("hi!\n");
for (int i = 0; i < 10; i++) {
a[i] = i;
}
int *b;
for (b = &a[0]; b <= &a[9]; b++) {
printf("*b : %d\n", *b);
printf("(int) (b - a) : %d\n", b - a);
printf("((int)b - (int)a) : %d\n", (int)b - (int)a);
}
return 0;
}
因為 int 的 type 是 4，所以 (int) b - (int) a 的值會是 0, 4, 8, 12 …
但是 (int) ( b - a ) 的值卻是 0, 1, 2, 3, 4 …
於是我們可以知道，當指標相減後，再轉變型態，在 C 語言裡會再去 Modulo ( % ) 指標所指向的型態的大小。
{ https://github.com/TommyWu-fdgkhdkgh/xv6-riscv/blob/xv6-riscv-rev5/kernel/vm.c#L64-L69 }
配置 root kernel page table，這個 page table 會被所有 CPU 共享。
正式初始化當前 hart 的 satp register。
因為每個 hart 都有自己的 satp register，所以每一顆 CPU 都要進行這樣的初始化。
在更改 satp 前，也用 sfence.vma 去確保所有對 page table 的寫入 ( store ) 已經結束了。
在更改satp 後，需要用 sfence.vma ( Supervisor Memory-Management Fence for Virtual Memory ) 去 invalidate TLB 的內容。
大部分操作 address space 以及 page tables 的程式碼，都在 kernel/vm.c 裡面。
最核心的資料結構是 pagetable_t，它指向了一個 page ( 4096 bytes )，而這個 page 裡面存放著的是 RISC-V 的 root pagetable ( 512 個 PTE，8 bytes per PTE，總共 4096 bytes )。
這個 root pagetable 可以指的是 kernel 本身的 page table，也可以是 user-process 的 root page table。
在 vm.c 這個檔案裡的 function
kvm 開頭的 function，處理的都是 kernel 的 page tableuvm 開頭的 function，處理的都是 user 的 page table幾個重要的 functions
walk : 給一個 virtual address，找出相對應的 leaf PTE。mappages : 替新的映射 ( mapping ) 配置相對應的 PTE。在開機的階段，會去呼叫 kvminit 去建立 kernel 的 page table。
透過 kvmmake 來建立核心的 va → pa 映射 ( e.g. UART, VIRTIO 的映射 )。這些事情都發生在啟用 RISC-V 的 paging 之前 ( 設定 satp 之前 )，所以這時候的位址都是 physical address。
kvmmake 會先呼叫 kalloc 取得一個 page 的記憶體，用來放置 kernel root page table。然後再呼叫 kvmmap 來配置 kernel 需要的 va → pa 映射。
每一個 CPU 都需要呼叫一次 kvminithart 來初始化自己的 satp CSR 來安裝 page table，因為每個 CPU 都有自己的 satp。就算 CPU 開始使用 kernel page table 了，kernel 還是可以正確地執行，這是因為大部份的 kernel page table 的 va 跟 pa 是完全相同的。
每一個 RISC-V CPU 也有自己的 Translation Look-aside Buffer ( TLB )，這個硬體會把 page table entries ( PTE ) 快取起來。這樣當我們想從 va 轉成 pa 的時候，就可以先從 TLB 裡面找找看，有沒有 va 所對應的 PTE，以此來加快 va → pa 的轉換速度。
當 CPU 要切換 page table ( 對 satp CSR 寫入新的 root page table 的 physical address ) 的時候，我們需要必須通知 CPU 使對應的 TLB 快取失效。否則，TLB 可能會使用舊的映射，指向一個在此期間已分配給其他行程的實體頁，導致行程可能竄改其他行程的記憶體。
RISC-V 提供了一條指令 sfence.vma，用於刷新當前 CPU 的 TLB。xv6 在 kvminithart 重新載入 satp 暫存器後，需要在程式碼中執行 sfence.vma。
此外，在更改 satp 之前也必須發出 sfence.vma，以等待所有未完成的載入（load）和儲存（store）指令完成。這種等待確保了先前對頁表的更新已經完成，並確保先前的讀寫操作使用的是舊頁表，而非新頁表。
iThome鐵人賽
看影片追技術