Chapter 3: Page Tables
本文是對xv6-book中，第三章所講述的內容的摘要。
xv6-book版本：August 31， 2020
Foreword:
在上一章討論
記憶體虛擬化
時，我們已經提到過
頁表Page Tables
，本質上是基於
分頁Paging
這種記憶體空間管理方法，這是實現記憶體虛擬化的一個標準的解決方案。作業系統
為每個程序維護一個頁表
，現在它們各自有屬於自己的
虛擬地址空間
。頁表儲存從
虛擬地址VA
到
物理地址PA
的對映，它決定了程序的虛擬地址是否有意義，哪些物理記憶體是程序可以訪問的，等等。
有了頁表，每個程序在訪問物理記憶體時，只需要給出屬於自己空間內的虛擬地址，剩餘的地址轉換工作就交給
記憶體管理單元MMU
（Memory Management Unit）來完成，如下圖所示，避免了所有程序在同一物理記憶體上訪存的操作，透過一些頁表對映的規則，我們也能禁止程序之間隨意訪問對方的記憶體，因此使用頁表增強了程序之間的
隔離性
；原來單一的物理記憶體，在我們引入分頁和頁表，構建起了
虛擬記憶體系統
之後，單一的
物理地址空間
，現在被我們對映到多個獨立的虛擬地址空間中，這實現了物理記憶體的
複用
。
MMU完成虛擬地址到物理地址的轉換
除了提供隔離性和複用，頁表還可以有一些巧妙的用途：例如將同一頁物理幀，對映到多個虛擬地址空間中（例如xv6將trampoline這一頁放置在了每個程序虛擬地址空間的頂端），在虛擬地址空間中，設定一些保護頁guard page（用於保護各使用者棧和核心棧，防止棧溢位）等等。在接下來的內容裡，我們將進一步學習頁表。
3.1 Paging Hardware
在討論分頁之前，我們先探討一下構建虛擬記憶體系統時的一個重要話題——記憶體空間的管理。
先考慮一種最簡單的方式來管理程序的虛擬地址空間，用一對
基址—界限暫存器
，基址暫存器現在一般也稱為
重定位暫存器
，如下圖所示，很簡便地就能檢查相關虛擬地址是否合法。但這種方式過於簡單，如果你重點關注它在記憶體上的表現的話，很容易會發現，這種方式浪費了過多的物理記憶體。它事先假設程序的虛擬地址空間小於物理記憶體，為了執行程序，應該分配出一塊同等大小的物理記憶體來載入程序。首先，要找出
一大塊連續的且空閒的物理記憶體
是很不容易的，因為隨著使用時間增加，程序被載入又被移出物理記憶體，物理記憶體的空閒空間會變得零散化和碎片化，你必須在空閒物理記憶體的管理上多下功夫；其次，大部分使用者程序的
棧區和堆區並不大
，因此用於裝載整個程序的物理記憶體中，大量的空間將被浪費；最後，每次執行一個程序，都必須將其整個載入到物理記憶體中，顯然此解決方案不能支援
動態載入
，從而限制了程序的虛擬地址空間大小。顯然，我們需要更復雜的記憶體空間管理方式。
基址（重定位）-界限暫存器方式
一般作業系統有兩種記憶體空間管理方法。一種是將空間分割成不同長度的分片，基於這種思想的管理方法稱為
分段
，它將虛擬記憶體空間劃分為程式碼、堆、棧等多個邏輯段，分別為每個邏輯段維護一對基址—界限暫存器。現在對於堆和棧之間的一大片空閒區域，不需要在物理記憶體中找一塊大空間來裝載它們了。但同樣，分段也會有一些問題。一是由於段的大小不同，
空間碎片化
的問題會變得更加嚴重，儘管可以定期緊湊記憶體，整理
外部碎片
，但這是分段方法帶來的本質問題，無法避免；二是分段對於稀疏地址空間的支援還不夠好，例如有一個很大但稀疏的堆，它們都在一個邏輯段中，整個堆仍然需要完整地載入到物理記憶體中。
外部碎片
：物理記憶體中的空閒空間被分割成不同大小的小塊，後續分配請求可能失敗，因為沒有一塊足夠大的連續空閒空間，儘管總的空閒空間超出了請求的大小。
內部碎片
：分配程式給出的記憶體塊超出請求的大小，在塊中超出請求的空間可能因此而未被使用，造成了發生在已分配單元內部的浪費。
另一種記憶體空間管理方法是
分頁
，這次我們將空間切成
固定長度的分片
，徹底解決了外部碎片的問題。每個固定長度的單元我們稱之為
頁Page
，然後我們將物理記憶體看成是定長槽塊的陣列，這些槽塊大小與頁相同，每個槽塊叫做
頁幀Page Frame
，每個頁幀都可以裝載一個
虛擬記憶體頁
。同時，分頁很靈活，能很好地支援稀疏虛擬地址空間。因此在記憶體空間管理方面，分頁方案表現優異。一般的分頁硬體如下圖，在MMU中實現這些分頁硬體。
典型分頁硬體的組成
採用分頁還需要考慮幾個問題，一是怎麼記住從虛擬記憶體頁到物理頁幀的對映關係？如上圖所示，我們使用
頁表
；二是地址空間的龐大，使得頁表中的表項數量級大得驚人，對此我們使用
分級頁表
的方案來降低記憶體開銷；三是頁表查詢時間，使用頁表本質上使我們增加了一次或多次訪問物理記憶體的操作，訪存時間至少變為原來的2倍（採用多級頁表則開銷更多），這樣的開銷增加是不可接受的，對此可以引入轉換旁路緩衝儲存器
TLB
（
Translation-Lookaside-Buffer
）來快取一些轉換項，避免一大部分的訪存操作，如下圖所示。我們可以看到對於分頁的一些缺陷，現在都有比較好的應對方法，因此分頁是大部分作業系統都採用的解決方案。
引入了TLB的分頁硬體
xv6採用
分頁
的手段來構建虛擬記憶體系統，提供
頁表
完成虛擬地址到物理地址的轉換。
在上一章我們曾提到過，這裡再次提醒，RISC-V指令（使用者指令或核心指令）對
虛擬地址
進行操作，物理地址則是用於定址實際物理記憶體RAM的（RISC-V可以處理64位的虛擬地址，而物理地址只被設計成56位）。其次，xv6執行在Sv39 RISC-V處理器上，64位虛擬地址中，只有低39位在被使用，剩下的25位都暫時保留，供日後的設計者利用。
RISC-V的分頁硬體，將每個虛擬地址對映到一個物理地址，頁表會以某種形式的表項來儲存這種對映關係，這種表項我們稱之為
頁表條目PTE
（Page Table Entry）。
RISC-V頁表的簡化圖如下所示，如果我們將頁表看成一個簡單的線性陣列，那麼一個頁表可以儲存2^27個PTE，這是因為在虛擬地址有效的39位中，高27位是用來索引PTE的。
RISC-V頁表簡化圖
每個PTE由44位的
物理頁幀號PPN
和10位的
標誌位Flags
組成。有效位為54位的PTE可以用8B的大小來儲存，這剛好是一個uint64型別。虛擬地址有效的39位中，還有低12位稱為
（頁內）偏移量Offset
（xv6的分頁大小是
4KB
，即2^12B，這是一個比較常規的粒度，很多作業系統（如Linux）都支援4KB大小的分頁）。
在頁錶轉換一個虛擬地址時，首先提取出有效的39位，用高27位來索引對應的PTE，從PTE中我們可以得到44位的PPN，並且根據Flags檢查一些許可權，最後將44位的PPN和原虛擬地址的低12位Offset加在一起，得到最後56位的有效物理地址，接著就可以訪問物理記憶體。
下圖展示了RISC-V頁表真正的細節，它採用的是
多級頁表
的方案，一共有三級，整體上是一個
樹形
的結構。這種樹形結構的多級頁表節省了大量記憶體空間，你應該能想象到，多級頁表分配的頁表空間，與你正在使用的地址空間記憶體量成正比，它通常很緊湊，且支援稀疏的地址空間。頁表被設計為剛好一頁的大小（4KB），如果整頁的PTE都不存在/無效，就完全不分配該頁來裝載頁表。為了跟蹤裝載頁表的頁是否有效，引入
頁目錄PD
（Page Directory，即高兩級的頁表，xv6並沒有嚴格區分頁目錄和頁表，也不嚴格區分PDE和PTE，之後本文也統一使用頁表和PTE這兩個術語，但希望你知道實際情況是怎樣的）。頁目錄指出裝載頁表或下一級頁目錄的物理頁幀的位置；或者告訴我們頁表或下一級頁目錄的整個頁不包含有效頁，這時頁目錄的
頁目錄項PDE
（Page Directory Entry）也不存在/無效。
RISC-V的分級頁表方案
每級頁表的大小都被設計為4KB，剛好能裝進一頁物理幀內。前面提過，PTE用uint64型別來儲存，因此一個PTE佔用8B的空間，所以一個頁表可以包含512個PTE。在每一級頁表中，都取27位索引的其中9位來找到對應的PTE。透過查詢前兩級頁表的PTE，可以訪問新的物理頁幀，在該物理頁幀內儲存著下一級的頁表。當查詢最後一級頁表的PTE時，才將PPN和Offset結合，得到虛擬地址所對映的真正物理地址，然後再訪問使用者或核心需要的內容。
整個查詢頁表的過程一共要遍歷三層，如果這三次查詢有任意一次沒有命中，即對應PTE不存在，這種異常的情況稱為
缺頁錯誤Page-Fault
。因為是一個異常，所以程序會陷入核心，由核心來處理缺頁錯誤，然後一般地，核心為該程序調入所需的頁面，更新並設定好頁表的相關PTE，並且重新執行原使用者指令。（但在xv6裡，對於缺頁錯誤的異常，沒有定義如何處理）
現在我們來看一些PTE的標誌位Flags，這些標誌位告訴頁表硬體，關於使用者程序提供的虛擬地址的一些許可權資訊，這將指示頁表硬體怎麼對待這次地址轉換。
PTE_V
指示PTE是否存在/有效。如果不存在，嘗試引用該頁時就會引發一個缺頁錯誤異常。
PTE_R
指示這一頁物理幀是否能被讀。
PTE_W
指示這一頁物理幀是否能被寫。
PTE_X
指示這一頁物理幀是否能被CPU看待並轉換成指令來執行。
PTE_U
指示這一頁物理幀在使用者模式下是否能訪問。如果沒有置位，則該一頁物理幀只能在監管者模式下被訪問。
上一章我們提過，在xv6核心的啟動階段時，頁表是被禁用的。為了告訴RISC-V的分頁硬體，現在可以使用頁表了，核心必須將
根頁表
的物理地址寫入到
satp
暫存器中。每個CPU都有自己的satp暫存器。CPU在執行指令時，將使用自己的satp暫存器裡指向的根頁表，完成指令中虛擬地址的轉換。正因為每個CPU有自己的satp暫存器，因此不同CPU可以使用不同的頁表。這代表著不同的CPU，看到的程序虛擬記憶體檢視是不同的，每個satp暫存器指向不同程序的根頁表，反映了這些使用者程序各自的虛擬地址空間佈局。
最後我們再弄清楚一些概念，
物理記憶體
通常指的是
DRAM
中的儲存單元，物理記憶體中的每一位元組都對應一個物理地址。而
指令由始至終只使用虛擬地址
，位於MMU的分頁硬體負責，將CPU傳來的虛擬地址轉換為物理地址，然後將物理地址傳送到DRAM以讀取或寫入資料。我們不常用虛擬記憶體這一概念，我自己也不喜歡，因為實際上它並不存在於物理世界中，使用這一術語總是容易把它和虛擬地址或者物理記憶體弄混淆。建議把虛擬記憶體理解為一種機制而不是具體的物件可能會來得更好，比如你可以認為它指代的是，由核心提供的，管理虛擬地址空間和物理記憶體的一些抽象方法和機制，你可能已經發現了，
虛擬記憶體系統
指的就是這個。
3.2 Kernel Address Space
除了為每個使用者程序都維護一個頁表，xv6為核心也單獨維護了一個頁表。下圖展示了
核心的虛擬地址空間
如何對映到實際的物理地址空間中。
左圖是核心的虛擬地址空間，右圖是物理記憶體佈局
QEMU模擬的RAM，將從物理地址0x80000000（
KERNBASE
）開始，至少到0x86400000為止（
PHYSTOP
，在kernel/memlayout。h中定義其值為0x88000000，所以xv6的RAM實際大小為128M）。QEMU同樣也模擬了一些I/O裝置，這些裝置介面透過
記憶體對映
的方式，將裝置的
控制暫存器
對映到物理記憶體中，位於KERNBASE下。核心只要讀出或寫入這些特殊的物理地址，就能直接讀寫裝置的控制暫存器，從而直接地與裝置進行通訊。
// the kernel expects there to be RAM
// for use by the kernel and user pages
// from physical address 0x80000000 to PHYSTOP。
#define KERNBASE 0x80000000L
#define PHYSTOP （KERNBASE + 128*1024*1024）
//
這裡
PHYSTOP
=
0x88000000L
值得提醒的是，在上圖右半部分的物理記憶體檢視中，只有從KERNBASE到PHYSTOP才對應真正的
DRAM晶片
。位於PHYSTOP上方，未使用的空間是沒有DRAM晶片與之對應的，透過放置新的DRAM晶片，這部分空間可以被擴充套件並使用。而位於KERNBASE下方，訪問相應的物理地址，實際上是直接訪問相關I/O裝置的控制暫存器，而不是訪問DRAM晶片。
在核心未啟用頁表的時候，訪問RAM以及經過記憶體對映的裝置控制暫存器時，核心的虛擬地址將採用
直接對映
的方式進行轉換，即虛擬地址與實際物理地址相同。這種直接對映，也會在初始化核心頁表的過程中（kernel/vm。c的kvminit），記錄到核心頁表中，即使核心開始使用頁表，這種直接對映的佈局也被保留了下來。
使用直接對映，核心對物理記憶體的讀或寫變簡單了。例如在進行系統呼叫fork時，fork會為子程序分配記憶體，記憶體分配器因此返回指向一塊物理記憶體的物理地址，因為是直接對映，所以fork直接把返回的物理地址當成虛擬地址用（指令對虛擬地址進行操作），然後透過一系列指令將父程序的使用者記憶體複製到子程序。
核心的虛擬地址空間中，也有一些部分
不僅僅使用直接對映
。上圖的左半部分展示了，除了直接對映之外，還有一些額外的佈局與設定，它們位於核心虛擬地址空間的頂部，在初始化了核心頁表，並且啟用頁表之後，就可以正式使用這些佈局設定。
// map the trampoline page to the highest address，
// in both user and kernel space。
#define TRAMPOLINE （MAXVA - PGSIZE）
// map kernel stacks beneath the trampoline，
// each surrounded by invalid guard pages。
#define KSTACK（p） （TRAMPOLINE - （（p）+1）* 2*PGSIZE）
一是
trampoline
頁，它被對映到虛擬地址空間的頂端，使用者和核心的頁表裡都有這一項對映，擺放的位置相同，很快我們將在下一章介紹這一頁的作用。trampoline頁被映射了兩次，一次對映到虛擬地址空間的頂端，一次是直接對映（trampoline頁位於RAM中）。
二是
核心棧
，我們上一章提過每個程序都對應一個核心棧。更準確地說，每個程序在使用者空間執行指令時使用的是使用者棧，而在核心空間下執行時（一般稱為這個使用者程序的核心執行緒）使用的是核心棧，xv6核心是C程式碼，自然需要核心棧來儲存關於函式呼叫等資訊。核心棧是一頁頁地被分配的，從靠近PHYSTOP的位置開始往下分配。因此這些核心棧也在RAM當中，自然會被直接對映到核心的虛擬地址空間裡。現在我們再一次將這些核心棧對映到核心虛擬地址空間的高地址部分，這樣就可以自然地在它們之間插入一些
保護頁guard page
。保護頁的PTE_V是無效的，訪問它會引發缺頁錯誤的異常，從而陷入核心，這樣的設計可以防止核心棧溢位。同樣地，核心棧也被映射了兩次，但是如果只使用直接對映的方式，而仍要保留這些保護頁，那麼分佈於核心棧之間的那些保護頁會浪費一些物理記憶體。
對於核心程式碼和trampoline頁，標誌位PTE_R和PTE_X被設定，因此核心可以從這些頁中讀取內容並且直接當作指令執行。其它的頁則設定標誌位PTE_R和PTE_W，作為常規頁進行讀寫。
3.3 Code: Creating an Address Space
與xv6虛擬記憶體系統密切相關的程式碼位於kernel/vm。c中，下面我們來分析其中一部分程式碼。
總體上看，核心的資料結構是pagetable_t，它是uint64*型別，指向存放RISC-V根頁表的一頁，它可以是核心的根頁表，也可以是使用者程序的根頁表。核心的函式是walk和mappages。walk為給定的虛擬地址，找到其相應的PTE，如果PTE不存在則新分配一頁使之有效，它
模仿
的是真實分頁硬體查詢頁表的過程，可以看成是查詢頁表的
軟體實現
，在核心或程序的頁表未初始化時，核心就用它來轉換相關虛擬地址；mappages為給定輸入的對映建立PTE，更新頁表。其它以kvm開頭的函式對核心頁表進行操作，以uvm開頭的函式對使用者頁表進行操作，函式copyout和copyin完成核心空間和使用者空間之間的資料複製，等等。
在核心啟動階段，
main
（kernel/main。c）將呼叫
kvminit
建立核心頁表，如下所示。整個工作流程如下，首先分配新的一頁物理幀用於裝載核心的根頁表，然後呼叫kvmmap，在即將裝載的核心頁表上建立一系列的直接對映，包括I/O裝置、核心程式碼和資料、核心空閒記憶體段等，最後再把trampoline對映到核心虛擬地址的最頂端，完成了核心頁表的初始化。
extern
char
etext
［］；
// kernel。ld sets this to end of kernel code。
extern
char
trampoline
［］；
// trampoline。S
// create a direct-map page table for the kernel。
void
kvminit
（）
{
// allocates a page of physical memory to hold the root page-table page。
kernel_pagetable
=
（
pagetable_t
）
kalloc
（）；
memset
（
kernel_pagetable
，
0
，
PGSIZE
）；
// include the kernel’s instructions and data， physical memory up to PHYSTOP，
// and memory ranges which are actually devices。
// install mappings into a page table for a range of virtual addresses
// to a corresponding range of physical addresses
// uart registers
kvmmap
（
UART0
，
UART0
，
PGSIZE
，
PTE_R
|
PTE_W
）；
// virtio mmio disk interface
kvmmap
（
VIRTIO0
，
VIRTIO0
，
PGSIZE
，
PTE_R
|
PTE_W
）；
// CLINT
kvmmap
（
CLINT
，
CLINT
，
0x10000
，
PTE_R
|
PTE_W
）；
// PLIC
kvmmap
（
PLIC
，
PLIC
，
0x400000
，
PTE_R
|
PTE_W
）；
// 大小為kernel text（code）的大小
// map kernel text executable and read-only。
kvmmap
（
KERNBASE
，
KERNBASE
，
（
uint64
）
etext
-
KERNBASE
，
PTE_R
|
PTE_X
）；
// 從kernel text之後到PHYSTOP之前的區域都是kernel data和free memory
// xv6 uses the physical memory between the end of the kernel and PHYSTOP for run-time allocation。
// map kernel data and the physical RAM we‘ll make use of。
kvmmap
（（
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。
// TRAMPOLINE = MAXVA - PGSIZE
// 從最大虛擬地址向下分配一頁給trampoline
kvmmap
（
TRAMPOLINE
，
（
uint64
）
trampoline
，
PGSIZE
，
PTE_R
|
PTE_X
）；
}
kvmmap
做的工作很簡單，直接轉交給mappages，讓它建立核心頁表中的相關對映項。
// add a mapping to the kernel page table。
// only used when booting。
// does not flush TLB or enable paging。
void
kvmmap
（
uint64
va
，
uint64
pa
，
uint64
sz
，
int
perm
）
{
if
（
mappages
（
kernel_pagetable
，
va
，
sz
，
pa
，
perm
）
！=
0
）
panic
（
“kvmmap”
）；
}
現在來看比較重要的
mappages
函式，它的輸入是一個頁表、要建立對映關係的va和pa、對映的範圍大小、以及PTE的許可權。mappages
以頁為單位
處理這些輸入，呼叫walk為va查詢最後一級頁表的PTE，如果該PTE沒有被佔用（輸入新的對映時，walk會返回有效位為0的PTE，代表沒有人在使用這項對映），就用輸入的pa和PTE許可權，更新該PTE項並設定其有效，從而在頁表中建立起新對映，反覆進行直到輸入的所有對映關係都被建立完成。
// Create PTEs for virtual addresses starting at va that refer to
// physical addresses starting at pa。 va and size might not
// 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
）
{
// installs PTEs for new mappings
// this mapping is separately for each virtual address in the range， at page intervals
uint64
a
，
last
；
pte_t
*
pte
；
a
=
PGROUNDDOWN
（
va
）；
last
=
PGROUNDDOWN
（
va
+
size
-
1
）；
// 為va的起始和終止地址分別向下向上取頁大小4096的整
for
（；；）{
// calls walk to find the address of the PTE for that address
if
（（
pte
=
walk
（
pagetable
，
a
，
1
））
==
0
）
// walk為虛擬地址a分配PTE失敗
return
-
1
；
if
（
*
pte
&
PTE_V
）
// 該PTE已經被別的va對映，有效位有效
panic
（
“remap”
）；
// 將物理地址pa的PPN提取出來，加上標誌位資訊perm和有效位
// 然後將該條目放到PTE中
*
pte
=
PA2PTE
（
pa
）
|
perm
|
PTE_V
；
if
（
a
==
last
）
// 分到了足夠頁數就返回
break
；
a
+=
PGSIZE
；
pa
+=
PGSIZE
；
// 已經分配了一頁，虛擬地址的起始位置和物理地址起始位置都加一頁
}
return
0
；
}
接著我們觀察
walk
函式，walk函式也很重要，它模仿RISC-V頁表硬體的行為，並用軟體來實現，從而在頁表未被初始化時，幫助核心完成頁表的查詢。walk為輸入的va找到其對應的
最後一級頁表的PTE
。每次都透過va中的9位來索引某一級頁表的相應PTE。如果PTE指示我們，下一級頁表不存在，而alloc設定為1，walk就會請求為下一級頁表分配新的一頁，並且更新該PTE。如此遍歷，walk最後返回的是最後一級頁表的PTE，且路徑上經過的三級頁表都一定已經被分配了物理幀，並被建立起來。
需要注意的是，如果傳入的是新va，相關的對映未被建立，那麼walk只會建立第二級和第三級頁表（根頁表是已經存在的），為它們分配新的物理幀，walk並
沒有
為最後一級頁表的PTE所指向的物理幀分配新的一頁。也就是說，如果這個對映是新的，透過walk返回的PTE是無效的（全0），如果原來就有這個對映，那麼walk就返回包含對映內容的PTE。
// Return the address of the PTE in page table pagetable
// that corresponds to virtual address va。 If alloc！=0，
// create any required page-table pages。
//
// The risc-v Sv39 scheme has three levels of page-table
// pages。 A page-table page contains 512 64-bit PTEs。
// A 64-bit virtual address is split into five fields：
// 39。。63 —— must be zero。
// 30。。38 —— 9 bits of level-2 index。
// 21。。29 —— 9 bits of level-1 index。
// 12。。20 —— 9 bits of level-0 index。
// 0。。11 —— 12 bits of byte offset within the page。
pte_t
*
walk
（
pagetable_t
pagetable
，
uint64
va
，
int
alloc
）
{
// walk函式為給定va找到其對應的PTE
// returns the address of the PTE in the lowest layer in the tree
if
（
va
>=
MAXVA
）
panic
（
“walk”
）；
for
（
int
level
=
2
；
level
>
0
；
level
——
）
{
pte_t
*
pte
=
&
pagetable
［
PX
（
level
，
va
）］；
// 根據當前level，對va進行移位和掩碼操作，得到當前level頁表中的對應PTE條目
// level=2時，向右移出12+2*9=30位，經掩碼後得到9位level=2頁表的PTE編號
// level=1時，向右移出12+9=21位，經掩碼後得到9位level=1頁表的PTE編號
if
（
*
pte
&
PTE_V
）
{
// 判斷有效位
pagetable
=
（
pagetable_t
）
PTE2PA
（
*
pte
）；
// 提取物理地址，對應一個頁的首地址
// 將最右10位標誌位移出，補充12位全0的偏移位，原44位PPN保留，得到指向下一層頁表的物理地址
// level=2時，pagetable指向level=1的頁表
// level=1時，pagetable指向level=0的頁表
}
else
{
// 對應PTE不存在，且alloc被置位，則為該PTE指向的下一層頁表分配一頁
if
（
！
alloc
||
（
pagetable
=
（
pde_t
*
）
kalloc
（））
==
0
）
return
0
；
// 一切清0，新分配的下一級頁表的所有PTE也都是無效的
memset
（
pagetable
，
0
，
PGSIZE
）；
// 更新PTE，將56位物理地址右移12位去掉偏移位，移進10位標誌位，同時將PTE_V置1
*
pte
=
PA2PTE
（
pagetable
）
|
PTE_V
；
}
}
// 跳出while後，此時pagetable指向level=0的頁表
return
&
pagetable
［
PX
（
0
，
va
）］；
// level=0，向右移出12位，經掩碼後得到9位level=0頁表的PTE編號
// 返回va對應的level=0頁表中的對應PTE
}
值得注意的細節是，在頁表未被啟用，核心利用以上函式初始化核心頁表時，能夠正常工作，是建立在核心虛擬地址空間被
直接對映
到物理記憶體的
前提
下。核心有一個物理記憶體分配器
kalloc
，我們馬上將會介紹它。它為核心頁表分配一頁，該分配器從RAM的頂端開始，也就是
free memory
區域往下按頁分配物理記憶體，而我們知道RAM是直接對映到核心虛擬地址空間的。因此在核心空間下，可以把kalloc返回的物理地址直接當作虛擬地址使用。
這一點，在核心初始化使用者頁表的時候也是相容的，建立使用者程序的頁表是在核心空間下進行操作，自然享受到了直接對映的好處。因此，在walk中，我們從PTE中抽取出了下一級頁表的pa，而下一個迴圈裡我們就把該pa當作va來訪問下一級頁表，抽取新的PTE。
kvminit呼叫完成後，核心頁表被初始化完畢，接著main就呼叫
kvminithart
裝載核心頁表。該函式將核心根頁表的物理地址寫入到satp暫存器中，在這之後CPU就會使用核心頁表來完成地址轉換。從這之後開始，核心下一條指令的虛擬地址將對映到正確的物理地址。
// Switch h/w page table register to the kernel‘s page table，
// and enable paging。
void
kvminithart
（）
{
// install the kernel page table
// writes the physical address of the root page-table page into the register satp
// After this the CPU will translate addresses using the kernel page table
w_satp
（
MAKE_SATP
（
kernel_pagetable
））；
// flushes the current CPU’s TLB
// 此外，在trampoline中，switches to a user page table before returning to user space，也會重新整理TLB
sfence_vma
（）；
}
還是在核心空間下，main馬上就呼叫
procinit
，為每個使用者程序分配一個核心棧，該核心棧將被對映到核心虛擬地址空間的高地址部分，位於trampoline下方。生成虛擬地址的步長為2頁，而且只處理低的那一頁，這樣高的一頁就自動成了保護頁（PTE_V無效）。更新了所有核心棧的PTE之後，最後呼叫kvminithart更新一次satp暫存器，分頁硬體就能使用新的頁表。
// initialize the proc table at boot time。
void
procinit
（
void
）
{
struct
proc
*
p
；
initlock
（
&
pid_lock
，
“nextpid”
）；
// 開始時p=proc，即p的地址是proc陣列的最開始位置
// 每次遍歷p就指向下一個程序結構
for
（
p
=
proc
；
p
<
&
proc
［
NPROC
］；
p
++
）
{
initlock
（
&
p
->
lock
，
“proc”
）；
// Allocate a page for a kernel stack， for each process
// Map it high in memory at the va generated by KSTACK， followed by an invalid guard page。
char
*
pa
=
kalloc
（）；
if
（
pa
==
0
）
panic
（
“kalloc”
）；
// 指標相減就是地址相減，獲取當前程序p和proc陣列最開始位置的偏移量
// 比如第一次，從p-proc=0開始，KSTACK生成虛擬地址： TRAMPOLINE - 2*PGSIZE
// 因此TRAMPOLINE的下面第一頁是guard page，第二頁是kstack，也就是va指向的位置
// 後面也以此類推，被跳過而未被處理的guard page，PTE_V是無效的
uint64
va
=
KSTACK
（（
int
）
（
p
-
proc
））；
// adds the mapping PTEs to the kernel page table
// 核心棧可讀可寫，但在使用者態不可訪問，也不能直接執行
kvmmap
（
va
，
（
uint64
）
pa
，
PGSIZE
，
PTE_R
|
PTE_W
）；
p
->
kstack
=
va
；
}
// 將更新後的核心頁表重新寫入到satp中
kvminithart
（）；
}
RISC-V的CPU也使用
TLB
來快取va到pa的轉換，避免反覆查詢頁錶帶來的巨大記憶體開銷。xv6在更改頁表之後，必須告訴CPU，其快取的TLB項可能已經失效，否則TLB稍後可能使用一箇舊的快取項，訪問一頁已經被分配給其它程序的舊物理幀，打破了我們之前建立的
隔離
機制。
RISC-V提供了
sfence.vma
指令來
重新整理/清空flush
當前CPU的TLB。在kvminithart的最後，每次更新頁表到satp暫存器之後，都會flush當前CPU的TLB。還有一處地方也會這麼做，位於trampoline程式碼中，發生在將使用者頁表寫到satp暫存器，並準備返回到使用者空間時。
3.4 Physical Memory Allocation
核心在執行時會分配和釋放很多物理記憶體，xv6將一部分的物理記憶體，從kernel data結束開始，到PHYSTOP為止，這一部分稱為free memory，用於執行時的記憶體分配。每次分配和回收都
以頁為單位
，一頁大小4KB，透過一個
空閒物理幀連結串列free-list
，將空閒的物理幀串起來儲存。頁表、使用者記憶體、核心棧、管道緩衝區等作業系統元件需要記憶體時，核心就從free-list上摘下一頁或者多頁分配給它們；在回收已經分配出去的記憶體時，這些被回收的物理幀，核心將它們一頁頁地重新掛到free-list上。
3.5 Code: Physical Memory Allocator
現在我們來看看核心的
記憶體分配器
，該模組位於kernel/kalloc。c中。分配器使用的資料結構很簡單，如下所示，就是一個struct kmem，有一把保護free-list的自旋鎖，每一頁物理幀都透過struct run串在一起，struct run被儲存在每個空閒物理頁內部。
struct
run
{
struct
run
*
next
；
}；
struct
{
struct
spinlock
lock
；
struct
run
*
freelist
；
}
kmem
；
在main中呼叫
kinit
來完成記憶體分配器的初始化。kinit初始化保護free-list的自旋鎖，然後給出起始地址：kernel data結束的位置（end［ ］），終止地址：PHYSTOP，呼叫freerange。
extern
char
end
［］；
// first address after kernel。
// defined by kernel。ld。
//initialize the allocator
void
kinit
（）
{
// initializes the free list to hold every page between the end of the kernel and PHYSTOP
// xv6 assumes that the machine has 128MB of RAM
initlock
（
&
kmem
。
lock
，
“kmem”
）；
// kernel data之後到PHYSTOP之前都可以用於分配
// add memory to the free list via per-page calls to kfree
freerange
（
end
，
（
void
*
）
PHYSTOP
）；
}
freerange
回收一大片已分配的物理記憶體。它將輸入的兩個物理地址之間的所有物理頁，
對每一頁都呼叫kfree
，以將它們掛到free-list上。注意這些操作都是以頁為單位的，所以需要用PGROUNDUP來對齊地址。輸入地址的型別是void*，因為我們有時用其做加法（在遍歷所有頁時），有時用其直接讀或寫入物理記憶體（例如修改物理幀中的struct run），以及在分配和回收物理幀時，本質上可能改變了物理記憶體的型別。因此統一使用void*型別，便於在C語言中使用強制型別轉換來操作。
void
freerange
（
void
*
pa_start
，
void
*
pa_end
）
{
char
*
p
；
p
=
（
char
*
）
PGROUNDUP
（（
uint64
）
pa_start
）；
//kfree是頭插法
for
（；
p
+
PGSIZE
<=
（
char
*
）
pa_end
；
p
+=
PGSIZE
）
kfree
（
p
）；
}
kfree
回收一頁已分配的物理幀。分配器開始時沒有記憶體能夠分配，只有對每一頁呼叫kfree之後，free-list上才有空閒物理頁。開始時，kfree先把將要回收的一頁物理頁，透過memset把所有位元組置1，因此這頁物理幀的此前擁有者再次讀取它時，讀到的會是垃圾資料。接著將指向物理頁的pa指標轉換成struct run*型別，並且使用
頭插法
，掛到原來的free-list上。
// Free the page of physical memory pointed at by v，
// 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”
）；
// Fill with junk to catch dangling refs。
memset
（
pa
，
1
，
PGSIZE
）；
// casts pa to a pointer to struct run， which records the old start of the free list in r->next，
// and sets the free list equal to r
r
=
（
struct
run
*
）
pa
；
acquire
（
&
kmem
。
lock
）；
r
->
next
=
kmem
。
freelist
；
kmem
。
freelist
=
r
；
release
（
&
kmem
。
lock
）；
}
在kinit呼叫完成後，核心的記憶體分配器準備就緒，free-list上已經有相當多的空閒物理幀可供分配。分配器呼叫
kalloc
來分配一頁物理幀，直接取free-list裡的
第一頁
以滿足請求。
// 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
）
{
// removes and returns the first element in the free list。
// When a process asks xv6 for more user memory， xv6 first uses kalloc to allocate physical pages。
struct
run
*
r
；
acquire
（
&
kmem
。
lock
）；
r
=
kmem
。
freelist
；
if
（
r
）
kmem
。
freelist
=
r
->
next
；
release
（
&
kmem
。
lock
）；
if
（
r
）
memset
（（
char
*
）
r
，
5
，
PGSIZE
）；
// fill with junk
return
（
void
*
）
r
；
}
值得注意的是，在kinit初始化核心記憶體分配器時，呼叫freerange時傳入的起始地址是end，終止地址是PHYSTOP，freerange按照物理地址從小到大的順序呼叫kfree。而kfree使用頭插法插入free-list，因此初始化完成後的free-list中，物理地址大的物理幀位於連結串列的前面。所以kalloc在分配物理幀時，
從大的物理地址開始往下分配
。
3.6 Process Address Space
前面我們已經討論過核心的虛擬地址空間，現在我們來看
使用者程序的虛擬地址空間
，每個使用者程序都有自己的頁表，因此也有不同的虛擬地址空間。
使用者程序的虛擬地址空間同樣從0開始，一直到MAXVA（2^38-1），這其中有多達256GB的空間。一個使用者程序如果在執行時需要額外記憶體，就向核心記憶體分配器發出請求，讓kalloc分配一些物理頁，然後核心會更新使用者程序的頁表，設定新的PTE（此前提到的5個標誌位都被設定）。程序中間那些未使用的虛擬地址，只需要在頁表中將相關的PTE標記為無效即可。
我們再次說明使用頁表的好處。一是使用者程序現在都有自己的頁表，在程序之間提供了
隔離性
。二是使用者的虛擬地址空間是
連續
的，而對應的物理幀分佈可以是
不連續
的。三是透過頁表，核心可以將trampoline頁對映到使用者虛擬地址空間的頂端，所有程序都可以看到這一頁。
使用者程序虛擬地址空間的佈局如下圖所示。與第二章裡的圖相比，在這裡我們看到了更多細節，尤其是
使用者棧
的細節。圖中使用者棧的
初始內容
是由系統呼叫
exec
產生的。在初始的使用者棧上包括了：各命令列引數的字串，指向各命令列引數的指標陣列argv［ ］，用於從呼叫
main(argc, argv[ ])
返回的其它引數（argc、argv指標和偽造的返回pc值）。在初始使用者棧的內容被設定好之後，使用者程式就返回並開始執行main函式。
使用者程序的虛擬地址空間
同樣地，為了防止使用者棧溢位，在棧的下面也放置了一頁保護頁。棧溢位時會訪問到該保護頁，從而出現缺頁錯誤異常，使用者程序因此陷入核心並等待處理，核心可能會終止掉該程序。而現在的作業系統在這種情況下，一般都會自動地為使用者棧分配更多的空間。
值得注意的地方有兩點：首先是這裡的保護頁，和核心虛擬地址空間中那些核心棧之間的保護頁有所不同。這裡的保護頁是
有實際的物理幀
對應的，即核心確實為使用者程序分配這一頁（標誌位為RWV，沒有U）；而在核心空間下，核心棧之間的保護頁PTE_V無效，並沒有實際分配物理頁。然後是user text和data，xv6為了簡單起見，將它們放在了同一頁內。實際上現在的作業系統都會將它們放在不同的頁內，這一點也可以透過在編譯時指定-N選項來強制實現。
3.7 Code: Sbrk
Sbrk
是一個系統呼叫，使用者程序呼叫它以增加或減少自己擁有的物理記憶體（proc->sz）。
uint64
sys_sbrk
（
void
）
{
int
addr
；
int
n
；
if
（
argint
（
0
，
&
n
）
<
0
）
return
-
1
；
addr
=
myproc
（）
->
sz
；
if
（
growproc
（
n
）
<
0
）
return
-
1
；
return
addr
；
}
growproc
根據增加或減少記憶體的需要，又分別呼叫uvmmalloc和uvmdealloc來滿足請求。
// Grow or shrink user memory by n bytes。
// Return 0 on success， -1 on failure。
// Sbrk is implemented by the function growproc
int
growproc
（
int
n
）
{
uint
sz
；
struct
proc
*
p
=
myproc
（）；
sz
=
p
->
sz
；
// 是從sz接著分配記憶體給增長需要的
// 也就是緊接著user text、user data、guard page和user stack之後
// 從那個虛擬地址繼續開始分配
if
（
n
>
0
）{
if
（（
sz
=
uvmalloc
（
p
->
pagetable
，
sz
，
sz
+
n
））
==
0
）
{
return
-
1
；
}
}
else
if
（
n
<
0
）{
sz
=
uvmdealloc
（
p
->
pagetable
，
sz
，
sz
+
n
）；
}
p
->
sz
=
sz
；
return
0
；
}
uvmalloc
透過呼叫kalloc來分配物理記憶體，並呼叫mappages來更新頁表，並設定PTE的5個標誌位都置位。
// Allocate PTEs and physical memory to grow process from oldsz to
// newsz， which need not be page aligned。 Returns new size or 0 on error。
uint64
uvmalloc
（
pagetable_t
pagetable
，
uint64
oldsz
，
uint64
newsz
）
{
char
*
mem
；
uint64
a
；
if
（
newsz
<
oldsz
）
return
oldsz
；
oldsz
=
PGROUNDUP
（
oldsz
）；
for
（
a
=
oldsz
；
a
<
newsz
；
a
+=
PGSIZE
）{
// allocates physical memory with kalloc， and adds PTEs to the user page table with mappages
mem
=
kalloc
（）；
if
（
mem
==
0
）{
uvmdealloc
（
pagetable
，
a
，
oldsz
）；
return
0
；
}
memset
（
mem
，
0
，
PGSIZE
）；
if
（
mappages
（
pagetable
，
a
，
PGSIZE
，
（
uint64
）
mem
，
PTE_W
|
PTE_X
|
PTE_R
|
PTE_U
）
！=
0
）{
kfree
（
mem
）；
uvmdealloc
（
pagetable
，
a
，
oldsz
）；
return
0
；
}
}
return
newsz
；
}
uvmdealloc
呼叫uvmunmap來回收已分配的物理記憶體。
// Deallocate user pages to bring the process size from oldsz to
// newsz。 oldsz and newsz need not be page-aligned， nor does newsz
// need to be less than oldsz。 oldsz can be larger than the actual
// process size。 Returns the new process size。
uint64
uvmdealloc
（
pagetable_t
pagetable
，
uint64
oldsz
，
uint64
newsz
）
{
if
（
newsz
>=
oldsz
）
return
oldsz
；
if
（
PGROUNDUP
（
newsz
）
<
PGROUNDUP
（
oldsz
））{
int
npages
=
（
PGROUNDUP
（
oldsz
）
-
PGROUNDUP
（
newsz
））
/
PGSIZE
；
// calls uvmunmap，
// which uses walk to find PTEs and kfree to free the physical memory they refer to。
uvmunmap
（
pagetable
，
PGROUNDUP
（
newsz
），
npages
，
1
）；
}
return
newsz
；
}
uvmunmap
使用walk找到相應的PTE，並且呼叫kfree回收相應的物理幀。在xv6中，使用者程序的頁表不僅告訴了分頁硬體如何轉換虛擬地址，也記錄著哪些物理幀被分配給該使用者程序，因此在回收分配給使用者的物理幀之前，應該先檢查相關的PTE是否存在/有效。
// Remove npages of mappings starting from va。 va must be
// page-aligned。 The mappings must exist。
// Optionally free the physical memory。
void
uvmunmap
（
pagetable_t
pagetable
，
uint64
va
，
uint64
npages
，
int
do_free
）
{
uint64
a
；
pte_t
*
pte
；
if
（（
va
%
PGSIZE
）
！=
0
）
panic
（
“uvmunmap： not aligned”
）；
for
（
a
=
va
；
a
<
va
+
npages
*
PGSIZE
；
a
+=
PGSIZE
）{
if
（（
pte
=
walk
（
pagetable
，
a
，
0
））
==
0
）
panic
（
“uvmunmap： walk”
）；
if
（（
*
pte
&
PTE_V
）
==
0
）
// examination of the user page table
// xv6 uses a process’s page table as the only record
// of which physical memory pages are allocated to that process
panic
（
“uvmunmap： not mapped”
）；
if
（
PTE_FLAGS
（
*
pte
）
==
PTE_V
）
panic
（
“uvmunmap： not a leaf”
）；
if
（
do_free
）{
uint64
pa
=
PTE2PA
（
*
pte
）；
kfree
（（
void
*
）
pa
）；
}
*
pte
=
0
；
}
}
3.8 Code: Exec
現在我們來看最後一段程式碼，系統呼叫
exec
的實現（kernel/exec。c）。我們之前知道，系統呼叫exec將儲存在檔案系統上的，新的使用者程式裝載進記憶體裡，然後執行它。現在我們將進一步觀察，在exec中，這個新使用者程序的虛擬地址空間是怎麼被建立起來的。
int exec（char *path， char **argv）
exec透過路徑名開啟檔案，然後讀取該檔案的
ELF Header
（kernel/elf。h）。xv6的所有應用程式以通用的
ELF格式
來描述，一個ELF二進位制檔案大概這樣組成（更準確的定義，建議查閱相關資料，這裡進行簡單的不嚴謹的說明）：一個ELF Header，後面緊跟一系列的Program Section Headers。每個Program Section Header都對應一段需要載入到記憶體中的程式，xv6的應用程式只有一個Program Section Header，而在其它作業系統上可能有好幾個。
// File header
struct
elfhdr
{
uint
magic
；
// must equal ELF_MAGIC
uchar
elf
［
12
］；
ushort
type
；
ushort
machine
；
uint
version
；
uint64
entry
；
uint64
phoff
；
uint64
shoff
；
uint
flags
；
ushort
ehsize
；
ushort
phentsize
；
ushort
phnum
；
ushort
shentsize
；
ushort
shnum
；
ushort
shstrndx
；
}；
// Program section header
struct
proghdr
{
uint32
type
；
uint32
flags
；
uint64
off
；
uint64
vaddr
；
uint64
paddr
；
uint64
filesz
；
uint64
memsz
；
uint64
align
；
}；
// Format of an ELF executable file
#define ELF_MAGIC 0x464C457FU
// “\x7FELF” in little endian
// Values for Proghdr type
#define ELF_PROG_LOAD 1
// Flag bits for Proghdr flags
#define ELF_PROG_FLAG_EXEC 1
#define ELF_PROG_FLAG_WRITE 2
#define ELF_PROG_FLAG_READ 4
exec讀取了檔案系統上的檔案之後，第一件事就是先檢查該檔案是否包含ELF二進位制檔案。
// Check ELF header
// exec的第一步是檢查檔案是否包ELF二進位制檔案。
// ELF二進位制檔案是以4個“magic number”開頭的，即0x7F，“E”，“L”，“F”，即宏定義ELF_MAGIC。
// 如果ELF頭中包含正確的magic number，exec就認為該ELF二進位制檔案的結構是正確的。
if
（
readi
（
ip
，
0
，
（
uint64
）
&
elf
，
0
，
sizeof
（
elf
））
！=
sizeof
（
elf
））
goto
bad
；
if
（
elf
。
magic
！=
ELF_MAGIC
）
goto
bad
；
接著，exec為使用者程序呼叫proc_pagetable，透過uvmcreate建立一個空的使用者頁表，接著只在該頁表上添加了trampoline和trapframe的對映，其它的虛擬地址空間都暫時為空。
//exec透過proc_pagetable分配了一個沒有使用者部分對映的頁表
if
（（
pagetable
=
proc_pagetable
（
p
））
==
0
）
goto
bad
；
// Create a user page table for a given process，
// with no user memory， but with trampoline pages。
pagetable_t
proc_pagetable
（
struct
proc
*
p
）
{
pagetable_t
pagetable
；
// An empty page table。
pagetable
=
uvmcreate
（）；
if
（
pagetable
==
0
）
return
0
；
// map the trampoline code （for system call return）
// at the highest user virtual address。
// only the supervisor uses it， on the way
// to/from user space， so not PTE_U。
if
（
mappages
（
pagetable
，
TRAMPOLINE
，
PGSIZE
，
（
uint64
）
trampoline
，
PTE_R
|
PTE_X
）
<
0
）{
uvmfree
（
pagetable
，
0
）；
return
0
；
}
// map the trapframe just below TRAMPOLINE， for trampoline。S。
if
（
mappages
（
pagetable
，
TRAPFRAME
，
PGSIZE
，
（
uint64
）（
p
->
trapframe
），
PTE_R
|
PTE_W
）
<
0
）{
uvmunmap
（
pagetable
，
TRAMPOLINE
，
1
，
0
）；
uvmfree
（
pagetable
，
0
）；
return
0
；
}
return
pagetable
；
}
// create an empty user page table。
// returns 0 if out of memory。
pagetable_t
uvmcreate
（）
{
pagetable_t
pagetable
；
pagetable
=
（
pagetable_t
）
kalloc
（）；
if
（
pagetable
==
0
）
return
0
；
memset
（
pagetable
，
0
，
PGSIZE
）；
return
pagetable
；
}
然後，exec對於每個程式段，先是呼叫uvmalloc分配足夠的物理幀，更新了使用者頁表。然後呼叫loadseg載入程式段到這些物理幀中。loadseg將虛擬地址傳給walkaddr，walkaddr又透過walk查詢相關PTE，將va轉換為pa，最後walkaddr成功返回uvmalloc分配的物理幀的物理地址，loadseg再呼叫readi，真正地將程式段載入到物理記憶體中。
// Load program into memory
for
（
i
=
0
，
off
=
elf
。
phoff
；
i
<
elf
。
phnum
；
i
++
，
off
+=
sizeof
（
ph
））{
if
（
readi
（
ip
，
0
，
（
uint64
）
&
ph
，
off
，
sizeof
（
ph
））
！=
sizeof
（
ph
））
goto
bad
；
if
（
ph
。
type
！=
ELF_PROG_LOAD
）
continue
；
if
（
ph
。
memsz
<
ph
。
filesz
）
goto
bad
；
if
（
ph
。
vaddr
+
ph
。
memsz
<
ph
。
vaddr
）
goto
bad
；
uint64
sz1
；
// 再透過uvmalloc為每個ELF段分配記憶體
if
（（
sz1
=
uvmalloc
（
pagetable
，
sz
，
ph
。
vaddr
+
ph
。
memsz
））
==
0
）
goto
bad
；
sz
=
sz1
；
if
（
ph
。
vaddr
%
PGSIZE
！=
0
）
goto
bad
；
// 然後透過loadseg把段的內容載入物理記憶體中
// loadseg透過walkaddr找到寫入ELF段的記憶體的物理地址；透過readi來將段的內容從檔案中讀出
if
（
loadseg
（
pagetable
，
ph
。
vaddr
，
ip
，
ph
。
off
，
ph
。
filesz
）
<
0
）
goto
bad
；
}
// Load a program segment into pagetable at virtual address va。
// va must be page-aligned
// and the pages from va to va+sz must already be mapped。
// Returns 0 on success， -1 on failure。
static
int
loadseg
（
pagetable_t
pagetable
，
uint64
va
，
struct
inode
*
ip
，
uint
offset
，
uint
sz
）
{
uint
i
，
n
；
uint64
pa
；
if
（（
va
%
PGSIZE
）
！=
0
）
panic
（
“loadseg： va must be page aligned”
）；
for
（
i
=
0
；
i
<
sz
；
i
+=
PGSIZE
）{
pa
=
walkaddr
（
pagetable
，
va
+
i
）；
if
（
pa
==
0
）
panic
（
“loadseg： address should exist”
）；
if
（
sz
-
i
<
PGSIZE
）
n
=
sz
-
i
；
else
n
=
PGSIZE
；
if
（
readi
（
ip
，
0
，
（
uint64
）
pa
，
offset
+
i
，
n
）
！=
n
）
return
-
1
；
}
return
0
；
}
// Look up a virtual address， return the physical address，
// or 0 if not mapped。
// Can only be used to look up user pages。
uint64
walkaddr
（
pagetable_t
pagetable
，
uint64
va
）
{
pte_t
*
pte
；
uint64
pa
；
if
（
va
>=
MAXVA
）
return
0
；
pte
=
walk
（
pagetable
，
va
，
0
）；
if
（
pte
==
0
）
return
0
；
if
（（
*
pte
&
PTE_V
）
==
0
）
return
0
；
if
（（
*
pte
&
PTE_U
）
==
0
）
return
0
；
pa
=
PTE2PA
（
*
pte
）；
return
pa
；
}
至此，exec已經將使用者程式的各程式段都裝載完成了。現在exec分配並初始化使用者棧。
exec首先分配兩頁物理幀。第一頁用作保護頁，透過呼叫uvmclear將PTE_U設為無效，這樣在使用者空間下不能訪問它；第二頁留給使用者棧，從棧頂開始，將命令列引數的字串、指向這些命令列引數的指標陣列argv［ ］、用於從呼叫main（argc， argv［ ］）返回的其它引數（argc、argv指標和偽造的返回pc值）推入使用者棧內。
// 到這裡，使用者空間的text和data都已經載入完畢了
// Allocate two pages at the next page boundary。
// 緊接著data的位置向上繼續分配兩個頁，第一頁用作guard page，第二頁用作user stack
// ustack中的前三項就是偽造的返回PC值，argc和argv指標
sz
=
PGROUNDUP
（
sz
）；
uint64
sz1
；
if
（（
sz1
=
uvmalloc
（
pagetable
，
sz
，
sz
+
2
*
PGSIZE
））
==
0
）
goto
bad
；
sz
=
sz1
；
// uvmclear將PTE_U設為無效，因此這一頁用作保護頁
uvmclear
（
pagetable
，
sz
-
2
*
PGSIZE
）；
sp
=
sz
；
stackbase
=
sp
-
PGSIZE
；
// Push argument strings， prepare rest of stack in ustack。
for
（
argc
=
0
；
argv
［
argc
］；
argc
++
）
{
if
（
argc
>=
MAXARG
）
goto
bad
；
sp
-=
strlen
（
argv
［
argc
］）
+
1
；
sp
-=
sp
%
16
；
// riscv sp must be 16-byte aligned
if
（
sp
<
stackbase
）
goto
bad
；
if
（
copyout
（
pagetable
，
sp
，
argv
［
argc
］，
strlen
（
argv
［
argc
］）
+
1
）
<
0
）
// 保護頁還讓exec能夠處理那些過於龐大的引數；當引數過於龐大時，
// exec 用於將引數複製到棧上的函式copyout會發現目標頁無法訪問，並且返回-1
goto
bad
；
ustack
［
argc
］
=
sp
；
}
ustack
［
argc
］
=
0
；
// push the array of argv［］ pointers。
sp
-=
（
argc
+
1
）
*
sizeof
（
uint64
）；
sp
-=
sp
%
16
；
if
（
sp
<
stackbase
）
goto
bad
；
if
（
copyout
（
pagetable
，
sp
，
（
char
*
）
ustack
，
（
argc
+
1
）
*
sizeof
（
uint64
））
<
0
）
goto
bad
；
// arguments to user main（argc， argv）
// argc is returned via the system call return
// value， which goes in a0。
// 現在的sp指向argv［］陣列，argc透過a0暫存器i 返回
p
->
trapframe
->
a1
=
sp
；
// Save program name for debugging。
for
（
last
=
s
=
path
；
*
s
；
s
++
）
if
（
*
s
==
’/‘
）
last
=
s
+
1
；
safestrcpy
（
p
->
name
，
last
，
sizeof
（
p
->
name
））；
// Commit to the user image。
oldpagetable
=
p
->
pagetable
；
p
->
pagetable
=
pagetable
；
p
->
sz
=
sz
；
// 注意，在使用者程序被建立的時候，這裡就將返回到main的pc值放到暫存器epc裡面
p
->
trapframe
->
epc
=
elf
。
entry
；
// initial program counter = main
p
->
trapframe
->
sp
=
sp
；
// initial stack pointer
proc_freepagetable
（
oldpagetable
，
oldsz
）；
// the C calling convention on RISC-V places return values in a0
return
argc
；
//
this
ends
up
in
a0
，
the
first
argument
to
main
（
argc
，
argv
）
最後，當用戶程式的程式段都成功載入，使用者棧也設定完畢後，核心確定這次exec將要成功時，exec就清除程序的舊記憶體映像，即釋放舊頁表所佔用的物理記憶體，並準備使用新的頁表。然後系統呼叫exec將會順利完成並返回，該程序將執行一個新的使用者程式。
3.9 Real World
xv6和許多作業系統一樣，使用分頁的方式構建虛擬記憶體系統，管理記憶體空間；使用頁表完成虛擬地址到物理地址的轉換。現代作業系統會使用更復雜的分頁機制來構建虛擬記憶體系統。
對於xv6的核心，我們使用了直接對映的方式，因為我們假定RAM會被載入到固定的物理地址，因此核心也被載入到相同的位置，這是一種簡化的解決方案，因為我們使用QEMU模擬所有硬體。事實上，對於真實的硬體來說這並不是一個好主意，在現實中硬體會將RAM、各種裝置載入到一個無法預知的物理地址，RAM的起始地址就不再是固定的。一種更為嚴格的核心設計方式是，利用頁表，將任意的硬體物理記憶體佈局轉換為可預測的核心虛擬地址佈局。
分頁可以有不同的粒度。如果本身就記憶體緊缺，仍然堅持使用大頁可能會產生很多的內部碎片，這時應該使用不那麼大的頁；但是如果你的記憶體充足，使用大頁，能顯著地減少操作頁錶帶來的開銷。因此，分頁的大小最好取決於你擁有多大的RAM。
雖然xv6核心有記憶體分配器kalloc，但是它並不像廣知的malloc那樣，核心無法根據需要，動態地給一些複雜資料結構分配記憶體（如果是malloc的話，你就可以使用sizeof（ ））。此外，xv6的記憶體分配器，只分配大小為一頁（4KB）的塊；更精細的記憶體分配器，應該能夠分配多種不同大小的塊，以滿足更多不同需求。
上一篇:上林賦•司馬相如
下一篇：考研期間異地戀怎麼辦？
