笔记016 - Lab4: Preemptive Multitasking

发表于 | 分类于

Part A: Multiprocessor Support and Cooperative Multitasking

任务：扩展jos使之支持多处理器；添加系统调用支持用户进程创建新进程；实现协作性循环调度，当前进程自愿放弃cpu或exit的时候允许内核由一个进程切换到另一个进程。

Multiprocessor Support

jos支持“对称多处理”(SMP：symmetric multiprocessing)，这是一种多处理器模型，所有cpu都能等价访问系统资源，如内存和I/O总线。在SMP中，尽管所有cpu在功能上是相同的，在引导过程中仍然可以将它们分为两类：1、引导处理器BSP（the bootstrap processor）：负责初始化系统和启动操作系统；2、应用程序处理器APs（the application processors）：在操作系统启动之后由BSP激活，然后开始运行。硬件和BIOS决定哪个处理器是BSP。到目前为止，所有jos代码都是运行在BSP上的。

在SMP系统中，每个cpu都有一个附带的局部高级可编程中断处理器LAPIC（local APIC：Advanced Programmable Interrupt Controller）。LAPIC负责在整个系统中传递中断。LAPIC为其所连接的cpu提供一个唯一的标识符。在lab4中，我们使用LAPIC单元的三个基本功能：
1、读取LAPIC标识符APIC ID以识别我们的代码当前运行在哪个cpu上。（见cpunum()）
2、从BSP处发送STARTUP处理器间中断IPI（interprocessor interrupt）到APs，启动其他cpu。（见lapic_startap()）
3、part C将编程LAPIC的内置计时器，触发时钟中断以支持抢占式多任务调度。（见apic_init()）

处理器通过内存映射I/O MMIO（memory-mapped I/O）来访问附带的LAPIC。在MMIO中，一部分物理内存是硬连线到一些I/O设备的寄存器上的，所以可以通过使用相同的用以访问内存的load/store指令来访问设备寄存器。关于IO hole，我们已经使用了物理地址0xA0000来写VGA display缓存。LAPIC存放的IO hole起始物理地址是0xFE000000（4G空间中的32m），使用在KERNBASE的直接映射来访问的话，这个地址太高了。在jos中，虚拟内存映射在MMIOBASE位置留出了4MB空间以映射设备。

1
Exercise 1: 实现kern/pmap.c的mmio_map_region函数，在kern/lapic.c的lapic_init中查看mmio_map_region函数的使用情况。需要做完Exercise 2之后才能通过对于mmio_map_region的测试。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//
// Reserve size bytes in the MMIO region and map [pa,pa+size) at this
// location.  Return the base of the reserved region.  size does *not*
// have to be multiple of PGSIZE.
//
// jianzzz: 我们可能会多次调用mmio_map_region()，每一次给出pa和size，将会将pa映射到递增的va，映射范围是size(以PGSIZE为大小向上对齐)。若映射地址超出MMIOLIM则越界。
void *
mmio_map_region(physaddr_t pa, size_t size)
{ 
	static uintptr_t base = MMIOBASE;

	// Reserve size bytes of virtual memory starting at base and
	// map physical pages [pa,pa+size) to virtual addresses
	// [base,base+size).  Since this is device memory and not
	// regular DRAM, you'll have to tell the CPU that it isn't
	// safe to cache access to this memory.  Luckily, the page
	// tables provide bits for this purpose; simply create the
	// mapping with PTE_PCD|PTE_PWT (cache-disable and
	// write-through) in addition to PTE_W.  (If you're interested
	// in more details on this, see section 10.5 of IA32 volume
	// 3A.)
	//
	// Be sure to round size up to a multiple of PGSIZE and to
	// handle if this reservation would overflow MMIOLIM (it's
	// okay to simply panic if this happens). 
	// Your code here:
	uint32_t sizeup = (uint32_t)ROUNDUP((char *) size, PGSIZE);
	if(base + sizeup > MMIOLIM){
		panic("mmio_map_region: requested size to map went over MMIOLIM");
	}
	boot_map_region(kern_pgdir,base,sizeup,pa,PTE_PCD | PTE_PWT | PTE_W | PTE_P);
	base += sizeup; 
	//panic("mmio_map_region not implemented");
	return (void *)(base-sizeup);
}

Application Processor Bootstrap

在启动APs之前，BSP从BIOS的内存区域中读取MP配置表，收集多处理器系统的信息，比如CPUs数目、APIC IDs、LAPIC单元的MMIO地址。见kern/mpconfig.c的mp_init()。

kern/init.c的boot_aps()函数驱动AP启动程序的运行。APs在实模式下启动，与boot/boot.S的引导过程相似：boot_aps()将AP入口代码（kern/mpentry.S）拷贝到实模式下的一个可寻址的内存位置。与boot/boot.S的引导过程不同的是，jos会控制AP将会在哪里开始执行代码；jos将入口代码拷贝到0x7000（MPENTRY_PADDR），但640KB以下的任何unused、page-aligned的物理地址都被使用。

此后，boot_aps()逐一激活APs，通过给匹配AP的LAPIC发送STARTUP IPIs以及一个初始CS:IP地址，AP将在该地址上（即MPENTRY_PADDR）执行入口代码。kern/mpentry.S在简单设置之后将AP运行模式设为保护模式，开启分页，然后调用c函数mp_main()（also in kern/init.c）。boot_aps()等待AP发送CPU_STARTED信号（见struct CpuInfo的cpu_status域），然后激活下一个AP。

1
Exercise 2. 阅读boot_aps()和mp_main()，以及kern/mpentry.S，了解APs启动过程的control flow transfer。修改kern/pmap.c的page_init()实现，避免在MPENTRY_PADDR分配页，保证APs启动代码的拷贝、运行安全。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
void
page_init(void)
{
	// LAB 4:
	// Change your code to mark the physical page at MPENTRY_PADDR
	// as in use

	// The example code here marks all physical pages as free.
	// However this is not truly the case.  What memory is free?
	//  1) Mark physical page 0 as in use.
	//     This way we preserve the real-mode IDT and BIOS structures
	//     in case we ever need them.  (Currently we don't, but...)
	//  第一页数据是被使用的，该页保存了实模式IDT和BIOS数据结构
	//  2) The rest of base memory, [PGSIZE, npages_basemem * PGSIZE)
	//     is free.
	//  第二页至基本内存结束位置(640K)是可用的
	//  3) Then comes the IO hole [IOPHYSMEM, EXTPHYSMEM), which must
	//     never be allocated.
	//  [IOPHYSMEM, EXTPHYSMEM),即[0x0A0000,0x100000)--[640K,1MB)是被使用的
	//  4) Then extended memory [EXTPHYSMEM, ...).
	//     Some of it is in use, some is free. Where is the kernel
	//     in physical memory?  Which pages are already in use for
	//     page tables and other data structures?
	//  扩展内存开始位置至当前pages数组存储的末端为不可使用的部分，其中包括页目录空间和映射内存的pages数组空间!!!
	//  当前pages数组存储的末端开始至可用内存末端即为可用的
	//
	// Change the code to reflect this.
	// NB: DO NOT actually touch the physical memory corresponding to
	// free pages!

	// uint32_t page_IOPHYSMEMBEGIN = npages_basemem;
	uint32_t page_IOPHYSMEMBEGIN = (uint32_t)IOPHYSMEM / PGSIZE;

	// uint32_t num_pages_io_hole = 96;
	// uint32_t page_EXTPHYSMEMBEGIN = npages_basemem + num_pages_io_hole;
	uint32_t page_EXTPHYSMEMBEGIN = (uint32_t)EXTPHYSMEM / PGSIZE;
	
	// 内核代码存放于0x100000处，即1M处，KERNBASE是内核代码存储起点的虚拟地址
	// 对于存于物理地址1M后的数据，其虚拟地址减去KERNBASE的值相当于该处与内核代码存储起点虚拟地址位置的差，
	// 而不是与0x0的差, 需要加上1M的空间
	// 1M = 256 page 
	// uint32_t num_kernelpages = (((uint32_t) boot_alloc(0)) - KERNBASE) / PGSIZE;
	//uint32_t page_KernelPageInfoEnd = npages_basemem + num_pages_io_hole + num_kernelpages; 
	uint32_t page_KernelPageInfoEnd = (((uint32_t) boot_alloc(0)) - KERNBASE) / PGSIZE + 256;    
	 
	page_free_list = NULL;
	size_t i;
	//pages数组与实际物理空间存在映射关系，但没有使用实际空间存储物理页位置
	for (i = 0; i < npages; i++) {
		if(i==0 ||
			//Lab4 : page at MPRENTRY_PADDR, reserved for CPU startup code . e.g. 0x7000
			i == PGNUM(MPENTRY_PADDR) ||
			//(i>=page_IOPHYSMEM && i<page_EXTPHYSMEMBEGIN) ||
			//(i>=page_EXTPHYSMEMBEGIN && i<page_KernelPageInfoEnd) ||
			(i>=page_IOPHYSMEMBEGIN && i<page_KernelPageInfoEnd)
			){
			pages[i].pp_ref = 1;
			continue;	
		} 
		pages[i].pp_ref = 0;		
		//往回指的指针pp_link要越过非空物理页,这样page_free_list才能通过pp_link往回获取空闲空间
		//双向链表
		pages[i].pp_link = page_free_list;
		page_free_list = &pages[i];
	}
}
1
Question 1. 比较kern/mpentry.S和boot/boot.S。请记住：kern/mpentry.S被编译和链接后是运行在KERNBASE之上的，就像其他程序一样。设计MPBOOTPHYS宏的目的是什么？为什么boot/boot.S不需要它？
1
2
kern/mpentry.S的内容原先是加载在内核程序的页空间中的，在BSP激活其他APs之前，BSP会将这部分内容移到MPENTRY_PADDR物理页中。所以AP在执行kern/mpentry.S时，kern/mpentry.S中的标记符物理地址需要以MPENTRY_PADDR为基础重新计算。MPBOOTPHYS宏就是用于确定kern/mpentry.S中的标识符物理地址。
对于boot/boot.S来说，它是由bios加载到0x7c00的，然后开始执行这部分代码，由于当时尚未开启分页，链接地址即为物理地址，所以boot/boot.S中标识符的物理地址是直接由链接地址确定的。

Per-CPU State and Initialization

多处理器操作系统很重要的一点是区分每个处理器私有的处理器状态和整个系统共享的全局状态。kern/cpu.h定义了per-CPU状态的大部分，包括struct CpuInfo（存储per-CPU变量）。cpunum()返回的是调用它的cpu的ID，该值可以索引cpus数组。thiscpu是个宏定义，指向当前cpu的struct CpuInfo。
以下是部分per-CPU状态：
1、Per-CPU kernel stack：多个cpu可以同时trap到内核中，为了防止干扰彼此的运行，需要为每个处理器设置单独的栈空间。内核物理空间中数组percpu_kstacks[NCPU][KSTKSIZE]保存了NCPU个栈空间。BSP的内核栈地址是bootstack，映射到虚拟地址KSTACKTOP之下的KSTKSIZE大小的空间。紧随着，越过KSTKGAP字节之后，映射CPU1栈空间，以此类推。
2、Per-CPU TSS and TSS descriptor：TSS任务状态段用于寻位每个cpu的内核栈。CPU i的TSS存于cpus[i].cpu_ts中，相关联的TSS描述符定义在GDT入口gdt[(GD_TSS0 >> 3) + i]。kern/trap.c定义的全局ts变量不再生效。
3、Per-CPU current environment pointer：因为每个cpu可以同时运行不同的用户进程，因此重新定义curenv指向cpus[cpunum()].cpu_env，它指向的是运行在当前cpu上的当前进程。
4、所有的寄存器，包括系统寄存器，对每个cpu来说都是私有的。因此，初始化这些寄存器的指令，比如lcr3(), ltr(), lgdt(), lidt()等，都必须在每个寄存器上执行一次。env_init_percpu()和trap_init_percpu()正是用于这个目的。

1
Exercise 3. 修改kern/pmap.c的mem_init_mp()函数，将每个cpu的栈映射到KSTACKTOP以下部分，参考inc/memlayout.h。每个栈的大小是KSTKSIZE+KSTKGAP字节。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
static void
mem_init_mp(void)
{ 
	//     Permissions: kernel RW, user NONE
	//
	// LAB 4: Your code here:
	int i=0;
	uint32_t bottom_stack = KSTACKTOP - KSTKSIZE;
	for (i = 0; i < NCPU; i++) {
		boot_map_region(kern_pgdir, bottom_stack, KSTKSIZE, PADDR(percpu_kstacks[i]), PTE_W | PTE_P);
		bottom_stack -= KSTKGAP; // guard
		bottom_stack -= KSTKSIZE;
	}
}
1
Exercise 4. kern/trap.c的trap_init_percpu()函数初始化了BSP的TSS和TSS描述符，修改这部分代码，使之支持所有cpu。提示：新代码将不会使用到全局变量ts。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void
trap_init_percpu(void)
{ 
	// ltr sets a 'busy' flag in the TSS selector, so if you
	// accidentally load the same TSS on more than one CPU, you'll
	// get a triple fault.  If you set up an individual CPU's TSS
	// wrong, you may not get a fault until you try to return from
	// user space on that CPU.
	//
	// LAB 4: Your code here:

	// Setup a TSS so that we get the right stack
	// when we trap to the kernel.
	//ts.ts_esp0 = KSTACKTOP;
	//ts.ts_ss0 = GD_KD;
	thiscpu->cpu_ts.ts_esp0 = (uintptr_t) percpu_kstacks[thiscpu->cpu_id] + KSTKSIZE;
	thiscpu->cpu_ts.ts_ss0 = GD_KD;

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

	// Load the TSS selector (like other segment selectors, the
	// bottom three bits are special; we leave them 0)
	//ltr(GD_TSS0);  
        //ltr(((GD_TSS0 >> 3) + thiscpu->cpu_id) << 3); 
	ltr(GD_TSS0 + (thiscpu->cpu_id << 3)); 

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

多处理器总结要点

jos支持多处理器之后，大概的启动过程如下：
1、BSP调用mem_init()函数，主要完成创建页目录、pages数组、envs数组、映射pages数组/envs数组/BSP内核栈等到页目录中。
2、BSP调用env_init()函数，初始化envs数组；同时调用env_init_percpu()函数加载当前cpu的GDT和gs/fs/es/ds/ss段描述符。
3、BSP调用trap_init()函数，初始化IDT表；同时调用trap_init_percpu()函数初始化当前cpu的TSS和IDT。
4、BSP调用mp_init()函数，mp_init()函数通过调用mpconfig()从BIOS中读取浮动指针mp，从mp中找到struct mpconf多处理器配置表，然后根据这个结构体内的entries信息（processor table entry）对各个cpu结构体进行配置（主要是cpuid）。如果proc->flag是MPPROC_BOOT，说明这个入口对应的处理器是用于启动的处理器，我们把结构体数组cpus[ncpu]地址赋值给bootcpu指针。注意这里ncpu是个全局变量，那么这里实质上就是把cpus数组的第一个元素的地址给了bootcpu。如果出现任何entries匹配错误，则认为处理器的初始化失败了，不能用多核处理器进行机器的运行。
5、BSP调用lapic_init()函数，映射lapic物理地址到页目录（映射的虚拟地址递增），设置时钟，允许APIC接收中断。
6、BSP调用pic_init()函数，初始化8259A中断控制器，允许生成中断。
7、BSP调用boot_aps()函数，复制cpu启动代码到0x7000，然后对每个cpu分别确定内核栈地址后调用lapic_startap()函数。lapic_startap()函数命令对应cpu从加载代码处开始执行。BSP使用轮询等待目标cpu启动完成（目标cpu使用自旋锁通知），然后激活下一个cpu。
8、AP（cpu）从加载代码处启动，加载gdt表、手动设置初始页表、开启保护模式、分页等，然后跳转到mp_main()函数；mp_main()函数直接切换到页目录，然后调用lapic_init()函数映射lapic物理地址到页目录（映射的虚拟地址递增），并允许APIC接收中断；调用env_init_percpu()函数加载当前cpu的GDT和gs/fs/es/ds/ss段描述符；调用trap_init_percpu()函数初始化当前cpu的TSS和IDT，然后使用自旋锁设置启动完成标识，并调用sched_yield()函数尝试开始执行可执行进程。
9、BSP上自行创建进程，并调用sched_yield()函数尝试开始执行可执行进程。

需要注意到：每个cpu都有自己独立的寄存器和CPU栈、TSS，但是整个内核中只有一份envs数组、pages数组、内核页目录、idt、gdt、lapic物理地址。

1
问题是：lapic物理地址只有一个，每次启动cpu的过程中是怎么改变lapic的呢？还有cpunum()的实现方式不明白。。。。。。
1
???

Locking

启动APs之后，我们需要解决多处理器并发执行内核代码的竞争条件。实现这一点的最简单的方法是使用一个内核锁，该内核锁是一个全局锁，一旦某个进程进入内核模式则尝试获取该锁，当进程返回到用户模式时释放该锁。在这个模型中，在用户模式下的进程可以并发在任何可用cpu上运行，但至多一个进程可以运行在内核模式下，其他试图进入内核模式的进程被迫等待。
kern/spinlock.h定义了内核锁kernel_lock，并提供lock_kernel()和unlock_kernel()方法用于获取和释放锁。需要在以下四个地方设置内核锁：
1、i386_init()：在BSP激活其他cpu之前获取内核锁。
2、mp_main()：初始化AP之后获取内核锁，然后调用sched_yield()在该AP上运行进程。
3、trap()：如果是由用户模式trap到内核的，获取内核锁。通过tf_cs的低两位判断是用户模式还是内核模式。
4、env_run()：在切换为用户模式之前释放内核锁。

1
Exercise 5: 完成以上任务。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
i386_init():
	// Acquire the big kernel lock before waking up APs
	// Your code here:
	lock_kernel();
	// Starting non-boot CPUs
	boot_aps(); 

mp_main():
	// Now that we have finished some basic setup, call sched_yield()
	// to start running processes on this CPU.  But make sure that
	// only one CPU can enter the scheduler at a time!
	//
	// Your code here: 
	lock_kernel();
	sched_yield(); 

trap():
        if ((tf->tf_cs & 3) == 3) {
		// Trapped from user mode.
		// Acquire the big kernel lock before doing any
		// serious kernel work.
		// LAB 4: Your code here.
		lock_kernel();
		assert(curenv);

env_run():
	lcr3(PADDR(e->env_pgdir)); 
	//lab4
	unlock_kernel(); 
	env_pop_tf(&(e->env_tf));//never return

在sched_yield()中实现循环调度时会调用env_run()函数，进而释放内核锁。经过上述加锁、释放锁操作后，只有当BSP激活所有APs并且开始调用sched_yield()运行用户程序时，其他CPU才可能开始执行用户程序。

1
Question 2. 使用内核锁可以保证一次只有一个CPU可以运行内核代码。那么，为何还需要将每个cpu的CPU栈分开？请描述一个使用了内核锁和共享内核栈后出错的场景。

如果使用共享的内核栈的话，当出现中断时，硬件会先自动将相关寄存器进栈，然后才执行锁的检查，共享内核栈可能会导致系统崩溃。
支持多个cpu的时候，只有一份内核页目录，所有cpu都会使用这个页目录映射CPU栈。不同的CPU栈映射到不同的虚拟地址上。
在此需要注意的是另一个现象：不同的用户进程是可以同时将用户栈物理地址映射到UXSTACKTOP上的。这是因为每一个用户进程都有一份独立的页目录，创建用户进程的时候会分配和映射一页用户栈物理页到UXSTACKTOP上，多个cpu同时运行多个用户进程的时候，实际上都是使用各自的页目录进行寻址和存储数据到各自的用户栈物理页上的。 

1
2
3
4
5
6
Challenge: 内核锁易于使用，但它消除了内核模式下的所有并发。大多数现代操作系统使用不同的锁来保护共享状态的不同部分，使用的方法称为细粒度锁（fine-grained locking）。细粒度锁可以显著提高性能，但更难以实现且容易出错。
若要在jos实现细粒度锁，可以自由决定锁的粒度（即每个锁保护的数据量大小）。可以使用自旋锁来实现互斥访问以下jos内容：
The page allocator：页分配器
The console driver：控制台驱动
The scheduler：调度器
The inter-process communication (IPC) state：进程间通信状态，将在part C实现。

Round-Robin Scheduling

此部分内容将修改jos内核使之可以以循环机制（round-robin）交替调度多个进程。jos的循环机制如下：
1、kern/sched.c的sched_yield()函数负责选择一个新的进程来执行。它从上一个运行进程之后开始，以循环方式顺序搜索envs[]数组，选择第一个状态为ENV_RUNNABLE的进程，并调用env_run()函数跳转到该进程。
2、sched_yield()不能同时在两个cpu上执行调度同一个进程。区分某个进程是否正在某个cpu上运行的方法是：该进程的状态是ENV_RUNNING。
3、用户进程可以调用sys_yield()系统调用（该函数调用sched_yield()函数），自愿放弃cpu资源给其他进程。

1
2
3
Exercise 6. 在sched_yield()中实现循环调度。在syscall()中分发sys_yield()。确保在mp_main()中调用sched_yield()。在kern/init.c中创建三个或三个以上进程，执行user/yield.c。在yield程序退出之后，系统将不存在可执行进程，并陷入到monitor中。
如果CPUS=1，所有进程将会成功执行。
如果CPUS>1，一旦没有更多可运行环境，由于未处理的定时器中断可能导致一般性保护异常或内核页错误。后面将解决该问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void
sched_yield(void)
{
	struct Env *idle;
		 
	// Implement simple round-robin scheduling.
	//
	// Search through 'envs' for an ENV_RUNNABLE environment in
	// circular fashion starting just after the env this CPU was
	// last running.  Switch to the first such environment found.
	//
	// If no envs are runnable, but the environment previously
	// running on this CPU is still ENV_RUNNING, it's okay to
	// choose that environment.
	//
	// Never choose an environment that's currently running on
	// another CPU (env_status == ENV_RUNNING). If there are
	// no runnable environments, simply drop through to the code
	// below to halt the cpu.

	// LAB 4: Your code here. 
	int i;
	int current_env_idx = curenv ? ENVX(curenv->env_id) : 0;
	int idx = curenv ? (current_env_idx + 1) % NENV : 0; // start by looking at the next process
 
	for (i = 0; i < NENV; i++) {
		if (envs[idx].env_status == ENV_RUNNABLE)
			env_run(&envs[idx]);
		idx = (idx + 1) % NENV;
	} 
	if (curenv != NULL && curenv->env_status == ENV_RUNNING)
		env_run(curenv);
  
	// sched_halt never returns
	sched_halt();
}
1
Question 3.env_run()修改了参数e的成员状态之后就会调用lcr3切换到进程的页目录，这时候内存管理单元MMU所使用的寻址上下文立即发生了变化。在地址切换前后，为什么参数e仍能够被引用？

因为对于所有env来说，内核空间的虚拟地址是相同的，这部分地址也被映射进env的页目录。参数e本身也是内核空间的一部分。

1
Question 4.每次内核从一个进程切换到另一个进程的时候，需要保存旧进程的寄存器以便后面恢复，怎么做？什么时候这样做？

由内核模式进入trap()函数时，只管调用trap_dispatch()就行，就算调用之后会执行新的env，也不涉及旧env寄存器存储的问题。但如果是由用户模式进入trap()函数时（trapframe上的cs表明是否来自于用户模式），可能会导致进程切换，因此在调用trap_dispatch()之前需要保存旧env的寄存器。具体做法是：curenv->env_tf = *tf;。之后如果切换到另一个进程，则会调用env_run()函数，并更新curenv变量。为什么这样子就可以保存呢？看一下变量的定义：1、#define curenv (thiscpu->cpu_env)，2、#define thiscpu (&cpus[cpunum()])、3、thiscpu的cpu_env定义是：struct Env *cpu_env;。由上可知，cpu_env是一个指针，始终指向envs数组的一员，而它的更新时机在于调用env_run()函数的时候，实际上就是更新当前cpu执行的进程env。所以在trap()函数中通过执行curenv->env_tf = *tf;就可以将旧进程保存在栈上的trapframe值复制到cpu_env所指向envs数组的一员上，下次若调用到该进程，又可以恢复寄存器环境了。

1
Challenge! 将调度方式扩展为固定优先级调度，优先级高的进程将先于优先级低的进程被调度。编写测试程序测试调用顺序是正确的。

扩展Env数据结构，添加优先级变量，然后修改调度函数，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// Choose a user environment to run and run it.
void
sched_yield(void)
{
	struct Env *idle;
		 
	// Implement simple round-robin scheduling.
	//
	// Search through 'envs' for an ENV_RUNNABLE environment in
	// circular fashion starting just after the env this CPU was
	// last running.  Switch to the first such environment found.
	//
	// If no envs are runnable, but the environment previously
	// running on this CPU is still ENV_RUNNING, it's okay to
	// choose that environment.
	//
	// Never choose an environment that's currently running on
	// another CPU (env_status == ENV_RUNNING). If there are
	// no runnable environments, simply drop through to the code
	// below to halt the cpu.
	// LAB 4: Your code here.  
  	// use priority, lab4 challenge
	enum EnvPriority priority;
	int i = 0;;
	int current_env_idx = curenv ? ENVX(curenv->env_id) : 0;
	int idx = curenv ? (current_env_idx + 1) % NENV : 0; // start by looking at the next process
 	for (priority = ENV_PRIORITY_HIGH; priority <= ENV_PRIORITY_LOW; priority++) { 
		for (i = 0; i < NENV; i++) {
			if (envs[idx].env_status == ENV_RUNNABLE && envs[idx].priority == priority){ 
				if (curenv != NULL && curenv->env_status == ENV_RUNNING && curenv->priority < envs[idx].priority){ 
					env_run(curenv);
				}else{
					env_run(&envs[idx]);
				}
			}
			idx = (idx + 1) % NENV;
		} 
 	}
	if (curenv != NULL && curenv->env_status == ENV_RUNNING){ 
		env_run(curenv);
	}

	// sched_halt never returns
	sched_halt();
}

测试程序为user/envpriority.c，注意需要在kern/Makefrag中添加KERN_BINFILES += user/envpriority。测试程序使用到下面添加的系统调用，整体思路是由当前root进程fork多个子进程，每次fork之后设置子进程的优先级，然后调用sys_yield()系统调用放弃cpu，观察内核调度进程结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// test env priority

#include <inc/string.h>
#include <inc/lib.h>

envid_t dumbfork_priority(uint32_t priority);

void
umain(int argc, char **argv)
{
	envid_t who,root;
	int i,p;
	root = sys_getenvid();
	for (p = 1; p <= 5; ++p) {
		// fork a child process
		if(root == sys_getenvid()){
        	who = dumbfork_priority(p); 

			// print a message and yield to the other a few times
			for (i = 0; i < 3; i++) {
				cprintf("%d: I am the %s! my env priority is %d\n", i, who ? "parent" : "child", sys_env_get_priority());
				sys_yield();
			}
		} 
    }
}

void
duppage(envid_t dstenv, void *addr)
{
	int r;

	// This is NOT what you should do in your fork.
	//alloc a page mapping at child's addr
	if ((r = sys_page_alloc(dstenv, addr, PTE_P|PTE_U|PTE_W)) < 0)
		panic("sys_page_alloc: %e", r);
	//map child's new page(mapping at addr) at parent's UTEMP
	if ((r = sys_page_map(dstenv, addr, 0, UTEMP, PTE_P|PTE_U|PTE_W)) < 0)
		panic("sys_page_map: %e", r);
	//copy page data mapping at parent's addr to page mapping at parent's UTEMP
	//as a result, it fills in child's page
	memmove(UTEMP, addr, PGSIZE);
	if ((r = sys_page_unmap(0, UTEMP)) < 0)
		panic("sys_page_unmap: %e", r);
}

envid_t
dumbfork_priority(uint32_t priority)
{
	envid_t envid;
	uint8_t *addr;
	int r;
	extern unsigned char end[];

	// Allocate a new child environment.
	// The kernel will initialize it with a copy of our register state,
	// so that the child will appear to have called sys_exofork() too -
	// except that in the child, this "fake" call to sys_exofork()
	// will return 0 instead of the envid of the child.
	envid = sys_exofork();
	if (envid < 0)
		panic("sys_exofork: %e", envid);
	if (envid == 0) {
		// We're the child.
		// The copied value of the global variable 'thisenv'
		// is no longer valid (it refers to the parent!).
		// Fix it and return 0.
		thisenv = &envs[ENVX(sys_getenvid())];
		return 0;
	}


	// We're the parent.
	//set child's prioroty
	sys_env_set_priority(envid,priority);
	// Eagerly copy our entire address space into the child.
	// This is NOT what you should do in your fork implementation.
	for (addr = (uint8_t*) UTEXT; addr < end; addr += PGSIZE)
		duppage(envid, addr);

	// Also copy the stack we are currently running on.
	duppage(envid, ROUNDDOWN((void*)USTACKTOP - PGSIZE, PGSIZE)); 
	// Start the child environment running
	if ((r = sys_env_set_status(envid, ENV_RUNNABLE)) < 0)
		panic("sys_env_set_status: %e", r);

	return envid;
}

运行结果：

1
Challenge! jos当前不支持应用使用x86处理器的x87 floating-point单元(FPU)、MMX指令或Streaming SIMD Extensions(SSE)。扩展Env数据结构，添加浮点状态成员（floating point state），并在进程切换代码中保存和恢复浮点状态。可使用FXSAVE和FXRSTOR指令，它们在最近的处理器才被介绍，在旧的i386用户手册中没有介绍。
1
???

System Calls for Environment Creation

sys_exofork：创建一个进程，创建页目录（映射内核空间，UTOP以下部分在页目录中的映射为空）、填充trapframe（包括env_alloc()中用户栈指针指向e->env_tf.tf_esp = USTACKTOP;，请注意，子进程只有将esp指向USTACKTOP，并没有再次为栈分配空间，而根父进程的栈空间是在env_create()的时候通过调用env_alloc()之后调用load_icode()实现的）、复制父进程的trapframe…，没有用户程序地址映射到地址空间、状态为不可执行。新进程的寄存器状态与调用sys_exofork的进程一样。调用sys_exofork的父进程返回子进程id，子进程返回0（具体原因可参考x86的fork实现）。
sys_env_set_status：设置进程状态为ENV_RUNNABLE或ENV_NOT_RUNNABLE，通常是进程的地址映射和寄存器状态设置完毕之后设置进程可被执行。
sys_page_alloc：分配一页物理页，并在指定进程的地址空间上映射到给定的虚拟地址。
sys_page_map：将A进程中映射到虚拟地址va_a的物理页映射到B进程的虚拟地址va_b，设置给出的权限。从而两个进程可以以不同的权限访问同一个物理页。
sys_page_unmap：在指定进程的地址空间上解除给定的虚拟地址上的映射。 

1
Exercise 7.完成以上内容。jos的envid2env()函数可以根据id获取对应的进程结构，并且传入0可以获取当前进程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Allocate a new environment.
// Returns envid of new environment, or < 0 on error.  Errors are:
//	-E_NO_FREE_ENV if no free environment is available.
//	-E_NO_MEM on memory exhaustion.
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.
	//panic("sys_exofork not implemented");
	struct Env *newEnv; 
	//set kernal stack, page dir, trapframe...
	int r = env_alloc(&newEnv,curenv->env_id);
	if(r<0) return r;
	newEnv->env_status = ENV_NOT_RUNNABLE; 
	newEnv->env_tf = curenv->env_tf; 
	//or : memmove((void *) &newEnv->env_tf, (void *) &curenv->env_tf, sizeof(struct Trapframe));
	//clear child's eax,so it will return pid 0
	newEnv->env_tf.tf_regs.reg_eax = 0;
	return newEnv->env_id;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Set envid's env_status to status, which must be ENV_RUNNABLE
// or ENV_NOT_RUNNABLE.
//
// Returns 0 on success, < 0 on error.  Errors are:
//	-E_BAD_ENV if environment envid doesn't currently exist,
//		or the caller doesn't have permission to change envid.
//	-E_INVAL if status is not a valid status for an environment.
static int
sys_env_set_status(envid_t envid, int status)
{
	// Hint: You should set envid2env's third argument to 1, which will
	// check whether the current environment has permission to set
	// envid's status.

	// LAB 4: Your code here.
	//panic("sys_env_set_status not implemented");
	struct Env *e; 
	// check whether the current environment has permission to set envid's status. 
	// i.e.,the specified environment must be either the
	// current environment or an immediate child of the current environment.
	int r = envid2env(envid,&e,true);
	if(r<0) return r;//-E_BAD_ENV 
	if(status != ENV_RUNNABLE && status != ENV_NOT_RUNNABLE) return -E_INVAL;
	e->env_status = status;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// Allocate a page of memory and map it at 'va' with permission
// 'perm' in the address space of 'envid'.
// The page's contents are set to 0.
// If a page is already mapped at 'va', that page is unmapped as a
// side effect.
//
// perm -- PTE_U | PTE_P must be set, PTE_AVAIL | PTE_W may or may not be set,
//         but no other bits may be set.  See PTE_SYSCALL in inc/mmu.h.
//
// Return 0 on success, < 0 on error.  Errors are:
//	-E_BAD_ENV if environment envid doesn't currently exist,
//		or the caller doesn't have permission to change envid.
//	-E_INVAL if va >= UTOP, or va is not page-aligned.
//	-E_INVAL if perm is inappropriate (see above).
//	-E_NO_MEM if there's no memory to allocate the new page,
//		or to allocate any necessary page tables.
static int
sys_page_alloc(envid_t envid, void *va, int perm)
{ 
	// LAB 4: Your code here.
	//panic("sys_page_alloc not implemented");
	struct Env *e; 
	// check whether the current environment has permission to change envid. 
	// i.e.,the specified environment must be either the
	// current environment or an immediate child of the current environment.
	int r = envid2env(envid,&e,true); 
	if(r<0) return r;//-E_BAD_ENV 
	
	if((uint32_t)va >= UTOP || (uint32_t)va%PGSIZE != 0) return -E_INVAL;
	
	if((perm & PTE_U) != PTE_U || (perm & PTE_P) != PTE_P) return -E_INVAL;
	//#define PTE_SYSCALL	(PTE_AVAIL | PTE_P | PTE_W | PTE_U)
	if ((perm & ~PTE_SYSCALL) != 0) //no other bits may be set
		return -E_INVAL;

	struct PageInfo *page = page_alloc(ALLOC_ZERO);
	if(page == NULL) return -E_NO_MEM;
	
	//store page's mapping physical address and perm in va's mapping page table entry
	r = page_insert(e->env_pgdir, page, va, perm);
	if(r<0) {
		page_remove(e->env_pgdir,va);
		return r;//-E_NO_MEM
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// Map the page of memory at 'srcva' in srcenvid's address space
// at 'dstva' in dstenvid's address space with permission 'perm'.
// Perm has the same restrictions as in sys_page_alloc, except
// that it also must not grant write access to a read-only
// page.
//
// Return 0 on success, < 0 on error.  Errors are:
//	-E_BAD_ENV if srcenvid and/or dstenvid doesn't currently exist,
//		or the caller doesn't have permission to change one of them.
//	-E_INVAL if srcva >= UTOP or srcva is not page-aligned,
//		or dstva >= UTOP or dstva is not page-aligned.
//	-E_INVAL is srcva is not mapped in srcenvid's address space.
//	-E_INVAL if perm is inappropriate (see sys_page_alloc).
//	-E_INVAL if (perm & PTE_W), but srcva is read-only in srcenvid's
//		address space.
//	-E_NO_MEM if there's no memory to allocate any necessary page tables.
static int
sys_page_map(envid_t srcenvid, void *srcva,
	     envid_t dstenvid, void *dstva, int perm)
{ 
	// LAB 4: Your code here.
	//panic("sys_page_map not implemented");
	struct Env *srce,*dste; 
	// check whether the current environment has permission to change envid. 
	// i.e.,the specified environment must be either the
	// current environment or an immediate child of the current environment.
	int r = envid2env(srcenvid,&srce,true);
	if(r<0) return r;//-E_BAD_ENV 
	r = envid2env(dstenvid,&dste,true);//envid 0 means "the current environment."
	if(r<0) return r;//-E_BAD_ENV 
	
	if((uint32_t)srcva >= UTOP || (uint32_t)srcva%PGSIZE != 0) return -E_INVAL;
	if((uint32_t)dstva >= UTOP || (uint32_t)dstva%PGSIZE != 0) return -E_INVAL;
	
	//return the page mapped at virtual address 'va'
	//pte_store stores the address of the page table entry for this page
	pte_t *pte_store;
	struct PageInfo *page = page_lookup(srce->env_pgdir, srcva, &pte_store);
	if(page == NULL) return -E_INVAL;//no page mapped at srcva

	if((perm & PTE_U) != PTE_U || (perm & PTE_P) != PTE_P) return -E_INVAL;
	//#define PTE_SYSCALL	(PTE_AVAIL | PTE_P | PTE_W | PTE_U)
	if ((perm & ~PTE_SYSCALL) != 0) //no other bits may be set
		return -E_INVAL;
	
	if((*pte_store & PTE_W) != PTE_W && ((perm & PTE_W) == PTE_W)) return -E_INVAL;//srcva is read-only but perm is writable

	//store page's mapping physical address and perm in dstva's mapping page table entry
	r = page_insert(dste->env_pgdir, page, dstva, perm);// allow to create page table
	if(r<0) {
		page_remove(dste->env_pgdir,dstva);
		return r;//-E_NO_MEM
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Unmap the page of memory at 'va' in the address space of 'envid'.
// If no page is mapped, the function silently succeeds.
//
// Return 0 on success, < 0 on error.  Errors are:
//	-E_BAD_ENV if environment envid doesn't currently exist,
//		or the caller doesn't have permission to change envid.
//	-E_INVAL if va >= UTOP, or va is not page-aligned.
static int
sys_page_unmap(envid_t envid, void *va)
{ 
	// LAB 4: Your code here.
	//panic("sys_page_unmap not implemented");
	struct Env *e; 
	// check whether the current environment has permission to change envid. 
	// i.e.,the specified environment must be either the
	// current environment or an immediate child of the current environment.
	int r = envid2env(envid,&e,true);
	if(r<0) return r;//-E_BAD_ENV 
	
	if((uint32_t)va >= UTOP || (uint32_t)va%PGSIZE != 0) return -E_INVAL;
	
	page_remove(e->env_pgdir,va);
	return 0;
}
1
Challenge! 添加系统调用以读取某个进程的所有重要状态。实现一个用户程序，该程序fork一个子进程，运行该程序（即循环迭代sys_yield()），然后获取子进程的完整snapshot或checkpoint，然后执行子程序一段时间。最后，恢复子进程在检查点的状态，然后继续执行子进程。这相当于从某个中间状态replaying子进程的执行。使用sys_cgetc()或readline()函数保证子进程与用户之间进行交互，以便用户可以查看和改变其内部状态。确保子进程在检查点处恢复执行时，子进程"forget"了之前任何发生在检查点之后的内容。
1
???

Part B: Copy-on-Write Fork

xv6实现的fork()将父进程所有物理页的内容拷贝给了分配给子进程的新物理页，类似于jos的dumbfork()函数。fork()过程中最“昂贵”的操作就是将父进程的地址空间拷贝给子进程。然而在子进程中，通常是紧接着就执行exec()，以新程序替代子进程执行。在这种情况下，父进程拷贝地址空间给子进程所花时间将被大大浪费了，因为子进程在执行exec()之前只使用了一小部分内存。鉴于此，更新版本的unix利用虚拟内存硬件允许父子进程共享分别映射到它们各自地址空间的物理内存，直至其中一方修改物理内存，这种技术称为“写时复制”。fork()将父进程地址空间的映射情况复制到子进程中，而不是复制父进程映射的物理页内容，并将共享的物理页标记为“只读”。当父子进程其中一方尝试写入到任一页共享的内存页，该进程将触发页错误。在这种情况下，内核识别出该页是“写时复制”副本，并为触发页错误的进程创建新的私有的可写入页。

User-level page fault handling

将Copy-on-Write Fork实现为一个用户空间库例程有以下优点：1、内核更为简单，更为正确；2、允许用户进程定义fork()的语义，用户程序可以很容易地提供一个稍有不同的实现版本，例如dumbfork()这种昂贵的always-copy版本，或者父子进程共享内存的版本。用户级别的Copy-on-Write Fork需要能够识别出在写保护页上触发的页错误。

典型的unix内核需要知道在进程地址空间的每一个区域上触发页错误时应该采取什么方法，例如：栈空间触发页错误时应该分配和映射新的物理页，在大多数unix内核中，一开始只给新进程分配一页的栈空间，用户程序在栈空间不足的情况下访问未映射的栈地址会触发页错误，从而导致内核分配并映射新物理页到栈空间；BSS空间触发页错误时应该分配新的一页、填充0并映射到地址空间；如果系统支持按需分配物理页的可执行文件，text region触发页错误时将从磁盘读取相应二进制页并映射到地址空间。

上述情况中内核需要跟踪许多信息。我们不采取传统的unix方法，而是在用户空间中决定对每个页错误所采取的行动。这种设计的好处是用户程序在定义内存区域时有极大的灵活性，我们将在后续使用用户级页错误处理程序来映射和访问基于硬盘的文件系统上的文件。

Setting the Page Fault Handler

1
Exercise 8. 实现sys_env_set_pgfault_upcall系统调用，该系统调用用于注册用户程序触发页错误时的处理函数入口。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Set the page fault upcall for 'envid' by modifying the corresponding struct
// Env's 'env_pgfault_upcall' field.  When 'envid' causes a page fault, the
// kernel will push a fault record onto the exception stack, then branch to
// 'func'.
//
// Returns 0 on success, < 0 on error.  Errors are:
//	-E_BAD_ENV if environment envid doesn't currently exist,
//		or the caller doesn't have permission to change envid.
static int
sys_env_set_pgfault_upcall(envid_t envid, void *func)
{
	// LAB 4: Your code here.
	//panic("sys_env_set_pgfault_upcall not implemented"); 
	struct Env *e; 
	// check whether the current environment has permission to change envid. 
	// i.e.,the specified environment must be either the
	// current environment or an immediate child of the current environment.
	int r = envid2env(envid,&e,true);
	if(r<0) return r;//-E_BAD_ENV 
	e->env_pgfault_upcall = func;
	return 0;
}

Normal and Exception Stacks in User Environments

jos正常执行进程过程中，用户进程所使用的用户栈是[USTACKTOP-PGSIZE,USTACKTOP-1]。然而，当用户程序触发页错误时，内核将在另一个栈[UXSTACKTOP-PGSIZE,UXSTACKTOP-1]上执行设计好的页错误处理函数，这个栈称为user exception stack。类似于x86为jos设计的由用户模式切换到内核模式时的栈切换，我们将在jos内核为用户程序设计自动栈切换。
当执行用户设计的页错误处理函数时，可以根据页错误原因使用jos的系统调用来映射新物理页或调整映射情况。之后页错误处理函数返回，通过汇编语言返回到原先触发页错误的代码。
每一个需要使用用户级别页错误处理流程的用户程序需要自行为user exception stack申请内存空间。

Invoking the User Page Fault Handler

用户程序触发页错误时，用户进程的状态称为“the trap-time state”。如果没有注册页错误处理程序，内核将销毁进程。否则，内核在异常栈上设置struct UTrapframe（见inc/trap.h），UTrapframe的值主要来源于内核栈的trap frame。之后，内核安排用户级页错误处理程序在异常栈上执行。
如果发生页错误的时候用户进程已经在异常栈上执行（tf->tf_esp在[UXSTACKTOP-PGSIZE, UXSTACKTOP-1]内），说明页错误处理程序本身触发了页错误。这种时候应该在tf->tf_esp而不是UXSTACKTOP的以下部分存储UTrapframe，而且需要先留空4个字节，再存储UTrapframe，具体原因下面讲。

1
Exercise 9. 完成kern/trap.c的page_fault_handler函数，该函数主要负责处理页错误，如果触发页错误的是用户进程，则检查页错误处理程序是否已设置、页错误处理程序地址是否合法、异常栈指针是否越界、是否递归触发页错误、是否已为异常栈分配物理页，然后在异常栈上存储UTrapframe，将栈指针指向异常栈，并跳转执行用户级页错误处理程序入口。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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("Kernel page fault!");
    // We've already handled kernel-mode exceptions, so if we get here,
    // the page fault happened in user mode.
 
    // LAB 4: Your code here. 
    //1. test if has page fault upcall
    if (curenv->env_pgfault_upcall == NULL ||
        //2. test if the exception stack overflows
        tf->tf_esp > UXSTACKTOP || (tf->tf_esp > USTACKTOP && tf->tf_esp < (UXSTACKTOP - PGSIZE))){
        // Destroy the environment that caused the fault.
        cprintf("[%08x] user fault va %08x ip %08x\n",
            curenv->env_id, fault_va, tf->tf_eip);
        print_trapframe(tf);
        env_destroy(curenv);
    }

    // 1. test if page fault upcall valid
    user_mem_assert(curenv, (void *)curenv->env_pgfault_upcall, 1, 0);
	
    //determine user exception stack pointer
    uint32_t exception_stack_top = 0;
    if(tf->tf_esp <= USTACKTOP){
        exception_stack_top = UXSTACKTOP - sizeof(struct UTrapframe);
    }else{
        //+4 : leave an extra word between the current top of the exception stack
        exception_stack_top = tf->tf_esp - sizeof(struct UTrapframe) - 4;
    }

    //2. test if the exception stack overflows
    if(exception_stack_top < (UXSTACKTOP - PGSIZE)){
        // Destroy the environment that caused the fault.
        cprintf("[%08x] user fault va %08x ip %08x\n",
            curenv->env_id, fault_va, tf->tf_eip);
        print_trapframe(tf);
        env_destroy(curenv);
    }

    //3. test if allocate a page for its exception stack or if can write to it
    user_mem_assert(curenv, (void *) exception_stack_top, 1, PTE_W | PTE_U);//1 is enough, may not return
	 
    //write UTrapframe in the stack
    struct UTrapframe* utf = (struct UTrapframe*)exception_stack_top;
    utf->utf_fault_va = fault_va;
    utf->utf_err = tf->tf_err;
    utf->utf_regs = tf->tf_regs;
    utf->utf_eip = tf->tf_eip;
    utf->utf_eflags = tf->tf_eflags;
    utf->utf_esp = tf->tf_esp;

    //branch to curenv->env_pgfault_upcall, that means we should change trapframe's esp and eip
    tf->tf_esp = (uintptr_t) exception_stack_top;
    tf->tf_eip = (uintptr_t) curenv->env_pgfault_upcall;
    env_run(curenv);
}

User-mode Page Fault Entrypoint

xv6的定时函数是在内核trap时将esp所指单元向下移动一个单元，然后存储tf的eip（触发中断的下一条指令），然后将tf的eip指向处理函数，然后弹出tf寄存器执行定时函数，定时函数返回时弹出trap设置的eip，进而执行用户函数。这种情况下esp仍然指向用户栈。
jos的用户级页错误处理程序入口是_pgfault_upcall，包括调用执行真正的处理程序和恢复执行用户函数。_pgfault_upcall将通过系统调用设置为页错误处理程序入口，内核trap时将tf的相关值复制到异常栈上，将tf的esp指向异常栈，然后弹出tf寄存器执行页错误处理程序入口。这种情况下执行处理函数的时候esp指向的是异常栈，设置异常栈可以方便传递参数。
用户级页错误处理程序执行完后，将返回执行原先触发页错误的用户代码（如果是页错误处理程序触发页错误，则应返回执行原先触发页错误的页错误处理程序）。lib/pfentry.S完成这个任务。

1
Exercise 10. 完成lib/pfentry.S。触发页错误时内核实际上是跳转执行该文件声明的入口_pgfault_upcall。pfentry.S主要是在用户态的page_fault_handler结束后如何恢复现场并跳回原程序执行。

内核在异常栈上存储UTrapframe之后安排用户级页错误处理程序在异常栈上执行。异常栈上的UTrapframe布局如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
                    <-- UXSTACKTOP or tf->tf_esp
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 oesp
trap-time ebp
trap-time esi
trap-time edi       end of struct PushRegs
tf_err (error code)
fault_va            <-- %esp when handler is run

分两种情况分析：
1、非递归触发页错误。由于此时是在异常栈上，想要恢复执行触发页错误的用户代码时，需要弹出通用寄存器，并由异常栈跳转到用户栈，最后执行ret恢复执行。因此，关键点是如何在弹出通用寄存器和eflags之前将eip存储到用户栈上。需要借助通用寄存器存储PushRegs的位置和eip的值，再跳到用户栈，存储eip，然后再跳回PushRegs位置，弹出通用寄存器和eflags，最后跳回用户栈执行ret（实验发现最后跳回用户栈之后，此时已经存了eip，如果执行subl向下跳到存eip的位置会改变eflags，因此在跳到用户栈存储eip之后，将最新的esp位置存到异常栈上，最后由异常栈直接跳到用户栈执行ret）。
2、递归触发页错误。与情况1不同的是，“用户栈”其实就是异常栈本身。因此，在跳到“用户栈”存储eip的时候，由于弹出的trap-time esp值恰好就是存储trap-time esp所在的位置（trap的时候esp指向异常栈该位置，然后跳到内核栈，内核再从异常栈该位置开始存储UTrapframe），存储eip会将trap-time esp覆盖，从而导致最后不能成功再跳回用户栈。这就是为什么如果是递归触发页错误的话，需要先留空4个字节，再存储UTrapframe，主要是为了防止存储eip的时候覆盖了原先的esp值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <inc/mmu.h>
#include <inc/memlayout.h>

// Page fault upcall entrypoint.
 
.text
.globl _pgfault_upcall
_pgfault_upcall:
    // Call the C page fault handler.
    pushl %esp          // function argument: pointer to UTF
    movl _pgfault_handler, %eax
    call *%eax
    addl $4, %esp           // pop function argument
    
    // Now the C page fault handler has returned and you must return
    // to the trap time state.
    // Push trap-time %eip onto the trap-time stack.
    //
    // Explanation:
    //   We must prepare the trap-time stack for our eventual return to
    //   re-execute the instruction that faulted.
    //   Unfortunately, we can't return directly from the exception stack:
    //   We can't call 'jmp', since that requires that we load the address
    //   into a register, and all registers must have their trap-time
    //   values after the return.
    //   We can't call 'ret' from the exception stack either, since if we
    //   did, %esp would have the wrong value.
    //   So instead, we push the trap-time %eip onto the *trap-time* stack!
    //   Below we'll switch to that stack and call 'ret', which will
    //   restore %eip to its pre-fault value.
    //
    //   In the case of a recursive fault on the exception stack,
    //   note that the word we're pushing now will fit in the
    //   blank word that the kernel reserved for us.
    //
    // Throughout the remaining code, think carefully about what
    // registers are available for intermediate calculations.  You
    // may find that you have to rearrange your code in non-obvious
    // ways as registers become unavailable as scratch space.
    //
    // LAB 4: Your code here.

    // 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.

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

    // Return to re-execute the instruction that faulted.
    // LAB 4: Your code here.
 
    addl $8, %esp  
    movl %esp,%eax  
    addl $32,%esp  
    popl %ebx  
    addl $4,%esp  
    movl %esp, %ebp 
    popl %esp  
    pushl %ebx  
    movl %esp, 0x0(%ebp) 
    movl %eax,%esp  
    popal  
    addl $4,%esp  
    popf  
    popl %esp  
    ret

//  do not use the following, cause I find that 'subl $4,%esp' will change eflags!

//	addl $8, %esp  
//	movl %esp,%eax  
//	addl $32,%esp  
//	popl %ebx  
//	addl $4,%esp  
//	popl %esp  
//	pushl %ebx  
//	movl %eax,%esp  
//	popal  
//	addl $4,%esp  
//	popf  
//	popl %esp  
//	subl $4,%esp  
//	ret

1
Exercise 11. 完成lib/pgfault.c的set_pgfault_handler()。该函数主要完成页错误处理程序的注册工作。如果是第一次注册，则申请分配并映射异常栈。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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");
		if (sys_page_alloc(sys_getenvid(), (void *)(UXSTACKTOP-PGSIZE), PTE_P|PTE_U|PTE_W) < 0)
			panic("in set_pgfault_handler, sys_page_alloc failed");
		sys_env_set_pgfault_upcall(0, (void*) _pgfault_upcall);
	}

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

综上所述，用户级别的页错误处理流程如下：
1、用户程序通过lib/pgfault.c的set_pgfault_handler()函数注册页错误处理函数入口_pgfault_upcall（见lib/pfentry.S），并指定页错误处理函数_pgfault_handler，该函数指针将在_pgfault_upcall中被使用。第一次注册_pgfault_upcall时将申请分配并映射异常栈。
2、用户程序触发页错误，切换到内核模式。
3、内核检查页错误处理程序是否已设置、异常栈指针是否越界、是否递归触发页错误、是否已为异常栈分配物理页，然后在异常栈上存储UTrapframe，将栈指针指向异常栈，并跳转执行当前进程的env_pgfault_upcall（被设为用户级页错误处理程序入口_pgfault_upcall）。
4、用户模式下_pgfault_upcall调用_pgfault_upcall，执行用户级别页错误处理函数，在用户态的page_fault_handler结束后恢复现场并跳回原程序执行。

Testing

user/faultalloc.c涉及了递归触发页错误。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// test user-level fault handler -- alloc pages to fix faults

#include <inc/lib.h>

void
handler(struct UTrapframe *utf)
{
	int r;
	void *addr = (void*)utf->utf_fault_va;

	cprintf("fault %x\n", addr);
	if ((r = sys_page_alloc(0, ROUNDDOWN(addr, PGSIZE),
				PTE_P|PTE_U|PTE_W)) < 0)
		panic("allocating at %x in page fault handler: %e", addr, r);
	snprintf((char*) addr, 100, "this string was faulted in at %x", addr);
}

void
umain(int argc, char **argv)
{
	set_pgfault_handler(handler);
	cprintf("%s\n", (char*)0xDeadBeef);
	cprintf("%s\n", (char*)0xCafeBffe);
}

首先，snprintf的定义是int snprintf(char *buf, int n, const char *fmt, ...)，向buf缓存区中按照格式填充字符串。
出错的原因是：当执行cprintf("%s\n", (char*)0xCafeBffe);时，触发了页错误。页错误处理函数在虚拟地址ROUNDDOWN(addr, PGSIZE)即cafeb000上分配和映射物理页，此时可访问的虚拟地址空间为[0xcafeb000,0xcafec000-1]。之后，调用snprintf向0xCafeBffe内存地址上填充字符串，由于字符串过长，导致越界访问0xcafec000，再次触发页错误。第二次页错误处理程序往0xcafec000填充字符串，返回到第一次页错误处理程序，第一次页错误处理程序往0xCafeBffe填充字符串，返回到用户程序，执行cprintf进行输出。

1
Challenge! 扩展jos内核，对运行用户程序代码时能触发的所有类型的处理器异常，都能重定向到用户模式的异常处理程序。编写用户模式的测试程序，测试divide-by-zero、general protection fault、illegal opcode等。
1
???

Implementing Copy-on-Write Fork

jos使用Copy-on-Write Fork时，将会扫描父进程的整个地址空间，并设置子进程的相关页映射，但不会复制页内容（dumpfork()复制页内容）。当父/子进程尝试写入某一页时，将申请新的一页并拷贝页内容到该页上。
fork()的基本流程如下：
1、父进程调用set_pgfault_handler()注册页错误处理函数pgfault()。
2、父进程调用sys_exofork()创建子进程。
3、对于[UTEXT,UTOP)每一个可写或写时复制的页，父进程调用duppage分别在子进程和自身的地址空间内映射该页为写时复制PTE_COW。
注意：不能将user exception stack映射为写时复制，而是应该为父子进程分别映射对应的物理页。这是因为页错误处理程序将在user exception stack上执行，当将user exception stack设为写时复制时，一旦发生页错误，内核将尝试往user exception stack写数据，由于user exception stack不可写而导致失败。
4、父进程为子进程注册页错误处理函数。
注意：我们不在子进程中注册页错误处理函数。首先，我们不在子进程中调用set_pgfault_handler()（该函数注册页错误处理函数，并在页错误处理函数未注册的情况下申请user exception stack），因为子进程是由父进程fork而来的，而父进程已经注册过页错误处理函数，所以在子进程中注册页错误处理函数的话子进程不会再申请user exception stack（if (_pgfault_handler == 0)条件判断失败）。其次，我们不在子进程中调用sys_page_alloc()和sys_env_set_pgfault_upcall()申请user exception stack，这是因为这涉及了函数调用，而父进程将子进程的用户栈映射为写时复制了，所以会触发页错误，但是此时还没有分配user exception stack，因此出错。
5、设置子进程状态为runnable。

页错误处理函数的处理流程如下：
1、内核跳转执行_pgfault_upcall，_pgfault_upcall将调用页错误处理函数pgfault()。
2、pgfault()确认fault是可写的（错误码的FEC_WR），并且引起页错误的虚拟地址对应的页表项权限为PTE_COW。
3、pgfault()为申请新的一页，映射到一个临时地址，将faulting page的内容复制到该新页，调用sys_page_map将映射到临时地址的物理页映射到引起页错误的虚拟地址，设置权限为可写。

1
Exercise 12.实现lib/fork.c的fork、duppage、pgfault。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
// PTE_COW marks copy-on-write page table entries.
// It is one of the bits explicitly allocated to user processes (PTE_AVAIL).
#define PTE_COW		0x800
extern void _pgfault_upcall(void);

//
// Custom page fault handler - if faulting page is copy-on-write,
// map in our own private writable copy.
//
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) == 0)
		panic("pgfault: faulting address [%08x] not a write\n", addr);

	if( (uvpd[PDX(addr)] & PTE_P) != PTE_P || 
	    (uvpt[PGNUM(addr)] & PTE_P) != PTE_P || 
	    (uvpt[PGNUM(addr)] & PTE_COW) != PTE_COW){ 
		//cprintf("(uvpt[PTX(addr)] & PTE_P)=%x,PTE_P=%x\n",(uvpt[PGNUM(addr)] & PTE_P),PTE_P);
		panic("not copy-on-write");
	}
	// 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.

	//panic("pgfault not implemented");
	addr = ROUNDDOWN(addr, PGSIZE);
	if ((r = sys_page_alloc(0, PFTEMP, PTE_P|PTE_U|PTE_W)) < 0)
		panic("allocating at %x in page fault handler: %e", addr, r);
	memmove(PFTEMP, addr, PGSIZE);
	//cprintf("in user pgfault,envid = %x\n",thisenv->env_id);
	if ((r = sys_page_map(0, PFTEMP, 0, addr, PTE_P|PTE_U|PTE_W)) < 0)
		panic("sys_page_map: %e", r);
	if ((r = sys_page_unmap(0, PFTEMP)) < 0)
		panic("sys_page_unmap: %e", r);
}

//
// Map our virtual page pn (address pn*PGSIZE) into the target envid
// at the same virtual address.  If the page is writable or copy-on-write,
// the new mapping must be created copy-on-write, and then our mapping must be
// marked copy-on-write as well.  (Exercise: Why do we need to mark ours
// copy-on-write again if it was already copy-on-write at the beginning of
// this function?)
//
// Returns: 0 on success, < 0 on error.
// It is also OK to panic on error.
//
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) == PTE_W || 
	    (uvpt[pn] & PTE_COW) == PTE_COW){ 
 		if ((r = sys_page_map(0, (void *)addr, envid, (void *)addr, PTE_P|PTE_U|PTE_COW)) < 0){
			panic("sys_page_map: %e", r);
 		} 
 		if ((r = sys_page_map(0, (void *)addr, 0, (void *)addr, PTE_P|PTE_U|PTE_COW)) < 0){
			panic("sys_page_map: %e", r);
 		} 
	}else{
		if ((r = sys_page_map(0, (void *)addr, envid, (void *)addr, PTE_P|PTE_U)) < 0){
			panic("sys_page_map: %e", r);
 		}
	}
	return 0;
}

//
// User-level fork with copy-on-write.
// Set up our page fault handler appropriately.
// Create a child.
// Copy our address space and page fault handler setup to the child.
// Then mark the child as runnable and return.
//
// Returns: child's envid to the parent, 0 to the child, < 0 on error.
// It is also OK to panic on error.
//
// Hint:
//   Use uvpd, uvpt, and duppage.
//   Remember to fix "thisenv" in the child process.
//   Neither user exception stack should ever be marked copy-on-write,
//   so you must allocate a new page for the child's user exception stack.
//
envid_t
fork(void)
{
	// LAB 4: Your code here.
	//panic("fork not implemented");
	set_pgfault_handler(pgfault);

	envid_t envid;
	unsigned addr;
	int r;
	extern unsigned char end[]; 

	envid = sys_exofork();
	if (envid < 0)
		panic("sys_exofork: %e", envid);
	if (envid == 0) {
		// We're the child. 
		// DO NOT CALL set_pgfault_handler DIRECTLY! Cause we are forked from parent who has
		// called "set_pgfault_handler", so the variable named "_pgfault_handler" in pgfault.c has been set,
		// and child-env will not call "sys_page_alloc" and "sys_env_set_pgfault_upcall"
		// do not call: set_pgfault_handler(pgfault); 
		
		// DO NOT SET USER EXCEPTION STACK IN CHILD! Cause we set COW on user stack(not user exception stack), so function call
		// like "sys_page_alloc" and "sys_env_set_pgfault_upcall"(which want to stack user excettion stack) 
		// will cause page fault, and kern will use user excettion stack, but it has not been set!!
		// do not call:
	  	// if (sys_page_alloc(0, (void *)(UXSTACKTOP-PGSIZE), PTE_P|PTE_U|PTE_W) < 0)
		//	 panic("in fork, sys_page_alloc failed");
		// if (sys_env_set_pgfault_upcall(0, (void*) _pgfault_upcall) < 0) 
		// 	 panic("in fork, sys_env_set_pgfault_upcall failed");
		//  

		thisenv = &envs[ENVX(sys_getenvid())];
		return 0;
	}

	// We're the parent. 
	// map the page copy-on-write into the address space of the child 
	// and then remap the page copy-on-write in its own address space
	for (addr = UTEXT; addr < (unsigned)end; addr += PGSIZE){
		duppage(envid, PGNUM(addr)); 
	} 
	// map the stack we are currently running on.
	duppage(envid, PGNUM(USTACKTOP - PGSIZE));    
    // also can:
  	/*
	for (addr = 0; addr < USTACKTOP; addr += PGSIZE)
		if ((uvpd[PDX(addr)] & PTE_P) && (uvpt[PGNUM(addr)] & PTE_P)
		    && (uvpt[PGNUM(addr)] & PTE_U)) {
		    duppage(envid, PGNUM(addr)); 
	}
	*/

	if (sys_page_alloc(envid, (void *)(UXSTACKTOP-PGSIZE), PTE_P|PTE_U|PTE_W) < 0)
		panic("in fork, sys_page_alloc failed");
	if (sys_env_set_pgfault_upcall(envid, (void*) _pgfault_upcall) < 0)
		panic("in fork, sys_env_set_pgfault_upcall failed");

	// Start the child environment running
	if ((r = sys_env_set_status(envid, ENV_RUNNABLE)) < 0)
		panic("sys_env_set_status: %e", r);
 
	return envid;
}

关于uvpd和uvpt数组

为了能通过虚拟地址访问到页表和页目录，jos设计了UVPT和UVPD（见Lab3笔记）。一旦设置uvpt数组并指向UVPT，uvpt相当于包含1M个页表项的数组。对于[0, 4G)的线性地址，其在通过地址转换过程中找到的页表项，刚好是以线性地址前20位为索引在uvpt中的项，即uvpt[PGNUM(线性地址)]。对于[UVPT, UVPT+4M)的线性地址，其在uvpt数组中索引到的刚好是页目录这张页表中的项。
一旦设置uvpd数组并指向(UVPT+(UVPT>>12)*4)，则uvpd相当于包含1K个页目录项的数组。

另外，注意到每个进程访问uvpt[]和uvpd[]时，都是彼此独立的。这是因为：如访问uvpt[i]，最终是访问uvpt[i]相关联的UVPT之上的一个虚拟地址，每个进程的页目录和页表都是根据自身情况请求分配页之后的映射结果，如果进程A在该虚拟地址上没有映射页，则uvpt[i]为空，而如果进程B在该虚拟地址上有映射页，则uvpt[i]不为空。

1
Challenge! 完成sfork，使父子进程能共享内存，除了用户栈和用户异常栈。

请注意，sys_exofork创建的子进程页目录只映射了内核空间，我们需要自行映射子进程的地址空间。另一方面，页表项低12位表示权限，但是sys_page_map中不支持设置PTE_AVAIL | PTE_P | PTE_W | PTE_U以外的权限位，因此需要对页表项权限提取进行&处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
int
sfork(void)
{ 
	set_pgfault_handler(pgfault);

	envid_t envid;
	unsigned addr;
	int r;
	extern unsigned char end[]; 

	envid = sys_exofork();
	if (envid < 0)
		panic("sys_exofork: %e", envid);
	if (envid == 0) { 
		thisenv = &envs[ENVX(sys_getenvid())];
		return 0;
	}

	// We're the parent. 
	// share memory
	for (addr = UTEXT; addr < (unsigned)end; addr += PGSIZE){
		// pte's low 12 bits,that means perm,
		// however, in sys_page_map, no other bits may be set except PTE_SYSCALL
		// #define PTE_SYSCALL	(PTE_AVAIL | PTE_P | PTE_W | PTE_U)
		int perm = uvpt[PGNUM(addr)] & PTE_SYSCALL;
		if ((r = sys_page_map(0, (void *)addr, envid, (void *)addr, perm)) < 0){
			panic("sys_page_map: %e", r);
 		} 
	} 
	// map the stack we are currently running on, set copy-on-write.
	duppage(envid, PGNUM(USTACKTOP - PGSIZE));   

	if (sys_page_alloc(envid, (void *)(UXSTACKTOP-PGSIZE), PTE_P|PTE_U|PTE_W) < 0)
		panic("in fork, sys_page_alloc failed");
	if (sys_env_set_pgfault_upcall(envid, (void*) _pgfault_upcall) < 0)
		panic("in fork, sys_env_set_pgfault_upcall failed");

	// Start the child environment running
	if ((r = sys_env_set_status(envid, ENV_RUNNABLE)) < 0)
		panic("sys_env_set_status: %e", r);
 
	return envid; 
}

1
Challenge! fork()使用了大量的系统调用接口。为了降低成本，扩展jos的系统调用接口，使之支持批量调用系统调用，并让fork使用该接口。可参考IA32的RDTSC指令。
1
???

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

Clock Interrupts and Preemption

user/spin程序中子进程一旦获取CPU将永远嵌入循环。为了保证内核能够抢占正在运行的进程，需要扩展内核以支持时钟硬件的外部硬件中断。

Interrupt discipline

外部中断被称为IRQs，共有16个，编号为0-15。IRQs到IDT表项的映射不是固定的，picirq.c的pic_init通过IRQ_OFFSET-IRQ_OFFSET+15将IRQs 0-15映射到IDT项中。在inc/trap.h，IRQ_OFFSET被定义为32，所以IDT的32-47项映射到IRQs 0-15。
在jos中，一个关键的简化是一旦处于内核模式就禁用了外部设备中断。外部中断由eflags的FL_IF位控制。虽然有多种方式可以修改该位，但由于jos的简化处理，我们仅需要在进入和退出用户模式的时候通过保存和恢复eflags寄存器来处理它即可。

1
Exercise 13. 修改kern/trapentry.S和kern/trap.c，初始化相关的IDT项，并提供IRQs 0-15的处理函数。然后修改kern/env.c的env_alloc()，在允许外部中断的情况下执行用户进程。当调用硬件中断处理函数的时候，处理器不会将错误码进栈，也不会检查IDT项的DPL。

相关资料可查询 section 9.2 of the 80386 Reference Manual 或 section 5.8 of the IA-32 Intel Architecture Software Developer’s Manual, Volume 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// kern/trapentry.S
// 处理器不会将错误码进栈
# IRQs 0    
TRAPHANDLER_NOEC(entry_point32,IRQ_OFFSET+IRQ_TIMER) 
# IRQs 1
TRAPHANDLER_NOEC(entry_point33,IRQ_OFFSET+IRQ_KBD) 
# IRQs 4
TRAPHANDLER_NOEC(entry_point36,IRQ_OFFSET+IRQ_SERIAL) 
# IRQs 7
TRAPHANDLER_NOEC(entry_point39,IRQ_OFFSET+IRQ_SPURIOUS) 
# IRQs 14
TRAPHANDLER_NOEC(entry_point46,IRQ_OFFSET+IRQ_IDE) 

// kern/trap.c, trap_init()
for (i = 0; i < 16; ++i){
	SETGATE(idt[IRQ_OFFSET+i], 0, GD_KT, entry_points[IRQ_OFFSET+i], 0);
}

// kern/env.c, env_alloc()
// 创建用户进程的时候设置允许中断标志，这样就可以在运行用户进程的时候通过中断来控制进程。
	e->env_tf.tf_eflags |= FL_IF;

Handling Clock Interrupts

lapic_init和pic_init进行了时钟和中断的相关设置，以生成中断。需要对中断进行相关处理。

1
Exercise 14. 修改trap_dispatch()函数，在每次触发时间中断的时候调用sched_yield()函数切换执行其他进程。测试案例为user/spin。

1
2
3
4
5
6
7
8
9
10
11
// trap_dispatch() 
	switch(tf->tf_trapno) {
	... 
	// Handle clock interrupts. Don't forget to acknowledge the
	// interrupt using lapic_eoi() before calling the scheduler!
	// LAB 4: Your code here.
 	case (IRQ_OFFSET + IRQ_TIMER):
 		lapic_eoi();
 		sched_yield();
		break;
	...

Inter-Process communication (IPC)

进程隔离和进程通信是两个重要课题，Unix的管道模型是典型的进程通信例子。进程间有许多通信模型，jos将实现一种简单的IPC机制。

IPC in JOS

jos实现的IPC机制是扩展系统调用接口sys_ipc_recv和sys_ipc_try_send，并实现库函数ipc_recv和ipc_send。jos的进程间通信信息包括两个部分：一个32位数和一个可选的页面映射。允许传递页面映射的做法一方面可以传递更多数据，一方面进程可以更方便地设置和安排内存共享。

Sending and Receiving Messages

进程希望接收消息时，调用sys_ipc_recv。该系统调用取消进程的执行，直到接收到消息。如果一个进行在等待接收消息，任何进程都可以发消息给它，而不局限于特定进程或有父子关系的进程。因此，Part A的权限检查不适用于IPC，因为IPC的设计确保进程A发送消息给进程B不能导致进程B发生故障。
进程希望发送消息时，调用sys_ipc_try_send，并传递目标进程号和参数。如果目标进程调用了sys_ipc_recv并且还没收到消息，系统调用将递交消息并返回0，否则返回-E_IPC_NOT_RECV。
库函数ipc_recv主要负责调用sys_ipc_recv和查找接收到的信息中所需要的部分。
库函数ipc_send主要负责重复调用sys_ipc_try_send，直至发送成功。

Transferring Pages

当进程携带dstva参数调用sys_ipc_recv时，表明它希望收到一个页映射。这样当发送者发送一个页时，接收者需要将dstva映射到自己的地址空间（如果原来已经有了页映射，则解除原来的映射）。
当进程携带srcva参数调用sys_ipc_try_send时，表明它希望将当前映射到srcva的页发送出去，权限是perm。发送成功后，发送者保持srcva的原有映射，接收者则有了新的页映射。从而达到共享页的目的。
如果发送者和接收者都没有指明要传递页，则没有页被传递。对于任何一个IPC，内核都会在接收者的Env结构体中的env_ipc_perm上设置接收页的权限。

1
Exercise 15. 实现kern/syscall.c的sys_ipc_recv和sys_ipc_try_send。调用envid2env的时候将checkperm设为0，表示任何进程都可以发送IPC消息。实现lib/ipc.c的ipc_recv和ipc_send。测试案例为user/pingpong和user/primes。

大体上的思路是：ipc_send负责调用sys_ipc_try_send，如果调用失败（如目标进程尚未准备好接收）则循环尝试，但为了不霸占资源，在循环体内调用sys_yield由内核选择进程的执行。目标进程尚未准备好接收的情况下尝试循环send，对其他返回的错误直接panic。原型为void ipc_send(envid_t to_env, uint32_t val, void *pg, int perm)，表示发送参数val，并将映射到pg的物理页映射到目标进程地址空间上，权限设为perm。
sys_ipc_try_send负责检查目标进程是否存在、目标进程是否准备好接收信息、目标进程是否要求接收页映射。如果目标进程要求接收页映射，则检查发送者提供的虚拟地址是否有效并页对齐、发送者提供的映射权限是否合理、发送者提供的虚拟地址是否有映射页、是否尝试将只读页映射为可写、是否尚有物理页可供接收者分配和映射，检查通过后将物理页映射到目标进程指定的虚拟地址上。最后设置目标进程env结构体相关参数，以说明由谁发送、接收的值是什么，更改目标进程接收信息标识为已接收，将目标进程设为可执行，解除其阻塞状态。原型为static int sys_ipc_try_send(envid_t envid, uint32_t value, void *srcva, unsigned perm)。
ipc_recv负责调用sys_ipc_recv，原型为int32_t ipc_recv(envid_t *from_env_store, void *pg, int *perm_store)，如果pg为空，代表接收者不希望接收页映射，否则表示希望发送者将页映射到pg上。调用sys_ipc_recv之后进程状态被更改为不可执行、阻塞，直至有进程发送消息给它并将其状态更改为可执行。接收到消息之后，存储发送者进程id以及映射权限，然后返回接收到的32位的ipc值。
sys_ipc_recv负责将给定的虚拟地址设置到env结构体的env_ipc_dstva上，表示希望发送者将页映射到其上，然后更改接收信息标识为等待接收，并更改进程的运行状态为不可执行。该系统调用将不会返回到用户模式，直至有发送者发送消息给它并解除其阻塞状态。

如果接收者要求接收页映射而发送者没有发送页映射，则出错；如果接收者不要求接收页映射而发送者发送页映射，不会出错。
接收者期望映射的虚拟地址不必与发送者发送的虚拟地址一致。
无需指定ipc_recv和ipc_send的先后调用顺序，因为即使接收者未准备好接收，发送者仍会判断sys_ipc_recv的返回结果，一旦是由于接收者未准备好接收而引起的错误，发送者会循环尝试发送。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void
ipc_send(envid_t to_env, uint32_t val, void *pg, int perm)
{
	// LAB 4: Your code here.
	//panic("ipc_send not implemented"); 
	int r; 
	if (!pg){
		pg = (void *)IPC_NOPAGE;
	}
	while((r = sys_ipc_try_send(to_env, val, pg, perm))){ 
		if(r == 0){
			break;
		}
		if(r != -E_IPC_NOT_RECV){
			panic("sys_ipc_try_send error, not -E_IPC_NOT_RECV, result: %d",r);
		}
		sys_yield();
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
static int
sys_ipc_try_send(envid_t envid, uint32_t value, void *srcva, unsigned perm)
{
	// LAB 4: Your code here.
	// panic("sys_ipc_try_send not implemented");
	struct Env *e; 
	int r = envid2env(envid,&e, 0);
	if(r<0) return r;//-E_BAD_ENV 
	// target is not blocked, waiting for an IPC.
	if(!e->env_ipc_recving) return -E_IPC_NOT_RECV;
	// if receiver asking for one page
	if ((uint32_t)e->env_ipc_dstva != IPC_NOPAGE && (uint32_t)e->env_ipc_dstva < UTOP) { 
		// if srcva < UTOP but srcva is not page-aligned.
		if((uint32_t)srcva >= UTOP || (uint32_t)srcva%PGSIZE != 0) return -E_INVAL;
		// if srcva < UTOP and perm is inappropriate
		if((perm & PTE_U) != PTE_U || (perm & PTE_P) != PTE_P) return -E_INVAL;
		//#define PTE_SYSCALL	(PTE_AVAIL | PTE_P | PTE_W | PTE_U)
		if ((perm & ~PTE_SYSCALL) != 0) //no other bits may be set
			return -E_INVAL;
		// if srcva < UTOP but srcva is not mapped in the caller's address space
		pte_t *pte_store;
		struct PageInfo *page = page_lookup(curenv->env_pgdir, srcva, &pte_store);
		if(page == NULL) return -E_INVAL;//no page mapped at srcva 
		// if (perm & PTE_W), but srcva is read-only in the current environment's address space
		if((perm & PTE_W) == PTE_W && (*pte_store & PTE_W) == 0) return -E_INVAL;

		// if there's not enough memory to map srcva in envid's address space
		// or if e->env_ipc_dstva invalid
        r = page_insert(e->env_pgdir, page, e->env_ipc_dstva, perm);
        if (r < 0) return r;// -E_NO_MEM
        e->env_ipc_perm = perm;
    }else{
    	e->env_ipc_perm = 0;
    } 
    e->env_ipc_recving = 0;
    e->env_ipc_from = curenv->env_id;
    e->env_ipc_value = value;
    e->env_status = ENV_RUNNABLE;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
int32_t
ipc_recv(envid_t *from_env_store, void *pg, int *perm_store)
{
	// LAB 4: Your code here.
	//panic("ipc_recv not implemented"); 
	if(!pg) pg = (void *)IPC_NOPAGE;
	int r = sys_ipc_recv(pg);
	if(r < 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static int
sys_ipc_recv(void *dstva)
{
	// LAB 4: Your code here.
	//panic("sys_ipc_recv not implemented");
	// if dstva < UTOP but dstva is not page-aligned.
	if((uint32_t)dstva == IPC_NOPAGE){
		curenv->env_ipc_dstva = (void*)IPC_NOPAGE; 
	}else if((uint32_t)dstva >= UTOP || (uint32_t)dstva%PGSIZE != 0) {
		return -E_INVAL;
	}else{
		curenv->env_ipc_dstva = dstva;
	}
	curenv->env_ipc_recving = 1;
	curenv->env_status = ENV_NOT_RUNNABLE;
	return 0;
}
1
Challenge! 为何ipc_send需要循环尝试发送?

原因见上分析。

1
Challenge! prime sieve只是大量并发程序之间消息传递的一种灵巧应用。阅读 C. A. R. Hoare, ``Communicating Sequential Processes,'' Communications of the ACM 21(8) (August 1978), 666-667 ，实现矩阵乘法的例子。

1
Challenge! Doug McIlroy开发的幂级数计算器是典型的消息传递例子，阅读  M. Douglas McIlroy, ``Squinting at Power Series,'' Software--Practice and Experience, 20(7) (July 1990), 661-683 (http://plan9.bell-labs.com/who/rsc/thread/squint.pdf)，实现该计算器并计算sin(x+x^3)的幂级数。
1
Challenge! 阅读 Improving IPC by Kernel Design (http://dl.acm.org/citation.cfm?id=168633)，改进jos的IPC效率。可扩展系统调用接口。
显示 Gitment 评论