chapter 2 Page tables 閱讀報告

概要

頁表是一種操作系統用來控制內存空間的機制，它使得xv6能夠把不同進程的地址空間映射到相同的物理內存上，還能夠為不同的進程的內存提供保護。

分頁硬件

回顧：

在x86中，用戶和內核指令計算的都是虛擬地址，頁表硬件通過映射機制把虛擬地址和物理地址

實際地址計算

頁表的具體結構就像一棵樹，樹根是page directory，包含了1024個類似PTE的條目，實際上每一條指向一個page table，每個page table包含1024個32位的PTE條目。這32位中，前20位表示了實際的物理頁號，後12位是一些標誌位。
當xv6翻譯虛擬地址時，先根據前10位在page directory中找到對應的條目，然後跳轉到該條目所指向的page table（若相應的page table未放在page directory中，分頁硬件則會拋出錯誤），在根據後10位在該page table中找到相應的PTE，用該PTE中的高20位來替換虛擬地址中的高20位，即得到物理地址。
疑問：為何大部分虛擬地址沒有進行映射？沒有映射的頁表頁又是指什麼？

標誌位

#define PTE_P 0x001 //present
#define PTE_W 0x002 //writeable
#define PTE_U 0x004 //user
#define PTE_PWT 0x008 //write-through
#define PTE_PCD 0x010 //cache-disable
#define PTE_A 0x020 //Accessed
#define PTE_D 0x040 //dirty
#define PTE_PS 0x080 //page size
#define PTE_MBZ 0x180 //bits must be zero

進程地址空間

每個進程都有自己的頁表，不同進程的頁表將其用戶內存映射到不同的物理內存中，當進程改變時，xv6會通知分頁硬件切換頁表。這樣就實現了概要中所說的對不同的進程的內存提供保護。

如上圖所示，進程的用戶內存：0到KERNBASE，且把相應的PTE_U設置為1.每個進程的頁表中都包含內核運行所需的所有映射，且他們都在KERNBASE之上，KERNBASE：KERNBASE+PHYSTOP映射到0:PHYSTOP。這些PTE的PTE_U被置為0，因此只有內核能使用這些頁。
疑問：PHYSTOP是什麼？xv6無法使用超過2GB的物理內存是怎麼計算出來的？

代碼：建立一個地址空間

程式流程如圖所示

物理內存分配

內核在運行時要為頁表、進程的用戶內存、內核棧和管道緩衝區分配物理內存。
xv6一次會分配出去一整個大小為4096byte的頁面。
它維護空閒頁的方法是形成一個空閒的物理頁組成的鏈表，分配內存就將該頁移出鏈表，釋放內存就將該頁存入鏈表。
疑問：自舉問題？

代碼：物理內存分配器

數據結構：鏈表
鏈表元素：struct run

struct run{
    struct run*next;
};

分配器初始化的流程如圖所示
具體看一下kfree的代碼部分

kfree(char *v)
{
    struct run *r;
    
    if((uint)v % PGSIZE || v < end || V2P(v) >= PHYSTOP)
        panic("kfree");
    
    // Fill with junk to catch dangling refs.
    memset(v, 1, PGSIZE);//填满垃圾数据
    
    if(kmem.use_lock)
        acquire(&kmem.lock);
    r = (struct run*)v;把v变成指向struct run的一个指针
    r−>next = kmem.freelist;//这一步之后v已经和原空闲链表的表头连接起来了
    kmem.freelist = r;//生成新的空闲链表
    if(kmem.use_lock)
        release(&kmem.lock);
}

從這段代碼中我們可以看到kfree是如何把頁表釋放並加入空閒鏈表中的。
同理，kalloc可以把空閒鏈表的表頭分配出去，並從空閒鏈表中移除病返回新的空閒鏈表的表頭。
疑問：分配器代碼中的類型轉換是什麼意思？

地址空間中的用戶部分

上圖顯示了在xv6中執行中的用戶進程的內存結構。堆在棧的上面，它可以通過sbrk增長自己。棧佔用的是單獨一頁內存，包含exec創建的廚師數據。棧的下方有一個保護頁（guard page），可以確保棧的增長不會超過一頁。
疑問：如何使得該程序可以彷彿剛剛調用了函數main？

代碼：sbrk

sbrk是一個允許進程縮小或擴張其內存的系統調用。主要靠growprc命令實現。

growproc(int n)
{
    uint sz;
    struct proc *curproc = myproc();
    
    sz = curproc−>sz;
    if(n > 0){
        if((sz = allocuvm(curproc−>pgdir, sz, sz + n)) == 0)
            return -1;
    }else if(n<0){
    if((sz = deallocuvm(curproc−>pgdir, sz, sz + n)) == 0)
        return −1;
    }
    curproc−>sz = sz;
    switchuvm(curproc);
    return 0;
}

當參數n為正時，growprc會分配一個或多個物理頁並把他們映射到進程的地址空間的頂部，如果參數n為負，則會從進程的地址空間取消映射並釋放這些物理頁。

代碼：exec

exec的運行流程圖：

接下來分配兩個頁面，一個用作保護頁，第二個用作棧，把參數拷貝到棧頂，然後把指向它們的指針保存在ustack中。最後創建新的內存映像，發現錯誤則跳轉到bad處並返回-1，無誤則在建立新的映像成功後裝載新映像並釋放舊映像。整個流程完成後返回0代表執行成功。
疑問：偽造的返回PC是什麼意思？argc和argv指針的意義？

顯示情況

-現實中的操作系統的分頁硬件更加精巧
-現實中不適總是需要4MB大小的“超級頁”
-現實中更精準的系統可以分配不同大小的內存塊，而不用總是分配4096bytes

感想

學習完這一章之後對與頁表是如何運作的，以及操作系統的內存管理系統還是有了一定的概念，但是學習的過程中也同樣產生了許多疑惑，希望在後面的學習中能夠有機會把這些疑問解決。