# 六、
來源：[JOS學習筆記（六）](http://blog.csdn.net/roger__wong/article/details/8661558)
接下來做part2，先上一張開啟分頁后的地址變換圖：（完整的圖在 http://pdos.csail.mit.edu/6.828/2011/lec/x86_translation_and_registers.pdf ）
然后再放一張具體的地址變換的圖：
好當我們把這兩張圖也牢記于心的時候就可以開始實驗的part2了。
## 1、實驗要求
完成以下幾個函數：
```
pgdir_walk()
boot_map_region()
page_lookup()
page_remove()
page_insert()
```
然后通過mem_init()里面的check_page函數就算過關了。
雖然要求比較簡單，但實現起來可真不容易。
## 2、原理
### （1）地址變換
首先從硬件機制說起，當cpu拿到一個地址并根據這個地址訪問主存時，在x86體系架構下要經過至少兩級的地址變換，第一級成為段式地址變換而第二級成為頁式地址變換。（為什么？主要是從安全、兼容老的os、考慮現代os等原因）
最原始的地址叫做虛擬地址，根據規定，將前16位作為段選擇子，后32位作為偏移。根據段選擇子查找gdt/ldt，查到的內容替加上偏移，此時的地址就變成了線性地址。
線性地址前10位被稱作頁目錄入口（page directory entry也就是pde），其含義為該地址在頁目錄中的索引，中間10位為頁表入口（page table entry，也就是pte），代表在頁表中的索引，最后12位是偏移。
當一個線性地址進入頁式地址變換機制時，首先cpu從cr3寄存器里得到頁目錄（page directory）在主存中的地址，然后根據這個地址加上pde得到該地址在頁目錄中對應的項。無論是頁目錄的項還是頁表的項均是32位，前20位為地址，后12位為標志位。當獲取了相應的頁目錄項之后，根據前20位地址得到頁表所在地址，加上偏移pte得到頁表項，取出前20位加上線性地址本身的后12位組成物理地址，整個變換過程結束。這也就是以上兩個圖所描述的功能。
值得注意的是，這個過程完全是由硬件實現，在這個部分的實驗中要做的是初始化并維護頁目錄與頁表，當頁目錄與頁表維護好了，然后使cr3裝載新的頁目錄，一切就交由硬件去處理地址變換了。
這里還有兩個點需要說下：
1、為什么是20位就能表示頁表所在地址？因為頁表的分配以頁為單位，換句話分配的過程是分配一個頁面，而這個頁面所有內容都用來當做頁表，而頁正好是4k，所以頁表地址必定是4k對齊。
2、一個頁表項對應一頁（也就是4K內容），因為其后面有12位的偏移。一個頁表有1024個頁表項，因為一個頁表大小為4K，一個頁表項為32位（4B）。一個頁目錄項對應一個頁表，對應4K\*1024=4M空間的映射。一個頁目錄有1024個頁目錄項，對應4M\*1024=4G地址的映射，正好是32位地址空間。
3、一個理發師只為不自己理發的人理發，當然我們在這里不套路羅素悖論。段頁地址變換只為虛擬地址進行地址變換，而不為它本身的地址進行變換。換句話說變換過程中所出現的任何地址都是物理地址，在編寫代碼的時候尤其要注意這一點。
### （2）JOS的相關部分
之前的日志里已經說過，JOS的機制中，雖然使用段式地址變換，但和沒使用完全一樣，因為只定義了一個段，其長度為4G，換句話說，經過段式地址變換后的內容和之前完全一樣，虛擬地址和線性地址完全一樣。
在part2中也就是mem_init()執行環境里，JOS已經開啟了頁式地址變換，但變換的比較粗糙，只是簡單的把0--4M物理地址分別映射到了0--4M物理地址和0xf0000000開始的4M 地址處，之前也已經詳細說過這個問題。但同時也感謝一下這種“粗糙”的變換方式，讓我們在編程填充頁表和頁目錄的時候方便了許多。（為什么？因為要往里填充物理地址，存在一個把當前符號地址轉化成物理地址的過程，因為變換的粗糙，所以這個過程相對簡單）。
值得注意的是，在代碼里我們的所有地址均為虛擬地址，不同通過任何方法直接得到某個符號實際存在于物理內存中的地址，只有通過算才能得到我們需要的物理地址。
## 3、實現
### （1）基本數據類型與函數說明
+ pde_t 代表一個頁目錄項
+ pte_t 代表一個頁表項
+ pgdir_walk() 用于查找某個虛擬地址是否有頁表項，如果沒有也可以通過此函數創建，值得注意的是，有頁表項并不代表已經被映射。
+ boot_map_region() 映射一個虛擬地址區間到一個物理地址區間，貌似在本部分沒用到。
+ page_insert() 將一個虛擬地址映射到一個Page數據結構，也就是映射到某個物理地址。
+ page_lookup() 查找一個虛擬地址對應的Page數據結構，若沒有映射返回空。
+ page_remove() 解除某個虛擬地址的映射。
### （2）具體實現
```
pte_t *
pgdir_walk(pde_t *pgdir, const void *va, int create)
{
cprintf("pgdir_walk\r\n");
// Fill this function in
pte_t* result=NULL;
if(pgdir[PDX(va)]==(pte_t)NULL)
{
if(create==0)
{
return NULL;
}
else
{
struct Page* page=page_alloc(1);
if(page==NULL)
{
return NULL;
}
page->pp_ref++;
pgdir[PDX(va)]=page2pa(page)|PTE_P|PTE_W|PTE_U;
result=page2kva(page);
}
}
else
{
//cprintf("%u ",PGNUM(PTE_ADDR(pgdir[PDX(va)])));
result=page2kva(pa2page(PTE_ADDR(pgdir[PDX(va)])));
}
return &result[PTX(va)];
}
```
思路：
首先明確一點，返回地址是虛擬地址，要不然沒有任何意義（在程序中拿到物理地址也沒法用）。
查找頁目錄表，根據宏PDX取得頁目錄項（相關宏定義在mmu.h中），如果不為空，取出該項內容的前20位（PTE_ADDR宏），這是物理地址，通過此物理地址查找對應的Page結構（pa2page宏），然后獲得此Page的虛擬地址（page2kva宏）。
此時的地址為頁表的虛擬地址，根據偏移得到頁目錄項，在返回此頁目錄項地址。
如果前20位不為空，檢查create，如果為0，返回null。否則新分配一個Page作為頁表，然后自增Page 的引用，讓該頁目錄項的前20位為頁表物理地址（page2pa得到物理地址），并設置一些權限符號（不加通不過最后的檢測函數），在通過此頁表的虛擬地址得到相應頁表項的虛擬地址并返回。
boot_map_region暫時略過，等到用的時候再說。
```
struct Page *
page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
{
cprintf("page_lookup\r\n");
// Fill this function in
pte_t* pte=pgdir_walk(pgdir,va,0);
if(pte==NULL)
{
return NULL;
}
if(pte_store!=0)
{
*pte_store=pte;
}
if(pte[0] !=(pte_t)NULL)
{
//cprintf("%x \r\n",pte[PTX(va)]);
return pa2page(PTE_ADDR(pte[0]));
}
else
{
return NULL;
}
}
```
首先使用pgdir_walk查找pte，如果為空則說明沒有映射，返回NULL。
否則根據pte_store是否為0，先把此pte的地址存到pte_store里。
接著看這個頁表項是否為0（更正確的寫法應該是pte[0] & PTE_U，也就是查找PTE_U這一位是否為0，但貌似我這么寫也沒出錯），如果為0，說明地址沒有被映射（有頁表項不代表被映射），返回NULL。
否則返回這個頁表項的前20位所組成的物理地址所對應的Page結構。
```
void
page_remove(pde_t *pgdir, void *va)
{
cprintf("page_remove\r\n");
pte_t* pte=0;
struct Page* page=page_lookup(pgdir,va,&pte);
if(page!=NULL)
{
page_decref(page);
}
pte[0]=0;
tlb_invalidate(pgdir,va);
}
```
這個函數邏輯很簡單，首先查找此va對應的物理頁面，如果此頁面不為空，說明va已經映射到了物理頁面，減少這個物理頁面的引用次數（次數為0就釋放這個頁面了，相關邏輯封裝在了page_decref中），然后置相應的頁表項為0，并通知tlb失效。tlb是個高速緩存，用來緩存查找記錄增加查找速度。
```
int
page_insert(pde_t *pgdir, struct Page *pp, void *va, int perm)
{
cprintf("page_insert\r\n");
// Fill this function in
pte_t* pte;
struct Page* pg=page_lookup(pgdir,va,NULL);
if(pg==pp)
{
pte=pgdir_walk(pgdir,va,1);
pte[0]=page2pa(pp)|perm|PTE_P;
return 0;
}
else if(pg!=NULL )
{
page_remove(pgdir,va);
}
pte=pgdir_walk(pgdir,va,1);
if(pte==NULL)
{
return -E_NO_MEM;
}
pte[0]=page2pa(pp)|perm|PTE_P;
pp->pp_ref++;
return 0;
}
```
首先查找該va是否已經映射到了某個物理頁面，如果映射到了，則解除映射。
使用pgdir_walk查詢該地址的pte（若不存在則建立，第三個參數傳入1），如果pte為空，說明沒有額外的空間分配頁表，因此返回-E_NO_MEM。
否則將該pte的內容填充成相應物理頁面的物理地址，增加這個物理頁面的引用次數。
存在一個問題，若此時的va已經映射到了物理頁面，而這個頁面恰好又是函數傳入的pp，則這段代碼不能正常的工作。
假設這個物理頁面恰好是pp，則會調用page_remove嘗試釋放這個pp，又假設這個pp的引用次數正好又是1，則這個pp就會被釋放掉，進入空閑頁面的鏈表中。
但問題是這個pp不是空閑頁面，雖然之后又為其建立了映射，但將Page結構從空閑鏈表中取出來的邏輯僅僅包含在page_alloc函數中，因此我們又不能簡單的將其取出來，這要就會導致一個非空閑的頁面（其引用是1）卻出現在了空閑頁面的鏈表中。
雖然實驗中再三要求不使用特例的方式進行實現，但我實在找不到更美的方式（把remove邏輯或者page_alloc部分邏輯拿出來在這個函數里重新實現一次諸如此類的方法），所以我還是用了特例進行實現，若發現引用了同一個頁面，就直接改pte即可。
基本到此這部分實驗就結束了，運行后能通過：
