MIT JOS LAB4學習筆記

Lab4

Part A: 多處理器支援和協作式多任務

練習 1 ：實作在 kern/pmap.c 中的 mmio_map_region 方法。你可以看看 kern/lapic.c 中的 lapic_init 開頭部分，了解一下它是如何被調用的。你還需要完成接下來的練習，你的 mmio_map_region 才能夠正常運作。

lapic_init()函數的一開始就調用了該函數，将從lapicaddr 開始的4kB實體位址映射到虛拟位址，并傳回其起始位址。注意到，它是以頁為機關對齊的，每次都映射一個頁的大小。

練習 2：閱讀 kern/init.c 中的 boot_aps() 和 mp_main() 方法，和 kern/mpentry.S 中的彙編代碼。確定你已經明白了引導 AP 啟動的控制流執行過程。接着，修改你在 kern/pmap.c 中實作過的 page_init() 以避免将 MPENTRY_PADDR 加入到 free list 中，以使得我們可以安全地将 AP 的引導代碼拷貝于這個實體位址并運作。你的代碼應當通過我們更新過的 check_page_free_list() 測試，不過可能仍會在我們更新過的 check_kern_pgdir() 測試中失敗，我們接下來将解決這個問題。

修改 kern/pmap.c中的page_init()将MPENTRY_PADDR(0x7000)這一頁不要加入到page_free_list。

問題 1：逐行比較 kern/mpentry.S 和 boot/boot.S。牢記 kern/mpentry.S 和其他核心代碼一樣也是被編譯和連結在 KERNBASE 之上運作的。那麼，MPBOOTPHYS 這個宏定義的目的是什麼呢？為什麼它在 kern/mpentry.S 中是必要的，但在 boot/boot.S 卻不用？換句話說，如果我們忽略掉 kern/mpentry.S 哪裡會出現問題呢？

提示：回憶一下我們在 Lab 1 讨論的連結位址和裝載位址的不同之處。

1.kern/mpentry.S 與 boot/boot.S 有以下差别：

沒有 Enable A20 的部分

GDT 相關的位址都用 MPBOOTPHYS 宏包裝了一下

棧設定在了 mpentry_kstack

跳轉到入口 mp_main

2.MPBOOTPHYS 宏的作用：

MPBOOTPHYS 的作用是将高位址變為位址。

因為 kern/mpentry.S 都連結到了高位的虛拟位址，但是實際上裝載在低位的實體位址，是以 MPBOOTPHYS 要把這個高位的位址映射到低位的位址。boot/boot.S 裝載在低位并且連結也在低位，是以就不需要這樣的宏。

練習 3：修改位于 kern/pmap.c 中的 mem_init_mp()，将每個CPU堆棧映射在 KSTACKTOP 開始的區域，就像 inc/memlayout.h 中描述的那樣。每個堆棧的大小都是 KSTKSIZE 位元組，加上 KSTKGAP 位元組沒有被映射的 守護頁 。現在，你的代碼應當能夠通過我們新的 check_kern_pgdir() 測試了。

對于 CPU i, 、實體位址為 'percpu_kstacks[i]'，然後映射過去就行。

練習 4 ：位于kern/trap.c 中的 trap_init_percpu() 為 BSP 初始化了 TSS 和 TSS描述符，它在 Lab 3 中可以工作，但是在其他 CPU 上運作時，它是不正确的。修改這段代碼使得它能夠在所有 CPU 上正确執行。（注意：你的代碼不應該再使用全局變量 ts。）

每一個 cpu 的 task state segment (TSS)被用來指定每一個 CPU 的核心棧存在的地方，The TSS for CPU i 儲存在 cpus[i].cpu_ts，相應的 TSS descriptor 定義在 gdt[(GD_TSS0 >> 3) + i]。先利用cpu_id建立TSS，初始化TSS descriptor,之後加載TSS selector,最後加載IDT（中斷描述符表）。

加鎖

你應當在以下 4 個位置使用全局核心鎖：

• i386_init() 中，在 BSP 喚醒其他 CPU 之前獲得核心鎖
• mp_main() 中，在初始化完 AP 後獲得核心鎖，接着調用 sched_yield() 來開始在這個 AP 上運作程序。
• trap() 中，從使用者模式陷入(trap into)核心模式之前獲得鎖。你可以通過檢查 tf_cs 的低位判斷這一 trap 發生在使用者模式還是核心模式（譯者注：Lab 3 中曾經使用過這一檢查）
• env_run() 中，恰好在回到使用者程序之前釋放核心鎖。不要太早或太晚做這件事，否則可能會出現競争或死鎖。

練習 5：在上述提到的位置使用核心鎖，加鎖時使用 lock_kernel()， 釋放鎖時使用 unlock_kernel()。

Lock_kernel()的函數定義如下：

Unlock_kernel()的函數定義如下：

在kern/spinlock.cpp中，

spin_lock()函數的定義如下：

其中，while循環展現了循環等待的思想，

xchg()函數在inc/x86.h中定義，是一個原子性操作，定義如下：

在kern/init.c下的i386_init()中添加代碼如下：

在kern/init.c下的mp_main()中添加代碼如下：

在kern/trap.c下的trap()中添加代碼如下：

在kern/env.c下的env_run()中添加代碼如下：

問題 2：看起來使用全局核心鎖能夠保證同一時段内隻有一個 CPU 能夠運作核心代碼。既然這樣，我們為什麼還需要為每個 CPU 配置設定不同的核心堆棧呢？請描述一個即使我們使用了全局核心鎖，共享核心堆棧仍會導緻錯誤的情形。

在某程序即将陷入核心态的時候（尚未獲得鎖），其實在 trap() 函數之前已經在 trapentry.S 中對核心棧進行了操作，壓入了寄存器資訊。如果共用一個核心棧，就可能會導緻資訊錯誤。

輪轉排程算法

你的下一個任務是修改 JOS 核心以使其能夠以 輪轉 的方式在多個程序中切換。JOS 的輪轉排程算法像這樣工作：

• kern/sched.c 中的 sched_yied() 函數負責挑選一個程序運作。它從剛剛在運作的程序開始，按順序循環搜尋 envs[] 數組（如果從來沒有運作過程序，那麼就從數組起點開始搜尋），選擇它遇到的第一個處于 ENV_RUNNABLE （參考inc/env.h）狀态的程序，并調用 env_run() 來運作它。
• sched_yield() 絕不應當在兩個CPU上同時運作同一程序。它可以分辨出一個程序正在其他CPU（或者就在目前CPU）上運作，因為這樣的程序處于 ENV_RUNNING 狀态。
• 我們已經為你實作了新的系統調用 sys_yield()，使用者程序可以調用它來觸發核心的 sched_yield() 方法，自願放棄 CPU，給其他程序運作。

練習 6：按照以上描述，實作 sched_yield() 輪轉算法。不要忘記修改你的 syscall() 将相應的系統調用分發至 sys_yield() （譯者注：以後還要添加新的系統調用，同樣不要忘記修改 sys_yield()）。

確定你在 mp_main 中調用了 sched_yield()。

修改你的 kern/init.c 建立三個或更多程序，運作 user/yield.c。

在kern/sched.c中添加代碼如下：

在kern/syscall.c中添加新的系統調用如下：

在kern/init.c中運作的使用者程序修改如下：

運作 user/yield.c,結果如下：

問題 3：在你實作的 env_run() 中你應當調用了 lcr3()。在調用 lcr3() 之前和之後，你的代碼應當都在引用 變量 e，就是 env_run() 所需要的參數。 在裝載 %cr3 寄存器之後， MMU 使用的位址上下文立刻發生改變，但是處在之前位址上下文的虛拟位址（比如說 e ）卻還能夠正常工作，為什麼？

在env.c的env_settup_vm()中，代碼如下：

使用核心的頁目錄指派，是以兩個頁目錄的e的位址映射到同一實體位址。

問題 4：無論何時，核心在從一個程序切換到另一個程序時，它應當確定舊的寄存器被儲存，以使得以後能夠恢複。為什麼？在哪裡實作的呢？

在程序陷入核心時，會儲存目前的運作資訊，這些資訊都儲存在核心棧上。而當從核心态回到使用者态時，會恢複之前儲存的運作資訊。儲存發生在 kern/trapentry.S，恢複發生在 kern/env.c  env_pop_tf()。

建立其他程序的系統調用

盡管你的核心目前能夠運作多個使用者程序并在其中切換，但仍受限于隻能運作由核心建立的程序。現在，你将實作必要的系統調用，使得使用者程序也可以建立和啟動其他新的使用者程序。

UNIX 提供了 fork() 系統調用作為建立程序的原型，UNIX 的 fork() 拷貝整個調用程序（父程序）的位址空間來建立新的程序（子程序），在使用者空間唯一可觀察到的差別是它們的 程序ID(process ID) 和 父程序ID(parent process ID)（分别是調用 getpid 和 getppid 傳回的）。在父程序中, fork() 傳回子程序 ID，但在子程序中，fork() 傳回0。預設情況下，每個程序的位址空間是私有的，記憶體修改對另一方不可見。

你将提供一系列不同的、更原始的系統調用來建立新的使用者程序。通過這些系統調用，你将能夠完全在使用者空間實作類似 Unix 的 fork()作為其他建立程序方式的補充。你将會為 JOS 實作的新的系統調用包括：

sys_exofork:

該系統調用建立一個幾乎完全空白的新程序：它的使用者位址空間沒有記憶體映射，也不可以運作。這個新的程序擁有和建立它的父程序（調用這一方法的程序）一樣的寄存器狀态。在父程序中，sys_exofork會傳回剛剛建立的新程序的envid_t（或者一個負錯誤代碼，如果程序配置設定失敗）。在子程序中，它應當傳回0。（因為子程序開始時被标記為不可運作，sys_exofork 并不會真的傳回到子程序，除非父程序顯式地将其标記為可以運作以允許子程序運作。

sys_env_set_status:

将一個程序的狀态設定為 ENV_RUNNABLE 或 ENV_NOT_RUNNABLE。這個系統調用通常用來在新建立的程序的位址空間和寄存器狀态已經初始化完畢後将它标記為就緒狀态。

sys_page_alloc:

配置設定一個實體記憶體頁面，并将它映射在給定程序虛拟位址空間的給定虛拟位址上。

sys_page_map:

從一個程序的位址空間拷貝一個頁的映射 (不是頁面的内容) 到另一個程序的位址空間，新程序和舊程序的映射應當指向同一個實體記憶體區域，使兩個程序得以共享記憶體。

sys_page_unmap:

取消給定程序在給定虛拟位址的頁映射。

對于所有以上提到的接受 Environment ID 作為參數的系統調用，JOS 核心支援用 0 指代目前程序的慣例。這一慣例在 kern/env.c 的 envid2env() 函數中被實作。

我們在測試程式 user/dumbfork.c 中提供了一種非常原始的 Unix 樣式的 fork()。它使用上述系統調用來建立并運作一個子程序，子程序的位址空間就是父程序的拷貝。接着，這兩個程序将會通過上一個練習中實作的系統調用 sys_yield 來回切換。 父程序在切換10次後退出，子程序切換20次。

練習 7：在 kern/syscall.c 中實作上面描述的系統調用。你将需要用到在 kern/pmap.c 和 kern/env.c 中定義的多個函數，尤其是 envid2env()。此時，無論何時你調用 envid2env()，都應該傳遞 1 給 checkperm 參數。确定你檢查了每個系統調用參數均合法，否則傳回 -E_INVAL。 用 user/dumbfork 來測試你的 JOS 核心，在繼續前确定它正常的工作。

在 user/dumbfork.c 中，核心是 duppage() 函數。它利用 sys_page_alloc() 為子程序配置設定空閑實體頁，再使用sys_page_map() 将該新實體頁映射到核心 (核心的 env_id = 0) 的交換區 UTEMP，友善在核心态進行 memmove 拷貝操作。在拷貝結束後，利用 sys_page_unmap() 将交換區的映射删除。

sys_exofork()：該函數主要是配置設定了一個新的程序，但是沒有做記憶體複制等處理。值得注意的就是如何使子程序傳回0。

sys_exofork()是一個非常特殊的系統調用，它的定義與實作在 inc/lib.h 中，而不是 lib/syscall.c 中。并且，它必須是 inline 的。

它的傳回值是 %eax 寄存器的值。

在kern/syscall.c中，sys_exofork():該系統調用建立一個幾乎完全空白的新程序

sys_env_set_status: 用來在新建立的程序的位址空間和寄存器狀态已經初始化完畢後将它标記為就緒狀态。

sys_page_alloc:配置設定一個實體記憶體頁面，并将它映射在給定程序虛拟位址空間的給定虛拟位址上。

sys_page_map：從一個程序的位址空間拷貝一個頁的映射 (不是頁的内容) 到另一個程序的位址空間，新程序和舊程序的映射應當指向同一個實體記憶體區域，使兩個程序得以共享記憶體。

sys_page_unmap:取消給定程序在給定虛拟位址的頁映射。

最後，在syscall()中添加代碼如下：

運作結果如下：

Part B: 寫時複制的 Fork

設定缺頁處理函數

為了處理自己的缺頁，使用者程序需要向 JOS 核心注冊一個 page fault handler entry point。 使用者程序通過我們新引入的 sys_env_set_pgfault_upcall 系統調用注冊它的缺頁處理入口。我們也在 Env 結構體中添加了一個新的成員，env_pgfault_upcall，來記錄這一資訊

為了實作寫時複制，首先要實作使用者程式頁面錯誤處理功能。基本流程是：

• 1）使用者程序通過 set_pgfault_handler(handler) 設定頁面錯誤處理函數。
• 2）函數set_pgfault_handler中為使用者程式配置設定異常棧，通過系統調用sys_env_set_pgfault_upcall 設定通用的頁面錯誤處理調用入口。
• 3）當使用者程序發生頁面錯誤時，陷入核心。核心先判斷該程序是否設定了 env_pgfault_upcall，如果沒有設定，則報錯。如果設定了，則切換使用者程序棧到異常棧，設定異常棧内容，然後設定EIP為 env_pgfault_upcall 位址，切回使用者态執行 env_pgfault_upcall 函數(即_pgfault_upcall)。
• 4）env_pgfault_upcall作為頁面錯誤處理函數的入口函數，它在使用者态運作。先調用步驟1中注冊的頁面錯誤處理函數，然後再恢複程序在頁面錯誤之前的棧内容，并切回正常棧，跳轉到頁面錯誤之前的地方繼續運作。

練習 8：實作 sys_env_set_pgfault_upcall 系統調用。因為這是一個危險的系統調用，不要忘記在獲得目标程序資訊時啟用權限檢查。

通過修改相應的struct Env的'env_pgfault_upcall'字段，為'envid'設定頁面錯誤upcall。 當'envid'導緻頁面錯誤時，核心會将錯誤記錄推送到異常堆棧，然後轉移到'func'。成功時傳回0，錯誤時傳回<0。 錯誤是：-E_BAD_ENV如果環境envid目前不存在，或者調用者沒有更改envid的權限。

練習 9：實作在 kern/trap.c 中的 page_fault_handler 方法，使其能夠将缺頁分發給使用者模式缺頁處理函數。确認你在寫入異常堆棧時已經采取足夠的預防措施了。（如果使用者程序的異常堆棧已經沒有空間了會發生什麼？）

首先需要了解使用者級别的頁錯誤處理的步驟是：

程序A（正常棧） - >核心 - >程序A（異常棧） - >程序A（正常棧）

page_fault_handler函數的實作方式就是先檢查處理函數的位址空間是否存在，如果不存在就應将引發錯誤的env摧毀掉，否則再判斷env運作在使用者棧還是異常棧，如果是使用者棧就将目前狀态壓入異常棧，是異常棧就隔一段空位再壓棧。

使用者模式缺頁入口點

接下來，你需要實作彙編例程(routine)，來調用 C 語言的缺頁處理函數，并從異常狀态傳回到一開始造成缺頁中斷的指令繼續執行。這個彙編例程 将會成為通過系統調用 sys_env_set_pgfault_upcall() 向核心注冊的處理函數。

練習 10：實作在 lib/pfentry.S 中的 _pgfault_upcall 例程。傳回到一開始運作造成缺頁的使用者代碼這一部分很有趣。你在這裡将會直接傳回，而不是通過核心。最難的部分是同時調整堆棧并重新裝載 EIP。

運作處理程式，切換回正常棧

練習 11：完成在 lib/pgfault.c 中的 set_pgfault_handler() 。

這是用來指定缺頁異常處理方式的函數。需要區厘清楚handler，_pgfault_handler，_pgfault_upcall三個變量。

1. handler 是傳入的使用者自定義頁錯誤處理函數指針。
2. _pgfault_upcall是一個全局變量，在lib/pfentry.S中完成的初始化。它是頁錯誤處理的總入口，頁錯誤除了運作頁面錯誤處理程式，還需要切換回正常棧。
3. _pgfault_handler 被指派為處理程式，在會_pgfault_upcall中被調用，是頁錯誤處理的一部分

先檢查handler 函數是否已被設定過，如果沒有就先為handler函數配置設定一塊空間，然後将handler函數設定成自己想要的處理函數。

實作寫時複制的 fork

練習 12：實作在 lib/fork.c 中的 fork，duppage和pgfault。 用 forktree 程式來測試你的代碼。它應當産生下面的輸出，其中夾雜着 new env, free env 和 exiting gracefully 這樣的消息。下面的這些輸出可能不是按照順序的，程序ID也可能有所不同：

1000: I am ''

1001: I am '0'

2000: I am '00'

2001: I am '000'

1002: I am '1'

3000: I am '11'

3001: I am '10'

4000: I am '100'

1003: I am '01'

5000: I am '010'

4001: I am '011'

2002: I am '110'

1004: I am '001'

1005: I am '111'

1006: I am '101'

fork() ：從主函數 fork() 入手，其大體結構可以仿造 user/dumbfork.c 寫，但是有關鍵幾處不同：設定 page fault handler，即 page fault upcall 調用的函數；duppage 的範圍不同，fork() 不需要複制核心區域的映射；為子程序設定 page fault upcall，因為 sys_exofork() 并不會複制父程序的 e->env_pgfault_upcall 給子程序。

duppage() ：複制父、子程序的頁面映射。因為sys_page_map() 頁面的權限有要求，是以要修正一下權限。

pgfault() ：這是 _pgfault_upcall 中調用的頁錯誤處理函數。在調用之前，父子程序的頁錯誤位址都引用同一頁實體記憶體，該函數作用是配置設定一個實體頁面使得兩者獨立。

首先配置設定一個頁面，映射到交換區 PFTEMP 這個虛拟位址，然後通過 memmove() 函數将 addr 所在頁面拷貝至 PFTEMP，此時有兩個實體頁儲存了同樣的内容。再将 addr 也映射到 PFTEMP 對應的實體頁，最後解除了 PFTEMP 的映射，此時就隻有 addr 指向新配置設定的實體頁了，如此就完成了錯誤處理。

通過 make run-forktree 驗證結果。

Part C: 搶占式多任務和程序間通信(IPC)

練習 13：修改 kern/trapenrty.S 和 kern/trap.c 來初始化一個合适的 IDT 入口，并為 IRQ 0-15 提供處理函數。接着修改 在 kern/env.c 中的 env_alloc()以確定使用者程序總是在中斷被打開的情況下運作。

一些宏定義：

在kern/trapentry.S中加入：

首先聲明處理函數，之後使用SETEGATE設定表項。

當調用使用者中斷處理函數時，處理器從來不會将 error code 壓棧，也不會檢查IDT 入口的描述符特權等級，是以在trapentry.S中使用TRAPHANDLER_NOEC（）,當某個中斷發生時，根據偏移量将對應的中斷号壓棧，然後開始執行相應的中斷處理函數（call trap）：

確定使用者程序總是在中斷被打開的情況下運作，保證 FL_IF 被置位，如果這個程序運作時出現中斷，中斷就可以到達處理器并被相應的中斷處理代碼所處理。是以在kern/env.c的env_alloc()中加入：

練習 14：修改核心的 trap_dispatch() 函數，使得其每當收到時鐘中斷的時候，它會調用 sched_yield() 尋找另一個程序并運作。

添加時鐘中斷的分支：

程序間通信 (IPC)

練習 15：實作 kern/syscall.c 中的 sys_ipc_recv 和 sys_ipc_try_send。在實作它們前，你應當讀讀兩邊的注釋，因為它們協同工作。當你在這些例程中調用 envid2env 時，你應當将 `checkperm 設定為 0，這意味着程序可以與任何其他程序通信，核心除了確定目标程序ID有效之外，不會做其他任何檢查。

接下來在 lib/ipc.c 中實作 ipc_recv 和 ipc_send。

sys_ipc_recv(void *dstva) ：

功能：将目前程序挂起，放棄CPU，準備接受其他程序發來的消息

實作方式：設定env_ipc_recving、env_ipc_dstva、env_status，執行系統調用sys_yield()

sys_ipc_try_send(envid_t envid, uint32_t value, void *srcva, unsigned perm)：

功能：試着發送消息，目标程序的id不存在、目标程序未開始接受、傳遞的頁映射有問題 等原因都會導緻發送失敗。若發送成功，則更新目标程序，使其變為就緒态，不再接受消息。

實作方式：先判斷發送的條件是否全滿足，若都滿足，更新目标程序的env_ipc_recving、enc_ipc_from、env_ipc_value等

然後在kern/syscall.c中添加新的系統調用如下：

ipc_recv(envid_t *from_env_store, void *pg, int *perm_store)：

功能：接受發送者發來的value并傳回它，擷取發送程序的id，頁權限

實作方式：執行系統調用，挂起目前程序，如果接收者想要共享頁（pg非空），則将接收方共享頁的虛拟位址設為pg，準備接收，修改from_env_store、perm_store

（如果發送者發來了共享頁，perm_store和發送者的相同;發送者未發送頁，則perm_store=0，權限為核心）

ipc_send(envid_t to_env, uint32_t val, void *pg, int perm)：

功能：向目标程序發送value和記憶體頁（如果pg非空）

實作方式：循環調用sys_ipc_try_send(),直到發送成功，同時調用sys_yield()，避免一直占用CPU，像spin一樣被kill。

測試：

make run-pingpong

make grade: