在昨天我們看到了 xv6 中記憶體分頁與虛擬記憶體的概念與實作的部分，有了這一些功能，我們就能夠實現作業系統中的隔離性，也就是 process 之間使用的都是虛擬的記憶體，並且彼此之間無法存取彼此的記憶體空間。
而今天會針對 xv6 中記憶體分頁的部分做進一步的介紹，昨天我們看到虛擬記憶體與記憶體分頁的實現，今天會看到虛擬記憶體與實體記憶體之間的映射關係。
前面說到，在 xv6 中有兩種記憶體分頁，一種是用在 process 的，另外一種為kernel page。kernel 也使用到了 address space 的概念，可以使用虛擬記憶體地址存取各實體記憶體地址以及一些外部的 I/O 設備。在 kernel/memlayout.h 可以看到 kernel address space 的結構。而將其以圖表示為以下
右半邊實體記憶體的結構是由硬體設計來決定，我們在 xv6 的啟動中得知作業系統會在0x80000000 (KERNBASE) 開始執行，而這個位置是取決於硬體的設計，QEMU 模擬了一部 RISC-V 架構的電腦，包含 RAM, I/O 設備以及 CPU 的部分，CPU 為一顆多核心 CPU，每一個核心都有各自的 MMU 和 TLB。
從上面的圖我們可以看到，左邊為虛擬記憶體地址，右邊為實體物理記憶體地址，當存取的記憶體地址大於0x80000000時，我們存取的會是 DRAM 的部分，而如果小於0x80000000時，就會正如在 xv6 的啟動與架構中提及的，會存取到外部 I/O 設備的部分，kernel 可以通過一些特殊的讀寫指令對其進行操作，例如在0x80000000 存在乙太網網卡，而這個外部裝置會通過 Memory-mapped I/O 映射到某一個物理地址，而我們可以通過這個地址進行對乙太網網卡的操作。這部分是由主機板的設計決定，可以通過查詢相關文件得知每一條物理記憶體地址背後的對應關係。
在右邊 Physical address 可以看到在 0x1000 的位置為 boot ROM，當主機板通電時，主機板進行的第一件事情為執行儲存在 ROM 中的程式碼，當執行完成，boot 完成後，便會跳轉到0x80000000 執行作業系統，此時作業系統需要確保該記憶體地址有存放用於啟動作業系統的程式碼
而在0x80000000下方還有存在許多 I/O 裝置，分別為以下
左邊的圖表示 xv6 的 Virtual address space。在電腦啟動時，並沒有任何可用的 page，kernel 會設置好 Virtual address space，也就是左圖的記憶體地址的結構與分布，而對於左圖的虛擬記憶體與右圖物理記憶體的映射，xv6 為了方便理解，大部分都是相等的對應關係。除了方便理解，也可以讓程式碼變得更加的簡單，例如使用fork() system call 時，親代 process 在將記憶體內容複製到子 process 時，可以直接將該記憶體地址作為虛擬記憶體地址。
而在 virtual addrss space 中也可以看見一些並非是使用直接映射到物理記憶體空間的記憶體分頁，例如 Kstack (kernel stack)，GuardPage，Trampoline。
而 free memory，會以分頁的形式被一個稱為 free list 的資料結構所儲存，當有程式需要記憶體時，通過kalloc()從 free list 獲得記憶體空間，而當使用完畢後，通過kfree()將分頁放回 free list 中。
在虛擬記憶體與物理記憶體之間的映射關係中可以發現幾件事情，有一對一映射，一對多映射 (kernel stack)，或是不進行任何映射 (guardpage)
而在每一個 section 旁，可以看見R-X, RW- 等等標示，這些表示對於這一些 section 的權限，R-X 表示可以用於讀取 (Read)，以及能夠在該 section 執行指令，但無法進行寫入 (write)，而在現實中 linux 系統也有相似的權限系統。
在現實中的 linux 系統，如果在 console 輸入la -al，可以看到以下資訊
drwxr-xr-x 2 user user 4096 Jul 26 00:35 Downloads
-rw-r----- 1 root root 352256 Jul 26 01:00 Flash1.bin
我們關注最左方由 10 bit 構成的區域，以下說明
\dev底下 (I/O 設備是一種特別的檔案)pipe()不同之處在於pipe()是建立虛擬檔案，而 socket 是通過一些網路協定達成。可以通過chmod(),chgrp(),chown()指令來改變檔案的權限設定。
在 xv6 的啟動與結構中，以及上面的介紹，我們知道 xv6 啟動時會進行記憶體分頁的相關配置，以下為main()函式
#include "types.h"
#include "param.h"
#include "memlayout.h"
#include "riscv.h"
#include "defs.h"
volatile static int started = 0;
// start() jumps here in supervisor mode on all CPUs.
void
main()
{
if(cpuid() == 0){
consoleinit();
printfinit();
printf("\n");
printf("xv6 kernel is booting\n");
printf("\n");
kinit(); // physical page allocator
kvminit(); // create kernel page table
kvminithart(); // turn on paging
procinit(); // process table
trapinit(); // trap vectors
trapinithart(); // install kernel trap vector
plicinit(); // set up interrupt controller
plicinithart(); // ask PLIC for device interrupts
binit(); // buffer cache
iinit(); // inode cache
fileinit(); // file table
virtio_disk_init(); // emulated hard disk
userinit(); // first user process
__sync_synchronize();
started = 1;
} else {
while(started == 0)
;
__sync_synchronize();
printf("hart %d starting\n", cpuid());
kvminithart(); // turn on paging
trapinithart(); // install kernel trap vector
plicinithart(); // ask PLIC for device interrupts
}
scheduler();
}
可以看到在consoleinit(),printfinit()結束後，就會執行 page table 的相關操作，以下為用於建立 kernel page table 的 kvminit()。
void
kvminit(void)
{
kernel_pagetable = kvmmake();
}
pagetable_t
kvmmake(void)
{
pagetable_t kpgtbl;
kpgtbl = (pagetable_t) kalloc();
memset(kpgtbl, 0, PGSIZE);
// uart registers
kvmmap(kpgtbl, UART0, UART0, PGSIZE, PTE_R | PTE_W);
// virtio mmio disk interface
kvmmap(kpgtbl, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);
// PLIC
kvmmap(kpgtbl, PLIC, PLIC, 0x400000, PTE_R | PTE_W);
// map kernel text executable and read-only.
kvmmap(kpgtbl, KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);
// 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);
// 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);
// allocate and map a kernel stack for each process.
proc_mapstacks(kpgtbl);
return kpgtbl;
}
我們使用 gdb 一步步的看kvminit是如何完成 kernel page tables 的初始化，使用 gdb 模式啟動 xv6，並在另外一個視窗監看其記憶體以及暫存器狀態
make CPUS=1 qemu-gdb
在gdb中輸入 layout split 可以檢視程式碼執行到的斷點以及其組合語言結構
在 kvmmake() 設置中斷點於 kalloc() 執行處，可以發現到 kvmmake() 第一步為使用 kalloc() 為 level 0的 page directory 分配物理記憶體分頁，下一行使用 memset() 將 page 中的所有 bit 設置為0，包含 PTE 的所有 bit 也同樣設置為0。
接著會執行 kvmmap(kpgtbl, UART0, UART0, PGSIZE, PTE_R | PTE_W);，可以看到 UART0 為一個巨集定義，我們將物理記憶體地址 UART0 映射到虛擬記憶體地址的 UART0，也就是物理記憶體地址和虛擬記憶體地址是相同的，而這也對應到我們最上面一開始的物理記憶體與虛擬記憶體之間映射的對照圖，其餘 I/O 裝置，包含 VIRTIO0 和 PLIC 都進行了相同的操作。
而我們希望可以看到在這過程中 page tables 的內容，而我們在先前知道在 kernel/riscv.h 中定義了 page table 的大小，每一個 bit 域所代表的意義，PTE 中用於權限控制的 flag，以及 PPN 的部分，以下為 kernel/riscv.h 的部分內容
#define PGSIZE 4096 // bytes per page
#define PGSHIFT 12 // bits of offset within a page
#define PGROUNDUP(sz) (((sz)+PGSIZE-1) & ~(PGSIZE-1))
#define PGROUNDDOWN(a) (((a)) & ~(PGSIZE-1))
#define PTE_V (1L << 0) // valid
#define PTE_R (1L << 1)
#define PTE_W (1L << 2)
#define PTE_X (1L << 3)
#define PTE_U (1L << 4) // user can access
// shift a physical address to the right place for a PTE.
#define PA2PTE(pa) ((((uint64)pa) >> 12) << 10)
#define PTE2PA(pte) (((pte) >> 10) << 12)
#define PTE_FLAGS(pte) ((pte) & 0x3FF)
// extract the three 9-bit page table indices from a virtual address.
#define PXMASK 0x1FF // 9 bits
#define PXSHIFT(level) (PGSHIFT+(9*(level)))
#define PX(level, va) ((((uint64) (va)) >> PXSHIFT(level)) & PXMASK)
PA2PTE(pa): 將物理記憶體地址 (physical address aka PA)轉換成 PTE。PTE2PA(pte): 將 PTE 轉換成物理記憶體地址 (physical address aka PA)。PTE_FLAGS(pte): 取出 PTE 中用於權限控制的 flag 域，如是否能夠被 MMU 轉換等等。PXSHIFY(level): 前面我們知道 page table 為樹狀結構，可以根據 page table (page directory) 所在的 level 得知對應 VPN 的偏移量 (回想下圖，VPN 拆分成三個域，L2 對應到 level 0，L1 對應到 level 1...)
vm.c 中 freewalk() 中看到相關樹的遞迴走訪void
freewalk(pagetable_t pagetable)
{
// there are 2^9 = 512 PTEs in a page table.
for(int i = 0; i < 512; i++){
pte_t pte = pagetable[i];
if((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0){
// this PTE points to a lower-level page table.
uint64 child = PTE2PA(pte);//通過PTE走向子節點
freewalk((pagetable_t)child);
pagetable[i] = 0;
} else if(pte & PTE_V){
panic("freewalk: leaf");
}
}
kfree((void*)pagetable);
}
參數可以看到傳入的 pagetable 型別為 pagetable_t，根據巨集定義可以得知，pagetable_t 型別為 uint64 *，傳入的是一個指標，判斷 pagetable_t 本質上就是一個元素皆為 uint 64 的陣列。
在一個 page table (page directory) 中，中間 L2,L1,L0 都對應到相應的 PTE，而這裡使用 for 迴圈進行線性遍歷(對應到前面提及的，page directory 為可線性走訪的線性結構，這邊是陣列)
在 if 中會比對 PTE_V 欄位，也就是該 PTE 是否為 Vaild，以及比對權限 (只有葉節點才能夠進行讀寫以及執行的操作)，如果為非葉節點，則繼續進行遞迴走訪，而如果走到葉節點，則會開始由最底層開始回朔並且釋放記憶體。
而根據freewalk()我們可以寫出遍歷並印出 page table 的 function (此為lab3-1的內容)。
void vmprint(pagetable_t pagetable)
{
printf("page table %p\n", &pagetable);
ptTravsal(pagetable, 0);
}
void ptTravsal(pagetable_t pagetable, int level)
{
for(int i = 0; i < 512; i++)
{
pte_t pte = pagetable[i];
uint64 child = PTE2PA(pte);
if((pte & PTE_V))
{
for (int j = 0; j <= level; j++)
j == 0? (printf("..")) : (printf(" .."));
printf("%d: pte %p pa %p\n", i, pte, child);
}
if((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0)
ptTravsal((pagetable_t)child, level + 1);
}
}
而在上方，我們在 kvmmake() 中看到 kernel page 的初始化過程，我們可以使用上面的 vmprint() 將初始化過程的 kernel page 給印出來，我們試著觀察在 kvmmap(kpgtbl, UART0, UART0, PGSIZE, PTE_R | PTE_W); 結束後 kernel page table 的狀況，我們只需要在 kvmmap(kpgtbl, UART0, UART0, PGSIZE, PTE_R | PTE_W); 下一行插入 vmprint(kpgtbl) 即可實現 kpgtbl 為 kernel page table。
由右邊的 gdb 畫面中可以看到我們目前停在第31行，也就是我們執行完了 UART0 區段的虛擬記憶體映射並執行 vmprint(kpgtbl) 將 kernel page table 給印出來，可以發現在左邊印出了三層的樹狀結構，以下說明
kvmmap(UART0)page table 0x000000008001f0d8
..0: pte 0x0000000021fff801 pa 0x0000000087ffe000
.. ..128: pte 0x0000000021fff401 pa 0x0000000087ffd000
.. .. ..0: pte 0x0000000004000007 pa 0x0000000010000000
第一行: 根據我們 vmprint() 的程式碼，可以知道我們印出 page table 所在的記憶體地址，而我們傳入的 page table 為 kpgtbl，因此此為 kernel page table 所在的記憶體地址，而這個地址會儲存在satp CSR 中。
第二行: 可以看到 level 0的 page directory 只有一條 PTE，編號為0，而 PTE 中包含了 level 1的 page directory 的物理記憶體地址。
第三行: 可以看到 level 1的 page directory 只有一條 PTE，編號為128，包含 level 2的 page directory 的物理記憶體地址。
第四行: 可以看到 level 2的 page directory 只有一條 PTE，編號為0，而該節點即為頁節點，包含記憶體地址為物理記憶體地址 0x0000000010000000，而這也對應到了 UART0。
我們可以使用物理記憶體地址 0x0000000010000000 來回推 level 2中 page directory 的 PTE 編號。
1. 0x0000000010000000 先向右移12 bit
2. 00000000100000000 000000000000 虛擬記憶體為27 bit + 12 bit，
目前總長度28 bit，因此再向右移(27 + 12) - 28 = 11 bit
3. 000000001 000000000 000000000 000000000000
可以得到 L1為0, L2為128, L3為0，也就對應到了 level 2的編號128。
而我們可以觀察 level 2 page directory 的內容，將0x0000000004000007轉換成二進位後可以得到0100000000000000000000000111，可以發現最低位6 bit 的PTE_W, PTE_R, PTE_E都為1
也就是可讀寫，且是 vaild，可以被 MMU 從虛擬記憶體轉換到物理記憶體的PTE。
最後整個kernel page table配置完之後，便會回傳，而看到 main() 函式可以發現接著會執行 kvminithart()
void
kvminithart()
{
w_satp(MAKE_SATP(kernel_pagetable));
sfence_vma();
}
可以看到使用 w_satp 對 satp CSR 進行寫入，而寫入到 satp 的便是剛剛在 kvminit() 配置完成的 kernel_pagetable，這裡就是告訴 MMU 使用 satp 指向的 page table，這一行執行完畢後，program counter 會隨之變動，而到了下一條指令，program counter 中的值就會被記憶體中的 page table 進行轉換，也就是現在開始的記憶體地址都不再是物理記憶體地址，而是虛擬記憶體地址了。
這裡 0x80000442 就是虛擬記憶體地址了，而由於我們在最一開始提及，在 xv6 中大部分虛擬記憶體地址與物理記憶體地址之間的映射關係都是相等的，因此，下面我們還是能夠根據該記憶體地址去執行到正確的指令。
而如果我們錯誤的配置虛擬記憶體，就可能會產生出 kernel data 被覆蓋的問題，進而進到 guardpage 中，最終觸發 page fault。
SiFive FU540-C000 Manual v1p0
xv6-riscv
Operating System Concepts, 9/e
RISC-V xv6 Book
iThome鐵人賽
看影片追技術