MIT 6.828 Lab04 : Preemptive Multitasking

• 2020 年 8 月 18 日
• 筆記
• mit-6.828 實驗筆記

在本實驗中，我們將在多個同時活動的用戶模式環境中實施搶佔式多任務處理。

• PartA:
  • 為 JOS 增添多處理器支援特性。
  • 實現 round-robin scheduling循環調度。
  • 添加一個基本的環境（進程）管理系統調用（創建和銷毀環境，分配和映射記憶體）。
• PartB:
  • 實現一個類Unix的fork(),其允許一個用戶模式的環境能創建一份它自身的拷貝。
• PartC:
  • 支援進程間通訊（inter-process communication, IPC）
  • 支援硬體時鐘中斷和搶佔

Part A：Multiprocessor Support and Cooperative Multitasking

🚩 不要搞混淆：multiprocessor support 是針對JOS 這個作業系統，讓它可以支援多處理器，而不是說某個處理器管理其他處理器

Multiprocessor Support

我們將讓 JOS 支援對稱多處理器（symmetric multiprocessing，SMP），這是一種多處理器模型，其中所有CPU都具有對系統資源（如記憶體和I / O匯流排）的等效訪問。雖然所有CPU在SMP中功能相同，但在引導過程中它們可分為兩種類型：

• 引導處理器（BSP）：負責初始化系統和引導作業系統;
• 應用程式處理器（AP）：只有在作業系統啟動並運行後，BSP才會激活應用程式處理器。

具體哪個處理器是BSP是由硬體和BIOS系統決定的。到目前為止，我們完成的JOS code都在BSP上運行。哪一個CPU是BSP由硬體和BISO決定，到目前位置所有JOS程式碼都運行在BSP上。
在SMP系統中，每個CPU都有一個對應的local APIC（LAPIC），負責傳遞中斷。CPU通過記憶體映射IO(MMIO)訪問它對應的APIC，這樣就能通過訪問記憶體達到訪問設備暫存器的目的。LAPIC從物理地址0xFE000000開始，JOS將通過MMIOBASE虛擬地址訪問該物理地址。

在SMP系統中，每個CPU都有一個附帶的本地APIC（LAPIC）單元。

APIC:Advanced Programmable Interrupt Controller高級可編程中斷控制器 。APIC 是裝置的擴充組合用來驅動 Interrupt 控制器 [1] 。在目前的建置中，系統的每一個部份都是經由 APIC Bus 連接的。”本機 APIC” 為系統的一部份，負責傳遞 Interrupt 至指定的處理器；舉例來說，當一台機器上有三個處理器則它必須相對的要有三個本機 APIC。自 1994 年的 Pentium P54c 開始Intel 已經將本機 APIC 建置在它們的處理器中。實際建置了 Intel 處理器的電腦就已經包含了 APIC 系統的部份。

LAPIC單元負責在整個系統中傳遞中斷。 LAPIC還為其連接的CPU提供唯一標識符。 在本實驗中，我們使用LAPIC單元的以下基本功能（在kern/lapic.c中）：

• 根據LAPIC識別碼（APIC ID）區別我們的程式碼運行在哪個CPU上。（cpunum()）
• 從BSP向APs發送STARTUP處理器間中斷（IPI）去喚醒其他的CPU。（lapic_startap()）
• 在Part C，我們編寫LAPIC的內置定時器來觸發時鐘中斷，以支援搶佔式多任務（pic_init()）。

LAPIC的 hole 開始於物理地址0xFE000000(4GB之下的32MB)，但是這地址太高我們無法訪問通過過去的直接映射(虛擬地址0xF0000000映射0x0，即只有256MB)。但是JOS虛擬地址映射預留了4MB空間在MMIOBASE處。

![]()

虛擬記憶體圖

/*
 * Virtual memory map:                                Permissions
 *                                                    kernel/user
 *
 *    4 Gig -------->  +------------------------------+
 *                     |                              | RW/--
 *                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *                     :              .               :
 *                     :              .               :
 *                     :              .               :
 *                     |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| RW/--
 *                     |                              | RW/--
 *                     |   Remapped Physical Memory   | RW/--
 *                     |                              | RW/--
 *    KERNBASE, ---->  +------------------------------+ 0xf0000000      --+
 *    KSTACKTOP        |     CPU0's Kernel Stack      | RW/--  KSTKSIZE   |
 *                     | - - - - - - - - - - - - - - -|                   |
 *                     |      Invalid Memory (*)      | --/--  KSTKGAP    |
 *                     +------------------------------+                   |
 *                     |     CPU1's Kernel Stack      | RW/--  KSTKSIZE   |
 *                     | - - - - - - - - - - - - - - -|                 PTSIZE
 *                     |      Invalid Memory (*)      | --/--  KSTKGAP    |
 *                     +------------------------------+                   |
 *                     :              .               :                   |
 *                     :              .               :                   |
 *    MMIOLIM ------>  +------------------------------+ 0xefc00000      --+
 *                     |       Memory-mapped I/O      | RW/--  PTSIZE
 * ULIM, MMIOBASE -->  +------------------------------+ 0xef800000
 *                     |  Cur. Page Table (User R-)   | R-/R-  PTSIZE
 *    UVPT      ---->  +------------------------------+ 0xef400000
 *                     |          RO PAGES            | R-/R-  PTSIZE
 *    UPAGES    ---->  +------------------------------+ 0xef000000
 *                     |           RO ENVS            | R-/R-  PTSIZE
 * UTOP,UENVS ------>  +------------------------------+ 0xeec00000
 * UXSTACKTOP -/       |     User Exception Stack     | RW/RW  PGSIZE
 *                     +------------------------------+ 0xeebff000
 *                     |       Empty Memory (*)       | --/--  PGSIZE
 *    USTACKTOP  --->  +------------------------------+ 0xeebfe000
 *                     |      Normal User Stack       | RW/RW  PGSIZE
 *                     +------------------------------+ 0xeebfd000
 *                     |                              |
 *                     |                              |
 *                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *                     .                              .
 *                     .                              .
 *                     .                              .
 *                     |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|
 *                     |     Program Data & Heap      |
 *    UTEXT -------->  +------------------------------+ 0x00800000
 *    PFTEMP ------->  |       Empty Memory (*)       |        PTSIZE
 *                     |                              |
 *    UTEMP -------->  +------------------------------+ 0x00400000      --+
 *                     |       Empty Memory (*)       |                   |
 *                     | - - - - - - - - - - - - - - -|                   |
 *                     |  User STAB Data (optional)   |                 PTSIZE
 *    USTABDATA ---->  +------------------------------+ 0x00200000        |
 *                     |       Empty Memory (*)       |                   |
 *    0 ------------>  +------------------------------+                 --+

Exercise 01

	void *ret = (void *)base;
	size = ROUNDUP(size,PGSIZE); //非常關鍵的一步，傳入的size不一定剛好是一頁
	pa = ROUNDDOWN(pa,PGSIZE);
	
	if (base + size > MMIOLIM || base + size <base)
	{
	    panic ("mmio_map_region() overflow!\n");
	}
	
	boot_map_region(kern_pgdir,base,size,pa,PTE_W|PTE_PCD|PTE_PWT);
	base += size;//base 是static的，需要維護！
	return ret;//return 起始位置
}

Application Processor Bootstrap

在啟動APs之前，BSP應該先收集關於多處理器系統的配置資訊，比如CPU總數，CPUs的APIC ID，LAPIC單元的MMIO地址等。 kern/mpconfig.c中的mp_init（）函數通過讀取駐留在BIOS記憶體區域中的MP配置表來檢索此資訊。 也就是說在出廠時，廠家就將此電腦的處理器資訊寫入了BIOS中，其有一定的規範，也就是kern/mpconfig.c中struct mp定義的。

boot_aps()（在kern / init.c中）函數驅動了AP引導過程。 AP以實模式啟動，非常類似於 bootloader 在boot/boot.S中啟動的方式，因此boot_aps()將AP進入程式碼（kern / mpentry.S）複製到可在實模式下定址的記憶體位置。與 bootloader 不同，我們可以控制 AP 開始執行程式碼的位置; 我們將 entry 程式碼複製到0x7000（MPENTRY_PADDR），（但其實任何未使用的，頁面對齊的物理地址低於640KB都可以）。

之後，boot_aps函數通過發送STARTUP的IPI(處理器間中斷)訊號到AP的 LAPIC 單元來一個個地激活AP。在kern/mpentry.S中的入口程式碼跟boot/boot.S中的程式碼類似。在一些簡短的配置後，它使AP進入開啟分頁機制的保護模式，調用C語言的setup函數mp_main。boot_aps 等待AP在其結構CpuInfo的cpu_status欄位中發出CPU_STARTED標誌訊號，然後再喚醒下一個。

整理：

1. i386_init() –>mp_init() 讀取初始配置中的CPU資訊 –>boot_aps() –>mp_main()
2. AP 以實模式啟動，kern/mpentry.S中的程式碼處理後，進入有分頁機制的保護模式

Exercise 02

添加結果：

Question

1. Compare kern/mpentry.S side by side with boot/boot.S. Bearing in mind that kern/mpentry.S is compiled and linked to run above KERNBASE just like everything else in the kernel, what is the purpose of macro MPBOOTPHYS? Why is it necessary in kern/mpentry.S but not in boot/boot.S? In other words, what could go wrong if it were omitted in kern/mpentry.S?
   Hint: recall the differences between the link address and the load address that we have discussed in Lab 1.

宏MPBOOTPHYS是為求得變數的物理地址，例如MPBOOTPHYS(gdtdesc)得到GDT的物理地址。

🚩 boot.S中，由於尚沒有啟用分頁機制，所以我們能夠指定程式開始執行的地方以及程式載入的地址；但是，在mpentry.S的時候，由於主CPU已經處於保護模式下了，因此是不能直接指定物理地址的，給定線性地址，映射到相應的物理地址是允許的。

Per-CPU State and Initialization

JOS使用struct CpuInfo結構來記錄CPU的資訊：

struct CpuInfo {
	uint8_t cpu_id;                 // Local APIC ID; index into cpus[] below
	volatile unsigned cpu_status;   // The status of the CPU
	struct Env *cpu_env;            // The currently-running environment.
	struct Taskstate cpu_ts;        // Used by x86 to find stack for interrupt
};

cpunum()總是返回調用它的CPU的ID，宏thiscpu提供了更加方便的方式獲取當前程式碼所在的CPU對應的CpuInfo結構。

// Maximum number of CPUs
#define NCPU  8

在多處理器OS中區分每個CPU私有和共享的處理器狀態十分重要。

• Per-CPU kernel stack.
• Per-CPU TSS and TSS descriptor
• Per-CPU current environment pointer
• Per-CPU system registers.

**1. Per-CPU kernel stack **

避免互相干擾，需要為每個CPU都準備一個kernal stack，所以在記憶體中，仍然從KSTACKTOP往下，中間間隔一個KSTKGAP的距離

**2.Per-CPU TSS and TSS descriptor **

TSS和TSS描述符：每個CPU都需要單獨的TSS和TSS描述符來指定該CPU對應的內核棧。

3. Per-CPU current environment pointer

進程結構指針：每個CPU都會獨立運行一個進程的程式碼，所以需要Env指針。

4. Per-CPU system registers.

系統暫存器：比如cr3, gdt, ltr這些暫存器都是每個CPU私有的，每個CPU都需要單獨設置。

Exercise 03

重新為多CPU 分為kernal stack

static void
mem_init_mp(void)
{
	// Map per-CPU stacks starting at KSTACKTOP, for up to 'NCPU' CPUs.
	//
	// For CPU i, use the physical memory that 'percpu_kstacks[i]' refers
	// to as its kernel stack. CPU i's kernel stack grows down from virtual
	// address kstacktop_i = KSTACKTOP - i * (KSTKSIZE + KSTKGAP), and is
	// divided into two pieces, just like the single stack you set up in
	// mem_init:
	//     * [kstacktop_i - KSTKSIZE, kstacktop_i)
	//          -- backed by physical memory
	//     * [kstacktop_i - (KSTKSIZE + KSTKGAP), kstacktop_i - KSTKSIZE)
	//          -- not backed; so if the kernel overflows its stack,
	//             it will fault rather than overwrite another CPU's stack.
	//             Known as a "guard page".
	//     Permissions: kernel RW, user NONE
	//
	// LAB 4: Your code here:
	for(int i=0;i<NCPU;i++)
	{
	    boot_map_region(kern_pgdir,KSTACKTOP-KSTKSIZE - i*(KSTKSIZE +KSTKGAP),KSTKSIZE,PADDR(percpu_kstacks[i]),PTE_W);
	}
}

Exercise 04

不是對所有的CPU進行init，實際上此時程式碼執行發生在不同的CPU上，只需要對自身CPU進行初始化即可。即使用thiscpu->cpu_ts代替全局變數 ts 。

	// LAB 4: Your code here:

        //用thiscpu->cpu_ts代替ts即可
        
	// Setup a TSS so that we get the right stack
	// when we trap to the kernel.
	thiscpu->cpu_ts.ts_esp0 = KSTACKTOP;
	thiscpu->cpu_ts.ts_ss0 = GD_KD;
	thiscpu->cpu_ts.ts_iomb = sizeof(struct Taskstate);

	// Initialize the TSS slot of the gdt.
	gdt[GD_TSS0 >> 3] = SEG16(STS_T32A, (uint32_t) (&thiscpu->cpu_ts),
					sizeof(struct Taskstate) - 1, 0);
	gdt[GD_TSS0 >> 3].sd_s = 0;

	// Load the TSS selector (like other segment selectors, the
	// bottom three bits are special; we leave them 0)
	ltr(GD_TSS0);

	// Load the IDT
	lidt(&idt_pd);
}

Locking

目前我們已經有多個CPU同時在執行內核程式碼了，我們必須要處理競爭條件。最簡單粗暴的辦法就是使用”big kernel lock”，”big kernel lock”是一個全局鎖，進程從用戶態進入內核後獲取該鎖，退出內核釋放該鎖。這樣就能保證只有一個CPU在執行內核程式碼，但缺點也很明顯就是一個CPU在執行內核程式碼時，另一個CPU如果也想進入內核，就會處於等待的狀態。

鎖的數據結構在kern/spinlock.h中:

struct spinlock {
	unsigned locked;       // Is the lock held?
};

這是一種spin-locks。讓我們來看看自旋鎖的實現原理。
我們最容易想到的獲取自旋鎖的程式碼如下：

21 void
22 acquire(struct spinlock *lk)
23 {
24    for(;;) {
25      if(!lk->locked) {
26          lk->locked = 1;
27          break;
28      }
29    }
30 }

但是這種實現是有問題的，假設兩個CPU同時執行到25行，發現lk->locked是0，那麼會同時獲取該鎖。問題出在25行和26行是兩條指令。

我們的獲取鎖，釋放鎖的操作在kern/spinlock.c中：

void
spin_lock(struct spinlock *lk)
{
	// The xchg is atomic.
	// It also serializes, so that reads after acquire are not
	// reordered before it. 
	while (xchg(&lk->locked, 1) != 0)			//原理見：//pdos.csail.mit.edu/6.828/2018/xv6/book-rev11.pdf  chapter 4
		asm volatile ("pause");
}

void
spin_unlock(struct spinlock *lk)
{
	// The xchg instruction is atomic (i.e. uses the "lock" prefix) with
	// respect to any other instruction which references the same memory.
	// x86 CPUs will not reorder loads/stores across locked instructions
	// (vol 3, 8.2.2). Because xchg() is implemented using asm volatile,
	// gcc will not reorder C statements across the xchg.
	xchg(&lk->locked, 0);
}


static inline uint32_t
xchg(volatile uint32_t *addr, uint32_t newval)
{
    uint32_t result;
    // The + in "+m" denotes a read-modify-write operand.
    asm volatile("lock; xchgl %0, %1"
         : "+m" (*addr), "=a" (result)
         : "1" (newval)
         : "cc");
    return result;
}

對於spin_lock()獲取鎖的操作，使用xchgl這個原子指令，xchg()封裝了該指令，交換lk->locked和1的值，並將lk-locked原來的值返回。如果lk-locked原來的值不等於0，說明該鎖已經被別的CPU申請了，繼續執行while循環吧。因為這裡使用的xchgl指令，從addr指向的位置讀數據保存到result，然後將newval寫到該位置，但是原子的，相當於之前25和26行的結合，所以也就不會出現上述的問題。對於spin_unlock()釋放鎖的操作，直接將lk->locked置為0，表明我已經用完了，這個鎖可以被別人獲取了。
至於為什麼spin_lock()的while循環中，需要加asm volatile ("pause");？可以參考
//c9x.me/x86/html/file_module_x86_id_232.html, pause指令相當於一個帶延遲的noop指令（that is, it performs essentially a delaying noop operation），主要是為了減少能耗。

還有另一類稱作sleep lock的鎖類型。例如在一個雙核的機器上有兩個執行緒(執行緒A和執行緒B)，它們分別運行在CPU 1和CPU 2上。假設執行緒A想要某個sleep lock，而此時這個鎖正被執行緒B所持有，那麼執行緒A就會被阻塞(blocking)，CPU1 會在此時進行上下文切換將執行緒A置於等待隊列中，此時CPU 1就可以運行其他的任務(例如另一個執行緒C)而不必進行忙等待。而spin lock則不是，如果執行緒A獲取spin lock，那麼執行緒A就會一直在 CPU 1上進行忙等待並不停的進行鎖請求，直到得到這個鎖為止。
jos中沒有實現sleep lock。

有了獲取鎖和釋放鎖的函數，我們看下哪些地方需要加鎖，和釋放鎖：

1. i386_init()中，BSP喚醒其它AP前需要獲取內核鎖。
2. mp_main()中，AP需要在執行sched_yield()前獲取內核鎖。
3. trap()中，需要獲取內核鎖，因為這是用戶態進入內核的唯一入口。
4. env_run()中，需要釋放內核鎖，因為該函數使用iret指令，從內核返回用戶態。

Exercise 05

// i386_init()
// Your code here:
lock_kernel();
boot_aps();

// mp_main()
// Your code here:
lock_kernel();
sched_yield();

// trap()
// LAB 4: Your code here.
lock_kernel();
assert(curenv); 

// env_run()
lcr3(PADDR(e->env_pgdir));
unlock_kernel();
env_pop_tf(&(e->env_tf));

Question

2. It seems that using the big kernel lock guarantees that only one CPU can run the kernel code at a time. Why do we still need separate kernel stacks for each CPU? Describe a scenario in which using a shared kernel stack will go wrong, even with the protection of the big kernel lock.

1. 因為在_alltraps到 lock_kernel()的過程中，進程已經切換到了內核態，但並沒有上內核鎖，此時如果有其他CPU進入內核，如果用同一個內核棧，則_alltraps中保存的上下文資訊會被破壞，所以即使有大內核棧，CPU也不能用用同一個內核棧。同樣的，解鎖也是在內核態內解鎖，在解鎖到真正返回用戶態這段過程中，也存在上述這種情況。fang92

2. 如果內核棧中留下不同 CPU 之後需要使用的數據，可能會造成混亂

Round-Robin Scheduling (RR輪轉式)

現要JOS內核需要讓CPU能在進程之間切換。目前先實現一個非搶佔式的進程調度，需要當前進程主動讓出CPU，其他進程才有機會在當前CPU運行。具體實現如下：

1. 實現sched_yield()，該函數選擇一個新的進程運行，從當前正在運行進程對應的Env結構下一個位置開始循環搜索envs數組，找到第一個cpu_status為ENV_RUNNABLE的Env結構，然後調用env_run()在當前CPU運行這個新的進程。
2. 我們需要實現一個新的系統調用sys_yield()，使得用戶程式能在用戶態通知內核，當前進程希望主動讓出CPU給另一個進程。

Exercise 06

	// LAB 4: Your code here.
	int start = 0;
	int j;
	if (curenv) {
		start = ENVX(curenv->env_id) + 1;	//從當前Env結構的後一個開始
	}
	for (int i = 0; i < NENV; i++) {		//遍歷所有Env結構
		j = (start + i) % NENV;
		if (envs[j].env_status == ENV_RUNNABLE) {
			env_run(&envs[j]);
		}
	}
	if (curenv && curenv->env_status == ENV_RUNNING) {		//這是必須的，假設當前只有一個Env，如果沒有這個判斷，那麼這個CPU將會停機
		env_run(curenv);
	}
	// sched_halt never returns
	sched_halt();

debug到深夜

寫完excercise6之後，始終提示有kern/env.c 處有env_creat() error !

一開始茫然無措，之前運氣好也沒有出過太多的bug，有bug也就再檢查一遍程式碼就可以發現一些顯而易見的低級錯誤。但這次我反覆看了很久也沒看出問題。。然後突然想到之前內核里已經加了backtrace命令，可以查看棧里資訊和對應函數，欣喜若狂！ 一連串查出2個大錯誤：

1. kern/env.c 中的env_init()函數中env_free_list 一直是NULL，鏈接方法有問題

2. kern/trapentry.S 中的 _alltraps 寫錯了！！導致一直報錯

成功！

Question

3. In your implementation of env_run() you should have called lcr3(). Before and after the call to lcr3(), your code makes references (at least it should) to the variable e, the argument to env_run. Upon loading the %cr3 register, the addressing context used by the MMU is instantly changed. But a virtual address (namely e) has meaning relative to a given address context–the address context specifies the physical address to which the virtual address maps. Why can the pointer e be dereferenced both before and after the addressing switch?

因為當前是運行在系統內核中的，而每個進程的頁表中都是存在內核映射的。每個進程頁表中虛擬地址高於UTOP之上的地方，只有UVPT不一樣，其餘的都是一樣的，只不過在用戶態下是看不到的。所以雖然這個時候的頁表換成了下一個要運行的進程的頁表，但是映射也沒變，還是依然有效的。

4. Whenever the kernel switches from one environment to another, it must ensure the old environment』s registers are saved so they can be restored properly later. Why? Where does this happen?

因為不保存下來就無法正確地恢復到原來的環境。用戶進程之間的切換，會調用系統調用sched_yield()；用戶態陷入到內核態，可以通過中斷、異常、系統調用；這樣的切換之處都是要在系統棧上建立用戶態的TrapFrame，在進入trap()函數後，語句curenv->env_tf = *tf;將內核棧上需要保存的暫存器的狀態實際保存在用戶環境的env_tf域中。

System Calls for Environment Creation

儘管現在內核有能力在多進程之前切換，但是僅限於內核創建的用戶進程。目前JOS還沒有提供系統調用，使用戶進程能創建新的進程。
Unix提供fork()系統調用創建新的進程，fork()拷貝父進程的地址空間和暫存器狀態到子進程。父進程從fork()返回的是子進程的進程ID，而子進程從fork()返回的是0。父進程和子進程有獨立的地址空間，任何一方修改了記憶體，不會影響到另一方。

本小節需要實現如下系統調用：

1. sys_exofork()：
   創建一個新的進程，用戶地址空間沒有映射，不能運行，暫存器狀態和父環境一致。在父進程中sys_exofork()返回新進程的envid，子進程返回0。

2. sys_env_set_status：

   設置一個特定進程的狀態為ENV_RUNNABLE或ENV_NOT_RUNNABLE。

3. sys_page_alloc：

   為特定進程分配一個物理頁，映射指定線性地址va到該物理頁。

4. sys_page_map：

   拷貝頁表，使指定進程共享當前進程相同的映射關係。本質上是修改特定進程的頁目錄和頁表。共享同樣的地址空間，而不是拷貝page的內容！

5. sys_page_unmap：

   解除頁映射關係。

Exercise 07

• 補充5個系統調用函數

sys_exofork(void)：

static envid_t
sys_exofork(void)
{
	// Create the new environment with env_alloc(), from kern/env.c.
	// It should be left as env_alloc created it, except that
	// status is set to ENV_NOT_RUNNABLE, and the register set is copied
	// from the current environment -- but tweaked so sys_exofork
	// will appear to return 0.

	// LAB 4: Your code here.
	struct Env *e;
	int ret = env_alloc(&e, curenv->env_id);    //分配一個Env結構
	if (ret < 0) {
		return ret;
	}
	e->env_tf = curenv->env_tf;			//暫存器狀態和當前進程一致
	e->env_status = ENV_NOT_RUNNABLE;   //目前還不能運行
	e->env_tf.tf_regs.reg_eax = 0;		//新的進程從sys_exofork()的返回值應該為0
	return e->env_id;
}

sys_env_set_status(envid_t envid, int status):

static int
sys_env_set_status(envid_t envid, int status)
{
	// Hint: Use the 'envid2env' function from kern/env.c to translate an
	// envid to a struct Env.
	// You should set envid2env's third argument to 1, which will
	// check whether the current environment has permission to set
	// envid's status.
	if (status != ENV_NOT_RUNNABLE && status != ENV_RUNNABLE) return -E_INVAL;

	struct Env *e;
	int ret = envid2env(envid, &e, 1);
	if (ret < 0) {
		return ret;
	}
	e->env_status = status;
	return 0;
}

sys_page_alloc(envid_t envid, void *va, int perm):

static int
sys_page_alloc(envid_t envid, void *va, int perm)
{
	// Hint: This function is a wrapper around page_alloc() and
	//   page_insert() from kern/pmap.c.
	//   Most of the new code you write should be to check the
	//   parameters for correctness.
	//   If page_insert() fails, remember to free the page you
	//   allocated!

	// LAB 4: Your code here.
	struct Env *e; 									//根據envid找出需要操作的Env結構
	int ret = envid2env(envid, &e, 1);
	if (ret) return ret;	//bad_env

	if ((va >= (void*)UTOP) || (ROUNDDOWN(va, PGSIZE) != va)) return -E_INVAL;		//一系列判定
	int flag = PTE_U | PTE_P;
	if ((perm & flag) != flag) return -E_INVAL;

	struct PageInfo *pg = page_alloc(1);			//分配物理頁
	if (!pg) return -E_NO_MEM;
	ret = page_insert(e->env_pgdir, pg, va, perm);	//建立映射關係
	if (ret) {
		page_free(pg);
		return ret;
	}

	return 0;
}

sys_page_map(envid_t srcenvid, void *srcva,envid_t dstenvid, void *dstva, int perm):

static int
sys_page_map(envid_t srcenvid, void *srcva,
	     envid_t dstenvid, void *dstva, int perm)
{
	// Hint: This function is a wrapper around page_lookup() and
	//   page_insert() from kern/pmap.c.
	//   Again, most of the new code you write should be to check the
	//   parameters for correctness.
	//   Use the third argument to page_lookup() to
	//   check the current permissions on the page.

	// LAB 4: Your code here.
	struct Env *se, *de;
	int ret = envid2env(srcenvid, &se, 1);
	if (ret) return ret;	//bad_env
	ret = envid2env(dstenvid, &de, 1);
	if (ret) return ret;	//bad_env

	//	-E_INVAL if srcva >= UTOP or srcva is not page-aligned,
	//		or dstva >= UTOP or dstva is not page-aligned.
	if (srcva >= (void*)UTOP || dstva >= (void*)UTOP || 
		ROUNDDOWN(srcva,PGSIZE) != srcva || ROUNDDOWN(dstva,PGSIZE) != dstva) 
		return -E_INVAL;

	//	-E_INVAL is srcva is not mapped in srcenvid's address space.
	pte_t *pte;
	struct PageInfo *pg = page_lookup(se->env_pgdir, srcva, &pte);
	if (!pg) return -E_INVAL;

	//	-E_INVAL if perm is inappropriate (see sys_page_alloc).
	int flag = PTE_U|PTE_P;
	if ((perm & flag) != flag) return -E_INVAL;

	//	-E_INVAL if (perm & PTE_W), but srcva is read-only in srcenvid's
	//		address space.
	if (((*pte&PTE_W) == 0) && (perm&PTE_W)) return -E_INVAL;

	//	-E_NO_MEM if there's no memory to allocate any necessary page tables.
	ret = page_insert(de->env_pgdir, pg, dstva, perm);
	return ret;

}

sys_page_unmap(envid_t envid, void *va):

static int
sys_page_unmap(envid_t envid, void *va)
{
	// Hint: This function is a wrapper around page_remove().

	// LAB 4: Your code here.
	struct Env *env;
	int ret = envid2env(envid, &env, 1);
	if (ret) return ret;

	if ((va >= (void*)UTOP) || (ROUNDDOWN(va, PGSIZE) != va)) return -E_INVAL;
	page_remove(env->env_pgdir, va);
	return 0;
}

• 再syscall.c裡面的syscall()函數補充上述系統調用

...
		case SYS_page_alloc:
    			ret = sys_page_alloc(a1, (void *) a2, a3);
    			break;
		case SYS_page_map:
    			ret = sys_page_map(a1, (void *) a2, a3, (void *) a4, a5);
    			break;
		case SYS_page_unmap:
    			ret = sys_page_unmap(a1, (void *) a2);
    			break;
		case SYS_exofork:
    			ret sys_exofork();
    			break;
		case SYS_env_set_status:
    			ret sys_env_set_status(a1, a2);
    			break;
...

檢驗：

kern/init.c中 ENV_CREATE(user_dumbfork, ENV_TYPE_USER); 成功輸出，且parent 進程exit after 10 iterations, while child exits after 20.

Part A 成功！

Part A 小結

多任務並行，需要由多處理器來支援。如何由引導處理器（BSP)載入應用處理器（APs）是PartA的一個重要環節。應用處理器的啟動程式碼與BSP的啟動程式碼最大的一個區別是：此時的BSP工作在保護模式，以虛擬地址的形式進行定址，在啟動APs時需要由物理地址變換為虛擬地址來載入頁目錄等操作。啟動多處理器後，需要記錄各個CPU的Info。因為不能讓多個CPU同時進入內核，因此很重要的一點是實現內核的互斥訪問。內核互斥與循環調度很容易理解，這個Part最難的一部分在於fork system call 的實現，fork實現了用戶環境創建新的用戶進程，以區別於之前只是在內建環境之間切換。 fork()的實現，創建一個環境並且進行環境複製(tf)，以至於孩子進程也像調用了sys_exofork，並且其返回0（從而可以區分父子進程）

Part B: Copy-on-Write Fork (寫時複製Fork)

實現fork()有多種方式，一種是將父進程的內容全部拷貝一次，這樣的話父進程和子進程就能做到進程隔離，但是這種方式的缺點在於耗時，且不一定有用。因為fork()函數後面大概率會緊跟在子進程中調用exec()函數，替代原來子進程的記憶體空間為新的程式。所以如果fork時即複製，那麼有很大概率白費功夫，因為在fork() 和 exec() 之前需要用mem的情況很少。

另一種方式叫做Copy-on-Write Fork，父進程將自己的頁目錄和頁表複製給子進程，並同時將shared-pages 改為 read-only。這樣父進程和子進程就能訪問相同的內容。只有當一方執行寫操作時，發生 page fault，然後生成新的可寫的page進行複製這一頁。這樣既能做到地址空間隔離，又能節省了大量的拷貝工作——很可能fork()後緊跟exec()的進程只需要copy 1 頁(current page of the stack)。

想要實現寫時拷貝的fork()需要先實現用戶級別的缺頁中斷處理函數，to know about page faults on write-proteced pages.

User-level page fault handling

與傳統的Unix方法不同，我們將決定如何處理用戶空間中的每一個頁面錯誤，其中bug的破壞性更小。這種設計的另一個好處是允許程式在定義其記憶體區域時具有極大的靈活性；稍後將使用用戶級頁面錯誤處理來映射和訪問基於磁碟的文件系統上的文件。

為了處理自己的page faults，用戶程式需要向JOS Kernel —— register a page fault handler entrypoint. 到這裡程式碼中為Env新加了一個屬性：env_pgfault_upcall來記錄註冊資訊。

struct Env 更新

struct Env {
	struct Trapframe env_tf;	// Saved registers
	struct Env *env_link;		// Next free Env
	envid_t env_id;			// Unique environment identifier
	envid_t env_parent_id;		// env_id of this env's parent
	enum EnvType env_type;		// Indicates special system environments
	unsigned env_status;		// Status of the environment
	uint32_t env_runs;		// Number of times environment has run
	int env_cpunum;			// The CPU that the env is running on

	// Address space
	pde_t *env_pgdir;		// Kernel virtual address of page dir

	// Exception handling
	void *env_pgfault_upcall;	// Page fault upcall entry point

	// Lab 4 IPC
	bool env_ipc_recving;		// Env is blocked receiving
	void *env_ipc_dstva;		// VA at which to map received page
	uint32_t env_ipc_value;		// Data value sent to us
	envid_t env_ipc_from;		// envid of the sender
	int env_ipc_perm;		// Perm of page mapping received
};

Exercise 08

實現sys_env_set_pgfault_upcall(envid_t envid, void *func)系統調用。該系統調用為指定的用戶環境設置env_pgfault_upcall。缺頁中斷髮生時，會執行env_pgfault_upcall指定位置的程式碼。當執行env_pgfault_upcall指定位置的程式碼時，棧已經轉到異常棧，並且壓入了UTrapframe結構。

static int
sys_env_set_pgfault_upcall(envid_t envid, void *func)
{
	// LAB 4: Your code here.
	struct Env *env;
	int ret;
	if ((ret = envid2env(envid, &env, 1)) < 0) {
		return ret;
	}
	env->env_pgfault_upcall = func;
	return 0;
}

Normal and Exception Stacks in User Environments

當缺頁中斷髮生時，內核會返回用戶模式來處理該中斷。我們需要一個用戶異常棧，來模擬內核異常棧。JOS的用戶異常棧被定義在虛擬地址UXSTACKTOP。

到目前為止出現了三個棧：

　　[KSTACKTOP-KSTKSIZE,  KSTACKTOP) 
　　內核態系統棧

　　[UXSTACKTOP - PGSIZE, UXSTACKTOP )
　　用戶態錯誤處理棧

　　[UTEXT, USTACKTOP)
　　用戶態運行棧

內核態系統棧是運行內核相關程式的棧，在有中斷被觸發之後，CPU會將棧自動切換到內核棧上來，而內核棧是在kern/trap.c的trap_init_percpu()中設置的。

Invoking the User Page Fault Handler

缺頁中斷髮生時會進入內核的trap()，然後分配page_fault_handler()來處理缺頁中斷。在該函數中應該做如下幾件事：

1. 判斷curenv->env_pgfault_upcall是否設置，如果沒有設置也就沒辦法修復，直接銷毀該進程。
2. 修改esp，切換到用戶異常棧。
3. 在棧上壓入一個UTrapframe結構。
4. 將eip設置為curenv->env_pgfault_upcall，然後回到用戶態執行curenv->env_pgfault_upcall處的程式碼。

UTrapframe 結構

inc/trap.h 中的 UTrapframe

struct UTrapframe {
	/* information about the fault */
	uint32_t utf_fault_va;	/* va for T_PGFLT, 0 otherwise */
	uint32_t utf_err;
	/* trap-time return state */
	struct PushRegs utf_regs;
	uintptr_t utf_eip;
	uint32_t utf_eflags;
	/* the trap-time stack to return to */
	uintptr_t utf_esp;
} __attribute__((packed));

對應的棧結構：（注意還是倒敘壓入！）

                    <-- UXSTACKTOP
trap-time esp
trap-time eflags
trap-time eip
trap-time eax       start of struct PushRegs
trap-time ecx
trap-time edx
trap-time ebx
trap-time esp
trap-time ebp
trap-time esi
trap-time edi       end of struct PushRegs
tf_err (error code)
fault_va            <-- %esp when handler is run

Exercise 09

void
page_fault_handler(struct Trapframe *tf)
{
	uint32_t fault_va;

	// Read processor's CR2 register to find the faulting address
	fault_va = rcr2();

	// Handle kernel-mode page faults.

	// LAB 3: Your code here.
	if((tf->tf_cs & 3) ==0)
	{
	     panic("page_fault in kernel mode, fault address %d\n", fault_va);
	}

// LAB 4: Your code here.
	if (curenv->env_pgfault_upcall) 
	{
		uintptr_t stacktop = UXSTACKTOP;
		if (UXSTACKTOP - PGSIZE < tf->tf_esp && tf->tf_esp < UXSTACKTOP) 
		{
			stacktop = tf->tf_esp;
		}
		uint32_t size = sizeof(struct UTrapframe) + sizeof(uint32_t);
		user_mem_assert(curenv, (void *)stacktop - size, size, PTE_U | PTE_W);
		struct UTrapframe *utr = (struct UTrapframe *)(stacktop - size);//在棧上壓入一個UTrapframe結構
		utr->utf_fault_va = fault_va;
		utr->utf_err = tf->tf_err;
		utr->utf_regs = tf->tf_regs;
		utr->utf_eip = tf->tf_eip;
		utr->utf_eflags = tf->tf_eflags;
		utr->utf_esp = tf->tf_esp;				//UXSTACKTOP棧上需要保存發生缺頁異常時的%esp和%eip

		curenv->env_tf.tf_eip = (uintptr_t)curenv->env_pgfault_upcall;  //將eip置為curenv->env_pgfault_upcall，然後回到用戶態執行curenv->env_pgfault_upcall處的程式碼
		curenv->env_tf.tf_esp = (uintptr_t)utr;  //修改esp 切換到用戶異常棧
		env_run(curenv);			//重新進入用戶態
	}

User-mode Page Fault Entrypoint

現在需要實現lib/pfentry.S中的_pgfault_upcall函數，該函數會作為系統調用sys_env_set_pgfault_upcall()的參數。

Exercise 10

實現lib/pfentry.S中的_pgfault_upcall函數。

⏰： 需要對照著UTrapframe 來寫；

同時，這裡的數字加減單位是位元組（8位），例如utf_fault_va是 uint32_t，那麼就是4個位元組32位

.text
.globl _pgfault_upcall
_pgfault_upcall:
	// Call the C page fault handler.
	pushl %esp			// function argument: pointer to UTF  //esp:棧頂指針
	movl _pgfault_handler, %eax    
	call *%eax                    //調用頁處理函數
	addl $4, %esp			// pop function argument

	// LAB 4: Your code here.
	
	//需要對照著UTrapframe 來寫
	//這裡的數字加減單位是位元組（8位），例如utf_fault_va是 uint32_t，那麼就是4個位元組32位
	addl $8, %esp			//esp+8 -> PushRegs，跳過utf_fault_va和utf_err，esp是棧頂，把棧頂往上減少
	movl 40(%esp), %eax 	//保存中斷髮生時的esp到eax   //都需要對照uft的堆棧結構
	movl 32(%esp), %ecx 	//保存終端發生時的eip到ecx，因為esp+0x20 即是 utf_eip
	movl %ecx, -4(%eax) 	//將中斷髮生時的esp值壓入到到原來的棧中
	popal
	addl $4, %esp			//跳過eip

	// Restore the trap-time registers.  After you do this, you
	// can no longer modify any general-purpose registers.
	// LAB 4: Your code here.
	
	

	// Restore eflags from the stack.  After you do this, you can
	// no longer use arithmetic operations or anything else that
	// modifies eflags.
	// LAB 4: Your code here.
	popfl
	

	// Switch back to the adjusted trap-time stack.
	// LAB 4: Your code here.
	popl %esp

	// Return to re-execute the instruction that faulted.
	// LAB 4: Your code here.
	lea -4(%esp), %esp		//因為之前壓入了eip的值但是沒有減esp的值，所以現在需要將esp暫存器中的值減4
	ret

Exercise 11

void
set_pgfault_handler(void (*handler)(struct UTrapframe *utf))  //函數指針
{
	int r;

	if (_pgfault_handler == 0) 
	{
		// First time through! //第一次
		// LAB 4: Your code here.
		//panic("set_pgfault_handler not implemented");
		int r = sys_page_alloc(0, (void *)(UXSTACKTOP-PGSIZE), PTE_W | PTE_U | PTE_P);	//為當前進程分配異常棧
		if (r < 0) 
		{
			panic("set_pgfault_handler:sys_page_alloc failed！\n");
		}
		sys_env_set_pgfault_upcall(0, _pgfault_upcall);		//系統調用，設置進程的env_pgfault_upcall屬性
	}
	

	// Save handler pointer for assembly to call.
	_pgfault_handler = handler;
}

測試+debug

1. Run user/faultread (make run-faultread). ✔
   

2. Run user/faultdie. （❌）

一開始是失敗的！錯誤提示資訊如下所示：

3. Run user/faultalloc. （❌）

一開始是失敗的！錯誤提示資訊如下所示：

這個跟書上的要求不太一樣

4. Run user/faultallocbad. ✔

Debug

經過backtrace+海王搜索法，找了快半個小時，終於找到原來是syscall.c裡面沒有給 SYS_env_set_pgfault_upcall添加到switch中進行調度！！！

加上之後：

• Run user/faultdie.
  

• Run user/faultalloc.
  

make grade

缺頁處理小結：

1. 引發缺頁中斷，執行內核函數鏈：trap()->trap_dispatch()->page_fault_handler()
2. page_fault_handler()切換棧到用戶異常棧，並且壓入UTrapframe結構，然後調用curenv->env_pgfault_upcall（系統調用sys_env_set_pgfault_upcall()設置）處程式碼。又重新回到用戶態。
3. 進入_pgfault_upcall處的程式碼執行，調用_pgfault_handler（庫函數set_pgfault_handler()設置）處的程式碼，最後返回到缺頁中斷髮生時的那條指令重新執行。

Implementing Copy-on-Write Fork

到目前已經可以實現用戶級別的寫時拷貝fork函數了。fork流程如下：

1. 使用set_pgfault_handler()設置缺頁處理函數_pgfault_handler = handler。

2. 調用sys_exofork()系統調用，在內核中創建一個Env結構，複製當前用戶環境暫存器狀態，UTOP以下的頁目錄還沒有建立，新創建的進程還不能直接運行。

3. 拷貝父進程的頁表和頁目錄到子進程。對於可寫的頁，將對應的PTE的PTE_COW位設置為1。

4. 為子進程設置_pgfault_upcall。

   sys_env_set_pgfault_upcall()中 為env->env_pgfault_upcall 設置了pgfault的時候的處理函數func

5. 將子進程狀態設置為ENV_RUNNABLE。

[Note] 此處的順序十分重要——父進程在子進程之後對 COW 頁進行 mark 。

缺頁處理函數pgfault()流程如下：

1. 如果發現錯誤是因為寫造成的（錯誤碼是FEC_WR）並且該頁的PTE_COW是1，則進行執行第2步，否則直接panic。
2. 分配一個新的物理頁，並將之前出現錯誤的頁的內容拷貝到新的物理頁，然後重新映射線性地址到新的物理頁。

Clever mapping tricks

官網材料：//pdos.csail.mit.edu/6.828/2018/labs/lab4/uvpt.html

簡而言之，這個trick的巧妙之處在於，我們定義page directory, page table,page frame的時候本能的想到了下圖：

但是他們本質上都是一串格式相同的數字罷了，誰規定的page directory只能是page directory了！如果我們將指針放入頁面目錄，該指針指向索引 V （page directory)的自身，那麼根據頁目錄查詢情況：kern_pgdir[PDX(kern_pgdir)]尋找到的頁面（這裡的角色是page table）仍然是V指向的頁面。

當我們嘗試翻譯一個虛擬地址與PDX和PTX等於V，以下三個箭頭離開我們在頁面目錄。因此，該虛擬頁面將轉換為包含頁面目錄的頁面。在JOS，V 為 0x3BD，因此 UVPD 的虛擬地址為 （0x3BD<<<22)|(0x3BD<<12）。

現在，如果我們嘗試使用 PDX = V 轉換虛擬地址，但使用任意的 PTX！= V 轉換，則從 CR3 中跟隨三個箭頭將比平常一個級別向上一個級別（而不是上一例中的兩個級別），這就是在頁表中。因此，PDX+V 的虛擬頁面集形成了一個 4MB 區域，其頁面內容（就處理器而言）是頁面表本身。在 Jos 中，V 為 0x3BD，因此 UVPT 的虛擬地址為 （0x3BD<<<22）。

🚩uvpt[pagenumber]

可以直接訪問第pagenumber項頁表條目。

Exercise 12

特別注意：

duppage()中複製的可能情況：

• 對於表示為PTE_SHARE的頁，拷貝映射關係，並且兩個進程都有讀寫許可權
• 對於UTOP以下的可寫的或者寫時拷貝的頁，拷貝映射關係的同時，需要同時標記當前進程和子進程的頁表項為PTE_COW
• 對於只讀的頁，只需要拷貝映射關係即可

static void
pgfault(struct UTrapframe *utf)
{
	void *addr = (void *) utf->utf_fault_va;
	uint32_t err = utf->utf_err;
	int r;

	// Check that the faulting access was (1) a write, and (2) to a
	// copy-on-write page.  If not, panic.
	// Hint:
	//   Use the read-only page table mappings at uvpt
	//   (see <inc/memlayout.h>).

	// LAB 4: Your code here.
	if (!((err & FEC_WR) && (uvpt[PGNUM(addr)] & PTE_COW))) { //只有因為寫操作寫時拷貝的地址這種情況，才可以搶救。否則一律panic
		panic("pgfault():not cow");
	}


	// Allocate a new page, map it at a temporary location (PFTEMP),
	// copy the data from the old page to the new page, then move the new
	// page to the old page's address.
	// Hint:
	//   You should make three system calls.

	// LAB 4: Your code here.
	addr = ROUNDDOWN(addr, PGSIZE);
	if ((r = sys_page_map(0, addr, 0, PFTEMP, PTE_U|PTE_P)) < 0)		//將當前進程PFTEMP也映射到當前進程addr指向的物理頁
		panic("sys_page_map: %e", r);
	if ((r = sys_page_alloc(0, addr, PTE_P|PTE_U|PTE_W)) < 0)	//令當前進程addr指向新分配的物理頁
		panic("sys_page_alloc: %e", r);
	memmove(addr, PFTEMP, PGSIZE);								//將PFTEMP指向的物理頁拷貝到addr指向的物理頁
	if ((r = sys_page_unmap(0, PFTEMP)) < 0)					//解除當前進程PFTEMP映射
		panic("sys_page_unmap: %e", r);
}

static int
duppage(envid_t envid, unsigned pn)
{
	int r;

	// LAB 4: Your code here.
 	void *addr = (void*) (pn * PGSIZE);
	if ((uvpt[pn] & PTE_W) || (uvpt[pn] & PTE_COW)) { //對於UTOP以下的可寫的或者寫時拷貝的頁，拷貝映射關係的同時，需要同時標記當前進程和子進程的頁表項為PTE_COW
		if ((r = sys_page_map(0, addr, envid, addr, PTE_COW|PTE_U|PTE_P)) < 0)
			panic("sys_page_map：%e", r);
		if ((r = sys_page_map(0, addr, 0, addr, PTE_COW|PTE_U|PTE_P)) < 0)
			panic("sys_page_map：%e", r);
	} else {
		sys_page_map(0, addr, envid, addr, PTE_U|PTE_P);	//對於只讀的頁，只需要拷貝映射關係即可
	}
	return 0;
}

envid_t
fork(void)
{
	// LAB 4: Your code here.
	extern void _pgfault_upcall(void);
	set_pgfault_handler(pgfault);	//設置缺頁處理函數
	envid_t envid = sys_exofork();	//系統調用，只是簡單創建一個Env結構，複製當前用戶環境暫存器狀態，UTOP以下的頁目錄還沒有建立
	if (envid == 0) {				//子進程將走這個邏輯
		thisenv = &envs[ENVX(sys_getenvid())];
		return 0;
	}
	if (envid < 0) {
		panic("sys_exofork: %e", envid);
	}

	uint32_t addr;
	for (addr = 0; addr < USTACKTOP; addr += PGSIZE) {
		if ((uvpd[PDX(addr)] & PTE_P) && (uvpt[PGNUM(addr)] & PTE_P) //為什麼uvpt[pagenumber]能訪問到第pagenumber項頁表條目：//pdos.csail.mit.edu/6.828/2018/labs/lab4/uvpt.html
			&& (uvpt[PGNUM(addr)] & PTE_U)) {
			duppage(envid, PGNUM(addr));	//拷貝當前進程映射關係到子進程
		}
	}
	int r;
	if ((r = sys_page_alloc(envid, (void *)(UXSTACKTOP-PGSIZE), PTE_P | PTE_W | PTE_U)) < 0)	//為子進程分配異常棧
		panic("sys_page_alloc: %e", r);
	sys_env_set_pgfault_upcall(envid, _pgfault_upcall);		//為子進程設置_pgfault_upcall

	if ((r = sys_env_set_status(envid, ENV_RUNNABLE)) < 0)	//設置子進程為ENV_RUNNABLE狀態
		panic("sys_env_set_status: %e", r);
	return envid;
}

Part C: Preemptive Multitasking and Inter-Process communication (IPC)

Interrupt discipline

目前程式一旦進入用戶模式，除非發生中斷，否則CPU永遠不會再執行內核程式碼。為了避免CPU資源被惡意搶佔，需要開啟時鐘中斷，強迫進入內核，然後內核就可以切換另一個進程執行。

外部中斷（即，設備中斷）被稱為IRQs。有16個可能的IRQ，編號為0到15。從IRQ編號到IDT條目的映射不是固定的。picirq.c中的pic_init通過IRQ_OFFSET+15將IRQ 0-15映射到IDT條目IRQ_OFFSET。

External interrupts are controlled by the FL_IF flag bit of the %eflags register (see inc/mmu.h).外部中斷由%eflags 的FL_IF flag位控制。設置了該位，外部中斷啟用。 bootloader的第一條指令是屏蔽外部中斷，不簽位置還沒有開啟中斷。

Exercise 13

修改kern/trapentry.S和kern/trap.c以初始化IDT中的相應條目，並為IRQ 0到15提供處理程式。然後修改kern/env.c中env_alloc（）中的程式碼，以確保用戶環境始終在啟用中斷的情況下運行.還要取消sched_halt（）中sti指令的注釋，以便空閑CPU取消掩碼中斷。

1. 修改Trapentry.s，當調用硬體中斷處理時，處理器不會傳入錯誤程式碼，因此我們需要調用TRAPHANDLER_NOEC宏。

2. 修改trap.c， 註冊IDT。

3. IDT表項中的每一項都初始化為中斷門，這樣在發生任何中斷/異常的時候，陷入內核態的時候，CPU都會將%eflags暫存器上的FL_IF標誌位清0，關閉中斷；切換回用戶態的時候，CPU將內核棧中保存的%eflags暫存器彈回%eflags暫存器，恢復原來的狀態。You will have to ensure that the FL_IF flag is set in user environments when they run so that when an interrupt arrives, it gets passed through to the processor and handled by your interrupt code.

4. 🚩 易錯！！在env_allco中加入以下程式碼， 同時取消 sched_halt()中sti的注釋，使能中斷。

   //STI 置中斷允許位.

Handling Clock Interrupts

lapic_init()和pic_init()設置時鐘中斷控制器產生中斷。需要寫程式碼來處理中斷。

具體地：lapic_init設定中斷號，設置時鐘以及中斷控制器生成中斷等。 pic_init初始化 8259A 中斷控制器。（但還是不太能理解具體幹什麼）

Exercise14

// Handle clock interrupts. Don't forget to acknowledge the
// interrupt using lapic_eoi() before calling the scheduler!
// LAB 4: Your code here.
if(IRO_OFFSET + IRO_TIMER)
{
    // 回應8259A CPU已經接收中斷。
    //處理始終中斷
        lapic_eoi();
        sched_yield();
        return;
}

Inter-Process communication (IPC)

到目前為止，我們都在做隔離的事情。作業系統另一個重要的內容是允許程式相互交流。

IPC in JOS

我們將要實現sys_ipc_recv()和sys_ipc_try_send()這兩個系統調用，來實現進程間通訊。並且實現兩個包裝函數ipc_recv()和 ipc_send()。
JOS中進程間通訊的「消息」包含兩部分：

1. 一個32位的值。
2. 可選的頁映射關係。

Sending and Receiving Messages

sys_ipc_recv()和sys_ipc_try_send()是這麼協作的：

1. 當某個進程調用sys_ipc_recv()後，該進程會阻塞（狀態被置為ENV_NOT_RUNNABLE），直到另一個進程向它發送「消息」。當進程調用sys_ipc_recv()傳入dstva參數時，表明當前進程準備接收頁映射。
2. 進程可以調用sys_ipc_try_send()向指定的進程發送「消息」，如果目標進程已經調用了sys_ipc_recv()，那麼就發送數據，然後返回0，否則返回-E_IPC_NOT_RECV，表示目標進程不希望接受數據。當傳入srcva參數時，表明發送進程希望和接收進程共享srcva對應的物理頁。如果發送成功了發送進程的srcva和接收進程的dstva將指向相同的物理頁。

Exercise 15

實現sys_ipc_recv()和sys_ipc_try_send()。包裝函數ipc_recv()和 ipc_send()。

static int
sys_ipc_try_send(envid_t envid, uint32_t value, void *srcva, unsigned perm)
{
	// LAB 4: Your code here.
	struct Env *rcvenv;
	int ret = envid2env(envid, &rcvenv, 0);
	if (ret) return ret;
	if (!rcvenv->env_ipc_recving) return -E_IPC_NOT_RECV;

	if (srcva < (void*)UTOP) {
		pte_t *pte;
		struct PageInfo *pg = page_lookup(curenv->env_pgdir, srcva, &pte);

		//按照注釋的順序進行判定
		if (debug) {
			cprintf("sys_ipc_try_send():srcva=%08x\n", (uintptr_t)srcva);
		}
		if (srcva != ROUNDDOWN(srcva, PGSIZE)) {		//srcva沒有頁對齊
			if (debug) {
				cprintf("sys_ipc_try_send():srcva is not page-alligned\n");
			}
			return -E_INVAL;
		}
		if ((*pte & perm & 7) != (perm & 7)) {  //perm應該是*pte的子集
			if (debug) {
				cprintf("sys_ipc_try_send():perm is wrong\n");
			}
			return -E_INVAL;
		}
		if (!pg) {			//srcva還沒有映射到物理頁
			if (debug) {
				cprintf("sys_ipc_try_send():srcva is not maped\n");
			}
			return -E_INVAL;
		}
		if ((perm & PTE_W) && !(*pte & PTE_W)) {	//寫許可權
			if (debug) {
				cprintf("sys_ipc_try_send():*pte do not have PTE_W, but perm have\n");
			}
			return -E_INVAL;
		}		
		
		if (rcvenv->env_ipc_dstva < (void*)UTOP) {
			ret = page_insert(rcvenv->env_pgdir, pg, rcvenv->env_ipc_dstva, perm); //共享相同的映射關係
			if (ret) return ret;
			rcvenv->env_ipc_perm = perm;
		}
	}
	rcvenv->env_ipc_recving = 0;					//標記接受進程可再次接受資訊
	rcvenv->env_ipc_from = curenv->env_id;
	rcvenv->env_ipc_value = value; 
	rcvenv->env_status = ENV_RUNNABLE;
	rcvenv->env_tf.tf_regs.reg_eax = 0;
	return 0;
}

static int
sys_ipc_recv(void *dstva)
{
	// LAB 4: Your code here.
	if (dstva < (void *)UTOP && dstva != ROUNDDOWN(dstva, PGSIZE)) {
		return -E_INVAL;
	}
	curenv->env_ipc_recving = 1;
	curenv->env_status = ENV_NOT_RUNNABLE;
	curenv->env_ipc_dstva = dstva;
	sys_yield();
	return 0;
}
int32_t
ipc_recv(envid_t *from_env_store, void *pg, int *perm_store)
{
	// LAB 4: Your code here.
	if (pg == NULL) {
		pg = (void *)-1;
	}
	int r = sys_ipc_recv(pg);
	if (r < 0) {				//系統調用失敗
		if (from_env_store) *from_env_store = 0;
		if (perm_store) *perm_store = 0;
		return r;
	}
	if (from_env_store)
		*from_env_store = thisenv->env_ipc_from;
	if (perm_store)
		*perm_store = thisenv->env_ipc_perm;
	return thisenv->env_ipc_value;
}

void
ipc_send(envid_t to_env, uint32_t val, void *pg, int perm)
{
	// LAB 4: Your code here.
	if (pg == NULL) {
		pg = (void *)-1;
	}
	int r;
	while(1) {
		r = sys_ipc_try_send(to_env, val, pg, perm);
		if (r == 0) {		//發送成功
			return;
		} else if (r == -E_IPC_NOT_RECV) {	//接收進程沒有準備好
			sys_yield();
		} else {			//其它錯誤
			panic("ipc_send():%e", r);
		}
	}
}

<Oh NO！！怎麼會這樣子！！>

認真尋找又是兩三個小時後，，，發現是lib/duppage()寫錯了！😭

錯誤版

static int
duppage(envid_t envid, unsigned pn)
{
	int r;

	// LAB 4: Your code here.
	//panic("duppage not implemented");

	void *addr = (void*) (pn * PGSIZE);
	if (uvpt[pn] & PTE_SHARE) 
	{
		sys_page_map(0, addr, envid, addr, PTE_SYSCALL);		//對於表示為PTE_SHARE的頁，拷貝映射關係，並且兩個進程都有讀寫許可權
	} 
	else if ((uvpt[pn] & PTE_W) || (uvpt[pn] & PTE_COW)) 
	    { //對於UTOP以下的可寫的或者寫時拷貝的頁，拷貝映射關係的同時，需要同時標記當前進程和子進程的頁表項為PTE_COW
		if ((r = sys_page_map(0, addr, envid, addr, PTE_COW|PTE_U|PTE_P)) < 0)
			panic("sys_page_map：%e", r);  
		if ((r = sys_page_map(0, addr, 0, addr, PTE_COW|PTE_U|PTE_P)) < 0)
			panic("sys_page_map：%e", r);
	    } 
        else 
	    {
		sys_page_map(0, addr, envid, addr, PTE_U|PTE_P);	//對於只讀的頁，只需要拷貝映射關係即可
	    }

	return 0;
}

正確版

static int
duppage(envid_t envid, unsigned pn)
{
	int r;

	// LAB 4: Your code here.
	//panic("duppage not implemented");
	
 	void *addr = (void*) (pn * PGSIZE);
	if ((uvpt[pn] & PTE_W) || (uvpt[pn] & PTE_COW)) { //對於UTOP以下的可寫的或者寫時拷貝的頁，拷貝映射關係的同時，需要同時標記當前進程和子進程的頁表項為PTE_COW
		if ((r = sys_page_map(0, addr, envid, addr, PTE_COW|PTE_U|PTE_P)) < 0)
			panic("sys_page_map：%e", r);
		if ((r = sys_page_map(0, addr, 0, addr, PTE_COW|PTE_U|PTE_P)) < 0)
			panic("sys_page_map：%e", r);
	} else {
		sys_page_map(0, addr, envid, addr, PTE_U|PTE_P);	//對於只讀的頁，只需要拷貝映射關係即可
	}
	return 0;
}

成功啦！